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};"
390 # Returns true if and only if `u` is a predecessor of `v`.
394 # var g = new HashDigraph[Int]
396 # assert g.is_predecessor(1, 3)
397 # assert not g.is_predecessor(3, 1)
399 fun is_predecessor
(u
, v
: V
): Bool do return has_arc
(u
, v
)
401 # Returns true if and only if `u` is a successor of `v`.
405 # var g = new HashDigraph[Int]
407 # assert not g.is_successor(1, 3)
408 # assert g.is_successor(3, 1)
410 fun is_successor
(u
, v
: V
): Bool do return has_arc
(v
, u
)
412 # Returns the number of arcs whose target is `u`.
416 # var g = new HashDigraph[Int]
419 # assert g.in_degree(3) == 2
420 # assert g.in_degree(1) == 0
422 fun in_degree
(u
: V
): Int do return predecessors
(u
).length
424 # Returns the number of arcs whose source is `u`.
428 # var g = new HashDigraph[Int]
432 # assert g.out_degree(3) == 0
433 # assert g.out_degree(1) == 2
435 fun out_degree
(u
: V
): Int do return successors
(u
).length
437 # ------------------ #
438 # Paths and circuits #
439 # ------------------ #
441 # Returns true if and only if `vertices` is a path of this digraph.
445 # var g = new HashDigraph[Int]
449 # assert g.has_path([1,2,3])
450 # assert not g.has_path([1,3,3])
452 fun has_path
(vertices
: SequenceRead[V
]): Bool
454 for i
in [0..vertices
.length
- 1[ do
455 if not has_arc
(vertices
[i
], vertices
[i
+ 1]) then return false
460 # Returns true if and only if `vertices` is a circuit of this digraph.
464 # var g = new HashDigraph[Int]
468 # assert g.has_circuit([1,2,3,1])
469 # assert not g.has_circuit([1,3,2,1])
471 fun has_circuit
(vertices
: SequenceRead[V
]): Bool
473 return vertices
.is_empty
or (has_path
(vertices
) and vertices
.first
== vertices
.last
)
476 # Returns a shortest path from vertex `u` to `v`.
478 # If no path exists between `u` and `v`, it returns `null`.
482 # var g = new HashDigraph[Int]
486 # assert g.a_shortest_path(1, 4).length == 4
488 # assert g.a_shortest_path(1, 4).length == 3
489 # assert g.a_shortest_path(4, 1) == null
491 fun a_shortest_path
(u
, v
: V
): nullable Sequence[V
]
493 var queue
= new List[V
].from
([u
]).as_fifo
494 var pred
= new HashMap[V
, nullable V
]
495 var visited
= new HashSet[V
]
496 var w
: nullable V
= null
498 while not queue
.is_empty
do
500 if not visited
.has
(w
) then
503 for wp
in successors
(w
) do
504 if not pred
.keys
.has
(wp
) then
514 var path
= new List[V
]
517 while pred
[w
] != null do
518 path
.unshift
(pred
[w
].as(not null))
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)`.
532 # var g = new HashDigraph[Int]
536 # assert g.distance(1, 4) == 3
538 # assert g.distance(1, 4) == 2
539 # assert g.distance(4, 1) == null
541 fun distance
(u
, v
: V
): nullable Int
543 var queue
= new List[V
].from
([u
]).as_fifo
544 var dist
= new HashMap[V
, Int]
545 var visited
= new HashSet[V
]
548 while not queue
.is_empty
do
550 if not visited
.has
(w
) then
553 for wp
in successors
(w
) do
554 if not dist
.keys
.has
(wp
) then
556 dist
[wp
] = dist
[w
] + 1
561 return dist
.get_or_null
(v
)
564 # -------------------- #
565 # Connected components #
566 # -------------------- #
568 # Returns the weak connected components of this digraph.
570 # The weak connected components of a digraph are the usual
571 # connected components of its associated undirected graph,
572 # i.e. the graph obtained by replacing each arc by an edge.
576 # var g = new HashDigraph[Int]
580 # assert g.weakly_connected_components.number_of_subsets == 2
582 fun weakly_connected_components
: DisjointSet[V
]
584 var components
= new DisjointSet[V
]
585 components
.add_all
(vertices
)
586 for arc
in arcs_iterator
do
587 components
.union
(arc
[0], arc
[1])
592 # Returns the strongly connected components of this digraph.
594 # Two vertices `u` and `v` belong to the same strongly connected
595 # component if and only if there exists a path from `u` to `v`
596 # and there exists a path from `v` to `u`.
598 # This is computed in linear time (Tarjan's algorithm).
602 # var g = new HashDigraph[Int]
610 # assert g.strongly_connected_components.number_of_subsets == 3
612 fun strongly_connected_components
: DisjointSet[V
]
614 var tarjanAlgorithm
= new TarjanAlgorithm[V
](self)
615 return tarjanAlgorithm
.strongly_connected_components
619 # Computing the strongly connected components using Tarjan's algorithm
620 private class TarjanAlgorithm[V
: Object]
621 # The graph whose strongly connected components will be computed
622 var graph
: Digraph[V
]
623 # The strongly connected components computed in Tarjan's algorithm
624 var sccs
= new DisjointSet[V
]
625 # An index used for Tarjan's algorithm
627 # A stack used for Tarjan's algorithm
628 var stack
: Queue[V
] = (new Array[V
]).as_lifo
629 # A map associating with each vertex its index
630 var vertex_to_index
= new HashMap[V
, Int]
631 # A map associating with each vertex its ancestor in Tarjan's algorithm
632 var ancestor
= new HashMap[V
, Int]
633 # True if and only if the vertex is in the stack
634 var in_stack
= new HashSet[V
]
636 # Returns the strongly connected components of a graph
637 fun strongly_connected_components
: DisjointSet[V
]
639 for u
in graph
.vertices_iterator
do sccs
.add
(u
)
640 for v
in graph
.vertices_iterator
do
646 # The recursive part of Tarjan's algorithm
649 vertex_to_index
[u
] = index
654 for v
in graph
.successors
(u
) do
655 if not vertex_to_index
.keys
.has
(v
) then
657 ancestor
[u
] = ancestor
[u
].min
(ancestor
[v
])
658 else if in_stack
.has
(v
) then
659 ancestor
[u
] = ancestor
[u
].min
(vertex_to_index
[v
])
662 if vertex_to_index
[u
] == ancestor
[u
] then
675 class ArcsIterator[V
: Object]
676 super Iterator[Array[V
]]
678 # The graph whose arcs are iterated over
679 var graph
: Digraph[V
]
682 private var sources_iterator
: Iterator[V
] is noinit
683 private var targets_iterator
: Iterator[V
] is noinit
686 sources_iterator
= graph
.vertices_iterator
687 if sources_iterator
.is_ok
then
688 targets_iterator
= graph
.successors
(sources_iterator
.item
).iterator
689 if not targets_iterator
.is_ok
then update_iterators
693 redef fun is_ok
do return sources_iterator
.is_ok
and targets_iterator
.is_ok
695 redef fun item
do return [sources_iterator
.item
, targets_iterator
.item
]
699 targets_iterator
.next
703 private fun update_iterators
705 while not targets_iterator
.is_ok
and sources_iterator
.is_ok
707 sources_iterator
.next
708 if sources_iterator
.is_ok
then
709 targets_iterator
= graph
.successors
(sources_iterator
.item
).iterator
716 abstract class MutableDigraph[V
: Object]
719 ## ---------------- ##
720 ## Abstract methods ##
721 ## ---------------- ##
723 # Adds the vertex `u` to this graph.
725 # If `u` already belongs to the graph, then nothing happens.
729 # var g = new HashDigraph[Int]
731 # assert g.has_vertex(0)
732 # assert not g.has_vertex(1)
734 # assert g.num_vertices == 2
736 fun add_vertex
(u
: V
) is abstract
738 # Removes the vertex `u` from this graph and all its incident arcs.
740 # If the vertex does not exist in the graph, then nothing happens.
744 # var g = new HashDigraph[Int]
747 # assert g.has_vertex(0)
749 # assert not g.has_vertex(0)
751 fun remove_vertex
(u
: V
) is abstract
753 # Adds the arc `(u,v)` to this graph.
755 # If there is already an arc from `u` to `v` in this graph, then
756 # nothing happens. If vertex `u` or vertex `v` do not exist in the
757 # graph, they are added.
761 # var g = new HashDigraph[Int]
764 # assert g.has_arc(0, 1)
765 # assert g.has_arc(1, 2)
766 # assert not g.has_arc(1, 0)
768 # assert g.num_arcs == 2
770 fun add_arc
(u
, v
: V
) is abstract
772 # Removes the arc `(u,v)` from this graph.
774 # If the arc does not exist in the graph, then nothing happens.
778 # var g = new HashDigraph[Int]
780 # assert g.num_arcs == 1
782 # assert g.num_arcs == 0
784 # assert g.num_arcs == 0
786 fun remove_arc
(u
, v
: V
) is abstract
788 ## -------------------- ##
789 ## Non abstract methods ##
790 ## -------------------- ##
792 # Adds all vertices of `vertices` to this digraph.
794 # If vertices appear more than once, they are only added once.
798 # var g = new HashDigraph[Int]
799 # g.add_vertices([0,1,2,3])
800 # assert g.num_vertices == 4
801 # g.add_vertices([2,3,4,5])
802 # assert g.num_vertices == 6
804 fun add_vertices
(vertices
: Collection[V
])
806 for u
in vertices
do add_vertex
(u
)
809 # Adds all arcs of `arcs` to this digraph.
811 # If arcs appear more than once, they are only added once.
815 # var g = new HashDigraph[Int]
816 # var arcs = [[0,1], [1,2], [1,2]]
818 # assert g.num_arcs == 2
820 fun add_arcs
(arcs
: Collection[Array[V
]])
822 for a
in arcs
do add_arc
(a
[0], a
[1])
825 # A directed graph represented by hash maps
826 class HashDigraph[V
: Object]
827 super MutableDigraph[V
]
831 private var incoming_vertices_map
= new HashMap[V
, Array[V
]]
832 private var outgoing_vertices_map
= new HashMap[V
, Array[V
]]
833 private var number_of_arcs
= 0
835 redef fun num_vertices
do return outgoing_vertices_map
.keys
.length
end
837 redef fun num_arcs
do return number_of_arcs
end
839 redef fun add_vertex
(u
)
841 if not has_vertex
(u
) then
842 incoming_vertices_map
[u
] = new Array[V
]
843 outgoing_vertices_map
[u
] = new Array[V
]
847 redef fun has_vertex
(u
) do return outgoing_vertices_map
.keys
.has
(u
)
849 redef fun remove_vertex
(u
)
851 if has_vertex
(u
) then
852 for v
in successors
(u
) do
855 for v
in predecessors
(u
) do
858 incoming_vertices_map
.keys
.remove
(u
)
859 outgoing_vertices_map
.keys
.remove
(u
)
863 redef fun add_arc
(u
, v
)
865 if not has_vertex
(u
) then add_vertex
(u
)
866 if not has_vertex
(v
) then add_vertex
(v
)
867 if not has_arc
(u
, v
) then
868 incoming_vertices_map
[v
].add
(u
)
869 outgoing_vertices_map
[u
].add
(v
)
874 redef fun has_arc
(u
, v
)
876 return outgoing_vertices_map
[u
].has
(v
)
879 redef fun remove_arc
(u
, v
)
881 if has_arc
(u
, v
) then
882 outgoing_vertices_map
[u
].remove
(v
)
883 incoming_vertices_map
[v
].remove
(u
)
888 redef fun predecessors
(u
): Array[V
]
890 if incoming_vertices_map
.keys
.has
(u
) then
891 return incoming_vertices_map
[u
].clone
897 redef fun successors
(u
): Array[V
]
899 if outgoing_vertices_map
.keys
.has
(u
) then
900 return outgoing_vertices_map
[u
].clone
906 redef fun vertices_iterator
: Iterator[V
] do return outgoing_vertices_map
.keys
.iterator