@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