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::NodeType
 -- Type: Graph::EdgeType
     The type of the data stored statically for each node and edge.

 -- Type: Graph::NodeIt
 -- Type: Graph::NodeIterator
     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::BiEdgeIt
 -- Type: Graph::SymEdgeIt
     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::EdgeIterator
 -- Type: Graph::InEdgeIterator
 -- Type: Graph::OutEdgeIterator
 -- Type: Graph::BiEdgeIterator
 -- Type: Graph::SymEdgeIterator
 -- Type: Graph::EachEdgeIterator
     Each of these types points an edge uniquely. The difference between the EdgeIt and the EdgeIterator series is that EdgeIt requires the graph structure itself for most of the operations.

     For the EdgeIterator types you can use operator ++ (both the prefix and the posfix one) to obtain the next edge.

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

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

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

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

 -- Function:   Graph::Graph (Graph &)
     The copy constructor. Not yet implemented.

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

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

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

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

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

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

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

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

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

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

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

 -- Function: EachEdgeIt Graph::getFirst (const EachEdgeIt & E)
 -- Function: EachEdgeIt Graph::next (const EachEdgeIt N)
 -- Function: EachEdgeIt & Graph::goNext (EachEdgeIt &N)
     With these functions you can go though all the edges of the graph. ??? What should be the return value ???

 -- Function: InEdgeIt Graph::getFirst (const InEdgeIt & E, const NodeIt N)
 -- Function: OutEdgeIt Graph::getFirst (const OutEdgeIt & E, const NodeIt N)
 -- Function: SymEdgeIt Graph::getFirst (const SymEdgeIt & E, const NodeIt N)
     The edges leaving from, arriving at 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 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 E is a SymEdgeIt then getFirst sets E to be the first incoming if there exists one otherwise the first outgoing edge.

     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.

     ???It is implemented in an other way now. (Member function <-> Graph global)???