digraph_utils
Algorithms for directed graphs.
This module provides algorithms based on depth-first traversal of
directed graphs. For basic functions on directed graphs, see the
digraph(3)
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 × 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.
Functions
arborescence_root(Digraph) -> no | {yes, Root}
Digraph = digraph:graph()
Root = digraph:vertex()
Returns {yes,
if
is the root of the arborescence
, otherwise no
.
components(Digraph) -> [Component]
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
occurs in exactly one component.
condensation(Digraph) -> CondensedDigraph
Digraph = CondensedDigraph = digraph:graph()
Creates a digraph where the vertices are
the strongly connected
components of
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
.
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]
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
are returned, otherwise the returned
list is equal to that returned by
strong_components/1
.
is_acyclic(Digraph) -> boolean()
Digraph = digraph:graph()
Returns true
if and only if digraph
is
acyclic.
is_arborescence(Digraph) -> boolean()
Digraph = digraph:graph()
Returns true
if and only if digraph
is
an arborescence.
is_tree(Digraph) -> boolean()
Digraph = digraph:graph()
Returns true
if and only if digraph
is
a tree.
loop_vertices(Digraph) -> Vertices
Digraph = digraph:graph()
Vertices = [digraph:vertex()]
Returns a list of all vertices of
that
are included in some loop.
postorder(Digraph) -> Vertices
Digraph = digraph:graph()
Vertices = [digraph:vertex()]
Returns all vertices of 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
Digraph = digraph:graph()
Vertices = [digraph:vertex()]
Returns all vertices of digraph
.
The order is given by
a depth-first
traversal of the digraph, collecting visited
vertices in preorder.
reachable(Vertices, Digraph) -> Reachable
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
from some
vertex of
to the vertex. In particular,
as paths can have length zero, the vertices of
are included in the returned list.
reachable_neighbours(Vertices, Digraph) -> Reachable
Digraph = digraph:graph()
Vertices = Reachable = [digraph:vertex()]
reaching(Vertices, Digraph) -> Reaching
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
. In particular, as paths
can have length zero, the vertices of
are included in the returned list.
reaching_neighbours(Vertices, Digraph) -> Reaching
Digraph = digraph:graph()
Vertices = Reaching = [digraph:vertex()]
strong_components(Digraph) -> [StrongComponent]
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
occurs in exactly one strong component.
subgraph(Digraph, Vertices) -> SubGraph
Digraph = digraph:graph()
Vertices = [digraph:vertex()]
SubGraph = digraph:graph()
subgraph(Digraph, Vertices, Options) -> SubGraph
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
that are
mentioned in
.
If the value of option type
is inherit
, which is
the default, the type of
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
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(
is
equivalent to
subgraph(
.
If any of the arguments are invalid, a badarg
exception is
raised.
topsort(Digraph) -> Vertices | false
Digraph = digraph:graph()
Vertices = [digraph:vertex()]
Returns a topological
ordering of the vertices of digraph
if such an ordering exists, otherwise
false
. For each vertex in the returned list,
no out-neighbors
occur earlier in the list.