# graphs

## Concerns

### graphs::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")
```

`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"
```

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
```

# 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.

###### Introduces

- Digraph: Interface for digraphs
- ArcsIterator: Arcs iterator
- MutableDigraph: Mutable digraph
- HashDigraph: A directed graph represented by hash maps