![[Ericsson AB]](min_head.gif)
The digraph module implements a version of labeled
directed graphs. What makes the graphs implemented here
non-proper directed graphs is that multiple edges between
vertices are allowed. However, the customary definition of
directed graphs will be used in the text that follows.
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 × 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.
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. Labels are Erlang terms.
An edge e = (v, w) is said to emanate from vertex v and to be incident 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 there is an edge emanating from v and incident on w, then w is 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 simple if all vertices are distinct, except that the first and the last vertices may be the same. 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. A simple cycle is a path that is both a cycle and simple. An acyclic digraph is a digraph that has no cycles.
add_edge(G, E, V1, V2, Label) -> edge() | {error, Reason}
add_edge(G, V1, V2, Label) -> edge() | {error, Reason}
add_edge(G, V1, V2) -> edge() | {error, Reason}
Types:
G = digraph()
E = edge()
V1 = V2 = vertex()
Label = label()
Reason = {bad_edge, Path} | {bad_vertex, V}
Path = [vertex()]
add_edge/5 creates (or modifies) the edge E
of the digraph G, using Label as the (new)
label of the edge. The
edge is emanating from
V1 and incident
on V2. Returns E.
add_edge(G, V1, V2, Label) is
equivalent to
add_edge(G, E, V1, V2, Label),
where E is a created edge. Tuples on the form
['$e' | N], where N is an
integer >= 1, are used for representing the
created edges.
add_edge(G, V1, V2) is equivalent to
add_edge(G, V1, V2, []).
If the edge would create a cycle in an acyclic digraph, then
{error, {bad_edge, Path}} is returned. If
either of V1 or V2 is not a vertex of the
digraph G, then
{error, {bad_vertex, V}} is
returned, V = V1 or
V = V2.
add_vertex(G, V, Label) -> vertex()
add_vertex(G, V) -> vertex()
add_vertex(G) -> vertex()
Types:
G = digraph()
V = vertex()
Label = label()
add_vertex/3 creates (or modifies) the vertex V
of the digraph G, using Label as the (new)
label of the
vertex. Returns V.
add_vertex(G, V) is equivalent to
add_vertex(G, V, []).
add_vertex/1 creates a vertex using the empty list
as label, and returns the created vertex. Tuples on the form
['$v' | N], where N is an
integer >= 1, are used for representing the
created vertices.
Types:
G = digraph()
E = edge()
Deletes the edge E from the digraph G.
Types:
G = digraph()
Edges = [edge()]
Deletes the edges in the list Edges from the digraph
G.
Types:
G = digraph()
V1 = V2 = vertex()
Deletes edges from the digraph G until there are no
paths from the vertex
V1 to the vertex V2.
A sketch of the procedure employed: Find an arbitrary
simple path
v[1], v[2], ..., 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.
Types:
G = digraph()
V = vertex()
Deletes the vertex V from the digraph G. Any
edges emanating from
V or incident
on V are also deleted.
del_vertices(G, Vertices) -> true
Types:
G = digraph()
Vertices = [vertex()]
Deletes the vertices in the list Vertices from the
digraph G.
Types:
G = digraph()
Deletes the digraph G. This call is important
because digraphs are implemented with Ets. There is
no garbage collection of Ets tables. The digraph
will, however, be deleted if the process that created the
digraph terminates.
edge(G, E) -> {E, V1, V2, Label} | false
Types:
G = digraph()
E = edge()
V1 = V2 = vertex()
Label = label()
Returns {E, V1, V2, Label} where
Label is the label
of the edge E emanating from V1 and
incident on V2
of the digraph G. If there is no edge E of the
digraph G, then false is returned.
Types:
G = digraph()
Edges = [edge()]
Returns a list of all edges of the digraph G, in
some unspecified order.
Types:
G = digraph()
V = vertex()
Edges = [edge()]
Returns a list of all edges emanating from or incident on V of the
digraph G, in some unspecified order.
get_cycle(G, V) -> Vertices | false
Types:
G = digraph()
V1 = V2 = vertex()
Vertices = [vertex()]
If there is a simple
cycle of length two or more through the vertex
V, then the cycle is returned as a list
[V, ..., V] of vertices, otherwise if there
is a loop through
V, then the loop is returned as a list [V]. If
there are no cycles through V, then false is
returned.
get_path/3 is used for finding a simple cycle
through V.
get_path(G, V1, V2) -> Vertices | false
Types:
G = digraph()
V1 = V2 = vertex()
Vertices = [vertex()]
Tries to find a simple
path from the vertex V1 to the vertex
V2 of the 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.
The digraph G is traversed in a depth-first manner,
and the first path found is returned.
get_short_cycle(G, V) -> Vertices | false
Types:
G = digraph()
V1 = V2 = vertex()
Vertices = [vertex()]
Tries to find an as short as possible simple cycle through the
vertex V of the digraph G. Returns the cycle
as a list [V, ..., V] of vertices, or
false if no simple cycle through V exists.
Note that a loop through
V is returned as the 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 = digraph()
V1 = V2 = vertex()
Vertices = [vertex()]
Tries to find an as short as possible simple path from the vertex
V1 to the vertex V2 of the 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.
The digraph G is traversed in a breadth-first
manner, and the first path found is returned.
Types:
G= digraph()
V = vertex()
Returns the in-degree of the vertex
V of the digraph G.
Types:
G = digraph()
V = vertex()
Edges = [edge()]
Returns a list of all edges incident on V of the
digraph G, in some unspecified order.
in_neighbours(G, V) -> Vertices
Types:
G = digraph()
V = vertex()
Vertices = [vertex()]
Returns a list of all in-neighbours of V
of the digraph G, in some unspecified order.
Types:
G = digraph()
InfoList = [{cyclicity, Cyclicity}, {memory, NoWords},
{protection, Protection}]
Cyclicity = cyclic | acyclic
Protection = protected | private
NoWords = integer() >= 0
Returns a list of {Tag, Value} pairs describing the
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 allocated to the ets tables.
{protection, Protection}, where Protection
is protected or private, according
to the options given to new.
Equivalent to new([]).
new(Type) -> digraph() | {error, Reason}
Types:
Type = [cyclic | acyclic | private | protected]
Reason = {unknown_type, term()}
Returns an empty
digraph with properties according to the options
in Type:
cyclic
acyclic
protected
private
If an unrecognized type option T is given, then
{error, {unknown_type, T}} is
returned.
Types:
G = digraph()
Returns the number of edges of the digraph G.
no_vertices(G) -> integer() >= 0
Types:
G = digraph()
Returns the number of vertices of the digraph G.
Types:
G = digraph()
V = vertex()
Returns the out-degree of the vertex
V of the digraph G.
Types:
G = digraph()
V = vertex()
Edges = [edge()]
Returns a list of all edges emanating from V of the
digraph G, in some unspecified order.
out_neighbours(G, V) -> Vertices
Types:
G = digraph()
V = vertex()
Vertices = [vertex()]
Returns a list of all out-neighbours of V
of the digraph G, in some unspecified order.
vertex(G, V) -> {V, Label} | false
Types:
G = digraph()
V = vertex()
Label = label()
Returns {V, Label} where Label is the
label of the vertex
V of the digraph G, or false if there
is no vertex V of the digraph G.
Types:
G = digraph()
Vertices = [vertex()]
Returns a list of all vertices of the digraph G, in
some unspecified order.