Connected Components

Generate graph from a list of connected components

An alternative to itertools.pairwise is networkx.path_graph.

An alternative to itertools.combinations is networkx.complete_graph.

These two networkx functions return a new graph, not a list of edges, so you can combine them with networkx.compose_all.

Note also union_all and disjoint_union_all as alternatives to compose_all.

import networkx as nx

l = [{0, 1, 3}, {2, 5}, {4}, {6}]

G = nx.compose_all(map(nx.path_graph, l))

H = nx.compose_all(map(nx.complete_graph, l))

print(G.nodes, G.edges)
# [0, 1, 3, 2, 5, 4, 6] [(0, 1), (1, 3), (2, 5)]

print(H.nodes, H.edges)
# [0, 1, 3, 2, 5, 4, 6] [(0, 1), (0, 3), (1, 3), (2, 5)]

I haven't actually run benchmarks, but I suspect creating several graphs and composing them might be slower than creating lists of edges and chaining them to create only one graph.

Z3 connected components

Nodes of a graph component connected via other nodes can be modelled using TransitiveClosure.

The following snippet might get you started:

#  https://stackoverflow.com/q/56496558/1911064
from z3 import *

B = BoolSort()
NodeSort = DeclareSort('Node')

R = Function('R', NodeSort, NodeSort, B)
TC_R = TransitiveClosure(R)

s = Solver()

na, nb, nc = Consts('na nb nc', NodeSort)
s.add(R(na, nb))
s.add(R(nb, nc))
s.add(Not(TC_R(na, nc)))

print(s.check())   # produces unsat

Connected Component in Undirected Graph in python

Your condition if not node: doesn't make sense: you're not modifying nodes or making them Falsey. Depth first search explores a forest of rooted trees. Your outer loop over nodes looks for the roots of these trees, so you should just pass a reference to an empty list into dfs, to track all the nodes explored in the search tree for that root:

class Solution:
    def connectedSet(self, nodes):
        res = []
        visited = set()

        def dfs(node, path):
            path.append(node.label)
            visited.add(node)
            for neighbor in node.neighbors:
                if neighbor not in visited:
                    dfs(neighbor, path)

        for node in nodes:
            if node not in visited:
                path = []
                dfs(node, path)
                res.append(sorted(path.copy()))
        return res

---

Related Topics