Repository: tinkerpop Updated Branches: refs/heads/TINKERPOP-1602 d7b7e66d7 -> 1633bd945 (forced update)
Added more cycle detection and traversal induced value recipes. Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/6dba5ec6 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/6dba5ec6 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/6dba5ec6 Branch: refs/heads/TINKERPOP-1602 Commit: 6dba5ec636aed6fd3eeb1ac7db7b4043657689b1 Parents: 9c44f0d Author: Stephen Mallette <sp...@genoprime.com> Authored: Fri Jan 6 08:57:31 2017 -0500 Committer: Stephen Mallette <sp...@genoprime.com> Committed: Fri Jan 6 08:57:31 2017 -0500 ---------------------------------------------------------------------- docs/src/recipes/cycle-detection.asciidoc | 55 ++++++++++++++++++ .../recipes/traversal-induced-values.asciidoc | 60 ++++++++++++++++++++ 2 files changed, 115 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/6dba5ec6/docs/src/recipes/cycle-detection.asciidoc ---------------------------------------------------------------------- diff --git a/docs/src/recipes/cycle-detection.asciidoc b/docs/src/recipes/cycle-detection.asciidoc index 1a8650b..7cebb00 100644 --- a/docs/src/recipes/cycle-detection.asciidoc +++ b/docs/src/recipes/cycle-detection.asciidoc @@ -58,4 +58,59 @@ arbitrary length over both incoming and outgoing edges in the modern graph? g.V().as('a').repeat(both().simplePath()).emit(loops().is(gt(1))). both().where(eq('a')).path(). dedup().by(unfold().order().by(id).dedup().fold()) +---- + +An interesting type of cycle is known as the Eulerian circuit which is a path taken in a graph where each edge is +visited once and the path starts and ends with the same vertex. Consider the following graph, representative of an +imaginary but geographically similar link:https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg[Königsberg] +that happens to have an eighth bridge (the diagram depicts edge direction but direction won't be considered in the traversal): + +image:eulerian-circuit.png[width=500] + +Gremlin can detect if such a cycle exists with: + +[gremlin-groovy] +---- +g.addV().property(id, 'blue').as('b'). + addV().property(id, 'orange').as('o'). + addV().property(id, 'red').as('r'). + addV().property(id, 'green').as('g'). + addE('bridge').from('g').to('b'). + addE('bridge').from('g').to('o'). + addE('bridge').from('g').to('r'). + addE('bridge').from('g').to('r'). + addE('bridge').from('o').to('b'). + addE('bridge').from('o').to('b'). + addE('bridge').from('o').to('r'). + addE('bridge').from('o').to('r').iterate() +g.V().sideEffect(outE("bridge").aggregate("bridges")).barrier(). <1> + repeat(bothE(). <2> + or(__.not(select('e')), + __.not(filter(__.as('x').select(all, 'e').unfold(). <3> + where(eq('x'))))).as('e'). + otherV()). + until(select(all, 'e').count(local).as("c"). <4> + select("bridges").count(local).where(eq("c"))).hasNext() +---- + +<1> Gather all the edges in a "bridges" side effect. +<2> As mentioned earlier with the diagram, directionality is ignored as the traversal uses `bothE` and, later, `otherV`. +<3> In continually traversing over both incoming and outgoing edges, this path is only worth continuing if the edges +traversed thus far are only traversed once. That set of edges is maintained in "e". +<4> The traversal should repeat until the number of edges traversed in "e" is equal to the total number gathered in +the first step above, which would mean that the complete circuit has been made. + +Unlike Königsberg, with just seven bridges, a Eulerian circuit exists in the case with an eighth bridge. The first +detected circuit can be displayed with: + +[gremlin-groovy,existing] +---- +g.V().sideEffect(outE("bridge").aggregate("bridges")).barrier(). + repeat(bothE().or(__.not(select('e')), + __.not(filter(__.as('x').select(all, 'e').unfold(). + where(eq('x'))))).as('e').otherV()). + until(select(all, 'e').count(local).as("c"). + select("bridges").count(local).where(eq("c"))).limit(1). + path().by(id).by(constant(" -> ")). + map {String.join("", it.get().objects())} ---- \ No newline at end of file http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/6dba5ec6/docs/src/recipes/traversal-induced-values.asciidoc ---------------------------------------------------------------------- diff --git a/docs/src/recipes/traversal-induced-values.asciidoc b/docs/src/recipes/traversal-induced-values.asciidoc index 5f48591..e292e16 100644 --- a/docs/src/recipes/traversal-induced-values.asciidoc +++ b/docs/src/recipes/traversal-induced-values.asciidoc @@ -64,4 +64,64 @@ of one `Vertex` to another: g.V().has('name', 'marko').as('marko'). out('created').property('creator', select('marko').by('name')) g.V().has('name', 'marko').out('created').valueMap() +---- + +In a more complex example of how this might work, consider a situation where the goal is to propagate a value stored on +a particular vertex through one of more additional connected vertices using some value on the connecting edges to +determine the value to assign. For example, the following graph depicts three "tank" vertices where the edges represent +the direction a particular "tank" should drain and the "factor" by which it should do it: + +image:traversal-induced-values-1.png[width=700] + +If the traversal started at tank "a", then the value of "amount" on that tank would be used to calculate what the value +of tank "b" was by multiplying it by the value of the "factor" property on the edge between vertices "a" and "b". In +this case the amount of tank "b" would then be 50. Following this pattern, when going from tank "b" to tank "c", the +value of the "amount" of tank "c" would be 5. + +image:traversal-induced-values-2.png[width=700] + +Using Gremlin `sack()`, this kind of operation could be specified as a single traversal: + +[gremlin-groovy] +---- +g.addV(label, 'tank', 'name', 'a', 'amount', 100.0).as('a'). + addV(label, 'tank', 'name', 'b', 'amount', 0.0).as('b'). + addV(label, 'tank', 'name', 'c', 'amount', 0.0).as('c'). + addE('drain').property('factor', 0.5).from('a').to('b'). + addE('drain').property('factor', 0.1).from('b').to('c').iterate() +a = g.V().has('name','a').next() +g.withSack(a.value('amount')). + V(a).repeat(outE('drain').sack(mult).by('factor'). + inV().property('amount', sack())). + until(__.outE('drain').count().is(0)).iterate() +g.V().valueMap() +---- + +The "sack value" gets initialized to the value of tank "a". The traversal iteratively traverses out on the "drain" +edges and uses `mult` to multiply the sack value by the value of "factor". The sack value at that point is then +written to the "amount" of the current vertex. + +As shown in the previous example, `sack()` is a useful way to "carry" and manipulate a value that can be later used +elsewhere in the traversal. Here is another example of its usage where it is utilized to increment all the "age" values +in the modern toy graph by 10: + +[gremlin-groovy,modern] +---- +g.withSack(0).V().has("age"). + sack(assign).by("age").sack(sum).by(constant(10)). + property("age", sack()).valueMap() +---- + +In the above case, the sack is initialized to zero and as each vertex is iterated, the "age" is assigned to the sack +with `sack(assign).by('age')`. That value in the sack is then incremented by the value `constant(10)` and assigned to +the "age" property of the same vertex. + +This value the sack is incremented by need not be a constant. It could also be derived from the traversal itself. +Using the same example, the "weight" property on the incident edges will be used as the value to add to the sack: + +[gremlin-groovy,modern] +---- +g.withSack(0).V().has("age"). + sack(assign).by("age").sack(sum).by(bothE().values("weight").sum()). + property("age", sack()).valueMap() ---- \ No newline at end of file
