#
# To create an (empty) new graph whose keys are integers, one simply type
# ~~~
-# import digraph
-# var g = new HashDigraph[Int]
+# var g0 = new HashDigraph[Int]
# ~~~
#
# Then we can add vertices and arcs. Note that if an arc is added whose source
# and target are not already in the digraph, the vertices are added beforehand.
# ~~~
-# import digraph
-# var g = new HashDigraph[Int]
-# g.add_vertex(0)
-# g.add_vertex(1)
-# g.add_arc(0,1)
-# g.add_arc(1,2)
-# assert g.to_s == "Digraph of 3 vertices and 2 arcs"
+# var g1 = new HashDigraph[Int]
+# g1.add_vertex(0)
+# g1.add_vertex(1)
+# g1.add_arc(0,1)
+# g1.add_arc(1,2)
+# assert g1.to_s == "Digraph of 3 vertices and 2 arcs"
# ~~~
#
# One might also create digraphs with strings in vertices, for instance to
# represent some directed relation. However, it is currently not possible to
# store values in the arcs.
# ~~~
-# import digraph
-# var g = new HashDigraph[String]
-# g.add_vertex("Amy")
-# g.add_vertex("Bill")
-# g.add_vertex("Chris")
-# g.add_vertex("Diane")
-# g.add_arc("Amy", "Bill") # Amy likes Bill
-# g.add_arc("Bill", "Amy") # Bill likes Amy
-# g.add_arc("Chris", "Diane") # and so on
-# g.add_arc("Diane", "Amy") # and so on
+# var g2 = new HashDigraph[String]
+# g2.add_vertex("Amy")
+# g2.add_vertex("Bill")
+# g2.add_vertex("Chris")
+# g2.add_vertex("Diane")
+# g2.add_arc("Amy", "Bill") # Amy likes Bill
+# g2.add_arc("Bill", "Amy") # Bill likes Amy
+# g2.add_arc("Chris", "Diane") # and so on
+# g2.add_arc("Diane", "Amy") # and so on
# ~~~
#
# `HashDigraph`s are mutable, i.e. one might remove arcs and/or vertices:
# ~~~
-# import digraph
-# var g = new HashDigraph[Int]
-# g.add_arc(0,1)
-# g.add_arc(0,2)
-# g.add_arc(1,2)
-# g.add_arc(2,3)
-# g.add_arc(2,4)
-# g.remove_vertex(1)
-# g.remove_arc(2, 4)
-# assert g.to_s == "Digraph of 4 vertices and 2 arcs"
+# var g3 = new HashDigraph[Int]
+# g3.add_arc(0,1)
+# g3.add_arc(0,2)
+# g3.add_arc(1,2)
+# g3.add_arc(2,3)
+# g3.add_arc(2,4)
+# g3.remove_vertex(1)
+# g3.remove_arc(2, 4)
+# assert g3.to_s == "Digraph of 4 vertices and 2 arcs"
# ~~~
#
# If one has installed [Graphviz](http://graphviz.org), it is easy to produce a
# *dot* file which Graphviz process into a picture:
# ~~~
-# import digraph
-# var g = new HashDigraph[Int]
-# g.add_arcs([[0,1],[0,2],[1,2],[2,3],[2,4]])
-# print g.to_dot
+# var g4 = new HashDigraph[Int]
+# g4.add_arcs([[0,1],[0,2],[1,2],[2,3],[2,4]])
+# print g4.to_dot
# # Then call "dot -Tpng -o graph.png"
# ~~~
#
# (https://en.wikipedia.org/wiki/Disjoint-set_data_structure) (i.e. a set of
# sets):
# ~~~
-# import digraph
-# var g = new HashDigraph[Int]
-# g.add_arcs([[1,2],[2,1],[2,3],[3,4],[4,5],[5,3]])
-# for component in g.strongly_connected_components.to_partitions
+# var g5 = new HashDigraph[Int]
+# g5.add_arcs([[1,2],[2,1],[2,3],[3,4],[4,5],[5,3]])
+# for component in g5.strongly_connected_components.to_partitions
# do
# print component
# end
# It is also possible to compute a shortest (directed) path between two
# vertices:
# ~~~
-# import digraph
-# var g = new HashDigraph[Int]
-# g.add_arcs([[1,2],[2,1],[2,3],[3,4],[4,5],[5,3]])
-# var path = g.a_shortest_path(2, 4)
+# var g6 = new HashDigraph[Int]
+# g6.add_arcs([[1,2],[2,1],[2,3],[3,4],[4,5],[5,3]])
+# var path = g6.a_shortest_path(2, 4)
# if path != null then print path else print "No path"
# # Prints [2,3,4]
-# path = g.a_shortest_path(4, 2)
+# path = g6.a_shortest_path(4, 2)
# if path != null then print path else print "No path"
# # Prints "No path"
# ~~~
# The number of vertices in this graph.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_vertex(0)
# g.add_vertex(1)
# The number of arcs in this graph.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(0, 1)
# assert g.num_arcs == 1
# Returns true if and only if `u` exists in this graph.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_vertex(1)
# assert g.has_vertex(1)
# Returns true if and only if `(u,v)` is an arc in this graph.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(0, 1)
# g.add_arc(1, 2)
# If `u` does not exist, then it returns null.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(0, 1)
# g.add_arc(1, 2)
# If `u` does not exist, then an empty collection is returned.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(0, 1)
# g.add_arc(1, 2)
# Returns an iterator over the vertices of this graph.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(0, 1)
# g.add_arc(0, 2)
# An empty graph is a graph without vertex and arc.
#
# ~~~
- # import digraph
# 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.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_vertices([0,2,4,5])
# assert g.vertices.length == 4
# Returns an iterator over the arcs of this graph
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(0, 1)
# g.add_arc(0, 2)
# Returns the arcs of this graph.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 3)
# g.add_arc(2, 3)
# If `u` is not in this graph, an empty array is returned.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 3)
# g.add_arc(2, 3)
# If `u` is not in this graph, an empty array is returned.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 3)
# g.add_arc(2, 3)
# Returns true if and only if `u` is a predecessor of `v`.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 3)
# assert g.is_predecessor(1, 3)
# Returns true if and only if `u` is a successor of `v`.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 3)
# assert not g.is_successor(1, 3)
# Returns the number of arcs whose target is `u`.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 3)
# g.add_arc(2, 3)
# Returns the number of arcs whose source is `u`.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 2)
# g.add_arc(1, 3)
# Returns true if and only if `vertices` is a path of this digraph.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 2)
# g.add_arc(2, 3)
# Returns true if and only if `vertices` is a circuit of this digraph.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 2)
# g.add_arc(2, 3)
# If no path exists between `u` and `v`, it returns `null`.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 2)
# g.add_arc(2, 3)
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)`.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 2)
# g.add_arc(2, 3)
# i.e. the graph obtained by replacing each arc by an edge.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 2)
# g.add_arc(2, 3)
# This is computed in linear time (Tarjan's algorithm).
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(1, 2)
# g.add_arc(2, 3)
# If `u` already belongs to the graph, then nothing happens.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_vertex(0)
# assert g.has_vertex(0)
# If the vertex does not exist in the graph, then nothing happens.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_vertex(0)
# g.add_vertex(1)
# graph, they are added.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(0, 1)
# g.add_arc(1, 2)
# If the arc does not exist in the graph, then nothing happens.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_arc(0, 1)
# assert g.num_arcs == 1
# If vertices appear more than once, they are only added once.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# g.add_vertices([0,1,2,3])
# assert g.num_vertices == 4
# If arcs appear more than once, they are only added once.
#
# ~~~
- # import digraph
# var g = new HashDigraph[Int]
# var arcs = [[0,1], [1,2], [1,2]]
# g.add_arcs(arcs)
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]
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
nitlanguage / nit.git / blobdiff