digraph

MODULE

digraph

MODULE SUMMARY

Directed Graphs

DESCRIPTION

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.

EXPORTS

new(Opts) -> graph()

Types:
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.
  

new() -> graph()

Equivalent to the call new([cyclic, protected]).

delete(G) -> true

Types:
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

Types:
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

Types:
G = graph()
V = vertex()
Data = term()

Returns {V, Data}, or false if the vertex V does not exist.

vertices(G) -> Vertices

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

Returns a list of all vertices in the graph G.

del_vertex(G, V) -> true

Types:
G = graph()
V = vertex()

Deletes the vertex V. The edges connected to vertex V are also deleted. Returns true.

del_vertices(G, Vertices) -> true

Types:
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}

Types:
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.
  
• Edge E otherwise.
  

del_edge(G, E) -> true

Types:
G = graph()
E = edge()

Deletes the edge E. Returns true.

del_edges(G, Edges) -> true

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

Deletes the edges in the list Edges. Returns true.

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

Types:
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.

edges(G) -> Edges

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

Returns all edges of the graph G as a list Edges.

out_neighbours(G, V) -> Vertices

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

Returns a list of the vertices to which the vertex V is connected.

in_neighbours(G, V) -> Vertices

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

Returns a list of vertices connected to V

out_edges(G, V) -> Edges

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

Returns the list of edges with starting points in vertex V.

in_edges(G, V) -> Edges

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

Returns the list of edges with ending point in vertex V.

edges(G, V) -> Edges

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

Returns the list of all edges, both to and from vertex V.

out_degree(G, V) -> int()

Types:
G = graph()
V = vertex()

Returns the number of edges with starting points in vertex V.

in_degree(G, V) -> int()

Types:
G= graph()
V = vertex()

Returns the number of edges with ending points in vertex V.

del_path(G, V1, V2) -> true

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

Deletes all paths from vertex V1 to vertex V2. Returns true.

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

Types:
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

Types:
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.

AUTHORS

Tony Rogvall - tony@erix.ericsson.se