# Interface for digraphs
interface Digraph[V: Object]

	## ---------------- ##
	## Abstract methods ##
	## ---------------- ##

	# The number of vertices in this graph.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_vertex(0)
	# g.add_vertex(1)
	# assert g.num_vertices == 2
	# g.add_vertex(0)
	# assert g.num_vertices == 2
	# ~~~
	fun num_vertices: Int is abstract

	# The number of arcs in this graph.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(0, 1)
	# assert g.num_arcs == 1
	# g.add_arc(0, 1)
	# assert g.num_arcs == 1
	# g.add_arc(2, 3)
	# assert g.num_arcs == 2
	# ~~~
	fun num_arcs: Int is abstract

	# Returns true if and only if `u` exists in this graph.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_vertex(1)
	# assert g.has_vertex(1)
	# assert not g.has_vertex(0)
	# g.add_vertex(1)
	# assert g.has_vertex(1)
	# assert not g.has_vertex(0)
	# ~~~
	fun has_vertex(u: V): Bool is abstract

	# Returns true if and only if `(u,v)` is an arc in this graph.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(0, 1)
	# g.add_arc(1, 2)
	# assert g.has_arc(0, 1)
	# assert g.has_arc(1, 2)
	# assert not g.has_arc(0, 2)
	# ~~~
	fun has_arc(u, v: V): Bool is abstract

	# Returns the predecessors of `u`.
	#
	# If `u` does not exist, then it returns null.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(0, 1)
	# g.add_arc(1, 2)
	# g.add_arc(0, 2)
	# assert g.predecessors(2).has(0)
	# assert g.predecessors(2).has(1)
	# assert not g.predecessors(2).has(2)
	# ~~~
	fun predecessors(u: V): Collection[V] is abstract

	# Returns the successors of `u`.
	#
	# If `u` does not exist, then an empty collection is returned.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(0, 1)
	# g.add_arc(1, 2)
	# g.add_arc(0, 2)
	# assert not g.successors(0).has(0)
	# assert g.successors(0).has(1)
	# assert g.successors(0).has(2)
	# ~~~
	fun successors(u: V): Collection[V] is abstract

	# Returns an iterator over the vertices of this graph.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(0, 1)
	# g.add_arc(0, 2)
	# g.add_arc(1, 2)
	# var vs = new HashSet[Int]
	# for v in g.vertices_iterator do vs.add(v)
	# assert vs == new HashSet[Int].from([0,1,2])
	# ~~~
	fun vertices_iterator: Iterator[V] is abstract

	## -------------------- ##
	## Non abstract methods ##
	## -------------------- ##

	## ------------- ##
	## Basic methods ##
	## ------------- ##

	# Returns true if and only if this graph is empty.
	#
	# An empty graph is a graph without vertex and arc.
	#
	# ~~~
	# assert (new HashDigraph[Int]).is_empty
	# ~~~
	fun is_empty: Bool do return num_vertices == 0 and num_arcs == 0

	# Returns an array containing the vertices of this graph.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_vertices([0,2,4,5])
	# assert g.vertices.length == 4
	# ~~~
	fun vertices: Array[V] do return [for u in vertices_iterator do u]

	# Returns an iterator over the arcs of this graph
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(0, 1)
	# g.add_arc(0, 2)
	# g.add_arc(1, 2)
	# for arc in g.arcs_iterator do
	#	assert g.has_arc(arc[0], arc[1])
	# end
	# ~~~
	fun arcs_iterator: Iterator[Array[V]] do return new ArcsIterator[V](self)

	# Returns the arcs of this graph.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 3)
	# g.add_arc(2, 3)
	# assert g.arcs.length == 2
	# ~~~
	fun arcs: Array[Array[V]] do return [for arc in arcs_iterator do arc]

	# Returns the incoming arcs of vertex `u`.
	#
	# If `u` is not in this graph, an empty array is returned.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 3)
	# g.add_arc(2, 3)
	# for arc in g.incoming_arcs(3) do
	#	assert g.is_predecessor(arc[0], arc[1])
	# end
	# ~~~
	fun incoming_arcs(u: V): Collection[Array[V]]
	do
		if has_vertex(u) then
			return [for v in predecessors(u) do [v, u]]
		else
			return new Array[Array[V]]
		end
	end

	# Returns the outgoing arcs of vertex `u`.
	#
	# If `u` is not in this graph, an empty array is returned.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 3)
	# g.add_arc(2, 3)
	# g.add_arc(1, 2)
	# for arc in g.outgoing_arcs(1) do
	#	assert g.is_successor(arc[1], arc[0])
	# end
	# ~~~
	fun outgoing_arcs(u: V): Collection[Array[V]]
	do
		if has_vertex(u) then
			return [for v in successors(u) do [u, v]]
		else
			return new Array[Array[V]]
		end
	end

	## ---------------------- ##
	## String representations ##
	## ---------------------- ##

	redef fun to_s
	do
		var vertex_word = "vertices"
		var arc_word = "arcs"
		if num_vertices <= 1 then vertex_word = "vertex"
		if num_arcs <= 1 then arc_word = "arc"
		return "Digraph of {num_vertices} {vertex_word} and {num_arcs} {arc_word}"
	end

	# Returns a GraphViz string representing this digraph.
	fun to_dot: String
	do
		var s = "digraph \{\n"
		var id_set = new HashMap[V, Int]
		# Writing the vertices
		for u in vertices_iterator, i in [0 .. vertices.length[ do
			id_set[u] = i
			s += "   \"{i}\" "
			s += "[label=\"{u.to_s.escape_to_dot}\"];\n"
		end
		# Writing the arcs
		for arc in arcs do
			s += "   {id_set[arc[0]]} "
			s += "-> {id_set[arc[1]]};"
		end
		s += "\}"
		return s
	end

	# Open Graphviz with `self.to_dot`.
	#
	# Mainly used for debugging.
	fun show_dot do
		var f = new ProcessWriter("dot", "-Txlib")
		f.write to_dot
		f.close
	end

	## ------------ ##
	## Neighborhood ##
	## ------------ ##

	# Returns true if and only if `u` is a predecessor of `v`.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 3)
	# assert g.is_predecessor(1, 3)
	# assert not g.is_predecessor(3, 1)
	# ~~~
	fun is_predecessor(u, v: V): Bool do return has_arc(u, v)

	# Returns true if and only if `u` is a successor of `v`.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 3)
	# assert not g.is_successor(1, 3)
	# assert g.is_successor(3, 1)
	# ~~~
	fun is_successor(u, v: V): Bool do return has_arc(v, u)

	# Returns the number of arcs whose target is `u`.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 3)
	# g.add_arc(2, 3)
	# assert g.in_degree(3) == 2
	# assert g.in_degree(1) == 0
	# ~~~
	fun in_degree(u: V): Int do return predecessors(u).length

	# Returns the number of arcs whose source is `u`.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 2)
	# g.add_arc(1, 3)
	# g.add_arc(2, 3)
	# assert g.out_degree(3) == 0
	# assert g.out_degree(1) == 2
	# ~~~
	fun out_degree(u: V): Int do return successors(u).length

	# ------------------ #
	# Paths and circuits #
	# ------------------ #

	# Returns true if and only if `vertices` is a path of this digraph.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 2)
	# g.add_arc(2, 3)
	# g.add_arc(3, 4)
	# assert g.has_path([1,2,3])
	# assert not g.has_path([1,3,3])
	# ~~~
	fun has_path(vertices: SequenceRead[V]): Bool
	do
		for i in [0..vertices.length - 1[ do
			if not has_arc(vertices[i], vertices[i + 1]) then return false
		end
		return true
	end

	# Returns true if and only if `vertices` is a circuit of this digraph.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 2)
	# g.add_arc(2, 3)
	# g.add_arc(3, 1)
	# assert g.has_circuit([1,2,3,1])
	# assert not g.has_circuit([1,3,2,1])
	# ~~~
	fun has_circuit(vertices: SequenceRead[V]): Bool
	do
		return vertices.is_empty or (has_path(vertices) and vertices.first == vertices.last)
	end

	# Returns a shortest path from vertex `u` to `v`.
	#
	# If no path exists between `u` and `v`, it returns `null`.
	#
	# ~~~
	# var g = new HashDigraph[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
	# g.add_arc(1, 3)
	# assert g.a_shortest_path(1, 4).length == 3
	# assert g.a_shortest_path(4, 1) == null
	# ~~~
	fun a_shortest_path(u, v: V): nullable Sequence[V]
	do
		var queue = new List[V].from([u]).as_fifo
		var pred = new HashMap[V, nullable V]
		var visited = new HashSet[V]
		var w: nullable V = null
		pred[u] = null
		while not queue.is_empty do
			w = queue.take
			if not visited.has(w) then
				visited.add(w)
				if w == v then break
				for wp in successors(w) do
					if not pred.keys.has(wp) then
						queue.add(wp)
						pred[wp] = w
					end
				end
			end
		end
		if w != v then
			return null
		else
			var path = new List[V]
			path.add(v)
			w = v
			while pred[w] != null do
				path.unshift(pred[w].as(not null))
				w = pred[w]
			end
			return path
		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
	# symmetric, i.e. we may have `dist(u, v) != dist(v, u)`.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 2)
	# g.add_arc(2, 3)
	# g.add_arc(3, 4)
	# assert g.distance(1, 4) == 3
	# g.add_arc(1, 3)
	# assert g.distance(1, 4) == 2
	# assert g.distance(4, 1) == null
	# ~~~
	fun distance(u, v: V): nullable Int
	do
		var queue = new List[V].from([u]).as_fifo
		var dist = new HashMap[V, Int]
		var visited = new HashSet[V]
		var w: nullable V
		dist[u] = 0
		while not queue.is_empty do
			w = queue.take
			if not visited.has(w) then
				visited.add(w)
				if w == v then break
				for wp in successors(w) do
					if not dist.keys.has(wp) then
						queue.add(wp)
						dist[wp] = dist[w] + 1
					end
				end
			end
		end
		return dist.get_or_null(v)
	end

	# -------------------- #
	# Connected components #
	# -------------------- #

	# Returns the weak connected components of this digraph.
	#
	# The weak connected components of a digraph are the usual
	# connected components of its associated undirected graph,
	# i.e. the graph obtained by replacing each arc by an edge.
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 2)
	# g.add_arc(2, 3)
	# g.add_arc(4, 5)
	# assert g.weakly_connected_components.number_of_subsets == 2
	# ~~~
	fun weakly_connected_components: DisjointSet[V]
	do
		var components = new DisjointSet[V]
		components.add_all(vertices)
		for arc in arcs_iterator do
			components.union(arc[0], arc[1])
		end
		return components
	end

	# Returns the strongly connected components of this digraph.
	#
	# Two vertices `u` and `v` belong to the same strongly connected
	# component if and only if there exists a path from `u` to `v`
	# and there exists a path from `v` to `u`.
	#
	# This is computed in linear time (Tarjan's algorithm).
	#
	# ~~~
	# var g = new HashDigraph[Int]
	# g.add_arc(1, 2)
	# g.add_arc(2, 3)
	# g.add_arc(3, 1)
	# g.add_arc(3, 4)
	# g.add_arc(4, 5)
	# g.add_arc(5, 6)
	# g.add_arc(6, 5)
	# assert g.strongly_connected_components.number_of_subsets == 3
	# ~~~
	fun strongly_connected_components: DisjointSet[V]
	do
		var tarjanAlgorithm = new TarjanAlgorithm[V](self)
		return tarjanAlgorithm.strongly_connected_components
	end
end