@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