# digraph_utils

## Algorithms for Directed Graphs

The `digraph_utils`

module implements some algorithms
based on depth-first traversal of directed graphs. See the
`digraph`

module for basic functions on directed graphs.

A *directed graph* (or
just "digraph") is a pair (V, E) of a finite set V of
*vertices* and a finite set E
of *directed edges* (or just
"edges"). The set of edges E is a subset of V × V
(the Cartesian product of V with itself).

Digraphs can be annotated with additional information. Such
information may be attached to the vertices and to the edges of
the digraph. A digraph which has been annotated is called a
*labeled digraph*, and the information attached to a
vertex or an edge is called a
*label*.

An edge e = (v, w) is said
to *emanate* from vertex v and
to be *incident* on vertex w.
If there is an edge emanating from v and incident on w, then w is
said to be
an *out-neighbour* of v,
and v is said to be
an *in-neighbour* of w.
A *path* P from v[1] to v[k] in a
digraph (V, E) is a non-empty sequence
v[1], v[2], ..., v[k] of vertices in V such that
there is an edge (v[i],v[i+1]) in E for
1 <= i < k.
The *length* of the path P is k-1.
P is a *cycle* if the length of P
is not zero and v[1] = v[k].
A *loop* is a cycle of length one.
An *acyclic digraph* is
a digraph that has no cycles.

A *depth-first
traversal* of a directed digraph can be viewed as a process
that visits all vertices of the digraph. Initially, all vertices
are marked as unvisited. The traversal starts with an
arbitrarily chosen vertex, which is marked as visited, and
follows an edge to an unmarked vertex, marking that vertex. The
search then proceeds from that vertex in the same fashion, until
there is no edge leading to an unvisited vertex. At that point
the process backtracks, and the traversal continues as long as
there are unexamined edges. If there remain unvisited vertices
when all edges from the first vertex have been examined, some
hitherto unvisited vertex is chosen, and the process is
repeated.

A *partial ordering* of
a set S is a transitive, antisymmetric and reflexive relation
between the objects of S. The problem
of *topological sorting* is to
find a total
ordering of S that is a superset of the partial ordering. A
digraph G = (V, E) is equivalent to a relation E
on V (we neglect the fact that the version of directed graphs
implemented in the `digraph`

module allows multiple edges
between vertices). If the digraph has no cycles of length two or
more, then the reflexive and transitive closure of E is a
partial ordering.

A *subgraph* G' of G is a
digraph whose vertices and edges form subsets of the vertices
and edges of G. G' is *maximal* with respect to a
property P if all other subgraphs that include the vertices of
G' do not have the property P. A *strongly connected
component* is a maximal subgraph such that there is a path
between each pair of vertices. A *connected component* is a
maximal subgraph such that there is a path between each pair of
vertices, considering all edges undirected. An *arborescence* is an acyclic
digraph with a vertex V, the *root*, such that there is a unique
path from V to every other vertex of G. A *tree* is an acyclic non-empty digraph
such that there is a unique path between every pair of vertices,
considering all edges undirected.

#### Functions

### arborescence_root(Digraph) -> no | {yes, Root}

`Digraph = digraph()`

`Root = digraph:vertex()`

Returns `{yes, `

if

is
the root of the arborescence

, `no`

otherwise.

### components(Digraph) -> [Component]

`Digraph = digraph()`

`Component = [digraph:vertex()]`

Returns a list
of connected components.
Each component is represented by its
vertices. The order of the vertices and the order of the
components are arbitrary. Each vertex of the digraph

occurs in exactly one component.

### condensation(Digraph) -> CondensedDigraph

`Digraph = CondensedDigraph = digraph()`

Creates a digraph where the vertices are
the strongly connected
components of

as returned by
`strong_components/1`

. If X and Y are two different strongly
connected components, and there exist vertices x and y in X
and Y respectively such that there is an
edge emanating from x
and incident on y, then
an edge emanating from X and incident on Y is created.

The created digraph has the same type as

.
All vertices and edges have the
default label `[]`

.

Each and every cycle is included in some strongly connected component, which implies that there always exists a topological ordering of the created digraph.

### cyclic_strong_components(Digraph) -> [StrongComponent]

`Digraph = digraph()`

`StrongComponent = [digraph:vertex()]`

Returns a list of strongly
connected components.
Each strongly component is represented
by its vertices. The order of the vertices and the order of
the components are arbitrary. Only vertices that are
included in some cycle in

are returned, otherwise the returned list is
equal to that returned by `strong_components/1`

.

### is_acyclic(Digraph) -> boolean()

`Digraph = digraph()`

Returns `true`

if and only if the digraph

is acyclic.

### is_arborescence(Digraph) -> boolean()

`Digraph = digraph()`

Returns `true`

if and only if the digraph

is
an arborescence.

### is_tree(Digraph) -> boolean()

`Digraph = digraph()`

Returns `true`

if and only if the digraph

is
a tree.

### loop_vertices(Digraph) -> Vertices

`Digraph = digraph()`

`Vertices = [digraph:vertex()]`

Returns a list of all vertices of

that are
included in some loop.

### postorder(Digraph) -> Vertices

`Digraph = digraph()`

`Vertices = [digraph:vertex()]`

Returns all vertices of the digraph

. The
order is given by
a depth-first
traversal of the digraph, collecting visited
vertices in postorder. More precisely, the vertices visited
while searching from an arbitrarily chosen vertex are
collected in postorder, and all those collected vertices are
placed before the subsequently visited vertices.

### preorder(Digraph) -> Vertices

`Digraph = digraph()`

`Vertices = [digraph:vertex()]`

Returns all vertices of the digraph

. The
order is given by
a depth-first
traversal of the digraph, collecting visited
vertices in pre-order.

### reachable(Vertices, Digraph) -> Reachable

`Digraph = digraph()`

`Vertices = Reachable = [digraph:vertex()]`

Returns an unsorted list of digraph vertices such that for
each vertex in the list, there is
a path in

from some
vertex of

to the vertex. In particular,
since paths may have length zero, the vertices of

are included in the returned list.

### reachable_neighbours(Vertices, Digraph) -> Reachable

`Digraph = digraph()`

`Vertices = Reachable = [digraph:vertex()]`

### reaching(Vertices, Digraph) -> Reaching

`Digraph = digraph()`

`Vertices = Reaching = [digraph:vertex()]`

Returns an unsorted list of digraph vertices such that for
each vertex in the list, there is
a path from the vertex to some
vertex of

. In particular, since paths may have
length zero, the vertices of

are included in
the returned list.

### reaching_neighbours(Vertices, Digraph) -> Reaching

`Digraph = digraph()`

`Vertices = Reaching = [digraph:vertex()]`

### strong_components(Digraph) -> [StrongComponent]

`Digraph = digraph()`

`StrongComponent = [digraph:vertex()]`

Returns a list of strongly
connected components.
Each strongly component is represented
by its vertices. The order of the vertices and the order of
the components are arbitrary. Each vertex of the digraph

occurs in exactly one strong component.

### subgraph(Digraph, Vertices) -> SubGraph

`Digraph = digraph()`

`Vertices = [digraph:vertex()]`

`SubGraph = digraph()`

### subgraph(Digraph, Vertices, Options) -> SubGraph

`Digraph = SubGraph = digraph()`

`Vertices = [digraph:vertex()]`

`Options = [{type, SubgraphType} | {keep_labels, boolean()}]`

`SubgraphType = inherit | [digraph:d_type()]`

Creates a maximal subgraph of `Digraph`

having
as vertices those vertices of

that are
mentioned in

.

If the value of the option `type`

is `inherit`

,
which is the default, then the type of

is used
for the subgraph as well. Otherwise the option value of `type`

is used as argument to `digraph:new/1`

.

If the value of the option `keep_labels`

is `true`

,
which is the default, then
the labels of vertices and edges
of

are used for the subgraph as well. If the value
is `false`

, then the default label, `[]`

, is used
for the subgraph's vertices and edges.

`subgraph(`

is equivalent to
`subgraph(`

.

There will be a `badarg`

exception if any of the arguments
are invalid.

### topsort(Digraph) -> Vertices | false

`Digraph = digraph()`

`Vertices = [digraph:vertex()]`

Returns a topological
ordering of the vertices of the digraph

if such an ordering exists, `false`

otherwise. For each vertex in the returned list, there are
no out-neighbours
that occur earlier in the list.