1.1 --- a/src/work/marci/bipartite_graph_wrapper.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,933 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef LEMON_BIPARTITE_GRAPH_WRAPPER_H
1.6 -#define LEMON_BIPARTITE_GRAPH_WRAPPER_H
1.7 -
1.8 -///\ingroup gwrappers
1.9 -///\file
1.10 -///\brief Several graph wrappers.
1.11 -///
1.12 -///This file contains several useful graph wrapper functions.
1.13 -///
1.14 -///\author Marton Makai
1.15 -
1.16 -#include <lemon/invalid.h>
1.17 -#include <iter_map.h>
1.18 -#include <lemon/graph_wrapper.h>
1.19 -#include <for_each_macros.h>
1.20 -
1.21 -namespace lemon {
1.22 -
1.23 - /// \brief A wrapper for composing a bipartite graph from a graph
1.24 - /// and from a node-map showing for any node which color class it belongs to.
1.25 - ///
1.26 - /// A wrapper for composing a bipartite graph.
1.27 - /// \c _graph have to be a reference to a graph of type \c Graph
1.28 - /// and \c _s_false_t_true_map is an \c IterableBoolMap
1.29 - /// reference containing the elements for the
1.30 - /// color classes S and T. \c _graph is to be referred to an undirected
1.31 - /// graph or a directed graph with edges oriented from S to T.
1.32 - ///
1.33 - /// \author Marton Makai
1.34 - template<typename Graph>
1.35 - class BipartiteGraphWrapper : public GraphWrapper<Graph> {
1.36 - public:
1.37 - typedef IterableBoolMap< typename Graph::template NodeMap<int> >
1.38 - SFalseTTrueMap;
1.39 - protected:
1.40 - SFalseTTrueMap* s_false_t_true_map;
1.41 -
1.42 - BipartiteGraphWrapper() : GraphWrapper<Graph>()/*,
1.43 - S_CLASS(false), T_CLASS(true)*/ { }
1.44 - void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) {
1.45 - s_false_t_true_map=&_s_false_t_true_map;
1.46 - }
1.47 -
1.48 - public:
1.49 - //marci
1.50 - //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
1.51 - static const bool S_CLASS;
1.52 - static const bool T_CLASS;
1.53 -
1.54 - /// This method is to reach the iterable maps of the bipartite graph or
1.55 - /// bipartite graph wrapper.
1.56 - const SFalseTTrueMap& sFalseTTrueMap() const {
1.57 - return *s_false_t_true_map;
1.58 - }
1.59 -
1.60 - //bool S_CLASS;
1.61 - //bool T_CLASS;
1.62 -
1.63 - BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
1.64 - : GraphWrapper<Graph>(_graph),
1.65 - s_false_t_true_map(&_s_false_t_true_map)/*,
1.66 - S_CLASS(false), T_CLASS(true)*/ { }
1.67 - typedef typename GraphWrapper<Graph>::Node Node;
1.68 - //using GraphWrapper<Graph>::NodeIt;
1.69 - typedef typename GraphWrapper<Graph>::Edge Edge;
1.70 - //using GraphWrapper<Graph>::EdgeIt;
1.71 - class ClassNodeIt;
1.72 - friend class ClassNodeIt;
1.73 - class OutEdgeIt;
1.74 - friend class OutEdgeIt;
1.75 - class InEdgeIt;
1.76 - friend class InEdgeIt;
1.77 - class ClassNodeIt : public Node {
1.78 - friend class BipartiteGraphWrapper<Graph>;
1.79 - protected:
1.80 - const BipartiteGraphWrapper<Graph>* gw;
1.81 - public:
1.82 - ClassNodeIt() { }
1.83 - ClassNodeIt(Invalid i) : Node(i) { }
1.84 - ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, bool _class) :
1.85 - Node(), gw(&_gw) {
1.86 - _gw.s_false_t_true_map->first(*this, _class);
1.87 - }
1.88 - //FIXME needed in new concept, important here
1.89 - ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, const Node& n) :
1.90 - Node(n), gw(&_gw) { }
1.91 - ClassNodeIt& operator++() {
1.92 - gw->s_false_t_true_map->next(*this);
1.93 - return *this;
1.94 - }
1.95 - };
1.96 -// class SNodeIt {
1.97 -// Node n;
1.98 -// public:
1.99 -// SNodeIt() { }
1.100 -// SNodeIt(const Invalid& i) : n(i) { }
1.101 -// SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
1.102 -// _G.s_false_t_true_map->first(n, false);
1.103 -// }
1.104 -// operator Node() const { return n; }
1.105 -// };
1.106 -// class TNodeIt {
1.107 -// Node n;
1.108 -// public:
1.109 -// TNodeIt() { }
1.110 -// TNodeIt(const Invalid& i) : n(i) { }
1.111 -// TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
1.112 -// _G.s_false_t_true_map->first(n, true);
1.113 -// }
1.114 -// operator Node() const { return n; }
1.115 -// };
1.116 -// class OutEdgeIt {
1.117 -// friend class BipartiteGraphWrapper<Graph>;
1.118 -// protected:
1.119 -// typename Graph::OutEdgeIt e;
1.120 -// public:
1.121 -// OutEdgeIt() { }
1.122 -// OutEdgeIt(const Invalid& i) : e(i) { }
1.123 -// OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
1.124 -// if (!(*(_G.s_false_t_true_map))[_n])
1.125 -// e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
1.126 -// else
1.127 -// e=INVALID;
1.128 -// }
1.129 -// operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.130 -// };
1.131 -// class InEdgeIt {
1.132 -// friend class BipartiteGraphWrapper<Graph>;
1.133 -// protected:
1.134 -// typename Graph::InEdgeIt e;
1.135 -// public:
1.136 -// InEdgeIt() { }
1.137 -// InEdgeIt(const Invalid& i) : e(i) { }
1.138 -// InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
1.139 -// if ((*(_G.s_false_t_true_map))[_n])
1.140 -// e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
1.141 -// else
1.142 -// e=INVALID;
1.143 -// }
1.144 -// operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.145 -// };
1.146 -
1.147 - using GraphWrapper<Graph>::first;
1.148 - ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
1.149 - n=ClassNodeIt(*this, _class); return n;
1.150 - }
1.151 -// SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
1.152 -// TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
1.153 -// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.154 -// i=OutEdgeIt(*this, p); return i;
1.155 -// }
1.156 -// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.157 -// i=InEdgeIt(*this, p); return i;
1.158 -// }
1.159 -
1.160 -// using GraphWrapper<Graph>::next;
1.161 -// ClassNodeIt& next(ClassNodeIt& n) const {
1.162 -// this->s_false_t_true_map->next(n.n); return n;
1.163 -// }
1.164 -// SNodeIt& next(SNodeIt& n) const {
1.165 -// this->s_false_t_true_map->next(n); return n;
1.166 -// }
1.167 -// TNodeIt& next(TNodeIt& n) const {
1.168 -// this->s_false_t_true_map->next(n); return n;
1.169 -// }
1.170 -// OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.171 -// InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.172 -
1.173 -// Node source(const Edge& e) {
1.174 -// if (!(*(this->s_false_t_true_map))[this->graph->source(e)])
1.175 -// return Node(this->graph->source(e));
1.176 -// else
1.177 -// return Node(this->graph->target(e));
1.178 -// }
1.179 -// Node target(const Edge& e) {
1.180 -// if (!(*(this->s_false_t_true_map))[this->graph->source(e)])
1.181 -// return Node(this->graph->target(e));
1.182 -// else
1.183 -// return Node(this->graph->source(e));
1.184 -// }
1.185 -
1.186 -// Node aNode(const OutEdgeIt& e) const {
1.187 -// return Node(this->graph->aNode(e.e));
1.188 -// }
1.189 -// Node aNode(const InEdgeIt& e) const {
1.190 -// return Node(this->graph->aNode(e.e));
1.191 -// }
1.192 -// Node bNode(const OutEdgeIt& e) const {
1.193 -// return Node(this->graph->bNode(e.e));
1.194 -// }
1.195 -// Node bNode(const InEdgeIt& e) const {
1.196 -// return Node(this->graph->bNode(e.e));
1.197 -// }
1.198 -
1.199 - /// Returns true iff \c n is in S.
1.200 - bool inSClass(const Node& n) const {
1.201 - return !(*(this->s_false_t_true_map))[n];
1.202 - }
1.203 -
1.204 - /// Returns true iff \c n is in T.
1.205 - bool inTClass(const Node& n) const {
1.206 - return (*(this->s_false_t_true_map))[n];
1.207 - }
1.208 - };
1.209 -
1.210 -
1.211 - template<typename G>
1.212 - const bool BipartiteGraphWrapper<G>::S_CLASS=false;
1.213 - template<typename G>
1.214 - const bool BipartiteGraphWrapper<G>::T_CLASS=true;
1.215 -
1.216 - /// \brief A bipartite graph template class
1.217 - ///
1.218 - /// This class composes a bipartite graph over a directed or undirected
1.219 - /// graph structure of type \c Graph.
1.220 - /// \c _graph have to be a reference to a graph of type \c Graph
1.221 - /// and \c _s_false_t_true_map is an \c IterableBoolMap
1.222 - /// reference containing the elements for the
1.223 - /// color classes S and T. \c _graph is to be referred to an undirected
1.224 - /// graph or a directed graph with edges oriented from S to T.
1.225 - ///
1.226 - ///\bug experimental. Do not use this while the bipartitemap augmentation
1.227 - /// does not work well.
1.228 - template<typename Graph>
1.229 - class BipartiteGraph : public BipartiteGraphWrapper<Graph> {
1.230 -// typedef IterableBoolMap< typename Graph::template NodeMap<int> >
1.231 -// SFalseTTrueMap;
1.232 - typedef BipartiteGraphWrapper<Graph> Parent;
1.233 - protected:
1.234 - Graph gr;
1.235 - typename Graph::template NodeMap<int> bipartite_map;
1.236 - typename Parent::SFalseTTrueMap s_false_t_true_map;
1.237 - public:
1.238 - typedef typename Parent::Node Node;
1.239 - typedef typename Parent::Edge Edge;
1.240 - BipartiteGraph() : BipartiteGraphWrapper<Graph>(),
1.241 - gr(), bipartite_map(gr, -1),
1.242 - s_false_t_true_map(bipartite_map) {
1.243 - Parent::setGraph(gr);
1.244 - Parent::setSFalseTTrueMap(s_false_t_true_map);
1.245 - }
1.246 -
1.247 - /// the \c bool parameter which can be \c S_Class or \c T_Class shows
1.248 - /// the color class where the new node is to be inserted.
1.249 - Node addNode(bool b) {
1.250 - Node n=Parent::graph->addNode();
1.251 - bipartite_map.update();
1.252 - //bipartite_map.set(n, -1);
1.253 - s_false_t_true_map.insert(n, b);
1.254 - return n;
1.255 - }
1.256 -
1.257 - /// A new edge is inserted.
1.258 - ///\pre \c source have to be in \c S_Class and \c target in \c T_Class.
1.259 - Edge addEdge(const Node& source, const Node& target) {
1.260 - return Parent::graph->addEdge(source, target);
1.261 - }
1.262 -
1.263 - void erase(const Node& n) {
1.264 - s_false_t_true_map.remove(n);
1.265 - Parent::graph->erase(n);
1.266 - }
1.267 - void erase(const Edge& e) {
1.268 - Parent::graph->erase(e);
1.269 - }
1.270 -
1.271 - void clear() {
1.272 - FOR_EACH_LOC(typename Parent::EdgeIt, e, *this) erase(e);
1.273 - FOR_EACH_LOC(typename Parent::NodeIt, n, *this) erase(n);
1.274 - }
1.275 - };
1.276 -
1.277 - template<typename Graph, typename sIterableMap, typename tIterableMap>
1.278 - class stGraphWrapper;
1.279 -
1.280 - /// Easier stuff for bipartite graphs.
1.281 - template<typename Graph>
1.282 - class stBipartiteGraphWrapper : public
1.283 - stGraphWrapper<Graph, typename Graph::SFalseTTrueMap,
1.284 - typename Graph::SFalseTTrueMap> {
1.285 - public:
1.286 - typedef stGraphWrapper<Graph, typename Graph::SFalseTTrueMap,
1.287 - typename Graph::SFalseTTrueMap> Parent;
1.288 - stBipartiteGraphWrapper(Graph& _graph) :
1.289 - Parent(_graph, _graph.sFalseTTrueMap(), _graph.sFalseTTrueMap()) { }
1.290 - };
1.291 -
1.292 -// template<typename Graph>
1.293 -// std::ostream&
1.294 -// operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) {
1.295 -// os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
1.296 -// return os;
1.297 -// }
1.298 -// template<typename Graph>
1.299 -// std::ostream&
1.300 -// operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) {
1.301 -// os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
1.302 -// " node: " << i.n << ")";
1.303 -// return os;
1.304 -// }
1.305 -
1.306 - /// \brief A wrapper for adding extra nodes s and t to a bipartite graph
1.307 - /// and edges from s to each node of S and form each node of T to t.
1.308 - ///
1.309 - /// A wrapper for adding extra nodes s and t to a bipartite graph
1.310 - /// and edges from s to each node of S and form each node of T to t.
1.311 - /// This class is very useful to reduce some matching or more
1.312 - /// generally, capacitataed b-matching problem to a flow problem.
1.313 - /// According to the bipartite graph concepts the bipartite
1.314 - /// graph have to be oriented from S to T.
1.315 - ///
1.316 - /// \author Marton Makai
1.317 - template<typename Graph, typename sIterableMap, typename tIterableMap>
1.318 - class stGraphWrapper : public GraphWrapper<Graph> {
1.319 - protected:
1.320 - const sIterableMap* s_iterable_map;
1.321 - const tIterableMap* t_iterable_map;
1.322 - public:
1.323 - class Node;
1.324 - friend class Node;
1.325 -//GN, int
1.326 -//0 normalis, 1 s, 2 t, ez az iteralasi sorrend,
1.327 -//es a vege a false azaz (invalid, 3)
1.328 - class NodeIt;
1.329 - friend class NodeIt;
1.330 -//GNI, int
1.331 - class Edge;
1.332 - friend class Edge;
1.333 -//GE, int, GN
1.334 -//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
1.335 -//invalid: (invalid, 3, invalid)
1.336 - class OutEdgeIt;
1.337 - friend class OutEdgeIt;
1.338 -//GO, int, GNI
1.339 -//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
1.340 -//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
1.341 -//t-bol (invalid, 3, invalid)
1.342 - class InEdgeIt;
1.343 - friend class InEdgeIt;
1.344 -//GI, int, GNI
1.345 -//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
1.346 -//s-be (invalid, 3, invalid)
1.347 -//t-be (invalid, 2, first), ... (invalid, 3, invalid)
1.348 - class EdgeIt;
1.349 - friend class EdgeIt;
1.350 -//(first, 0, invalid) ...
1.351 -//(invalid, 1, vmi)
1.352 -//(invalid, 2, vmi)
1.353 -//invalid, 3, invalid)
1.354 - template <typename T> class NodeMap;
1.355 - template <typename T> class EdgeMap;
1.356 -
1.357 -// template <typename T> friend class NodeMap;
1.358 -// template <typename T> friend class EdgeMap;
1.359 -
1.360 - ///\todo FIXME ezt majd static-ra kell javitani
1.361 - const Node S_NODE;
1.362 - const Node T_NODE;
1.363 -
1.364 - static const bool S_CLASS=false;
1.365 - static const bool T_CLASS=true;
1.366 -
1.367 - // \bug not too nice constructor.
1.368 - stGraphWrapper(Graph& _graph,
1.369 - const sIterableMap& _s_iterable_map,
1.370 - const tIterableMap& _t_iterable_map) :
1.371 - GraphWrapper<Graph>(_graph),
1.372 - s_iterable_map(&_s_iterable_map),
1.373 - t_iterable_map(&_t_iterable_map),
1.374 - S_NODE(INVALID, 1),
1.375 - T_NODE(INVALID, 2) { }
1.376 -
1.377 -
1.378 -// std::ostream&
1.379 -// operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
1.380 -// friend std::ostream&
1.381 -// operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
1.382 -// friend std::ostream&
1.383 -// operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);
1.384 -
1.385 - class Node : public Graph::Node {
1.386 - protected:
1.387 - friend class GraphWrapper<Graph>;
1.388 - friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.389 - template <typename T> friend class NodeMap;
1.390 - friend class Edge;
1.391 - friend class OutEdgeIt;
1.392 - friend class InEdgeIt;
1.393 - friend class EdgeIt;
1.394 - int spec;
1.395 - public:
1.396 - Node() { }
1.397 - Node(const typename Graph::Node& _n, int _spec=0) :
1.398 - Graph::Node(_n), spec(_spec) { }
1.399 - Node(const Invalid& i) : Graph::Node(i), spec(3) { }
1.400 - friend bool operator==(const Node& u, const Node& v) {
1.401 - return (u.spec==v.spec &&
1.402 - static_cast<typename Graph::Node>(u)==
1.403 - static_cast<typename Graph::Node>(v));
1.404 - }
1.405 - friend bool operator!=(const Node& u, const Node& v) {
1.406 - return (v.spec!=u.spec ||
1.407 - static_cast<typename Graph::Node>(u)!=
1.408 - static_cast<typename Graph::Node>(v));
1.409 - }
1.410 -// template<typename G>
1.411 -// friend std::ostream&
1.412 -// operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i);
1.413 - friend std::ostream& operator<< (std::ostream& os, const Node& i);
1.414 - int getSpec() const { return spec; }
1.415 - };
1.416 -
1.417 - class NodeIt {
1.418 - friend class GraphWrapper<Graph>;
1.419 - friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.420 - typename Graph::NodeIt n;
1.421 - int spec;
1.422 - public:
1.423 - NodeIt() { }
1.424 - NodeIt(const typename Graph::NodeIt& _n, int _spec) :
1.425 - n(_n), spec(_spec) { }
1.426 - NodeIt(const Invalid& i) : n(i), spec(3) { }
1.427 - NodeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G)
1.428 - : n(*(_G.graph)), spec(0) {
1.429 - if (!_G.graph->valid(n)) spec=1;
1.430 - }
1.431 - operator Node() const { return Node(n, spec); }
1.432 - };
1.433 -
1.434 - class Edge : public Graph::Edge {
1.435 - friend class GraphWrapper<Graph>;
1.436 - friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.437 - template <typename T> friend class EdgeMap;
1.438 - int spec;
1.439 - typename Graph::Node n;
1.440 - public:
1.441 - Edge() { }
1.442 - Edge(const typename Graph::Edge& _e, int _spec,
1.443 - const typename Graph::Node& _n) :
1.444 - Graph::Edge(_e), spec(_spec), n(_n) {
1.445 - }
1.446 - Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
1.447 - friend bool operator==(const Edge& u, const Edge& v) {
1.448 - return (u.spec==v.spec &&
1.449 - static_cast<typename Graph::Edge>(u)==
1.450 - static_cast<typename Graph::Edge>(v) &&
1.451 - u.n==v.n);
1.452 - }
1.453 - friend bool operator!=(const Edge& u, const Edge& v) {
1.454 - return (v.spec!=u.spec ||
1.455 - static_cast<typename Graph::Edge>(u)!=
1.456 - static_cast<typename Graph::Edge>(v) ||
1.457 - u.n!=v.n);
1.458 - }
1.459 -// template<typename G>
1.460 -// friend std::ostream&
1.461 -// operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i);
1.462 - friend std::ostream& operator<< (std::ostream& os, const Edge& i);
1.463 - int getSpec() const { return spec; }
1.464 - typename Graph::Node getNode() const { return n; }
1.465 - };
1.466 -
1.467 - class OutEdgeIt {
1.468 - friend class GraphWrapper<Graph>;
1.469 - friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.470 - typename Graph::OutEdgeIt e;
1.471 - int spec;
1.472 - typename Graph::ClassNodeIt n;
1.473 - public:
1.474 - OutEdgeIt() { }
1.475 - OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
1.476 - const typename Graph::ClassNodeIt& _n) :
1.477 - e(_e), spec(_spec), n(_n) {
1.478 - }
1.479 - OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1.480 - OutEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G,
1.481 - const Node& _n) {
1.482 - switch (_n.spec) {
1.483 - case 0 :
1.484 - if (_G.graph->inSClass(_n)) { //S, van normalis kiel
1.485 - e=typename Graph::OutEdgeIt(*(_G.graph),
1.486 - typename Graph::Node(_n));
1.487 - spec=0;
1.488 - n=INVALID;
1.489 - if (!_G.graph->valid(e)) spec=3;
1.490 - } else { //T, specko kiel van
1.491 - e=INVALID;
1.492 - spec=2;
1.493 - n=_n;
1.494 - }
1.495 - break;
1.496 - case 1:
1.497 - e=INVALID;
1.498 - spec=1;
1.499 - _G.graph->first(n, S_CLASS); //s->vmi;
1.500 - if (!_G.graph->valid(n)) spec=3; //Ha S ures
1.501 - break;
1.502 - case 2:
1.503 - e=INVALID;
1.504 - spec=3;
1.505 - n=INVALID;
1.506 - break;
1.507 - }
1.508 - }
1.509 - operator Edge() const { return Edge(e, spec, n); }
1.510 - };
1.511 -
1.512 - class InEdgeIt {
1.513 - friend class GraphWrapper<Graph>;
1.514 - friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.515 - typename Graph::InEdgeIt e;
1.516 - int spec;
1.517 - typename Graph::ClassNodeIt n;
1.518 - public:
1.519 - InEdgeIt() { }
1.520 - InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
1.521 - const typename Graph::ClassNodeIt& _n) :
1.522 - e(_e), spec(_spec), n(_n) {
1.523 - }
1.524 - InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1.525 - InEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G,
1.526 - const Node& _n) {
1.527 - switch (_n.spec) {
1.528 - case 0 :
1.529 - if (_G.graph->inTClass(_n)) { //T, van normalis beel
1.530 - e=typename Graph::InEdgeIt(*(_G.graph),
1.531 - typename Graph::Node(_n));
1.532 - spec=0;
1.533 - n=INVALID;
1.534 - if (!_G.graph->valid(e)) spec=3;
1.535 - } else { //S, specko beel van
1.536 - e=INVALID;
1.537 - spec=1;
1.538 - n=_n;
1.539 - }
1.540 - break;
1.541 - case 1:
1.542 - e=INVALID;
1.543 - spec=3;
1.544 - n=INVALID;
1.545 - break;
1.546 - case 2:
1.547 - e=INVALID;
1.548 - spec=2;
1.549 - _G.graph->first(n, T_CLASS); //vmi->t;
1.550 - if (!_G.graph->valid(n)) spec=3; //Ha T ures
1.551 - break;
1.552 - }
1.553 - }
1.554 - operator Edge() const { return Edge(e, spec, n); }
1.555 - };
1.556 -
1.557 - class EdgeIt {
1.558 - friend class GraphWrapper<Graph>;
1.559 - friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
1.560 - typename Graph::EdgeIt e;
1.561 - int spec;
1.562 - typename Graph::ClassNodeIt n;
1.563 - public:
1.564 - EdgeIt() { }
1.565 - EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
1.566 - const typename Graph::ClassNodeIt& _n) :
1.567 - e(_e), spec(_spec), n(_n) { }
1.568 - EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1.569 - EdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) :
1.570 - e(*(_G.graph)), spec(0), n(INVALID) {
1.571 - if (!_G.graph->valid(e)) {
1.572 - spec=1;
1.573 - _G.graph->first(n, S_CLASS);
1.574 - if (!_G.graph->valid(n)) { //Ha S ures
1.575 - spec=2;
1.576 - _G.graph->first(n, T_CLASS);
1.577 - if (!_G.graph->valid(n)) { //Ha T ures
1.578 - spec=3;
1.579 - }
1.580 - }
1.581 - }
1.582 - }
1.583 - operator Edge() const { return Edge(e, spec, n); }
1.584 - };
1.585 -
1.586 - NodeIt& first(NodeIt& i) const {
1.587 - i=NodeIt(*this); return i;
1.588 - }
1.589 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.590 - i=OutEdgeIt(*this, p); return i;
1.591 - }
1.592 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.593 - i=InEdgeIt(*this, p); return i;
1.594 - }
1.595 - EdgeIt& first(EdgeIt& i) const {
1.596 - i=EdgeIt(*this); return i;
1.597 - }
1.598 -
1.599 - NodeIt& next(NodeIt& i) const {
1.600 - switch (i.spec) {
1.601 - case 0:
1.602 - this->graph->next(i.n);
1.603 - if (!this->graph->valid(i.n)) {
1.604 - i.spec=1;
1.605 - }
1.606 - break;
1.607 - case 1:
1.608 - i.spec=2;
1.609 - break;
1.610 - case 2:
1.611 - i.spec=3;
1.612 - break;
1.613 - }
1.614 - return i;
1.615 - }
1.616 - OutEdgeIt& next(OutEdgeIt& i) const {
1.617 - typename Graph::Node v;
1.618 - switch (i.spec) {
1.619 - case 0: //normal edge
1.620 - v=this->graph->aNode(i.e);
1.621 - this->graph->next(i.e);
1.622 - if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1.623 - if (this->graph->inSClass(v)) { //S, nincs kiel
1.624 - i.spec=3;
1.625 - i.n=INVALID;
1.626 - } else { //T, van kiel
1.627 - i.spec=2;
1.628 - i.n=v;
1.629 - }
1.630 - }
1.631 - break;
1.632 - case 1: //s->vmi
1.633 - this->graph->next(i.n);
1.634 - if (!this->graph->valid(i.n)) i.spec=3;
1.635 - break;
1.636 - case 2: //vmi->t
1.637 - i.spec=3;
1.638 - i.n=INVALID;
1.639 - break;
1.640 - }
1.641 - return i;
1.642 - }
1.643 - InEdgeIt& next(InEdgeIt& i) const {
1.644 - typename Graph::Node v;
1.645 - switch (i.spec) {
1.646 - case 0: //normal edge
1.647 - v=this->graph->aNode(i.e);
1.648 - this->graph->next(i.e);
1.649 - if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1.650 - if (this->graph->inTClass(v)) { //S, nincs beel
1.651 - i.spec=3;
1.652 - i.n=INVALID;
1.653 - } else { //S, van beel
1.654 - i.spec=1;
1.655 - i.n=v;
1.656 - }
1.657 - }
1.658 - break;
1.659 - case 1: //s->vmi
1.660 - i.spec=3;
1.661 - i.n=INVALID;
1.662 - break;
1.663 - case 2: //vmi->t
1.664 - this->graph->next(i.n);
1.665 - if (!this->graph->valid(i.n)) i.spec=3;
1.666 - break;
1.667 - }
1.668 - return i;
1.669 - }
1.670 -
1.671 - EdgeIt& next(EdgeIt& i) const {
1.672 - switch (i.spec) {
1.673 - case 0:
1.674 - this->graph->next(i.e);
1.675 - if (!this->graph->valid(i.e)) {
1.676 - i.spec=1;
1.677 - this->graph->first(i.n, S_CLASS);
1.678 - if (!this->graph->valid(i.n)) {
1.679 - i.spec=2;
1.680 - this->graph->first(i.n, T_CLASS);
1.681 - if (!this->graph->valid(i.n)) i.spec=3;
1.682 - }
1.683 - }
1.684 - break;
1.685 - case 1:
1.686 - this->graph->next(i.n);
1.687 - if (!this->graph->valid(i.n)) {
1.688 - i.spec=2;
1.689 - this->graph->first(i.n, T_CLASS);
1.690 - if (!this->graph->valid(i.n)) i.spec=3;
1.691 - }
1.692 - break;
1.693 - case 2:
1.694 - this->graph->next(i.n);
1.695 - if (!this->graph->valid(i.n)) i.spec=3;
1.696 - break;
1.697 - }
1.698 - return i;
1.699 - }
1.700 -
1.701 - Node source(const Edge& e) const {
1.702 - switch (e.spec) {
1.703 - case 0:
1.704 - return Node(this->graph->source(e));
1.705 - break;
1.706 - case 1:
1.707 - return S_NODE;
1.708 - break;
1.709 - case 2:
1.710 - default:
1.711 - return Node(e.n);
1.712 - break;
1.713 - }
1.714 - }
1.715 - Node target(const Edge& e) const {
1.716 - switch (e.spec) {
1.717 - case 0:
1.718 - return Node(this->graph->target(e));
1.719 - break;
1.720 - case 1:
1.721 - return Node(e.n);
1.722 - break;
1.723 - case 2:
1.724 - default:
1.725 - return T_NODE;
1.726 - break;
1.727 - }
1.728 - }
1.729 -
1.730 - bool valid(const Node& n) const { return (n.spec<3); }
1.731 - bool valid(const Edge& e) const { return (e.spec<3); }
1.732 -
1.733 - int nodeNum() const { return this->graph->nodeNum()+2; }
1.734 - int edgeNum() const {
1.735 - return this->graph->edgeNum()+this->graph->nodeNum();
1.736 - }
1.737 -
1.738 - Node aNode(const OutEdgeIt& e) const { return source(e); }
1.739 - Node aNode(const InEdgeIt& e) const { return target(e); }
1.740 - Node bNode(const OutEdgeIt& e) const { return target(e); }
1.741 - Node bNode(const InEdgeIt& e) const { return source(e); }
1.742 -
1.743 - void addNode() const { }
1.744 - void addEdge() const { }
1.745 -
1.746 -// Node addNode() const { return Node(this->graph->addNode()); }
1.747 -// Edge addEdge(const Node& source, const Node& target) const {
1.748 -// return Edge(this->graph->addEdge(source, target)); }
1.749 -
1.750 -// void erase(const Node& i) const { this->graph->erase(i); }
1.751 -// void erase(const Edge& i) const { this->graph->erase(i); }
1.752 -
1.753 -// void clear() const { this->graph->clear(); }
1.754 -
1.755 - template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
1.756 - typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
1.757 - protected:
1.758 - T s_value, t_value;
1.759 - public:
1.760 - NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) :
1.761 - Parent(_G),
1.762 - s_value(),
1.763 - t_value() { }
1.764 - NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a)
1.765 - : Parent(_G, a),
1.766 - s_value(a),
1.767 - t_value(a) { }
1.768 - T operator[](const Node& n) const {
1.769 - switch (n.spec) {
1.770 - case 0:
1.771 - return Parent::operator[](n);
1.772 - case 1:
1.773 - return s_value;
1.774 - case 2:
1.775 - default:
1.776 - return t_value;
1.777 - }
1.778 - }
1.779 - void set(const Node& n, T t) {
1.780 - switch (n.spec) {
1.781 - case 0:
1.782 - GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
1.783 - break;
1.784 - case 1:
1.785 - s_value=t;
1.786 - break;
1.787 - case 2:
1.788 - default:
1.789 - t_value=t;
1.790 - break;
1.791 - }
1.792 - }
1.793 - };
1.794 -
1.795 - /// This class is to wrap a node-map of \c Graph and two variables
1.796 - /// storing values for \c S_NODE and \c T_NODE to a node-map of
1.797 - /// stGraphWrapper<Graph, sIterableMap, tIterableMap>.
1.798 - template<typename NM> class NodeMapWrapper {
1.799 - public:
1.800 - typedef Node Key;
1.801 - typedef typename NM::Value Value;
1.802 - protected:
1.803 - NM* nm;
1.804 - Value* s_value, t_value;
1.805 - public:
1.806 - NodeMapWrapper(NM& _nm, Value& _s_value, Value& _t_value) :
1.807 - nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }
1.808 - Value operator[](const Node& n) const {
1.809 - switch (n.getSpec()) {
1.810 - case 0:
1.811 - return (*nm)[n];
1.812 - case 1:
1.813 - return *s_value;
1.814 - case 2:
1.815 - default:
1.816 - return *t_value;
1.817 - }
1.818 - }
1.819 - void set(const Node& n, Value t) {
1.820 - switch (n.getSpec()) {
1.821 - case 0:
1.822 - nm->set(n, t);
1.823 - break;
1.824 - case 1:
1.825 - *s_value=t;
1.826 - break;
1.827 - case 2:
1.828 - default:
1.829 - *t_value=t;
1.830 - break;
1.831 - }
1.832 - }
1.833 - };
1.834 -
1.835 - template<typename T>
1.836 - class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
1.837 - typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
1.838 - protected:
1.839 - typename GraphWrapper<Graph>::template NodeMap<T> node_value;
1.840 - public:
1.841 - EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G)
1.842 - : Parent(_G),
1.843 - node_value(_G) { }
1.844 - EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a)
1.845 - : Parent(_G, a),
1.846 - node_value(_G, a) { }
1.847 - T operator[](const Edge& e) const {
1.848 - switch (e.spec) {
1.849 - case 0:
1.850 - return Parent::operator[](e);
1.851 - case 1:
1.852 - return node_value[e.n];
1.853 - case 2:
1.854 - default:
1.855 - return node_value[e.n];
1.856 - }
1.857 - }
1.858 - void set(const Edge& e, T t) {
1.859 - switch (e.spec) {
1.860 - case 0:
1.861 - Parent::set(e, t);
1.862 - break;
1.863 - case 1:
1.864 - node_value.set(e.n, t);
1.865 - break;
1.866 - case 2:
1.867 - default:
1.868 - node_value.set(e.n, t);
1.869 - break;
1.870 - }
1.871 - }
1.872 - };
1.873 -
1.874 - /// This class is to wrap an edge-map and a node-map of \c Graph
1.875 - /// to an edge-map of stGraphWrapper<Graph, sIterableMap, tIterableMap>.
1.876 - template<typename EM, typename NM>
1.877 - class EdgeMapWrapper {
1.878 - public:
1.879 - typedef Edge Key;
1.880 - typedef typename EM::Value Value;
1.881 - protected:
1.882 - EM* em;
1.883 - NM* nm;
1.884 - public:
1.885 - EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }
1.886 - Value operator[](const Edge& e) const {
1.887 - switch (e.getSpec()) {
1.888 - case 0:
1.889 - return (*em)[e];
1.890 - case 1:
1.891 - return (*nm)[e.getNode()];
1.892 - case 2:
1.893 - default:
1.894 - return (*nm)[e.getNode()];
1.895 - }
1.896 - }
1.897 - void set(const Edge& e, Value t) {
1.898 - switch (e.getSpec()) {
1.899 - case 0:
1.900 - em->set(e, t);
1.901 - break;
1.902 - case 1:
1.903 - nm->set(e.getNode(), t);
1.904 - break;
1.905 - case 2:
1.906 - default:
1.907 - nm->set(e.getNode(), t);
1.908 - break;
1.909 - }
1.910 - }
1.911 - };
1.912 -
1.913 -
1.914 -// template<typename G>
1.915 - friend std::ostream&
1.916 - operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) {
1.917 - os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
1.918 - return os;
1.919 - }
1.920 -// template<typename G>
1.921 - friend std::ostream&
1.922 - operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) {
1.923 - os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
1.924 - " node: " << i.n << ")";
1.925 - return os;
1.926 - }
1.927 -
1.928 - };
1.929 -
1.930 - ///@}
1.931 -
1.932 -} //namespace lemon
1.933 -
1.934 -
1.935 -#endif //LEMON_BIPARTITE_GRAPH_WRAPPER_H
1.936 -