Provided by: erlang-manpages_22.2.7+dfsg-1_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 to v[k] in a digraph (V, E) is a non-empty sequence v, v,
..., 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 = 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.

```

#### SEEALSO

```       digraph(3erl)
```