Find all connected components of graph by performing one dfs
Complexity : O(M+N) light and fast in practice
180108
public void findAllCC() {
		if (nodeCC == null) {
			CCFirstNode = new int[n];
			CCNextNode = new int[n];
			nodeCC = new int[n];
			sizeCC = new int[n];
		}
		sizeMinCC = 0;
		sizeMaxCC = 0;
		ISet act = graph.getNodes();
		for (int i : act) {
			p[i] = -1;
		}
		for (int i = 0; i < CCFirstNode.length; i++) {
			CCFirstNode[i] = -1;
			sizeCC[i] = -1;
		}
		int cc = 0;
		for (int i : act) {
			if (p[i] == -1) {
				findCC(i, cc);
				if (sizeMinCC == 0 || sizeMinCC > sizeCC[cc]) {
					sizeMinCC = sizeCC[cc];
				}
				if (sizeMaxCC < sizeCC[cc]) {
					sizeMaxCC = sizeCC[cc];
				}
				cc++;
			}
		}
		nbCC = cc;
	}
113381
def determine_network_topology(self):
        

        adjacency_matrix = self.adjacency_matrix(self.passive_branch_components)
        n_components, labels = csgraph.connected_components(adjacency_matrix, directed=False)

        # remove all old sub_networks
        for sub_network in self.sub_networks.index:
            obj = self.sub_networks.at[sub_network,"obj"]
            self.remove("SubNetwork", sub_network)
            del obj

        for i in np.arange(n_components):
            # index of first bus
            buses_i = (labels == i).nonzero()[0]
            carrier = self.buses.carrier.iat[buses_i[0]]

            if carrier not in ["AC","DC"] and len(buses_i) > 1:
                logger.warning("Warning, sub network {} is not electric but contains multiple buses\n"
                                "and branches. Passive flows are not allowed for non-electric networks!".format(i))

            if (self.buses.carrier.iloc[buses_i] != carrier).any():
                logger.warning("Warning, sub network {} contains buses with mixed carriers! Value counts:\n{}".format(i),
                                self.buses.carrier.iloc[buses_i].value_counts())

            self.add("SubNetwork", i, carrier=carrier)

        #add objects
        self.sub_networks["obj"] = [SubNetwork(self, name) for name in self.sub_networks.index]

        self.buses.loc[:, "sub_network"] = labels.astype(str)

        for c in self.iterate_components(self.passive_branch_components):
            c.df["sub_network"] = c.df.bus0.map(self.buses["sub_network"])
713236
def dfs(graph, func, head, reverse=None):
    
    todo = deque()
    todo.append(head)
    path = deque()
    done = set()
    while todo:
        node = todo.popleft()
        if node in done:
            path.pop()
            continue

        done.add(node)
        path.append(node)
        result = func(node, path, graph)
        if result:
            if reverse:
                children = graph.get_parents(node)
            else:
                children = graph.get_children(node)
            todo.extend(children)
243113
def _connected(cm, nodes, connection):
    """"""
    if nodes is not None:
        cm = cm[np.ix_(nodes, nodes)]

    num_components, _ = connected_components(cm, connection=connection)
    return num_components < 2
908676
def _parse_loops_from_graph(self, graph):
        
        outtop = []
        outall = []
        for subg in networkx.strongly_connected_component_subgraphs(graph):
            if len(subg.nodes()) == 1:
                if len(list(subg.successors(list(subg.nodes())[0]))) == 0:
                    continue
            thisloop, allloops = self._parse_loop_graph(subg, graph)
            if thisloop is not None:
                outall += allloops
                outtop.append(thisloop)
        return outtop, outall
398726
private Set<Integer> getSuccessors(Graph g, Integer vertex) {
        if (g instanceof DirectedGraph) {
            DirectedGraph<?> dg = (DirectedGraph)g;
            return dg.successors(vertex);
        }
        else
            return Collections.<Integer>emptySet();
    }
299671
private void compute() {

        int n = graph.length;

        // the set 'S' contains the pairs of vertices adjacent to 'y'
        int[] s = new int[n];
        int sizeOfS;

        // order the vertices by degree
        int[] vertices = new int[n];
        for (int v = 0; v < n; v++) {
            vertices[ordering[v]] = v;
        }

        // if the graph is known to be a biconnected component (prepossessing)
        // and there is at least one vertex with a degree > 2 we can skip all
        // vertices of degree 2.
        //
        // otherwise the smallest possible cycle is {0,1,2} (no parallel edges
        // or loops) we can therefore don't need to do the first two shortest
        // paths calculations
        int first = biconnected && nDeg2Vertices < n ? nDeg2Vertices : 2;

        for (int i = first; i < n; i++) {
            final int r = vertices[i];

            ShortestPaths pathsFromR = new ShortestPaths(graph, null, r, limit / 2, ordering);

            // we only check the vertices which belong to the set Vr. this
            // set is vertices reachable from 'r' by only travelling though
            // vertices smaller then r. In the ShortestPaths API this is
            // name 'isPrecedingPathTo'.
            //
            // using Vr allows us to prune the number of vertices to check and
            // discover each cycle exactly once. This is possible as for each
            // simple cycle there is only one vertex with a maximum ordering.
            for (int j = 0; j < i; j++) {
                final int y = vertices[j];
                if (!pathsFromR.isPrecedingPathTo(y)) continue;

                // start refilling set 's' by resetting it's size
                sizeOfS = 0;

                // z is adjacent to y and belong to Vr
                for (final int z : graph[y]) {
                    if (!pathsFromR.isPrecedingPathTo(z)) continue;

                    final int distToZ = pathsFromR.distanceTo(z);
                    final int distToY = pathsFromR.distanceTo(y);

                    // the distance of the path to z is one less then the
                    // path to y. the vertices are adjacent, therefore z must
                    // also belong to the shortest path from r to y.
                    //
                    // we queue up (in 's') all the vertices adjacent to y for
                    // which this holds and then check these once we've processed
                    // all adjacent vertices
                    //
                    //  / ¯ ¯ z1 \          z1 and z2 are added to 's' and
                    // r          y - z3    checked later as p and q (see below)
                    //  \ _ _ z2 /
                    //
                    if (distToZ + 1 == distToY) {
                        s[sizeOfS++] = z;
                    }

                    // if the distances are equal we could have an odd cycle
                    // but we need to check the paths only intersect at 'r'.
                    //
                    // we check the intersect for cases like this, shortest
                    // cycle here is {p .. y, z .. p} not {r .. y, z .. r}
                    //
                    //           / ¯ ¯ y         / ¯ ¯ \ / ¯ ¯ y
                    //  r - - - p      |    or  r       p      |
                    //           \ _ _ z         \ _ _ / \ _ _ z
                    //
                    // if it's the shortest cycle then the intersect is just {r}
                    //
                    //  / ¯ ¯ y
                    // r      |
                    //  \ _ _ z
                    //
                    else if (distToZ == distToY && ordering[z] < ordering[y]) {
                        final int[] pathToY = pathsFromR.pathTo(y);
                        final int[] pathToZ = pathsFromR.pathTo(z);
                        if (singletonIntersect(pathToZ, pathToY)) {
                            Cycle cycle = new OddCycle(pathsFromR, pathToY, pathToZ);
                            add(cycle);
                        }
                    }
                }

                // check each pair vertices adjacent to 'y' for an
                // even cycle, as with the odd cycle we ensure the intersect
                // of the paths {r .. p} and {r .. q} is {r}.
                //
                //  / ¯ ¯ p \
                // r         y
                //  \ _ _ q /
                //
                for (int k = 0; k < sizeOfS; k++) {
                    for (int l = k + 1; l < sizeOfS; l++) {
                        int[] pathToP = pathsFromR.pathTo(s[k]);
                        int[] pathToQ = pathsFromR.pathTo(s[l]);
                        if (singletonIntersect(pathToP, pathToQ)) {
                            Cycle cycle = new EvenCycle(pathsFromR, pathToP, y, pathToQ);
                            add(cycle);
                        }
                    }
                }
            }
        }
    }
746468
def euler_tour_dfs(G, source=None):
    
    if source is None:
        # produce edges for all components
        nodes = G
    else:
        # produce edges for components with source
        nodes = [source]
    yielder = []
    visited = set()
    for start in nodes:
        if start in visited:
            continue
        visited.add(start)
        stack = [(start, iter(G[start]))]
        while stack:
            parent, children = stack[-1]
            try:
                child = next(children)
                if child not in visited:
                    # yielder += [[parent, child]]
                    yielder += [parent]
                    visited.add(child)
                    stack.append((child, iter(G[child])))
            except StopIteration:
                if stack:
                    last = stack[-1]
                    yielder += [last[0]]
                stack.pop()
    return yielder
1171451
def cut_nodes_edges(graph):
    
    n = len(graph)
    time = 0
    num = [None] * n
    low = [n] * n
    father = [None] * n        # father[v] = None if root else father of v
    critical_childs = [0] * n  # c_c[u] = #childs v s.t. low[v] >= num[u]
    times_seen = [-1] * n
    for start in range(n):
        if times_seen[start] == -1:               # init DFS path
            times_seen[start] = 0
            to_visit = [start]
            while to_visit:
                node = to_visit[-1]
                if times_seen[node] == 0:         # start processing
                    num[node] = time
                    time += 1
                    low[node] = float('inf')
                children = graph[node]
                if times_seen[node] == len(children):  # end processing
                    to_visit.pop()
                    up = father[node]            # propagate low to father
                    if up is not None:
                        low[up] = min(low[up], low[node])
                        if low[node] >= num[up]:
                            critical_childs[up] += 1
                else:
                    child = children[times_seen[node]]   # next arrow
                    times_seen[node] += 1
                    if times_seen[child] == -1:   # not visited yet
                        father[child] = node      # link arrow
                        times_seen[child] = 0
                        to_visit.append(child)    # (below) back arrow
                    elif num[child] < num[node] and father[node] != child:
                        low[node] = min(low[node], num[child])
    cut_edges = []
    cut_nodes = []                                # extract solution
    for node in range(n):
        if father[node] is None:                  # characteristics
            if critical_childs[node] >= 2:
                cut_nodes.append(node)
        else:                                     # internal nodes
            if critical_childs[node] >= 1:
                cut_nodes.append(node)
            if low[node] >= num[node]:
                cut_edges.append((father[node], node))
    return cut_nodes, cut_edges
155468
def find_max_matching(graph):
    
    left = list(graph)
    pair = defaultdict(lambda: None)
    dist = defaultdict(lambda: None)
    q = deque()

    full_graph = graph.copy()
    for v in left:
        for n in graph[v]:
            full_graph[n].add(v)

    def bfs():
        for v in left:
            if pair[v] is None:
                dist[v] = 0
                q.append(v)
            else:
                dist[v] = None

        dist[None] = None

        while q:
            v = q.popleft()
            if v is not None:
                for u in full_graph[v]:
                    if dist[pair[u]] is None:
                        dist[pair[u]] = dist[v] + 1
                        q.append(pair[u])

        return dist[None] is not None

    def dfs(v):
        if v is not None:
            for u in full_graph[v]:
                if dist[pair[u]] == dist[v] + 1 and dfs(pair[u]):
                    pair[u] = v
                    pair[v] = u
                    return True

            dist[v] = None
            return False

        return True

    matching = 0

    while bfs():
        for v in left:
            if pair[v] is None and dfs(v):
                matching += 1
                if matching == len(graph):
                    break

    return {v: pair[v] for v in pair if pair[v] is not None}
954100
def graph_structure(self, x1x2):
        
        with argscope([tf.layers.conv2d], activation=lambda x: tf.nn.leaky_relu(x, 0.1),
                      padding='valid', strides=2, kernel_size=3,
                      data_format='channels_first'), \
            argscope([tf.layers.conv2d_transpose], padding='same', activation=tf.identity,
                     data_format='channels_first', strides=2, kernel_size=4):

            # extract features
            x = tf.layers.conv2d(pad(x1x2, 3), 64, kernel_size=7, name='conv1')
            conv2 = tf.layers.conv2d(pad(x, 2), 128, kernel_size=5, name='conv2')
            conv3 = tf.layers.conv2d(pad(conv2, 2), 256, kernel_size=5, name='conv3')

            conv2a, _ = tf.split(conv2, 2, axis=0)
            conv3a, conv3b = tf.split(conv3, 2, axis=0)

            corr = correlation(conv3a, conv3b,
                               kernel_size=1,
                               max_displacement=20,
                               stride_1=1,
                               stride_2=2,
                               pad=20, data_format='NCHW')
            corr = tf.nn.leaky_relu(corr, 0.1)

            conv_redir = tf.layers.conv2d(conv3a, 32, kernel_size=1, strides=1, name='conv_redir')

            in_conv3_1 = tf.concat([conv_redir, corr], axis=1, name='in_conv3_1')
            conv3_1 = tf.layers.conv2d(pad(in_conv3_1, 1), 256, name='conv3_1', strides=1)

            x = tf.layers.conv2d(pad(conv3_1, 1), 512, name='conv4')
            conv4 = tf.layers.conv2d(pad(x, 1), 512, name='conv4_1', strides=1)
            x = tf.layers.conv2d(pad(conv4, 1), 512, name='conv5')
            conv5 = tf.layers.conv2d(pad(x, 1), 512, name='conv5_1', strides=1)
            x = tf.layers.conv2d(pad(conv5, 1), 1024, name='conv6')
            conv6 = tf.layers.conv2d(pad(x, 1), 1024, name='conv6_1', strides=1)

            flow6 = tf.layers.conv2d(pad(conv6, 1), 2, name='predict_flow6', strides=1, activation=tf.identity)
            flow6_up = tf.layers.conv2d_transpose(flow6, 2, name='upsampled_flow6_to_5')
            x = tf.layers.conv2d_transpose(conv6, 512, name='deconv5', activation=lambda x: tf.nn.leaky_relu(x, 0.1))

            # return flow6
            concat5 = tf.concat([conv5, x, flow6_up], axis=1, name='concat5')
            flow5 = tf.layers.conv2d(pad(concat5, 1), 2, name='predict_flow5', strides=1, activation=tf.identity)
            flow5_up = tf.layers.conv2d_transpose(flow5, 2, name='upsampled_flow5_to_4')
            x = tf.layers.conv2d_transpose(concat5, 256, name='deconv4', activation=lambda x: tf.nn.leaky_relu(x, 0.1))

            concat4 = tf.concat([conv4, x, flow5_up], axis=1, name='concat4')
            flow4 = tf.layers.conv2d(pad(concat4, 1), 2, name='predict_flow4', strides=1, activation=tf.identity)
            flow4_up = tf.layers.conv2d_transpose(flow4, 2, name='upsampled_flow4_to_3')
            x = tf.layers.conv2d_transpose(concat4, 128, name='deconv3', activation=lambda x: tf.nn.leaky_relu(x, 0.1))

            concat3 = tf.concat([conv3_1, x, flow4_up], axis=1, name='concat3')
            flow3 = tf.layers.conv2d(pad(concat3, 1), 2, name='predict_flow3', strides=1, activation=tf.identity)
            flow3_up = tf.layers.conv2d_transpose(flow3, 2, name='upsampled_flow3_to_2')
            x = tf.layers.conv2d_transpose(concat3, 64, name='deconv2', activation=lambda x: tf.nn.leaky_relu(x, 0.1))

            concat2 = tf.concat([conv2a, x, flow3_up], axis=1, name='concat2')
            flow2 = tf.layers.conv2d(pad(concat2, 1), 2, name='predict_flow2', strides=1, activation=tf.identity)

            return tf.identity(flow2, name='flow2')
49347
def subgraph(graph, nodes: Iterable[BaseEntity]):
    
    sg = graph.subgraph(nodes)

    # see implementation for .copy()
    result = graph.fresh_copy()
    result.graph.update(sg.graph)

    for node, data in sg.nodes(data=True):
        result.add_node(node, **data)

    result.add_edges_from(
        (u, v, key, datadict.copy())
        for u, v, key, datadict in sg.edges(keys=True, data=True)
    )

    return result
453904
def get_subgraphs(graph=None):
    
    graph = graph or DEPENDENCIES
    keys = set(graph)
    frontier = set()
    seen = set()
    while keys:
        frontier.add(keys.pop())
        while frontier:
            component = frontier.pop()
            seen.add(component)
            frontier |= set([d for d in get_dependencies(component) if d in graph])
            frontier |= set([d for d in get_dependents(component) if d in graph])
            frontier -= seen
        yield dict((s, get_dependencies(s)) for s in seen)
        keys -= seen
        seen.clear()
1125947
def one_to_one(graph, nodes):
    
    edges = itertools.chain.from_iterable(graph.values())
    return len(graph) == len(nodes) and len(set(edges)) == len(nodes)
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
229305
def find_minimum_spanning_forest(graph):
    
    msf = []

    if graph.num_nodes() == 0:
        return msf
    if graph.num_edges() == 0:
        return msf

    connected_components = get_connected_components_as_subgraphs(graph)
    for subgraph in connected_components:
        edge_list = kruskal_mst(subgraph)
        msf.append(edge_list)

    return msf
1142710
def _get_connected_components_adjacency(self, graph, counts):
        ''' '''

        found = set()
        components = list()

        for node in sorted(graph, key=lambda x: counts[x], reverse=True):
            if node not in found:
                # component = self.search(node, graph)
                component = breadth_first_search(node, graph)
                found.update(component)
                components.append(component)
        return components