topological sort

[Harshita Jain]

Hi,

I am trying to perform topological sort on a graph which looks like this :

1 -> 2

1 -> 3

2 -> 4

2 -> 5

3 -> 5

This is the query that I am using : 

g.V().not_(__.inE()).store("x").repeat(outE().store("e").inV().not_(inE().where(without("e"))).store("x")).cap("x").toList()

and the output is : 1-2-5-4-3

The expected answer should be : 1-2-3-4-5 or 1-3-2-4-5 or similar variations.

Any idea what is going wrong here?

[Daniel Kuppitz]

Your query you're looking for is a lot simpler than what you have now:

gremlin> g = TinkerGraph.open().traversal()

==>graphtraversalsource[tinkergraph[vertices:0 edges:0], standard]

gremlin> g.addV().property(id, 1).

......1>   addV().property(id, 2).

......2>   addV().property(id, 3).

......3>   addV().property(id, 4).

......4>   addV().property(id, 5).

......5>   addE('link').from(V(1)).to(V(2)).

......6>   addE('link').from(V(1)).to(V(3)).

......7>   addE('link').from(V(2)).to(V(4)).

......8>   addE('link').from(V(2)).to(V(5)).

......9>   addE('link').from(V(3)).to(V(5)).

.....10>   iterate()

gremlin> g.V().not(inE()).

           emit().

            repeat(out().dedup())

==>v[1]

==>v[2]

==>v[3]

==>v[4]

==>v[5]

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-users+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/d1666330-323d-4043-8eeb-6395e15d2ea8%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Harshita Jain]

Thank you, Daniel. 

I tried with the above query by adding one more edge and in this case the answer is not correct

1 -> 2

1 -> 3

2 -> 4

2 -> 5

3 -> 5

New edge : 5 -> 4

Expected Answer : 1, 2, 3, 5, 4 or 1, 3, 2, 5, 4 

Output : 1, 2, 3, 4, 5

Any idea about this?

To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.

[Harshita Jain]

Also, I tried again with 

1 -> 2

1 -> 3

2 -> 4

2 -> 5

3 -> 5

New edge : 5 -> 4, 6 -> 2

The output was : 6 - 2 - 5- 4 - 1 - 3

This is wrong as 2 can never occur before 1. 

[Daniel Kuppitz]

Then it's probably easier to transform the result using Groovy:

g = TinkerGraph.open().traversal()

g.addV().property(id, 1).

  addV().property(id, 2).

  addV().property(id, 3).

  addV().property(id, 4).

  addV().property(id, 5).

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

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

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

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

  addE('link').from(V(3)).to(V(5)).

  addE('link').from(V(5)).to(V(4)).

  iterate()

g.V().not(inE()).

  emit().

   repeat(out()).

  reverse().unique().reverse()

The same is possible using pure Gremlin, but it's a lot more complicated in comparison. Would be nice if we would have a reverse() step:

g.V().not(inE()).

  emit().

   repeat(out()).

  store('a').

    by(project('v','i').

         by().

         by(select('a').count(local))).cap('a').

  unfold().

  order().

    by(select('i'), decr).

  barrier().

  dedup().

    by(select('v')).

  order().

    by(select('i')).

  select('v')

Cheers,

Daniel

To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-users+unsubscribe@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/311d0c6f-14fd-42a4-bedc-096a3341341b%40googlegroups.com.