Mutual-accessibility matrix (strongly connected components).

    @type  graph: graph, digraph
    @param graph: Graph.

    @rtype:  dictionary
    @return: Mutual-accessibility information for each node.
13891
def mutual_accessibility(graph):
    
    recursionlimit = getrecursionlimit()
    setrecursionlimit(max(len(graph.nodes())*2,recursionlimit))
    
    mutual_access = {}
    stack = []
    low = {}
        
    def visit(node):
        if node in low:
            return

        num = len(low)
        low[node] = num
        stack_pos = len(stack)
        stack.append(node)
        
        for successor in graph.neighbors(node):
            visit(successor)
            low[node] = min(low[node], low[successor])
        
        if num == low[node]:
            component = stack[stack_pos:]
            del stack[stack_pos:]
            component.sort()
            for each in component:
                mutual_access[each] = component

            for item in component:
                low[item] = len(graph)
    
    for node in graph:
        visit(node)
    
    setrecursionlimit(recursionlimit)
    return mutual_access
161518
def graph_isolated_nodes(self):
        
        return sorted(nx.isolates(self._graph), key=lambda x: repr(x))
440477
def reverse(self):
        
        assert self.DIRECTED, "Undirected graph types such as %s cannot be reversed" % self.__class__.__name__
        
        N = self.__class__()
    
        #- Add the nodes
        N.add_nodes( n for n in self.nodes() )
    
        #- Add the reversed edges
        for (u, v) in self.edges():
            wt = self.edge_weight((u, v))
            label = self.edge_label((u, v))
            attributes = self.edge_attributes((u, v))
            N.add_edge((v, u), wt, label, attributes)
        return N
522223
def get_connected_components_as_subgraphs(graph):
    
    components = get_connected_components(graph)

    list_of_graphs = []

    for c in components:
        edge_ids = set()
        nodes = [graph.get_node(node) for node in c]
        for n in nodes:
            # --Loop through the edges in each node, to determine if it should be included
            for e in n['edges']:
                # --Only add the edge to the subgraph if both ends are in the subgraph
                edge = graph.get_edge(e)
                a, b = edge['vertices']
                if a in c and b in c:
                    edge_ids.add(e)
        # --Build the subgraph and add it to the list
        list_of_edges = list(edge_ids)
        subgraph = make_subgraph(graph, c, list_of_edges)
        list_of_graphs.append(subgraph)

    return list_of_graphs
729125
private void dfs(int v, int[] cc, int id) {
        cc[v] = id;
        for (Edge edge : graph[v]) {
            int t = edge.v2;
            if (!digraph && t == v) {
                t = edge.v1;
            }

            if (cc[t] == -1) {
                dfs(t, cc, id);
            }
        }
    }
17136
def graph_from_adjacency_matrix(matrix, node_prefix='', directed=False):
    

    node_orig = 1

    if directed:
        graph = Dot(graph_type='digraph')
    else:
        graph = Dot(graph_type='graph')

    for row in matrix:
        if not directed:
            skip = matrix.index(row)
            r = row[skip:]
        else:
            skip = 0
            r = row
        node_dest = skip + 1

        for e in r:
            if e:
                graph.add_edge(
                    Edge(
                        node_prefix + node_orig,
                        node_prefix + node_dest))
            node_dest += 1
        node_orig += 1

    return graph
550155
def graph(self):
        
        if not hasattr(self, '_graph') or self._graph is None:
            self._graph = ConjunctiveGraph(store=self.store,
                                           identifier=self.base_uri)
        return self._graph
484649
def bipartite_as_graph(self) -> Graph:  # pragma: no cover
        """"""
        if Graph is None:
            raise ImportError('The graphviz package is required to draw the graph.')
        graph = Graph()
        nodes_left = {}  # type: Dict[TLeft, str]
        nodes_right = {}  # type: Dict[TRight, str]
        node_id = 0
        for (left, right), value in self.bipartite._edges.items():
            if left not in nodes_left:
                name = 'node{:d}'.format(node_id)
                nodes_left[left] = name
                label = str(self.subjects_by_id[left])
                graph.node(name, label=label)
                node_id += 1
            if right not in nodes_right:
                name = 'node{:d}'.format(node_id)
                nodes_right[right] = name
                label = str(self.automaton.patterns[right][0])
                graph.node(name, label=label)
                node_id += 1
            edge_label = value is not True and str(value) or ''
            graph.edge(nodes_left[left], nodes_right[right], edge_label)
        return graph
1018052
def get_connected_components(graph):
    

    list_of_components = []
    component = []  # Not strictly necessary due to the while loop structure, but it helps the automated analysis tools

    # Store a list of all unreached vertices
    unreached = set(graph.get_all_node_ids())
    to_explore = deque()

    while len(unreached) > 0:
        # This happens when we reach the end of a connected component and still have more vertices to search through
        if len(to_explore) == 0:
            n = unreached.pop()
            unreached.add(n)
            to_explore.append(n)
            component = []
            list_of_components.append(component)

        # This is the BFS that searches for connected vertices
        while len(to_explore) > 0:
            n = to_explore.pop()
            if n in unreached:
                component.append(n)
                unreached.remove(n)
                nodes = graph.neighbors(n)
                for n in nodes:
                    if n in unreached:
                        to_explore.append(n)

    return list_of_components
863478
def graph(self):
        
        g = networkx.MultiDiGraph()
        edge_list = [(x.knob_helix, x.hole_helix, x.id, {'kih': x}) for x in self.get_monomers()]
        g.add_edges_from(edge_list)
        return g
457277
def get_digraph(ont, relations=None, writecache=False):
    
    digraph = networkx.MultiDiGraph()
    logging.info("Getting edges (may be cached)")
    for (s,p,o) in get_edges(ont):
        p = map_legacy_pred(p)
        if relations is None or p in relations:
            digraph.add_edge(o,s,pred=p)
    logging.info("Getting labels (may be cached)")
    for (n,label) in fetchall_labels(ont):
        digraph.add_node(n, **{'label':label})
    return digraph
25788
def connected_components(G):
    
    result = []
    vertices = set(G.vertices)
    while vertices:
        n = vertices.pop()
        group = {n}
        queue = Queue()
        queue.put(n)
        while not queue.empty():
            n = queue.get()
            neighbors = set(G.vertices[n])
            neighbors.difference_update(group)
            vertices.difference_update(neighbors)
            group.update(neighbors)
            for element in neighbors:
                queue.put(element)
        result.append(group)
    return result
816114
def convert_graph_directed_to_undirected(dg):
    """"""

    udg = UndirectedGraph()

    # Copy the graph
    # --Copy nodes
    # --Copy edges
    udg.nodes = copy.deepcopy(dg.nodes)
    udg.edges = copy.deepcopy(dg.edges)
    udg.next_node_id = dg.next_node_id
    udg.next_edge_id = dg.next_edge_id

    # Convert the directed edges into undirected edges
    for edge_id in udg.get_all_edge_ids():
        edge = udg.get_edge(edge_id)
        target_node_id = edge['vertices'][1]
        target_node = udg.get_node(target_node_id)
        target_node['edges'].append(edge_id)

    return udg
567281
def get_idb_graph():
    
    digraph = nx.DiGraph()

    for function in functions():
        for xref in itertools.chain(function.xrefs_from, function.xrefs_to):
            frm = _try_get_function_start(xref.frm)
            to = _try_get_function_start(xref.to)

            digraph.add_edge(frm, to)

    return digraph
206266
public static <TT> EquivalencesDAGImpl<TT> getEquivalencesDAG(DefaultDirectedGraph<TT,DefaultEdge> graph) {
		
		// each set contains vertices which together form a strongly connected
		// component within the given graph		
		GabowSCC<TT, DefaultEdge> inspector = new GabowSCC<>(graph);
		List<Equivalences<TT>> equivalenceSets = inspector.stronglyConnectedSets();

		// create the vertex index
		
		ImmutableMap.Builder<TT, Equivalences<TT>> vertexIndexBuilder = new ImmutableMap.Builder<>();
		for (Equivalences<TT> equivalenceSet : equivalenceSets) {
			for (TT node : equivalenceSet) 
				vertexIndexBuilder.put(node, equivalenceSet);
		}
		ImmutableMap<TT, Equivalences<TT>> vertexIndex = vertexIndexBuilder.build();
		
		// compute the edges between the SCCs
		
		Map<Equivalences<TT>, Set<Equivalences<TT>>> outgoingEdges = new HashMap<>();
		
		for (DefaultEdge edge : graph.edgeSet()) {
			Equivalences<TT> v1 = vertexIndex.get(graph.getEdgeSource(edge));
			Equivalences<TT> v2 = vertexIndex.get(graph.getEdgeTarget(edge));
			if (v1 == v2)
				continue; // do not add loops
			
			Set<Equivalences<TT>> out = outgoingEdges.get(v1);
			if (out == null) {
				out = new HashSet<>();
				outgoingEdges.put(v1, out);
			}
			out.add(v2);
		}

		// compute the transitively reduced DAG
		
		SimpleDirectedGraph<Equivalences<TT>,DefaultEdge> dag = new SimpleDirectedGraph<>(DefaultEdge.class);
		for (Equivalences<TT> equivalenceSet : equivalenceSets)  
			dag.addVertex(equivalenceSet);
		
		for (Map.Entry<Equivalences<TT>, Set<Equivalences<TT>>> edges : outgoingEdges.entrySet()) {
			Equivalences<TT> v1 = edges.getKey();
			for (Equivalences<TT> v2 : edges.getValue()) {
				// an edge from v1 to v2 is redundant if 
				//  v1 has an edge going to a vertex v2p 
				//         from which v2 is reachable (in one step) 
				boolean redundant = false;
				if (edges.getValue().size() > 1) {
	 				for (Equivalences<TT> v2p : edges.getValue()) {
						Set<Equivalences<TT>> t2p = outgoingEdges.get(v2p);
						if (t2p!= null && t2p.contains(v2)) {
							redundant = true;
							break;
						}	
					}
				}
				if (!redundant)
					dag.addEdge(v1, v2);
			}
		}
		
		return new EquivalencesDAGImpl<>(graph, dag, vertexIndex, vertexIndex);
	}
320569
def connected_components(self) -> (dict, dict):
        """"""
        inclusions = utils.completed_graph(self.inclusions)  # allow bottom-up movement
        edges = utils.completed_graph(self.edges) if self.oriented else self.edges
        cc = {}  # maps cc root with nodes in the cc
        subroots = defaultdict(set)  # maps cc root with other roots of the cc
        walked_roots = set()  # all roots that have been walked already
        for root in self.roots:
            if root in walked_roots: continue  # this cc have been done already
            # walk in the graph starting at root
            cc[root] = set([root])
            walked = cc[root]
            stack = list(edges.get(root, ())) + list(inclusions.get(root, ()))
            while len(stack) > 0:
                *stack, curr = stack
                walked.add(curr)
                if curr in self.roots:  # don't do the walk for already found roots
                    walked_roots.add(curr)
                    subroots[root].add(curr)
                for succ in it.chain(edges.get(curr, ()), inclusions.get(curr, ())):
                    if succ not in walked:
                        stack.append(succ)
        return cc, dict(subroots)
105725
def graph(self, **kw):
        
        self.name = kw.get('name', 'G')
        self.fillcolor = kw.get('fillcolor', '#ffffff')
        self.fontcolor = kw.get('fontcolor', '#000000')
        self.rankdir = kw.get('rankdir', 'BT' if self.reverse else 'TB')
        if kw.get('concentrate', True):
            self.concentrate = 'concentrate = true;'
        else:
            self.concentrate = ''
        self.dedent("""
            digraph {self.name} {{
                {self.concentrate}
                rankdir = {self.rankdir};
                node [style=filled,fillcolor="{self.fillcolor}",fontcolor="{self.fontcolor}",fontname=Helvetica,fontsize=10];

        """.format(self=self))
        yield
        self.writeln('}')