Graphframes BFS вопрос

Question

Я тестирование graphframes BFS игрушечный пример:

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

В результате я получаю это:

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

Это довольно странно, так как Фанни и Дэвид также исходящие ребра. И связанные с ними вершины также имеют исходящие ребра, например, результирующий фреймворк должен содержать не только один путь перехода, но и все пути из исходной вершины.

Я сам создал игрушку график:

1 2 
2 3 
3 4 
4 5 

И когда я делаю такой же запрос:

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

я до сих пор получить только один хмель соседей. Я что-то упускаю? Я также тестировал других операторов, которые не имеют равных результатов без успеха. Дикое предположение: возможно, когда BFS снова вернется к исходной вершине (она должна смотреть на нее, но не навестить ее соседей), она не соответствует выражению «toExpr» и прерывается.

Другой вопрос: Графические рамки направлены, не так ли? Чтобы получить «непрямый граф», я должен добавить обратные ребра, не так ли?

Answer 1

По достижении Фанни и Дэвида, вы нашли кратчайший путь от Эстер до узла без Esther, поэтому поиск останавливается.

Согласно GraphFrames User Guide, то bfs метод «находит кратчайший путь (ы) из одной вершины (или множества вершин) в другую вершину (или множество вершин). Начало и конец вершина определяются как Спарк Выражения DataFrame. "

На графике, который вы используете, кратчайший путь от Esther до узла без Esther - это всего лишь один прыжок, поэтому поиск по ширине останавливается там.

Рассмотрите свой цифровой график игрушек. Вы находите это (один хмель):

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]| 
+----+-----+---+ 

Предположит, вы опрошен его, как это вместо:

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]| 
+----+-----+---+-----+---+-----+---+ 

Теперь метод bfs занимает три хмеля. Это самый короткий путь от 1 до узла, который больше 3. Даже если есть край от 4 до 5 (и 5> 3), он не продолжается, потому что это будет более длинный путь (четыре прыжка).

Другой вопрос: Графические рамки направлены, не так ли? Чтобы получить «непрямый граф», я должен добавить обратные ребра, не так ли?

Я думаю, что это зависит от алгоритма, который вы хотите применить к графику. Кто-то может написать алгоритм, который игнорирует направление в базовом edges DataFrame. Но если алгоритм предполагает ориентированный граф, то я думаю, что вы правы: вам придется добавлять обратные ребра.

Вы можете получить лучший ответ (от кого-то другого), если вы зададите это как отдельный вопрос.