如何使用 gremlin 在 titan 图形数据库中查找 clique？

Question

我需要找到所有 cliques of three size from my graph with Gremlin。我能够在 neo4j 中使用 cypher 做到这一点：

MATCH (a)-[:edge]-(b)-[:edge]-(c)-[:edge]-(a)
RETURN a,b,c

例子是：A->B->C->A

基于@pkohan 的回答的一个可能的解决方案是：

g.V().as('x').sideEffect{x = it}.out().loop(1){it.loops < 4}{if(it.loops==4){if(it.object.id==x.id){true}else{false}}else{false}}.path.dedup().collect{"${it[0].id}->${it[1].id}->${it[2].id}"}

有人有别的想法吗？

Answer 1

这是一个在大图上效率极低的查询，但可以达到您的预期：

g.V().filter{it.out().loop(1){it.loops < 3}.id.filter{i -> it.id == i}.hasNext()}.map

这个 returns 一个包含顶点的管道，这些顶点在走完三个出边后可以指向它们自己。您可以通过更改闭包中的 it.loops < 3 来更改要遵循的边数。您可以通过将 out() 更改为 in() 来执行传入边，或者您可以使用 both() 遵循任一方向。您还可以通过将边缘类型放在括号中来缩小边缘类型，例如：

g.V().filter{it.out("EDGE_TYPE").loop(1){it.loops < 3}.id.filter{i -> it.id == i}.hasNext()}.map

我不确定 neo4j 是否具有使该查询在大型数据库上可行的优化，但我认为运行在具有数百万条边和顶点的泰坦图上进行该查询会很危险。

Answer 2

我假设您使用的是 Gremlin2。

gremlin> g = TinkerGraphFactory.createTinkerGraph()
==>tinkergraph[vertices:6 edges:6]
gremlin> g.V().as('x').both().loop('x') {it.loops < 3}.both().retain('x').path()
==>[v[1], v[3], v[4], v[1]]
==>[v[1], v[4], v[3], v[1]]
==>[v[3], v[4], v[1], v[3]]
==>[v[3], v[1], v[4], v[3]]
==>[v[4], v[1], v[3], v[4]]
==>[v[4], v[3], v[1], v[4]]

如您所见，它是同一个集团的 6 倍，只是不同的开始和结束顶点以及不同的路径。以下是对结果集进行重复数据删除的方法：

gremlin> g.V().as('x').both().except('x').loop('x') {it.loops < 3}.both().retain('x').path().transform {it[0..2].sort()}.dedup()
==>[v[1], v[3], v[4]]

由于您要查找的路径具有固定长度，因此您还可以去掉循环结构（这会导致执行速度更快）：

gremlin> g.V().as('a').both().as('b').except('a').both().as('c').both().retain('a').path().transform {it[0..2].sort()}.dedup()
==>[v[1], v[3], v[4]]

您可以在 Gremlin3 中做几乎相同的事情，但您也可以选择使用新的 match 步来查找模式（如果您知道如何编写在 Cypher 中查询):

gremlin> graph = TinkerFactory.createModern()
==>tinkergraph[vertices:6 edges:6]
gremlin> g = graph.traversal(standard())
==>graphtraversalsource[tinkergraph[vertices:6 edges:6], standard]
gremlin> g.V().match("a",
gremlin>   __.as("a").both().as("b"),
gremlin>   __.as("b").both().as("c"),
gremlin>   __.as("c").both().as("d")).where("a", eq("d")).select("a", "b", "c").map {it.get().values().sort()}.dedup()
==>[v[1], v[3], v[4]]

如何使用 gremlin 在 titan 图形数据库中查找 clique？

How to find clique in titan graph database with gremlin?

graph

neo4j

titan

gremlin