.TH digraph_utils 3erl "stdlib 3.14" "Ericsson AB" "Erlang Module Definition"
.SH NAME
digraph_utils \- Algorithms for directed graphs.
.SH DESCRIPTION
.LP
This module provides algorithms based on depth-first traversal of directed graphs\&. For basic functions on directed graphs, see the \fIdigraph(3erl)\fR\& module\&.
.RS 2
.TP 2
*
A \fIdirected graph\fR\& (or just "digraph") is a pair (V, E) of a finite set V of \fIvertices\fR\& and a finite set E of \fIdirected edges\fR\& (or just "edges")\&. The set of edges E is a subset of V x V (the Cartesian product of V with itself)\&.
.LP
.TP 2
*
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 \fIlabeled digraph\fR\&, and the information attached to a vertex or an edge is called a \fIlabel\fR\&\&.
.LP
.TP 2
*
An edge e = (v, w) is said to \fIemanate\fR\& from vertex v and to be \fIincident\fR\& on vertex w\&.
.LP
.TP 2
*
If an edge is emanating from v and incident on w, then w is said to be an \fIout-neighbor\fR\& of v, and v is said to be an \fIin-neighbor\fR\& of w\&.
.LP
.TP 2
*
A \fIpath\fR\& 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\&.
.LP
.TP 2
*
The \fIlength\fR\& of path P is k-1\&.
.LP
.TP 2
*
Path P is a \fIcycle\fR\& if the length of P is not zero and v[1] = v[k]\&.
.LP
.TP 2
*
A \fIloop\fR\& is a cycle of length one\&.
.LP
.TP 2
*
An \fIacyclic digraph\fR\& is a digraph without cycles\&.
.LP
.TP 2
*
A \fIdepth-first traversal\fR\& 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\&.
.LP
.TP 2
*
A \fIpartial ordering\fR\& of a set S is a transitive, antisymmetric, and reflexive relation between the objects of S\&.
.LP
.TP 2
*
The problem of \fItopological sorting\fR\& 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 \fIdigraph\fR\& 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\&.
.LP
.TP 2
*
A \fIsubgraph\fR\& G\&' of G is a digraph whose vertices and edges form subsets of the vertices and edges of G\&.
.LP
.TP 2
*
G\&' is \fImaximal\fR\& with respect to a property P if all other subgraphs that include the vertices of G\&' do not have property P\&.
.LP
.TP 2
*
A \fIstrongly connected component\fR\& is a maximal subgraph such that there is a path between each pair of vertices\&.
.LP
.TP 2
*
A \fIconnected component\fR\& is a maximal subgraph such that there is a path between each pair of vertices, considering all edges undirected\&.
.LP
.TP 2
*
An \fIarborescence\fR\& is an acyclic digraph with a vertex V, the \fIroot\fR\&, such that there is a unique path from V to every other vertex of G\&.
.LP
.TP 2
*
A \fItree\fR\& is an acyclic non-empty digraph such that there is a unique path between every pair of vertices, considering all edges undirected\&.
.LP
.RE

.SH EXPORTS
.LP
.nf

.B
arborescence_root(Digraph) -> no | {yes, Root}
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
Root = digraph:vertex()
.br
.RE
.RE
.RS
.LP
Returns \fI{yes, Root}\fR\& if \fIRoot\fR\& is the root of the arborescence \fIDigraph\fR\&, otherwise \fIno\fR\&\&.
.RE

.LP
.nf

.B
components(Digraph) -> [Component]
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
Component = [digraph:vertex()]
.br
.RE
.RE
.RS
.LP
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 \fIDigraph\fR\& occurs in exactly one component\&.
.RE

.LP
.nf

.B
condensation(Digraph) -> CondensedDigraph
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = CondensedDigraph = digraph:graph()
.br
.RE
.RE
.RS
.LP
Creates a digraph where the vertices are the strongly connected components of \fIDigraph\fR\& as returned by \fIstrong_components/1\fR\&\&. 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\&.
.LP
The created digraph has the same type as \fIDigraph\fR\&\&. All vertices and edges have the default label \fI[]\fR\&\&.
.LP
Each cycle is included in some strongly connected component, which implies that a topological ordering of the created digraph always exists\&.
.RE

.LP
.nf

.B
cyclic_strong_components(Digraph) -> [StrongComponent]
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
StrongComponent = [digraph:vertex()]
.br
.RE
.RE
.RS
.LP
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 \fIDigraph\fR\& are returned, otherwise the returned list is equal to that returned by \fIstrong_components/1\fR\&\&.
.RE

.LP
.nf

.B
is_acyclic(Digraph) -> boolean()
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
.RE
.RE
.RS
.LP
Returns \fItrue\fR\& if and only if digraph \fIDigraph\fR\& is acyclic\&.
.RE

.LP
.nf

.B
is_arborescence(Digraph) -> boolean()
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
.RE
.RE
.RS
.LP
Returns \fItrue\fR\& if and only if digraph \fIDigraph\fR\& is an arborescence\&.
.RE

.LP
.nf

.B
is_tree(Digraph) -> boolean()
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
.RE
.RE
.RS
.LP
Returns \fItrue\fR\& if and only if digraph \fIDigraph\fR\& is a tree\&.
.RE

.LP
.nf

.B
loop_vertices(Digraph) -> Vertices
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
Vertices = [digraph:vertex()]
.br
.RE
.RE
.RS
.LP
Returns a list of all vertices of \fIDigraph\fR\& that are included in some loop\&.
.RE

.LP
.nf

.B
postorder(Digraph) -> Vertices
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
Vertices = [digraph:vertex()]
.br
.RE
.RE
.RS
.LP
Returns all vertices of digraph \fIDigraph\fR\&\&. 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\&.
.RE

.LP
.nf

.B
preorder(Digraph) -> Vertices
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
Vertices = [digraph:vertex()]
.br
.RE
.RE
.RS
.LP
Returns all vertices of digraph \fIDigraph\fR\&\&. The order is given by a depth-first traversal of the digraph, collecting visited vertices in preorder\&.
.RE

.LP
.nf

.B
reachable(Vertices, Digraph) -> Reachable
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
Vertices = Reachable = [digraph:vertex()]
.br
.RE
.RE
.RS
.LP
Returns an unsorted list of digraph vertices such that for each vertex in the list, there is a path in \fIDigraph\fR\& from some vertex of \fIVertices\fR\& to the vertex\&. In particular, as paths can have length zero, the vertices of \fIVertices\fR\& are included in the returned list\&.
.RE

.LP
.nf

.B
reachable_neighbours(Vertices, Digraph) -> Reachable
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
Vertices = Reachable = [digraph:vertex()]
.br
.RE
.RE
.RS
.LP
Returns an unsorted list of digraph vertices such that for each vertex in the list, there is a path in \fIDigraph\fR\& of length one or more from some vertex of \fIVertices\fR\& to the vertex\&. As a consequence, only those vertices of \fIVertices\fR\& that are included in some cycle are returned\&.
.RE

.LP
.nf

.B
reaching(Vertices, Digraph) -> Reaching
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
Vertices = Reaching = [digraph:vertex()]
.br
.RE
.RE
.RS
.LP
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 \fIVertices\fR\&\&. In particular, as paths can have length zero, the vertices of \fIVertices\fR\& are included in the returned list\&.
.RE

.LP
.nf

.B
reaching_neighbours(Vertices, Digraph) -> Reaching
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
Vertices = Reaching = [digraph:vertex()]
.br
.RE
.RE
.RS
.LP
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 \fIVertices\fR\&\&. Therefore only those vertices of \fIVertices\fR\& that are included in some cycle are returned\&.
.RE

.LP
.nf

.B
strong_components(Digraph) -> [StrongComponent]
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
StrongComponent = [digraph:vertex()]
.br
.RE
.RE
.RS
.LP
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 \fIDigraph\fR\& occurs in exactly one strong component\&.
.RE

.LP
.nf

.B
subgraph(Digraph, Vertices) -> SubGraph
.br
.fi
.br
.nf

.B
subgraph(Digraph, Vertices, Options) -> SubGraph
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = SubGraph = digraph:graph()
.br
Vertices = [digraph:vertex()]
.br
Options = [{type, SubgraphType} | {keep_labels, boolean()}]
.br
SubgraphType = inherit | [digraph:d_type()]
.br
.RE
.RE
.RS
.LP
Creates a maximal subgraph of \fIDigraph\fR\& having as vertices those vertices of \fIDigraph\fR\& that are mentioned in \fIVertices\fR\&\&.
.LP
If the value of option \fItype\fR\& is \fIinherit\fR\&, which is the default, the type of \fIDigraph\fR\& is used for the subgraph as well\&. Otherwise the option value of \fItype\fR\& is used as argument to \fIdigraph:new/1\fR\&\&.
.LP
If the value of option \fIkeep_labels\fR\& is \fItrue\fR\&, which is the default, the labels of vertices and edges of \fIDigraph\fR\& are used for the subgraph as well\&. If the value is \fIfalse\fR\&, default label \fI[]\fR\& is used for the vertices and edges of the subgroup\&.
.LP
\fIsubgraph(Digraph, Vertices)\fR\& is equivalent to \fIsubgraph(Digraph, Vertices, [])\fR\&\&.
.LP
If any of the arguments are invalid, a \fIbadarg\fR\& exception is raised\&.
.RE

.LP
.nf

.B
topsort(Digraph) -> Vertices | false
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Digraph = digraph:graph()
.br
Vertices = [digraph:vertex()]
.br
.RE
.RE
.RS
.LP
Returns a topological ordering of the vertices of digraph \fIDigraph\fR\& if such an ordering exists, otherwise \fIfalse\fR\&\&. For each vertex in the returned list, no out-neighbors occur earlier in the list\&.
.RE

.SH "SEE ALSO"

.LP
\fIdigraph(3erl)\fR\&