👤
Home Man
Search
Today's Posts
Register

Linux & Unix Commands - Search Man Pages
Man Page or Keyword Search:
Select Section of Man Page:
Select Man Page Repository:

Linux 2.6 - man page for digraph_utils (linux section 3erl)

digraph_utils(3erl)		     Erlang Module Definition		      digraph_utils(3erl)

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 order-
       ing.

       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, consid-
       ering all edges undirected.

EXPORTS
       arborescence_root(Digraph) -> no | {yes, Root}

	      Types  Digraph = digraph()
		     Root = vertex()

	      Returns {yes, Root} if Root is the root of the arborescence Digraph , no otherwise.

       components(Digraph) -> [Component]

	      Types  Digraph = digraph()
		     Component = [vertex()]

	      Returns a list of connected components . Each component is represented by its  ver-
	      tices.  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 strongly connected com-
	      ponents, 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 = [vertex()]

	      Returns a list of strongly connected components . Each strongly component is repre-
	      sented  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_compo-
	      nents/1 .

       is_acyclic(Digraph) -> bool()

	      Types  Digraph = digraph()

	      Returns true if and only if the digraph Digraph is acyclic .

       is_arborescence(Digraph) -> bool()

	      Types  Digraph = digraph()

	      Returns true if and only if the digraph Digraph is an arborescence .

       is_tree(Digraph) -> bool()

	      Types  Digraph = digraph()

	      Returns true if and only if the digraph Digraph is a tree .

       loop_vertices(Digraph) -> Vertices

	      Types  Digraph = digraph()
		     Vertices = [vertex()]

	      Returns a list of all vertices of Digraph that are included in some loop .

       postorder(Digraph) -> Vertices

	      Types  Digraph = digraph()
		     Vertices = [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  col-
	      lected  in postorder, and all those collected vertices are placed before the subse-
	      quently visited vertices.

       preorder(Digraph) -> Vertices

	      Types  Digraph = digraph()
		     Vertices = [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) -> Vertices

	      Types  Digraph = digraph()
		     Vertices = [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  particu-
	      lar, since paths may have length zero, the vertices of Vertices are included in the
	      returned list.

       reachable_neighbours(Vertices, Digraph) -> Vertices

	      Types  Digraph = digraph()
		     Vertices = [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) -> Vertices

	      Types  Digraph = digraph()
		     Vertices = [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) -> Vertices

	      Types  Digraph = digraph()
		     Vertices = [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 = [vertex()]

	      Returns a list of strongly connected components . Each strongly component is repre-
	      sented 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 com-
	      ponent.

       subgraph(Digraph, Vertices [, Options]) -> Subgraph

	      Types  Digraph = Subgraph = digraph()
		     Options = [{type, SubgraphType}, {keep_labels, bool()}]
		     SubgraphType = inherit | type()
		     Vertices = [vertex()]

	      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 = [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)

Ericsson AB				  stdlib 1.17.3 		      digraph_utils(3erl)


All times are GMT -4. The time now is 01:56 AM.

Unix & Linux Forums Content Copyrightę1993-2018. All Rights Reserved.
×
UNIX.COM Login
Username:
Password:  
Show Password