digraph - Directed graphs.
Please see following description for synopsis
digraph(3) Erlang Module Definition digraph(3) NAME digraph - Directed graphs. DESCRIPTION This module provides a version of labeled directed graphs ("digraphs"). The digraphs managed by this module are stored in ETS tables. That implies the following: * Only the process that created the digraph is allowed to update it. * Digraphs will not be garbage collected. The ETS tables used for a digraph will only be deleted when delete/1 is called or the process that created the digraph terminates. * A digraph is a mutable data structure. 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. * Digraphs can be annotated with more information. Such information 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 Erlang 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[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 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[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 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, V1, V2) -> edge() | {error, add_edge_err_rsn()} add_edge(G, V1, V2, Label) -> edge() | {error, add_edge_err_rsn()} add_edge(G, E, V1, V2, Label) -> edge() | {error, add_edge_err_rsn()} Types: G = graph() E = edge() V1 = V2 = vertex() Label = label() add_edge_err_rsn() = {bad_edge, Path :: [vertex()]} | {bad_vertex, V :: vertex()} add_edge/5 creates (or modifies) edge E of 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. The created edge is rep- resented by term ['$e' | N], where N is an integer >= 0. add_edge(G, V1, V2) is equivalent to add_edge(G, V1, V2, []). If the edge would create a cycle in an acyclic digraph, {error, {bad_edge, Path}} is returned. If G already has an edge with 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. add_vertex(G) -> vertex() add_vertex(G, V) -> vertex() add_vertex(G, V, Label) -> vertex() 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(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. 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[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. 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 on V 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 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 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 allocated 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 options 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. SEE ALSO digraph_utils(3), ets(3) Ericsson AB stdlib 3.17 digraph(3)