File: digraph.html

package info (click to toggle)
erlang-doc-html 1%3A11.b.2-1
links: PTS
area: main
in suites: etch, etch-m68k
size: 23,284 kB
ctags: 10,724
sloc: erlang: 505; ansic: 323; makefile: 62; perl: 61; sh: 45
file content (824 lines) | stat: -rw-r--r-- 22,967 bytes
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<!-- This document was generated using DocBuilder 3.3.3 -->
<HTML>
<HEAD>
  <TITLE>digraph</TITLE>
  <SCRIPT type="text/javascript" src="../../../../doc/erlresolvelinks.js">
</SCRIPT>
  <STYLE TYPE="text/css">
<!--
    .REFBODY     { margin-left: 13mm }
    .REFTYPES    { margin-left: 8mm }
-->
  </STYLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#FF00FF"
      ALINK="#FF0000">
<!-- refpage -->
<CENTER>
<A HREF="http://www.erlang.se">
  <IMG BORDER=0 ALT="[Ericsson AB]" SRC="min_head.gif">
</A>
<H1>digraph</H1>
</CENTER>

<H3>MODULE</H3>
<DIV CLASS=REFBODY>
digraph
</DIV>

<H3>MODULE SUMMARY</H3>
<DIV CLASS=REFBODY>
Directed Graphs
</DIV>

<H3>DESCRIPTION</H3>
<DIV CLASS=REFBODY>

<P>The <CODE>digraph</CODE> 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.




<P>A <A NAME="digraph"><!-- Empty --></A><STRONG>directed graph</STRONG> (or just
&#34;digraph&#34;) is a pair (V,E) of a finite set V of <A NAME="vertex"><!-- Empty --></A><STRONG>vertices</STRONG> and a finite set E of <A NAME="edge"><!-- Empty --></A><STRONG>directed edges</STRONG> (or just &#34;edges&#34;). The set of
edges E is a subset of Vנ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 <A NAME="empty_digraph"><!-- Empty --></A> <STRONG>empty digraph</STRONG>. Both vertices and
edges are represented by unique Erlang terms.


<P>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
<STRONG>labeled digraph</STRONG>, and the information attached to a
vertex or an edge is called a <A NAME="label"><!-- Empty --></A><STRONG>label</STRONG>.
Labels are Erlang terms.


<P>An edge e=(v,w) is said to <A NAME="emanate"><!-- Empty --></A><STRONG>emanate</STRONG> from vertex v and to be <A NAME="incident"><!-- Empty --></A><STRONG>incident</STRONG> on vertex w. The <A NAME="out_degree"><!-- Empty --></A><STRONG>out-degree</STRONG> of a vertex is the number of
edges emanating from that vertex. The <A NAME="in_degree"><!-- Empty --></A><STRONG>in-degree</STRONG> 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 is said to be an <A NAME="out_neighbour"><!-- Empty --></A><STRONG>out-neighbour</STRONG> of v, and v is said to
be an <A NAME="in_neighbour"><!-- Empty --></A><STRONG>in-neighbour</STRONG> of w. A
<A NAME="path"><!-- Empty --></A><STRONG>path</STRONG> 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&#60;=i&#60;k. The <A NAME="length"><!-- Empty --></A><STRONG>length</STRONG> of the path P is k-1. P is <A NAME="simple_path"><!-- Empty --></A><STRONG>simple</STRONG> if all vertices are distinct,
except that the first and the last vertices may be the same. P
is a <A NAME="cycle"><!-- Empty --></A><STRONG>cycle</STRONG> if the length of P is not
zero and v[1] = v[k]. A <A NAME="loop"><!-- Empty --></A><STRONG>loop</STRONG> is a
cycle of length one. A <A NAME="simple_cycle"><!-- Empty --></A><STRONG>simple
cycle</STRONG> is a path that is both a cycle and simple. An <A NAME="acyclic_digraph"><!-- Empty --></A><STRONG>acyclic digraph</STRONG> is a digraph that
has no cycles.


</DIV>

<H3>EXPORTS</H3>

<P><A NAME="add_edge/5"><STRONG><CODE>add_edge(G, E, V1, V2, Label) -&#62; edge() | {error, Reason}</CODE></STRONG></A><BR>
<A NAME="add_edge/4"><STRONG><CODE>add_edge(G, V1, V2, Label) -&#62; edge() | {error, Reason}</CODE></STRONG></A><BR>
<A NAME="add_edge/3"><STRONG><CODE>add_edge(G, V1, V2) -&#62; edge() | {error, Reason}</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>E = edge()</CODE></STRONG><BR>
<STRONG><CODE>V1 = V2 = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Label = label()</CODE></STRONG><BR>
<STRONG><CODE>Reason = {bad_edge, Path} | {bad_vertex, V}</CODE></STRONG><BR>
<STRONG><CODE>Path = [vertex()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P><CODE>add_edge/5</CODE> creates (or modifies) the edge <CODE>E</CODE>
         of the digraph <CODE>G</CODE>, using <CODE>Label</CODE> as the (new)
         <A HREF="#label">label</A> of the edge. The
         edge is <A HREF="#emanate">emanating</A> from
         <CODE>V1</CODE> and <A HREF="#incident">incident</A>
         on <CODE>V2</CODE>. Returns <CODE>E</CODE>.

        
<P><CODE>add_edge(G,V1,V2,Label)</CODE> is
         equivalent to
         <CODE>add_edge(G,E,V1,V2,Label)</CODE>,
         where <CODE>E</CODE> is a created edge. Tuples on the form
         <CODE>['$e'|N]</CODE>, where N is an
         integer&#62;=1, are used for representing the
         created edges.

        
<P><CODE>add_edge(G,V1,V2)</CODE> is equivalent to
         <CODE>add_edge(G,V1,V2,[])</CODE>.

        
<P>If the edge would create a cycle in an <A HREF="#acyclic_digraph">acyclic digraph</A>, then
         <CODE>{error,{bad_edge,Path}}</CODE> is returned. If
         either of <CODE>V1</CODE> or <CODE>V2</CODE> is not a vertex of the
         digraph <CODE>G</CODE>, then
         <CODE>{error,{bad_vertex,</CODE>V<CODE>}}</CODE> is
         returned, V=<CODE>V1</CODE> or
         V=<CODE>V2</CODE>.


</DIV>

<P><A NAME="add_vertex/3"><STRONG><CODE>add_vertex(G, V, Label) -&#62; vertex()</CODE></STRONG></A><BR>
<A NAME="add_vertex/2"><STRONG><CODE>add_vertex(G, V) -&#62; vertex()</CODE></STRONG></A><BR>
<A NAME="add_vertex/1"><STRONG><CODE>add_vertex(G) -&#62; vertex()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Label = label()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P><CODE>add_vertex/3</CODE> creates (or modifies) the vertex <CODE>V</CODE>
         of the digraph <CODE>G</CODE>, using <CODE>Label</CODE> as the (new)
         <A HREF="#label">label</A> of the
         vertex. Returns <CODE>V</CODE>.

        
<P><CODE>add_vertex(G,V)</CODE> is equivalent to
         <CODE>add_vertex(G,V,[])</CODE>.

        
<P><CODE>add_vertex/1</CODE> creates a vertex using the empty list
         as label, and returns the created vertex. Tuples on the form
         <CODE>['$v'|N]</CODE>, where N is an
         integer&#62;=1, are used for representing the
         created vertices.


</DIV>

<P><A NAME="del_edge/2"><STRONG><CODE>del_edge(G, E) -&#62; true</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>E = edge()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Deletes the edge <CODE>E</CODE> from the digraph <CODE>G</CODE>.


</DIV>

<P><A NAME="del_edges/2"><STRONG><CODE>del_edges(G, Edges) -&#62; true</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Edges = [edge()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Deletes the edges in the list <CODE>Edges</CODE> from the digraph
         <CODE>G</CODE>.


</DIV>

<P><A NAME="del_path/3"><STRONG><CODE>del_path(G, V1, V2) -&#62; true</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V1 = V2 = vertex()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Deletes edges from the digraph <CODE>G</CODE> until there are no
         <A HREF="#path">paths</A> from the vertex
         <CODE>V1</CODE> to the vertex <CODE>V2</CODE>.

        
<P>A sketch of the procedure employed: Find an arbitrary
         <A HREF="#simple_path">simple path</A>
         v[1],v[2],...,v[k] from <CODE>V1</CODE> to
         <CODE>V2</CODE> in <CODE>G</CODE>. Remove all edges of <CODE>G</CODE> <A HREF="#emanate">emanating</A> from v[i] and <A HREF="#incident">incident</A> to v[i+1] for
         1&#60;=i&#60;k (including multiple
         edges). Repeat until there is no path between <CODE>V1</CODE> and
         <CODE>V2</CODE>.


</DIV>

<P><A NAME="del_vertex/2"><STRONG><CODE>del_vertex(G, V) -&#62; true</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V = vertex()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Deletes the vertex <CODE>V</CODE> from the digraph <CODE>G</CODE>. Any
         edges <A HREF="#emanate">emanating</A> from
         <CODE>V</CODE> or <A HREF="#incident">incident</A>
         on <CODE>V</CODE> are also deleted.


</DIV>

<P><A NAME="del_vertices/2"><STRONG><CODE>del_vertices(G, Vertices) -&#62; true</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Deletes the vertices in the list <CODE>Vertices</CODE> from the
         digraph <CODE>G</CODE>.


</DIV>

<P><A NAME="delete/1"><STRONG><CODE>delete(G) -&#62; true</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Deletes the digraph <CODE>G</CODE>. This call is important
         because digraphs are implemented with <CODE>Ets</CODE>. There is
         no garbage collection of <CODE>Ets</CODE> tables. The digraph
         will, however, be deleted if the process that created the
         digraph terminates.


</DIV>

<P><A NAME="edge/2"><STRONG><CODE>edge(G, E) -&#62; {E, V1, V2, Label} | false</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>E = edge()</CODE></STRONG><BR>
<STRONG><CODE>V1 = V2 = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Label = label()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>{E,V1,V2,Label}</CODE> where
         <CODE>Label</CODE> is the <A HREF="#label">label</A>
         of the edge <CODE>E</CODE> <A HREF="#emanate">emanating</A> from <CODE>V1</CODE> and
         <A HREF="#incident">incident</A> on <CODE>V2</CODE>
         of the digraph <CODE>G</CODE>. If there is no edge <CODE>E</CODE> of the
         digraph <CODE>G</CODE>, then <CODE>false</CODE> is returned.


</DIV>

<P><A NAME="edges/1"><STRONG><CODE>edges(G) -&#62; Edges</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Edges = [edge()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a list of all edges of the digraph <CODE>G</CODE>, in
         some unspecified order.


</DIV>

<P><A NAME="edges/2"><STRONG><CODE>edges(G, V) -&#62; Edges</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Edges = [edge()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a list of all edges <A HREF="#emanate">emanating</A> from or <A HREF="#incident">incident</A> on <CODE>V</CODE> of the
         digraph <CODE>G</CODE>, in some unspecified order.


</DIV>

<P><A NAME="get_cycle/2"><STRONG><CODE>get_cycle(G, V) -&#62; Vertices | false</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V1 = V2 = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>If there is a <A HREF="#simple_cycle">simple
         cycle</A> of length two or more through the vertex
         <CODE>V</CODE>, then the cycle is returned as a list
         <CODE>[V,...,V]</CODE> of vertices, otherwise if there
         is a <A HREF="#loop">loop</A> through
         <CODE>V</CODE>, then the loop is returned as a list <CODE>[V]</CODE>. If
         there are no cycles through <CODE>V</CODE>, then <CODE>false</CODE> is
         returned.

        
<P><CODE>get_path/3</CODE> is used for finding a simple cycle
         through <CODE>V</CODE>.


</DIV>

<P><A NAME="get_path/3"><STRONG><CODE>get_path(G, V1, V2) -&#62; Vertices | false</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V1 = V2 = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Tries to find a <A HREF="#simple_path">simple
         path</A> from the vertex <CODE>V1</CODE> to the vertex
         <CODE>V2</CODE> of the digraph <CODE>G</CODE>. Returns the path as a
         list <CODE>[V1,...,V2]</CODE> of vertices, or
         <CODE>false</CODE> if no simple path from <CODE>V1</CODE> to <CODE>V2</CODE>
         of length one or more exists.

        
<P>The digraph <CODE>G</CODE> is traversed in a depth-first manner,
         and the first path found is returned.


</DIV>

<P><A NAME="get_short_cycle/2"><STRONG><CODE>get_short_cycle(G, V) -&#62; Vertices | false</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V1 = V2 = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Tries to find an as short as possible <A HREF="#simple_cycle">simple cycle</A> through the
         vertex <CODE>V</CODE> of the digraph <CODE>G</CODE>. Returns the cycle
         as a list <CODE>[V,...,V]</CODE> of vertices, or
         <CODE>false</CODE> if no simple cycle through <CODE>V</CODE> exists.
         Note that a <A HREF="#loop">loop</A> through
         <CODE>V</CODE> is returned as the list <CODE>[V,V]</CODE>.

        
<P><CODE>get_short_path/3</CODE> is used for finding a simple cycle
         through <CODE>V</CODE>.


</DIV>

<P><A NAME="get_short_path/3"><STRONG><CODE>get_short_path(G, V1, V2) -&#62; Vertices | false</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V1 = V2 = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Tries to find an as short as possible <A HREF="#simple_path">simple path</A> from the vertex
         <CODE>V1</CODE> to the vertex <CODE>V2</CODE> of the digraph <CODE>G</CODE>.
         Returns the path as a list <CODE>[V1,...,V2]</CODE> of
         vertices, or <CODE>false</CODE> if no simple path from <CODE>V1</CODE>
         to <CODE>V2</CODE> of length one or more exists.

        
<P>The digraph <CODE>G</CODE> is traversed in a breadth-first
         manner, and the first path found is returned.


</DIV>

<P><A NAME="in_degree/2"><STRONG><CODE>in_degree(G, V) -&#62; integer()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G= digraph()</CODE></STRONG><BR>
<STRONG><CODE>V = vertex()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the <A HREF="#in_degree">in-degree</A> of the vertex
         <CODE>V</CODE> of the digraph <CODE>G</CODE>.


</DIV>

<P><A NAME="in_edges/2"><STRONG><CODE>in_edges(G, V) -&#62; Edges</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Edges = [edge()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a list of all edges <A HREF="#incident">incident</A> on <CODE>V</CODE> of the
         digraph <CODE>G</CODE>, in some unspecified order.


</DIV>

<P><A NAME="in_neighbours/2"><STRONG><CODE>in_neighbours(G, V) -&#62; Vertices</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a list of all <A HREF="#in_neighbour">in-neighbours</A> of <CODE>V</CODE>
         of the digraph <CODE>G</CODE>, in some unspecified order.


</DIV>

<P><A NAME="info/1"><STRONG><CODE>info(G) -&#62; InfoList</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>InfoList = [{cyclicity, Cyclicity}, {memory, NoWords},
         {protection, Protection}]</CODE></STRONG><BR>
<STRONG><CODE>Cyclicity = cyclic | acyclic</CODE></STRONG><BR>
<STRONG><CODE>Protection = protected | private</CODE></STRONG><BR>
<STRONG><CODE>NoWords = integer() &#62;= 0</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a list of <CODE>{Tag, Value}</CODE> pairs describing the
         digraph <CODE>G</CODE>. The following pairs are returned:

        
<P>
<UL>

<LI>
<CODE>{cyclicity, Cyclicity}</CODE>, where <CODE>Cyclicity</CODE>
         is <CODE>cyclic</CODE> or <CODE>acyclic</CODE>, according to the
         options given to <CODE>new</CODE>.
         <BR>

</LI>


<LI>
<CODE>{memory, NoWords}</CODE>, where <CODE>NoWords</CODE> is 
         the number of words allocated to the <CODE>ets</CODE> tables.
         <BR>

</LI>


<LI>
<CODE>{protection, Protection}</CODE>, where <CODE>Protection</CODE>
         is <CODE>protected</CODE> or <CODE>private</CODE>, according
         to the options given to <CODE>new</CODE>.
        <BR>

</LI>


</UL>

</DIV>

<P><A NAME="new/0"><STRONG><CODE>new() -&#62; digraph()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY>

<P>Equivalent to <CODE>new([])</CODE>.


</DIV>

<P><A NAME="new/1"><STRONG><CODE>new(Type) -&#62; digraph() | {error, Reason}</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Type = [cyclic | acyclic | private | protected]</CODE></STRONG><BR>
<STRONG><CODE>Reason = {unknown_type, term()}</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns an <A HREF="#empty_digraph">empty
         digraph</A> with properties according to the options
         in <CODE>Type</CODE>:
        
<P>
<DL>

<DT>
<CODE>cyclic</CODE>
         
</DT>

<DD>
Allow <A HREF="#cycle">cycles</A> in the
         digraph (default).
         
</DD>

<DT>
<CODE>acyclic</CODE>
         
</DT>

<DD>
The digraph is to be kept <A HREF="#acyclic_digraph">acyclic</A>.
         
</DD>

<DT>
<CODE>protected</CODE>
         
</DT>

<DD>
Other processes can read the digraph (default).
         
</DD>

<DT>
<CODE>private</CODE>
         
</DT>

<DD>
The digraph can be read and modified by the creating
         process only.
        
</DD>

</DL>

<P>If an unrecognized type option T is given, then
         <CODE>{error,{unknown_type,</CODE>T<CODE>}}</CODE> is
         returned.


</DIV>

<P><A NAME="no_edges/1"><STRONG><CODE>no_edges(G) -&#62; integer() &#62;= 0</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the number of edges of the digraph <CODE>G</CODE>.


</DIV>

<P><A NAME="no_vertices/1"><STRONG><CODE>no_vertices(G) -&#62; integer() &#62;= 0</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the number of vertices of the digraph <CODE>G</CODE>.


</DIV>

<P><A NAME="out_degree/2"><STRONG><CODE>out_degree(G, V) -&#62; integer()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V = vertex()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the <A HREF="#out_degree">out-degree</A> of the vertex
         <CODE>V</CODE> of the digraph <CODE>G</CODE>.


</DIV>

<P><A NAME="out_edges/2"><STRONG><CODE>out_edges(G, V) -&#62; Edges</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Edges = [edge()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a list of all edges <A HREF="#emanate">emanating</A> from <CODE>V</CODE> of the
         digraph <CODE>G</CODE>, in some unspecified order.


</DIV>

<P><A NAME="out_neighbours/2"><STRONG><CODE>out_neighbours(G, V) -&#62; Vertices</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a list of all <A HREF="#out_neighbour">out-neighbours</A> of <CODE>V</CODE>
         of the digraph <CODE>G</CODE>, in some unspecified order.


</DIV>

<P><A NAME="vertex/2"><STRONG><CODE>vertex(G, V) -&#62; {V, Label} | false</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>V = vertex()</CODE></STRONG><BR>
<STRONG><CODE>Label = label()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>{V,Label}</CODE> where <CODE>Label</CODE> is the
         <A HREF="#label">label</A> of the vertex
         <CODE>V</CODE> of the digraph <CODE>G</CODE>, or <CODE>false</CODE> if there
         is no vertex <CODE>V</CODE> of the digraph <CODE>G</CODE>.


</DIV>

<P><A NAME="vertices/1"><STRONG><CODE>vertices(G) -&#62; Vertices</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>G = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a list of all vertices of the digraph <CODE>G</CODE>, in
         some unspecified order.


</DIV>

<H3>See Also</H3>
<DIV CLASS=REFBODY>

<P><A HREF="digraph_utils.html">digraph_utils(3)</A>, 
<A HREF="ets.html">ets(3)</A>


</DIV>

<H3>AUTHORS</H3>
<DIV CLASS=REFBODY>
Tony Rogvall - support@erlang.ericsson.se<BR>

</DIV>
<CENTER>
<HR>
<SMALL>stdlib 1.14.2<BR>
Copyright &copy; 1991-2006
<A HREF="http://www.erlang.se">Ericsson AB</A><BR>
</SMALL>
</CENTER>
</BODY>
</HTML>