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::NodePoint
 -- Type: Graph::NodeIterator
     These types points a node uniquely. The difference between the NodePoint and the NodeIterator is that NodePoint 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 NodePoint the last line looks like this.

          for(MyGraph::NodePoint n(G);n.Valid();n=G.Next(n)) ++nodenum;

     or

          MyGraph::NodePoint n;
          for(G.GetFirst(n);G.Valid(n);G.GoNext(n)) ++nodenum;

 -- Type: Graph::EdgePoint
 -- Type: Graph::InEdgePoint
 -- Type: Graph::OutEdgePoint
 -- Type: Graph::BiEdgePoint
 -- Type: Graph::SymEdgePoint
     Each of these types points an edge uniquely. The difference between the EdgePoint and the Graph-NodeIterator , EdgeIterator series is that EdgePoint 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::AllEdgeIterator
     Each of these types points an edge uniquely. The difference between the EdgePoint and the EdgeIterator series is that EdgePoint 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.

NodePoint Operations
....................

 -- Function: NodePoint Graph::GetFirst (NodePoint &N)
 -- Function: NodePoint Graph::Next (const NodePoint N)
 -- Function: NodePoint & Graph::GoNext (NodePoint &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 (NodePoint &E)
 -- Function: bool NodePoint::Valid ()
     These functions check if and NodePoint is valid or not. ??? Which one should be implemented ???

EdgePoint Operations
....................

 -- Function: AllEdgePoint Graph::GetFirst (const AllEdgePoint & E)
 -- Function: AllEdgePoint Graph::Next (const AllEdgePoint N)
 -- Function: AllEdgePoint & Graph::GoNext (AllEdgePoint &N)
     With these functions you can go though all the edges of the graph. ??? What should be the return value ???

 -- Function: InEdgePoint Graph::GetFirst (const InEdgePoint & E, const NodePoint N)
 -- Function: OutEdgePoint Graph::GetFirst (const OutEdgePoint & E, const NodePoint N)
 -- Function: SymEdgePoint Graph::GetFirst (const SymEdgePoint & E, const NodePoint 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 InEdgePoint or an OutEdgePoint then GetFirst sets E to be the first incoming or outgoing edge of the node N, respectively.

     If E is a SymEdgePoint 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: InEdgePoint Graph::Next (const InEdgePoint E)
 -- Function: OutEdgePoint Graph::Next (const OutEdgePoint E)
 -- Function: SymEdgePoint Graph::Next (const SymEdgePoint E)
     These functions give back the edge that follows E

 -- Function: InEdgePoint & Graph::GoNext (InEdgePoint &E)
 -- Function: OutEdgePoint & Graph::GoNext (OutEdgePoint &E)
 -- Function: SymEdgePoint & Graph::GoNext (SymEdgePoint &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 (EdgePoint &E)
 -- Function: bool EdgePoint::Valid ()
     These functions check if and EdgePoint is valid or not. ??? Which one should be implemented ???

 -- Function: NodePoint Graph::From (const EdgePoint E)
 -- Function: NodePoint Graph::To (const EdgePoint E)
 -- Function: NodePoint Graph::ANode (const InEdgePoint E)
 -- Function: NodePoint Graph::ANode (const OutEdgePoint E)
 -- Function: NodePoint Graph::ANode (const SymEdgePoint E)
 -- Function: NodePoint Graph::BNode (const InEdgePoint E)
 -- Function: NodePoint Graph::BNode (const OutEdgePoint E)
 -- Function: NodePoint Graph::BNode (const SymEdgePoint E)
     There queries give back the two endpoints of the edge E.  For a directed edge E, From(e) and To(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 From(e) if E is an OutEdgePoint and To(e) if E is an InEdgePoint. If E is a SymEdgePoint 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 it implemented in an other way now. (Member function <-> Graph global)???