1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bpugraph_adaptor.h Mon Apr 03 09:45:23 2006 +0000
1.3 @@ -0,0 +1,412 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_BPUGRAPH_ADAPTOR_H
1.23 +#define LEMON_BPUGRAPH_ADAPTOR_H
1.24 +
1.25 +#include <lemon/bits/invalid.h>
1.26 +#include <lemon/maps.h>
1.27 +
1.28 +#include <lemon/bits/graph_adaptor_extender.h>
1.29 +
1.30 +#include <lemon/bits/traits.h>
1.31 +
1.32 +#include <iostream>
1.33 +
1.34 +///\ingroup graph_adaptors
1.35 +///\file
1.36 +///\brief Several graph adaptors.
1.37 +///
1.38 +///This file contains several useful bpugraph adaptor functions.
1.39 +///
1.40 +///\author Balazs Dezso
1.41 +
1.42 +namespace lemon {
1.43 +
1.44 + /// \ingroup graph_adaptors
1.45 + ///
1.46 + /// \brief Base type for the Bipartite Undirected Graph Adaptors
1.47 + ///
1.48 + /// This is the base type for most of LEMON bpugraph adaptors.
1.49 + /// This class implements a trivial graph adaptor i.e. it only wraps the
1.50 + /// functions and types of the graph. The purpose of this class is to
1.51 + /// make easier implementing graph adaptors. E.g. if an adaptor is
1.52 + /// considered which differs from the wrapped graph only in some of its
1.53 + /// functions or types, then it can be derived from BpUGraphAdaptor, and
1.54 + /// only the differences should be implemented.
1.55 + ///
1.56 + /// \author Balazs Dezso
1.57 + template<typename _BpUGraph>
1.58 + class BpUGraphAdaptorBase {
1.59 + public:
1.60 + typedef _BpUGraph Graph;
1.61 + typedef Graph ParentGraph;
1.62 +
1.63 + protected:
1.64 + Graph* graph;
1.65 +
1.66 + BpUGraphAdaptorBase() : graph(0) {}
1.67 +
1.68 + void setGraph(Graph& _graph) { graph = &_graph; }
1.69 +
1.70 + Graph& getGraph() { return *graph; }
1.71 + const Graph& getGraph() const { return *graph; }
1.72 +
1.73 + public:
1.74 +
1.75 + BpUGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
1.76 +
1.77 + typedef typename Graph::Node Node;
1.78 + typedef typename Graph::ANode ANode;
1.79 + typedef typename Graph::BNode BNode;
1.80 + typedef typename Graph::Edge Edge;
1.81 + typedef typename Graph::UEdge UEdge;
1.82 +
1.83 + void first(Node& i) const { graph->first(i); }
1.84 + void firstANode(Node& i) const { graph->firstANode(i); }
1.85 + void firstBNode(Node& i) const { graph->firstBNode(i); }
1.86 + void first(Edge& i) const { graph->first(i); }
1.87 + void first(UEdge& i) const { graph->first(i); }
1.88 + void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
1.89 + void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
1.90 + void firstInc(UEdge &i, bool &d, const Node &n) const {
1.91 + graph->firstInc(i, d, n);
1.92 + }
1.93 +
1.94 + void next(Node& i) const { graph->next(i); }
1.95 + void nextANode(Node& i) const { graph->nextANode(i); }
1.96 + void nextBNode(Node& i) const { graph->nextBNode(i); }
1.97 + void next(Edge& i) const { graph->next(i); }
1.98 + void next(UEdge& i) const { graph->next(i); }
1.99 + void nextIn(Edge& i) const { graph->nextIn(i); }
1.100 + void nextOut(Edge& i) const { graph->nextOut(i); }
1.101 + void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
1.102 +
1.103 + Node source(const UEdge& e) const { return graph->source(e); }
1.104 + Node target(const UEdge& e) const { return graph->target(e); }
1.105 +
1.106 + Node source(const Edge& e) const { return graph->source(e); }
1.107 + Node target(const Edge& e) const { return graph->target(e); }
1.108 +
1.109 + typedef NodeNumTagIndicator<Graph> NodeNumTag;
1.110 + int nodeNum() const { return graph->nodeNum(); }
1.111 + int aNodeNum() const { return graph->aNodeNum(); }
1.112 + int bNodeNum() const { return graph->bNodeNum(); }
1.113 +
1.114 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
1.115 + int edgeNum() const { return graph->edgeNum(); }
1.116 + int uEdgeNum() const { return graph->uEdgeNum(); }
1.117 +
1.118 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.119 + Edge findEdge(const Node& source, const Node& target,
1.120 + const Edge& prev = INVALID) {
1.121 + return graph->findEdge(source, target, prev);
1.122 + }
1.123 + UEdge findUEdge(const Node& source, const Node& target,
1.124 + const UEdge& prev = INVALID) {
1.125 + return graph->findUEdge(source, target, prev);
1.126 + }
1.127 +
1.128 + Node addNode() const { return graph->addNode(); }
1.129 + UEdge addEdge(const Node& source, const Node& target) const {
1.130 + return graph->addEdge(source, target);
1.131 + }
1.132 +
1.133 + void erase(const Node& i) const { graph->erase(i); }
1.134 + void erase(const UEdge& i) const { graph->erase(i); }
1.135 +
1.136 + void clear() const { graph->clear(); }
1.137 +
1.138 + bool direction(const Edge& e) const { return graph->direction(e); }
1.139 + Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
1.140 +
1.141 + int id(const Node& v) const { return graph->id(v); }
1.142 + int id(const ANode& v) const { return graph->id(v); }
1.143 + int id(const BNode& v) const { return graph->id(v); }
1.144 + int id(const Edge& e) const { return graph->id(e); }
1.145 + int id(const UEdge& e) const { return graph->id(e); }
1.146 +
1.147 + Node fromNodeId(int id) const { return graph->fromNodeId(id); }
1.148 + ANode fromANodeId(int id) const { return graph->fromANodeId(id); }
1.149 + BNode fromBNodeId(int id) const { return graph->fromBNodeId(id); }
1.150 + Edge fromEdgeId(int id) const { return graph->fromEdgeId(id); }
1.151 + UEdge fromUEdgeId(int id) const { return graph->fromUEdgeId(id); }
1.152 +
1.153 + int maxNodeId() const { return graph->maxNodeId(); }
1.154 + int maxANodeId() const { return graph->maxANodeId(); }
1.155 + int maxBNodeId() const { return graph->maxBNodeId(); }
1.156 + int maxEdgeId() const { return graph->maxEdgeId(); }
1.157 + int maxUEdgeId() const { return graph->maxEdgeId(); }
1.158 +
1.159 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.160 + NodeNotifier& getNotifier(Node) const {
1.161 + return graph->getNotifier(Node());
1.162 + }
1.163 +
1.164 + typedef typename ItemSetTraits<Graph, ANode>::ItemNotifier ANodeNotifier;
1.165 + ANodeNotifier& getNotifier(ANode) const {
1.166 + return graph->getNotifier(ANode());
1.167 + }
1.168 +
1.169 + typedef typename ItemSetTraits<Graph, BNode>::ItemNotifier BNodeNotifier;
1.170 + BNodeNotifier& getNotifier(BNode) const {
1.171 + return graph->getNotifier(BNode());
1.172 + }
1.173 +
1.174 + typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
1.175 + EdgeNotifier& getNotifier(Edge) const {
1.176 + return graph->getNotifier(Edge());
1.177 + }
1.178 +
1.179 + typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
1.180 + UEdgeNotifier& getNotifier(UEdge) const {
1.181 + return graph->getNotifier(UEdge());
1.182 + }
1.183 +
1.184 + template <typename _Value>
1.185 + class NodeMap : public Graph::template NodeMap<_Value> {
1.186 + public:
1.187 + typedef typename Graph::template NodeMap<_Value> Parent;
1.188 + explicit NodeMap(const BpUGraphAdaptorBase<Graph>& ga)
1.189 + : Parent(*ga.graph) {}
1.190 + NodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
1.191 + : Parent(*ga.graph, value) {}
1.192 +
1.193 + NodeMap& operator=(const NodeMap& cmap) {
1.194 + return operator=<NodeMap>(cmap);
1.195 + }
1.196 +
1.197 + template <typename CMap>
1.198 + NodeMap& operator=(const CMap& cmap) {
1.199 + Parent::operator=(cmap);
1.200 + return *this;
1.201 + }
1.202 + };
1.203 +
1.204 + template <typename _Value>
1.205 + class ANodeMap : public Graph::template ANodeMap<_Value> {
1.206 + public:
1.207 + typedef typename Graph::template ANodeMap<_Value> Parent;
1.208 + explicit ANodeMap(const BpUGraphAdaptorBase& ga)
1.209 + : Parent(*ga.graph) {}
1.210 + ANodeMap(const BpUGraphAdaptorBase& ga, const _Value& value)
1.211 + : Parent(*ga.graph, value) {}
1.212 +
1.213 + ANodeMap& operator=(const ANodeMap& cmap) {
1.214 + return operator=<ANodeMap>(cmap);
1.215 + }
1.216 +
1.217 + template <typename CMap>
1.218 + ANodeMap& operator=(const CMap& cmap) {
1.219 + Parent::operator=(cmap);
1.220 + return *this;
1.221 + }
1.222 + };
1.223 +
1.224 + template <typename _Value>
1.225 + class BNodeMap : public Graph::template BNodeMap<_Value> {
1.226 + public:
1.227 + typedef typename Graph::template BNodeMap<_Value> Parent;
1.228 + explicit BNodeMap(const BpUGraphAdaptorBase<Graph>& ga)
1.229 + : Parent(*ga.graph) {}
1.230 + BNodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
1.231 + : Parent(*ga.graph, value) {}
1.232 +
1.233 + BNodeMap& operator=(const BNodeMap& cmap) {
1.234 + return operator=<BNodeMap>(cmap);
1.235 + }
1.236 +
1.237 + template <typename CMap>
1.238 + BNodeMap& operator=(const CMap& cmap) {
1.239 + Parent::operator=(cmap);
1.240 + return *this;
1.241 + }
1.242 + };
1.243 +
1.244 + template <typename _Value>
1.245 + class EdgeMap : public Graph::template EdgeMap<_Value> {
1.246 + public:
1.247 + typedef typename Graph::template EdgeMap<_Value> Parent;
1.248 + explicit EdgeMap(const BpUGraphAdaptorBase<Graph>& ga)
1.249 + : Parent(*ga.graph) {}
1.250 + EdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
1.251 + : Parent(*ga.graph, value) {}
1.252 +
1.253 + EdgeMap& operator=(const EdgeMap& cmap) {
1.254 + return operator=<EdgeMap>(cmap);
1.255 + }
1.256 +
1.257 + template <typename CMap>
1.258 + EdgeMap& operator=(const CMap& cmap) {
1.259 + Parent::operator=(cmap);
1.260 + return *this;
1.261 + }
1.262 + };
1.263 +
1.264 + template <typename _Value>
1.265 + class UEdgeMap : public Graph::template UEdgeMap<_Value> {
1.266 + public:
1.267 + typedef typename Graph::template UEdgeMap<_Value> Parent;
1.268 + explicit UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga)
1.269 + : Parent(*ga.graph) {}
1.270 + UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
1.271 + : Parent(*ga.graph, value) {}
1.272 +
1.273 + UEdgeMap& operator=(const UEdgeMap& cmap) {
1.274 + return operator=<UEdgeMap>(cmap);
1.275 + }
1.276 +
1.277 + template <typename CMap>
1.278 + UEdgeMap& operator=(const CMap& cmap) {
1.279 + Parent::operator=(cmap);
1.280 + return *this;
1.281 + }
1.282 + };
1.283 +
1.284 + };
1.285 +
1.286 + /// \ingroup graph_adaptors
1.287 + template <typename _BpUGraph>
1.288 + class BpUGraphAdaptor
1.289 + : public BpUGraphAdaptorExtender< BpUGraphAdaptorBase<_BpUGraph> > {
1.290 + public:
1.291 + typedef _BpUGraph Graph;
1.292 + typedef BpUGraphAdaptorExtender<BpUGraphAdaptorBase<_BpUGraph> > Parent;
1.293 + protected:
1.294 + BpUGraphAdaptor() : Parent() {}
1.295 +
1.296 + public:
1.297 + explicit BpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
1.298 + };
1.299 +
1.300 + template <typename _BpUGraph>
1.301 + class SwapBpUGraphAdaptorBase : public BpUGraphAdaptorBase<_BpUGraph> {
1.302 + public:
1.303 +
1.304 + typedef _BpUGraph Graph;
1.305 + typedef BpUGraphAdaptorBase<_BpUGraph> Parent;
1.306 +
1.307 + protected:
1.308 +
1.309 + SwapBpUGraphAdaptorBase() {}
1.310 +
1.311 + public:
1.312 +
1.313 + typedef typename Parent::Node Node;
1.314 + typedef typename Parent::BNode ANode;
1.315 + typedef typename Parent::ANode BNode;
1.316 +
1.317 + void firstANode(Node& i) const { Parent::firstBNode(i); }
1.318 + void firstBNode(Node& i) const { Parent::firstANode(i); }
1.319 +
1.320 + void nextANode(Node& i) const { Parent::nextBNode(i); }
1.321 + void nextBNode(Node& i) const { Parent::nextANode(i); }
1.322 +
1.323 + int id(const ANode& v) const { return Parent::id(v); }
1.324 + int id(const BNode& v) const { return Parent::id(v); }
1.325 +
1.326 + ANode fromANodeId(int id) const { return Parent::fromBNodeId(id); }
1.327 + BNode fromBNodeId(int id) const { return Parent::fromANodeId(id); }
1.328 +
1.329 + int maxANodeId() const { return Parent::maxBNodeId(); }
1.330 + int maxBNodeId() const { return Parent::maxANodeId(); }
1.331 +
1.332 + int aNodeNum() const { return Parent::bNodeNum(); }
1.333 + int bNodeNum() const { return Parent::aNodeNum(); }
1.334 +
1.335 + typedef typename Parent::BNodeNotifier ANodeNotifier;
1.336 + ANodeNotifier& getNotifier(ANode) const {
1.337 + return Parent::getNotifier(typename Parent::BNode());
1.338 + }
1.339 +
1.340 + typedef typename Parent::ANodeNotifier BNodeNotifier;
1.341 + BNodeNotifier& getNotifier(BNode) const {
1.342 + return Parent::getNotifier(typename Parent::ANode());
1.343 + }
1.344 +
1.345 + template <typename _Value>
1.346 + class ANodeMap : public Graph::template BNodeMap<_Value> {
1.347 + public:
1.348 + typedef typename Graph::template BNodeMap<_Value> Parent;
1.349 + explicit ANodeMap(const SwapBpUGraphAdaptorBase& ga)
1.350 + : Parent(*ga.graph) {}
1.351 + ANodeMap(const SwapBpUGraphAdaptorBase& ga, const _Value& value)
1.352 + : Parent(*ga.graph, value) {}
1.353 +
1.354 + ANodeMap& operator=(const ANodeMap& cmap) {
1.355 + return operator=<ANodeMap>(cmap);
1.356 + }
1.357 +
1.358 + template <typename CMap>
1.359 + ANodeMap& operator=(const CMap& cmap) {
1.360 + Parent::operator=(cmap);
1.361 + return *this;
1.362 + }
1.363 + };
1.364 +
1.365 + template <typename _Value>
1.366 + class BNodeMap : public Graph::template ANodeMap<_Value> {
1.367 + public:
1.368 + typedef typename Graph::template ANodeMap<_Value> Parent;
1.369 + explicit BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga)
1.370 + : Parent(*ga.graph) {}
1.371 + BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga, const _Value& value)
1.372 + : Parent(*ga.graph, value) {}
1.373 +
1.374 + BNodeMap& operator=(const BNodeMap& cmap) {
1.375 + return operator=<BNodeMap>(cmap);
1.376 + }
1.377 +
1.378 + template <typename CMap>
1.379 + BNodeMap& operator=(const CMap& cmap) {
1.380 + Parent::operator=(cmap);
1.381 + return *this;
1.382 + }
1.383 + };
1.384 +
1.385 + };
1.386 +
1.387 + /// \ingroup graph_adaptors
1.388 + ///
1.389 + /// \brief Bipartite graph adaptor which swaps the two nodeset.
1.390 + ///
1.391 + /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
1.392 + /// a-nodeset will be the original graph's b-nodeset and the adaptor's
1.393 + /// b-nodeset will be the original graph's a-nodeset.
1.394 + template <typename _BpUGraph>
1.395 + class SwapBpUGraphAdaptor
1.396 + : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > {
1.397 + public:
1.398 +
1.399 + typedef _BpUGraph Graph;
1.400 + typedef BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> >
1.401 + Parent;
1.402 +
1.403 + protected:
1.404 + SwapBpUGraphAdaptor() : Parent() {}
1.405 +
1.406 + public:
1.407 +
1.408 + explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
1.409 +
1.410 + };
1.411 +
1.412 +
1.413 +}
1.414 +
1.415 +#endif