グラフのサイクル数を見つける（Python）

Question

グラフのサイクル数を求めなければなりません。

Iは、以下の構造を有する相互に接続されたノードのセットを有する：

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

Iグラフを正常に作成されており、それは収束点である場合のフィールドdivergencePointと convergencePointが1に設定されています発散点である。

どうすればサイクルを検出できますか？

Answer 1

すでにコンバージェンスと相違点が見つかりましたので、これは簡単な作業です。あなたは発散点から始まり、収束点に達するまでその子をダイアモンドに再帰的に追加します。

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