## table of contents

- stretch 1:19.2.1+dfsg-2+deb9u2
- testing 1:21.2.6+dfsg-1
- unstable 1:21.2.6+dfsg-1
- experimental 1:22.0.4+dfsg-1

digraph_utils(3erl) | Erlang Module Definition | digraph_utils(3erl) |

# NAME¶

digraph_utils - Algorithms for directed graphs.# DESCRIPTION¶

This module provides algorithms based on depth-first traversal of directed graphs. For basic functions on directed graphs, see the*digraph(3erl)*module.

- *
- 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 x V (the Cartesian product of V with itself). - *
- Digraphs can be annotated with more information. Such information can be
attached to the vertices and to the edges of the digraph. An annotated
digraph 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 an edge is emanating from v and incident on w, then w is said to be an
*out-neighbor*of v, and v is said to be an*in-neighbor*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 path P is k-1. - *
- Path 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 without 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 unvisited vertices remain when all edges from the first vertex have been examined, some so far 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 that the version of directed graphs provided by the*digraph*module allows multiple edges between vertices). If the digraph has no cycles of length two or more, 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 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.

# EXPORTS¶

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

Types:

**digraph:graph()**

Root =

**digraph:vertex()**

Returns *{yes, Root}* if *Root* is the **root** of
the arborescence *Digraph*, otherwise *no*.

components(Digraph) -> [Component]

Types:

**digraph:graph()**

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 digraph *Digraph* occurs in
exactly one component.

condensation(Digraph) -> CondensedDigraph

Types:

**digraph:graph()**

Creates a digraph where the vertices are the **strongly connected
components** of *Digraph* as returned by
*strong_components/1*. If X and Y are two different strongly
connected components, and vertices x and y exist 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 *Digraph*. All
vertices and edges have the default **label** *[]*.

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

cyclic_strong_components(Digraph) -> [StrongComponent]

Types:

**digraph:graph()**

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 *Digraph* are returned, otherwise the
returned list is equal to that returned by
*strong_components/1*.

is_acyclic(Digraph) -> boolean()

Types:

**digraph:graph()**

Returns *true* if and only if digraph *Digraph* is
**acyclic**.

is_arborescence(Digraph) -> boolean()

Types:

**digraph:graph()**

Returns *true* if and only if digraph *Digraph* is an
**arborescence**.

is_tree(Digraph) -> boolean()

Types:

**digraph:graph()**

Returns *true* if and only if digraph *Digraph* is a
**tree**.

loop_vertices(Digraph) -> Vertices

Types:

**digraph:graph()**

Vertices = [

**digraph:vertex()**]

Returns a list of all vertices of *Digraph* that are included
in some **loop**.

postorder(Digraph) -> Vertices

Types:

**digraph:graph()**

Vertices = [

**digraph:vertex()**]

Returns all vertices of digraph *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

Types:

**digraph:graph()**

Vertices = [

**digraph:vertex()**]

Returns all vertices of digraph *Digraph*. The order is given
by a **depth-first traversal** of the digraph, collecting visited
vertices in preorder.

reachable(Vertices, Digraph) -> Reachable

Types:

**digraph:graph()**

Vertices = Reachable = [

**digraph:vertex()**]

Returns an unsorted list of digraph vertices such that for each
vertex in the list, there is a **path** in *Digraph* from some
vertex of *Vertices* to the vertex. In particular, as paths can have
length zero, the vertices of *Vertices* are included in the returned
list.

reachable_neighbours(Vertices, Digraph) -> Reachable

Types:

**digraph:graph()**

Vertices = Reachable = [

**digraph:vertex()**]

Returns an unsorted list of digraph vertices such that for each
vertex in the list, there is a **path** in *Digraph* of length one
or more from some vertex of *Vertices* to the vertex. As a consequence,
only those vertices of *Vertices* that are included in some
**cycle** are returned.

reaching(Vertices, Digraph) -> Reaching

Types:

**digraph:graph()**

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
*Vertices*. In particular, as paths can have length zero, the vertices
of *Vertices* are included in the returned list.

reaching_neighbours(Vertices, Digraph) -> Reaching

Types:

**digraph:graph()**

Vertices = Reaching = [

**digraph:vertex()**]

Returns an unsorted list of digraph vertices such that for each
vertex in the list, there is a **path** of length one or more from the
vertex to some vertex of *Vertices*. Therefore only those vertices of
*Vertices* that are included in some **cycle** are returned.

strong_components(Digraph) -> [StrongComponent]

Types:

**digraph:graph()**

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 digraph
*Digraph* occurs in exactly one strong component.

subgraph(Digraph, Vertices) -> SubGraph

subgraph(Digraph, Vertices, Options) -> SubGraph

Types:

**digraph:graph()**

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 *Digraph* that are mentioned in
*Vertices*.

If the value of option *type* is *inherit*, which is the
default, the type of *Digraph* 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 option *keep_labels* is *true*, which is
the default, the **labels** of vertices and edges of *Digraph* are
used for the subgraph as well. If the value is *false*, default label
*[]* is used for the vertices and edges of the subgroup.

*subgraph(Digraph, Vertices)* is equivalent to
*subgraph(Digraph, Vertices, [])*.

If any of the arguments are invalid, a *badarg* exception is
raised.

topsort(Digraph) -> Vertices | false

Types:

**digraph:graph()**

Vertices = [

**digraph:vertex()**]

Returns a **topological ordering** of the vertices of digraph
*Digraph* if such an ordering exists, otherwise *false*. For each
vertex in the returned list, no **out-neighbors** occur earlier in the
list.

# SEE ALSO¶

*digraph(3erl)*

stdlib 3.2 | Ericsson AB |