The 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.

Declaration
-----------

 -- Class: class Graph
     Graph is the imaginary full feature graph class. G denotes the instance of this class in the exaples below.

Types
-----

 -- Type: Graph::NodeIt
     These types points a node uniquely. The difference between the NodeIt and the NodeIterator is that NodeIt requires the graph structure itself for most of the operations. For examples using iterators you can go through all nodes as follows.

          Graph G;
          int nodenum=0;
          for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum;

     Using NodeIt the last line looks like this.

          for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum;

     or

          MyGraph::NodeIt n;
          for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum;

 -- Type: Graph::EdgeIt
 -- Type: Graph::InEdgeIt
 -- Type: Graph::OutEdgeIt
 -- Type: Graph::EachEdgeIt
     Each of these types points an edge uniquely. The difference between the EdgeIt and the Graph-NodeIterator , EdgeIterator series is that EdgeIt requires the graph structure itself for most of the operations.

 -- Type: Graph::NodeMap<typename T>
 -- Type: Graph::EdgeMap<typename T>
     There are the default property maps for the edges and the nodes.

 -- Type: Graph::DynNodeMap<typename T>
 -- Type: Graph::DynEdgeMap<typename T>
     There are the default dynamic property maps for the edges and the nodes.

Member Functions
----------------

Constructors
............

 -- Function:   Graph::Graph ()
     The default constructor.

 -- Function:   Graph::Graph (Graph &)
     The copy constructor.

Graph Maintenence Operations
............................

 -- Function: NodeIt Graph::addNode ()
     Adds a new node to the graph and returns a NodeIt pointing to it.

 -- Function: EdgeIt Graph::addEdge (const Graph-NodeIterator,NodeIt FROM, const Graph-NodeIterator,NodeIt TO)
     Adds a new edge with tail FROM and head TO to the graph and returns an EdgeIt pointing to it.

 -- Function: void Graph::delete (const Graph-NodeIterator,NodeIt N)
     Deletes the node N. It also deletes the adjacent edges.

 -- Function: void Graph::delete (const Graph-EdgeIterator,EdgeIt E)
     Deletes the edge N.

 -- Function: void Graph::clear ()
     Deletes all edges and nodes from the graph.

 -- Function: int Graph::nodeNum ()
     Returns the number of the nodes in the graph. ??? Is it necessary???

NodeIt Operations
.................

 -- Function: NodeIt Graph::getFirst (NodeIt &N) const
 -- Function: NodeIt Graph::getNext (NodeIt N) const
 -- Function: NodeIt & Graph::next (NodeIt &N)
     The nodes in the graph forms a list. getFirst(n) sets N to be the first node. getNext(n) gives back the subsequent node. next(n) is equivalent to n=getNext(n), though it might be faster.  ??? What should be the return value ???

 -- Function: bool Graph::valid (NodeIt &E)
     These functions check if and NodeIt is valid or not.

EdgeIt Operations
.................

 -- Function: EachEdgeIt Graph::getFirst (const EachEdgeIt & E) const
 -- Function: EachEdgeIt Graph::getNext (EachEdgeIt N) const
 -- Function: EachEdgeIt & Graph::next (EachEdgeIt &N)
     With these functions you can go though all the edges of the graph.

 -- Function: InEdgeIt &Graph::getFirst (InEdgeIt & E, const NodeIt N)
 -- Function: OutEdgeIt &Graph::getFirst (OutEdgeIt & E, const NodeIt N)
     The edges leaving from or arriving at a node forms a list.  These functions give back the first elements of these lists. The exact behavior depends on the type of E.

     If E is an InEdgeIt or an OutEdgeIt then getFirst sets E to be the first incoming or outgoing edge of the node N, respectively.

     If there are no such edges, E will be invalid.

 -- Function: InEdgeIt Graph::next (const InEdgeIt E)
 -- Function: OutEdgeIt Graph::next (const OutEdgeIt E)
 -- Function: SymEdgeIt Graph::next (const SymEdgeIt E)
     These functions give back the edge that follows E

 -- Function: InEdgeIt & Graph::goNext (InEdgeIt &E)
 -- Function: OutEdgeIt & Graph::goNext (OutEdgeIt &E)
 -- Function: SymEdgeIt & Graph::goNext (SymEdgeIt &E)
     G.goNext(e) is equivalent to e=G.next(e), though it might be faster. ??? What should be the return value ???

 -- Function: bool Graph::valid (EdgeIt &E)
 -- Function: bool EdgeIt::valid ()
     These functions check if and EdgeIt is valid or not. ??? Which one should be implemented ???

 -- Function: NodeIt Graph::tail (const EdgeIt E)
 -- Function: NodeIt Graph::head (const EdgeIt E)
 -- Function: NodeIt Graph::aNode (const InEdgeIt E)
 -- Function: NodeIt Graph::aNode (const OutEdgeIt E)
 -- Function: NodeIt Graph::aNode (const SymEdgeIt E)
 -- Function: NodeIt Graph::bNode (const InEdgeIt E)
 -- Function: NodeIt Graph::bNode (const OutEdgeIt E)
 -- Function: NodeIt Graph::bNode (const SymEdgeIt E)
     There queries give back the two endpoints of the edge E.  For a directed edge E, tail(e) and head(e) is its tail and its head, respectively. For an undirected E, they are two endpoints, but you should not rely on which end is which.

     aNode(e) is the node which E is bounded to, i.e. it is equal to tail(e) if E is an OutEdgeIt and head(e) if E is an InEdgeIt. If E is a SymEdgeIt and it or its first preceding edge was created by getFirst(e,n), then aNode(e) is equal to N.

     bNode(e) is the other end of the edge.

      -- Function: void Graph::setInvalid (EdgeIt &E)
      -- Function: void Graph::setInvalid (EdgeIt &E)
          These functions set the corresponding iterator to be invalid.