COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/leda/leda_graph_wrapper.h @ 987:87f7c54892df

Last change on this file since 987:87f7c54892df was 987:87f7c54892df, checked in by Alpar Juttner, 19 years ago

Naming changes:

File size: 12.1 KB
RevLine 
[189]1// -*- c++ -*-
[921]2#ifndef LEMON_LEDA_GRAPH_WRAPPER_H
3#define LEMON_LEDA_GRAPH_WRAPPER_H
[189]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
[921]17#include <lemon/invalid.h>
[189]18
[921]19namespace lemon {
[189]20
[921]21  /// \brief A graph wrapper structure for wrapping LEDA graphs in LEMON.
[617]22  ///
23  /// This graph wrapper class wraps LEDA graphs and LEDA parametrized graphs
[921]24  /// to satisfy LEMON graph concepts.
25  /// Then the generic LEMON algorithms and wrappers can be used
[409]26  /// with LEDA graphs.
[617]27  /// \ingroup gwrapper
[189]28  template<typename Graph>
29  class LedaGraphWrapper
30  {
[473]31  protected:
[617]32    Graph* l_graph;
33    LedaGraphWrapper() : l_graph(0) { }
34    void setGraph(Graph& _l_graph) { l_graph=&_l_graph; }
[189]35  public:
[650]36
37    /// Constructor for wrapping LEDA graphs.
[617]38    LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { }
[650]39    /// Copy constructor
40    LedaGraphWrapper(const LedaGraphWrapper &g) : l_graph(g.l_graph) { }
[189]41
42    template <typename T> class NodeMap;
43    template <typename T> class EdgeMap;
[646]44    template <typename T> class NodeMapWrapper;
45    template <typename T> class EdgeMapWrapper;
[189]46
[461]47    class Node;
48    class NodeIt;
49    class Edge;
50    class EdgeIt;
51    class OutEdgeIt;
52    class InEdgeIt;
53
[650]54    /// Trivial node-iterator
[189]55    class Node {
[461]56      friend class LedaGraphWrapper<Graph>;
[189]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;
[617]63      leda_node l_n;
[446]64    public: //FIXME
[617]65      Node(leda_node _l_n) : l_n(_l_n) { }
[189]66    public:
67      /// @warning The default constructor sets the iterator
68      /// to an undefined value.
[650]69      Node() { }   //FIXME
[189]70      /// Initialize the iterator to be invalid
[617]71      Node(Invalid) : l_n(0) { }
[189]72      //Node(const Node &) {}
[617]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; }
[189]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.
[650]83      NodeIt() { } //FIXME
[189]84      /// Initialize the iterator to be invalid
[650]85      NodeIt(Invalid i) : Node(i) { }
[189]86      /// Sets the iterator to the first node of \c G.
[617]87      NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph->first_node()) { }
[189]88      //NodeIt(const NodeIt &) {} //FIXME
89    };
90   
[650]91    /// Trivial edge-iterator.
[189]92    class Edge {
93      friend class LedaGraphWrapper;
94    protected:
95      template <typename T> friend class EdgeMap;
[617]96      leda_edge l_e;
[446]97    public: //FIXME
[617]98      Edge(leda_edge _l_e) : l_e(_l_e) { }
[189]99    public:
100      /// @warning The default constructor sets the iterator
101      /// to an undefined value.
[650]102      Edge() { }   //FIXME
[189]103      /// Initialize the iterator to be invalid
[650]104      Edge(Invalid) : l_e(0) { }
[189]105      //Edge(const Edge &) {}
[617]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; }
[189]109    };
110   
[650]111    /// This iterator goes trought the outgoing edges of a certain node.
[189]112    class OutEdgeIt : public Edge {
113    public:
114      /// @warning The default constructor sets the iterator
115      /// to an undefined value.
[650]116      OutEdgeIt() { }
[189]117      /// Initialize the iterator to be invalid
[650]118      OutEdgeIt(Invalid i) : Edge(i) { }
[189]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
[617]125      OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_adj_edge(n.l_n)) { }
[189]126    };
127
[650]128    /// This iterator goes trought the incoming edges of a certain node.
[189]129    class InEdgeIt : public Edge {
130    public:
131      /// @warning The default constructor sets the iterator
132      /// to an undefined value.
[650]133      InEdgeIt() { }
[189]134      /// Initialize the iterator to be invalid
[650]135      InEdgeIt(Invalid i) : Edge(i) { }
[617]136      InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_in_edge(n.l_n)) { }
[189]137    };
138
139    //  class SymEdgeIt : public Edge {};
[650]140   
141    /// This iterator goes trought the edges of the graph.
[189]142    class EdgeIt : public Edge {
143    public:
144      /// @warning The default constructor sets the iterator
145      /// to an undefined value.
[650]146      EdgeIt() { }
[189]147      /// Initialize the iterator to be invalid
[650]148      EdgeIt(Invalid i) : Edge(i) { }
[617]149      EdgeIt(const LedaGraphWrapper & G) : Edge(G.l_graph->first_edge()) { }
[189]150    };
151
152    /// First node of the graph.
[650]153    ///
[189]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;}
[650]169    /// The first edge of the graph.
[189]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 {
[617]182      i.l_n=l_graph->succ_node(i.l_n);
[189]183      return i;
184    }
185    /// Go to the next incoming edge.
186    InEdgeIt &next(InEdgeIt &i) const {
[617]187      i.l_e=l_graph->in_succ(i.l_e);
[189]188      return i;
189    }
190    /// Go to the next outgoing edge.
191    OutEdgeIt &next(OutEdgeIt &i) const {
[617]192      i.l_e=l_graph->adj_succ(i.l_e);
[189]193      return i;
194    }
195    //SymEdgeIt &next(SymEdgeIt &) const {}
196    /// Go to the next edge.
197    EdgeIt &next(EdgeIt &i) const {     
[617]198      i.l_e=l_graph->succ_edge(i.l_e);
[189]199      return i;
200    }
201
[409]202//     template< typename It >
203//     It first() const {
204//       It e;
205//       first(e);
206//       return e;
207//     }
[189]208
[409]209//     template< typename It >
210//     It first(Node v) const {
211//       It e;
212//       first(e, v);
213//       return e;
214//     }
[189]215
[986]216    ///Gives back the target node of an edge.
217    Node target(Edge e) const {
[617]218      return Node(l_graph->target(e.l_e));
[189]219    }
[986]220    ///Gives back the source node of an edge.
221    Node source(Edge e) const {
[617]222      return Node(l_graph->source(e.l_e));
[189]223    }
224 
[986]225    Node aNode(InEdgeIt e) const { return target(e); }
226    Node aNode(OutEdgeIt e) const { return source(e); }
[189]227    //   Node aNode(SymEdgeIt) const {}
228
[986]229    Node bNode(InEdgeIt e) const { return source(e); }
230    Node bNode(OutEdgeIt e) const { return target(e); }
[189]231    //   Node bNode(SymEdgeIt) const {}
232
233    /// Checks if a node iterator is valid
[617]234    bool valid(Node n) const { return n.l_n; }
[189]235    /// Checks if an edge iterator is valid
[617]236    bool valid(Edge e) const { return e.l_e; }
[189]237
238    ///Gives back the \e id of a node.
[617]239    int id(Node n) const { return n.l_n->id(); }
[189]240    ///Gives back the \e id of an edge.
[617]241    int id(Edge e) const { return e.l_e->id(); }
[189]242
243    //void setInvalid(Node &) const {};
244    //void setInvalid(Edge &) const {};
245 
[617]246    Node addNode() const { return Node(l_graph->new_node()); }
[986]247    Edge addEdge(Node source, Node target) const {
248      return Edge(l_graph->new_edge(source.l_n, target.l_n));
[189]249    }
250   
[617]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); }
[189]253
[617]254    void clear() const { l_graph->clear(); }
[189]255
[617]256    int nodeNum() const { return l_graph->number_of_nodes(); }
257    int edgeNum() const { return l_graph->number_of_edges(); }
[189]258
[650]259    /// Read/write map from the nodes to type \c T.
[189]260    template<typename T> class NodeMap
261    {
262      leda_node_map<T> leda_stuff;
263    public:
[987]264      typedef T Value;
265      typedef Node Key;
[189]266
[617]267      NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
268      NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
[189]269
[617]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]; }
[189]274
275      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
[617]276      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
[189]277    };
278
[650]279    /// Read/write map from the edges to type \c T.
[189]280    template<typename T> class EdgeMap
281    {
282      leda_edge_map<T> leda_stuff;
283    public:
[987]284      typedef T Value;
285      typedef Edge Key;
[189]286
[617]287      EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
288      EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
[189]289
[617]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]; }
[189]294
295      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
[617]296      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
[189]297    };
298
[646]299
[650]300    /// This class is to wrap existing
[921]301    /// LEDA node-maps to LEMON ones.
[646]302    template<typename T> class NodeMapWrapper
303    {
[650]304      leda_node_array<T>* leda_stuff;
[646]305    public:
[987]306      typedef T Value;
307      typedef Node Key;
[646]308
[650]309      NodeMapWrapper(leda_node_array<T>& _leda_stuff) :
[646]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; }
[650]314      //T get(Node i) const { return (*leda_stuff)[i.l_n]; }  //FIXME: Is it necessary
[646]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
[650]322    /// This class is to wrap existing
[921]323    /// LEDA edge-maps to LEMON ones.
[646]324    template<typename T> class EdgeMapWrapper
325    {
[650]326      leda_edge_array<T>* leda_stuff;
[646]327    public:
[987]328      typedef T Value;
329      typedef Edge Key;
[646]330
[650]331      EdgeMapWrapper(leda_edge_array<T>& _leda_stuff) :
[646]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; }
[650]336      //T get(Edge i) const { return (*leda_stuff)[i.l_e]; }  //FIXME: Is it necessary
[646]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
[650]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
[189]364  };
365
[617]366
367  /// \brief LEDA graph template.
368  ///
369  /// This graph stucture uses LEDA graphs for physical storage.
370  /// \ingroup graphs
[473]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
[921]382} //namespace lemon
[189]383
[921]384#endif // LEMON_LEDA_GRAPH_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.