View Source digraph_utils (stdlib v6.0)
This module provides algorithms based on depth-first traversal of directed graphs.
For basic functions on directed graphs, see the digraph 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
digraphmodule 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.
See Also
Summary
Functions
Returns {yes, Root} if Root is the root of the
arborescence Digraph, otherwise no.
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.
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.
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.
Returns true if and only if digraph Digraph is
acyclic.
Returns true if and only if digraph Digraph is an
arborescence.
Returns true if and only if digraph Digraph is a
tree.
Returns a list of all vertices of Digraph that are included in some
loop.
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.
Returns all vertices of digraph Digraph. The order is given by a
depth-first traversal of the digraph,
collecting visited vertices in preorder.
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.
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.
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.
Equivalent to subgraph/3.
Creates a maximal subgraph of Digraph having as
vertices those vertices of Digraph that are mentioned in Vertices.
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.
Functions
-spec arborescence_root(Digraph) -> no | {yes, Root} when Digraph :: digraph:graph(), Root :: digraph:vertex().
Returns {yes, Root} if Root is the root of the
arborescence Digraph, otherwise no.
-spec components(Digraph) -> [Component] when 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.
-spec condensation(Digraph) -> CondensedDigraph when Digraph :: digraph:graph(), 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.
-spec cyclic_strong_components(Digraph) -> [StrongComponent] when 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.
-spec is_acyclic(Digraph) -> boolean() when Digraph :: digraph:graph().
Returns true if and only if digraph Digraph is
acyclic.
-spec is_arborescence(Digraph) -> boolean() when Digraph :: digraph:graph().
Returns true if and only if digraph Digraph is an
arborescence.
-spec is_tree(Digraph) -> boolean() when Digraph :: digraph:graph().
Returns true if and only if digraph Digraph is a
tree.
-spec loop_vertices(Digraph) -> Vertices when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()].
Returns a list of all vertices of Digraph that are included in some
loop.
-spec postorder(Digraph) -> Vertices when 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.
-spec preorder(Digraph) -> Vertices when 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.
-spec reachable(Vertices, Digraph) -> Reachable when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()], 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.
-spec reachable_neighbours(Vertices, Digraph) -> Reachable when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()], 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.
-spec reaching(Vertices, Digraph) -> Reaching when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()], 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.
-spec reaching_neighbours(Vertices, Digraph) -> Reaching when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()], 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.
-spec strong_components(Digraph) -> [StrongComponent] when 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.
-spec subgraph(Digraph, Vertices) -> SubGraph when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()], SubGraph :: digraph:graph().
Equivalent to subgraph/3.
-spec subgraph(Digraph, Vertices, Options) -> SubGraph when Digraph :: digraph:graph(), 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.
-spec topsort(Digraph) -> Vertices | false when 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.