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 # Writing the vertices
373 for u
in vertices_iterator
do
374 s
+= " \"{u.to_s.escape_to_dot}\
" "
375 s
+= "[label=\"{u.to_s.escape_to_dot}\
"];\n"
379 s
+= " {arc[0].to_s.escape_to_dot} "
380 s
+= "-> {arc[1].to_s.escape_to_dot};"
386 # Open Graphviz with `self.to_dot`.
388 # Mainly used for debugging.
390 var f
= new ProcessWriter("dot", "-Txlib")
399 # Returns true if and only if `u` is a predecessor of `v`.
403 # var g = new HashDigraph[Int]
405 # assert g.is_predecessor(1, 3)
406 # assert not g.is_predecessor(3, 1)
408 fun is_predecessor
(u
, v
: V
): Bool do return has_arc
(u
, v
)
410 # Returns true if and only if `u` is a successor of `v`.
414 # var g = new HashDigraph[Int]
416 # assert not g.is_successor(1, 3)
417 # assert g.is_successor(3, 1)
419 fun is_successor
(u
, v
: V
): Bool do return has_arc
(v
, u
)
421 # Returns the number of arcs whose target is `u`.
425 # var g = new HashDigraph[Int]
428 # assert g.in_degree(3) == 2
429 # assert g.in_degree(1) == 0
431 fun in_degree
(u
: V
): Int do return predecessors
(u
).length
433 # Returns the number of arcs whose source is `u`.
437 # var g = new HashDigraph[Int]
441 # assert g.out_degree(3) == 0
442 # assert g.out_degree(1) == 2
444 fun out_degree
(u
: V
): Int do return successors
(u
).length
446 # ------------------ #
447 # Paths and circuits #
448 # ------------------ #
450 # Returns true if and only if `vertices` is a path of this digraph.
454 # var g = new HashDigraph[Int]
458 # assert g.has_path([1,2,3])
459 # assert not g.has_path([1,3,3])
461 fun has_path
(vertices
: SequenceRead[V
]): Bool
463 for i
in [0..vertices
.length
- 1[ do
464 if not has_arc
(vertices
[i
], vertices
[i
+ 1]) then return false
469 # Returns true if and only if `vertices` is a circuit of this digraph.
473 # var g = new HashDigraph[Int]
477 # assert g.has_circuit([1,2,3,1])
478 # assert not g.has_circuit([1,3,2,1])
480 fun has_circuit
(vertices
: SequenceRead[V
]): Bool
482 return vertices
.is_empty
or (has_path
(vertices
) and vertices
.first
== vertices
.last
)
485 # Returns a shortest path from vertex `u` to `v`.
487 # If no path exists between `u` and `v`, it returns `null`.
491 # var g = new HashDigraph[Int]
495 # assert g.a_shortest_path(1, 4).length == 4
497 # assert g.a_shortest_path(1, 4).length == 3
498 # assert g.a_shortest_path(4, 1) == null
500 fun a_shortest_path
(u
, v
: V
): nullable Sequence[V
]
502 var queue
= new List[V
].from
([u
]).as_fifo
503 var pred
= new HashMap[V
, nullable V
]
504 var visited
= new HashSet[V
]
505 var w
: nullable V
= null
507 while not queue
.is_empty
do
509 if not visited
.has
(w
) then
512 for wp
in successors
(w
) do
513 if not pred
.keys
.has
(wp
) then
523 var path
= new List[V
]
526 while pred
[w
] != null do
527 path
.unshift
(pred
[w
].as(not null))
534 # Returns the distance between `u` and `v`
536 # If no path exists between `u` and `v`, it returns null. It is not
537 # symmetric, i.e. we may have `dist(u, v) != dist(v, u)`.
541 # var g = new HashDigraph[Int]
545 # assert g.distance(1, 4) == 3
547 # assert g.distance(1, 4) == 2
548 # assert g.distance(4, 1) == null
550 fun distance
(u
, v
: V
): nullable Int
552 var queue
= new List[V
].from
([u
]).as_fifo
553 var dist
= new HashMap[V
, Int]
554 var visited
= new HashSet[V
]
557 while not queue
.is_empty
do
559 if not visited
.has
(w
) then
562 for wp
in successors
(w
) do
563 if not dist
.keys
.has
(wp
) then
565 dist
[wp
] = dist
[w
] + 1
570 return dist
.get_or_null
(v
)
573 # -------------------- #
574 # Connected components #
575 # -------------------- #
577 # Returns the weak connected components of this digraph.
579 # The weak connected components of a digraph are the usual
580 # connected components of its associated undirected graph,
581 # i.e. the graph obtained by replacing each arc by an edge.
585 # var g = new HashDigraph[Int]
589 # assert g.weakly_connected_components.number_of_subsets == 2
591 fun weakly_connected_components
: DisjointSet[V
]
593 var components
= new DisjointSet[V
]
594 components
.add_all
(vertices
)
595 for arc
in arcs_iterator
do
596 components
.union
(arc
[0], arc
[1])
601 # Returns the strongly connected components of this digraph.
603 # Two vertices `u` and `v` belong to the same strongly connected
604 # component if and only if there exists a path from `u` to `v`
605 # and there exists a path from `v` to `u`.
607 # This is computed in linear time (Tarjan's algorithm).
611 # var g = new HashDigraph[Int]
619 # assert g.strongly_connected_components.number_of_subsets == 3
621 fun strongly_connected_components
: DisjointSet[V
]
623 var tarjanAlgorithm
= new TarjanAlgorithm[V
](self)
624 return tarjanAlgorithm
.strongly_connected_components
628 # Computing the strongly connected components using Tarjan's algorithm
629 private class TarjanAlgorithm[V
: Object]
630 # The graph whose strongly connected components will be computed
631 var graph
: Digraph[V
]
632 # The strongly connected components computed in Tarjan's algorithm
633 var sccs
= new DisjointSet[V
]
634 # An index used for Tarjan's algorithm
636 # A stack used for Tarjan's algorithm
637 var stack
: Queue[V
] = (new Array[V
]).as_lifo
638 # A map associating with each vertex its index
639 var vertex_to_index
= new HashMap[V
, Int]
640 # A map associating with each vertex its ancestor in Tarjan's algorithm
641 var ancestor
= new HashMap[V
, Int]
642 # True if and only if the vertex is in the stack
643 var in_stack
= new HashSet[V
]
645 # Returns the strongly connected components of a graph
646 fun strongly_connected_components
: DisjointSet[V
]
648 for u
in graph
.vertices_iterator
do sccs
.add
(u
)
649 for v
in graph
.vertices_iterator
do
655 # The recursive part of Tarjan's algorithm
658 vertex_to_index
[u
] = index
663 for v
in graph
.successors
(u
) do
664 if not vertex_to_index
.keys
.has
(v
) then
666 ancestor
[u
] = ancestor
[u
].min
(ancestor
[v
])
667 else if in_stack
.has
(v
) then
668 ancestor
[u
] = ancestor
[u
].min
(vertex_to_index
[v
])
671 if vertex_to_index
[u
] == ancestor
[u
] then
684 class ArcsIterator[V
: Object]
685 super Iterator[Array[V
]]
687 # The graph whose arcs are iterated over
688 var graph
: Digraph[V
]
691 private var sources_iterator
: Iterator[V
] is noinit
692 private var targets_iterator
: Iterator[V
] is noinit
695 sources_iterator
= graph
.vertices_iterator
696 if sources_iterator
.is_ok
then
697 targets_iterator
= graph
.successors
(sources_iterator
.item
).iterator
698 if not targets_iterator
.is_ok
then update_iterators
702 redef fun is_ok
do return sources_iterator
.is_ok
and targets_iterator
.is_ok
704 redef fun item
do return [sources_iterator
.item
, targets_iterator
.item
]
708 targets_iterator
.next
712 private fun update_iterators
714 while not targets_iterator
.is_ok
and sources_iterator
.is_ok
716 sources_iterator
.next
717 if sources_iterator
.is_ok
then
718 targets_iterator
= graph
.successors
(sources_iterator
.item
).iterator
725 abstract class MutableDigraph[V
: Object]
728 ## ---------------- ##
729 ## Abstract methods ##
730 ## ---------------- ##
732 # Adds the vertex `u` to this graph.
734 # If `u` already belongs to the graph, then nothing happens.
738 # var g = new HashDigraph[Int]
740 # assert g.has_vertex(0)
741 # assert not g.has_vertex(1)
743 # assert g.num_vertices == 2
745 fun add_vertex
(u
: V
) is abstract
747 # Removes the vertex `u` from this graph and all its incident arcs.
749 # If the vertex does not exist in the graph, then nothing happens.
753 # var g = new HashDigraph[Int]
756 # assert g.has_vertex(0)
758 # assert not g.has_vertex(0)
760 fun remove_vertex
(u
: V
) is abstract
762 # Adds the arc `(u,v)` to this graph.
764 # If there is already an arc from `u` to `v` in this graph, then
765 # nothing happens. If vertex `u` or vertex `v` do not exist in the
766 # graph, they are added.
770 # var g = new HashDigraph[Int]
773 # assert g.has_arc(0, 1)
774 # assert g.has_arc(1, 2)
775 # assert not g.has_arc(1, 0)
777 # assert g.num_arcs == 2
779 fun add_arc
(u
, v
: V
) is abstract
781 # Removes the arc `(u,v)` from this graph.
783 # If the arc does not exist in the graph, then nothing happens.
787 # var g = new HashDigraph[Int]
789 # assert g.num_arcs == 1
791 # assert g.num_arcs == 0
793 # assert g.num_arcs == 0
795 fun remove_arc
(u
, v
: V
) is abstract
797 ## -------------------- ##
798 ## Non abstract methods ##
799 ## -------------------- ##
801 # Adds all vertices of `vertices` to this digraph.
803 # If vertices appear more than once, they are only added once.
807 # var g = new HashDigraph[Int]
808 # g.add_vertices([0,1,2,3])
809 # assert g.num_vertices == 4
810 # g.add_vertices([2,3,4,5])
811 # assert g.num_vertices == 6
813 fun add_vertices
(vertices
: Collection[V
])
815 for u
in vertices
do add_vertex
(u
)
818 # Adds all arcs of `arcs` to this digraph.
820 # If arcs appear more than once, they are only added once.
824 # var g = new HashDigraph[Int]
825 # var arcs = [[0,1], [1,2], [1,2]]
827 # assert g.num_arcs == 2
829 fun add_arcs
(arcs
: Collection[Array[V
]])
831 for a
in arcs
do add_arc
(a
[0], a
[1])
834 # A directed graph represented by hash maps
835 class HashDigraph[V
: Object]
836 super MutableDigraph[V
]
840 private var incoming_vertices_map
= new HashMap[V
, Array[V
]]
841 private var outgoing_vertices_map
= new HashMap[V
, Array[V
]]
842 private var number_of_arcs
= 0
844 redef fun num_vertices
do return outgoing_vertices_map
.keys
.length
end
846 redef fun num_arcs
do return number_of_arcs
end
848 redef fun add_vertex
(u
)
850 if not has_vertex
(u
) then
851 incoming_vertices_map
[u
] = new Array[V
]
852 outgoing_vertices_map
[u
] = new Array[V
]
856 redef fun has_vertex
(u
) do return outgoing_vertices_map
.keys
.has
(u
)
858 redef fun remove_vertex
(u
)
860 if has_vertex
(u
) then
861 for v
in successors
(u
) do
864 for v
in predecessors
(u
) do
867 incoming_vertices_map
.keys
.remove
(u
)
868 outgoing_vertices_map
.keys
.remove
(u
)
872 redef fun add_arc
(u
, v
)
874 if not has_vertex
(u
) then add_vertex
(u
)
875 if not has_vertex
(v
) then add_vertex
(v
)
876 if not has_arc
(u
, v
) then
877 incoming_vertices_map
[v
].add
(u
)
878 outgoing_vertices_map
[u
].add
(v
)
883 redef fun has_arc
(u
, v
)
885 return outgoing_vertices_map
[u
].has
(v
)
888 redef fun remove_arc
(u
, v
)
890 if has_arc
(u
, v
) then
891 outgoing_vertices_map
[u
].remove
(v
)
892 incoming_vertices_map
[v
].remove
(u
)
897 redef fun predecessors
(u
): Array[V
]
899 if incoming_vertices_map
.keys
.has
(u
) then
900 return incoming_vertices_map
[u
].clone
906 redef fun successors
(u
): Array[V
]
908 if outgoing_vertices_map
.keys
.has
(u
) then
909 return outgoing_vertices_map
[u
].clone
915 redef fun vertices_iterator
: Iterator[V
] do return outgoing_vertices_map
.keys
.iterator