Topological sort in Gremlin

Question

Using the Gremlin/TinkerPop query language, is there a way to compute the topological ordering of a directed acyclic graph?

For example, given a graph with the following edges

a -> b, a -> d, b -> c, c -> d, e -> c

I would like to obtain one of the following topological orderings: a, b, e, c, d, or a, e, b, c, d, or e, a, b, c, d.

Answer 1

Alright, let's create your sample graph first:

g = TinkerGraph.open().traversal()
g.addV(id, "a").as("a").
  addV(id, "b").as("b").
  addV(id, "c").as("c").
  addV(id, "d").as("d").
  addV(id, "e").as("e").
  addE("link").from("a").to("b").
  addE("link").from("a").to("d").
  addE("link").from("b").to("c").
  addE("link").from("c").to("d").
  addE("link").from("e").to("c").iterate()

And this is Kahn's algorithm implemented in Gremlin:

gremlin> g.V().not(__.inE()).store("x").
           repeat(outE().store("e").inV().not(inE().where(without("e"))).store("x")).
         cap("x")
==>[v[a],v[b],v[e],v[c],v[d]]