src/work/alpar/attic/texi/flf-graph.texi
changeset 1174 5dccf1916ed8
equal deleted inserted replaced
-1:000000000000 0:04625ecd227f
       
     1 @node The Full Feature Graph Class
       
     2 @section The Full Feature Graph Class
       
     3 @cindex Full Feature Graph Class
       
     4 
       
     5 This section describes what an imaginary full feature graph class knows.
       
     6 The set of features provided by a real graph implementation is typically
       
     7 a subset of the features below.
       
     8 
       
     9 On the other hand, each graph algorithm requires the underlying graph
       
    10 structure to provide a certain (typically small) set of features in order
       
    11 to be able to run.
       
    12 
       
    13 @subsection Declaration
       
    14 
       
    15 @deftp {Class} {class Graph}
       
    16 @code{Graph} is the imaginary @emph{full feature graph class}.
       
    17 @code{G} denotes the instance of this class in the exaples below.
       
    18 @c Each node and edge has a user defined data sturcure
       
    19 @c @var{N} and @var{E} statically attached to it.
       
    20 @end deftp
       
    21 
       
    22 @subsection Types
       
    23 
       
    24 @c @deftp {Type} Graph::NodeType
       
    25 @c @deftpx {Type} Graph::EdgeType
       
    26 @c The type of the data stored statically for each node and edge.
       
    27 @c @end deftp
       
    28 
       
    29 @anchor{Graph-NodeIterator}
       
    30 @deftp {Type} Graph::NodeIt
       
    31 @c @deftpx {Type} Graph::NodeIterator
       
    32 These types points a node uniquely. The difference between the
       
    33 @code{NodeIt} and the @code{NodeIterator} is that @code{NodeIt}
       
    34 requires the graph structure itself for most of the operations.
       
    35 For examples using iterators you can go through all nodes as follows.
       
    36 @quotation
       
    37 @verbatim
       
    38 Graph G;
       
    39 int nodenum=0;
       
    40 for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum;
       
    41 @end verbatim
       
    42 @end quotation
       
    43 Using @code{NodeIt} the last line looks like this.
       
    44 @quotation
       
    45 @verbatim
       
    46 for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum;
       
    47 @end verbatim
       
    48 @end quotation
       
    49 or
       
    50 @quotation
       
    51 @verbatim
       
    52 MyGraph::NodeIt n;
       
    53 for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum;
       
    54 @end verbatim
       
    55 @end quotation
       
    56 @end deftp
       
    57 
       
    58 @deftp {Type} Graph::EdgeIt
       
    59 @deftpx {Type} Graph::InEdgeIt
       
    60 @deftpx {Type} Graph::OutEdgeIt
       
    61 @deftpx {Type} Graph::EachEdgeIt
       
    62 @c @deftpx {Type} Graph::BiEdgeIt
       
    63 @c @deftpx {Type} Graph::SymEdgeIt
       
    64 Each of these types points an edge uniquely. The difference between the
       
    65 @code{EdgeIt} and the
       
    66 @c @mref{Graph-NodeIterator,@code{EdgeIterator}}
       
    67 @mref{Graph-NodeIterator , EdgeIterator}
       
    68 series is that
       
    69 @code{EdgeIt} requires the graph structure itself for most of the
       
    70 operations.
       
    71 @end deftp
       
    72 
       
    73 @anchor{Graph-EdgeIterator}
       
    74 @c @deftp {Type} Graph::EdgeIterator
       
    75 @c @deftpx {Type} Graph::InEdgeIterator
       
    76 @c @deftpx {Type} Graph::OutEdgeIterator
       
    77 @c @deftpx {Type} Graph::BiEdgeIterator
       
    78 @c @deftpx {Type} Graph::SymEdgeIterator
       
    79 @c @deftpx {Type} Graph::EachEdgeIterator
       
    80 @c Each of these types points an edge uniquely. The difference between the
       
    81 @c @code{EdgeIt} and the @code{EdgeIterator} series is that
       
    82 @c @code{EdgeIt} requires the graph structure itself for most of the
       
    83 @c operations. 
       
    84 
       
    85 @c For the @code{EdgeIterator} types you can use operator @code{++}
       
    86 @c (both the prefix and the posfix one) to obtain the next edge.
       
    87 @c @end deftp
       
    88 
       
    89 @deftp {Type} Graph::NodeMap<typename T>
       
    90 @deftpx {Type} Graph::EdgeMap<typename T>
       
    91 There are the default property maps for the edges and the nodes.
       
    92 @end deftp
       
    93 
       
    94 @deftp {Type} Graph::DynNodeMap<typename T>
       
    95 @deftpx {Type} Graph::DynEdgeMap<typename T>
       
    96 There are the default @emph{dynamic} property maps for the edges and the nodes.
       
    97 @end deftp
       
    98 
       
    99 @subsection Member Functions
       
   100 
       
   101 @subsubsection Constructors
       
   102 
       
   103 @deftypefun { } Graph::Graph ()
       
   104 The default constructor.
       
   105 @end deftypefun
       
   106 
       
   107 @c @deftypefun { } Graph::Graph (Graph@tie{}&)
       
   108 @deftypefun { } Graph::Graph (Graph &)
       
   109 The copy constructor.
       
   110 @end deftypefun
       
   111 
       
   112 @subsubsection Graph Maintenence Operations
       
   113 
       
   114 @deftypefun NodeIt Graph::addNode ()
       
   115 Adds a new node to the graph and returns a @code{NodeIt} pointing to it.
       
   116 @end deftypefun
       
   117 
       
   118 @deftypefun EdgeIt Graph::addEdge (@w{const @mref{Graph-NodeIterator,NodeIt} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIt} @var{to}})
       
   119 Adds a new edge with tail @var{from} and head @var{to} to the graph
       
   120 and returns an @code{EdgeIt} pointing to it.
       
   121 @end deftypefun
       
   122 
       
   123 @deftypefun void Graph::delete (@w{const @mref{Graph-NodeIterator,NodeIt} @var{n}})
       
   124 Deletes the node @var{n}. It also deletes the adjacent edges.
       
   125 @end deftypefun
       
   126 
       
   127 @deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIt} @var{e}})
       
   128 Deletes the edge @var{n}.
       
   129 @end deftypefun
       
   130 
       
   131 @deftypefun void Graph::clear ()
       
   132 Deletes all edges and nodes from the graph.
       
   133 @end deftypefun
       
   134 
       
   135 @deftypefun int Graph::nodeNum ()
       
   136 Returns the number of the nodes in the graph.
       
   137 ??? Is it necessary???
       
   138 @end deftypefun
       
   139 
       
   140 @subsubsection NodeIt Operations
       
   141 
       
   142 @deftypefun NodeIt Graph::getFirst (NodeIt &@var{n}) const
       
   143 @deftypefunx NodeIt Graph::getNext (NodeIt @var{n}) const
       
   144 @deftypefunx {NodeIt &} Graph::next (NodeIt &@var{n})
       
   145 The nodes in the graph forms a list. @code{getFirst(n)} sets @var{n} to
       
   146 be the first node. @code{getNext(n)} gives back the subsequent
       
   147 node. @code{next(n)} is equivalent to @code{n=getNext(n)}, though it
       
   148 might be faster.  ??? What should be the return value ???
       
   149 @end deftypefun
       
   150 
       
   151 @deftypefun bool Graph::valid (NodeIt &@var{e})
       
   152 @c @deftypefunx bool NodeIt::valid ()
       
   153 These functions check if and NodeIt is valid or not.
       
   154 @c ??? Which one should be implemented ???
       
   155 @end deftypefun
       
   156 
       
   157 @subsubsection EdgeIt Operations
       
   158 
       
   159 @deftypefun EachEdgeIt Graph::getFirst (const EachEdgeIt & @var{e}) const
       
   160 @deftypefunx EachEdgeIt Graph::getNext (EachEdgeIt @var{n}) const
       
   161 @deftypefunx {EachEdgeIt &} Graph::next (EachEdgeIt &@var{n})
       
   162 With these functions you can go though all the edges of the graph.
       
   163 @c ??? What should be the return value ???
       
   164 @end deftypefun
       
   165 
       
   166 @deftypefun InEdgeIt &Graph::getFirst (InEdgeIt & @var{e}, const NodeIt @var{n})
       
   167 @deftypefunx OutEdgeIt &Graph::getFirst (OutEdgeIt & @var{e}, const NodeIt @var{n})
       
   168 @c @deftypefunx SymEdgeIt &Graph::getFirst (SymEdgeIt & @var{e}, const NodeIt @var{n})
       
   169 The edges leaving from
       
   170 or
       
   171 arriving at
       
   172 @c or adjacent with
       
   173 a node forms a
       
   174 list.  These functions give back the first elements of these
       
   175 lists. The exact behavior depends on the type of @var{e}.
       
   176 
       
   177 If @var{e} is an @code{InEdgeIt} or an @code{OutEdgeIt} then
       
   178 @code{getFirst} sets @var{e} to be the first incoming or outgoing edge
       
   179 of the node @var{n}, respectively.
       
   180 
       
   181 @c If @var{e} is a @code{SymEdgeIt} then
       
   182 @c @code{getFirst} sets @var{e} to be the first incoming if there exists one
       
   183 @c otherwise the first outgoing edge.
       
   184 
       
   185 If there are no such edges, @var{e} will be invalid.
       
   186 
       
   187 @end deftypefun
       
   188 
       
   189 @deftypefun InEdgeIt Graph::next (const InEdgeIt @var{e})
       
   190 @deftypefunx OutEdgeIt Graph::next (const OutEdgeIt @var{e})
       
   191 @deftypefunx SymEdgeIt Graph::next (const SymEdgeIt @var{e})
       
   192 These functions give back the edge that follows @var{e}
       
   193 @end deftypefun
       
   194 
       
   195 @deftypefun {InEdgeIt &} Graph::goNext (InEdgeIt &@var{e})
       
   196 @deftypefunx {OutEdgeIt &} Graph::goNext (OutEdgeIt &@var{e})
       
   197 @deftypefunx {SymEdgeIt &} Graph::goNext (SymEdgeIt &@var{e})
       
   198 @code{G.goNext(e)} is equivalent to @code{e=G.next(e)}, though it
       
   199 might be faster.
       
   200 ??? What should be the return value ???
       
   201 @end deftypefun
       
   202 
       
   203 @deftypefun bool Graph::valid (EdgeIt &@var{e})
       
   204 @deftypefunx bool EdgeIt::valid ()
       
   205 These functions check if and EdgeIt is valid or not.
       
   206 ??? Which one should be implemented ???
       
   207 @end deftypefun
       
   208 
       
   209 @deftypefun NodeIt Graph::tail (const EdgeIt @var{e})
       
   210 @deftypefunx NodeIt Graph::head (const EdgeIt @var{e})
       
   211 @deftypefunx NodeIt Graph::aNode (const InEdgeIt @var{e})
       
   212 @deftypefunx NodeIt Graph::aNode (const OutEdgeIt @var{e})
       
   213 @deftypefunx NodeIt Graph::aNode (const SymEdgeIt @var{e})
       
   214 @deftypefunx NodeIt Graph::bNode (const InEdgeIt @var{e})
       
   215 @deftypefunx NodeIt Graph::bNode (const OutEdgeIt @var{e})
       
   216 @deftypefunx NodeIt Graph::bNode (const SymEdgeIt @var{e})
       
   217 There queries give back the two endpoints of the edge @var{e}.  For a
       
   218 directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and
       
   219 its head, respectively. For an undirected @var{e}, they are two
       
   220 endpoints, but you should not rely on which end is which.
       
   221 
       
   222 @code{aNode(e)} is the node which @var{e} is bounded to, i.e. it is
       
   223 equal to @code{tail(e)} if @var{e} is an @code{OutEdgeIt} and
       
   224 @code{head(e)} if @var{e} is an @code{InEdgeIt}. If @var{e} is a
       
   225 @code{SymEdgeIt} and it or its first preceding edge was created by
       
   226 @code{getFirst(e,n)}, then @code{aNode(e)} is equal to @var{n}.
       
   227 
       
   228 @code{bNode(e)} is the other end of the edge.
       
   229 
       
   230 @deftypefun void Graph::setInvalid (EdgeIt &@var{e})
       
   231 @deftypefunx void Graph::setInvalid (EdgeIt &@var{e})
       
   232 These functions set the corresponding iterator to be invalid.
       
   233 @end deftypefun
       
   234 
       
   235 @c ???It is implemented in an other way now. (Member function <-> Graph global)???
       
   236 @end deftypefun
       
   237 
       
   238 
       
   239 
       
   240 @c @deftypevar int from
       
   241 @c  the tail of the created edge.
       
   242 @c @end deftypevar