# FreeBSD Manual Pages

```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).

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	to v[k]	in a digraph (V, E) is a non-empty se-
quence 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 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.