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
47 # var g = new HashDigraph[Int]
50 # Then we can add vertices and arcs. Note that if an arc is added whose source
51 # and target are not already in the digraph, the vertices are added beforehand.
54 # var g = new HashDigraph[Int]
59 # assert g.to_s == "Digraph of 3 vertices and 2 arcs"
62 # One might also create digraphs with strings in vertices, for instance to
63 # represent some directed relation. However, it is currently not possible to
64 # store values in the arcs.
67 # var g = new HashDigraph[String]
69 # g.add_vertex("Bill")
70 # g.add_vertex("Chris")
71 # g.add_vertex("Diane")
72 # g.add_arc("Amy", "Bill") # Amy likes Bill
73 # g.add_arc("Bill", "Amy") # Bill likes Amy
74 # g.add_arc("Chris", "Diane") # and so on
75 # g.add_arc("Diane", "Amy") # and so on
78 # `HashDigraph`s are mutable, i.e. one might remove arcs and/or vertices:
81 # var g = new HashDigraph[Int]
89 # assert g.to_s == "Digraph of 4 vertices and 2 arcs"
92 # If one has installed [Graphviz](http://graphviz.org), it is easy to produce a
93 # *dot* file which Graphviz process into a picture:
96 # var g = new HashDigraph[Int]
97 # g.add_arcs([[0,1],[0,2],[1,2],[2,3],[2,4]])
99 # # Then call "dot -Tpng -o graph.png"
102 # ![A graph drawing produced by Graphviz](https://github.com/nitlang/nit/blob/master/lib/graph.png)
107 # There exist other methods available for digraphs and many other will be
108 # implemented in the future. For more details, one should look at the methods
109 # directly. For instance, the [strongly connected components]
110 # (https://en.wikipedia.org/wiki/Strongly_connected_component) of a digraph are
111 # returned as a [disjoint set data structure]
112 # (https://en.wikipedia.org/wiki/Disjoint-set_data_structure) (i.e. a set of
116 # var g = new HashDigraph[Int]
117 # g.add_arcs([[1,2],[2,1],[2,3],[3,4],[4,5],[5,3]])
118 # for component in g.strongly_connected_components.to_partitions
122 # # Prints [1,2] and [3,4,5]
125 # It is also possible to compute a shortest (directed) path between two
129 # var g = new HashDigraph[Int]
130 # g.add_arcs([[1,2],[2,1],[2,3],[3,4],[4,5],[5,3]])
131 # var path = g.a_shortest_path(2, 4)
132 # if path != null then print path else print "No path"
134 # path = g.a_shortest_path(4, 2)
135 # if path != null then print path else print "No path"
139 # Extending the library
140 # =====================
142 # There are at least two ways of providing new methods on digraphs. If the
143 # method is standard and could be useful to other users, you should consider
144 # including your implementation directly in this library.
146 # Otherwise, for personal use, you should simply define a new class inheriting
147 # from `HashDigraph` and add the new services.
150 # Interface for digraphs
151 interface Digraph[V
: Object]
153 ## ---------------- ##
154 ## Abstract methods ##
155 ## ---------------- ##
157 # The number of vertices in this graph.
161 # var g = new HashDigraph[Int]
164 # assert g.num_vertices == 2
166 # assert g.num_vertices == 2
168 fun num_vertices
: Int is abstract
170 # The number of arcs in this graph.
174 # var g = new HashDigraph[Int]
176 # assert g.num_arcs == 1
178 # assert g.num_arcs == 1
180 # assert g.num_arcs == 2
182 fun num_arcs
: Int is abstract
184 # Returns true if and only if `u` exists in this graph.
188 # var g = new HashDigraph[Int]
190 # assert g.has_vertex(1)
191 # assert not g.has_vertex(0)
193 # assert g.has_vertex(1)
194 # assert not g.has_vertex(0)
196 fun has_vertex
(u
: V
): Bool is abstract
198 # Returns true if and only if `(u,v)` is an arc in this graph.
202 # var g = new HashDigraph[Int]
205 # assert g.has_arc(0, 1)
206 # assert g.has_arc(1, 2)
207 # assert not g.has_arc(0, 2)
209 fun has_arc
(u
, v
: V
): Bool is abstract
211 # Returns the predecessors of `u`.
213 # If `u` does not exist, then it returns null.
217 # var g = new HashDigraph[Int]
221 # assert g.predecessors(2).has(0)
222 # assert g.predecessors(2).has(1)
223 # assert not g.predecessors(2).has(2)
225 fun predecessors
(u
: V
): Collection[V
] is abstract
227 # Returns the successors of `u`.
229 # If `u` does not exist, then an empty collection is returned.
233 # var g = new HashDigraph[Int]
237 # assert not g.successors(0).has(0)
238 # assert g.successors(0).has(1)
239 # assert g.successors(0).has(2)
241 fun successors
(u
: V
): Collection[V
] is abstract
243 # Returns an iterator over the vertices of this graph.
247 # var g = new HashDigraph[Int]
251 # var vs = new HashSet[Int]
252 # for v in g.vertices_iterator do vs.add(v)
253 # assert vs == new HashSet[Int].from([0,1,2])
255 fun vertices_iterator
: Iterator[V
] is abstract
257 ## -------------------- ##
258 ## Non abstract methods ##
259 ## -------------------- ##
265 # Returns true if and only if this graph is empty.
267 # An empty graph is a graph without vertex and arc.
271 # assert (new HashDigraph[Int]).is_empty
273 fun is_empty
: Bool do return num_vertices
== 0 and num_arcs
== 0
275 # Returns an array containing the vertices of this graph.
279 # var g = new HashDigraph[Int]
280 # g.add_vertices([0,2,4,5])
281 # assert g.vertices.length == 4
283 fun vertices
: Array[V
] do return [for u
in vertices_iterator
do u
]
285 # Returns an iterator over the arcs of this graph
289 # var g = new HashDigraph[Int]
293 # for arc in g.arcs_iterator do
294 # assert g.has_arc(arc[0], arc[1])
297 fun arcs_iterator
: Iterator[Array[V
]] do return new ArcsIterator[V
](self)
299 # Returns the arcs of this graph.
303 # var g = new HashDigraph[Int]
306 # assert g.arcs.length == 2
308 fun arcs
: Array[Array[V
]] do return [for arc
in arcs_iterator
do arc
]
310 # Returns the incoming arcs of vertex `u`.
312 # If `u` is not in this graph, an empty array is returned.
316 # var g = new HashDigraph[Int]
319 # for arc in g.incoming_arcs(3) do
320 # assert g.is_predecessor(arc[0], arc[1])
323 fun incoming_arcs
(u
: V
): Collection[Array[V
]]
325 if has_vertex
(u
) then
326 return [for v
in predecessors
(u
) do [v
, u
]]
328 return new Array[Array[V
]]
332 # Returns the outgoing arcs of vertex `u`.
334 # If `u` is not in this graph, an empty array is returned.
338 # var g = new HashDigraph[Int]
342 # for arc in g.outgoing_arcs(1) do
343 # assert g.is_successor(arc[1], arc[0])
346 fun outgoing_arcs
(u
: V
): Collection[Array[V
]]
348 if has_vertex
(u
) then
349 return [for v
in successors
(u
) do [u
, v
]]
351 return new Array[Array[V
]]
355 ## ---------------------- ##
356 ## String representations ##
357 ## ---------------------- ##
361 var vertex_word
= "vertices"
362 var arc_word
= "arcs"
363 if num_vertices
<= 1 then vertex_word
= "vertex"
364 if num_arcs
<= 1 then arc_word
= "arc"
365 return "Digraph of {num_vertices} {vertex_word} and {num_arcs} {arc_word}"
368 # Returns a GraphViz string representing this digraph.
371 var s
= "digraph \{\n"
372 var id_set
= new HashMap[V
, Int]
373 # Writing the vertices
374 for u
in vertices_iterator
, i
in [0 .. vertices
.length
[ do
377 s
+= "[label=\"{u.to_s.escape_to_dot}\
"];\n"
381 s
+= " {id_set[arc[0]]} "
382 s
+= "-> {id_set[arc[1]]};"
388 # Open Graphviz with `self.to_dot`.
390 # Mainly used for debugging.
392 var f
= new ProcessWriter("dot", "-Txlib")
401 # Returns true if and only if `u` is a predecessor of `v`.
405 # var g = new HashDigraph[Int]
407 # assert g.is_predecessor(1, 3)
408 # assert not g.is_predecessor(3, 1)
410 fun is_predecessor
(u
, v
: V
): Bool do return has_arc
(u
, v
)
412 # Returns true if and only if `u` is a successor of `v`.
416 # var g = new HashDigraph[Int]
418 # assert not g.is_successor(1, 3)
419 # assert g.is_successor(3, 1)
421 fun is_successor
(u
, v
: V
): Bool do return has_arc
(v
, u
)
423 # Returns the number of arcs whose target is `u`.
427 # var g = new HashDigraph[Int]
430 # assert g.in_degree(3) == 2
431 # assert g.in_degree(1) == 0
433 fun in_degree
(u
: V
): Int do return predecessors
(u
).length
435 # Returns the number of arcs whose source is `u`.
439 # var g = new HashDigraph[Int]
443 # assert g.out_degree(3) == 0
444 # assert g.out_degree(1) == 2
446 fun out_degree
(u
: V
): Int do return successors
(u
).length
448 # ------------------ #
449 # Paths and circuits #
450 # ------------------ #
452 # Returns true if and only if `vertices` is a path of this digraph.
456 # var g = new HashDigraph[Int]
460 # assert g.has_path([1,2,3])
461 # assert not g.has_path([1,3,3])
463 fun has_path
(vertices
: SequenceRead[V
]): Bool
465 for i
in [0..vertices
.length
- 1[ do
466 if not has_arc
(vertices
[i
], vertices
[i
+ 1]) then return false
471 # Returns true if and only if `vertices` is a circuit of this digraph.
475 # var g = new HashDigraph[Int]
479 # assert g.has_circuit([1,2,3,1])
480 # assert not g.has_circuit([1,3,2,1])
482 fun has_circuit
(vertices
: SequenceRead[V
]): Bool
484 return vertices
.is_empty
or (has_path
(vertices
) and vertices
.first
== vertices
.last
)
487 # Returns a shortest path from vertex `u` to `v`.
489 # If no path exists between `u` and `v`, it returns `null`.
493 # var g = new HashDigraph[Int]
497 # assert g.a_shortest_path(1, 4).length == 4
499 # assert g.a_shortest_path(1, 4).length == 3
500 # assert g.a_shortest_path(4, 1) == null
502 fun a_shortest_path
(u
, v
: V
): nullable Sequence[V
]
504 var queue
= new List[V
].from
([u
]).as_fifo
505 var pred
= new HashMap[V
, nullable V
]
506 var visited
= new HashSet[V
]
507 var w
: nullable V
= null
509 while not queue
.is_empty
do
511 if not visited
.has
(w
) then
514 for wp
in successors
(w
) do
515 if not pred
.keys
.has
(wp
) then
525 var path
= new List[V
]
528 while pred
[w
] != null do
529 path
.unshift
(pred
[w
].as(not null))
536 # Returns the distance between `u` and `v`
538 # If no path exists between `u` and `v`, it returns null. It is not
539 # symmetric, i.e. we may have `dist(u, v) != dist(v, u)`.
543 # var g = new HashDigraph[Int]
547 # assert g.distance(1, 4) == 3
549 # assert g.distance(1, 4) == 2
550 # assert g.distance(4, 1) == null
552 fun distance
(u
, v
: V
): nullable Int
554 var queue
= new List[V
].from
([u
]).as_fifo
555 var dist
= new HashMap[V
, Int]
556 var visited
= new HashSet[V
]
559 while not queue
.is_empty
do
561 if not visited
.has
(w
) then
564 for wp
in successors
(w
) do
565 if not dist
.keys
.has
(wp
) then
567 dist
[wp
] = dist
[w
] + 1
572 return dist
.get_or_null
(v
)
575 # -------------------- #
576 # Connected components #
577 # -------------------- #
579 # Returns the weak connected components of this digraph.
581 # The weak connected components of a digraph are the usual
582 # connected components of its associated undirected graph,
583 # i.e. the graph obtained by replacing each arc by an edge.
587 # var g = new HashDigraph[Int]
591 # assert g.weakly_connected_components.number_of_subsets == 2
593 fun weakly_connected_components
: DisjointSet[V
]
595 var components
= new DisjointSet[V
]
596 components
.add_all
(vertices
)
597 for arc
in arcs_iterator
do
598 components
.union
(arc
[0], arc
[1])
603 # Returns the strongly connected components of this digraph.
605 # Two vertices `u` and `v` belong to the same strongly connected
606 # component if and only if there exists a path from `u` to `v`
607 # and there exists a path from `v` to `u`.
609 # This is computed in linear time (Tarjan's algorithm).
613 # var g = new HashDigraph[Int]
621 # assert g.strongly_connected_components.number_of_subsets == 3
623 fun strongly_connected_components
: DisjointSet[V
]
625 var tarjanAlgorithm
= new TarjanAlgorithm[V
](self)
626 return tarjanAlgorithm
.strongly_connected_components
630 # Computing the strongly connected components using Tarjan's algorithm
631 private class TarjanAlgorithm[V
: Object]
632 # The graph whose strongly connected components will be computed
633 var graph
: Digraph[V
]
634 # The strongly connected components computed in Tarjan's algorithm
635 var sccs
= new DisjointSet[V
]
636 # An index used for Tarjan's algorithm
638 # A stack used for Tarjan's algorithm
639 var stack
: Queue[V
] = (new Array[V
]).as_lifo
640 # A map associating with each vertex its index
641 var vertex_to_index
= new HashMap[V
, Int]
642 # A map associating with each vertex its ancestor in Tarjan's algorithm
643 var ancestor
= new HashMap[V
, Int]
644 # True if and only if the vertex is in the stack
645 var in_stack
= new HashSet[V
]
647 # Returns the strongly connected components of a graph
648 fun strongly_connected_components
: DisjointSet[V
]
650 for u
in graph
.vertices_iterator
do sccs
.add
(u
)
651 for v
in graph
.vertices_iterator
do
657 # The recursive part of Tarjan's algorithm
660 vertex_to_index
[u
] = index
665 for v
in graph
.successors
(u
) do
666 if not vertex_to_index
.keys
.has
(v
) then
668 ancestor
[u
] = ancestor
[u
].min
(ancestor
[v
])
669 else if in_stack
.has
(v
) then
670 ancestor
[u
] = ancestor
[u
].min
(vertex_to_index
[v
])
673 if vertex_to_index
[u
] == ancestor
[u
] then
686 class ArcsIterator[V
: Object]
687 super Iterator[Array[V
]]
689 # The graph whose arcs are iterated over
690 var graph
: Digraph[V
]
693 private var sources_iterator
: Iterator[V
] is noinit
694 private var targets_iterator
: Iterator[V
] is noinit
697 sources_iterator
= graph
.vertices_iterator
698 if sources_iterator
.is_ok
then
699 targets_iterator
= graph
.successors
(sources_iterator
.item
).iterator
700 if not targets_iterator
.is_ok
then update_iterators
704 redef fun is_ok
do return sources_iterator
.is_ok
and targets_iterator
.is_ok
706 redef fun item
do return [sources_iterator
.item
, targets_iterator
.item
]
710 targets_iterator
.next
714 private fun update_iterators
716 while not targets_iterator
.is_ok
and sources_iterator
.is_ok
718 sources_iterator
.next
719 if sources_iterator
.is_ok
then
720 targets_iterator
= graph
.successors
(sources_iterator
.item
).iterator
727 abstract class MutableDigraph[V
: Object]
730 ## ---------------- ##
731 ## Abstract methods ##
732 ## ---------------- ##
734 # Adds the vertex `u` to this graph.
736 # If `u` already belongs to the graph, then nothing happens.
740 # var g = new HashDigraph[Int]
742 # assert g.has_vertex(0)
743 # assert not g.has_vertex(1)
745 # assert g.num_vertices == 2
747 fun add_vertex
(u
: V
) is abstract
749 # Removes the vertex `u` from this graph and all its incident arcs.
751 # If the vertex does not exist in the graph, then nothing happens.
755 # var g = new HashDigraph[Int]
758 # assert g.has_vertex(0)
760 # assert not g.has_vertex(0)
762 fun remove_vertex
(u
: V
) is abstract
764 # Adds the arc `(u,v)` to this graph.
766 # If there is already an arc from `u` to `v` in this graph, then
767 # nothing happens. If vertex `u` or vertex `v` do not exist in the
768 # graph, they are added.
772 # var g = new HashDigraph[Int]
775 # assert g.has_arc(0, 1)
776 # assert g.has_arc(1, 2)
777 # assert not g.has_arc(1, 0)
779 # assert g.num_arcs == 2
781 fun add_arc
(u
, v
: V
) is abstract
783 # Removes the arc `(u,v)` from this graph.
785 # If the arc does not exist in the graph, then nothing happens.
789 # var g = new HashDigraph[Int]
791 # assert g.num_arcs == 1
793 # assert g.num_arcs == 0
795 # assert g.num_arcs == 0
797 fun remove_arc
(u
, v
: V
) is abstract
799 ## -------------------- ##
800 ## Non abstract methods ##
801 ## -------------------- ##
803 # Adds all vertices of `vertices` to this digraph.
805 # If vertices appear more than once, they are only added once.
809 # var g = new HashDigraph[Int]
810 # g.add_vertices([0,1,2,3])
811 # assert g.num_vertices == 4
812 # g.add_vertices([2,3,4,5])
813 # assert g.num_vertices == 6
815 fun add_vertices
(vertices
: Collection[V
])
817 for u
in vertices
do add_vertex
(u
)
820 # Adds all arcs of `arcs` to this digraph.
822 # If arcs appear more than once, they are only added once.
826 # var g = new HashDigraph[Int]
827 # var arcs = [[0,1], [1,2], [1,2]]
829 # assert g.num_arcs == 2
831 fun add_arcs
(arcs
: Collection[Array[V
]])
833 for a
in arcs
do add_arc
(a
[0], a
[1])
836 # A directed graph represented by hash maps
837 class HashDigraph[V
: Object]
838 super MutableDigraph[V
]
842 private var incoming_vertices_map
= new HashMap[V
, Array[V
]]
843 private var outgoing_vertices_map
= new HashMap[V
, Array[V
]]
844 private var number_of_arcs
= 0
846 redef fun num_vertices
do return outgoing_vertices_map
.keys
.length
end
848 redef fun num_arcs
do return number_of_arcs
end
850 redef fun add_vertex
(u
)
852 if not has_vertex
(u
) then
853 incoming_vertices_map
[u
] = new Array[V
]
854 outgoing_vertices_map
[u
] = new Array[V
]
858 redef fun has_vertex
(u
) do return outgoing_vertices_map
.keys
.has
(u
)
860 redef fun remove_vertex
(u
)
862 if has_vertex
(u
) then
863 for v
in successors
(u
) do
866 for v
in predecessors
(u
) do
869 incoming_vertices_map
.keys
.remove
(u
)
870 outgoing_vertices_map
.keys
.remove
(u
)
874 redef fun add_arc
(u
, v
)
876 if not has_vertex
(u
) then add_vertex
(u
)
877 if not has_vertex
(v
) then add_vertex
(v
)
878 if not has_arc
(u
, v
) then
879 incoming_vertices_map
[v
].add
(u
)
880 outgoing_vertices_map
[u
].add
(v
)
885 redef fun has_arc
(u
, v
)
887 return outgoing_vertices_map
[u
].has
(v
)
890 redef fun remove_arc
(u
, v
)
892 if has_arc
(u
, v
) then
893 outgoing_vertices_map
[u
].remove
(v
)
894 incoming_vertices_map
[v
].remove
(u
)
899 redef fun predecessors
(u
): Array[V
]
901 if incoming_vertices_map
.keys
.has
(u
) then
902 return incoming_vertices_map
[u
].clone
908 redef fun successors
(u
): Array[V
]
910 if outgoing_vertices_map
.keys
.has
(u
) then
911 return outgoing_vertices_map
[u
].clone
917 redef fun vertices_iterator
: Iterator[V
] do return outgoing_vertices_map
.keys
.iterator