Provided by: erlang-manpages_22.2.7+dfsg-1_all bug

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[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.

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.

SEE ALSO

       digraph(3erl)