graphs

package graphs

Concerns

  • graphs
    • digraph: Implementation of directed graphs, also called digraphs.
    • pagerank: Add PageRank computation for vertices in Digraph.

graphs::digraph

module digraph

Implementation of directed graphs, also called digraphs.

Overview

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 predecessors, successors, 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 any Object, but there is no information stored in the arcs, which are simple arrays of the form [u,v], where u is the source of the arc and v is the target.

There is currently only one concrete implementation named HashDigraph that 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 Digraph or MutableDigraph.

Basic methods

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

A graph drawing produced by Graphviz

Other methods

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 from HashDigraph and add the new services.