Flink Gelly Path/Trail Usecase

Question

私たちのチームはGelly apiを初めて使用しています。最初の頂点に由来するすべてのパスをリストする簡単なユースケースを実装しようとしています。

入力エッジCSVファイル 1,2-ある\ n2,3 \ n3,4 \ n1,5 \ n5,6

必要な出力は、 1（1から始まるフルパス）であろう2,3,4 \ n1,5,6

助けてもらえますか？

Answer 1

Gelly's iteration abstractionsのいずれかを使用できます。頂点中心の反復ソース頂点から出発して、パスを反復的に拡張できます。スーパーステップごとに1ホップです。パスを受け取ると、頂点はそのIDをパスに付加し、それをその隣接する隣接ノードに伝搬させる。頂点に発信隣接ノードがない場合は、パスを印刷/保存し、それをさらに伝播しません。ループを回避するために、頂点は伝播する前にそのIDがパスに存在するかどうかをチェックすることもできます。計算機能は、次のようになります。

public static final class ComputePaths extends ComputeFunction<Integer, Boolean, NullValue, ArrayList<Integer>> { 

    @Override 
    public void compute(Vertex<Integer, Boolean> vertex, MessageIterator<ArrayList<Integer>> paths) { 
     if (getSuperstepNumber() == 1) { 
      // the source propagates its ID 
      if (vertex.getId().equals(1)) { 
       ArrayList<Integer> msg = new ArrayList<>(); 
       msg.add(1); 
       sendMessageToAllNeighbors(msg); 
      } 
     } 
     else { 
      // go through received messages 
      for (ArrayList<Integer> p : paths) { 
       if (!p.contains(vertex.getId())) { 
        // if no cycle => append ID and forward to neighbors 
        p.add(vertex.getId()); 
        if (!vertex.getValue()) { 
         sendMessageToAllNeighbors(p); 
        } 
        else { 
         // no out-neighbors: print p 
         System.out.println(p); 
        } 
       } 
       else { 
        // found a cycle => print the path and don't propagate further 
        System.out.println(p); 
       } 
      } 
     } 
    } 
} 

をこのコードでは、私はあなたが「真」の値とは、アウト隣人を持っていないものをマークするための前処理された頂点を持っていることを前提としています。たとえば、それらを見つけるにはgraph.outDegrees()を使用してください。

大規模で高密度のグラフのすべてのパスを列挙することは、計算コストが高いことに注意してください。中間パス状態は非常に迅速に爆発する可能性があります。あなたは、intのArrayListを使うよりも、パスを表現するためのよりコンパクトな方法を使うことができます。しかし、大きな直径の密集したグラフがあれば、コストに注意してください。 パス自体は必要なく、到達可能性や最短パスにのみ関心がある場合は、より効率的なアルゴリズムが存在します。