// -*- c++ -*-

 #ifndef HUGO_LEDA_GRAPH_H

 #define HUGO_LEDA_GRAPH_H

 #include <LEDA/graph.h>

 #include <LEDA/node_array.h>

 #include <LEDA/edge_array.h>

 //#include <LEDA/graph_alg.h>

 //#include <LEDA/dimacs.h>

 //#if defined(LEDA_NAMESPACE)

 //using namespace leda;

 //#endif

 #include <invalid.h>

 /// The namespace of HugoLib

 namespace hugo {

   // @defgroup empty_graph The LedaGraph class

   // @{

   /// An empty graph class.

   /// This class provides all the common features of a grapf structure,

   /// however completely without implementations or real data structures

   /// behind the interface.

   /// All graph algorithms should compile with this class, but it will not

   /// run properly, of course.

   ///

   /// It can be used for checking the interface compatibility,

   /// or it can serve as a skeleton of a new graph structure.

   /// 

   /// Also, you will find here the full documentation of a certain graph

   /// feature, the documentation of a real graph imlementation

   /// like @ref ListGraph or

   /// @ref SmartGraph will just refer to this structure.

   template<typename Graph>

   class LedaGraph

   {

     Graph* _graph;

   public:

         //LedaGraph() { }

     LedaGraph(Graph& __graph) : _graph(&__graph) { }

     LedaGraph(const LedaGraph &G) : _graph(G._graph) { }

     template <typename T> class NodeMap;

     template <typename T> class EdgeMap;

     /// The base type of the node iterators.

     class Node {

       friend class LedaGraph;

       //friend class Edge;

       friend class EdgeIt;

       friend class InEdgeIt;

       friend class OutEdgeIt;

     protected:

       template <typename T> friend class NodeMap;

       leda_node _n;

       Node(leda_node __n) : _n(__n) { } 

     public:

       /// @warning The default constructor sets the iterator

       /// to an undefined value.

       Node() {}   //FIXME

       /// Initialize the iterator to be invalid

       Node(Invalid) : _n(0) { }

       //Node(const Node &) {} 

       bool operator==(Node n) const { return _n==n._n; } //FIXME

       bool operator!=(Node n) const { return _n!=n._n; } //FIXME

     };

     /// This iterator goes through each node.

     class NodeIt : public Node {

     public:

       /// @warning The default constructor sets the iterator

       /// to an undefined value.

       NodeIt() {} //FIXME

       /// Initialize the iterator to be invalid

       NodeIt(Invalid i) : Node(i) {}

       /// Sets the iterator to the first node of \c G.

       NodeIt(const LedaGraph &G) : Node(G._graph->first_node()) { }

       //NodeIt(const NodeIt &) {} //FIXME

     };

     /// The base type of the edge iterators.

     class Edge {

       friend class LedaGraph;

     protected:

       template <typename T> friend class EdgeMap;

       leda_edge _e;

       Edge(leda_edge __e) : _e(__e) { } 

     public:

       /// @warning The default constructor sets the iterator

       /// to an undefined value.

       Edge() {}   //FIXME

       /// Initialize the iterator to be invalid

       Edge(Invalid) : _e(0) {}

       //Edge(const Edge &) {} 

       bool operator==(Edge e) const { return _e==e._e; } //FIXME

       bool operator!=(Edge e) const { return _e!=e._e; } //FIXME    

     };

     /// This iterator goes trought the outgoing edges of a certain graph.

     class OutEdgeIt : public Edge {

     public:

       /// @warning The default constructor sets the iterator

       /// to an undefined value.

       OutEdgeIt() {}

       /// Initialize the iterator to be invalid

       OutEdgeIt(Invalid i) : Edge(i) {}

       /// This constructor sets the iterator to first outgoing edge.

       /// This constructor set the iterator to the first outgoing edge of

       /// node

       ///@param n the node

       ///@param G the graph

       OutEdgeIt(const LedaGraph & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }

     };

     class InEdgeIt : public Edge {

     public:

       /// @warning The default constructor sets the iterator

       /// to an undefined value.

       InEdgeIt() {}

       /// Initialize the iterator to be invalid

       InEdgeIt(Invalid i) : Edge(i) {}

       InEdgeIt(const LedaGraph & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }

     };

     //  class SymEdgeIt : public Edge {};

     class EdgeIt : public Edge {

     public:

       /// @warning The default constructor sets the iterator

       /// to an undefined value.

       EdgeIt() {}

       /// Initialize the iterator to be invalid

       EdgeIt(Invalid i) : Edge(i) {}

       EdgeIt(const LedaGraph & G) : Edge(G._graph->first_edge()) { }

     };

     /// First node of the graph.

     /// \post \c i and the return value will be the first node.

     ///

     NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }

     /// The first outgoing edge.

     InEdgeIt &first(InEdgeIt &i, Node n) const { 

       i=InEdgeIt(*this, n); 

       return i;

     }

     /// The first incoming edge.

     OutEdgeIt &first(OutEdgeIt &i, Node n) const { 

       i=OutEdgeIt(*this, n); 

       return i;

     }

     //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}

     /// The first edge of the Graph.

     EdgeIt &first(EdgeIt &i) const {      

       i=EdgeIt(*this); 

       return i; }

 //     Node getNext(Node) const {}

 //     InEdgeIt getNext(InEdgeIt) const {}

 //     OutEdgeIt getNext(OutEdgeIt) const {}

 //     //SymEdgeIt getNext(SymEdgeIt) const {}

 //     EdgeIt getNext(EdgeIt) const {}

     /// Go to the next node.

     NodeIt &next(NodeIt &i) const { 

       i._n=_graph->succ_node(i._n); 

       return i; 

     }

     /// Go to the next incoming edge.

     InEdgeIt &next(InEdgeIt &i) const { 

       i._e=_graph->in_succ(i._e); 

       return i;

     }

     /// Go to the next outgoing edge.

     OutEdgeIt &next(OutEdgeIt &i) const { 

       i._e=_graph->adj_succ(i._e); 

       return i;

     }

     //SymEdgeIt &next(SymEdgeIt &) const {}

     /// Go to the next edge.

     EdgeIt &next(EdgeIt &i) const {      

       i._e=_graph->succ_edge(i._e); 

       return i; 

     }

     template< typename It >

     It first() const { 

       It e;

       first(e);

       return e; 

     }

     template< typename It >

     It first(Node v) const { 

       It e;

       first(e, v);

       return e; 

     }

     ///Gives back the head node of an edge.

     Node head(Edge e) const { 

       return Node(_graph->target(e._e)); 

     }

     ///Gives back the tail node of an edge.

     Node tail(Edge e) const { 

       return Node(_graph->source(e._e)); 

     }

     Node aNode(InEdgeIt e) const { return head(e); }

     Node aNode(OutEdgeIt e) const { return tail(e); }

     //   Node aNode(SymEdgeIt) const {}

     Node bNode(InEdgeIt e) const { return tail(e); }

     Node bNode(OutEdgeIt e) const { return head(e); }

     //   Node bNode(SymEdgeIt) const {}

     /// Checks if a node iterator is valid

     bool valid(Node n) const { return n._n; }

     /// Checks if an edge iterator is valid

     bool valid(Edge e) const { return e._e; }

     ///Gives back the \e id of a node.

     int id(Node n) const { return n._n->id(); }

     ///Gives back the \e id of an edge.

     int id(Edge e) const { return e._e->id(); }

     //void setInvalid(Node &) const {};

     //void setInvalid(Edge &) const {};

     Node addNode() const { return Node(_graph->new_node()); }

     Edge addEdge(Node tail, Node head) const { 

       return Edge(_graph->new_edge(tail._n, head._n));

     }

     void erase(Node n) const { _graph->del_node(n._n); }

     void erase(Edge e) const { _graph->del_edge(e._e); }

     void clear() const { _graph->clear(); }

     int nodeNum() const { return _graph->number_of_nodes(); }

     int edgeNum() const { return _graph->number_of_edges(); }

     ///Read/write map from the nodes to type \c T.

     template<typename T> class NodeMap

     {

       leda_node_map<T> leda_stuff;

     public:

       typedef T ValueType;

       typedef Node KeyType;

       NodeMap(const LedaGraph &G) : leda_stuff(*(G._graph)) {}

       NodeMap(const LedaGraph &G, T t) : leda_stuff(*(G._graph), t) {}

       void set(Node i, T t) { leda_stuff[i._n]=t; }

       T get(Node i) const { return leda_stuff[i._n]; }  //FIXME: Is it necessary

       T &operator[](Node i) { return leda_stuff[i._n]; }

       const T &operator[](Node i) const { return leda_stuff[i._n]; }

       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }

       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary

     };

     ///Read/write map from the edges to type \c T.

     template<typename T> class EdgeMap

     {

       leda_edge_map<T> leda_stuff;

     public:

       typedef T ValueType;

       typedef Edge KeyType;

       EdgeMap(const LedaGraph &G) : leda_stuff(*(G._graph)) {}

       EdgeMap(const LedaGraph &G, T t) : leda_stuff(*(G._graph), t) {}

       void set(Edge i, T t) { leda_stuff[i._e]=t; }

       T get(Edge i) const { return leda_stuff[i._e]; }  //FIXME: Is it necessary

       T &operator[](Edge i) { return leda_stuff[i._e]; }

       const T &operator[](Edge i) const { return leda_stuff[i._e]; }

       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }

       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary

     };

   };

   // @}

 } //namespace hugo

 // class EmptyBipGraph : public EmptyGraph

 // {

 //   class ANode {};

 //   class BNode {};

 //   ANode &next(ANode &) {}

 //   BNode &next(BNode &) {}

 //   ANode &getFirst(ANode &) const {}

 //   BNode &getFirst(BNode &) const {}

 //   enum NodeClass { A = 0, B = 1 };

 //   NodeClass getClass(Node n) {}

 // }

 #endif // HUGO_LEDA_GRAPH_H