Provided by: erlang-manpages_16.b.3-dfsg-1ubuntu2_all bug

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)