Unix/Linux Go Back    


Linux 2.6 - man page for digraph (linux section 3erl)

Linux & Unix Commands - Search Man Pages
Man Page or Keyword Search:   man
Select Man Page Set:       apropos Keyword Search (sections above)


digraph(3erl)			     Erlang Module Definition			    digraph(3erl)

NAME
       digraph - Directed Graphs

DESCRIPTION
       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 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.

EXPORTS
       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. 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 ALSO
       digraph_utils(3erl) , ets(3erl)

Ericsson AB				  stdlib 1.17.3 			    digraph(3erl)
Unix & Linux Commands & Man Pages : ©2000 - 2018 Unix and Linux Forums


All times are GMT -4. The time now is 02:03 AM.