src/work/marci/leda/leda_graph_wrapper.h
author ladanyi
Thu, 16 Sep 2004 19:51:28 +0000
changeset 875 fda944f15ca7
parent 646 bd7a69231cf8
child 921 818510fa3d99
permissions -rw-r--r--
Changed to conform to the new iterator style.
     1 // -*- c++ -*-
     2 #ifndef HUGO_LEDA_GRAPH_WRAPPER_H
     3 #define HUGO_LEDA_GRAPH_WRAPPER_H
     4 
     5 #include <LEDA/graph.h>
     6 #include <LEDA/node_array.h>
     7 #include <LEDA/edge_array.h>
     8 #include <LEDA/node_map.h>
     9 #include <LEDA/edge_map.h>
    10 //#include <LEDA/graph_alg.h>
    11 //#include <LEDA/dimacs.h>
    12 
    13 //#if defined(LEDA_NAMESPACE)
    14 //using namespace leda;
    15 //#endif
    16 
    17 #include <hugo/invalid.h>
    18 
    19 namespace hugo {
    20 
    21   /// \brief A graph wrapper structure for wrapping LEDA graphs in HUGO.
    22   ///
    23   /// This graph wrapper class wraps LEDA graphs and LEDA parametrized graphs
    24   /// to satisfy HUGO graph concepts.
    25   /// Then the generic HUGOlib algorithms and wrappers can be used 
    26   /// with LEDA graphs. 
    27   /// \ingroup gwrapper
    28   template<typename Graph>
    29   class LedaGraphWrapper
    30   {
    31   protected:
    32     Graph* l_graph;
    33     LedaGraphWrapper() : l_graph(0) { }
    34     void setGraph(Graph& _l_graph) { l_graph=&_l_graph; }
    35   public:
    36 
    37     /// Constructor for wrapping LEDA graphs.
    38     LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { }
    39     /// Copy constructor
    40     LedaGraphWrapper(const LedaGraphWrapper &g) : l_graph(g.l_graph) { }
    41 
    42     template <typename T> class NodeMap;
    43     template <typename T> class EdgeMap;
    44     template <typename T> class NodeMapWrapper;
    45     template <typename T> class EdgeMapWrapper;
    46 
    47     class Node;
    48     class NodeIt;
    49     class Edge;
    50     class EdgeIt;
    51     class OutEdgeIt;
    52     class InEdgeIt;
    53 
    54     /// Trivial node-iterator
    55     class Node {
    56       friend class LedaGraphWrapper<Graph>;
    57       //friend class Edge;
    58       friend class EdgeIt;
    59       friend class InEdgeIt;
    60       friend class OutEdgeIt;
    61     protected:
    62       template <typename T> friend class NodeMap;
    63       leda_node l_n;
    64     public: //FIXME
    65       Node(leda_node _l_n) : l_n(_l_n) { } 
    66     public:
    67       /// @warning The default constructor sets the iterator
    68       /// to an undefined value.
    69       Node() { }   //FIXME
    70       /// Initialize the iterator to be invalid
    71       Node(Invalid) : l_n(0) { }
    72       //Node(const Node &) {} 
    73       bool operator==(Node n) const { return l_n==n.l_n; } //FIXME
    74       bool operator!=(Node n) const { return l_n!=n.l_n; } //FIXME
    75       operator leda_node () { return l_n; }
    76     };
    77     
    78     /// This iterator goes through each node.
    79     class NodeIt : public Node {
    80     public:
    81       /// @warning The default constructor sets the iterator
    82       /// to an undefined value.
    83       NodeIt() { } //FIXME
    84       /// Initialize the iterator to be invalid
    85       NodeIt(Invalid i) : Node(i) { }
    86       /// Sets the iterator to the first node of \c G.
    87       NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph->first_node()) { }
    88       //NodeIt(const NodeIt &) {} //FIXME
    89     };
    90     
    91     /// Trivial edge-iterator.
    92     class Edge {
    93       friend class LedaGraphWrapper;
    94     protected:
    95       template <typename T> friend class EdgeMap;
    96       leda_edge l_e;
    97     public: //FIXME
    98       Edge(leda_edge _l_e) : l_e(_l_e) { } 
    99     public:
   100       /// @warning The default constructor sets the iterator
   101       /// to an undefined value.
   102       Edge() { }   //FIXME
   103       /// Initialize the iterator to be invalid
   104       Edge(Invalid) : l_e(0) { }
   105       //Edge(const Edge &) {} 
   106       bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME
   107       bool operator!=(Edge e) const { return l_e!=e.l_e; } //FIXME 
   108       operator leda_edge () { return l_e; }
   109     };
   110     
   111     /// This iterator goes trought the outgoing edges of a certain node.
   112     class OutEdgeIt : public Edge {
   113     public:
   114       /// @warning The default constructor sets the iterator
   115       /// to an undefined value.
   116       OutEdgeIt() { }
   117       /// Initialize the iterator to be invalid
   118       OutEdgeIt(Invalid i) : Edge(i) { }
   119       /// This constructor sets the iterator to first outgoing edge.
   120     
   121       /// This constructor set the iterator to the first outgoing edge of
   122       /// node
   123       ///@param n the node
   124       ///@param G the graph
   125       OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_adj_edge(n.l_n)) { }
   126     };
   127 
   128     /// This iterator goes trought the incoming edges of a certain node.
   129     class InEdgeIt : public Edge {
   130     public:
   131       /// @warning The default constructor sets the iterator
   132       /// to an undefined value.
   133       InEdgeIt() { }
   134       /// Initialize the iterator to be invalid
   135       InEdgeIt(Invalid i) : Edge(i) { }
   136       InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_in_edge(n.l_n)) { }
   137     };
   138 
   139     //  class SymEdgeIt : public Edge {};
   140     
   141     /// This iterator goes trought the edges of the graph.
   142     class EdgeIt : public Edge {
   143     public:
   144       /// @warning The default constructor sets the iterator
   145       /// to an undefined value.
   146       EdgeIt() { }
   147       /// Initialize the iterator to be invalid
   148       EdgeIt(Invalid i) : Edge(i) { }
   149       EdgeIt(const LedaGraphWrapper & G) : Edge(G.l_graph->first_edge()) { }
   150     };
   151 
   152     /// First node of the graph.
   153     ///
   154     /// \post \c i and the return value will be the first node.
   155     ///
   156     NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
   157 
   158     /// The first outgoing edge.
   159     InEdgeIt &first(InEdgeIt &i, Node n) const { 
   160       i=InEdgeIt(*this, n); 
   161       return i;
   162     }
   163     /// The first incoming edge.
   164     OutEdgeIt &first(OutEdgeIt &i, Node n) const { 
   165       i=OutEdgeIt(*this, n); 
   166       return i;
   167     }
   168     //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
   169     /// The first edge of the graph.
   170     EdgeIt &first(EdgeIt &i) const {      
   171       i=EdgeIt(*this); 
   172       return i; }
   173 
   174 //     Node getNext(Node) const {}
   175 //     InEdgeIt getNext(InEdgeIt) const {}
   176 //     OutEdgeIt getNext(OutEdgeIt) const {}
   177 //     //SymEdgeIt getNext(SymEdgeIt) const {}
   178 //     EdgeIt getNext(EdgeIt) const {}
   179 
   180     /// Go to the next node.
   181     NodeIt &next(NodeIt &i) const { 
   182       i.l_n=l_graph->succ_node(i.l_n); 
   183       return i; 
   184     }
   185     /// Go to the next incoming edge.
   186     InEdgeIt &next(InEdgeIt &i) const { 
   187       i.l_e=l_graph->in_succ(i.l_e); 
   188       return i;
   189     }
   190     /// Go to the next outgoing edge.
   191     OutEdgeIt &next(OutEdgeIt &i) const { 
   192       i.l_e=l_graph->adj_succ(i.l_e); 
   193       return i;
   194     }
   195     //SymEdgeIt &next(SymEdgeIt &) const {}
   196     /// Go to the next edge.
   197     EdgeIt &next(EdgeIt &i) const {      
   198       i.l_e=l_graph->succ_edge(i.l_e); 
   199       return i; 
   200     }
   201 
   202 //     template< typename It >
   203 //     It first() const { 
   204 //       It e;
   205 //       first(e);
   206 //       return e; 
   207 //     }
   208 
   209 //     template< typename It >
   210 //     It first(Node v) const { 
   211 //       It e;
   212 //       first(e, v);
   213 //       return e; 
   214 //     }
   215 
   216     ///Gives back the head node of an edge.
   217     Node head(Edge e) const { 
   218       return Node(l_graph->target(e.l_e)); 
   219     }
   220     ///Gives back the tail node of an edge.
   221     Node tail(Edge e) const { 
   222       return Node(l_graph->source(e.l_e)); 
   223     }
   224   
   225     Node aNode(InEdgeIt e) const { return head(e); }
   226     Node aNode(OutEdgeIt e) const { return tail(e); }
   227     //   Node aNode(SymEdgeIt) const {}
   228 
   229     Node bNode(InEdgeIt e) const { return tail(e); }
   230     Node bNode(OutEdgeIt e) const { return head(e); }
   231     //   Node bNode(SymEdgeIt) const {}
   232 
   233     /// Checks if a node iterator is valid
   234     bool valid(Node n) const { return n.l_n; }
   235     /// Checks if an edge iterator is valid
   236     bool valid(Edge e) const { return e.l_e; }
   237 
   238     ///Gives back the \e id of a node.
   239     int id(Node n) const { return n.l_n->id(); }
   240     ///Gives back the \e id of an edge.
   241     int id(Edge e) const { return e.l_e->id(); }
   242 
   243     //void setInvalid(Node &) const {};
   244     //void setInvalid(Edge &) const {};
   245   
   246     Node addNode() const { return Node(l_graph->new_node()); }
   247     Edge addEdge(Node tail, Node head) const { 
   248       return Edge(l_graph->new_edge(tail.l_n, head.l_n));
   249     }
   250     
   251     void erase(Node n) const { l_graph->del_node(n.l_n); }
   252     void erase(Edge e) const { l_graph->del_edge(e.l_e); }
   253 
   254     void clear() const { l_graph->clear(); }
   255 
   256     int nodeNum() const { return l_graph->number_of_nodes(); }
   257     int edgeNum() const { return l_graph->number_of_edges(); }
   258 
   259     /// Read/write map from the nodes to type \c T.
   260     template<typename T> class NodeMap
   261     {
   262       leda_node_map<T> leda_stuff;
   263     public:
   264       typedef T ValueType;
   265       typedef Node KeyType;
   266 
   267       NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
   268       NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
   269 
   270       void set(Node i, T t) { leda_stuff[i.l_n]=t; }
   271       T get(Node i) const { return leda_stuff[i.l_n]; }  //FIXME: Is it necessary
   272       T &operator[](Node i) { return leda_stuff[i.l_n]; }
   273       const T &operator[](Node i) const { return leda_stuff[i.l_n]; }
   274 
   275       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
   276       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
   277     };
   278 
   279     /// Read/write map from the edges to type \c T.
   280     template<typename T> class EdgeMap
   281     {
   282       leda_edge_map<T> leda_stuff;
   283     public:
   284       typedef T ValueType;
   285       typedef Edge KeyType;
   286 
   287       EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
   288       EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
   289 
   290       void set(Edge i, T t) { leda_stuff[i.l_e]=t; }
   291       T get(Edge i) const { return leda_stuff[i.l_e]; }  //FIXME: Is it necessary
   292       T &operator[](Edge i) { return leda_stuff[i.l_e]; }
   293       const T &operator[](Edge i) const { return leda_stuff[i.l_e]; }
   294 
   295       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
   296       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
   297     };
   298 
   299 
   300     /// This class is to wrap existing 
   301     /// LEDA node-maps to HUGO ones.
   302     template<typename T> class NodeMapWrapper
   303     {
   304       leda_node_array<T>* leda_stuff;
   305     public:
   306       typedef T ValueType;
   307       typedef Node KeyType;
   308 
   309       NodeMapWrapper(leda_node_array<T>& _leda_stuff) : 
   310 	leda_stuff(&_leda_stuff) { }
   311       //NodeMap(leda_node_map& &G, T t) : leda_stuff(*(G.l_graph), t) {}
   312 
   313       void set(Node i, T t) { (*leda_stuff)[i.l_n]=t; }
   314       //T get(Node i) const { return (*leda_stuff)[i.l_n]; }  //FIXME: Is it necessary
   315       T &operator[](Node i) { return (*leda_stuff)[i.l_n]; }
   316       const T &operator[](Node i) const { return (*leda_stuff)[i.l_n]; }
   317 
   318       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
   319       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
   320     };
   321 
   322     /// This class is to wrap existing 
   323     /// LEDA edge-maps to HUGO ones.
   324     template<typename T> class EdgeMapWrapper
   325     {
   326       leda_edge_array<T>* leda_stuff;
   327     public:
   328       typedef T ValueType;
   329       typedef Edge KeyType;
   330 
   331       EdgeMapWrapper(leda_edge_array<T>& _leda_stuff) : 
   332 	leda_stuff(_leda_stuff) { }
   333       //EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
   334 
   335       void set(Edge i, T t) { (*leda_stuff)[i.l_e]=t; }
   336       //T get(Edge i) const { return (*leda_stuff)[i.l_e]; }  //FIXME: Is it necessary
   337       T &operator[](Edge i) { return (*leda_stuff)[i.l_e]; }
   338       const T &operator[](Edge i) const { return (*leda_stuff)[i.l_e]; }
   339 
   340       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
   341       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
   342     };
   343 
   344     /// This class is used for access node-data of 
   345     /// LEDA parametrized graphs.
   346     template<typename T> 
   347     class NodeDataMap : public NodeMapWrapper<T>
   348     {
   349     public:
   350       NodeDataMap(LedaGraphWrapper<Graph>& LGW) : 
   351 	NodeMapWrapper<T>(*(LGW._g_graph).node_data()) { }
   352     };
   353 
   354     /// This class is used for access edge-data of 
   355     /// LEDA parametrized graphs.
   356     template<typename T> 
   357     class EdgeDataMap : public EdgeMapWrapper<T>
   358     {
   359     public:
   360       EdgeDataMap(LedaGraphWrapper<Graph>& LGW) : 
   361 	EdgeMapWrapper<T>(*(LGW._g_graph).edge_data()) { }
   362     };
   363 
   364   };
   365 
   366 
   367   /// \brief LEDA graph template.
   368   ///
   369   /// This graph stucture uses LEDA graphs for physical storage.
   370   /// \ingroup graphs
   371   template<typename Graph>
   372   class LedaGraph : public LedaGraphWrapper<Graph> {
   373     typedef LedaGraphWrapper<Graph> Parent;
   374   protected:
   375     Graph gr;
   376   public:
   377     LedaGraph() { 
   378       Parent::setGraph(gr); 
   379     }
   380   };
   381 
   382 } //namespace hugo
   383 
   384 #endif // HUGO_LEDA_GRAPH_WRAPPER_H