CODEWITHSUNDEEP
pythonpython-3.xalgorithmgraph
takibu
takibu

Reputation: 65

Find all connected nodes in graph with loops

I have been sitting on this problem for days, but unfortunately, I could not find an answer that would help me here (and I searched a lot) and I did not have luck with implementing the correct solution by myself.

So, I have a Graph with loops and I would like to find all connected nodes from all nodes (excluding the nodes that are connected with itself). For example

1 -> 3 -> 4  
2 -> 4  
3 -> 2    
4 -> 5, 3  
5 -> NULL

And the output should be: (order is irrelevant)

1 -> {2, 3, 4, 5}
2 -> {4, 3, 5}
3 -> {2, 4, 5}
4 -> {2, 3, 5}
5 -> NULL

The closest solution that I could find was THIS one but unfortunately that does not work for my problem since I have loops (and hence I always get endless recursion) and I do not have an idea how to correct the code given there so that the loops are accepted as well.

Any help would be greatly appreciated!

Upvotes: 2

Views: 1820

Answers (3)

Ajax1234
Ajax1234

Reputation: 71451

You can use a recursive generator function to find the connections:

First, creating the graph:

s = """
1 -> 3 -> 4
2 -> 4
3 -> 2
4 -> 5, 3
5 -> NULL
"""
from itertools import product as pr
def to_graph():
   for i in filter(None, s.split('\n')):
      d = [tuple(int(l) if l.isdigit() else None for l in k.split(', ')) for k in i.split(' -> ')]
      for j in range(len(d)-1):
         yield from pr(d[j], d[j+1])

graph = list(to_graph())
#[(1, 3), (3, 4), (2, 4), (3, 2), (4, 5), (4, 3), (5, None)]

Then, finding the connections:

from collections import defaultdict
def connections(d, n, c = [], s = []):
   if not (k:=[b for a, b in graph if a == n and b not in c]):
      yield (d, c+[n])
      if (l:=[a for a, _ in graph if a not in s+[d]]):
        yield from connections(l[0], l[0], c = [], s=s+[d])
   else:
      yield from [j for i in k for j in connections(d, i, c=c+[n], s = s)]
      
result = defaultdict(set)
for a, b in connections(graph[0][0], graph[0][0]): #choosing `1` as the starting node, but any other node in `graph` will work as well
   for i in filter(lambda x:x != a, b):
      result[a].add(i)

#formatting results to match your desired output
print({a:k if (k:=set(filter(None, b))) else None for a, b in result.items()})

Output:

{1: {2, 3, 4, 5}, 3: {2, 4, 5}, 2: {3, 4, 5}, 4: {2, 3, 5}, 5: None}

To prevent a recursive depth error, connections keeps a running list of all nodes previously collected during the path traversal, and potential additions to the path are checked against that list before the recursion occurs again.

Upvotes: 1

Matt Timmermans
Matt Timmermans

Reputation: 59184

You are trying to compute the transitive closure of a directed graph with cycles. You can do this in O(V2) time as follows:

  1. Use, for example, Tarjan's algorithm to find the strongly connected components of the graph.
  2. Collapse every SCC into a single vertex. Remember that they all have the same reachable vertex set, and they can all reach each other. After collapsing SCCs, the result is a DAG.
  3. Process vertices in reverse topological order to find the reachability set for each SCC, as in this answer for DAGs that you already found.

Upvotes: 2

Kyle Parsons
Kyle Parsons

Reputation: 1525

We can keep a running list of all connectednesses and bail as soon as they don't change.

graph = {
    1: {3},
    2: {4},
    3: {2, 4},
    4: {5, 3},
    5: set(),
}

connectedness = {**graph}
while True:
    new_connectedness = {v: n.union(*[connectedness[nn] for nn in n]) 
                         for v, n in connectedness.items()}
    if new_connectedness == connectedness:
        break
    connectedness = new_connectedness
    
connectedness = {v: c - {v} for v, c in connectedness.items()}

Each time through the loop, the set of edges a node is connected to gets updated with all of the nodes that it's already connected to are connected to. We bail once nothing changes. Then we just normalize by removing self connections.

Upvotes: 2

Related Questions