Implementation of directed graphs, also called digraphs.
This module provides a simple interface together with a concrete implementation of directed graphs (or digraphs).
The upper level interface is
Digraph and contains all methods for digraphs
that do not depend on the underlying data structure. More precisely, if basic
operations such as
num_vertices, etc. are
implemented, then high level operations (such as computing the connected
components or a shortest path between two vertices) can be easily derived.
Also, all methods found in
Digraph do no modify the graph. For mutable
methods, one needs to check the
MutableDigraph child class. Vertices can be
Object, but there is no information stored in the arcs, which are
simple arrays of the form
u is the source of the arc and
is the target.
There is currently only one concrete implementation named
makes use of the HashMap class for storing the predecessors and successors.
It is therefore simple to provide another implementation: One only has to
create a concrete specialization of either
To create an (empty) new graph whose keys are integers, one simply type
import digraph var g = 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"
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")
HashDigraphs 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"
If one has installed Graphviz, 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
There exist other methods available for digraphs and many other will be implemented in the future. For more details, one should look at the methods directly. For instance, the strongly connected components of a digraph are returned as a 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 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) if path != null then print path else print "No path" # Prints [2,3,4] path = g.a_shortest_path(4, 2) if path != null then print path else print "No path"
Extending the library
There are at least two ways of providing new methods on digraphs. If the method is standard and could be useful to other users, you should consider including your implementation directly in this library.
Otherwise, for personal use, you should simply define a new class inheriting
HashDigraph and add the new services.