Tinkerpop 3:使用Gremlin遍历计算连接的组件 [英] Tinkerpop 3: compute connected components with Gremlin traversal

问题描述

我认为标签很好地说明了我的问题:)

I think the tags explain quite well my problem :)

我一直在尝试编写Gremlin遍历，以计算帖子结尾处描述的简单图的连接组件.

I've been trying to write a Gremlin traversal to compute the connected components of the simple graph described at the end of the post.

我尝试过

g.V().repeat(both('e')).until(cyclicPath()).dedup().tree().by('name').next()

获取

==>a={b={a={}, c={b={}}, d={c={d={}}}}, c={d={c={}}}}
==>e={f={e={}, g={f={}}}, h={f={h={}}}}
==>g={f={g={}}}

这很糟糕，因为cyclicPath过滤器在到达g之前终止了从e开始的遍历. 显然，如果删除until子句，则会出现无限循环. 此外，如果使用simplePath，则遍历在一步之后结束. 有什么方法可以告诉它以深度优先的顺序探索节点吗?

which is bad, since the cyclicPath filter terminated the traversal starting from e before reaching g. Obviously, if I remove the until clause I get an infinite loop. Moreover, if I use simplePath the traverse ends after one step. Is there any way to tell it to explore the nodes in depth-first order?

干杯！

a = graph.addVertex(T.id, 1, "name", "a")
b = graph.addVertex(T.id, 2, "name", "b")
c = graph.addVertex(T.id, 3, "name", "c")
d = graph.addVertex(T.id, 4, "name", "d")
e = graph.addVertex(T.id, 5, "name", "e")
f = graph.addVertex(T.id, 6, "name", "f")
g = graph.addVertex(T.id, 7, "name", "g")
h = graph.addVertex(T.id, 8, "name", "h")

a.addEdge("e", b)
a.addEdge("e", c)
b.addEdge("e", c)
b.addEdge("e", d)
c.addEdge("e", d)

e.addEdge("e", f)
e.addEdge("e", h)
f.addEdge("e", h)
f.addEdge("e", g)

推荐答案

此查询

This query was also discussed in the Gremlin-users group. Here is the solution I came out with. @Daniel Kuppitz also had an interesting solution you can find in the mentioned thread.

我认为，如果始终正确，在无向图中，所连接组件的遍历的最后一个"节点要么导致先前访问的节点(cyclicPath())，要么具有度数＜＝ 1，因此该查询应工作

I think that if it is always true that in an undirected graph the "last" node of the traversal of a connected component either leads to a previously visited node (cyclicPath()) or has degree <=1 this query should work

g.V().repeat(both('e')).until( cyclicPath().or().both('e').count().is(lte(1)) ).dedup().tree().by('name').next()

在我的示例中，它提供了以下输出

On my example it gives the following output

gremlin>  g.V().repeat(both('e')).until(cyclicPath().or().both('e').count().is(lte(1))).dedup().tree().by('name').next()
==>a={b={a={}, c={b={}}, d={c={d={}}}}, c={d={c={}}}}
==>e={f={e={}, g={}, h={f={}}}, h={f={h={}}}}

这篇关于Tinkerpop 3:使用Gremlin遍历计算连接的组件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！