# Digraph library

**Digraph** is a very simple, C++ 11 template-based, directed graph library. It is not designed to be general, but to suit the needs of the (next) Faust compiler.

It is made of two files:

`digraph.hh`

the digraph class`digraphop.hh`

some operations on digraphs

## Building a digraph

A **digraph** is a directed graph. It is composed of a set of nodes `{n_1,n_2,...}`

and a set of connections (i.e. arrows) between these nodes `{(n_i -d-> n_j),...}`

.

For a connection `(n_i -d-> n_j)`

, the node `n_i`

is the source of the connection, the node `n_j`

is the destination of the connections, and the integer `d`

is the value of the connection. When the value is not specified its is by default 0.

The API to create a graph is very simple. You start by creating an empty graph:

`digraph<char> g;`

Then you add nodes and connections to the graph:

`g.add('A','B').add('B','C',1).add('D')...`

The method `add()`

can be used to add individual nodes like in `add('D')`

or connections `add('A','B')`

. In this case, the involved nodes are automatically added to the graph. There is no need to add them individually.

By default the value of the connection is 0. To create a connection with a different value use: `add('A','B',3)`

. If multiple connections between two nodes are created, only the connection with the smallest value is kept.

It is also possible to `add()`

a whole graph with all its nodes and connections. For example if `g1`

and `g2`

are two graphs, then:

`g1.add(g2)`

Will add all the nodes and connections of `g2`

into `g1`

. If multiple connections between two nodes are created, only the connection with the smallest value is kept.

Please note that the only way to modify a digraphs is by adding nodes and connections using the `add()`

method. Digraphs are otherwise immutable, and all other transformation implies the creation of a new digraph.

## Accessing nodes and connections

To access the nodes of a graph, one uses the method `g.nodes()`

. For example to iterate over the nodes:

```
for (const auto& n : g.nodes()) {
... do something with node n ...
}
```

Once you have a node you can iterate over its connections. To access the connections of a node we use the method `g.connections(n)`

:

```
for (const auto& n : g.nodes()) {
for (const auto& c : g.connections(n)) {
... c.first: destination node of the connection
... c.second: value of the connection
}
}
```

## Algorithms and Operations on digraphs

Please note that the following operations never modify the graphs used as arguments.

### Partition

A partition of a digraph into strongly connected components can be obtained using the Tarjan class, an implementation of Robert Tarjan's algorithm

```
Tarjan<N> t(const digraph<N>&);
...t.partition()...
```

The Tarjan class has essentially two methods:

#### Partition

The method `partition()`

returns the partition of the graph into strongly connected components.

`partition() -> set<set<N>>&`

The result is a set of set on nodes. Each set of nodes represents a strongly connected component of the graph.

#### Cycles

The method `cycles()`

returns the number of cycles of the graph.

`cycles() -> int`

### Number of cycles

The function `cycles(mygraph)`

return the number of cycles of a graph. It uses internally `Tarjan`

.

`cycles(const digraph<N>&) -> int`

### Direct acyclic graph of graphes

The function `graph2dag(mygraph)`

uses Tarjan to transform a graph into a direct acyclic graph (DAG):

` graph2dag(const digraph<N>&) -> digraph<digraph<N>>`

The nodes of the resulting DAG are themselves graphs representing the strongly connected components of the input graph.

### Parallelize

Provided the input graph is a DAG, the function `parallelize()`

transforms the input graph into a sequence of parallel nodes

`parallelize(const digraph<N>&) -> vector<vector<N>>`

### Serialize

Provided the input graph is a DAG, the function `serialize()`

transforms the input graph into a vector of nodes

`serialize(const digraph<N>&) -> vector<N>`

### Map nodes

The function `mapnodes()`

creates a copy of the input graph in which each node is transformed by the function `f()`

. Existing connections in the input graph are preserved in the resulting graph.

`mapnodes(const digraph<N>&, f:N->M) -> digraph<M>`

### Map connections

The function `mapconnections()`

creates a copy of the input graph in which only the connections that satisfy the predicate `f()`

are kept.

`mapconnections(const digraph<N>&, f:(N,N,int)->bool) -> digraph<N>`

### Cut high-value connections

The function `cut()`

creates a copy of the input graph in which all connections of value >= `d`

are eliminated.

`cut(const digraph<N>&, d) -> digraph<N>`

### Split graph

The function `splitgraph()`

splits a graph `G`

into two subgraphs `L`

and `R`

according to a predicate `left()`

. The nodes satisfying the predicate are copied into `L`

, the others into `R`

. The connections are kept, unless they concern nodes that are not in the same subgraph.

`splitgraph(const digraph<N>& G, function<bool(const N&)> left, digraph<N>& L, digraph<N>& R)`