How to find connected components?

by

I like this algorithm:

def connected_components(neighbors):
    seen = set()
    def component(node):
        nodes = set([node])
        while nodes:
            node = nodes.pop()
            seen.add(node)
            nodes |= neighbors[node] - seen
            yield node
    for node in neighbors:
        if node not in seen:
            yield component(node)

Not only is it short and elegant, but also fast. Use it like so (Python 2.7):

old_graph = {
    0: [(0, 1), (0, 2), (0, 3)],
    1: [],
    2: [(2, 1)],
    3: [(3, 4), (3, 5)],
    4: [(4, 3), (4, 5)],
    5: [(5, 3), (5, 4), (5, 7)],
    6: [(6, 8)],
    7: [],
    8: [(8, 9)],
    9: []}

edges = {v for k, vs in old_graph.items() for v in vs}
graph = defaultdict(set)

for v1, v2 in edges:
    graph[v1].add(v2)
    graph[v2].add(v1)

components = []
for component in connected_components(graph):
    c = set(component)
    components.append([edge for edges in old_graph.values()
                            for edge in edges
                            if c.intersection(edge)])

print(components)

The result is:

[[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), (5, 3), (5, 4), (5, 7)],
 [(6, 8), (8, 9)]]

Thanks, aparpara for spotting the bug.

More Related Contents:

  1. Find sets of disjoint sets from a list of tuples or sets in python
  2. Merge lists that share common elements
  3. How to use OpenCV’s connectedComponentsWithStats in Python?
  4. How do I run graphx with Python / pyspark?
  5. Python eval() not multiplying properly
  6. Reading past the first three lines of a cvs file in python [duplicate]
  7. Python string interning
  8. matplotlib/seaborn: first and last row cut in half of heatmap plot
  9. zip variable empty after first use
  10. Large, persistent DataFrame in pandas
  11. Tkinter lambda function
  12. Pandas “Can only compare identically-labeled DataFrame objects” error
  13. Why do circular imports seemingly work further up in the call stack but then raise an ImportError further down?
  14. Python – Activate conda env through shell script
  15. Constructing a co-occurrence matrix in python pandas
  16. Python: why does my list change when I’m not actually changing it?
  17. Composing functions in python
  18. How to get a GCP Bearer token programmatically with python
  19. What is the right way to debug in iPython notebook?
  20. Getting a default value on index out of range in Python [duplicate]
  21. Combine –user with –prefix error with setup.py install
  22. Django Admin nested inline
  23. Python super method and calling alternatives
  24. How to update matplotlib’s imshow() window interactively?
  25. Accessing dictionary by key in Django template
  26. Get dimensions of a video file
  27. Reason for globals() in Python?
  28. TensorFlow, “‘module’ object has no attribute ‘placeholder'”
  29. How do I run a long-running job in the background in Python
  30. What does the term “blocking” mean in programming?

Leave a Comment