Gremlin recursive graph traversal with parent and child relationship

user_350374 0
Viewed 414

I want to traverse a tree and aggregate the parent and its immediate children only. How would I do this using Gremlin and aggregate this into a structure list arrayOf({parent1,child},{child, child1}...}

Example graph here

In this case I want to output [{0,1}, {0,2}, {1,8} {1,6}, {2,7},{2,9}, {8,16},{8,14},{8,15},{7,17}}

The order isnt important. Also, note I want to avoid any circular edges which can exist on the same node only (no circular loop possible from a child vertex to a parent)

Each vertex has a label city and each edge has a label highway

g.V().hasLabel("city").toList().map(x->x.id()+x.edges(Direction.OUT,"highway").collect(Collectors.toList())

My query is timing out and I was wondering if there is a faster way to do this. I have abt 5000 vertices and two vertices are connected with only one edge.

tinkerpop gremlin
1 Answers

You can get close to what you are looking for using the Gremlin tree step while also avoiding Groovy closures. Assuming the following setup:

gremlin> g = traversal().withGraph(TinkerGraph.open())
==>graphtraversalsource[tinkergraph[vertices:0 edges:0], standard]   

g.addV('0').as('0').
  addV('1').as('1').
  addV('2').as('2').
  addV('6').as('6').
  addV('7').as('7').
  addV('8').as('8').
  addV('9').as('9').
  addV('14').as('14').
  addV('15').as('15').
  addV('16').as('16').
  addV('17').as('17').
  addE('route').from('0').to('1').
  addE('route').from('0').to('2').
  addE('route').from('1').to('6').
  addE('route').from('1').to('8').
  addE('route').from('2').to('2').
  addE('route').from('2').to('9').
  addE('route').from('2').to('7').
  addE('route').from('7').to('17').
  addE('route').from('8').to('14').
  addE('route').from('8').to('15').
  addE('route').from('8').to('16').iterate()

A query can be written to return the tree (minus cycles) as follows:

gremlin> g.V().hasLabel('0').
......1>   repeat(out().simplePath()).
......2>   until(__.not(out())).
......3>   tree().
......4>     by(label)   

==>[0:[1:[6:[],8:[14:[],15:[],16:[]]],2:[7:[17:[]],9:[]]]]

An alternative approach, that also avoids using closures:

gremlin> g.V().local(union(label(),out().simplePath().label()).fold())

==>[17]
==>[0,1,2]
==>[1,6,8]
==>[2,9,7]
==>[6]
==>[7,17]
==>[8,14,15,16]
==>[9]
==>[14]
==>[15]
==>[16]

Which can be further refined to avoid leaf only nodes using:

gremlin> g.V().local(union(label(),out().simplePath().label()).fold()).where(count(local).is(gt(1)))

==>[0,1,2]
==>[1,6,8]
==>[2,9,7]
==>[7,17]
==>[8,14,15,16]

In your code you can then create the final pairs or perhaps extend the Gremlin to break up the result even more. Hopefully these approaches will prove more efficient than falling back onto closures (which are not going to be very portable to other TinkerPop implementations that do not support in-line code).

user_54420340
Related