Используйте Gremlin, чтобы найти кратчайший путь в графе, избегая заданного списка вершин? - PullRequest
Новая
       23

Используйте Gremlin, чтобы найти кратчайший путь в графе, избегая заданного списка вершин?

9 голосов
/ 31 августа 2011

Мне нужно использовать Gremlin, чтобы найти кратчайший путь между двумя узлами (вершинами), избегая списка заданных вершин.

У меня уже есть:

v.bothE.bothV.loop(2){!it.object.equals(y)}.paths>>1

Чтобы получить мой кратчайший путь.

Я пытался что-то вроде:

v.bothE.bothV.filter{it.name!="ignored"}.loop(3){!it.object.equals(y)}.paths>>1

, но, похоже, не работает.

Пожалуйста, ПОМОГИТЕ!!!

1 Ответ

15 голосов
/ 02 сентября 2011

Второе решение у вас выглядит правильно.Тем не менее, чтобы быть ясно, что вы пытаетесь достичь.Если x и y - это вершины, между которыми вы хотите найти кратчайший путь, и вершина, которую нужно игнорировать во время обхода, если у нее есть имя свойства: "ignored", тогда запрос: 

x.both.filter{it.name!="ignored"}.loop(2){!it.object.equals(y)}.paths>>1

Если«список заданных вершин», который вы хотите отфильтровать, на самом деле является списком, тогда обход описывается так: 

list = [ ... ] // construct some list
x.both.except(list).loop(2){!it.object.equals(y)}.paths>>1

Более того, я склонен использовать фильтр диапазона только для безопасности, так какбесконечный цикл, если вы забыли >> 1:) 

x.both.except(list).loop(2){!it.object.equals(y)}[1].paths>>1

Кроме того, если есть потенциал для отсутствия пути, то, чтобы избежать бесконечно долгого поиска, вы можете сделать ограничение цикла (например, не болеечем 4 шага): 

x.both.except(list).loop(2){!it.object.equals(y) & it.loop < 5}.filter{it.object.equals(y)}.paths>>1

Обратите внимание, зачем нужен последний шаг фильтра перед путями.Есть две причины, по которым цикл нарушен.Таким образом, вы можете не оказаться в точке y, когда выходите из цикла (вместо этого вы выходите из цикла, потому что it.loops <5). </p>

Вот ваше решение, реализованное на графе Grateful Dead, распределенном с помощьюGremlin.Сначала нужно настроить код, где мы загружаем график и определяем две вершины x и y: 

gremlin> g = new TinkerGraph()
==>tinkergraph[vertices:0 edges:0]
gremlin> g.loadGraphML('data/graph-example-2.xml')
==>null
gremlin> x = g.v(89) 
==>v[89]
gremlin> y = g.v(100) 
==>v[100]
gremlin> x.name
==>DARK STAR
gremlin> y.name
==>BROWN EYED WOMEN

Теперь ваш обход.Обратите внимание, что нет свойства name: «ignored», поэтому я изменил его, чтобы учесть количество исполнений каждой песни на пути.Таким образом, кратчайший путь песен, сыгранных более 10 раз на концерте: 

gremlin> x.both.filter{it.performances > 10}.loop(2){!it.object.equals(y)}.paths>>1
==>v[89]
==>v[26]
==>v[100]

Если вы используете Gremlin 1.2+, то вы можете использовать замыкание пути для предоставления названий этих вершин (например) вместотолько необработанные объекты вершин: 

gremlin> x.both.filter{it.performances > 10}.loop(2){!it.object.equals(y)}.paths{it.name}>>1
==>DARK STAR
==>PROMISED LAND
==>BROWN EYED WOMEN

Надеюсь, это поможет.

Удачи!Марко.

...