Graphframes BFS Ausgabe

Question

Ich war Test graphframes BFS Spielzeug Beispiel:

val g: GraphFrame = examples.Graphs.friends 
val paths: DataFrame = g.bfs.fromExpr("name = 'Esther'").toExpr("name <> 'Esther'").run() 

Das Ergebnis, das ich bekommen ist:

+-------------+------------+------------+ 
|   from|   e0|   to| 
+-------------+------------+------------+ 
|[e,Esther,32]|[e,f,follow]|[f,Fanny,36]| 
|[e,Esther,32]|[e,d,friend]|[d,David,29]| 
+-------------+------------+------------+ 

Das ziemlich seltsam, da Fanny und David auch ausgehende Kanten aufweisen. Und die mit ihnen verbundenen Scheitelpunkte haben auch ausgehende Kanten, z. B. sollte der Ergebnisdatenrahmen nicht nur einen Sprungpfad, sondern alle Pfade vom Quellknoten enthalten.

Ich habe mich ein Spielzeug Diagramm:

1 2 
2 3 
3 4 
4 5 

Und wenn ich die gleiche Art von Abfrage:

g.bfs.fromExpr("id = 1").toExpr("id <> 1").run() 

ich nur die einen Sprung bekommen noch Nachbarn. Fehle ich etwas? Ich habe auch andere Betreiber getestet, die ohne Erfolg für "nicht gleich" stehen. Eine wilde Vermutung: Vielleicht, wenn BFS wieder den Quellknoten erreicht (er sollte es betrachten, aber seine Nachbarn nicht besuchen), stimmt es nicht mit dem Ausdruck "toExpr" überein und bricht ab.

Eine andere Frage: GraphFrames ist gerichtet, nicht? Um einen "indirekten Graphen" zu erhalten, sollte ich reziproke Kanten hinzufügen, oder?

Answer 1

Nachdem Sie Fanny und David erreicht haben, haben Sie den kürzesten Weg von Esther zu einem Nicht-Esther-Knoten gefunden, sodass die Suche beendet wird.

Gemäß den GraphFrames User Guide die bfs Methode „findet den kürzesten Weg (s) von einem Scheitelpunkt (oder einem Satz von Eckpunkten) zu einem anderen Scheitelpunkt (oder einen Satz von Eckpunkten). Anfang und Ende Vertices werden als Funken angegebenen DataFrame-Ausdrücke. "

In der Grafik, die Sie verwenden, der kürzeste Pfad von Esther zu einem Non-Esther-Knoten ist nur ein Hop, so dass die Breitensuche dort stoppt.

Betrachten Sie Ihr numerisches Spielzeugdiagramm. Sie sind daran, diese (ein Hop):

import org.graphframes.GraphFrame 

val edgesDf = spark.sqlContext.createDataFrame(Seq(
    (1, 2), 
    (2, 3), 
    (3, 4), 
    (4, 5)  
)).toDF("src", "dst") 

val g = GraphFrame.fromEdges(edgesDf) 
g.bfs.fromExpr("id = 1").toExpr("id <> 1").run().show() 

+----+-----+---+ 
|from| e0| to| 
+----+-----+---+ 
| [1]|[1,2]|[2]| 
+----+-----+---+ 

Angenommen, Sie es wie folgt statt abgefragt:

g.bfs.fromExpr("id = 1").toExpr("id > 3").run().show() 

+----+-----+---+-----+---+-----+---+ 
|from| e0| v1| e1| v2| e2| to| 
+----+-----+---+-----+---+-----+---+ 
| [1]|[1,2]|[2]|[2,3]|[3]|[3,4]|[4]| 
+----+-----+---+-----+---+-----+---+ 

Nun ist die bfs Methode nimmt drei Hops. Dies ist der kürzeste Pfad von 1 zu einem Knoten, der größer als 3 ist. Obwohl es eine Kante von 4 bis 5 (und 5> 3) gibt, wird sie nicht fortgesetzt, da dies ein längerer Pfad wäre (vier Hops).

Eine andere Frage: GraphFrames ist gerichtet, nicht? Um einen "indirekten Graphen" zu erhalten, sollte ich reziproke Kanten hinzufügen, oder?

Ich denke, es hängt von dem Algorithmus ab, den Sie auf das Diagramm anwenden möchten. Jemand könnte einen Algorithmus schreiben, der die Richtung im zugrunde liegenden edges DataFrame ignoriert. Aber wenn ein Algorithmus einen gerichteten Graphen annimmt, dann glaube ich, dass Sie Recht haben: Sie müssten reziproke Kanten hinzufügen.

Sie können eine bessere Antwort (von jemand anderem) erhalten, wenn Sie dies als eine separate Frage stellen.