Returns whether a directed graph is consistent.

@param g
a <code>DirectedGraph</code>.
@return <code>true</code> if the given graph is consistent,
<code>false</code> otherwise.
172400
static boolean getConsistent(DirectedGraph g) {
        Object[] vertexOrdering = new Object[g.size()];
        int voa = 0;
        for (Iterator<?> itr = g.iterator(); itr.hasNext(); voa++) {
            vertexOrdering[voa] = itr.next();
        }
        int vol = vertexOrdering.length;
        Weight[][] updatedEdges = new Weight[vol][vol];
        for (int k = vol - 1; k > 1; k--) {
            Object vk = vertexOrdering[k];
            for (int i = 0; i < k; i++) {
                Object vi = vertexOrdering[i];
                Weight wik = getWeight(i, k, vi, vk, g, updatedEdges);
                if (wik != null) {
                    /*
                     * wki may be different from wik, so we can't just get the
                     * inverse of wik.
                     */
                    Weight wki = getWeight(k, i, vk, vi, g, updatedEdges);
                    // i > j because we evaluate the vertices in order.
                    for (int j = i + 1; j < k; j++) {
                        Object vj = vertexOrdering[j];
                        Weight wjk = getWeight(j, k, vj, vk, g, updatedEdges);
                        if (wjk != null) {
                            Weight wkj = getWeight(k, j, vk, vj, g,
                                    updatedEdges);
                            Weight wikj = wik.add(wkj);
                            Weight wjki = wjk.add(wki);
                            Weight wij = getWeight(i, j, vi, vj, g,
                                    updatedEdges);
                            Weight wji = getWeight(j, i, vj, vi, g,
                                    updatedEdges);
                            Weight iwjki = wjki.invertSign();
                            Weight iwji = null;
                            if (wji != null) {
                                iwji = wji.invertSign();
                            }
                            if (wij != null) {
                                Weight intersectionMin = Weight.max(iwji, iwjki);
                                Weight intersectionMax = Weight.min(wij, wikj);
                                if (intersectionMin.compareTo(intersectionMax) > 0) {
                                    return false;
                                }
                                updatedEdges[i][j] = intersectionMax;
                                updatedEdges[j][i] = intersectionMin.invertSign();
                            } else {
                                updatedEdges[i][j] = wikj;
                                updatedEdges[j][i] = wjki;
                            }
                        }
                    }
                }
            }
        }

        return true;
    }
32300
protected Integer compatibilityGraphNodesIfCEdgeIsZero() throws IOException {

        int countNodes = 1;
        List<String> map = new ArrayList<String>();
        compGraphNodesCZero = new ArrayList<Integer>(); //Initialize the compGraphNodesCZero List
        LabelContainer labelContainer = LabelContainer.getInstance();
        compGraphNodes.clear();

        for (int i = 0; i < source.getAtomCount(); i++) {
            for (int j = 0; j < target.getAtomCount(); j++) {
                IAtom atom1 = source.getAtom(i);
                IAtom atom2 = target.getAtom(j);

                //You can also check object equal or charge, hydrogen count etc

                if (atom1.getSymbol().equalsIgnoreCase(atom2.getSymbol()) && (!map.contains(i + "_" + j))) {
                    compGraphNodesCZero.add(i);
                    compGraphNodesCZero.add(j);
                    compGraphNodesCZero.add(labelContainer.getLabelID(atom1.getSymbol())); //i.e C is label 1
                    compGraphNodesCZero.add(countNodes);
                    compGraphNodes.add(i);
                    compGraphNodes.add(j);
                    compGraphNodes.add(countNodes++);
                    map.add(i + "_" + j);
                }
            }
        }
        map.clear();
        return countNodes;
    }
798219
static int[] rank(final int[][] g) {
        final int ord = g.length;

        final int[] count = new int[ord + 1];
        final int[] rank = new int[ord];

        // frequency of each degree
        for (int v = 0; v < ord; v++)
            count[g[v].length + 1]++;
        // cumulated counts
        for (int i = 0; count[i] < ord; i++)
            count[i + 1] += count[i];
        // store sorted position of each vertex
        for (int v = 0; v < ord; v++)
            rank[v] = count[g[v].length]++;

        return rank;
    }
1288974
function(){
            var isPositive = false,
                num = this.vertices.length,
                prev,
                next,
                d0,
                d1,
                newIsP;

            for( var i = 0; i < num; i++ ){
                prev = (i===0) ? num -1 : i - 1;
                next = (i===num-1) ? 0 : i + 1;
                d0 = this.vertices[i].sub(this.vertices[prev]);
                d1 = this.vertices[next].sub(this.vertices[i]);
                newIsP = (d0.cross(d1) > 0);
                if( i === 0 ) {
                    isPositive = true;
                } else if( isPositive != newIsP ) {
                    return false;
                }
            }
            return true;
        }
955374
def _check_graph(self, graph):
        """"""
        if graph.num_vertices != self.size:
            raise TypeError("The number of vertices in the graph does not "
                "match the length of the atomic numbers array.")
        # In practice these are typically the same arrays using the same piece
        # of memory. Just checking to be sure.
        if (self.numbers != graph.numbers).any():
            raise TypeError("The atomic numbers in the graph do not match the "
                "atomic numbers in the molecule.")
1088247
function(g) {
    this.isDag = true;
    this.sorted = topoSort(uniqueVertexs(g.edges()), g.edges());
}
120639
boolean arbitaryMatching(final int[][] graph, final BitSet subset) {

        final BitSet unmatched = new BitSet();

        // indicates the deg of each vertex in unmatched subset
        final int[] deg = new int[graph.length];

        // queue/stack of vertices with deg1 vertices
        final int[] deg1 = new int[graph.length];
        int nd1 = 0, nMatched = 0;

        for (int v = subset.nextSetBit(0); v >= 0; v = subset.nextSetBit(v + 1)) {
            if (matched(v)) {
                assert subset.get(other(v));
                nMatched++;
                continue;
            }
            unmatched.set(v);
            for (int w : graph[v])
                if (subset.get(w) && unmatched(w)) deg[v]++;
            if (deg[v] == 1) deg1[nd1++] = v;
        }

        while (!unmatched.isEmpty()) {

            int v = -1;

            // attempt to select a vertex with degree = 1 (in matched set)
            while (nd1 > 0) {
                v = deg1[--nd1];
                if (unmatched.get(v)) break;
            }

            // no unmatched degree 1 vertex, select the first unmatched
            if (v < 0 || unmatched.get(v)) v = unmatched.nextSetBit(0);

            unmatched.clear(v);

            // find a unmatched edge and match it, adjacent degrees are updated
            for (final int w : graph[v]) {
                if (unmatched.get(w)) {
                    match(v, w);
                    nMatched += 2;
                    unmatched.clear(w);
                    // update neighbors of w and v (if needed)
                    for (final int u : graph[w])
                        if (--deg[u] == 1 && unmatched.get(u)) deg1[nd1++] = u;

                    // if deg == 1, w is the only neighbor
                    if (deg[v] > 1) {
                        for (final int u : graph[v])
                            if (--deg[u] == 1 && unmatched.get(u)) deg1[nd1++] = u;
                    }
                    break;
                }
            }
        }

        return nMatched == subset.cardinality();
    }
595397
private static boolean isInChain(Group g) {
		ChemComp chemComp = g.getChemComp();

		if (chemComp==null) {
			logger.warn("Warning: can't determine PolymerType for group "+g.getResidueNumber()+" ("+g.getPDBName()+"). Will consider it as non-nucleotide/non-protein type.");
			return false;
		}

		PolymerType polyType = chemComp.getPolymerType();
		for (PolymerType protOnlyType: PolymerType.PROTEIN_ONLY) {
			if (polyType==protOnlyType) return true;
		}
		for (PolymerType protOnlyType: PolymerType.POLYNUCLEOTIDE_ONLY) {
			if (polyType==protOnlyType) return true;
		}

		return false;
	}
965402
private boolean checkAllPathsWithoutBackEdges(DiGraphNode<N, E> a,
      DiGraphNode<N, E> b) {
    if (nodePredicate.apply(a.getValue()) &&
        (inclusive || (a != start && a != end))) {
      return true;
    }
    if (a == b) {
      return false;
    }
    for (DiGraphEdge<N, E> e : a.getOutEdges()) {
      // Once we visited that edge once, we no longer need to
      // re-visit it again.
      if (e.getAnnotation() == VISITED_EDGE) {
        continue;
      }
      e.setAnnotation(VISITED_EDGE);

      if (ignoreEdge(e)) {
        continue;
      }
      if (e.getAnnotation() == BACK_EDGE) {
        continue;
      }

      DiGraphNode<N, E> next = e.getDestination();
      if (!checkAllPathsWithoutBackEdges(next, b)) {
        return false;
      }
    }
    return true;
  }
685700
public int getCount(G g) {
        Pair<Integer> orderAndSize = new Pair<Integer>(g.order(), g.size());
        Map<G,Integer> graphs = orderAndSizeToGraphs.get(orderAndSize);
        if (graphs == null) 
            return 0;
        for (Map.Entry<G,Integer> e : graphs.entrySet()) {
            if (isoTest.areIsomorphic(g, e.getKey())) 
                return e.getValue();
        }
        return 0;
    }
216743
public boolean isWeaklyConnected() {

		final AbstractJobVertex[] reachable = getAllReachableJobVertices();
		final AbstractJobVertex[] all = getAllJobVertices();

		// Check if number if reachable vertices matches number of registered vertices
		if (reachable.length != all.length) {
			return false;
		}

		final HashMap<JobVertexID, AbstractJobVertex> tmp = new HashMap<JobVertexID, AbstractJobVertex>();
		for (int i = 0; i < reachable.length; i++) {
			tmp.put(reachable[i].getID(), reachable[i]);
		}

		// Check if all is subset of reachable
		for (int i = 0; i < all.length; i++) {
			if (!tmp.containsKey(all[i].getID())) {
				return false;
			}
		}

		// Check if reachable is a subset of all
		for (int i = 0; i < reachable.length; i++) {
			if (!includedInJobGraph(reachable[i].getID())) {
				return false;
			}
		}

		return true;
	}
188155
def is_cyclic(graph):
    
    path = set()

    def visit(vertex):
        path.add(vertex)
        for neighbour in graph.get(vertex, ()):
            if neighbour in path or visit(neighbour):
                return True
        path.remove(vertex)
        return False

    return any(visit(v) for v in graph)
294876
private void dfs(Visitor visitor, int v, int[] cc, int id) {
        visitor.visit(v);
        cc[v] = id;
        for (Edge edge : graph[v]) {
            int t = edge.v2;
            if (!digraph && t == v) {
                t = edge.v1;
            }

            if (cc[t] == -1) {
                dfs(visitor, t, cc, id);
            }
        }
    }
1041305
public static Graph sortDFS(Graph g, Graph sortedGraph) {
        int nodes = g.getNodes();
        final GHIntArrayList list = new GHIntArrayList(nodes);
        list.fill(nodes, -1);
        final GHBitSetImpl bitset = new GHBitSetImpl(nodes);
        final AtomicInteger ref = new AtomicInteger(-1);
        EdgeExplorer explorer = g.createEdgeExplorer();
        for (int startNode = 0; startNode >= 0 && startNode < nodes;
             startNode = bitset.nextClear(startNode + 1)) {
            new DepthFirstSearch() {
                @Override
                protected GHBitSet createBitSet() {
                    return bitset;
                }

                @Override
                protected boolean goFurther(int nodeId) {
                    list.set(nodeId, ref.incrementAndGet());
                    return super.goFurther(nodeId);
                }
            }.start(explorer, startNode);
        }
        return createSortedGraph(g, sortedGraph, list);
    }
13178
@Override
	public boolean validate(Graph<K, VV, EV> graph) throws Exception {
		DataSet<Tuple1<K>> edgeIds = graph.getEdges()
				.flatMap(new MapEdgeIds<>()).distinct();
		DataSet<K> invalidIds = graph.getVertices().coGroup(edgeIds).where(0)
				.equalTo(0).with(new GroupInvalidIds<>()).first(1);

		return invalidIds.map(new KToTupleMap<>()).count() == 0;
	}
722804
public static <T> List<T> getParents(DirectedGraph g, T n) {
        List<IndexedEdge> incoming = new ArrayList(g.incomingEdgesOf(n));
        Collections.sort(incoming);
        List<T> ret = new ArrayList();
        for(IndexedEdge e: incoming) {
            ret.add((T)e.source);
        }        
        return ret;
    }
420710
public static function isRegular(Graph $g){
	        
	        $allVertices = $g->getVertexSet();

	        $degree = -1;
	        
	        foreach($allVertices as $vertex){
	            if($degree != -1){
	                if($g->degreeOf($vertex) != $degree)
	                    return false;
	            }
	            else $degree = $g->degreeOf($vertex);
	        }
	        
	        return true;
	    }