#
# 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)
# 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)
nitlanguage / nit.git / commitdiff