trusty (3) digraph_utils.3erl.gz
NAME
digraph_utils - Algorithms for Directed Graphs
DESCRIPTION
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 x 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.
DATA TYPES
digraph()
A digraph as returned by digraph:new/0,1.
EXPORTS
arborescence_root(Digraph) -> no | {yes, Root}
Types:
Digraph = digraph()
Root = digraph:vertex()
Returns {yes, Root} if Root is the root of the arborescence Digraph, no otherwise.
components(Digraph) -> [Component]
Types:
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 Digraph
occurs in exactly one component.
condensation(Digraph) -> CondensedDigraph
Types:
Digraph = CondensedDigraph = digraph()
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 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 Digraph. 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]
Types:
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 Digraph are returned, otherwise the returned list is equal to
that returned by strong_components/1.
is_acyclic(Digraph) -> boolean()
Types:
Digraph = digraph()
Returns true if and only if the digraph Digraph is acyclic.
is_arborescence(Digraph) -> boolean()
Types:
Digraph = digraph()
Returns true if and only if the digraph Digraph is an arborescence.
is_tree(Digraph) -> boolean()
Types:
Digraph = digraph()
Returns true if and only if the digraph Digraph is a tree.
loop_vertices(Digraph) -> Vertices
Types:
Digraph = digraph()
Vertices = [digraph:vertex()]
Returns a list of all vertices of Digraph that are included in some loop.
postorder(Digraph) -> Vertices
Types:
Digraph = digraph()
Vertices = [digraph:vertex()]
Returns all vertices of the 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()
Vertices = [digraph:vertex()]
Returns all vertices of the digraph Digraph. The order is given by a depth-first traversal of the
digraph, collecting visited vertices in pre-order.
reachable(Vertices, Digraph) -> Reachable
Types:
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 Digraph from some vertex of Vertices to the vertex. In particular, since paths may have
length zero, the vertices of Vertices are included in the returned list.
reachable_neighbours(Vertices, Digraph) -> Reachable
Types:
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 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()
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, since paths may have length zero,
the vertices of Vertices are included in the returned list.
reaching_neighbours(Vertices, Digraph) -> Reaching
Types:
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 of length one or more from the vertex to some vertex of Vertices. As a consequence, only
those vertices of Vertices that are included in some cycle are returned.
strong_components(Digraph) -> [StrongComponent]
Types:
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 Digraph occurs in exactly one strong component.
subgraph(Digraph, Vertices) -> SubGraph
subgraph(Digraph, Vertices, Options) -> SubGraph
Types:
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 Digraph that are
mentioned in Vertices.
If the value of the option type is inherit, which is the default, then 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 the option keep_labels is true, which is the default, then the labels of vertices
and edges of Digraph 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(Digraph, Vertices) is equivalent to subgraph(Digraph, Vertices, []).
There will be a badarg exception if any of the arguments are invalid.
topsort(Digraph) -> Vertices | false
Types:
Digraph = digraph()
Vertices = [digraph:vertex()]
Returns a topological ordering of the vertices of the digraph 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.
SEE ALSO
digraph(3erl)