marci@189: // -*- c++ -*-
marci@189: #ifndef HUGO_LEDA_GRAPH_WRAPPER_H
marci@189: #define HUGO_LEDA_GRAPH_WRAPPER_H
marci@189: 
marci@189: #include <LEDA/graph.h>
marci@189: #include <LEDA/node_array.h>
marci@189: #include <LEDA/edge_array.h>
marci@189: #include <LEDA/node_map.h>
marci@189: #include <LEDA/edge_map.h>
marci@189: //#include <LEDA/graph_alg.h>
marci@189: //#include <LEDA/dimacs.h>
marci@189: 
marci@189: //#if defined(LEDA_NAMESPACE)
marci@189: //using namespace leda;
marci@189: //#endif
marci@189: 
marci@189: #include <invalid.h>
marci@189: 
marci@189: /// The namespace of HugoLib
marci@189: namespace hugo {
marci@189: 
marci@189:   // @defgroup empty_graph The LedaGraphWrapper class
marci@189:   // @{
marci@189: 
marci@409:   /// A graph wrapperstructure for wrapping LEDA graphs in HUGO.
marci@189:   
marci@409:   /// This graph wrapper class wraps LEDA graph and LEDA parametrized graph
marci@409:   /// and then the generic algorithms and wrappers of HUGO can be used 
marci@409:   /// with LEDA graphs. 
marci@189:   /// This class provides all the common features of a grapf structure,
marci@189:   /// however completely without implementations or real data structures
marci@189:   /// behind the interface.
marci@189:   /// All graph algorithms should compile with this class, but it will not
marci@189:   /// run properly, of course.
marci@189:   ///
marci@189:   /// It can be used for checking the interface compatibility,
marci@189:   /// or it can serve as a skeleton of a new graph structure.
marci@189:   /// 
marci@189:   /// Also, you will find here the full documentation of a certain graph
marci@189:   /// feature, the documentation of a real graph imlementation
marci@189:   /// like @ref ListGraph or
marci@189:   /// @ref SmartGraph will just refer to this structure.
marci@189:   template<typename Graph>
marci@189:   class LedaGraphWrapper
marci@189:   {
marci@189:     Graph* _graph;
marci@189:   public:
marci@189:    
marci@189:         //LedaGraphWrapper() { }
marci@189:     LedaGraphWrapper(Graph& __graph) : _graph(&__graph) { }
marci@189:     LedaGraphWrapper(const LedaGraphWrapper &G) : _graph(G._graph) { }
marci@189: 
marci@189:     template <typename T> class NodeMap;
marci@189:     template <typename T> class EdgeMap;
marci@189: 
marci@189:     /// The base type of the node iterators.
marci@189:     class Node {
marci@189:       friend class LedaGraphWrapper;
marci@189:       //friend class Edge;
marci@189:       friend class EdgeIt;
marci@189:       friend class InEdgeIt;
marci@189:       friend class OutEdgeIt;
marci@189:     protected:
marci@189:       template <typename T> friend class NodeMap;
marci@189:       leda_node _n;
marci@446:     public: //FIXME
marci@189:       Node(leda_node __n) : _n(__n) { } 
marci@189:     public:
marci@189:       /// @warning The default constructor sets the iterator
marci@189:       /// to an undefined value.
marci@189:       Node() {}   //FIXME
marci@189:       /// Initialize the iterator to be invalid
marci@189:       Node(Invalid) : _n(0) { }
marci@189:       //Node(const Node &) {} 
marci@189:       bool operator==(Node n) const { return _n==n._n; } //FIXME
marci@189:       bool operator!=(Node n) const { return _n!=n._n; } //FIXME
marci@198:       operator leda_node () { return _n; }
marci@189:     };
marci@189:     
marci@189:     /// This iterator goes through each node.
marci@189:     class NodeIt : public Node {
marci@189:     public:
marci@189:       /// @warning The default constructor sets the iterator
marci@189:       /// to an undefined value.
marci@189:       NodeIt() {} //FIXME
marci@189:       /// Initialize the iterator to be invalid
marci@189:       NodeIt(Invalid i) : Node(i) {}
marci@189:       /// Sets the iterator to the first node of \c G.
marci@189:       NodeIt(const LedaGraphWrapper &G) : Node(G._graph->first_node()) { }
marci@189:       //NodeIt(const NodeIt &) {} //FIXME
marci@189:     };
marci@189:     
marci@189:     /// The base type of the edge iterators.
marci@189:     class Edge {
marci@189:       friend class LedaGraphWrapper;
marci@189:     protected:
marci@189:       template <typename T> friend class EdgeMap;
marci@189:       leda_edge _e;
marci@446:     public: //FIXME
marci@189:       Edge(leda_edge __e) : _e(__e) { } 
marci@189:     public:
marci@189:       /// @warning The default constructor sets the iterator
marci@189:       /// to an undefined value.
marci@189:       Edge() {}   //FIXME
marci@189:       /// Initialize the iterator to be invalid
marci@189:       Edge(Invalid) : _e(0) {}
marci@189:       //Edge(const Edge &) {} 
marci@189:       bool operator==(Edge e) const { return _e==e._e; } //FIXME
marci@198:       bool operator!=(Edge e) const { return _e!=e._e; } //FIXME 
marci@198:       operator leda_edge () { return _e; }
marci@189:     };
marci@189:     
marci@189:     /// This iterator goes trought the outgoing edges of a certain graph.
marci@189:     
marci@189:     class OutEdgeIt : public Edge {
marci@189:     public:
marci@189:       /// @warning The default constructor sets the iterator
marci@189:       /// to an undefined value.
marci@189:       OutEdgeIt() {}
marci@189:       /// Initialize the iterator to be invalid
marci@189:       OutEdgeIt(Invalid i) : Edge(i) {}
marci@189:       /// This constructor sets the iterator to first outgoing edge.
marci@189:     
marci@189:       /// This constructor set the iterator to the first outgoing edge of
marci@189:       /// node
marci@189:       ///@param n the node
marci@189:       ///@param G the graph
marci@189:       OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
marci@189:     };
marci@189: 
marci@189:     class InEdgeIt : public Edge {
marci@189:     public:
marci@189:       /// @warning The default constructor sets the iterator
marci@189:       /// to an undefined value.
marci@189:       InEdgeIt() {}
marci@189:       /// Initialize the iterator to be invalid
marci@189:       InEdgeIt(Invalid i) : Edge(i) {}
marci@189:       InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }
marci@189:     };
marci@189: 
marci@189:     //  class SymEdgeIt : public Edge {};
marci@189:     class EdgeIt : public Edge {
marci@189:     public:
marci@189:       /// @warning The default constructor sets the iterator
marci@189:       /// to an undefined value.
marci@189:       EdgeIt() {}
marci@189:       /// Initialize the iterator to be invalid
marci@189:       EdgeIt(Invalid i) : Edge(i) {}
marci@189:       EdgeIt(const LedaGraphWrapper & G) : Edge(G._graph->first_edge()) { }
marci@189:     };
marci@189: 
marci@189:     /// First node of the graph.
marci@189: 
marci@189:     /// \post \c i and the return value will be the first node.
marci@189:     ///
marci@189:     NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
marci@189: 
marci@189:     /// The first outgoing edge.
marci@189:     InEdgeIt &first(InEdgeIt &i, Node n) const { 
marci@189:       i=InEdgeIt(*this, n); 
marci@189:       return i;
marci@189:     }
marci@189:     /// The first incoming edge.
marci@189:     OutEdgeIt &first(OutEdgeIt &i, Node n) const { 
marci@189:       i=OutEdgeIt(*this, n); 
marci@189:       return i;
marci@189:     }
marci@189:     //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
marci@189:     /// The first edge of the Graph.
marci@189:     EdgeIt &first(EdgeIt &i) const {      
marci@189:       i=EdgeIt(*this); 
marci@189:       return i; }
marci@189: 
marci@189: //     Node getNext(Node) const {}
marci@189: //     InEdgeIt getNext(InEdgeIt) const {}
marci@189: //     OutEdgeIt getNext(OutEdgeIt) const {}
marci@189: //     //SymEdgeIt getNext(SymEdgeIt) const {}
marci@189: //     EdgeIt getNext(EdgeIt) const {}
marci@189: 
marci@189:     /// Go to the next node.
marci@189:     NodeIt &next(NodeIt &i) const { 
marci@189:       i._n=_graph->succ_node(i._n); 
marci@189:       return i; 
marci@189:     }
marci@189:     /// Go to the next incoming edge.
marci@189:     InEdgeIt &next(InEdgeIt &i) const { 
marci@189:       i._e=_graph->in_succ(i._e); 
marci@189:       return i;
marci@189:     }
marci@189:     /// Go to the next outgoing edge.
marci@189:     OutEdgeIt &next(OutEdgeIt &i) const { 
marci@189:       i._e=_graph->adj_succ(i._e); 
marci@189:       return i;
marci@189:     }
marci@189:     //SymEdgeIt &next(SymEdgeIt &) const {}
marci@189:     /// Go to the next edge.
marci@189:     EdgeIt &next(EdgeIt &i) const {      
marci@189:       i._e=_graph->succ_edge(i._e); 
marci@189:       return i; 
marci@189:     }
marci@189: 
marci@409: //     template< typename It >
marci@409: //     It first() const { 
marci@409: //       It e;
marci@409: //       first(e);
marci@409: //       return e; 
marci@409: //     }
marci@189: 
marci@409: //     template< typename It >
marci@409: //     It first(Node v) const { 
marci@409: //       It e;
marci@409: //       first(e, v);
marci@409: //       return e; 
marci@409: //     }
marci@189: 
marci@189:     ///Gives back the head node of an edge.
marci@189:     Node head(Edge e) const { 
marci@189:       return Node(_graph->target(e._e)); 
marci@189:     }
marci@189:     ///Gives back the tail node of an edge.
marci@189:     Node tail(Edge e) const { 
marci@189:       return Node(_graph->source(e._e)); 
marci@189:     }
marci@189:   
marci@189:     Node aNode(InEdgeIt e) const { return head(e); }
marci@189:     Node aNode(OutEdgeIt e) const { return tail(e); }
marci@189:     //   Node aNode(SymEdgeIt) const {}
marci@189: 
marci@189:     Node bNode(InEdgeIt e) const { return tail(e); }
marci@189:     Node bNode(OutEdgeIt e) const { return head(e); }
marci@189:     //   Node bNode(SymEdgeIt) const {}
marci@189: 
marci@189:     /// Checks if a node iterator is valid
marci@189:     bool valid(Node n) const { return n._n; }
marci@189:     /// Checks if an edge iterator is valid
marci@189:     bool valid(Edge e) const { return e._e; }
marci@189: 
marci@189:     ///Gives back the \e id of a node.
marci@189:     int id(Node n) const { return n._n->id(); }
marci@189:     ///Gives back the \e id of an edge.
marci@189:     int id(Edge e) const { return e._e->id(); }
marci@189: 
marci@189:     //void setInvalid(Node &) const {};
marci@189:     //void setInvalid(Edge &) const {};
marci@189:   
marci@189:     Node addNode() const { return Node(_graph->new_node()); }
marci@189:     Edge addEdge(Node tail, Node head) const { 
marci@189:       return Edge(_graph->new_edge(tail._n, head._n));
marci@189:     }
marci@189:     
marci@189:     void erase(Node n) const { _graph->del_node(n._n); }
marci@189:     void erase(Edge e) const { _graph->del_edge(e._e); }
marci@189: 
marci@189:     void clear() const { _graph->clear(); }
marci@189: 
marci@189:     int nodeNum() const { return _graph->number_of_nodes(); }
marci@189:     int edgeNum() const { return _graph->number_of_edges(); }
marci@189: 
marci@189:     ///Read/write map from the nodes to type \c T.
marci@189:     template<typename T> class NodeMap
marci@189:     {
marci@189:       leda_node_map<T> leda_stuff;
marci@189:     public:
marci@189:       typedef T ValueType;
marci@189:       typedef Node KeyType;
marci@189: 
marci@189:       NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
marci@189:       NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
marci@189: 
marci@189:       void set(Node i, T t) { leda_stuff[i._n]=t; }
marci@189:       T get(Node i) const { return leda_stuff[i._n]; }  //FIXME: Is it necessary
marci@189:       T &operator[](Node i) { return leda_stuff[i._n]; }
marci@189:       const T &operator[](Node i) const { return leda_stuff[i._n]; }
marci@189: 
marci@189:       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
marci@189:       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary
marci@189:     };
marci@189: 
marci@189:     ///Read/write map from the edges to type \c T.
marci@189:     template<typename T> class EdgeMap
marci@189:     {
marci@189:       leda_edge_map<T> leda_stuff;
marci@189:     public:
marci@189:       typedef T ValueType;
marci@189:       typedef Edge KeyType;
marci@189: 
marci@189:       EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
marci@189:       EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
marci@189: 
marci@189:       void set(Edge i, T t) { leda_stuff[i._e]=t; }
marci@189:       T get(Edge i) const { return leda_stuff[i._e]; }  //FIXME: Is it necessary
marci@189:       T &operator[](Edge i) { return leda_stuff[i._e]; }
marci@189:       const T &operator[](Edge i) const { return leda_stuff[i._e]; }
marci@189: 
marci@189:       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
marci@189:       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary
marci@189:     };
marci@189: 
marci@189:   };
marci@189: 
marci@189:   // @}
marci@189: 
marci@189: } //namespace hugo
marci@189: 
marci@189: 
marci@189: 
marci@189: // class EmptyBipGraph : public EmptyGraph
marci@189: // {
marci@189: //   class ANode {};
marci@189: //   class BNode {};
marci@189: 
marci@189: //   ANode &next(ANode &) {}
marci@189: //   BNode &next(BNode &) {}
marci@189: 
marci@189: //   ANode &getFirst(ANode &) const {}
marci@189: //   BNode &getFirst(BNode &) const {}
marci@189: 
marci@189: //   enum NodeClass { A = 0, B = 1 };
marci@189: //   NodeClass getClass(Node n) {}
marci@189: 
marci@189: // }
marci@189: 
marci@189: #endif // HUGO_LEDA_GRAPH_WRAPPER_H