diff -r ee5959aa4410 -r c280de819a73 src/work/alpar/attic/texi/flf-graph.texi --- a/src/work/alpar/attic/texi/flf-graph.texi Sun Apr 17 18:57:22 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,242 +0,0 @@ -@node The Full Feature Graph Class -@section The Full Feature Graph Class -@cindex Full Feature Graph Class - -This section describes what an imaginary full feature graph class knows. -The set of features provided by a real graph implementation is typically -a subset of the features below. - -On the other hand, each graph algorithm requires the underlying graph -structure to provide a certain (typically small) set of features in order -to be able to run. - -@subsection Declaration - -@deftp {Class} {class Graph} -@code{Graph} is the imaginary @emph{full feature graph class}. -@code{G} denotes the instance of this class in the exaples below. -@c Each node and edge has a user defined data sturcure -@c @var{N} and @var{E} statically attached to it. -@end deftp - -@subsection Types - -@c @deftp {Type} Graph::NodeType -@c @deftpx {Type} Graph::EdgeType -@c The type of the data stored statically for each node and edge. -@c @end deftp - -@anchor{Graph-NodeIterator} -@deftp {Type} Graph::NodeIt -@c @deftpx {Type} Graph::NodeIterator -These types points a node uniquely. The difference between the -@code{NodeIt} and the @code{NodeIterator} is that @code{NodeIt} -requires the graph structure itself for most of the operations. -For examples using iterators you can go through all nodes as follows. -@quotation -@verbatim -Graph G; -int nodenum=0; -for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum; -@end verbatim -@end quotation -Using @code{NodeIt} the last line looks like this. -@quotation -@verbatim -for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum; -@end verbatim -@end quotation -or -@quotation -@verbatim -MyGraph::NodeIt n; -for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum; -@end verbatim -@end quotation -@end deftp - -@deftp {Type} Graph::EdgeIt -@deftpx {Type} Graph::InEdgeIt -@deftpx {Type} Graph::OutEdgeIt -@deftpx {Type} Graph::EachEdgeIt -@c @deftpx {Type} Graph::BiEdgeIt -@c @deftpx {Type} Graph::SymEdgeIt -Each of these types points an edge uniquely. The difference between the -@code{EdgeIt} and the -@c @mref{Graph-NodeIterator,@code{EdgeIterator}} -@mref{Graph-NodeIterator , EdgeIterator} -series is that -@code{EdgeIt} requires the graph structure itself for most of the -operations. -@end deftp - -@anchor{Graph-EdgeIterator} -@c @deftp {Type} Graph::EdgeIterator -@c @deftpx {Type} Graph::InEdgeIterator -@c @deftpx {Type} Graph::OutEdgeIterator -@c @deftpx {Type} Graph::BiEdgeIterator -@c @deftpx {Type} Graph::SymEdgeIterator -@c @deftpx {Type} Graph::EachEdgeIterator -@c Each of these types points an edge uniquely. The difference between the -@c @code{EdgeIt} and the @code{EdgeIterator} series is that -@c @code{EdgeIt} requires the graph structure itself for most of the -@c operations. - -@c For the @code{EdgeIterator} types you can use operator @code{++} -@c (both the prefix and the posfix one) to obtain the next edge. -@c @end deftp - -@deftp {Type} Graph::NodeMap -@deftpx {Type} Graph::EdgeMap -There are the default property maps for the edges and the nodes. -@end deftp - -@deftp {Type} Graph::DynNodeMap -@deftpx {Type} Graph::DynEdgeMap -There are the default @emph{dynamic} property maps for the edges and the nodes. -@end deftp - -@subsection Member Functions - -@subsubsection Constructors - -@deftypefun { } Graph::Graph () -The default constructor. -@end deftypefun - -@c @deftypefun { } Graph::Graph (Graph@tie{}&) -@deftypefun { } Graph::Graph (Graph &) -The copy constructor. -@end deftypefun - -@subsubsection Graph Maintenence Operations - -@deftypefun NodeIt Graph::addNode () -Adds a new node to the graph and returns a @code{NodeIt} pointing to it. -@end deftypefun - -@deftypefun EdgeIt Graph::addEdge (@w{const @mref{Graph-NodeIterator,NodeIt} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIt} @var{to}}) -Adds a new edge with tail @var{from} and head @var{to} to the graph -and returns an @code{EdgeIt} pointing to it. -@end deftypefun - -@deftypefun void Graph::delete (@w{const @mref{Graph-NodeIterator,NodeIt} @var{n}}) -Deletes the node @var{n}. It also deletes the adjacent edges. -@end deftypefun - -@deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIt} @var{e}}) -Deletes the edge @var{n}. -@end deftypefun - -@deftypefun void Graph::clear () -Deletes all edges and nodes from the graph. -@end deftypefun - -@deftypefun int Graph::nodeNum () -Returns the number of the nodes in the graph. -??? Is it necessary??? -@end deftypefun - -@subsubsection NodeIt Operations - -@deftypefun NodeIt Graph::getFirst (NodeIt &@var{n}) const -@deftypefunx NodeIt Graph::getNext (NodeIt @var{n}) const -@deftypefunx {NodeIt &} Graph::next (NodeIt &@var{n}) -The nodes in the graph forms a list. @code{getFirst(n)} sets @var{n} to -be the first node. @code{getNext(n)} gives back the subsequent -node. @code{next(n)} is equivalent to @code{n=getNext(n)}, though it -might be faster. ??? What should be the return value ??? -@end deftypefun - -@deftypefun bool Graph::valid (NodeIt &@var{e}) -@c @deftypefunx bool NodeIt::valid () -These functions check if and NodeIt is valid or not. -@c ??? Which one should be implemented ??? -@end deftypefun - -@subsubsection EdgeIt Operations - -@deftypefun EachEdgeIt Graph::getFirst (const EachEdgeIt & @var{e}) const -@deftypefunx EachEdgeIt Graph::getNext (EachEdgeIt @var{n}) const -@deftypefunx {EachEdgeIt &} Graph::next (EachEdgeIt &@var{n}) -With these functions you can go though all the edges of the graph. -@c ??? What should be the return value ??? -@end deftypefun - -@deftypefun InEdgeIt &Graph::getFirst (InEdgeIt & @var{e}, const NodeIt @var{n}) -@deftypefunx OutEdgeIt &Graph::getFirst (OutEdgeIt & @var{e}, const NodeIt @var{n}) -@c @deftypefunx SymEdgeIt &Graph::getFirst (SymEdgeIt & @var{e}, const NodeIt @var{n}) -The edges leaving from -or -arriving at -@c or adjacent with -a node forms a -list. These functions give back the first elements of these -lists. The exact behavior depends on the type of @var{e}. - -If @var{e} is an @code{InEdgeIt} or an @code{OutEdgeIt} then -@code{getFirst} sets @var{e} to be the first incoming or outgoing edge -of the node @var{n}, respectively. - -@c If @var{e} is a @code{SymEdgeIt} then -@c @code{getFirst} sets @var{e} to be the first incoming if there exists one -@c otherwise the first outgoing edge. - -If there are no such edges, @var{e} will be invalid. - -@end deftypefun - -@deftypefun InEdgeIt Graph::next (const InEdgeIt @var{e}) -@deftypefunx OutEdgeIt Graph::next (const OutEdgeIt @var{e}) -@deftypefunx SymEdgeIt Graph::next (const SymEdgeIt @var{e}) -These functions give back the edge that follows @var{e} -@end deftypefun - -@deftypefun {InEdgeIt &} Graph::goNext (InEdgeIt &@var{e}) -@deftypefunx {OutEdgeIt &} Graph::goNext (OutEdgeIt &@var{e}) -@deftypefunx {SymEdgeIt &} Graph::goNext (SymEdgeIt &@var{e}) -@code{G.goNext(e)} is equivalent to @code{e=G.next(e)}, though it -might be faster. -??? What should be the return value ??? -@end deftypefun - -@deftypefun bool Graph::valid (EdgeIt &@var{e}) -@deftypefunx bool EdgeIt::valid () -These functions check if and EdgeIt is valid or not. -??? Which one should be implemented ??? -@end deftypefun - -@deftypefun NodeIt Graph::tail (const EdgeIt @var{e}) -@deftypefunx NodeIt Graph::head (const EdgeIt @var{e}) -@deftypefunx NodeIt Graph::aNode (const InEdgeIt @var{e}) -@deftypefunx NodeIt Graph::aNode (const OutEdgeIt @var{e}) -@deftypefunx NodeIt Graph::aNode (const SymEdgeIt @var{e}) -@deftypefunx NodeIt Graph::bNode (const InEdgeIt @var{e}) -@deftypefunx NodeIt Graph::bNode (const OutEdgeIt @var{e}) -@deftypefunx NodeIt Graph::bNode (const SymEdgeIt @var{e}) -There queries give back the two endpoints of the edge @var{e}. For a -directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and -its head, respectively. For an undirected @var{e}, they are two -endpoints, but you should not rely on which end is which. - -@code{aNode(e)} is the node which @var{e} is bounded to, i.e. it is -equal to @code{tail(e)} if @var{e} is an @code{OutEdgeIt} and -@code{head(e)} if @var{e} is an @code{InEdgeIt}. If @var{e} is a -@code{SymEdgeIt} and it or its first preceding edge was created by -@code{getFirst(e,n)}, then @code{aNode(e)} is equal to @var{n}. - -@code{bNode(e)} is the other end of the edge. - -@deftypefun void Graph::setInvalid (EdgeIt &@var{e}) -@deftypefunx void Graph::setInvalid (EdgeIt &@var{e}) -These functions set the corresponding iterator to be invalid. -@end deftypefun - -@c ???It is implemented in an other way now. (Member function <-> Graph global)??? -@end deftypefun - - - -@c @deftypevar int from -@c the tail of the created edge. -@c @end deftypevar