Tinkerpop Gremlin Depth First Search Order

问题:

I have a very simple example graph which I am trying to get a depth first query on. Let's say the graph edges look like this

A->B
A->C
B->D
B->E
C->F
C->G

A depth first search from A should return

A-B-D-E-C-F-G

But if I could get the below order it would be even better

D-E-B-A-F-G-C-A

How can I create a Gremlin query that will output this order? If I do something like this

g.V('A').repeat(outE().inV()).emit()

I get an order of A,B,C,D,E,F,G which is breadth first. I can't work out how to get the order I want above.

回答1:

For others to reproduce, here's the sample graph:

g = TinkerGraph.open().traversal()
g.addV().property(id, 'A').
  addV().property(id, 'B').
  addV().property(id, 'C').
  addV().property(id, 'D').
  addV().property(id, 'E').
  addV().property(id, 'F').
  addV().property(id, 'G').
  addE('link').from(V('A')).to(V('B')).
  addE('link').from(V('A')).to(V('C')).
  addE('link').from(V('B')).to(V('D')).
  addE('link').from(V('B')).to(V('E')).
  addE('link').from(V('C')).to(V('F')).
  addE('link').from(V('C')).to(V('G')).iterate()

A depth first search from A should return

A-B-D-E-C-F-G

gremlin> g.V('A').repeat(out('link')).until(__.not(outE('link'))).path().
           unfold().dedup().id().fold()
==>[A,B,D,E,C,F,G]

But if I could get the below order it would be even better

D-E-B-F-G-C-A

This one is kinda rolling up the paths from behind. It's tricky, but doable:

gremlin> g.V('A').
           repeat(outE('link').aggregate('edges').inV()).
             until(__.not(outE('link'))).
           flatMap(
             union(identity(),
                   repeat(inE('link').where(within('edges')).as('current').
                          map(select('edges').unfold().
                                where(neq('current').and(without('done'))).
                              outV().where(without('ad')).fold()).as('bl').
                          select(last, 'current').store('done').
                            filter(outV().where(without('bl').and(without('ad')))).
                          outV().store('ad')).
                     emit())).
           id().fold()
==>[D,E,B,F,G,C,A]

However, it's probably a lot easier to just get the paths and do the ordering on the application side.

回答2:

At the moment: you can't.

We are co-sufferers. This is a known issue that I initially raised on the mailing list and then attempted a fix which unfortunately only works if there's no emit step in the traversal. You are invited to help fix it, I didn't yet have time to dig deeper.