[PYTHON] 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.

graph.jpg

$ ./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

Connected components of the graph
About the components of Luigi
[pyqtgraph] Set the size ratio of the graph
Display the graph of tensorBoard on jupyter
Increase the font size of the graph with matplotlib
The basis of graph theory with matplotlib animation
The beginning of cif2cell
The meaning of self
the zen of Python
The story of sys.path.append ()
Revenge of the Types: Revenge of types
Omit the decimal point of the graph scale in matplotlib
Align the version of chromedriver_binary
Scraping the result of "Schedule-kun"
10. Counting the number of lines
The story of building Zabbix 4.4
Towards the retirement of Python2
[Apache] The story of prefork
Compare the fonts of jupyter-themes
About the ease of Python
Get the number of digits
Have the equation graph of the linear function drawn in Python
Explain the code of Tensorflow_in_ROS
Reuse the results of clustering
GoPiGo3 of the old man
Cut the PyTorch calculation graph
Calculate the number of changes
Change the theme of Jupyter
The popularity of programming languages
Change the style of matplotlib
Find the diameter of the graph by breadth-first search (Python memory)
One-liner basic graph of HoloViews
Filter the output of tracemalloc
About the features of Python
Interactive plot of 3D graph
Simulation of the contents of the wallet
The Power of Pandas: Python
I checked the distribution of the number of video views of "Flag-chan!" [Python] [Graph]
[Statistics] Grasp the image of the central limit theorem with a graph
Display the image of the camera connected to the personal computer on the GUI.
[Python] Try to graph from the image of Ring Fit [OCR]
[TensorFlow 2] How to check the contents of Tensor in graph mode
Count the maximum concatenated part of a random graph with NetworkX
Seaborn basics for beginners ① Aggregate graph of the number of data (Countplot)
The specifications of pytz have changed
Test the version of the argparse module
Find the definition of the value of errno
The day of docker run (note)
The story of Python and the story of NaN
Raise the version of pyenv itself
Get the number of views of Qiita
First Python 3 ~ The beginning of repetition ~
The story of participating in AtCoder
Change the background of Ubuntu (GNOME)
I investigated the mechanism of flask-login!
Understand the contents of sklearn's pipeline
The world of control engineering books
Step into the darkness of msync
Take the execution log of Celery
Test the goodness of fit of the distribution
Existence from the viewpoint of Python