Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
digraph(3)		   Erlang Module Definition		    digraph(3)

NAME
       digraph - Directed graphs.

DESCRIPTION
       This  module  provides a	version	of labeled directed graphs. 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  Er-
	   lang	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 se-
	   quence 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  La-
	      bel  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  onV  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  di-
	      graph  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 al-
		  located 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 op-
	      tions 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.8			    digraph(3)

NAME | DESCRIPTION | DATA TYPES | EXPORTS | SEE ALSO

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=digraph&sektion=3&manpath=FreeBSD+13.0-RELEASE+and+Ports>

home | help