Returning a Sub Tree for a Graph

[Timothy Trinidad]

Hello!

Let's say I have the following graph:

0 <-[belongs]- A <-[belongs]- A.1

0 <-[belongs]- A <-[belongs]- A.2  

0 <-[belongs]- B <-[belongs]- B.1

0 <-[belongs]- B <-[belongs]- B.2  

0 <-[belongs]- C <-[belongs]- C.1

0 <-[belongs]- C <-[belongs]- C.2  

Where B.1 and C.2 have properties "foo: bar". I'm trying to get the subtree between vertices that have "foo: bar" and the root node:

0 <-[belongs]- B <-[belongs]- B.1

0 <-[belongs]- C <-[belongs]- C.2 

I've tried the following:

g.V().has('foo', 'bar')

  .repeat(out().simplePath())

  .until(hasId('0'))

  .tree()

But I end up getting two different trees that are effectively the single path from the bottom to the top. I'm using `gremlin-javascript` so I can't take advantage of subgraphs. What's the best way to get the following tree?

{

  key: 0

  tree: [

    {

      key: B

      tree: [

        {

          key: B.1

        }

      ]

    },

    {

      key: C

      tree: [

        {

          key: C.2

        }

      ]

    }

  ]

 ]

Thank you in advance!

Tim

[Daniel Kuppitz]

Hi Timothy,

you have a few options. The first obvious one is to start from the other side:

gremlin> g.V('0').repeat(__.in()).until(has('foo','bar')).tree()

==>[v[0]:[v[B]:[v[B.1]:[]],v[C]:[v[C.2]:[]]]]

However, the problem is probably an unpredictable branching factor. So if you start from B.1 and C.2, you have to remember the path, destroy the path history and then traverse the known path back.

gremlin> g.V().has('foo','bar').aggregate('v').

           repeat(outE().simplePath().as('e').inV()).

             until(hasId('0')).as('x').

           select(all, 'e').unfold().aggregate('y').

           select('x').dedup().fold().                       /* fold() destroys the path history, side-effects will survive                                         */

           limit(local, 1).                                  /* this step adds an extra root element to the tree, which is later removed by select(values).unfold() */

           repeat(flatMap(inE().where(within('y')).outV())).

             until(where(within('v'))).

           tree().

           select(values).unfold()

==>[v[0]:[v[B]:[v[B.1]:[]],v[C]:[v[C.2]:[]]]]

A bit complicated, I agree. The third and last solution I can think of is to create a subgraph and then use the subgraph to traverse from 0 to [B.1,C.2]; the number of edges will then be limited and there will be no unnecessary branching in the traversal.

gremlin> g.V().has('foo','bar').

           repeat(outE().simplePath().as('e').inV()).

             until(hasId('0')).as('x').

           select(all, 'e').unfold().subgraph('sg').

           cap('sg').next().traversal().                     /* new traversal, thus a fresh path history */

         V('0').

         repeat(__.in()).

           emit().

         tree()

==>[v[0]:[v[B]:[v[B.1]:[]],v[C]:[v[C.2]:[]]]]

For those who want to follow along, the following script creates the sample graph:

g = TinkerGraph.open().traversal()

g.addV().property(id, '0').

  addV().property(id, 'A').

  addV().property(id, 'B').

  addV().property(id, 'C').

  addV().property(id, 'A.1').

  addV().property(id, 'A.2').

  addV().property(id, 'B.1').property('foo', 'bar').

  addV().property(id, 'B.2').

  addV().property(id, 'C.1').

  addV().property(id, 'C.2').property('foo', 'bar').

  addE('link').from(V('A.1')).to(V('A')).

  addE('link').from(V('A.2')).to(V('A')).

  addE('link').from(V('B.1')).to(V('B')).

  addE('link').from(V('B.2')).to(V('B')).

  addE('link').from(V('C.1')).to(V('C')).

  addE('link').from(V('C.2')).to(V('C')).

  addE('link').from(V('A')).to(V('0')).

  addE('link').from(V('B')).to(V('0')).

  addE('link').from(V('C')).to(V('0')).iterate()

Cheers,

Daniel

--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/5833d83b-f294-48ba-9a7e-5b9bf361c9e7%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Timothy Trinidad]

Daniel,

Thank you for the quick response! I'm currently using option 1 but like you mentioned it could see performance issues. I really like option 3 (subgraph) but since I'm using gremlin in NodeJS, it looks like subgraphs are not supported.

I'll give option 2 a try, or use option 3 to select and return all the nodes/vertices and reconstruct the tree natively in NodeJS.

Tim