How do I find a clique in a titanium gremlin graph database?
I need to find all the cliques of three sizes from my Gremlin graph . I was able to do this in neo4j using cypher:
MATCH (a)-[:edge]-(b)-[:edge]-(c)-[:edge]-(a)
RETURN a,b,c
Example: A-> B-> C-> A
One possible solution, based on @pkohan's answer, is:
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}"}
Anyone have another idea?
source to share
Here's a query that will be extremely inefficient on a large chart, but does what you expect:
g.V().filter{it.out().loop(1){it.loops < 3}.id.filter{i -> it.id == i}.hasNext()}.map
This returns a pipe containing vertices that can point to themselves after traversing three outgoing edges. You can change the number of edges to follow by changing it.loops < 3
in the closure. You can make incoming edges by changing out()
to in()
, or you can follow in any direction using both()
. You can also narrow down to the types of boundaries by placing them in parentheses, for example:
g.V().filter{it.out("EDGE_TYPE").loop(1){it.loops < 3}.id.filter{i -> it.id == i}.hasNext()}.map
I'm not sure if neo4j has optimizations that make this query doable on a large database, but I would assume that running this query on a titanium plot with millions of edges and vertices would be dangerous.
source to share
I am assuming you are using 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]]
As you can see, it is 6 times more like a click, only different start and end vertices and different paths. Here's how you can deduplicate the result set:
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]]
Since the path you are looking for has a fixed length, you can also get rid of the loop construct (which should result in faster execution):
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]]
You can do pretty much the same thing in Gremlin3, but you also have the option to use the new match
-pattern to find a pattern (which should be pretty simple if you know how to write a query in 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]]
source to share