Connected components of the graph
Hello. Connected components of graphs ([Connected graph](https://ja.wikipedia.org/wiki/Connected graph), [Disjoint-set data structure](https://ja.wikipedia.org/wiki/Disjoint-set data structure) I found "Python connected components" (Stack Overflow) in the calculation to find). I ran the source there almost as-is and compared it to the networkx results for verification.
$ ./connected_components.py
graph = {0: [1, 2, 3], 1: [2], 2: [], 3: [4, 6], 4: [], 5: [7], 6: [], 7: []}
[[0, 1, 2, 3, 4, 6], [5, 7]]
True (equal to one derived from networkx)
connected_components.py
#!/usr/bin/env python
from __future__ import print_function
def connected_components(graph):
seen = set()
def component(n):
nodes = set([n])
while nodes:
n = nodes.pop()
seen.add(n)
nodes |= set(graph[n]) - seen
yield n
for n in graph:
if n not in seen:
yield component(n)
def print_gen(gen):
print([list(x) for x in gen])
def check_connected(graph):
import networkx as nx
G = nx.Graph()
G.add_nodes_from(graph.keys())
for k, v in graph.items():
for n in v:
G.add_edge(k, n)
check = sorted([set(x) for x in nx.connected_components(G)]) == sorted([set(x) for x in connected_components(graph)])
print(check, "(equal to one derived from networkx)")
graph = {0: [1, 2, 3], 1: [2], 2: [], 3: [4, 6], 4: [], 5: [7], 6: [], 7: []}
print("graph =", graph)
print_gen(connected_components(graph))
check_connected(graph)
# graph:
# 0
# / | \
# 1--2 3
# | \
# 4 6
# 5--7
――I'm sorry that the check judgment department is a little childish.
Recommended Posts