@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<typename T>

 @deftpx {Type} Graph::EdgeMap<typename T>

 There are the default property maps for the edges and the nodes.

 @end deftp

 @deftp {Type} Graph::DynNodeMap<typename T>

 @deftpx {Type} Graph::DynEdgeMap<typename T>

 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