CODEWITHSUNDEEP
pythongraphconnection
annndrey
annndrey

Reputation: 1788

Graph connections in python

I'm not very familiar with the graph theory, but I'll try to explain my problem. I have a dictionnary like this:

{67: [68, 332],
 68: [67],
 265: [266],
 266: [265],
 332: [67, 333],
 333: [332, 334],
 334: [333, 335],
 335: [334, 336],
 336: [335]}

The keys of this dict are nodes, and the values are edges of the graph. How can we find the connected groups in this graph? [there are two groups - 265->266 and 67->...->366]

Upvotes: 1

Views: 4844

Answers (3)

DSM
DSM

Reputation: 353059

If you're going to be doing a lot of graph stuff and don't want the overhead of using Sage I'd simply install networkx:

>>> import networkx as nx
>>> 
>>> nodes_and_edges = {67: [68, 332], 68: [67], 265: [266],
...                    266: [265], 332: [67, 333],  333: [332, 334],
...                    334: [333, 335], 335: [334, 336],  336: [335]}
>>> 
>>> G = nx.Graph(nodes_and_edges)
>>> G
<networkx.classes.graph.Graph object at 0x11ac510>
>>> nx.connected_components(G)
[[67, 68, 332, 333, 334, 335, 336], [265, 266]]

Upvotes: 2

Adam Mihalcin
Adam Mihalcin

Reputation: 14458

It looks like your graph is undirected, meaning that, for any two nodes A and B, if there is an edge from A to B then there is an edge from B to A. To find the connected components of a graph, you can simply use a depth-first search. Start at any node and follow edges until you can't reach any more nodes without hitting duplicates. This is the first connected component. Then start at any node you haven't touched yet and repeat. You're done when you've reached all the nodes in the graph.

Upvotes: 2

senderle
senderle

Reputation: 150977

I believe you're talking about Tarjan's strongly connected components algorithm.

Here's a Python implementation that I think is correct. You'll have to convert the dictionary to a list of edges, as in [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'A'), ('A', 'E'), ('C', 'A'), ('C', 'E'), ('D', 'F'), ('F', 'B'), ('E', 'F')]:

import itertools

def strong_connect(vertex):
    global edges, indices, lowlinks, connected_components, index, stack
    indices[vertex] = index
    lowlinks[vertex] = index
    index += 1
    stack.append(vertex)

    for v, w in (e for e in edges if e[0] == vertex):
        if indices[w] < 0:
            strong_connect(w)
            lowlinks[v] = min(lowlinks[v], lowlinks[w])
        elif w in stack:
            lowlinks[v] = min(lowlinks[v], indices[w])

    if indices[vertex] == lowlinks[vertex]:
        connected_components.append([])
        while stack[-1] != vertex:
            connected_components[-1].append(stack.pop())
        connected_components[-1].append(stack.pop())

edges = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'A'), ('A', 'E'), ('C', 'A'), ('C', 'E'), ('D', 'F'), ('F', 'B'), ('E', 'F')]
vertices = set(v for v in itertools.chain(*edges))
indices = dict((v, -1) for v in vertices)
lowlinks = indices.copy()
connected_components = []

index = 0
stack = []
for v in vertices:
    if indices[v] < 0:
        strong_connect(v)

print(connected_components)

It's from this question.

Upvotes: 2

Related Questions