Provided by: erlang-manpages_20.2.2+dfsg-1ubuntu2_all 
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 = digraph:graph()
Root = digraph:vertex()
Returns {yes, Root} if Root is the root of the arborescence Digraph, otherwise no.
components(Digraph) -> [Component]
Types:
Digraph = 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 = CondensedDigraph = 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 = 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 = digraph:graph()
Returns true if and only if digraph Digraph is acyclic.
is_arborescence(Digraph) -> boolean()
Types:
Digraph = digraph:graph()
Returns true if and only if digraph Digraph is an arborescence.
is_tree(Digraph) -> boolean()
Types:
Digraph = digraph:graph()
Returns true if and only if digraph Digraph is a tree.
loop_vertices(Digraph) -> Vertices
Types:
Digraph = digraph:graph()
Vertices = [digraph:vertex()]
Returns a list of all vertices of Digraph that are included in some loop.
postorder(Digraph) -> Vertices
Types:
Digraph = 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 = 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 = 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 = 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 = 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 = 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 = 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 = SubGraph = 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 = 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)