Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
digraph_utils(3)	   Erlang Module Definition	      digraph_utils(3)

NAME
       digraph_utils - Algorithms for directed graphs.

DESCRIPTION
       This  module  provides algorithms based on depth-first traversal	of di-
       rected graphs. For basic	functions on  directed	graphs,	 see  the  di-
       graph(3)	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 inci-
	   dent	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 se-
	   quence 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 ar-
	   bitrarily 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	 unex-
	   amined  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 di-
	   rected  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	order-
	   ing.

	 * A subgraph G' of G is a digraph whose vertices and edges form  sub-
	   sets	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	 undi-
	   rected.

	 * 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 undi-
	   rected.

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  Di-
	      graph, otherwise no.

       components(Digraph) -> [Component]

	      Types:

		 Digraph = digraph:graph()
		 Component = [digraph:vertex()]

	      Returns  a list of connected components..	Each component is rep-
	      resented by its vertices.	The order of the vertices and the  or-
	      der  of the components are arbitrary. Each vertex	of digraph Di-
	      graph 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  ver-
	      tices 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 emanat-
	      ing 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 ver-
	      tices and	the order of the components are	arbitrary.  Only  ver-
	      tices  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 ver-
	      tices 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  ver-
	      tices 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  re-
	      turned 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	conse-
	      quence, 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 ver-
	      tex  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 ver-
	      tices 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  ver-
	      tices 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 de-
	      fault, 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  Di-
	      graph if such an ordering	exists,	otherwise false. For each ver-
	      tex in the returned list,	no out-neighbors occur earlier in  the
	      list.

SEE ALSO
       digraph(3)

Ericsson AB			  stdlib 3.8		      digraph_utils(3)

NAME | DESCRIPTION | EXPORTS | SEE ALSO

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=digraph_utils&sektion=3&manpath=FreeBSD+13.0-RELEASE+and+Ports>

home | help