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 di-
rected graphs. For basic functions on directed graphs, see the di-
graph(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 inci-
dent 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 se-
quence 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 ar-
bitrarily 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 unex-
amined 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 di-
rected 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 order-
ing.
* A subgraph G' of G is a digraph whose vertices and edges form sub-
sets 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 undi-
rected.
* 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 undi-
rected.
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 Di-
graph, otherwise no.
components(Digraph) -> [Component]
Types:
Digraph = digraph:graph()
Component = [digraph:vertex()]
Returns a list of connected components.. Each component is rep-
resented by its vertices. The order of the vertices and the or-
der of the components are arbitrary. Each vertex of digraph Di-
graph 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 ver-
tices 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 emanat-
ing 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 ver-
tices and the order of the components are arbitrary. Only ver-
tices 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 ver-
tices 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 ver-
tices 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 re-
turned 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 conse-
quence, 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 ver-
tex 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 ver-
tices 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 ver-
tices 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 de-
fault, 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 Di-
graph if such an ordering exists, otherwise false. For each ver-
tex in the returned list, no out-neighbors occur earlier in the
list.
SEE ALSO
digraph(3erl)
Ericsson AB stdlib 3.13 digraph_utils(3erl)