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