Linux & Unix Commands - Search Man Pages

Select Section of Man Page:

Select Man Page Repository:

digraph(3erl) Erlang Module Definition digraph(3erl)NAMEdigraph - Directed GraphsDESCRIPTIONThe 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 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 repre- sented 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 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 dis- tinct, 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.EXPORTSadd_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. The created edge is represented by the 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 , 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 cre- ated vertex. The created vertex is represented by the term ['$v' | N] , where N is an integer >= 0. del_edge(G, E) -> true Types G = digraph() E = edge() Deletes the edge E from the digraph G . del_edges(G, Edges) -> true Types G = digraph() Edges = [edge()] Deletes the edges in the list Edges from the digraph G . del_path(G, V1, V2) -> true 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 . del_vertex(G, V) -> true 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 . delete(G) -> true 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. edges(G) -> Edges Types G = digraph() Edges = [edge()] Returns a list of all edges of the digraph G , in some unspecified order. edges(G, V) -> Edges 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. in_degree(G, V) -> integer() Types G= digraph() V = vertex() Returns the in-degree of the vertex V of the digraph G . in_edges(G, V) -> Edges 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. info(G) -> InfoList Types G = digraph() InfoList = [{cyclicity, Cyclicity}, {memory, NoWords}, {protection, Protec- tion}] 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 . new() -> digraph() Equivalent to new([]) . new(Type) -> digraph() Types Type = [cyclic | acyclic | private | protected] Returns an empty digraph with properties according to the options in Type : cyclic : Allow 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 given or Type is not a proper list, there will be a badarg exception. no_edges(G) -> integer() >= 0 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 . out_degree(G, V) -> integer() Types G = digraph() V = vertex() Returns the out-degree of the vertex V of the digraph G . out_edges(G, V) -> Edges 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 . vertices(G) -> Vertices Types G = digraph() Vertices = [vertex()] Returns a list of all vertices of the digraph G , in some unspecified order.SEE ALSOdigraph_utils(3erl) , ets(3erl)Ericsson ABstdlib 1.17.3 digraph(3erl)

All times are GMT -4. The time now is 01:53 AM.