Merge: lib/core: provide default codec-aware read_char

[nit.git] / lib / graph / digraph.nit

diff --git a/lib/graph/digraph.nit b/lib/graph/digraph.nit
index 7ddb5a8..e574dc4 100644 (file)
--- a/lib/graph/digraph.nit
+++ b/lib/graph/digraph.nit
@@ -506,6 +506,22 @@ interface Digraph[V: Object]
                end
        end
 
+       # Build a path (or circuit) from the vertex `start` that visits every edge exactly once.
+       #
+       # ~~~
+       # var g = new HashDigraph[Int]
+       # g.add_arc(1, 2)
+       # g.add_arc(2, 3)
+       # g.add_arc(3, 4)
+       # assert g.eulerian_path(1) == [1, 2, 3, 4]
+       # ~~~
+       fun eulerian_path(start: V): Array[V]
+       do
+               var visited = new HashDigraph[V]
+               visited.add_graph(self)
+               return visited.remove_eulerian_path(start)
+       end
+
        # Returns the distance between `u` and `v`
        #
        # If no path exists between `u` and `v`, it returns null. It is not
@@ -796,6 +812,56 @@ abstract class MutableDigraph[V: Object]
        do
                for a in arcs do add_arc(a[0], a[1])
        end
+
+       # Add all vertices and arcs from the `other` graph.
+       #
+       # ~~~
+       # var g1 = new HashDigraph[Int]
+       # var arcs1 = [[0,1], [1,2]]
+       # g1.add_arcs(arcs1)
+       # g1.add_arcs(arcs1)
+       # g1.add_vertex(3)
+       # var g2 = new HashDigraph[Int]
+       # var arcs2 = [[0,1], [1,4]]
+       # g2.add_arcs(arcs2)
+       # g2.add_vertex(5)
+       # g2.add_graph(g1)
+       # assert g2.vertices.has_exactly([0, 1, 2, 3, 4, 5])
+       # var arcs3 = [[0,1], [1,2], [1,4]]
+       # assert g2.arcs.has_exactly(arcs3)
+       # ~~~
+       fun add_graph(other: Digraph[V])
+       do
+               for v in other.vertices do
+                       add_vertex(v)
+                       for w in other.successors(v) do
+                               add_arc(v, w)
+                       end
+               end
+       end
+
+       # Build a path (or circuit) that removes every edge exactly once.
+       #
+       # See `eulerian_path` for details
+       fun remove_eulerian_path(start: V): Array[V]
+       do
+               var stack = new Array[V]
+               var path = new Array[V]
+               var current = start
+               loop
+                       if out_degree(current) == 0 then
+                               path.unshift current
+                               if stack.is_empty then break
+                               current = stack.pop
+                       else
+                               stack.add current
+                               var n = successors(current).first
+                               remove_arc(current, n)
+                               current = n
+                       end
+               end
+               return path
+       end
 end
 # A directed graph represented by hash maps
 class HashDigraph[V: Object]