This module implements directed graphs. A directed graph consists of a set of vertices (nodes) and a set of edges (connections). Both vertices and edges are identified with an Erlang term. It is possible to have multiple edges between vertices, and both vertices and edges may have user data attached.
Opts = [cyclic|acyclic|public|private|protected]
Returns an empty graph of the type Type
.
Type
is a list of type specifiers:
cyclic
Allows cyclic graphs.
acyclic
Does not allow cyclic graphs.
public
The graph may be read and modified by any process.
protected
Other processes can only read the graph.
private
The graph can be read and modified by the creating process.
Equivalent to the call new([cyclic, protected]).
G = graph()
Deletes the graph. This call is important because graphs are
implemented with ets
. There is no garbage collection of ets
tables.
The graph will, however, be deleted if the process that created the
graph terminates.
add_vertex(G, Vertex, Data) -> V
add_vertex(G, Vertex) -> V
add_vertex(G) -> V
G = graph()
Vertex = term()
Data = term()
V = vertex()
add_vertex/3
creates or modifies the vertex Vertex
with the associated data Data
.
Vertex
and Data
may be any Erlang
term. Returns vertex V
.
add_vertex/2 is equivalent to <c>add_vertex(G, Vertex, [])
.
add_vertex/1
adds a vertex with a generated name and the empty
list as data. Returns the new vertex V
.
vertex(G, V) -> {V,Data} | false
G = graph()
V = vertex()
Data = term()
Returns {V, Data}
, or false
if the vertex
V
does not exist.
G = graph()
Vertices = [vertex()]
Returns a list of all vertices in the graph G
.
G = graph()
V = vertex()
Deletes the vertex V
. The edges connected to vertex V
are also deleted. Returns true
.
del_vertices(G, Vertices) -> true
G = graph()
Vertices = [vertex()]
Deletes the vertices in the list Vertices
.
Returns true
.
add_edge(G, Edge, V1, V2, Data) -> E | {error, Reason}
add_edge(G, V1, V2, Data) -> E | {error, Reason}
add_edge(G, V1, V2) -> E | {error, Reason}
G = graph()
Edge = term()
V1 = V2 = vertex()
Data = term()
E = edge()
Reason = {bad_edge, Path} | {bad_vertex, V}
Path = [vertex()]
add_edge/5
adds a directed edge with the identifier
Edge
,
to the start vertex V1
and end vertex V2
.
It also attaches Data
to the edge Edge
. Edge
and
Data
may be any Erlang terms.
add_edge/4
works as add_edge/5
, but a unique name is
generated for the edge.
add_edge/3
is equivalent to add_edge(G,V1,V2,[])
.
Returns:
{error, {bad_edge, Path}}
if adding the edge
will create a cycle in an acyclic graph.
{error, {bad_vertex, V}}
if either end point does
not exists in the graph.
E
otherwise.
G = graph()
E = edge()
Deletes the edge E
.
Returns true
.
G = graph()
Edges = [edge()]
Deletes the edges in the list Edges
. Returns true
.
edge(G, E) -> {E, V1, V2, Data} | false
G = graph()
E = edge()
V1 = V2 = vertex()
Data = term()
Returns {E, V1, V2, Data}
, where V1
is the start
vertex and V2
is the end vertex. edge/2
returns false if the
edge E
does not exist.
G = graph()
Edges = [edge()]
Returns all edges of the graph G
as a list Edges
.
out_neighbours(G, V) -> Vertices
G = graph()
V = vertex()
Vertices = [vertex()]
Returns a list of the vertices to which the vertex V
is
connected.
in_neighbours(G, V) -> Vertices
G = graph()
V = vertex()
Vertices = [vertex()]
Returns a list of vertices connected to V
G = graph()
V = vertex()
Edges = [edge()]
Returns the list of edges with starting points in vertex V
.
G = graph()
V = vertex()
Edges = [edge()]
Returns the list of edges with ending point in vertex V
.
G = graph()
V = vertex()
Edges = [edge()]
Returns the list of all edges, both to and from vertex V
.
G = graph()
V = vertex()
Returns the number of edges with starting points in vertex V
.
G= graph()
V = vertex()
Returns the number of edges with ending points in vertex V
.
G = graph()
V1 = V2 = vertex()
Deletes all paths from vertex V1
to vertex V2
.
Returns true
.
get_path(G, V1, V2) -> Vertices | false
G = graph()
V1 = V2 = vertex()
Vertices = [vertex()]
Finds a path from vertex V1
to vertex V2
. Returns the
path as the list [V1, ..., V2]
, or false
if no path
exists.
get_cycle(G, V) -> Vertices | false
G = graph()
V1 = V2 = vertex()
Vertices = [vertex()]
Finds a cycle through vertex V
. It first attempts to find
cycles longer than one, and then a cycle of one. Returns the
cycle as [V, ..., V]
for lengths greater then one,
[V]
for lengths of one, and false
if no cycle is found.