Find the number of cycles in a graph (Python)

Question

I have to find the number of cycles in a graph.

I have a set of nodes connected to each other which have the following structure:

class Node:
   def __init__(self, id, value):
     self.divergencePoint = 0
     self.convergencePoint = 0
     self.id = id
     self.value = value
     self.parents = []
     self.children = []

I have successfully created the graph and the fields divergencePoint and convergencePoint are set to 1 if it is a convergence point or a divergence point.

Now how can I detect the cycles ?

So in this case, divergence points are A and D, and convergence points are D and E? — Aran-Fey, Apr 23 '17 at 10:42
A diamond is a subgraph delimited by a divergence point followed by a convergence point where one or several nodes are present between these two points with the condition that all the "flows" traverse both points — Gaulthier, Apr 23 '17 at 10:44
this may help: https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph — hiro protagonist, Apr 23 '17 at 10:47
@LukeSky Can you label other vertices too? From what I've understood, I think there is another convergence point connected to D. — frederick99, Apr 23 '17 at 12:34

score 0 · Answer 1 · answered Apr 23 '17 at 10:55

Since you've already found the convergence and divergence points, this is an easy task. You start at a divergence point and recursively add its children to the diamond until you encounter a convergence point.

for node in divergence_nodes:
    diamond= {node}
    queue= node.children[:]

    while queue:
        node= queue.pop()
        if node in diamond:
            continue

        diamond.add(node)

        if not node.convergencePoint:
            queue+= node.children

Find the number of cycles in a graph (Python)

1 Answers1