Gremlin query to get k distance vertices and edges connecting them

Question

I want to start from a given vertex and get all connected vertices and edges up to a k distance. The output should include all edges that connect the included vertices (even if that edge is at k+1 distance) so that we have a complete sub-graph.

Imagine we have this:

g.addV('person').property('name', 'a').as('va')
 .addV('person').property('name', 'b').as('vb')
 .addV('person').property('name', 'c').as('vc')
 .addV('person').property('name', 'd').as('vd')
 .addV('person').property('name', 'e').as('ve')
 .addV('person').property('name', 'f').as('vf')
 .addV('person').property('name', 'g').as('vg')
 .select('va').addE('knows').to('vb')
 .select('vb').addE('knows').to('vc')
 .select('vc').addE('knows').to('vd')
 .select('vd').addE('knows').to('ve')
 .select('ve').addE('knows').to('va')
 .select('ve').addE('knows').to('vf')
 .select('vf').addE('knows').to('vg')

a->b->c->d->e->(a) and e->f->g

If we start at c with a distance of 2 we should have

a->b->c->d->e->(a)

With this query

g.V().has('person','name','c')
     .repeat(bothE().dedup()
                    .store("e")
                    .bothV()
                    .dedup()
                    .store("v"))
     .times(2)
     .cap('e','v')

I can get a->b->c->d->e but we lose the e->a edge

With this query

g.V().has('person','name','c')
     .repeat(bothE().dedup()
                    .store("e")
                    .bothV()
                    .dedup()
                    .store("v"))
     .times(2)
     .bothE()
     .dedup()
     .store('e')
     .cap('e','v')

we get the extra edges that connect the outer vertices but we also get an edge the connects an outside vertex f We get a->b->c->d->e->(a) but also e->f

How can we get only the k distance vertices and edges connecting them?

This seems to work although with some duplicated edges: g.V().has('person','name','c').sideEffect(repeat(bothE().dedup().aggregate('e').bothV().dedup().aggregate('v')).times(2).bothE().dedup().where(__.inV().where(within('v'))).where(__.outV().where(within('v'))).aggregate('e')).cap('v','e') — PedroF

Daniel Kuppitz Daniel Kuppitz · Accepted Answer · 2019-06-26T19:50:40

You can integrate the break condition in your inner repeat-traversal, that makes it a bit easier:

g.V().has('person','name','c').store('v').
  repeat(bothE().where(without('e')).
         choose(loops().is(lt(2)),
                  aggregate('e'),
                  filter(otherV().where(within('v'))).aggregate('e').not(identity())).
         otherV().where(without('v')).aggregate('v')).
  cap('e','v')

On your sample graph:

gremlin> g.V().has('person','name','c').store('v').
......1>   repeat(bothE().where(without('e')).
......2>          choose(loops().is(lt(2)),
......3>                   aggregate('e'),
......4>                   filter(otherV().where(within('v'))).aggregate('e').
......5>                   not(identity())).
......6>          otherV().where(without('v')).aggregate('v')).
......7>   cap('e','v').sideEffect {
......8>      m = it.get()
......9>      println 'Vertices:'
.....10>      m.get('v').each {
.....11>        println "* " + it.value('name')
.....12>      }
.....13>      println 'Edges:'
.....14>      m.get('e').each {
.....15>        println "* " + [it.outVertex(), it.inVertex()]*.value('name').join(' -> ')
.....16>      }
.....17>   }.iterate()
Vertices:
* c
* d
* b
* e
* a
Edges:
* c -> d
* b -> c
* d -> e
* a -> b
* e -> a

Gremlin query to get k distance vertices and edges connecting them

1 Answers