COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/merge_node_graph_wrapper.h @ 1009:8cb323dbae93

Last change on this file since 1009:8cb323dbae93 was 1009:8cb323dbae93, checked in by marci, 20 years ago

RoadMap? to STGraphWrapper

File size: 17.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  /*! A base class for merging the node-set of two node-disjoint graphs
42    into the node-set of one graph.
43   */
44  template <typename _Graph1, typename _Graph2, typename Enable=void>
45  class MergeNodeGraphWrapperBase :
46    public P1<_Graph1>, public P2<_Graph2> {
47  public:
48    void printNode() const { std::cout << "generic" << std::endl; }
49    typedef _Graph1 Graph1;
50    typedef _Graph2 Graph2;
51    typedef P1<_Graph1> Parent1;
52    typedef P2<_Graph2> Parent2;
53    typedef typename Parent1::Node Graph1Node;
54    typedef typename Parent2::Node Graph2Node;
55  protected:
56    MergeNodeGraphWrapperBase() { }
57  public:
58    template <typename _Value> class NodeMap;
59
60    class Node : public Graph1Node, public Graph2Node {
61      friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
62      template <typename Value> friend class NodeMap;
63    protected:
64      bool backward; //true, iff backward
65    public:
66      Node() { }
67      /// \todo =false is needed, or causes problems?
68      /// If \c _backward is false, then we get an edge corresponding to the
69      /// original one, otherwise its oppositely directed pair is obtained.
70      Node(const Graph1Node& n1,
71           const Graph2Node& n2, bool _backward) :
72        Graph1Node(n1), Graph2Node(n2), backward(_backward) { }
73      Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }
74      bool operator==(const Node& v) const {
75        return (this->backward==v.backward &&
76                static_cast<Graph1Node>(*this)==
77                static_cast<Graph1Node>(v) &&
78                static_cast<Graph2Node>(*this)==
79                static_cast<Graph2Node>(v));
80      }
81      bool operator!=(const Node& v) const {
82        return (this->backward!=v.backward ||
83                static_cast<Graph1Node>(*this)!=
84                static_cast<Graph1Node>(v) ||
85                static_cast<Graph2Node>(*this)!=
86                static_cast<Graph2Node>(v));
87      }
88    };
89
90    //typedef void Edge;
91    class Edge { };
92   
93    void first(Node& i) const {
94      Parent1::graph->first(*static_cast<Graph1Node*>(&i));
95      i.backward=false;
96      if (*static_cast<Graph1Node*>(&i)==INVALID) {
97        Parent2::graph->first(*static_cast<Graph2Node*>(&i));
98        i.backward=true;
99      }
100    }
101    void next(Node& i) const {
102      if (!(i.backward)) {
103        Parent1::graph->next(*static_cast<Graph1Node*>(&i));
104        if (*static_cast<Graph1Node*>(&i)==INVALID) {
105          Parent2::graph->first(*static_cast<Graph2Node*>(&i));
106          i.backward=true;
107        }
108      } else {
109        Parent2::graph->next(*static_cast<Graph2Node*>(&i));
110      }
111    }
112
113    int id(const Node& n) const {
114      if (!n.backward)
115        return this->Parent1::graph->id(n);
116      else
117        return this->Parent2::graph->id(n);
118    }
119
120    template <typename _Value>
121    class NodeMap : public Parent1::template NodeMap<_Value>,
122                    public Parent2::template NodeMap<_Value> {
123      typedef typename Parent1::template NodeMap<_Value> ParentMap1;
124      typedef typename Parent2::template NodeMap<_Value> ParentMap2;
125    public:
126      typedef _Value Value;
127      typedef Node Key;
128      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
129        ParentMap1(gw), ParentMap2(gw) { }
130      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
131              const _Value& value) :
132        ParentMap1(gw, value), ParentMap2(gw, value) { }
133      _Value operator[](const Node& n) const {
134        if (!n.backward)
135          return ParentMap1::operator[](n);
136        else
137          return ParentMap2::operator[](n);
138      }
139      void set(const Node& n, const _Value& value) {
140        if (!n.backward)
141          ParentMap1::set(n, value);
142        else
143          ParentMap2::set(n, value);
144      }
145//       using ParentMap1::operator[];
146//       using ParentMap2::operator[];
147    };
148
149  };
150
151  //not yet working
152  template <typename _Graph1, typename _Graph2>
153  class MergeNodeGraphWrapperBase<
154    _Graph1, _Graph2, typename boost::enable_if<
155    boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
156    public P1<_Graph1>, public P2<_Graph2> {
157  public :
158    void printNode() const { std::cout << "same" << std::endl; }
159    typedef _Graph1 Graph1;
160    typedef _Graph2 Graph2;
161    typedef P1<_Graph1> Parent1;
162    typedef P2<_Graph2> Parent2;
163    typedef typename Parent1::Node Graph1Node;
164    typedef typename Parent2::Node Graph2Node;
165  protected:
166    MergeNodeGraphWrapperBase() { }
167  public:
168    class Node { };
169    class Edge { };
170    void first() const;
171    void next() const;
172  };
173
174  //not yet working
175  template <typename _Graph1, typename _Graph2>
176  class MergeNodeGraphWrapperBase<
177    _Graph1, _Graph2, typename boost::enable_if<
178    boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
179    public P1<_Graph1>, public P2<_Graph2> {
180  public :
181    void printNode() const { std::cout << "2. nagyobb" << std::endl; }
182    typedef _Graph1 Graph1;
183    typedef _Graph2 Graph2;
184    typedef P1<_Graph1> Parent1;
185    typedef P2<_Graph2> Parent2;
186    typedef typename Parent1::Node Graph1Node;
187    typedef typename Parent2::Node Graph2Node;
188  protected:
189    MergeNodeGraphWrapperBase() { }
190  public:
191    class Node { };
192    class Edge { };
193    void first() const;
194    void next() const;
195  };
196
197  //not yet working
198  template <typename _Graph1, typename _Graph2>
199  class MergeNodeGraphWrapperBase<
200    _Graph1, _Graph2, typename boost::enable_if<
201    boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
202    public P1<_Graph1>, public P2<_Graph2> {
203  public :
204    void printNode() const { std::cout << "1. nagyobb" << std::endl; }
205    typedef _Graph1 Graph1;
206    typedef _Graph2 Graph2;
207    typedef P1<_Graph1> Parent1;
208    typedef P2<_Graph2> Parent2;
209    typedef typename Parent1::Node Graph1Node;
210    typedef typename Parent2::Node Graph2Node;
211  protected:
212    MergeNodeGraphWrapperBase() { }
213  public:
214    class Node { };
215    class Edge { };
216    void first() const;
217    void next() const;
218  };
219
220
221  template <typename _Graph1, typename _Graph2>
222  class MergeNodeGraphWrapper : public
223  IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
224  public:
225    typedef _Graph1 Graph1;
226    typedef _Graph2 Graph2;
227    typedef IterableGraphExtender<
228      MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
229  protected:
230    MergeNodeGraphWrapper() { }
231  public:
232    MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
233      Parent::Parent1::setGraph(_graph1);
234      Parent::Parent2::setGraph(_graph2);
235    }
236  };
237
238
239  /*! A base class for merging the node-sets and edge-sets of
240    two node-disjoint graphs
241    into one graph.
242   */
243  template <typename _Graph1, typename _Graph2, typename Enable=void>
244  class MergeEdgeGraphWrapperBase :
245    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
246  public:
247    void printEdge() const { std::cout << "generic" << std::endl; }
248    typedef _Graph1 Graph1;
249    typedef _Graph2 Graph2;
250    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
251    typedef typename Parent::Parent1 Parent1;
252    typedef typename Parent::Parent2 Parent2;
253//     typedef P1<_Graph1> Parent1;
254//     typedef P2<_Graph2> Parent2;
255    typedef typename Parent1::Edge Graph1Edge;
256    typedef typename Parent2::Edge Graph2Edge;
257  protected:
258    MergeEdgeGraphWrapperBase() { }
259  public:
260    template <typename _Value> class EdgeMap;
261
262    typedef typename Parent::Node Node;
263
264    class Edge : public Graph1Edge, public Graph2Edge {
265      friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
266      template <typename Value> friend class EdgeMap;
267    protected:
268      bool backward; //true, iff backward
269    public:
270      Edge() { }
271      /// \todo =false is needed, or causes problems?
272      /// If \c _backward is false, then we get an edge corresponding to the
273      /// original one, otherwise its oppositely directed pair is obtained.
274      Edge(const Graph1Edge& n1,
275           const Graph2Edge& n2, bool _backward) :
276        Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
277      Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
278      bool operator==(const Edge& v) const {
279        return (this->backward==v.backward &&
280                static_cast<Graph1Edge>(*this)==
281                static_cast<Graph1Edge>(v) &&
282                static_cast<Graph2Edge>(*this)==
283                static_cast<Graph2Edge>(v));
284      }
285      bool operator!=(const Edge& v) const {
286        return (this->backward!=v.backward ||
287                static_cast<Graph1Edge>(*this)!=
288                static_cast<Graph1Edge>(v) ||
289                static_cast<Graph2Edge>(*this)!=
290                static_cast<Graph2Edge>(v));
291      }
292    };
293
294    using Parent::first;
295    void first(Edge& i) const {
296      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
297      i.backward=false;
298      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
299        Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
300        i.backward=true;
301      }
302    }
303    void firstIn(Edge& i, const Node& n) const {
304      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
305      i.backward=false;
306      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
307        Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
308        i.backward=true;
309      }
310    }
311    void firstOut(Edge& i, const Node& n) const {
312      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
313      i.backward=false;
314      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
315        Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
316        i.backward=true;
317      }
318    }
319
320    using Parent::next;
321    void next(Edge& i) const {
322      if (!(i.backward)) {
323        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
324        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
325          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
326          i.backward=true;
327        }
328      } else {
329        Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
330      }
331    }
332    void nextIn(Edge& i) const {
333      if (!(i.backward)) {
334        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
335        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
336          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
337          i.backward=true;
338        }
339      } else {
340        Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
341      }
342    }
343    void nextOut(Edge& i) const {
344      if (!(i.backward)) {
345        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
346        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
347          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
348          i.backward=true;
349        }
350      } else {
351        Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
352      }
353    }
354
355    Node source(const Edge& i) const {
356      if (!(i.backward)) {
357        return
358          Node(Parent1::graph->source(i), INVALID, false);
359      } else {
360        return
361          Node(INVALID, Parent2::graph->source(i), true);
362      }
363    }
364
365    Node target(const Edge& i) const {
366      if (!(i.backward)) {
367        return
368          Node(Parent1::graph->target(i), INVALID, false);
369      } else {
370        return
371          Node(INVALID, Parent2::graph->target(i), true);
372      }
373    }
374
375    using Parent::id;
376    int id(const Edge& n) const {
377      if (!n.backward)
378        return this->Parent1::graph->id(n);
379      else
380        return this->Parent2::graph->id(n);
381    }
382
383    template <typename _Value>
384    class EdgeMap : public Parent1::template EdgeMap<_Value>,
385                    public Parent2::template EdgeMap<_Value> {
386      typedef typename Parent1::template EdgeMap<_Value> ParentMap1;
387      typedef typename Parent2::template EdgeMap<_Value> ParentMap2;
388    public:
389      typedef _Value Value;
390      typedef Edge Key;
391      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
392        ParentMap1(gw), ParentMap2(gw) { }
393      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
394              const _Value& value) :
395        ParentMap1(gw, value), ParentMap2(gw, value) { }
396      _Value operator[](const Edge& n) const {
397        if (!n.backward)
398          return ParentMap1::operator[](n);
399        else
400          return ParentMap2::operator[](n);
401      }
402      void set(const Edge& n, const _Value& value) {
403        if (!n.backward)
404          ParentMap1::set(n, value);
405        else
406          ParentMap2::set(n, value);
407      }
408//       using ParentMap1::operator[];
409//       using ParentMap2::operator[];
410    };
411
412  };
413
414
415  template <typename _Graph1, typename _Graph2>
416  class MergeEdgeGraphWrapper : public
417  IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
418  public:
419    typedef _Graph1 Graph1;
420    typedef _Graph2 Graph2;
421    typedef IterableGraphExtender<
422      MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
423  protected:
424    MergeEdgeGraphWrapper() { }
425  public:
426    MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
427      Parent::Parent1::setGraph(_graph1);
428      Parent::Parent2::setGraph(_graph2);
429    }
430  };
431
432 
433  template <typename _Graph, typename _EdgeSetGraph>
434  class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
435  public:
436    typedef GraphWrapperBase<_Graph> Parent;
437    typedef _Graph Graph;
438    typedef _EdgeSetGraph EdgeSetGraph;
439    typedef typename _Graph::Node Node;
440    typedef typename _EdgeSetGraph::Node ENode;
441  protected:
442    EdgeSetGraph* edge_set_graph;
443    typename Graph::NodeMap<ENode>* e_node;
444    typename EdgeSetGraph::NodeMap<Node>* n_node;
445    void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) {
446      edge_set_graph=&_edge_set_graph;
447    }
448    /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
449    void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) {
450      n_node=&_n_node;
451    }
452    /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
453    void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) {
454      e_node=&_e_node;
455    }
456  public:
457    class Edge : public EdgeSetGraph::Edge {
458      typedef typename EdgeSetGraph::Edge Parent;
459    public:
460      Edge() { }
461      Edge(const Parent& e) : Parent(e) { }
462      Edge(Invalid i) : Parent(i) { }
463    };
464
465    using Parent::first;
466    void first(Edge &e) const {
467      edge_set_graph->first(e);
468    }
469    void firstOut(Edge& e, const Node& n) const {
470//       cout << e_node << endl;
471//       cout << n_node << endl;
472      edge_set_graph->firstOut(e, (*e_node)[n]);
473    }
474    void firstIn(Edge& e, const Node& n) const {
475      edge_set_graph->firstIn(e, (*e_node)[n]);
476    }
477
478    using Parent::next;
479    void next(Edge &e) const {
480      edge_set_graph->next(e);
481    }
482    void nextOut(Edge& e) const {
483      edge_set_graph->nextOut(e);
484    }
485    void nextIn(Edge& e) const {
486      edge_set_graph->nextIn(e);
487    }
488
489    Node source(const Edge& e) const {
490      return (*n_node)[edge_set_graph->source(e)];
491    }
492    Node target(const Edge& e) const {
493      return (*n_node)[edge_set_graph->target(e)];
494    }
495
496    int edgeNum() const { return edge_set_graph->edgeNum(); }
497
498    Edge addEdge(const Node& u, const Node& v) {
499      return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
500    }
501
502    using Parent::erase;
503    void erase(const Edge& i) const { edge_set_graph->erase(i); }
504 
505    void clear() const { Parent::clear(); edge_set_graph->clear(); }
506
507    bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
508    bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
509
510    using Parent::id;
511    int id(const Edge& e) const { return edge_set_graph->id(e); }
512   
513    Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
514
515    template <typename _Value>
516    class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
517    public:
518      typedef typename EdgeSetGraph::EdgeMap<_Value> Parent;
519      typedef _Value Value;
520      typedef Edge Key;
521      EdgeMap(const NewEdgeSetGraphWrapperBase& gw) :
522        Parent(*(gw.edge_set_graph)) { }
523      EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) :
524        Parent(*(gw.edge_set_graph), _value) { }
525    };
526
527  };
528
529  template <typename _Graph, typename _EdgeSetGraph>
530  class NewEdgeSetGraphWrapper :
531    public IterableGraphExtender<
532    NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
533  public:
534    typedef _Graph Graph;
535    typedef _EdgeSetGraph EdgeSetGraph;
536    typedef IterableGraphExtender<
537      NewEdgeSetGraphWrapper<_Graph, _EdgeSetGraph> > Parent;
538  protected:
539    NewEdgeSetGraphWrapper() { }
540  public:
541    NewEdgeSetGraphWrapper(_Graph& _graph,
542                           _EdgeSetGraph& _edge_set_graph,
543                           typename _Graph::
544                           NodeMap<typename _EdgeSetGraph::Node>& _e_node,
545                           typename _EdgeSetGraph::
546                           NodeMap<typename _Graph::Node>& _n_node) {
547      setGraph(_graph);
548      setEdgeSetGraph(_edge_set_graph);
549      setNodeMap(_n_node);
550      setENodeMap(_e_node);
551    }
552  };
553
554} //namespace lemon
555
556#endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.