Flink Gelly Pfad/Pfad Usecase

Question

Unser Team ist neu in Gelly api. Wir versuchen, einen einfachen Anwendungsfall zu implementieren, der alle Pfade auflistet, die von einem anfänglichen Vertex stammen - z.

Eingangskante CSV-Datei ist 1,2 \ n 2,3 \ n3,4 \ n1,5 \ n5,6

die erforderliche Ausgabe sein wird (der vollständige Pfad, der von 1 beginnt) 1, 2,3,4 \ n1,5,6

Kann jemand bitte helfen.

Answer 1

Sie können einen von Gelly's iteration abstractions, z. vertex-zentrische Iterationen. Ausgehend vom Quellknoten können Sie die Pfade iterativ um einen Hop pro Superschritt erweitern. Nach dem Empfang eines Pfades hängt ein Knoten seine ID an den Pfad an und überträgt ihn an seine abgehenden Nachbarn. Wenn ein Vertex keine ausgehenden Nachbarn hat, druckt/speichert er den Pfad und propagiert ihn nicht weiter. Um Schleifen zu vermeiden, könnte ein Scheitelpunkt auch prüfen, ob seine ID im Pfad existiert, bevor er sich ausbreitet. Die Rechenfunktion könnte wie folgt aussehen:

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); 
       } 
      } 
     } 
    } 
} 

In diesem Code habe ich davon ausgegangen, dass Sie vorverarbeiteten Ecken haben diejenigen zu markieren, die keine out-Nachbarn mit einem „echten“ Wert haben. Sie könnten z.B. Verwenden Sie graph.outDegrees(), um diese zu finden.

Bedenken Sie, dass die Aufzählung aller Pfade in einem großen und dichten Graphen teuer zu berechnen ist. Der Zustand der Zwischenpfade kann ziemlich schnell explodieren. Sie könnten eine kompaktere Methode zum Darstellen von Pfaden verwenden als eine ArrayList von Ints, aber achten Sie auf die Kosten, wenn Sie einen dichten Graphen mit großem Durchmesser haben. Wenn Sie die Pfade nicht selbst benötigen, sondern nur an Erreichbarkeit oder kürzesten Wegen interessiert sind, dann gibt es effizientere Algorithmen.