X-Git-Url: http://nitlanguage.org

diff --git a/lib/graph/digraph.nit b/lib/graph/digraph.nit
index e6af185..aa57681 100644
--- 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
@@ -823,6 +839,29 @@ abstract class MutableDigraph[V: Object]
 			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]
@@ -907,3 +946,134 @@ class HashDigraph[V: Object]
 
 	redef fun vertices_iterator: Iterator[V] do return outgoing_vertices_map.keys.iterator
 end
+
+# A reflexive directed graph
+# i.e an element is in relation with itself (ie is implies `self.has_arc(u,u)`))
+# This class avoids manually adding the reflexive vertices and at the same time it's avoids adding useless data to the hashmap.
+class ReflexiveHashDigraph[V: Object]
+	super HashDigraph[V]
+
+	# Adds the arc (u,v) to this graph.
+	# if `u` is the same as `v` do nothing
+	#
+	# ~~~
+	# var g = new ReflexiveHashDigraph[Int]
+	# g.add_arc(1, 2)
+	# g.add_arc(3, 1)
+	# assert g.has_arc(2,2)
+	# assert g.has_arc(1,2)
+	# assert g.has_arc(3,1)
+	# ~~~
+	redef fun add_arc(u, v)
+	do
+		# Check `u` is the same as `v`
+		if u != v then
+			super
+		end
+	end
+
+	# Is (u,v) an arc in this graph?
+	# If `u` is the same as `v` return true
+	#
+	# ~~~
+	# var g = new ReflexiveHashDigraph[Int]
+	# g.add_arc(1, 2)
+	# g.add_arc(3, 1)
+	# g.add_vertex(4)
+	# assert g.has_arc(1,1)
+	# assert g.has_arc(2,2)
+	# assert g.has_arc(2,2)
+	# assert g.has_arc(3,2) == false
+	# assert g.has_arc(4,4)
+	# ~~~
+	redef fun has_arc(u, v)
+	do
+		return u == v or super
+	end
+
+	redef fun show_dot
+	do
+		var f = new ProcessWriter("dot", "-Txlib")
+		f.write to_dot
+		f.close
+		f.wait
+	end
+
+	# Returns a shortest path from vertex `u` to `v`.
+	#
+	# If `u` is the same as `v` return `[u]`
+	#
+	# ~~~
+	# var g = new ReflexiveHashDigraph[Int]
+	# g.add_arc(1, 2)
+	# g.add_arc(2, 3)
+	# g.add_arc(3, 4)
+	# assert g.a_shortest_path(1, 4).length == 4
+	# assert g.a_shortest_path(1, 1).length == 1
+	# ~~~
+	redef fun a_shortest_path(u, v)
+	do
+		if u == v then
+			var path = new List[V]
+			path.add(u)
+			return path
+		end
+		return super
+	end
+
+	# Returns the distance between `u` and `v`
+	#
+	# If `u` is the same as `v` return `1`
+	#
+	# ~~~
+	# var g = new ReflexiveHashDigraph[Int]
+	# g.add_arc(1, 2)
+	# g.add_arc(2, 3)
+	# g.add_arc(3, 4)
+	# assert g.distance(1, 1) == 1
+	# assert g.distance(2, 2) == 1
+	# ~~~
+	redef fun distance(u, v)
+	do
+		if has_arc(u, v) and u == v then return 1
+		return super
+	end
+
+	# Returns the predecessors of `u`.
+	#
+	# `u` is include in the returned collection
+	#
+	# ~~~
+	# var g = new ReflexiveHashDigraph[Int]
+	# g.add_arc(1, 2)
+	# g.add_arc(2, 3)
+	# g.add_arc(3, 1)
+	# assert g.predecessors(2).has(1)
+	# assert g.predecessors(2).has(2)
+	# ~~~
+	redef fun predecessors(u)
+	do
+		var super_predecessors = super
+		if incoming_vertices_map.has_key(u) then super_predecessors.add(u)
+		return super_predecessors
+	end
+
+	# Returns the successors of `u`.
+	#
+	# `u` is include in the returned collection
+	#
+	# ~~~
+	# var g = new ReflexiveHashDigraph[Int]
+	# g.add_arc(1, 2)
+	# g.add_arc(2, 3)
+	# g.add_arc(3, 1)
+	# assert g.successors(2).has(3)
+	# assert g.successors(2).has(2)
+	# ~~~
+	redef fun successors(u: V)
+	do
+		var super_successors = super
+		if outgoing_vertices_map.has_key(u) then super_successors.add(u)
+		return super_successors
+	end
+end