グラフ内のすべてのエッジタイプを検索する。ツリー、フォワード、バックワードまたはクロスエッジ

Question

グラフでエッジタイプを計算する擬似コードを探して数時間を費やしました。私は完全なバージョンを見つけることができませんでしたので、私は新しいバージョンを書きました。私はこの投稿への返信としてそれを共有するので、必要に応じて他の人がそれにアクセスできます。

Answer 1

edgeTypes(G, Source) 
    time = 1 
    Stack s 
    for each(node in G.vertices) 
     node.start = 0 
     node.finish = 0 

    s.push(Source) 

    while(!s.isEmpty()) 
     node = s.peek() 
     if(node.start > 0) 
      node.finish = time++ 
      s.pop() 
     else 
      node.start = time++ 
      for each(neig in node.neighbors) 
       if(neig.start == 0) 
        |node, neig|.type = 'tree' 
       else if(neig.finish == 0) 
        |node, neig|.type = 'back' 
       else if(node.start < neig.start) 
        |node, neig|.type = 'forward' 
       else |node, neig|.type = 'cross' 

       if(neig.start == 0) 
        s.push(neig)