1 # This file is part of NIT (http://www.nitlanguage.org).
3 # Copyright 2015 Alexandre Blondin Massé <blondin_masse.alexandre@uqam.ca>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
17 # Implementation of directed graphs, also called digraphs.
22 # This module provides a simple interface together with a concrete
23 # implementation of directed graphs (or digraphs).
25 # The upper level interface is `Digraph` and contains all methods for digraphs
26 # that do not depend on the underlying data structure. More precisely, if basic
27 # operations such as `predecessors`, `successors`, `num_vertices`, etc. are
28 # implemented, then high level operations (such as computing the connected
29 # components or a shortest path between two vertices) can be easily derived.
30 # Also, all methods found in `Digraph` do no modify the graph. For mutable
31 # methods, one needs to check the `MutableDigraph` child class. Vertices can be
32 # any `Object`, but there is no information stored in the arcs, which are
33 # simple arrays of the form `[u,v]`, where `u` is the source of the arc and `v`
36 # There is currently only one concrete implementation named `HashDigraph` that
37 # makes use of the HashMap class for storing the predecessors and successors.
38 # It is therefore simple to provide another implementation: One only has to
39 # create a concrete specialization of either `Digraph` or `MutableDigraph`.
44 # To create an (empty) new graph whose keys are integers, one simply type
46 # var g0 = new HashDigraph[Int]
49 # Then we can add vertices and arcs. Note that if an arc is added whose source
50 # and target are not already in the digraph, the vertices are added beforehand.
52 # var g1 = new HashDigraph[Int]
57 # assert g1.to_s == "Digraph of 3 vertices and 2 arcs"
60 # One might also create digraphs with strings in vertices, for instance to
61 # represent some directed relation. However, it is currently not possible to
62 # store values in the arcs.
64 # var g2 = new HashDigraph[String]
65 # g2.add_vertex("Amy")
66 # g2.add_vertex("Bill")
67 # g2.add_vertex("Chris")
68 # g2.add_vertex("Diane")
69 # g2.add_arc("Amy", "Bill") # Amy likes Bill
70 # g2.add_arc("Bill", "Amy") # Bill likes Amy
71 # g2.add_arc("Chris", "Diane") # and so on
72 # g2.add_arc("Diane", "Amy") # and so on
75 # `HashDigraph`s are mutable, i.e. one might remove arcs and/or vertices:
77 # var g3 = new HashDigraph[Int]
85 # assert g3.to_s == "Digraph of 4 vertices and 2 arcs"
88 # If one has installed [Graphviz](http://graphviz.org), it is easy to produce a
89 # *dot* file which Graphviz process into a picture:
91 # var g4 = new HashDigraph[Int]
92 # g4.add_arcs([[0,1],[0,2],[1,2],[2,3],[2,4]])
94 # # Then call "dot -Tpng -o graph.png"
97 # ![A graph drawing produced by Graphviz](https://github.com/nitlang/nit/blob/master/lib/graph.png)
102 # There exist other methods available for digraphs and many other will be
103 # implemented in the future. For more details, one should look at the methods
104 # directly. For instance, the [strongly connected components]
105 # (https://en.wikipedia.org/wiki/Strongly_connected_component) of a digraph are
106 # returned as a [disjoint set data structure]
107 # (https://en.wikipedia.org/wiki/Disjoint-set_data_structure) (i.e. a set of
110 # var g5 = new HashDigraph[Int]
111 # g5.add_arcs([[1,2],[2,1],[2,3],[3,4],[4,5],[5,3]])
112 # for component in g5.strongly_connected_components.to_partitions
116 # # Prints [1,2] and [3,4,5]
119 # It is also possible to compute a shortest (directed) path between two
122 # var g6 = new HashDigraph[Int]
123 # g6.add_arcs([[1,2],[2,1],[2,3],[3,4],[4,5],[5,3]])
124 # var path = g6.a_shortest_path(2, 4)
125 # if path != null then print path else print "No path"
127 # path = g6.a_shortest_path(4, 2)
128 # if path != null then print path else print "No path"
132 # Extending the library
133 # =====================
135 # There are at least two ways of providing new methods on digraphs. If the
136 # method is standard and could be useful to other users, you should consider
137 # including your implementation directly in this library.
139 # Otherwise, for personal use, you should simply define a new class inheriting
140 # from `HashDigraph` and add the new services.
143 # Interface for digraphs
144 interface Digraph[V
: Object]
146 ## ---------------- ##
147 ## Abstract methods ##
148 ## ---------------- ##
150 # The number of vertices in this graph.
153 # var g = new HashDigraph[Int]
156 # assert g.num_vertices == 2
158 # assert g.num_vertices == 2
160 fun num_vertices
: Int is abstract
162 # The number of arcs in this graph.
165 # var g = new HashDigraph[Int]
167 # assert g.num_arcs == 1
169 # assert g.num_arcs == 1
171 # assert g.num_arcs == 2
173 fun num_arcs
: Int is abstract
175 # Returns true if and only if `u` exists in this graph.
178 # var g = new HashDigraph[Int]
180 # assert g.has_vertex(1)
181 # assert not g.has_vertex(0)
183 # assert g.has_vertex(1)
184 # assert not g.has_vertex(0)
186 fun has_vertex
(u
: V
): Bool is abstract
188 # Returns true if and only if `(u,v)` is an arc in this graph.
191 # var g = new HashDigraph[Int]
194 # assert g.has_arc(0, 1)
195 # assert g.has_arc(1, 2)
196 # assert not g.has_arc(0, 2)
198 fun has_arc
(u
, v
: V
): Bool is abstract
200 # Returns the predecessors of `u`.
202 # If `u` does not exist, then it returns null.
205 # var g = new HashDigraph[Int]
209 # assert g.predecessors(2).has(0)
210 # assert g.predecessors(2).has(1)
211 # assert not g.predecessors(2).has(2)
213 fun predecessors
(u
: V
): Collection[V
] is abstract
215 # Returns the successors of `u`.
217 # If `u` does not exist, then an empty collection is returned.
220 # var g = new HashDigraph[Int]
224 # assert not g.successors(0).has(0)
225 # assert g.successors(0).has(1)
226 # assert g.successors(0).has(2)
228 fun successors
(u
: V
): Collection[V
] is abstract
230 # Returns an iterator over the vertices of this graph.
233 # var g = new HashDigraph[Int]
237 # var vs = new HashSet[Int]
238 # for v in g.vertices_iterator do vs.add(v)
239 # assert vs == new HashSet[Int].from([0,1,2])
241 fun vertices_iterator
: Iterator[V
] is abstract
243 ## -------------------- ##
244 ## Non abstract methods ##
245 ## -------------------- ##
251 # Returns true if and only if this graph is empty.
253 # An empty graph is a graph without vertex and arc.
256 # assert (new HashDigraph[Int]).is_empty
258 fun is_empty
: Bool do return num_vertices
== 0 and num_arcs
== 0
260 # Returns an array containing the vertices of this graph.
263 # var g = new HashDigraph[Int]
264 # g.add_vertices([0,2,4,5])
265 # assert g.vertices.length == 4
267 fun vertices
: Array[V
] do return [for u
in vertices_iterator
do u
]
269 # Returns an iterator over the arcs of this graph
272 # var g = new HashDigraph[Int]
276 # for arc in g.arcs_iterator do
277 # assert g.has_arc(arc[0], arc[1])
280 fun arcs_iterator
: Iterator[Array[V
]] do return new ArcsIterator[V
](self)
282 # Returns the arcs of this graph.
285 # var g = new HashDigraph[Int]
288 # assert g.arcs.length == 2
290 fun arcs
: Array[Array[V
]] do return [for arc
in arcs_iterator
do arc
]
292 # Returns the incoming arcs of vertex `u`.
294 # If `u` is not in this graph, an empty array is returned.
297 # var g = new HashDigraph[Int]
300 # for arc in g.incoming_arcs(3) do
301 # assert g.is_predecessor(arc[0], arc[1])
304 fun incoming_arcs
(u
: V
): Collection[Array[V
]]
306 if has_vertex
(u
) then
307 return [for v
in predecessors
(u
) do [v
, u
]]
309 return new Array[Array[V
]]
313 # Returns the outgoing arcs of vertex `u`.
315 # If `u` is not in this graph, an empty array is returned.
318 # var g = new HashDigraph[Int]
322 # for arc in g.outgoing_arcs(1) do
323 # assert g.is_successor(arc[1], arc[0])
326 fun outgoing_arcs
(u
: V
): Collection[Array[V
]]
328 if has_vertex
(u
) then
329 return [for v
in successors
(u
) do [u
, v
]]
331 return new Array[Array[V
]]
335 ## ---------------------- ##
336 ## String representations ##
337 ## ---------------------- ##
341 var vertex_word
= "vertices"
342 var arc_word
= "arcs"
343 if num_vertices
<= 1 then vertex_word
= "vertex"
344 if num_arcs
<= 1 then arc_word
= "arc"
345 return "Digraph of {num_vertices} {vertex_word} and {num_arcs} {arc_word}"
348 # Returns a GraphViz string representing this digraph.
351 var s
= "digraph \{\n"
352 var id_set
= new HashMap[V
, Int]
353 # Writing the vertices
354 for u
in vertices_iterator
, i
in [0 .. vertices
.length
[ do
357 s
+= "[label=\"{u.to_s.escape_to_dot}\
"];\n"
361 s
+= " {id_set[arc[0]]} "
362 s
+= "-> {id_set[arc[1]]};"
368 # Open Graphviz with `self.to_dot`.
370 # Mainly used for debugging.
372 var f
= new ProcessWriter("dot", "-Txlib")
381 # Returns true if and only if `u` is a predecessor of `v`.
384 # var g = new HashDigraph[Int]
386 # assert g.is_predecessor(1, 3)
387 # assert not g.is_predecessor(3, 1)
389 fun is_predecessor
(u
, v
: V
): Bool do return has_arc
(u
, v
)
391 # Returns true if and only if `u` is a successor of `v`.
394 # var g = new HashDigraph[Int]
396 # assert not g.is_successor(1, 3)
397 # assert g.is_successor(3, 1)
399 fun is_successor
(u
, v
: V
): Bool do return has_arc
(v
, u
)
401 # Returns the number of arcs whose target is `u`.
404 # var g = new HashDigraph[Int]
407 # assert g.in_degree(3) == 2
408 # assert g.in_degree(1) == 0
410 fun in_degree
(u
: V
): Int do return predecessors
(u
).length
412 # Returns the number of arcs whose source is `u`.
415 # var g = new HashDigraph[Int]
419 # assert g.out_degree(3) == 0
420 # assert g.out_degree(1) == 2
422 fun out_degree
(u
: V
): Int do return successors
(u
).length
424 # ------------------ #
425 # Paths and circuits #
426 # ------------------ #
428 # Returns true if and only if `vertices` is a path of this digraph.
431 # var g = new HashDigraph[Int]
435 # assert g.has_path([1,2,3])
436 # assert not g.has_path([1,3,3])
438 fun has_path
(vertices
: SequenceRead[V
]): Bool
440 for i
in [0..vertices
.length
- 1[ do
441 if not has_arc
(vertices
[i
], vertices
[i
+ 1]) then return false
446 # Returns true if and only if `vertices` is a circuit of this digraph.
449 # var g = new HashDigraph[Int]
453 # assert g.has_circuit([1,2,3,1])
454 # assert not g.has_circuit([1,3,2,1])
456 fun has_circuit
(vertices
: SequenceRead[V
]): Bool
458 return vertices
.is_empty
or (has_path
(vertices
) and vertices
.first
== vertices
.last
)
461 # Returns a shortest path from vertex `u` to `v`.
463 # If no path exists between `u` and `v`, it returns `null`.
466 # var g = new HashDigraph[Int]
470 # assert g.a_shortest_path(1, 4).length == 4
472 # assert g.a_shortest_path(1, 4).length == 3
473 # assert g.a_shortest_path(4, 1) == null
475 fun a_shortest_path
(u
, v
: V
): nullable Sequence[V
]
477 var queue
= new List[V
].from
([u
]).as_fifo
478 var pred
= new HashMap[V
, nullable V
]
479 var visited
= new HashSet[V
]
480 var w
: nullable V
= null
482 while not queue
.is_empty
do
484 if not visited
.has
(w
) then
487 for wp
in successors
(w
) do
488 if not pred
.keys
.has
(wp
) then
498 var path
= new List[V
]
501 while pred
[w
] != null do
502 path
.unshift
(pred
[w
].as(not null))
509 # Build a path (or circuit) from the vertex `start` that visits every edge exactly once.
512 # var g = new HashDigraph[Int]
516 # assert g.eulerian_path(1) == [1, 2, 3, 4]
518 fun eulerian_path
(start
: V
): Array[V
]
520 var visited
= new HashDigraph[V
]
521 visited
.add_graph
(self)
522 return visited
.remove_eulerian_path
(start
)
525 # Returns the distance between `u` and `v`
527 # If no path exists between `u` and `v`, it returns null. It is not
528 # symmetric, i.e. we may have `dist(u, v) != dist(v, u)`.
531 # var g = new HashDigraph[Int]
535 # assert g.distance(1, 4) == 3
537 # assert g.distance(1, 4) == 2
538 # assert g.distance(4, 1) == null
540 fun distance
(u
, v
: V
): nullable Int
542 var queue
= new List[V
].from
([u
]).as_fifo
543 var dist
= new HashMap[V
, Int]
544 var visited
= new HashSet[V
]
547 while not queue
.is_empty
do
549 if not visited
.has
(w
) then
552 for wp
in successors
(w
) do
553 if not dist
.keys
.has
(wp
) then
555 dist
[wp
] = dist
[w
] + 1
560 return dist
.get_or_null
(v
)
563 # -------------------- #
564 # Connected components #
565 # -------------------- #
567 # Returns the weak connected components of this digraph.
569 # The weak connected components of a digraph are the usual
570 # connected components of its associated undirected graph,
571 # i.e. the graph obtained by replacing each arc by an edge.
574 # var g = new HashDigraph[Int]
578 # assert g.weakly_connected_components.number_of_subsets == 2
580 fun weakly_connected_components
: DisjointSet[V
]
582 var components
= new DisjointSet[V
]
583 components
.add_all
(vertices
)
584 for arc
in arcs_iterator
do
585 components
.union
(arc
[0], arc
[1])
590 # Returns the strongly connected components of this digraph.
592 # Two vertices `u` and `v` belong to the same strongly connected
593 # component if and only if there exists a path from `u` to `v`
594 # and there exists a path from `v` to `u`.
596 # This is computed in linear time (Tarjan's algorithm).
599 # var g = new HashDigraph[Int]
607 # assert g.strongly_connected_components.number_of_subsets == 3
609 fun strongly_connected_components
: DisjointSet[V
]
611 var tarjanAlgorithm
= new TarjanAlgorithm[V
](self)
612 return tarjanAlgorithm
.strongly_connected_components
616 # Computing the strongly connected components using Tarjan's algorithm
617 private class TarjanAlgorithm[V
: Object]
618 # The graph whose strongly connected components will be computed
619 var graph
: Digraph[V
]
620 # The strongly connected components computed in Tarjan's algorithm
621 var sccs
= new DisjointSet[V
]
622 # An index used for Tarjan's algorithm
624 # A stack used for Tarjan's algorithm
625 var stack
: Queue[V
] = (new Array[V
]).as_lifo
626 # A map associating with each vertex its index
627 var vertex_to_index
= new HashMap[V
, Int]
628 # A map associating with each vertex its ancestor in Tarjan's algorithm
629 var ancestor
= new HashMap[V
, Int]
630 # True if and only if the vertex is in the stack
631 var in_stack
= new HashSet[V
]
633 # Returns the strongly connected components of a graph
634 fun strongly_connected_components
: DisjointSet[V
]
636 for u
in graph
.vertices_iterator
do sccs
.add
(u
)
637 for v
in graph
.vertices_iterator
do
643 # The recursive part of Tarjan's algorithm
646 vertex_to_index
[u
] = index
651 for v
in graph
.successors
(u
) do
652 if not vertex_to_index
.keys
.has
(v
) then
654 ancestor
[u
] = ancestor
[u
].min
(ancestor
[v
])
655 else if in_stack
.has
(v
) then
656 ancestor
[u
] = ancestor
[u
].min
(vertex_to_index
[v
])
659 if vertex_to_index
[u
] == ancestor
[u
] then
672 class ArcsIterator[V
: Object]
673 super Iterator[Array[V
]]
675 # The graph whose arcs are iterated over
676 var graph
: Digraph[V
]
679 private var sources_iterator
: Iterator[V
] is noinit
680 private var targets_iterator
: Iterator[V
] is noinit
683 sources_iterator
= graph
.vertices_iterator
684 if sources_iterator
.is_ok
then
685 targets_iterator
= graph
.successors
(sources_iterator
.item
).iterator
686 if not targets_iterator
.is_ok
then update_iterators
690 redef fun is_ok
do return sources_iterator
.is_ok
and targets_iterator
.is_ok
692 redef fun item
do return [sources_iterator
.item
, targets_iterator
.item
]
696 targets_iterator
.next
700 private fun update_iterators
702 while not targets_iterator
.is_ok
and sources_iterator
.is_ok
704 sources_iterator
.next
705 if sources_iterator
.is_ok
then
706 targets_iterator
= graph
.successors
(sources_iterator
.item
).iterator
713 abstract class MutableDigraph[V
: Object]
716 ## ---------------- ##
717 ## Abstract methods ##
718 ## ---------------- ##
720 # Adds the vertex `u` to this graph.
722 # If `u` already belongs to the graph, then nothing happens.
725 # var g = new HashDigraph[Int]
727 # assert g.has_vertex(0)
728 # assert not g.has_vertex(1)
730 # assert g.num_vertices == 2
732 fun add_vertex
(u
: V
) is abstract
734 # Removes the vertex `u` from this graph and all its incident arcs.
736 # If the vertex does not exist in the graph, then nothing happens.
739 # var g = new HashDigraph[Int]
742 # assert g.has_vertex(0)
744 # assert not g.has_vertex(0)
746 fun remove_vertex
(u
: V
) is abstract
748 # Adds the arc `(u,v)` to this graph.
750 # If there is already an arc from `u` to `v` in this graph, then
751 # nothing happens. If vertex `u` or vertex `v` do not exist in the
752 # graph, they are added.
755 # var g = new HashDigraph[Int]
758 # assert g.has_arc(0, 1)
759 # assert g.has_arc(1, 2)
760 # assert not g.has_arc(1, 0)
762 # assert g.num_arcs == 2
764 fun add_arc
(u
, v
: V
) is abstract
766 # Removes the arc `(u,v)` from this graph.
768 # If the arc does not exist in the graph, then nothing happens.
771 # var g = new HashDigraph[Int]
773 # assert g.num_arcs == 1
775 # assert g.num_arcs == 0
777 # assert g.num_arcs == 0
779 fun remove_arc
(u
, v
: V
) is abstract
781 ## -------------------- ##
782 ## Non abstract methods ##
783 ## -------------------- ##
785 # Adds all vertices of `vertices` to this digraph.
787 # If vertices appear more than once, they are only added once.
790 # var g = new HashDigraph[Int]
791 # g.add_vertices([0,1,2,3])
792 # assert g.num_vertices == 4
793 # g.add_vertices([2,3,4,5])
794 # assert g.num_vertices == 6
796 fun add_vertices
(vertices
: Collection[V
])
798 for u
in vertices
do add_vertex
(u
)
801 # Adds all arcs of `arcs` to this digraph.
803 # If arcs appear more than once, they are only added once.
806 # var g = new HashDigraph[Int]
807 # var arcs = [[0,1], [1,2], [1,2]]
809 # assert g.num_arcs == 2
811 fun add_arcs
(arcs
: Collection[Array[V
]])
813 for a
in arcs
do add_arc
(a
[0], a
[1])
816 # Add all vertices and arcs from the `other` graph.
819 # var g1 = new HashDigraph[Int]
820 # var arcs1 = [[0,1], [1,2]]
824 # var g2 = new HashDigraph[Int]
825 # var arcs2 = [[0,1], [1,4]]
829 # assert g2.vertices.has_exactly([0, 1, 2, 3, 4, 5])
830 # var arcs3 = [[0,1], [1,2], [1,4]]
831 # assert g2.arcs.has_exactly(arcs3)
833 fun add_graph
(other
: Digraph[V
])
835 for v
in other
.vertices
do
837 for w
in other
.successors
(v
) do
843 # Build a path (or circuit) that removes every edge exactly once.
845 # See `eulerian_path` for details
846 fun remove_eulerian_path
(start
: V
): Array[V
]
848 var stack
= new Array[V
]
849 var path
= new Array[V
]
852 if out_degree
(current
) == 0 then
854 if stack
.is_empty
then break
858 var n
= successors
(current
).first
859 remove_arc
(current
, n
)
866 # A directed graph represented by hash maps
867 class HashDigraph[V
: Object]
868 super MutableDigraph[V
]
872 private var incoming_vertices_map
= new HashMap[V
, Array[V
]]
873 private var outgoing_vertices_map
= new HashMap[V
, Array[V
]]
874 private var number_of_arcs
= 0
876 redef fun num_vertices
do return outgoing_vertices_map
.keys
.length
end
878 redef fun num_arcs
do return number_of_arcs
end
880 redef fun add_vertex
(u
)
882 if not has_vertex
(u
) then
883 incoming_vertices_map
[u
] = new Array[V
]
884 outgoing_vertices_map
[u
] = new Array[V
]
888 redef fun has_vertex
(u
) do return outgoing_vertices_map
.keys
.has
(u
)
890 redef fun remove_vertex
(u
)
892 if has_vertex
(u
) then
893 for v
in successors
(u
) do
896 for v
in predecessors
(u
) do
899 incoming_vertices_map
.keys
.remove
(u
)
900 outgoing_vertices_map
.keys
.remove
(u
)
904 redef fun add_arc
(u
, v
)
906 if not has_vertex
(u
) then add_vertex
(u
)
907 if not has_vertex
(v
) then add_vertex
(v
)
908 if not has_arc
(u
, v
) then
909 incoming_vertices_map
[v
].add
(u
)
910 outgoing_vertices_map
[u
].add
(v
)
915 redef fun has_arc
(u
, v
)
917 return outgoing_vertices_map
[u
].has
(v
)
920 redef fun remove_arc
(u
, v
)
922 if has_arc
(u
, v
) then
923 outgoing_vertices_map
[u
].remove
(v
)
924 incoming_vertices_map
[v
].remove
(u
)
929 redef fun predecessors
(u
): Array[V
]
931 if incoming_vertices_map
.keys
.has
(u
) then
932 return incoming_vertices_map
[u
].clone
938 redef fun successors
(u
): Array[V
]
940 if outgoing_vertices_map
.keys
.has
(u
) then
941 return outgoing_vertices_map
[u
].clone
947 redef fun vertices_iterator
: Iterator[V
] do return outgoing_vertices_map
.keys
.iterator