Как я могу найти все повторно поддающиеся вершины, в то время как направление чести - PullRequest
Новая
       11

Как я могу найти все повторно поддающиеся вершины, в то время как направление чести

0 голосов
/ 08 июня 2019

Есть официальное решение (квитанция) для поиска всех подключенных компонентов. Но мне нужно то же самое, но там, где направление ребер учтено.

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

Мои примеры кода написаны на Java. 

// My test graph
    TinkerGraph graph = TinkerGraph.open();
    GraphTraversalSource g = graph.traversal();

        g
            .addV().property(T.id, 1).as("1")
            .addV().property(T.id, 2).as("2")
            .addV().property(T.id, 3).as("3")
            .addV().property(T.id, 4).as("4")
            .addV().property(T.id, 5).as("5")
            .addV().property(T.id, 6).as("6")
            .addE("link").from("1").to("2")
            .addE("link").from("1").to("3")
            .addE("link").from("1").to("4")
            .addE("link").from("2").to("3")
            .addE("link").from("3").to("4")
            .addE("link").from("4").to("5")
            .addE("link").from("4").to("6")
            .addE("link").from("5").to("2")
            .iterate();

Например 

for vertex 1 I expect the result [1, 2, 3, 4, 5, 6]
for vertices 2, 3, 4, 5 I expect [2, 3, 4, 5, 6]
for vertex 6 I expect [6]

задание наоборот: 

for vertex 6 result [1, 2, 3, 4, 5]
for vertex 1 result [1]

Возможно ли это? Это кажется обычной задачей, но я не могу найти вопросы по этому поводу. Люди просто хотят найти подключенные компоненты. Заранее спасибо!

1 Ответ

1 голос
/ 09 июня 2019

Для одной начальной вершины это так просто: 

g.V(startId).
  emit().
    repeat(out("link").dedup()).
  dedup()

Теперь для всех вершин одновременно (или набора вершин) вы должны сделать: 

g.V().project("vertex","result").
        by().
        by(emit().
             repeat(out("link").dedup()).
           dedup().fold())

Запросы на вашем примере графика 

gremlin> (1..6).collect { i ->
           result = g.V(i).emit().repeat(out("link").dedup()).dedup().id().toList()
           "for vertex ${i} result ${result}"
         }
==>for vertex 1 result [1, 2, 3, 4, 5, 6]
==>for vertex 2 result [2, 3, 4, 5, 6]
==>for vertex 3 result [3, 4, 5, 6, 2]
==>for vertex 4 result [4, 5, 6, 2, 3]
==>for vertex 5 result [5, 2, 3, 4, 6]
==>for vertex 6 result [6]

gremlin> g.V().project("vertex","result").
                 by(id).
                 by(emit().
                      repeat(out("link").dedup()).
                    dedup().id().fold())
==>[vertex:1,result:[1,2,3,4,5,6]]
==>[vertex:2,result:[2,3,4,5,6]]
==>[vertex:3,result:[3,4,5,6,2]]
==>[vertex:4,result:[4,5,6,2,3]]
==>[vertex:5,result:[5,2,3,4,6]]
==>[vertex:6,result:[6]]
...