1.1 --- a/src/work/alpar/attic/texi/flf-graph.texi Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,242 +0,0 @@
1.4 -@node The Full Feature Graph Class
1.5 -@section The Full Feature Graph Class
1.6 -@cindex Full Feature Graph Class
1.7 -
1.8 -This section describes what an imaginary full feature graph class knows.
1.9 -The set of features provided by a real graph implementation is typically
1.10 -a subset of the features below.
1.11 -
1.12 -On the other hand, each graph algorithm requires the underlying graph
1.13 -structure to provide a certain (typically small) set of features in order
1.14 -to be able to run.
1.15 -
1.16 -@subsection Declaration
1.17 -
1.18 -@deftp {Class} {class Graph}
1.19 -@code{Graph} is the imaginary @emph{full feature graph class}.
1.20 -@code{G} denotes the instance of this class in the exaples below.
1.21 -@c Each node and edge has a user defined data sturcure
1.22 -@c @var{N} and @var{E} statically attached to it.
1.23 -@end deftp
1.24 -
1.25 -@subsection Types
1.26 -
1.27 -@c @deftp {Type} Graph::NodeType
1.28 -@c @deftpx {Type} Graph::EdgeType
1.29 -@c The type of the data stored statically for each node and edge.
1.30 -@c @end deftp
1.31 -
1.32 -@anchor{Graph-NodeIterator}
1.33 -@deftp {Type} Graph::NodeIt
1.34 -@c @deftpx {Type} Graph::NodeIterator
1.35 -These types points a node uniquely. The difference between the
1.36 -@code{NodeIt} and the @code{NodeIterator} is that @code{NodeIt}
1.37 -requires the graph structure itself for most of the operations.
1.38 -For examples using iterators you can go through all nodes as follows.
1.39 -@quotation
1.40 -@verbatim
1.41 -Graph G;
1.42 -int nodenum=0;
1.43 -for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum;
1.44 -@end verbatim
1.45 -@end quotation
1.46 -Using @code{NodeIt} the last line looks like this.
1.47 -@quotation
1.48 -@verbatim
1.49 -for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum;
1.50 -@end verbatim
1.51 -@end quotation
1.52 -or
1.53 -@quotation
1.54 -@verbatim
1.55 -MyGraph::NodeIt n;
1.56 -for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum;
1.57 -@end verbatim
1.58 -@end quotation
1.59 -@end deftp
1.60 -
1.61 -@deftp {Type} Graph::EdgeIt
1.62 -@deftpx {Type} Graph::InEdgeIt
1.63 -@deftpx {Type} Graph::OutEdgeIt
1.64 -@deftpx {Type} Graph::EachEdgeIt
1.65 -@c @deftpx {Type} Graph::BiEdgeIt
1.66 -@c @deftpx {Type} Graph::SymEdgeIt
1.67 -Each of these types points an edge uniquely. The difference between the
1.68 -@code{EdgeIt} and the
1.69 -@c @mref{Graph-NodeIterator,@code{EdgeIterator}}
1.70 -@mref{Graph-NodeIterator , EdgeIterator}
1.71 -series is that
1.72 -@code{EdgeIt} requires the graph structure itself for most of the
1.73 -operations.
1.74 -@end deftp
1.75 -
1.76 -@anchor{Graph-EdgeIterator}
1.77 -@c @deftp {Type} Graph::EdgeIterator
1.78 -@c @deftpx {Type} Graph::InEdgeIterator
1.79 -@c @deftpx {Type} Graph::OutEdgeIterator
1.80 -@c @deftpx {Type} Graph::BiEdgeIterator
1.81 -@c @deftpx {Type} Graph::SymEdgeIterator
1.82 -@c @deftpx {Type} Graph::EachEdgeIterator
1.83 -@c Each of these types points an edge uniquely. The difference between the
1.84 -@c @code{EdgeIt} and the @code{EdgeIterator} series is that
1.85 -@c @code{EdgeIt} requires the graph structure itself for most of the
1.86 -@c operations.
1.87 -
1.88 -@c For the @code{EdgeIterator} types you can use operator @code{++}
1.89 -@c (both the prefix and the posfix one) to obtain the next edge.
1.90 -@c @end deftp
1.91 -
1.92 -@deftp {Type} Graph::NodeMap<typename T>
1.93 -@deftpx {Type} Graph::EdgeMap<typename T>
1.94 -There are the default property maps for the edges and the nodes.
1.95 -@end deftp
1.96 -
1.97 -@deftp {Type} Graph::DynNodeMap<typename T>
1.98 -@deftpx {Type} Graph::DynEdgeMap<typename T>
1.99 -There are the default @emph{dynamic} property maps for the edges and the nodes.
1.100 -@end deftp
1.101 -
1.102 -@subsection Member Functions
1.103 -
1.104 -@subsubsection Constructors
1.105 -
1.106 -@deftypefun { } Graph::Graph ()
1.107 -The default constructor.
1.108 -@end deftypefun
1.109 -
1.110 -@c @deftypefun { } Graph::Graph (Graph@tie{}&)
1.111 -@deftypefun { } Graph::Graph (Graph &)
1.112 -The copy constructor.
1.113 -@end deftypefun
1.114 -
1.115 -@subsubsection Graph Maintenence Operations
1.116 -
1.117 -@deftypefun NodeIt Graph::addNode ()
1.118 -Adds a new node to the graph and returns a @code{NodeIt} pointing to it.
1.119 -@end deftypefun
1.120 -
1.121 -@deftypefun EdgeIt Graph::addEdge (@w{const @mref{Graph-NodeIterator,NodeIt} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIt} @var{to}})
1.122 -Adds a new edge with tail @var{from} and head @var{to} to the graph
1.123 -and returns an @code{EdgeIt} pointing to it.
1.124 -@end deftypefun
1.125 -
1.126 -@deftypefun void Graph::delete (@w{const @mref{Graph-NodeIterator,NodeIt} @var{n}})
1.127 -Deletes the node @var{n}. It also deletes the adjacent edges.
1.128 -@end deftypefun
1.129 -
1.130 -@deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIt} @var{e}})
1.131 -Deletes the edge @var{n}.
1.132 -@end deftypefun
1.133 -
1.134 -@deftypefun void Graph::clear ()
1.135 -Deletes all edges and nodes from the graph.
1.136 -@end deftypefun
1.137 -
1.138 -@deftypefun int Graph::nodeNum ()
1.139 -Returns the number of the nodes in the graph.
1.140 -??? Is it necessary???
1.141 -@end deftypefun
1.142 -
1.143 -@subsubsection NodeIt Operations
1.144 -
1.145 -@deftypefun NodeIt Graph::getFirst (NodeIt &@var{n}) const
1.146 -@deftypefunx NodeIt Graph::getNext (NodeIt @var{n}) const
1.147 -@deftypefunx {NodeIt &} Graph::next (NodeIt &@var{n})
1.148 -The nodes in the graph forms a list. @code{getFirst(n)} sets @var{n} to
1.149 -be the first node. @code{getNext(n)} gives back the subsequent
1.150 -node. @code{next(n)} is equivalent to @code{n=getNext(n)}, though it
1.151 -might be faster. ??? What should be the return value ???
1.152 -@end deftypefun
1.153 -
1.154 -@deftypefun bool Graph::valid (NodeIt &@var{e})
1.155 -@c @deftypefunx bool NodeIt::valid ()
1.156 -These functions check if and NodeIt is valid or not.
1.157 -@c ??? Which one should be implemented ???
1.158 -@end deftypefun
1.159 -
1.160 -@subsubsection EdgeIt Operations
1.161 -
1.162 -@deftypefun EachEdgeIt Graph::getFirst (const EachEdgeIt & @var{e}) const
1.163 -@deftypefunx EachEdgeIt Graph::getNext (EachEdgeIt @var{n}) const
1.164 -@deftypefunx {EachEdgeIt &} Graph::next (EachEdgeIt &@var{n})
1.165 -With these functions you can go though all the edges of the graph.
1.166 -@c ??? What should be the return value ???
1.167 -@end deftypefun
1.168 -
1.169 -@deftypefun InEdgeIt &Graph::getFirst (InEdgeIt & @var{e}, const NodeIt @var{n})
1.170 -@deftypefunx OutEdgeIt &Graph::getFirst (OutEdgeIt & @var{e}, const NodeIt @var{n})
1.171 -@c @deftypefunx SymEdgeIt &Graph::getFirst (SymEdgeIt & @var{e}, const NodeIt @var{n})
1.172 -The edges leaving from
1.173 -or
1.174 -arriving at
1.175 -@c or adjacent with
1.176 -a node forms a
1.177 -list. These functions give back the first elements of these
1.178 -lists. The exact behavior depends on the type of @var{e}.
1.179 -
1.180 -If @var{e} is an @code{InEdgeIt} or an @code{OutEdgeIt} then
1.181 -@code{getFirst} sets @var{e} to be the first incoming or outgoing edge
1.182 -of the node @var{n}, respectively.
1.183 -
1.184 -@c If @var{e} is a @code{SymEdgeIt} then
1.185 -@c @code{getFirst} sets @var{e} to be the first incoming if there exists one
1.186 -@c otherwise the first outgoing edge.
1.187 -
1.188 -If there are no such edges, @var{e} will be invalid.
1.189 -
1.190 -@end deftypefun
1.191 -
1.192 -@deftypefun InEdgeIt Graph::next (const InEdgeIt @var{e})
1.193 -@deftypefunx OutEdgeIt Graph::next (const OutEdgeIt @var{e})
1.194 -@deftypefunx SymEdgeIt Graph::next (const SymEdgeIt @var{e})
1.195 -These functions give back the edge that follows @var{e}
1.196 -@end deftypefun
1.197 -
1.198 -@deftypefun {InEdgeIt &} Graph::goNext (InEdgeIt &@var{e})
1.199 -@deftypefunx {OutEdgeIt &} Graph::goNext (OutEdgeIt &@var{e})
1.200 -@deftypefunx {SymEdgeIt &} Graph::goNext (SymEdgeIt &@var{e})
1.201 -@code{G.goNext(e)} is equivalent to @code{e=G.next(e)}, though it
1.202 -might be faster.
1.203 -??? What should be the return value ???
1.204 -@end deftypefun
1.205 -
1.206 -@deftypefun bool Graph::valid (EdgeIt &@var{e})
1.207 -@deftypefunx bool EdgeIt::valid ()
1.208 -These functions check if and EdgeIt is valid or not.
1.209 -??? Which one should be implemented ???
1.210 -@end deftypefun
1.211 -
1.212 -@deftypefun NodeIt Graph::tail (const EdgeIt @var{e})
1.213 -@deftypefunx NodeIt Graph::head (const EdgeIt @var{e})
1.214 -@deftypefunx NodeIt Graph::aNode (const InEdgeIt @var{e})
1.215 -@deftypefunx NodeIt Graph::aNode (const OutEdgeIt @var{e})
1.216 -@deftypefunx NodeIt Graph::aNode (const SymEdgeIt @var{e})
1.217 -@deftypefunx NodeIt Graph::bNode (const InEdgeIt @var{e})
1.218 -@deftypefunx NodeIt Graph::bNode (const OutEdgeIt @var{e})
1.219 -@deftypefunx NodeIt Graph::bNode (const SymEdgeIt @var{e})
1.220 -There queries give back the two endpoints of the edge @var{e}. For a
1.221 -directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and
1.222 -its head, respectively. For an undirected @var{e}, they are two
1.223 -endpoints, but you should not rely on which end is which.
1.224 -
1.225 -@code{aNode(e)} is the node which @var{e} is bounded to, i.e. it is
1.226 -equal to @code{tail(e)} if @var{e} is an @code{OutEdgeIt} and
1.227 -@code{head(e)} if @var{e} is an @code{InEdgeIt}. If @var{e} is a
1.228 -@code{SymEdgeIt} and it or its first preceding edge was created by
1.229 -@code{getFirst(e,n)}, then @code{aNode(e)} is equal to @var{n}.
1.230 -
1.231 -@code{bNode(e)} is the other end of the edge.
1.232 -
1.233 -@deftypefun void Graph::setInvalid (EdgeIt &@var{e})
1.234 -@deftypefunx void Graph::setInvalid (EdgeIt &@var{e})
1.235 -These functions set the corresponding iterator to be invalid.
1.236 -@end deftypefun
1.237 -
1.238 -@c ???It is implemented in an other way now. (Member function <-> Graph global)???
1.239 -@end deftypefun
1.240 -
1.241 -
1.242 -
1.243 -@c @deftypevar int from
1.244 -@c the tail of the created edge.
1.245 -@c @end deftypevar