# FreeBSD Manual Pages

```digraph(3)		   Erlang Module Definition		    digraph(3)

NAME
digraph - Directed graphs.

DESCRIPTION
This  module  provides a	version	of labeled directed graphs. What makes
the graphs provided here	non-proper directed graphs  is	that  multiple
edges  between  vertices	are allowed. However, the customary definition
of directed graphs is used here.

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

In  this  module,  V	is allowed to be empty.	The so obtained	unique
digraph is called the empty digraph.	Both vertices  and  edges  are
represented by unique Erlang	terms.

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. Labels  are  Er-
lang	terms.

* An edge e = (v, w) is said to emanate from vertex v and to be inci-
dent	on vertex w.

* The out-degree of a vertex is the number of	edges  emanating  from
that	vertex.

* The	in-degree  of a	vertex is the number of	edges incident on that
vertex.

* 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	simple	if  all	vertices are distinct, except that the
first and the last vertices can be the same.

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

* A simple cycle is a path that is both a cycle and simple.

* An acyclic digraph is a digraph without cycles.

DATA TYPES
d_type()	= d_cyclicity()	| d_protection()

d_cyclicity() = acyclic | cyclic

d_protection() =	private	| protected

graph()

A	digraph	as returned by new/0,1.

edge()

label() = term()

vertex()

EXPORTS

add_edge(G, E, V1, V2, Label) ->

Types:

G = graph()
E = edge()
V1 = V2 = vertex()
Label = label()

add_edge/5 creates (or modifies) edge E of digraph G, using  La-
bel  as  the (new) label of the edge. The	edge is	emanating from
V1 and incident on V2. Returns E.

V2,  Label), where E is a	created	edge. The created edge is rep-
resented by term ['\$e' | N], where N is an integer >= 0.

If the edge would	create a cycle in an acyclic digraph,  {error,
value  E	connecting  a  different  pair	of  vertices,  {error,
{bad_edge,  [V1, V2]}} is	returned. If either of V1 or V2	is not
a	vertex of digraph G, {error, {bad_vertex, V}} is returned, V =
V1 or V =	V2.

Types:

G = graph()
V = vertex()
Label = label()

add_vertex/3  creates (or	modifies) vertex V of digraph G, using
Label as the (new) label of the vertex. Returns V.

add_vertex/1 creates a vertex using the empty list as label, and
returns the created vertex. The created vertex is	represented by
term ['\$v' | N], where N is an integer >=	0.

del_edge(G, E) -> true

Types:

G = graph()
E = edge()

Deletes edge E from digraph G.

del_edges(G, Edges) -> true

Types:

G = graph()
Edges = [edge()]

Deletes the edges	in list	Edges from digraph G.

del_path(G, V1, V2) -> true

Types:

G = graph()
V1 = V2 = vertex()

Deletes edges from digraph G until there are no paths from  ver-
tex V1 to	vertex V2.

A	sketch of the procedure	employed:

* Find	an arbitrary simple path v, v, ..., v[k] from V1
to V2	in G.

* Remove all edges of G	emanating from v[i]  and  incident  to
v[i+1] for 1 <= i < k	(including multiple edges).

* Repeat until there is	no path	between	V1 and V2.

del_vertex(G, V)	-> true

Types:

G = graph()
V = vertex()

Deletes  vertex  V from digraph G. Any edges emanating from V or
incident on V are	also deleted.

del_vertices(G, Vertices) -> true

Types:

G = graph()
Vertices = [vertex()]

Deletes the vertices in list Vertices from digraph G.

delete(G) -> true

Types:

G = graph()

Deletes digraph G. This call is important	as digraphs are	imple-
mented  with  ETS. There is no garbage collection	of ETS tables.
However, the digraph is deleted if the process that created  the
digraph terminates.

edge(G, E) -> {E, V1, V2, Label}	| false

Types:

G = graph()
E = edge()
V1 = V2 = vertex()
Label = label()

Returns  {E,  V1,	V2, Label}, where Label	is the label of	edge E
emanating	from V1	and incident on	V2 of digraph G. If no edge  E
of digraph G exists, false is returned.

edges(G)	-> Edges

Types:

G = graph()
Edges = [edge()]

Returns  a  list	of all edges of	digraph	G, in some unspecified
order.

edges(G,	V) -> Edges

Types:

G = graph()
V = vertex()
Edges = [edge()]

Returns a	list of	all edges emanating from or  incident  onV  of
digraph G, in some unspecified order.

get_cycle(G, V) -> Vertices | false

Types:

G = graph()
V = vertex()
Vertices = [vertex(), ...]

If a simple cycle	of length two or more exists through vertex V,
the cycle	is returned as a list [V, ..., V] of  vertices.	 If  a
loop through V exists, the loop is returned as a list [V]. If no
cycles through V exist, false is returned.

get_path/3 is used for finding a simple cycle through V.

get_path(G, V1, V2) -> Vertices | false

Types:

G = graph()
V1 = V2 = vertex()
Vertices = [vertex(), ...]

Tries to find a simple path from vertex V1 to vertex V2  of  di-
graph  G.	 Returns the path as a list [V1, ..., V2] of vertices,
or false if no simple path from V1 to V2 of length one  or  more
exists.

Digraph  G  is  traversed	in a depth-first manner, and the first
found path is returned.

get_short_cycle(G, V) ->	Vertices | false

Types:

G = graph()
V = vertex()
Vertices = [vertex(), ...]

Tries to find an as short	as possible simple cycle through  ver-
tex  V  of digraph G. Returns the	cycle as a list	[V, ..., V] of
vertices,	or false if no simple cycle through V  exists.	Notice
that a loop through V is returned	as list	[V, V].

get_short_path/3 is used for finding a simple cycle through V.

get_short_path(G, V1, V2) -> Vertices | false

Types:

G = graph()
V1 = V2 = vertex()
Vertices = [vertex(), ...]

Tries to find an as short	as possible simple path	from vertex V1
to vertex	V2 of digraph G. Returns the path as a list [V1,  ...,
V2]  of  vertices,  or  false if no simple path from V1 to V2 of
length one or more exists.

Digraph G	is traversed in	a breadth-first	manner,	and the	 first
found path is returned.

in_degree(G, V) -> integer() >= 0

Types:

G = graph()
V = vertex()

Returns the in-degree of vertex V	of digraph G.

in_edges(G, V) -> Edges

Types:

G = graph()
V = vertex()
Edges = [edge()]

Returns  a list of all edges incident on V of digraph G, in some
unspecified order.

in_neighbours(G,	V) -> Vertex

Types:

G = graph()
V = vertex()
Vertex	= [vertex()]

Returns a	list of	all in-neighbors of V of digraph  G,  in  some
unspecified order.

info(G) -> InfoList

Types:

G = graph()
InfoList =
[{cyclicity, Cyclicity :: d_cyclicity()} |
{memory, NoWords :: integer() >= 0} |
{protection, Protection :: d_protection()}]
d_cyclicity() = acyclic | cyclic
d_protection()	= private | protected

Returns  a  list of {Tag,	Value} pairs describing	digraph	G. The
following	pairs are returned:

* {cyclicity,  Cyclicity},  where  Cyclicity  is   cyclic   or
acyclic, according to	the options given to new.

* {memory,  NoWords}, where NoWords is the number of words al-
located to the ETS tables.

* {protection, Protection}, where Protection is	 protected  or
private, according to	the options given to new.

new() ->	graph()

Equivalent to new([]).

new(Type) -> graph()

Types:

Type =	[d_type()]
d_type() = d_cyclicity() | d_protection()
d_cyclicity() = acyclic | cyclic
d_protection()	= private | protected

Returns  an  empty  digraph with properties according to the op-
tions in Type:

cyclic:
Allows cycles	in the digraph (default).

acyclic:
The digraph is to be kept acyclic.

protected:
Other	processes can read the digraph (default).

private:
The digraph can be read and modified by the creating process
only.

If  an  unrecognized type	option T is specified or Type is not a
proper list, a badarg exception is raised.

no_edges(G) -> integer()	>= 0

Types:

G = graph()

Returns the number of edges of digraph G.

no_vertices(G) -> integer() >= 0

Types:

G = graph()

Returns the number of vertices of	digraph	G.

out_degree(G, V)	-> integer() >=	0

Types:

G = graph()
V = vertex()

Returns the out-degree of	vertex V of digraph G.

out_edges(G, V) -> Edges

Types:

G = graph()
V = vertex()
Edges = [edge()]

Returns a	list of	all edges emanating from V of  digraph	G,  in
some unspecified order.

out_neighbours(G, V) -> Vertices

Types:

G = graph()
V = vertex()
Vertices = [vertex()]

Returns  a  list of all out-neighbors of V of digraph G, in some
unspecified order.

vertex(G, V) -> {V, Label} | false

Types:

G = graph()
V = vertex()
Label = label()

Returns {V, Label}, where	Label is the label of the vertex V  of
digraph G, or false if no	vertex V of digraph G exists.

vertices(G) -> Vertices

Types:

G = graph()
Vertices = [vertex()]

Returns a	list of	all vertices of	digraph	G, in some unspecified
order.