1.1 --- a/src/work/marci/bipartite_graph_wrapper.h Fri Apr 30 13:52:17 2004 +0000
1.2 +++ b/src/work/marci/bipartite_graph_wrapper.h Fri Apr 30 14:02:10 2004 +0000
1.3 @@ -1,6 +1,6 @@
1.4 // -*- c++ -*-
1.5 -#ifndef HUGO_GRAPH_WRAPPER_H
1.6 -#define HUGO_GRAPH_WRAPPER_H
1.7 +#ifndef HUGO_BIPARTITE_GRAPH_WRAPPER_H
1.8 +#define HUGO_BIPARTITE_GRAPH_WRAPPER_H
1.9
1.10 ///\ingroup gwrappers
1.11 ///\file
1.12 @@ -12,927 +12,10 @@
1.13
1.14 #include <invalid.h>
1.15 #include <iter_map.h>
1.16 +#include <graph_wrapper.h>
1.17
1.18 namespace hugo {
1.19
1.20 - // Graph wrappers
1.21 -
1.22 - /// \addtogroup gwrappers
1.23 - /// A main parts of HUGOlib are the different graph structures,
1.24 - /// generic graph algorithms, graph concepts which couple these, and
1.25 - /// graph wrappers. While the previous ones are more or less clear, the
1.26 - /// latter notion needs further explanation.
1.27 - /// Graph wrappers are graph classes which serve for considering graph
1.28 - /// structures in different ways. A short example makes the notion much
1.29 - /// clearer.
1.30 - /// Suppose that we have an instance \c g of a directed graph
1.31 - /// type say \c ListGraph and an algorithm
1.32 - /// \code template<typename Graph> int algorithm(const Graph&); \endcode
1.33 - /// is needed to run on the reversely oriented graph.
1.34 - /// It may be expensive (in time or in memory usage) to copy
1.35 - /// \c g with the reverse orientation.
1.36 - /// Thus, a wrapper class
1.37 - /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
1.38 - /// The code looks as follows
1.39 - /// \code
1.40 - /// ListGraph g;
1.41 - /// RevGraphWrapper<ListGraph> rgw(g);
1.42 - /// int result=algorithm(rgw);
1.43 - /// \endcode
1.44 - /// After running the algorithm, the original graph \c g
1.45 - /// remains untouched. Thus the graph wrapper used above is to consider the
1.46 - /// original graph with reverse orientation.
1.47 - /// This techniques gives rise to an elegant code, and
1.48 - /// based on stable graph wrappers, complex algorithms can be
1.49 - /// implemented easily.
1.50 - /// In flow, circulation and bipartite matching problems, the residual
1.51 - /// graph is of particular importance. Combining a wrapper implementing
1.52 - /// this, shortest path algorithms and minimum mean cycle algorithms,
1.53 - /// a range of weighted and cardinality optimization algorithms can be
1.54 - /// obtained. For lack of space, for other examples,
1.55 - /// the interested user is referred to the detailed documentation of graph
1.56 - /// wrappers.
1.57 - /// The behavior of graph wrappers can be very different. Some of them keep
1.58 - /// capabilities of the original graph while in other cases this would be
1.59 - /// meaningless. This means that the concepts that they are a model of depend
1.60 - /// on the graph wrapper, and the wrapped graph(s).
1.61 - /// If an edge of \c rgw is deleted, this is carried out by
1.62 - /// deleting the corresponding edge of \c g. But for a residual
1.63 - /// graph, this operation has no sense.
1.64 - /// Let we stand one more example here to simplify your work.
1.65 - /// wrapper class
1.66 - /// \code template<typename Graph> class RevGraphWrapper; \endcode
1.67 - /// has constructor
1.68 - /// <tt> RevGraphWrapper(Graph& _g)</tt>.
1.69 - /// This means that in a situation,
1.70 - /// when a <tt> const ListGraph& </tt> reference to a graph is given,
1.71 - /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
1.72 - /// \code
1.73 - /// int algorithm1(const ListGraph& g) {
1.74 - /// RevGraphWrapper<const ListGraph> rgw(g);
1.75 - /// return algorithm2(rgw);
1.76 - /// }
1.77 - /// \endcode
1.78 -
1.79 - /// \addtogroup gwrappers
1.80 - /// @{
1.81 -
1.82 - ///Base type for the Graph Wrappers
1.83 -
1.84 - ///This is the base type for the Graph Wrappers.
1.85 - ///\todo Some more docs...
1.86 - ///
1.87 - ///\author Marton Makai
1.88 -
1.89 - template<typename Graph>
1.90 - class GraphWrapper {
1.91 - protected:
1.92 - Graph* graph;
1.93 -
1.94 - public:
1.95 - typedef Graph BaseGraph;
1.96 - typedef Graph ParentGraph;
1.97 -
1.98 -// GraphWrapper() : graph(0) { }
1.99 - GraphWrapper(Graph& _graph) : graph(&_graph) { }
1.100 -// void setGraph(Graph& _graph) { graph=&_graph; }
1.101 -// Graph& getGraph() const { return *graph; }
1.102 -
1.103 -// typedef typename Graph::Node Node;
1.104 - class Node : public Graph::Node {
1.105 - friend class GraphWrapper<Graph>;
1.106 - public:
1.107 - Node() { }
1.108 - Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
1.109 - Node(const Invalid& i) : Graph::Node(i) { }
1.110 - };
1.111 - class NodeIt {
1.112 - friend class GraphWrapper<Graph>;
1.113 - typename Graph::NodeIt n;
1.114 - public:
1.115 - NodeIt() { }
1.116 - NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.117 - NodeIt(const Invalid& i) : n(i) { }
1.118 - NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
1.119 - operator Node() const { return Node(typename Graph::Node(n)); }
1.120 - };
1.121 -// typedef typename Graph::Edge Edge;
1.122 - class Edge : public Graph::Edge {
1.123 - friend class GraphWrapper<Graph>;
1.124 - public:
1.125 - Edge() { }
1.126 - Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
1.127 - Edge(const Invalid& i) : Graph::Edge(i) { }
1.128 - };
1.129 - class OutEdgeIt {
1.130 - friend class GraphWrapper<Graph>;
1.131 - typename Graph::OutEdgeIt e;
1.132 - public:
1.133 - OutEdgeIt() { }
1.134 - OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.135 - OutEdgeIt(const Invalid& i) : e(i) { }
1.136 - OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
1.137 - e(*(_G.graph), typename Graph::Node(_n)) { }
1.138 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.139 - };
1.140 - class InEdgeIt {
1.141 - friend class GraphWrapper<Graph>;
1.142 - typename Graph::InEdgeIt e;
1.143 - public:
1.144 - InEdgeIt() { }
1.145 - InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.146 - InEdgeIt(const Invalid& i) : e(i) { }
1.147 - InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
1.148 - e(*(_G.graph), typename Graph::Node(_n)) { }
1.149 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.150 - };
1.151 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.152 - class EdgeIt {
1.153 - friend class GraphWrapper<Graph>;
1.154 - typename Graph::EdgeIt e;
1.155 - public:
1.156 - EdgeIt() { }
1.157 - EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.158 - EdgeIt(const Invalid& i) : e(i) { }
1.159 - EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
1.160 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.161 - };
1.162 -
1.163 - NodeIt& first(NodeIt& i) const {
1.164 - i=NodeIt(*this); return i;
1.165 - }
1.166 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.167 - i=OutEdgeIt(*this, p); return i;
1.168 - }
1.169 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.170 - i=InEdgeIt(*this, p); return i;
1.171 - }
1.172 - EdgeIt& first(EdgeIt& i) const {
1.173 - i=EdgeIt(*this); return i;
1.174 - }
1.175 -
1.176 - NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1.177 - OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
1.178 - InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
1.179 - EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
1.180 -
1.181 - Node tail(const Edge& e) const {
1.182 - return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
1.183 - Node head(const Edge& e) const {
1.184 - return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
1.185 -
1.186 - bool valid(const Node& n) const {
1.187 - return graph->valid(static_cast<typename Graph::Node>(n)); }
1.188 - bool valid(const Edge& e) const {
1.189 - return graph->valid(static_cast<typename Graph::Edge>(e)); }
1.190 -
1.191 - int nodeNum() const { return graph->nodeNum(); }
1.192 - int edgeNum() const { return graph->edgeNum(); }
1.193 -
1.194 - Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1.195 - Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1.196 - Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1.197 - Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1.198 -
1.199 - Node addNode() const { return Node(graph->addNode()); }
1.200 - Edge addEdge(const Node& tail, const Node& head) const {
1.201 - return Edge(graph->addEdge(tail, head)); }
1.202 -
1.203 - void erase(const Node& i) const { graph->erase(i); }
1.204 - void erase(const Edge& i) const { graph->erase(i); }
1.205 -
1.206 - void clear() const { graph->clear(); }
1.207 -
1.208 - template<typename T> class NodeMap : public Graph::template NodeMap<T> {
1.209 - typedef typename Graph::template NodeMap<T> Parent;
1.210 - public:
1.211 - NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
1.212 - NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
1.213 - };
1.214 -
1.215 - template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
1.216 - typedef typename Graph::template EdgeMap<T> Parent;
1.217 - public:
1.218 - EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
1.219 - EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
1.220 - };
1.221 - };
1.222 -
1.223 - /// A graph wrapper which reverses the orientation of the edges.
1.224 -
1.225 - /// A graph wrapper which reverses the orientation of the edges.
1.226 - ///
1.227 - ///\author Marton Makai
1.228 - template<typename Graph>
1.229 - class RevGraphWrapper : public GraphWrapper<Graph> {
1.230 - public:
1.231 -
1.232 - RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.233 -
1.234 - typedef typename GraphWrapper<Graph>::Node Node;
1.235 - typedef typename GraphWrapper<Graph>::Edge Edge;
1.236 - //If Graph::OutEdgeIt is not defined
1.237 - //and we do not want to use RevGraphWrapper::InEdgeIt,
1.238 - //the typdef techinque does not work.
1.239 - //Unfortunately all the typedefs are instantiated in templates.
1.240 - //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
1.241 - //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
1.242 -
1.243 - class OutEdgeIt {
1.244 - friend class GraphWrapper<Graph>;
1.245 - friend class RevGraphWrapper<Graph>;
1.246 - typename Graph::InEdgeIt e;
1.247 - public:
1.248 - OutEdgeIt() { }
1.249 - OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.250 - OutEdgeIt(const Invalid& i) : e(i) { }
1.251 - OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
1.252 - e(*(_G.graph), typename Graph::Node(_n)) { }
1.253 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.254 - };
1.255 - class InEdgeIt {
1.256 - friend class GraphWrapper<Graph>;
1.257 - friend class RevGraphWrapper<Graph>;
1.258 - typename Graph::OutEdgeIt e;
1.259 - public:
1.260 - InEdgeIt() { }
1.261 - InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.262 - InEdgeIt(const Invalid& i) : e(i) { }
1.263 - InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
1.264 - e(*(_G.graph), typename Graph::Node(_n)) { }
1.265 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.266 - };
1.267 -
1.268 - using GraphWrapper<Graph>::first;
1.269 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.270 - i=OutEdgeIt(*this, p); return i;
1.271 - }
1.272 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.273 - i=InEdgeIt(*this, p); return i;
1.274 - }
1.275 -
1.276 - using GraphWrapper<Graph>::next;
1.277 - OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.278 - InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.279 -
1.280 - Node aNode(const OutEdgeIt& e) const {
1.281 - return Node(this->graph->aNode(e.e)); }
1.282 - Node aNode(const InEdgeIt& e) const {
1.283 - return Node(this->graph->aNode(e.e)); }
1.284 - Node bNode(const OutEdgeIt& e) const {
1.285 - return Node(this->graph->bNode(e.e)); }
1.286 - Node bNode(const InEdgeIt& e) const {
1.287 - return Node(this->graph->bNode(e.e)); }
1.288 -
1.289 - Node tail(const Edge& e) const {
1.290 - return GraphWrapper<Graph>::head(e); }
1.291 - Node head(const Edge& e) const {
1.292 - return GraphWrapper<Graph>::tail(e); }
1.293 -
1.294 - };
1.295 -
1.296 - /// Wrapper for hiding nodes and edges from a graph.
1.297 -
1.298 - /// This wrapper shows a graph with filtered node-set and
1.299 - /// edge-set. The quick brown fox iterator jumps over
1.300 - /// the lazy dog nodes or edges if the values for them are false
1.301 - /// in the bool maps.
1.302 - ///
1.303 - ///\author Marton Makai
1.304 - template<typename Graph, typename NodeFilterMap,
1.305 - typename EdgeFilterMap>
1.306 - class SubGraphWrapper : public GraphWrapper<Graph> {
1.307 - protected:
1.308 - NodeFilterMap* node_filter_map;
1.309 - EdgeFilterMap* edge_filter_map;
1.310 - public:
1.311 -
1.312 - SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
1.313 - EdgeFilterMap& _edge_filter_map) :
1.314 - GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
1.315 - edge_filter_map(&_edge_filter_map) { }
1.316 -
1.317 - typedef typename GraphWrapper<Graph>::Node Node;
1.318 - class NodeIt {
1.319 - friend class GraphWrapper<Graph>;
1.320 - friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.321 - typename Graph::NodeIt n;
1.322 - public:
1.323 - NodeIt() { }
1.324 - NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.325 - NodeIt(const Invalid& i) : n(i) { }
1.326 - NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.327 - n(*(_G.graph)) {
1.328 - while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
1.329 - _G.graph->next(n);
1.330 - }
1.331 - operator Node() const { return Node(typename Graph::Node(n)); }
1.332 - };
1.333 - typedef typename GraphWrapper<Graph>::Edge Edge;
1.334 - class OutEdgeIt {
1.335 - friend class GraphWrapper<Graph>;
1.336 - friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.337 - typename Graph::OutEdgeIt e;
1.338 - public:
1.339 - OutEdgeIt() { }
1.340 - OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.341 - OutEdgeIt(const Invalid& i) : e(i) { }
1.342 - OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.343 - const Node& _n) :
1.344 - e(*(_G.graph), typename Graph::Node(_n)) {
1.345 - while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.346 - _G.graph->next(e);
1.347 - }
1.348 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.349 - };
1.350 - class InEdgeIt {
1.351 - friend class GraphWrapper<Graph>;
1.352 - friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.353 - typename Graph::InEdgeIt e;
1.354 - public:
1.355 - InEdgeIt() { }
1.356 - InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.357 - InEdgeIt(const Invalid& i) : e(i) { }
1.358 - InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.359 - const Node& _n) :
1.360 - e(*(_G.graph), typename Graph::Node(_n)) {
1.361 - while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.362 - _G.graph->next(e);
1.363 - }
1.364 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.365 - };
1.366 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.367 - class EdgeIt {
1.368 - friend class GraphWrapper<Graph>;
1.369 - friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.370 - typename Graph::EdgeIt e;
1.371 - public:
1.372 - EdgeIt() { }
1.373 - EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.374 - EdgeIt(const Invalid& i) : e(i) { }
1.375 - EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.376 - e(*(_G.graph)) {
1.377 - while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.378 - _G.graph->next(e);
1.379 - }
1.380 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.381 - };
1.382 -
1.383 - NodeIt& first(NodeIt& i) const {
1.384 - i=NodeIt(*this); return i;
1.385 - }
1.386 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.387 - i=OutEdgeIt(*this, p); return i;
1.388 - }
1.389 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.390 - i=InEdgeIt(*this, p); return i;
1.391 - }
1.392 - EdgeIt& first(EdgeIt& i) const {
1.393 - i=EdgeIt(*this); return i;
1.394 - }
1.395 -
1.396 - NodeIt& next(NodeIt& i) const {
1.397 - this->graph->next(i.n);
1.398 - while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
1.399 - this->graph->next(i.n); }
1.400 - return i;
1.401 - }
1.402 - OutEdgeIt& next(OutEdgeIt& i) const {
1.403 - this->graph->next(i.e);
1.404 - while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.405 - this->graph->next(i.e); }
1.406 - return i;
1.407 - }
1.408 - InEdgeIt& next(InEdgeIt& i) const {
1.409 - this->graph->next(i.e);
1.410 - while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.411 - this->graph->next(i.e); }
1.412 - return i;
1.413 - }
1.414 - EdgeIt& next(EdgeIt& i) const {
1.415 - this->graph->next(i.e);
1.416 - while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.417 - this->graph->next(i.e); }
1.418 - return i;
1.419 - }
1.420 -
1.421 - Node aNode(const OutEdgeIt& e) const {
1.422 - return Node(this->graph->aNode(e.e)); }
1.423 - Node aNode(const InEdgeIt& e) const {
1.424 - return Node(this->graph->aNode(e.e)); }
1.425 - Node bNode(const OutEdgeIt& e) const {
1.426 - return Node(this->graph->bNode(e.e)); }
1.427 - Node bNode(const InEdgeIt& e) const {
1.428 - return Node(this->graph->bNode(e.e)); }
1.429 -
1.430 - ///\todo
1.431 - ///Some doki, please.
1.432 - void hide(const Node& n) const { node_filter_map->set(n, false); }
1.433 - ///\todo
1.434 - ///Some doki, please.
1.435 - void hide(const Edge& e) const { edge_filter_map->set(e, false); }
1.436 -
1.437 - ///\todo
1.438 - ///Some doki, please.
1.439 - void unHide(const Node& n) const { node_filter_map->set(n, true); }
1.440 - ///\todo
1.441 - ///Some doki, please.
1.442 - void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
1.443 -
1.444 - ///\todo
1.445 - ///Some doki, please.
1.446 - bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
1.447 - ///\todo
1.448 - ///Some doki, please.
1.449 - bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
1.450 - };
1.451 -
1.452 - /// A wrapper for forgetting the orientation of a graph.
1.453 -
1.454 - /// A wrapper for getting an undirected graph by forgetting
1.455 - /// the orientation of a directed one.
1.456 - template<typename Graph>
1.457 - class UndirGraphWrapper : public GraphWrapper<Graph> {
1.458 - public:
1.459 - typedef typename GraphWrapper<Graph>::Node Node;
1.460 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.461 - typedef typename GraphWrapper<Graph>::Edge Edge;
1.462 - typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1.463 -
1.464 - UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.465 -
1.466 - class OutEdgeIt {
1.467 - friend class UndirGraphWrapper<Graph>;
1.468 - bool out_or_in; //true iff out
1.469 - typename Graph::OutEdgeIt out;
1.470 - typename Graph::InEdgeIt in;
1.471 - public:
1.472 - OutEdgeIt() { }
1.473 - OutEdgeIt(const Invalid& i) : Edge(i) { }
1.474 - OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
1.475 - out_or_in=true; _G.graph->first(out, _n);
1.476 - if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
1.477 - }
1.478 - operator Edge() const {
1.479 - if (out_or_in) return Edge(out); else return Edge(in);
1.480 - }
1.481 - };
1.482 -
1.483 -//FIXME InEdgeIt
1.484 - typedef OutEdgeIt InEdgeIt;
1.485 -
1.486 - using GraphWrapper<Graph>::first;
1.487 -// NodeIt& first(NodeIt& i) const {
1.488 -// i=NodeIt(*this); return i;
1.489 -// }
1.490 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.491 - i=OutEdgeIt(*this, p); return i;
1.492 - }
1.493 -//FIXME
1.494 -// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.495 -// i=InEdgeIt(*this, p); return i;
1.496 -// }
1.497 -// EdgeIt& first(EdgeIt& i) const {
1.498 -// i=EdgeIt(*this); return i;
1.499 -// }
1.500 -
1.501 - using GraphWrapper<Graph>::next;
1.502 -// NodeIt& next(NodeIt& n) const {
1.503 -// GraphWrapper<Graph>::next(n);
1.504 -// return n;
1.505 -// }
1.506 - OutEdgeIt& next(OutEdgeIt& e) const {
1.507 - if (e.out_or_in) {
1.508 - typename Graph::Node n=this->graph->tail(e.out);
1.509 - this->graph->next(e.out);
1.510 - if (!this->graph->valid(e.out)) {
1.511 - e.out_or_in=false; this->graph->first(e.in, n); }
1.512 - } else {
1.513 - this->graph->next(e.in);
1.514 - }
1.515 - return e;
1.516 - }
1.517 - //FIXME InEdgeIt
1.518 -// EdgeIt& next(EdgeIt& e) const {
1.519 -// GraphWrapper<Graph>::next(n);
1.520 -// // graph->next(e.e);
1.521 -// return e;
1.522 -// }
1.523 -
1.524 - Node aNode(const OutEdgeIt& e) const {
1.525 - if (e.out_or_in) return this->graph->tail(e); else
1.526 - return this->graph->head(e); }
1.527 - Node bNode(const OutEdgeIt& e) const {
1.528 - if (e.out_or_in) return this->graph->head(e); else
1.529 - return this->graph->tail(e); }
1.530 - };
1.531 -
1.532 - /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.533 -
1.534 - /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.535 - template<typename Graph, typename Number,
1.536 - typename CapacityMap, typename FlowMap>
1.537 - class ResGraphWrapper : public GraphWrapper<Graph> {
1.538 - protected:
1.539 - const CapacityMap* capacity;
1.540 - FlowMap* flow;
1.541 - public:
1.542 -
1.543 - ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.544 - FlowMap& _flow) :
1.545 - GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
1.546 -
1.547 - class Edge;
1.548 - class OutEdgeIt;
1.549 - friend class Edge;
1.550 - friend class OutEdgeIt;
1.551 -
1.552 - typedef typename GraphWrapper<Graph>::Node Node;
1.553 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.554 - class Edge : public Graph::Edge {
1.555 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.556 - protected:
1.557 - bool forward; //true, iff forward
1.558 -// typename Graph::Edge e;
1.559 - public:
1.560 - Edge() { }
1.561 - Edge(const typename Graph::Edge& _e, bool _forward) :
1.562 - Graph::Edge(_e), forward(_forward) { }
1.563 - Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
1.564 -//the unique invalid iterator
1.565 - friend bool operator==(const Edge& u, const Edge& v) {
1.566 - return (v.forward==u.forward &&
1.567 - static_cast<typename Graph::Edge>(u)==
1.568 - static_cast<typename Graph::Edge>(v));
1.569 - }
1.570 - friend bool operator!=(const Edge& u, const Edge& v) {
1.571 - return (v.forward!=u.forward ||
1.572 - static_cast<typename Graph::Edge>(u)!=
1.573 - static_cast<typename Graph::Edge>(v));
1.574 - }
1.575 - };
1.576 -
1.577 - class OutEdgeIt {
1.578 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.579 - protected:
1.580 - typename Graph::OutEdgeIt out;
1.581 - typename Graph::InEdgeIt in;
1.582 - bool forward;
1.583 - public:
1.584 - OutEdgeIt() { }
1.585 - //FIXME
1.586 -// OutEdgeIt(const Edge& e) : Edge(e) { }
1.587 - OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
1.588 -//the unique invalid iterator
1.589 - OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
1.590 - forward=true;
1.591 - resG.graph->first(out, v);
1.592 - while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1.593 - if (!resG.graph->valid(out)) {
1.594 - forward=false;
1.595 - resG.graph->first(in, v);
1.596 - while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1.597 - }
1.598 - }
1.599 - operator Edge() const {
1.600 -// Edge e;
1.601 -// e.forward=this->forward;
1.602 -// if (this->forward) e=out; else e=in;
1.603 -// return e;
1.604 - if (this->forward)
1.605 - return Edge(out, this->forward);
1.606 - else
1.607 - return Edge(in, this->forward);
1.608 - }
1.609 - };
1.610 -
1.611 - class InEdgeIt {
1.612 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.613 - protected:
1.614 - typename Graph::OutEdgeIt out;
1.615 - typename Graph::InEdgeIt in;
1.616 - bool forward;
1.617 - public:
1.618 - InEdgeIt() { }
1.619 - //FIXME
1.620 -// OutEdgeIt(const Edge& e) : Edge(e) { }
1.621 - InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
1.622 -//the unique invalid iterator
1.623 - InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
1.624 - forward=true;
1.625 - resG.graph->first(in, v);
1.626 - while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1.627 - if (!resG.graph->valid(in)) {
1.628 - forward=false;
1.629 - resG.graph->first(out, v);
1.630 - while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1.631 - }
1.632 - }
1.633 - operator Edge() const {
1.634 -// Edge e;
1.635 -// e.forward=this->forward;
1.636 -// if (this->forward) e=out; else e=in;
1.637 -// return e;
1.638 - if (this->forward)
1.639 - return Edge(in, this->forward);
1.640 - else
1.641 - return Edge(out, this->forward);
1.642 - }
1.643 - };
1.644 -
1.645 - class EdgeIt {
1.646 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.647 - protected:
1.648 - typename Graph::EdgeIt e;
1.649 - bool forward;
1.650 - public:
1.651 - EdgeIt() { }
1.652 - EdgeIt(const Invalid& i) : e(i), forward(false) { }
1.653 - EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
1.654 - forward=true;
1.655 - resG.graph->first(e);
1.656 - while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1.657 - if (!resG.graph->valid(e)) {
1.658 - forward=false;
1.659 - resG.graph->first(e);
1.660 - while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1.661 - }
1.662 - }
1.663 - operator Edge() const {
1.664 - return Edge(e, this->forward);
1.665 - }
1.666 - };
1.667 -
1.668 - using GraphWrapper<Graph>::first;
1.669 -// NodeIt& first(NodeIt& i) const {
1.670 -// i=NodeIt(*this); return i;
1.671 -// }
1.672 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.673 - i=OutEdgeIt(*this, p); return i;
1.674 - }
1.675 -// FIXME not tested
1.676 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.677 - i=InEdgeIt(*this, p); return i;
1.678 - }
1.679 - EdgeIt& first(EdgeIt& i) const {
1.680 - i=EdgeIt(*this); return i;
1.681 - }
1.682 -
1.683 - using GraphWrapper<Graph>::next;
1.684 -// NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1.685 - OutEdgeIt& next(OutEdgeIt& e) const {
1.686 - if (e.forward) {
1.687 - Node v=this->graph->aNode(e.out);
1.688 - this->graph->next(e.out);
1.689 - while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.690 - this->graph->next(e.out); }
1.691 - if (!this->graph->valid(e.out)) {
1.692 - e.forward=false;
1.693 - this->graph->first(e.in, v);
1.694 - while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.695 - this->graph->next(e.in); }
1.696 - }
1.697 - } else {
1.698 - this->graph->next(e.in);
1.699 - while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.700 - this->graph->next(e.in); }
1.701 - }
1.702 - return e;
1.703 - }
1.704 -// FIXME Not tested
1.705 - InEdgeIt& next(InEdgeIt& e) const {
1.706 - if (e.forward) {
1.707 - Node v=this->graph->aNode(e.in);
1.708 - this->graph->next(e.in);
1.709 - while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.710 - this->graph->next(e.in); }
1.711 - if (!this->graph->valid(e.in)) {
1.712 - e.forward=false;
1.713 - this->graph->first(e.out, v);
1.714 - while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.715 - this->graph->next(e.out); }
1.716 - }
1.717 - } else {
1.718 - this->graph->next(e.out);
1.719 - while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.720 - this->graph->next(e.out); }
1.721 - }
1.722 - return e;
1.723 - }
1.724 - EdgeIt& next(EdgeIt& e) const {
1.725 - if (e.forward) {
1.726 - this->graph->next(e.e);
1.727 - while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.728 - this->graph->next(e.e); }
1.729 - if (!this->graph->valid(e.e)) {
1.730 - e.forward=false;
1.731 - this->graph->first(e.e);
1.732 - while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.733 - this->graph->next(e.e); }
1.734 - }
1.735 - } else {
1.736 - this->graph->next(e.e);
1.737 - while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.738 - this->graph->next(e.e); }
1.739 - }
1.740 - return e;
1.741 - }
1.742 -
1.743 - Node tail(Edge e) const {
1.744 - return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
1.745 - Node head(Edge e) const {
1.746 - return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
1.747 -
1.748 - Node aNode(OutEdgeIt e) const {
1.749 - return ((e.forward) ? this->graph->aNode(e.out) :
1.750 - this->graph->aNode(e.in)); }
1.751 - Node bNode(OutEdgeIt e) const {
1.752 - return ((e.forward) ? this->graph->bNode(e.out) :
1.753 - this->graph->bNode(e.in)); }
1.754 -
1.755 - Node aNode(InEdgeIt e) const {
1.756 - return ((e.forward) ? this->graph->aNode(e.in) :
1.757 - this->graph->aNode(e.out)); }
1.758 - Node bNode(InEdgeIt e) const {
1.759 - return ((e.forward) ? this->graph->bNode(e.in) :
1.760 - this->graph->bNode(e.out)); }
1.761 -
1.762 -// int nodeNum() const { return graph->nodeNum(); }
1.763 - //FIXME
1.764 - void edgeNum() const { }
1.765 - //int edgeNum() const { return graph->edgeNum(); }
1.766 -
1.767 -
1.768 -// int id(Node v) const { return graph->id(v); }
1.769 -
1.770 - bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1.771 - bool valid(Edge e) const {
1.772 - return this->graph->valid(e);
1.773 - //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1.774 - }
1.775 -
1.776 - void augment(const Edge& e, Number a) const {
1.777 - if (e.forward)
1.778 -// flow->set(e.out, flow->get(e.out)+a);
1.779 - flow->set(e, (*flow)[e]+a);
1.780 - else
1.781 -// flow->set(e.in, flow->get(e.in)-a);
1.782 - flow->set(e, (*flow)[e]-a);
1.783 - }
1.784 -
1.785 - Number resCap(const Edge& e) const {
1.786 - if (e.forward)
1.787 -// return (capacity->get(e.out)-flow->get(e.out));
1.788 - return ((*capacity)[e]-(*flow)[e]);
1.789 - else
1.790 -// return (flow->get(e.in));
1.791 - return ((*flow)[e]);
1.792 - }
1.793 -
1.794 -// Number resCap(typename Graph::OutEdgeIt out) const {
1.795 -// // return (capacity->get(out)-flow->get(out));
1.796 -// return ((*capacity)[out]-(*flow)[out]);
1.797 -// }
1.798 -
1.799 -// Number resCap(typename Graph::InEdgeIt in) const {
1.800 -// // return (flow->get(in));
1.801 -// return ((*flow)[in]);
1.802 -// }
1.803 -
1.804 - template <typename T>
1.805 - class EdgeMap {
1.806 - typename Graph::template EdgeMap<T> forward_map, backward_map;
1.807 - public:
1.808 - EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.809 - EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.810 - void set(Edge e, T a) {
1.811 - if (e.forward)
1.812 - forward_map.set(e.out, a);
1.813 - else
1.814 - backward_map.set(e.in, a);
1.815 - }
1.816 - T operator[](Edge e) const {
1.817 - if (e.forward)
1.818 - return forward_map[e.out];
1.819 - else
1.820 - return backward_map[e.in];
1.821 - }
1.822 -// T get(Edge e) const {
1.823 -// if (e.out_or_in)
1.824 -// return forward_map.get(e.out);
1.825 -// else
1.826 -// return backward_map.get(e.in);
1.827 -// }
1.828 - };
1.829 - };
1.830 -
1.831 - /// ErasingFirstGraphWrapper for blocking flows.
1.832 -
1.833 - /// ErasingFirstGraphWrapper for blocking flows.
1.834 - ///
1.835 - ///\author Marton Makai
1.836 - template<typename Graph, typename FirstOutEdgesMap>
1.837 - class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1.838 - protected:
1.839 - FirstOutEdgesMap* first_out_edges;
1.840 - public:
1.841 - ErasingFirstGraphWrapper(Graph& _graph,
1.842 - FirstOutEdgesMap& _first_out_edges) :
1.843 - GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1.844 -
1.845 - typedef typename GraphWrapper<Graph>::Node Node;
1.846 -// class NodeIt {
1.847 -// friend class GraphWrapper<Graph>;
1.848 -// friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.849 -// typename Graph::NodeIt n;
1.850 -// public:
1.851 -// NodeIt() { }
1.852 -// NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.853 -// NodeIt(const Invalid& i) : n(i) { }
1.854 -// NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.855 -// n(*(_G.graph)) { }
1.856 -// operator Node() const { return Node(typename Graph::Node(n)); }
1.857 -// };
1.858 - typedef typename GraphWrapper<Graph>::Edge Edge;
1.859 - class OutEdgeIt {
1.860 - friend class GraphWrapper<Graph>;
1.861 - friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.862 -// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.863 - typename Graph::OutEdgeIt e;
1.864 - public:
1.865 - OutEdgeIt() { }
1.866 - OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.867 - OutEdgeIt(const Invalid& i) : e(i) { }
1.868 - OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.869 - const Node& _n) :
1.870 - e((*_G.first_out_edges)[_n]) { }
1.871 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.872 - };
1.873 - class InEdgeIt {
1.874 - friend class GraphWrapper<Graph>;
1.875 - friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.876 -// typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.877 - typename Graph::InEdgeIt e;
1.878 - public:
1.879 - InEdgeIt() { }
1.880 - InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.881 - InEdgeIt(const Invalid& i) : e(i) { }
1.882 - InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.883 - const Node& _n) :
1.884 - e(*(_G.graph), typename Graph::Node(_n)) { }
1.885 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.886 - };
1.887 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.888 - class EdgeIt {
1.889 - friend class GraphWrapper<Graph>;
1.890 - friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.891 -// typedef typename Graph::EdgeIt GraphEdgeIt;
1.892 - typename Graph::EdgeIt e;
1.893 - public:
1.894 - EdgeIt() { }
1.895 - EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.896 - EdgeIt(const Invalid& i) : e(i) { }
1.897 - EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.898 - e(*(_G.graph)) { }
1.899 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.900 - };
1.901 -
1.902 - using GraphWrapper<Graph>::first;
1.903 -// NodeIt& first(NodeIt& i) const {
1.904 -// i=NodeIt(*this); return i;
1.905 -// }
1.906 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.907 - i=OutEdgeIt(*this, p); return i;
1.908 - }
1.909 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.910 - i=InEdgeIt(*this, p); return i;
1.911 - }
1.912 - EdgeIt& first(EdgeIt& i) const {
1.913 - i=EdgeIt(*this); return i;
1.914 - }
1.915 -
1.916 - using GraphWrapper<Graph>::next;
1.917 -// NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1.918 - OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.919 - InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.920 - EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
1.921 -
1.922 - Node aNode(const OutEdgeIt& e) const {
1.923 - return Node(this->graph->aNode(e.e)); }
1.924 - Node aNode(const InEdgeIt& e) const {
1.925 - return Node(this->graph->aNode(e.e)); }
1.926 - Node bNode(const OutEdgeIt& e) const {
1.927 - return Node(this->graph->bNode(e.e)); }
1.928 - Node bNode(const InEdgeIt& e) const {
1.929 - return Node(this->graph->bNode(e.e)); }
1.930 -
1.931 - void erase(const OutEdgeIt& e) const {
1.932 - OutEdgeIt f=e;
1.933 - this->next(f);
1.934 - first_out_edges->set(this->tail(e), f.e);
1.935 - }
1.936 - };
1.937 -
1.938 /// A wrapper for composing a bipartite graph.
1.939 /// \c _graph have to be a reference to a graph of type \c Graph
1.940 /// and \c _s_false_t_true_map is an \c IterableBoolMap
2.1 --- a/src/work/marci/bipartite_graph_wrapper_test.cc Fri Apr 30 13:52:17 2004 +0000
2.2 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc Fri Apr 30 14:02:10 2004 +0000
2.3 @@ -10,6 +10,7 @@
2.4 #include <for_each_macros.h>
2.5 #include <bfs_iterator.h>
2.6 #include <graph_wrapper.h>
2.7 +#include <bipartite_graph_wrapper.h>
2.8 #include <maps.h>
2.9 #include <max_flow.h>
2.10
3.1 --- a/src/work/marci/bipartite_matching_try.cc Fri Apr 30 13:52:17 2004 +0000
3.2 +++ b/src/work/marci/bipartite_matching_try.cc Fri Apr 30 14:02:10 2004 +0000
3.3 @@ -11,6 +11,7 @@
3.4 #include <for_each_macros.h>
3.5 #include <bfs_iterator.h>
3.6 #include <graph_wrapper.h>
3.7 +#include <bipartite_graph_wrapper.h>
3.8 #include <maps.h>
3.9 #include <max_flow.h>
3.10
4.1 --- a/src/work/marci/graph_wrapper.h Fri Apr 30 13:52:17 2004 +0000
4.2 +++ b/src/work/marci/graph_wrapper.h Fri Apr 30 14:02:10 2004 +0000
4.3 @@ -933,747 +933,6 @@
4.4 }
4.5 };
4.6
4.7 - /// A wrapper for composing a bipartite graph.
4.8 - /// \c _graph have to be a reference to a graph of type \c Graph
4.9 - /// and \c _s_false_t_true_map is an \c IterableBoolMap
4.10 - /// reference containing the elements for the
4.11 - /// color classes S and T. \c _graph is to be referred to an undirected
4.12 - /// graph or a directed graph with edges oriented from S to T.
4.13 - ///
4.14 - ///\author Marton Makai
4.15 - template<typename Graph>
4.16 - class BipartiteGraphWrapper : public GraphWrapper<Graph> {
4.17 - typedef IterableBoolMap< typename Graph::template NodeMap<int> >
4.18 - SFalseTTrueMap;
4.19 - SFalseTTrueMap* s_false_t_true_map;
4.20 -
4.21 - public:
4.22 - //marci
4.23 - //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
4.24 - //static const bool S_CLASS=false;
4.25 - //static const bool T_CLASS=true;
4.26 -
4.27 - bool S_CLASS;
4.28 - bool T_CLASS;
4.29 -
4.30 - BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
4.31 - : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map),
4.32 - S_CLASS(false), T_CLASS(true) { }
4.33 - typedef typename GraphWrapper<Graph>::Node Node;
4.34 - //using GraphWrapper<Graph>::NodeIt;
4.35 - typedef typename GraphWrapper<Graph>::Edge Edge;
4.36 - //using GraphWrapper<Graph>::EdgeIt;
4.37 - class ClassNodeIt;
4.38 - friend class ClassNodeIt;
4.39 - class OutEdgeIt;
4.40 - friend class OutEdgeIt;
4.41 - class InEdgeIt;
4.42 - friend class InEdgeIt;
4.43 - class ClassNodeIt {
4.44 - friend class BipartiteGraphWrapper<Graph>;
4.45 - protected:
4.46 - Node n;
4.47 - public:
4.48 - ClassNodeIt() { }
4.49 - ClassNodeIt(const Invalid& i) : n(i) { }
4.50 - ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
4.51 - _G.s_false_t_true_map->first(n, _class);
4.52 - }
4.53 - //FIXME needed in new concept, important here
4.54 - ClassNodeIt(const Node& _n) : n(_n) { }
4.55 - operator Node() const { return n; }
4.56 - };
4.57 -// class SNodeIt {
4.58 -// Node n;
4.59 -// public:
4.60 -// SNodeIt() { }
4.61 -// SNodeIt(const Invalid& i) : n(i) { }
4.62 -// SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
4.63 -// _G.s_false_t_true_map->first(n, false);
4.64 -// }
4.65 -// operator Node() const { return n; }
4.66 -// };
4.67 -// class TNodeIt {
4.68 -// Node n;
4.69 -// public:
4.70 -// TNodeIt() { }
4.71 -// TNodeIt(const Invalid& i) : n(i) { }
4.72 -// TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
4.73 -// _G.s_false_t_true_map->first(n, true);
4.74 -// }
4.75 -// operator Node() const { return n; }
4.76 -// };
4.77 - class OutEdgeIt {
4.78 - friend class BipartiteGraphWrapper<Graph>;
4.79 - protected:
4.80 - typename Graph::OutEdgeIt e;
4.81 - public:
4.82 - OutEdgeIt() { }
4.83 - OutEdgeIt(const Invalid& i) : e(i) { }
4.84 - OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
4.85 - if (!(*(_G.s_false_t_true_map))[_n])
4.86 - e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
4.87 - else
4.88 - e=INVALID;
4.89 - }
4.90 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
4.91 - };
4.92 - class InEdgeIt {
4.93 - friend class BipartiteGraphWrapper<Graph>;
4.94 - protected:
4.95 - typename Graph::InEdgeIt e;
4.96 - public:
4.97 - InEdgeIt() { }
4.98 - InEdgeIt(const Invalid& i) : e(i) { }
4.99 - InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
4.100 - if ((*(_G.s_false_t_true_map))[_n])
4.101 - e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
4.102 - else
4.103 - e=INVALID;
4.104 - }
4.105 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
4.106 - };
4.107 -
4.108 - using GraphWrapper<Graph>::first;
4.109 - ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
4.110 - n=ClassNodeIt(*this, _class) ; return n; }
4.111 -// SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
4.112 -// TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
4.113 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
4.114 - i=OutEdgeIt(*this, p); return i;
4.115 - }
4.116 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
4.117 - i=InEdgeIt(*this, p); return i;
4.118 - }
4.119 -
4.120 - using GraphWrapper<Graph>::next;
4.121 - ClassNodeIt& next(ClassNodeIt& n) const {
4.122 - this->s_false_t_true_map->next(n.n); return n;
4.123 - }
4.124 -// SNodeIt& next(SNodeIt& n) const {
4.125 -// this->s_false_t_true_map->next(n); return n;
4.126 -// }
4.127 -// TNodeIt& next(TNodeIt& n) const {
4.128 -// this->s_false_t_true_map->next(n); return n;
4.129 -// }
4.130 - OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
4.131 - InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
4.132 -
4.133 - Node tail(const Edge& e) {
4.134 - if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
4.135 - return Node(this->graph->tail(e));
4.136 - else
4.137 - return Node(this->graph->head(e));
4.138 - }
4.139 - Node head(const Edge& e) {
4.140 - if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
4.141 - return Node(this->graph->head(e));
4.142 - else
4.143 - return Node(this->graph->tail(e));
4.144 - }
4.145 -
4.146 - Node aNode(const OutEdgeIt& e) const {
4.147 - return Node(this->graph->aNode(e.e));
4.148 - }
4.149 - Node aNode(const InEdgeIt& e) const {
4.150 - return Node(this->graph->aNode(e.e));
4.151 - }
4.152 - Node bNode(const OutEdgeIt& e) const {
4.153 - return Node(this->graph->bNode(e.e));
4.154 - }
4.155 - Node bNode(const InEdgeIt& e) const {
4.156 - return Node(this->graph->bNode(e.e));
4.157 - }
4.158 -
4.159 - bool inSClass(const Node& n) const {
4.160 - return !(*(this->s_false_t_true_map))[n];
4.161 - }
4.162 - bool inTClass(const Node& n) const {
4.163 - return (*(this->s_false_t_true_map))[n];
4.164 - }
4.165 - };
4.166 -
4.167 - template<typename Graph>
4.168 - class stGraphWrapper;
4.169 -
4.170 -// template<typename Graph>
4.171 -// std::ostream&
4.172 -// operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) {
4.173 -// os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
4.174 -// return os;
4.175 -// }
4.176 -// template<typename Graph>
4.177 -// std::ostream&
4.178 -// operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) {
4.179 -// os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
4.180 -// " node: " << i.n << ")";
4.181 -// return os;
4.182 -// }
4.183 -
4.184 - /// experimentral, do not try it.
4.185 - /// It eats a bipartite graph, oriented from S to T.
4.186 - /// Such one can be made e.g. by the above wrapper.
4.187 - ///
4.188 - ///\author Marton Makai
4.189 - template<typename Graph>
4.190 - class stGraphWrapper : public GraphWrapper<Graph> {
4.191 - public:
4.192 - class Node;
4.193 - friend class Node;
4.194 -//GN, int
4.195 -//0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
4.196 -//es a vege a false azaz (invalid, 3)
4.197 - class NodeIt;
4.198 - friend class NodeIt;
4.199 -//GNI, int
4.200 - class Edge;
4.201 - friend class Edge;
4.202 -//GE, int, GN
4.203 -//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
4.204 -//invalid: (invalid, 3, invalid)
4.205 - class OutEdgeIt;
4.206 - friend class OutEdgeIt;
4.207 -//GO, int, GNI
4.208 -//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
4.209 -//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
4.210 -//t-bol (invalid, 3, invalid)
4.211 - class InEdgeIt;
4.212 - friend class InEdgeIt;
4.213 -//GI, int, GNI
4.214 -//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
4.215 -//s-be (invalid, 3, invalid)
4.216 -//t-be (invalid, 2, first), ... (invalid, 3, invalid)
4.217 - class EdgeIt;
4.218 - friend class EdgeIt;
4.219 -//(first, 0, invalid) ...
4.220 -//(invalid, 1, vmi)
4.221 -//(invalid, 2, vmi)
4.222 -//invalid, 3, invalid)
4.223 - template <typename T> class NodeMap;
4.224 - template <typename T, typename Parent> class EdgeMap;
4.225 -
4.226 -// template <typename T> friend class NodeMap;
4.227 -// template <typename T> friend class EdgeMap;
4.228 -
4.229 - const Node S_NODE;
4.230 - const Node T_NODE;
4.231 -
4.232 - static const bool S_CLASS=false;
4.233 - static const bool T_CLASS=true;
4.234 -
4.235 - stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
4.236 - S_NODE(INVALID, 1),
4.237 - T_NODE(INVALID, 2) { }
4.238 -
4.239 -
4.240 -// std::ostream&
4.241 -// operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
4.242 -// friend std::ostream&
4.243 -// operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
4.244 -// friend std::ostream&
4.245 -// operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);
4.246 -
4.247 - class Node : public Graph::Node {
4.248 - protected:
4.249 - friend class GraphWrapper<Graph>;
4.250 - friend class stGraphWrapper<Graph>;
4.251 - template <typename T> friend class NodeMap;
4.252 - friend class Edge;
4.253 - friend class OutEdgeIt;
4.254 - friend class InEdgeIt;
4.255 - friend class EdgeIt;
4.256 - int spec;
4.257 - public:
4.258 - Node() { }
4.259 - Node(const typename Graph::Node& _n, int _spec=0) :
4.260 - Graph::Node(_n), spec(_spec) { }
4.261 - Node(const Invalid& i) : Graph::Node(i), spec(3) { }
4.262 - friend bool operator==(const Node& u, const Node& v) {
4.263 - return (u.spec==v.spec &&
4.264 - static_cast<typename Graph::Node>(u)==
4.265 - static_cast<typename Graph::Node>(v));
4.266 - }
4.267 - friend bool operator!=(const Node& u, const Node& v) {
4.268 - return (v.spec!=u.spec ||
4.269 - static_cast<typename Graph::Node>(u)!=
4.270 - static_cast<typename Graph::Node>(v));
4.271 - }
4.272 -// template<typename G>
4.273 -// friend std::ostream&
4.274 -// operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i);
4.275 - friend std::ostream& operator<< (std::ostream& os, const Node& i);
4.276 - int getSpec() const { return spec; }
4.277 - };
4.278 -
4.279 - class NodeIt {
4.280 - friend class GraphWrapper<Graph>;
4.281 - friend class stGraphWrapper<Graph>;
4.282 - typename Graph::NodeIt n;
4.283 - int spec;
4.284 - public:
4.285 - NodeIt() { }
4.286 - NodeIt(const typename Graph::NodeIt& _n, int _spec) :
4.287 - n(_n), spec(_spec) { }
4.288 - NodeIt(const Invalid& i) : n(i), spec(3) { }
4.289 - NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
4.290 - if (!_G.graph->valid(n)) spec=1;
4.291 - }
4.292 - operator Node() const { return Node(n, spec); }
4.293 - };
4.294 -
4.295 - class Edge : public Graph::Edge {
4.296 - friend class GraphWrapper<Graph>;
4.297 - friend class stGraphWrapper<Graph>;
4.298 - template <typename T, typename Parent> friend class EdgeMap;
4.299 - int spec;
4.300 - typename Graph::Node n;
4.301 - public:
4.302 - Edge() { }
4.303 - Edge(const typename Graph::Edge& _e, int _spec,
4.304 - const typename Graph::Node& _n) :
4.305 - Graph::Edge(_e), spec(_spec), n(_n) {
4.306 - }
4.307 - Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
4.308 - friend bool operator==(const Edge& u, const Edge& v) {
4.309 - return (u.spec==v.spec &&
4.310 - static_cast<typename Graph::Edge>(u)==
4.311 - static_cast<typename Graph::Edge>(v) &&
4.312 - u.n==v.n);
4.313 - }
4.314 - friend bool operator!=(const Edge& u, const Edge& v) {
4.315 - return (v.spec!=u.spec ||
4.316 - static_cast<typename Graph::Edge>(u)!=
4.317 - static_cast<typename Graph::Edge>(v) ||
4.318 - u.n!=v.n);
4.319 - }
4.320 -// template<typename G>
4.321 -// friend std::ostream&
4.322 -// operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i);
4.323 - friend std::ostream& operator<< (std::ostream& os, const Edge& i);
4.324 - int getSpec() const { return spec; }
4.325 - };
4.326 -
4.327 - class OutEdgeIt {
4.328 - friend class GraphWrapper<Graph>;
4.329 - friend class stGraphWrapper<Graph>;
4.330 - typename Graph::OutEdgeIt e;
4.331 - int spec;
4.332 - typename Graph::ClassNodeIt n;
4.333 - public:
4.334 - OutEdgeIt() { }
4.335 - OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
4.336 - const typename Graph::ClassNodeIt& _n) :
4.337 - e(_e), spec(_spec), n(_n) {
4.338 - }
4.339 - OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
4.340 - OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
4.341 - switch (_n.spec) {
4.342 - case 0 :
4.343 - if (_G.graph->inSClass(_n)) { //S, van normalis kiel
4.344 - e=typename Graph::OutEdgeIt(*(_G.graph),
4.345 - typename Graph::Node(_n));
4.346 - spec=0;
4.347 - n=INVALID;
4.348 - if (!_G.graph->valid(e)) spec=3;
4.349 - } else { //T, specko kiel van
4.350 - e=INVALID;
4.351 - spec=2;
4.352 - n=_n;
4.353 - }
4.354 - break;
4.355 - case 1:
4.356 - e=INVALID;
4.357 - spec=1;
4.358 - _G.graph->first(n, S_CLASS); //s->vmi;
4.359 - if (!_G.graph->valid(n)) spec=3; //Ha S ures
4.360 - break;
4.361 - case 2:
4.362 - e=INVALID;
4.363 - spec=3;
4.364 - n=INVALID;
4.365 - break;
4.366 - }
4.367 - }
4.368 - operator Edge() const { return Edge(e, spec, n); }
4.369 - };
4.370 -
4.371 - class InEdgeIt {
4.372 - friend class GraphWrapper<Graph>;
4.373 - friend class stGraphWrapper<Graph>;
4.374 - typename Graph::InEdgeIt e;
4.375 - int spec;
4.376 - typename Graph::ClassNodeIt n;
4.377 - public:
4.378 - InEdgeIt() { }
4.379 - InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
4.380 - const typename Graph::ClassNodeIt& _n) :
4.381 - e(_e), spec(_spec), n(_n) {
4.382 - }
4.383 - InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
4.384 - InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
4.385 - switch (_n.spec) {
4.386 - case 0 :
4.387 - if (_G.graph->inTClass(_n)) { //T, van normalis beel
4.388 - e=typename Graph::InEdgeIt(*(_G.graph),
4.389 - typename Graph::Node(_n));
4.390 - spec=0;
4.391 - n=INVALID;
4.392 - if (!_G.graph->valid(e)) spec=3;
4.393 - } else { //S, specko beel van
4.394 - e=INVALID;
4.395 - spec=1;
4.396 - n=_n;
4.397 - }
4.398 - break;
4.399 - case 1:
4.400 - e=INVALID;
4.401 - spec=3;
4.402 - n=INVALID;
4.403 - break;
4.404 - case 2:
4.405 - e=INVALID;
4.406 - spec=2;
4.407 - _G.graph->first(n, T_CLASS); //vmi->t;
4.408 - if (!_G.graph->valid(n)) spec=3; //Ha T ures
4.409 - break;
4.410 - }
4.411 - }
4.412 - operator Edge() const { return Edge(e, spec, n); }
4.413 - };
4.414 -
4.415 - class EdgeIt {
4.416 - friend class GraphWrapper<Graph>;
4.417 - friend class stGraphWrapper<Graph>;
4.418 - typename Graph::EdgeIt e;
4.419 - int spec;
4.420 - typename Graph::ClassNodeIt n;
4.421 - public:
4.422 - EdgeIt() { }
4.423 - EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
4.424 - const typename Graph::ClassNodeIt& _n) :
4.425 - e(_e), spec(_spec), n(_n) { }
4.426 - EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
4.427 - EdgeIt(const stGraphWrapper<Graph>& _G) :
4.428 - e(*(_G.graph)), spec(0), n(INVALID) {
4.429 - if (!_G.graph->valid(e)) {
4.430 - spec=1;
4.431 - _G.graph->first(n, S_CLASS);
4.432 - if (!_G.graph->valid(n)) { //Ha S ures
4.433 - spec=2;
4.434 - _G.graph->first(n, T_CLASS);
4.435 - if (!_G.graph->valid(n)) { //Ha T ures
4.436 - spec=3;
4.437 - }
4.438 - }
4.439 - }
4.440 - }
4.441 - operator Edge() const { return Edge(e, spec, n); }
4.442 - };
4.443 -
4.444 - NodeIt& first(NodeIt& i) const {
4.445 - i=NodeIt(*this); return i;
4.446 - }
4.447 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
4.448 - i=OutEdgeIt(*this, p); return i;
4.449 - }
4.450 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
4.451 - i=InEdgeIt(*this, p); return i;
4.452 - }
4.453 - EdgeIt& first(EdgeIt& i) const {
4.454 - i=EdgeIt(*this); return i;
4.455 - }
4.456 -
4.457 - NodeIt& next(NodeIt& i) const {
4.458 - switch (i.spec) {
4.459 - case 0:
4.460 - this->graph->next(i.n);
4.461 - if (!this->graph->valid(i.n)) {
4.462 - i.spec=1;
4.463 - }
4.464 - break;
4.465 - case 1:
4.466 - i.spec=2;
4.467 - break;
4.468 - case 2:
4.469 - i.spec=3;
4.470 - break;
4.471 - }
4.472 - return i;
4.473 - }
4.474 - OutEdgeIt& next(OutEdgeIt& i) const {
4.475 - typename Graph::Node v;
4.476 - switch (i.spec) {
4.477 - case 0: //normal edge
4.478 - v=this->graph->aNode(i.e);
4.479 - this->graph->next(i.e);
4.480 - if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
4.481 - if (this->graph->inSClass(v)) { //S, nincs kiel
4.482 - i.spec=3;
4.483 - i.n=INVALID;
4.484 - } else { //T, van kiel
4.485 - i.spec=2;
4.486 - i.n=v;
4.487 - }
4.488 - }
4.489 - break;
4.490 - case 1: //s->vmi
4.491 - this->graph->next(i.n);
4.492 - if (!this->graph->valid(i.n)) i.spec=3;
4.493 - break;
4.494 - case 2: //vmi->t
4.495 - i.spec=3;
4.496 - i.n=INVALID;
4.497 - break;
4.498 - }
4.499 - return i;
4.500 - }
4.501 - InEdgeIt& next(InEdgeIt& i) const {
4.502 - typename Graph::Node v;
4.503 - switch (i.spec) {
4.504 - case 0: //normal edge
4.505 - v=this->graph->aNode(i.e);
4.506 - this->graph->next(i.e);
4.507 - if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
4.508 - if (this->graph->inTClass(v)) { //S, nincs beel
4.509 - i.spec=3;
4.510 - i.n=INVALID;
4.511 - } else { //S, van beel
4.512 - i.spec=1;
4.513 - i.n=v;
4.514 - }
4.515 - }
4.516 - break;
4.517 - case 1: //s->vmi
4.518 - i.spec=3;
4.519 - i.n=INVALID;
4.520 - break;
4.521 - case 2: //vmi->t
4.522 - this->graph->next(i.n);
4.523 - if (!this->graph->valid(i.n)) i.spec=3;
4.524 - break;
4.525 - }
4.526 - return i;
4.527 - }
4.528 -
4.529 - EdgeIt& next(EdgeIt& i) const {
4.530 - switch (i.spec) {
4.531 - case 0:
4.532 - this->graph->next(i.e);
4.533 - if (!this->graph->valid(i.e)) {
4.534 - i.spec=1;
4.535 - this->graph->first(i.n, S_CLASS);
4.536 - if (!this->graph->valid(i.n)) {
4.537 - i.spec=2;
4.538 - this->graph->first(i.n, T_CLASS);
4.539 - if (!this->graph->valid(i.n)) i.spec=3;
4.540 - }
4.541 - }
4.542 - break;
4.543 - case 1:
4.544 - this->graph->next(i.n);
4.545 - if (!this->graph->valid(i.n)) {
4.546 - i.spec=2;
4.547 - this->graph->first(i.n, T_CLASS);
4.548 - if (!this->graph->valid(i.n)) i.spec=3;
4.549 - }
4.550 - break;
4.551 - case 2:
4.552 - this->graph->next(i.n);
4.553 - if (!this->graph->valid(i.n)) i.spec=3;
4.554 - break;
4.555 - }
4.556 - return i;
4.557 - }
4.558 -
4.559 - Node tail(const Edge& e) const {
4.560 - switch (e.spec) {
4.561 - case 0:
4.562 - return Node(this->graph->tail(e));
4.563 - break;
4.564 - case 1:
4.565 - return S_NODE;
4.566 - break;
4.567 - case 2:
4.568 - default:
4.569 - return Node(e.n);
4.570 - break;
4.571 - }
4.572 - }
4.573 - Node head(const Edge& e) const {
4.574 - switch (e.spec) {
4.575 - case 0:
4.576 - return Node(this->graph->head(e));
4.577 - break;
4.578 - case 1:
4.579 - return Node(e.n);
4.580 - break;
4.581 - case 2:
4.582 - default:
4.583 - return T_NODE;
4.584 - break;
4.585 - }
4.586 - }
4.587 -
4.588 - bool valid(const Node& n) const { return (n.spec<3); }
4.589 - bool valid(const Edge& e) const { return (e.spec<3); }
4.590 -
4.591 - int nodeNum() const { return this->graph->nodeNum()+2; }
4.592 - int edgeNum() const {
4.593 - return this->graph->edgeNum()+this->graph->nodeNum();
4.594 - }
4.595 -
4.596 - Node aNode(const OutEdgeIt& e) const { return tail(e); }
4.597 - Node aNode(const InEdgeIt& e) const { return head(e); }
4.598 - Node bNode(const OutEdgeIt& e) const { return head(e); }
4.599 - Node bNode(const InEdgeIt& e) const { return tail(e); }
4.600 -
4.601 - void addNode() const { }
4.602 - void addEdge() const { }
4.603 -
4.604 -// Node addNode() const { return Node(this->graph->addNode()); }
4.605 -// Edge addEdge(const Node& tail, const Node& head) const {
4.606 -// return Edge(this->graph->addEdge(tail, head)); }
4.607 -
4.608 -// void erase(const Node& i) const { this->graph->erase(i); }
4.609 -// void erase(const Edge& i) const { this->graph->erase(i); }
4.610 -
4.611 -// void clear() const { this->graph->clear(); }
4.612 -
4.613 - template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
4.614 - typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
4.615 - T s_value, t_value;
4.616 - public:
4.617 - NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
4.618 - s_value(),
4.619 - t_value() { }
4.620 - NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
4.621 - s_value(a),
4.622 - t_value(a) { }
4.623 - T operator[](const Node& n) const {
4.624 - switch (n.spec) {
4.625 - case 0:
4.626 - return Parent::operator[](n);
4.627 - break;
4.628 - case 1:
4.629 - return s_value;
4.630 - break;
4.631 - case 2:
4.632 - default:
4.633 - return t_value;
4.634 - break;
4.635 - }
4.636 - }
4.637 - void set(const Node& n, T t) {
4.638 - switch (n.spec) {
4.639 - case 0:
4.640 - GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
4.641 - break;
4.642 - case 1:
4.643 - s_value=t;
4.644 - break;
4.645 - case 2:
4.646 - default:
4.647 - t_value=t;
4.648 - break;
4.649 - }
4.650 - }
4.651 - };
4.652 -
4.653 - template<typename T,
4.654 - typename Parent=
4.655 - typename GraphWrapper<Graph>::template EdgeMap<T> >
4.656 - class EdgeMap : public Parent {
4.657 - //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
4.658 - typename GraphWrapper<Graph>::template NodeMap<T> node_value;
4.659 - public:
4.660 - EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
4.661 - node_value(_G) { }
4.662 - EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
4.663 - node_value(_G, a) { }
4.664 - T operator[](const Edge& e) const {
4.665 - switch (e.spec) {
4.666 - case 0:
4.667 - return Parent::operator[](e);
4.668 - break;
4.669 - case 1:
4.670 - return node_value[e.n];
4.671 - break;
4.672 - case 2:
4.673 - default:
4.674 - return node_value[e.n];
4.675 - break;
4.676 - }
4.677 - }
4.678 - void set(const Edge& e, T t) {
4.679 - switch (e.spec) {
4.680 - case 0:
4.681 - Parent::set(e, t);
4.682 - break;
4.683 - case 1:
4.684 - node_value.set(e.n, t);
4.685 - break;
4.686 - case 2:
4.687 - default:
4.688 - node_value.set(e.n, t);
4.689 - break;
4.690 - }
4.691 - }
4.692 - };
4.693 -
4.694 -// template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
4.695 -// typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
4.696 -// typename GraphWrapper<Graph>::template NodeMap<T> node_value;
4.697 -// public:
4.698 -// EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
4.699 -// node_value(_G) { }
4.700 -// EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
4.701 -// node_value(_G, a) { }
4.702 -// T operator[](const Edge& e) const {
4.703 -// switch (e.spec) {
4.704 -// case 0:
4.705 -// return Parent::operator[](e);
4.706 -// break;
4.707 -// case 1:
4.708 -// return node_value[e.n];
4.709 -// break;
4.710 -// case 2:
4.711 -// default:
4.712 -// return node_value[e.n];
4.713 -// break;
4.714 -// }
4.715 -// }
4.716 -// void set(const Edge& e, T t) {
4.717 -// switch (e.spec) {
4.718 -// case 0:
4.719 -// GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
4.720 -// break;
4.721 -// case 1:
4.722 -// node_value.set(e.n, t);
4.723 -// break;
4.724 -// case 2:
4.725 -// default:
4.726 -// node_value.set(e.n, t);
4.727 -// break;
4.728 -// }
4.729 -// }
4.730 -// };
4.731 -
4.732 -// template<typename G>
4.733 - friend std::ostream&
4.734 - operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) {
4.735 - os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
4.736 - return os;
4.737 - }
4.738 -// template<typename G>
4.739 - friend std::ostream&
4.740 - operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) {
4.741 - os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
4.742 - " node: " << i.n << ")";
4.743 - return os;
4.744 - }
4.745 -
4.746 - };
4.747 -
4.748 ///@}
4.749
4.750 } //namespace hugo
5.1 --- a/src/work/marci/leda/bipartite_matching_leda.cc Fri Apr 30 13:52:17 2004 +0000
5.2 +++ b/src/work/marci/leda/bipartite_matching_leda.cc Fri Apr 30 14:02:10 2004 +0000
5.3 @@ -17,6 +17,7 @@
5.4 #include <for_each_macros.h>
5.5 //#include <bfs_iterator.h>
5.6 #include <graph_wrapper.h>
5.7 +#include <bipartite_graph_wrapper.h>
5.8 #include <maps.h>
5.9 #include <max_flow.h>
5.10
6.1 --- a/src/work/marci/leda/bipartite_matching_leda_gen.cc Fri Apr 30 13:52:17 2004 +0000
6.2 +++ b/src/work/marci/leda/bipartite_matching_leda_gen.cc Fri Apr 30 14:02:10 2004 +0000
6.3 @@ -16,6 +16,7 @@
6.4 #include <time_measure.h>
6.5 #include <for_each_macros.h>
6.6 #include <graph_wrapper.h>
6.7 +#include <bipartite_graph_wrapper.h>
6.8 #include <maps.h>
6.9 #include <max_flow.h>
6.10