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