COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/merge_node_graph_wrapper.h @ 1008:3fef334f5f37

Last change on this file since 1008:3fef334f5f37 was 1008:3fef334f5f37, checked in by marci, 17 years ago

RoadMap? to MergeGraphWrapper? and STGraphWrapper,
NewEdgeSetGraphWrapper? which is similar to the old EdgeSet?

File size: 11.0 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/merge_node_graph_wrapper.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_MERGE_NODE_GRAPH_WRAPPER_H
18#define LEMON_MERGE_NODE_GRAPH_WRAPPER_H
19
20#include <lemon/invalid.h>
21#include <lemon/maps.h>
22#include <lemon/map_defines.h>
23#include <lemon/graph_wrapper.h>
24#include <iostream>
25using std::cout;
26using std::endl;
27
28#include <boost/type_traits.hpp>
29#include <boost/utility/enable_if.hpp>
30
31namespace lemon {
32
33  template <class _Graph1>
34  class P1 : public GraphWrapperBase<_Graph1> {
35  };
36
37  template <class _Graph2>
38  class P2 : public GraphWrapperBase<_Graph2> {
39  };
40
41  template <typename _Graph1, typename _Graph2, typename Enable=void>
42  class MergeNodeGraphWrapperBase :
43    public P1<_Graph1>, public P2<_Graph2> {
44  public:
45    void print() const { std::cout << "generic" << std::endl; }
46    typedef _Graph1 Graph1;
47    typedef _Graph2 Graph2;
48    typedef P1<_Graph1> Parent1;
49    typedef P2<_Graph2> Parent2;
50    typedef typename Parent1::Node Graph1Node;
51    typedef typename Parent2::Node Graph2Node;
52  protected:
53    MergeNodeGraphWrapperBase() { }
54  public:
55    template <typename _Value> class NodeMap;
56
57    class Node : public Graph1Node, public Graph2Node {
58      friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
59      template <typename Value> friend class NodeMap;
60    protected:
61      bool backward; //true, iff backward
62    public:
63      Node() { }
64      /// \todo =false is needed, or causes problems?
65      /// If \c _backward is false, then we get an edge corresponding to the
66      /// original one, otherwise its oppositely directed pair is obtained.
67      Node(const Graph1Node& n1,
68           const Graph2Node& n2, bool _backward) :
69        Graph1Node(n1), Graph2Node(n2), backward(_backward) { }
70      Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }
71      bool operator==(const Node& v) const {
72        return (this->backward==v.backward &&
73                static_cast<Graph1Node>(*this)==
74                static_cast<Graph1Node>(v) &&
75                static_cast<Graph2Node>(*this)==
76                static_cast<Graph2Node>(v));
77      }
78      bool operator!=(const Node& v) const {
79        return (this->backward!=v.backward ||
80                static_cast<Graph1Node>(*this)!=
81                static_cast<Graph1Node>(v) ||
82                static_cast<Graph2Node>(*this)!=
83                static_cast<Graph2Node>(v));
84      }
85    };
86
87    //typedef void Edge;
88    class Edge { };
89   
90    void first(Node& i) const {
91      Parent1::graph->first(*static_cast<Graph1Node*>(&i));
92      i.backward=false;
93      if (*static_cast<Graph1Node*>(&i)==INVALID) {
94        Parent2::graph->first(*static_cast<Graph2Node*>(&i));
95        i.backward=true;
96      }
97    }
98    void next(Node& i) const {
99      if (!(i.backward)) {
100        Parent1::graph->next(*static_cast<Graph1Node*>(&i));
101        if (*static_cast<Graph1Node*>(&i)==INVALID) {
102          Parent2::graph->first(*static_cast<Graph2Node*>(&i));
103          i.backward=true;
104        }
105      } else {
106        Parent2::graph->next(*static_cast<Graph2Node*>(&i));
107      }
108    }
109
110    int id(const Node& n) const {
111      if (!n.backward)
112        return this->Parent1::graph->id(n);
113      else
114        return this->Parent2::graph->id(n);
115    }
116
117    template <typename _Value>
118    class NodeMap : public Parent1::template NodeMap<_Value>,
119                    public Parent2::template NodeMap<_Value> {
120      typedef typename Parent1::template NodeMap<_Value> ParentMap1;
121      typedef typename Parent2::template NodeMap<_Value> ParentMap2;
122    public:
123      typedef _Value Value;
124      typedef Node Key;
125      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
126        ParentMap1(gw), ParentMap2(gw) { }
127      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
128              const _Value& value) :
129        ParentMap1(gw, value), ParentMap2(gw, value) { }
130      _Value operator[](const Node& n) const {
131        if (!n.backward)
132          return ParentMap1::operator[](n);
133        else
134          return ParentMap2::operator[](n);
135      }
136      void set(const Node& n, const _Value& value) {
137        if (!n.backward)
138          ParentMap1::set(n, value);
139        else
140          ParentMap2::set(n, value);
141      }
142      using ParentMap1::operator[];
143      using ParentMap2::operator[];
144    };
145
146  };
147
148  //not yet working
149  template <typename _Graph1, typename _Graph2>
150  class MergeNodeGraphWrapperBase<
151    _Graph1, _Graph2, typename boost::enable_if<
152    boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
153    public P1<_Graph1>, public P2<_Graph2> {
154  public :
155    void print() const { std::cout << "same" << std::endl; }
156    typedef _Graph1 Graph1;
157    typedef _Graph2 Graph2;
158    typedef P1<_Graph1> Parent1;
159    typedef P2<_Graph2> Parent2;
160    typedef typename Parent1::Node Graph1Node;
161    typedef typename Parent2::Node Graph2Node;
162  protected:
163    MergeNodeGraphWrapperBase() { }
164  public:
165    class Node { };
166    class Edge { };
167    void first() const;
168    void next() const;
169  };
170
171  //not yet working
172  template <typename _Graph1, typename _Graph2>
173  class MergeNodeGraphWrapperBase<
174    _Graph1, _Graph2, typename boost::enable_if<
175    boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
176    public P1<_Graph1>, public P2<_Graph2> {
177  public :
178    void print() const { std::cout << "2. nagyobb" << std::endl; }
179    typedef _Graph1 Graph1;
180    typedef _Graph2 Graph2;
181    typedef P1<_Graph1> Parent1;
182    typedef P2<_Graph2> Parent2;
183    typedef typename Parent1::Node Graph1Node;
184    typedef typename Parent2::Node Graph2Node;
185  protected:
186    MergeNodeGraphWrapperBase() { }
187  public:
188    class Node { };
189    class Edge { };
190    void first() const;
191    void next() const;
192  };
193
194  //not yet working
195  template <typename _Graph1, typename _Graph2>
196  class MergeNodeGraphWrapperBase<
197    _Graph1, _Graph2, typename boost::enable_if<
198    boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
199    public P1<_Graph1>, public P2<_Graph2> {
200  public :
201    void print() const { std::cout << "1. nagyobb" << std::endl; }
202    typedef _Graph1 Graph1;
203    typedef _Graph2 Graph2;
204    typedef P1<_Graph1> Parent1;
205    typedef P2<_Graph2> Parent2;
206    typedef typename Parent1::Node Graph1Node;
207    typedef typename Parent2::Node Graph2Node;
208  protected:
209    MergeNodeGraphWrapperBase() { }
210  public:
211    class Node { };
212    class Edge { };
213    void first() const;
214    void next() const;
215  };
216
217
218  template <typename _Graph1, typename _Graph2, typename Enable=void>
219  class MergeNodeGraphWrapper : public
220  IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2, Enable> > {
221  public:
222    typedef _Graph1 Graph1;
223    typedef _Graph2 Graph2;
224    typedef IterableGraphExtender<
225      MergeNodeGraphWrapperBase<_Graph1, _Graph2, Enable> > Parent;
226  protected:
227    MergeNodeGraphWrapper() { }
228  public:
229    MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
230      Parent::Parent1::setGraph(_graph1);
231      Parent::Parent2::setGraph(_graph2);
232    }
233  };
234
235 
236  template <typename _Graph, typename _EdgeSetGraph>
237  class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
238  public:
239    typedef GraphWrapperBase<_Graph> Parent;
240    typedef _Graph Graph;
241    typedef _EdgeSetGraph EdgeSetGraph;
242    typedef typename _Graph::Node Node;
243    typedef typename _EdgeSetGraph::Node ENode;
244  protected:
245    EdgeSetGraph* edge_set_graph;
246    typename Graph::NodeMap<ENode>* e_node;
247    typename EdgeSetGraph::NodeMap<Node>* n_node;
248    void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) {
249      edge_set_graph=&_edge_set_graph;
250    }
251    /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
252    void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) {
253      n_node=&_n_node;
254    }
255    /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
256    void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) {
257      e_node=&_e_node;
258    }
259  public:
260    class Edge : public EdgeSetGraph::Edge {
261      typedef typename EdgeSetGraph::Edge Parent;
262    public:
263      Edge() { }
264      Edge(const Parent& e) : Parent(e) { }
265      Edge(Invalid i) : Parent(i) { }
266    };
267
268    using Parent::first;
269    void first(Edge &e) const {
270      edge_set_graph->first(e);
271    }
272    void firstOut(Edge& e, const Node& n) const {
273//       cout << e_node << endl;
274//       cout << n_node << endl;
275      edge_set_graph->firstOut(e, (*e_node)[n]);
276    }
277    void firstIn(Edge& e, const Node& n) const {
278      edge_set_graph->firstIn(e, (*e_node)[n]);
279    }
280
281    using Parent::next;
282    void next(Edge &e) const {
283      edge_set_graph->next(e);
284    }
285    void nextOut(Edge& e) const {
286      edge_set_graph->nextOut(e);
287    }
288    void nextIn(Edge& e) const {
289      edge_set_graph->nextIn(e);
290    }
291
292    Node source(const Edge& e) const {
293      return (*n_node)[edge_set_graph->source(e)];
294    }
295    Node target(const Edge& e) const {
296      return (*n_node)[edge_set_graph->target(e)];
297    }
298
299    int edgeNum() const { return edge_set_graph->edgeNum(); }
300
301    Edge addEdge(const Node& u, const Node& v) {
302      return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
303    }
304
305    using Parent::erase;
306    void erase(const Edge& i) const { edge_set_graph->erase(i); }
307 
308    void clear() const { Parent::clear(); edge_set_graph->clear(); }
309
310    bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
311    bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
312
313    using Parent::id;
314    int id(const Edge& e) const { return edge_set_graph->id(e); }
315   
316    Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
317
318    template <typename _Value>
319    class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
320    public:
321      typedef typename EdgeSetGraph::EdgeMap<_Value> Parent;
322      typedef _Value Value;
323      typedef Edge Key;
324      EdgeMap(const NewEdgeSetGraphWrapperBase& gw) :
325        Parent(*(gw.edge_set_graph)) { }
326      EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) :
327        Parent(*(gw.edge_set_graph), _value) { }
328    };
329
330  };
331
332  template <typename _Graph, typename _EdgeSetGraph>
333  class NewEdgeSetGraphWrapper :
334    public IterableGraphExtender<
335    NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
336  public:
337    typedef _Graph Graph;
338    typedef _EdgeSetGraph EdgeSetGraph;
339    typedef IterableGraphExtender<
340      NewEdgeSetGraphWrapper<_Graph, _EdgeSetGraph> > Parent;
341  protected:
342    NewEdgeSetGraphWrapper() { }
343  public:
344    NewEdgeSetGraphWrapper(_Graph& _graph,
345                           _EdgeSetGraph& _edge_set_graph,
346                           typename _Graph::
347                           NodeMap<typename _EdgeSetGraph::Node>& _e_node,
348                           typename _EdgeSetGraph::
349                           NodeMap<typename _Graph::Node>& _n_node) {
350      setGraph(_graph);
351      setEdgeSetGraph(_edge_set_graph);
352      setNodeMap(_n_node);
353      setENodeMap(_e_node);
354    }
355  };
356
357} //namespace lemon
358
359#endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.