lemon-0.x: lemon/bpugraph_adaptor.h@080d51024ac5

     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2006

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    19 #ifndef LEMON_BPUGRAPH_ADAPTOR_H

    20 #define LEMON_BPUGRAPH_ADAPTOR_H

    22 #include <lemon/bits/invalid.h>

    23 #include <lemon/maps.h>

    25 #include <lemon/bits/graph_adaptor_extender.h>

    27 #include <lemon/bits/traits.h>

    29 #include <iostream>

    31 ///\ingroup graph_adaptors

    32 ///\file

    33 ///\brief Several graph adaptors.

    34 ///

    35 ///This file contains several useful bpugraph adaptor functions.

    36 ///

    37 ///\author Balazs Dezso

    39 namespace lemon {

    41   /// \ingroup graph_adaptors

    42   ///

    43   /// \brief Base type for the Bipartite Undirected Graph Adaptors

    44   ///

    45   /// This is the base type for most of LEMON bpugraph adaptors.

    46   /// This class implements a trivial graph adaptor i.e. it only wraps the

    47   /// functions and types of the graph. The purpose of this class is to

    48   /// make easier implementing graph adaptors. E.g. if an adaptor is

    49   /// considered which differs from the wrapped graph only in some of its

    50   /// functions or types, then it can be derived from BpUGraphAdaptor, and

    51   /// only the differences should be implemented.

    52   ///

    53   /// \author Balazs Dezso

    54   template<typename _BpUGraph>

    55   class BpUGraphAdaptorBase {

    56   public:

    57     typedef _BpUGraph Graph;

    58     typedef Graph ParentGraph;

    60   protected:

    61     Graph* graph;

    63     BpUGraphAdaptorBase() : graph(0) {}

    65     void setGraph(Graph& _graph) { graph = &_graph; }

    67     Graph& getGraph() { return *graph; }

    68     const Graph& getGraph() const { return *graph; }

    70   public:

    72     BpUGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}

    74     typedef typename Graph::Node Node;

    75     typedef typename Graph::ANode ANode;

    76     typedef typename Graph::BNode BNode;

    77     typedef typename Graph::Edge Edge;

    78     typedef typename Graph::UEdge UEdge;

    80     void first(Node& i) const { graph->first(i); }

    81     void firstANode(Node& i) const { graph->firstANode(i); }

    82     void firstBNode(Node& i) const { graph->firstBNode(i); }

    83     void first(Edge& i) const { graph->first(i); }

    84     void first(UEdge& i) const { graph->first(i); }

    85     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }

    86     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }

    87     void firstInc(UEdge &i, bool &d, const Node &n) const {

    88       graph->firstInc(i, d, n);

    89     }

    91     void next(Node& i) const { graph->next(i); }

    92     void nextANode(Node& i) const { graph->nextANode(i); }

    93     void nextBNode(Node& i) const { graph->nextBNode(i); }

    94     void next(Edge& i) const { graph->next(i); }

    95     void next(UEdge& i) const { graph->next(i); }

    96     void nextIn(Edge& i) const { graph->nextIn(i); }

    97     void nextOut(Edge& i) const { graph->nextOut(i); }

    98     void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }

   100     Node source(const UEdge& e) const { return graph->source(e); }

   101     Node target(const UEdge& e) const { return graph->target(e); }

   103     Node source(const Edge& e) const { return graph->source(e); }

   104     Node target(const Edge& e) const { return graph->target(e); }

   106     typedef NodeNumTagIndicator<Graph> NodeNumTag;

   107     int nodeNum() const { return graph->nodeNum(); }

   108     int aNodeNum() const { return graph->aNodeNum(); }

   109     int bNodeNum() const { return graph->bNodeNum(); }

   111     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

   112     int edgeNum() const { return graph->edgeNum(); }

   113     int uEdgeNum() const { return graph->uEdgeNum(); }

   115     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

   116     Edge findEdge(const Node& source, const Node& target,

   117 		  const Edge& prev = INVALID) {

   118       return graph->findEdge(source, target, prev);

   119     }

   120     UEdge findUEdge(const Node& source, const Node& target,

   121                     const UEdge& prev = INVALID) {

   122       return graph->findUEdge(source, target, prev);

   123     }

   125     Node addNode() const { return graph->addNode(); }

   126     UEdge addEdge(const Node& source, const Node& target) const {

   127       return graph->addEdge(source, target);

   128     }

   130     void erase(const Node& i) const { graph->erase(i); }

   131     void erase(const UEdge& i) const { graph->erase(i); }

   133     void clear() const { graph->clear(); }

   135     bool direction(const Edge& e) const { return graph->direction(e); }

   136     Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }

   138     int id(const Node& v) const { return graph->id(v); }

   139     int id(const ANode& v) const { return graph->id(v); }

   140     int id(const BNode& v) const { return graph->id(v); }

   141     int id(const Edge& e) const { return graph->id(e); }

   142     int id(const UEdge& e) const { return graph->id(e); }

   144     Node fromNodeId(int id) const { return graph->fromNodeId(id); }

   145     ANode fromANodeId(int id) const { return graph->fromANodeId(id); }

   146     BNode fromBNodeId(int id) const { return graph->fromBNodeId(id); }

   147     Edge fromEdgeId(int id) const { return graph->fromEdgeId(id); }

   148     UEdge fromUEdgeId(int id) const { return graph->fromUEdgeId(id); }

   150     int maxNodeId() const { return graph->maxNodeId(); }

   151     int maxANodeId() const { return graph->maxANodeId(); }

   152     int maxBNodeId() const { return graph->maxBNodeId(); }

   153     int maxEdgeId() const { return graph->maxEdgeId(); }

   154     int maxUEdgeId() const { return graph->maxEdgeId(); }

   156     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;

   157     NodeNotifier& getNotifier(Node) const {

   158       return graph->getNotifier(Node());

   159     }

   161     typedef typename ItemSetTraits<Graph, ANode>::ItemNotifier ANodeNotifier;

   162     ANodeNotifier& getNotifier(ANode) const {

   163       return graph->getNotifier(ANode());

   164     }

   166     typedef typename ItemSetTraits<Graph, BNode>::ItemNotifier BNodeNotifier;

   167     BNodeNotifier& getNotifier(BNode) const {

   168       return graph->getNotifier(BNode());

   169     }

   171     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;

   172     EdgeNotifier& getNotifier(Edge) const {

   173       return graph->getNotifier(Edge());

   174     }

   176     typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;

   177     UEdgeNotifier& getNotifier(UEdge) const {

   178       return graph->getNotifier(UEdge());

   179     }

   181     template <typename _Value>

   182     class NodeMap : public Graph::template NodeMap<_Value> {

   183     public:

   184       typedef typename Graph::template NodeMap<_Value> Parent;

   185       explicit NodeMap(const BpUGraphAdaptorBase<Graph>& ga)

   186 	: Parent(*ga.graph) {}

   187       NodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)

   188 	: Parent(*ga.graph, value) {}

   190       NodeMap& operator=(const NodeMap& cmap) {

   191 	return operator=<NodeMap>(cmap);

   192       }

   194       template <typename CMap>

   195       NodeMap& operator=(const CMap& cmap) {

   196         Parent::operator=(cmap);

   197 	return *this;

   198       }

   199     };

   201     template <typename _Value>

   202     class ANodeMap : public Graph::template ANodeMap<_Value> {

   203     public:

   204       typedef typename Graph::template ANodeMap<_Value> Parent;

   205       explicit ANodeMap(const BpUGraphAdaptorBase& ga)

   206 	: Parent(*ga.graph) {}

   207       ANodeMap(const BpUGraphAdaptorBase& ga, const _Value& value)

   208 	: Parent(*ga.graph, value) {}

   210       ANodeMap& operator=(const ANodeMap& cmap) {

   211 	return operator=<ANodeMap>(cmap);

   212       }

   214       template <typename CMap>

   215       ANodeMap& operator=(const CMap& cmap) {

   216         Parent::operator=(cmap);

   217 	return *this;

   218       }

   219     };

   221     template <typename _Value>

   222     class BNodeMap : public Graph::template BNodeMap<_Value> {

   223     public:

   224       typedef typename Graph::template BNodeMap<_Value> Parent;

   225       explicit BNodeMap(const BpUGraphAdaptorBase<Graph>& ga)

   226 	: Parent(*ga.graph) {}

   227       BNodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)

   228 	: Parent(*ga.graph, value) {}

   230       BNodeMap& operator=(const BNodeMap& cmap) {

   231 	return operator=<BNodeMap>(cmap);

   232       }

   234       template <typename CMap>

   235       BNodeMap& operator=(const CMap& cmap) {

   236         Parent::operator=(cmap);

   237 	return *this;

   238       }

   239     };

   241     template <typename _Value>

   242     class EdgeMap : public Graph::template EdgeMap<_Value> {

   243     public:

   244       typedef typename Graph::template EdgeMap<_Value> Parent;

   245       explicit EdgeMap(const BpUGraphAdaptorBase<Graph>& ga)

   246 	: Parent(*ga.graph) {}

   247       EdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)

   248 	: Parent(*ga.graph, value) {}

   250       EdgeMap& operator=(const EdgeMap& cmap) {

   251 	return operator=<EdgeMap>(cmap);

   252       }

   254       template <typename CMap>

   255       EdgeMap& operator=(const CMap& cmap) {

   256         Parent::operator=(cmap);

   257 	return *this;

   258       }

   259     };

   261     template <typename _Value>

   262     class UEdgeMap : public Graph::template UEdgeMap<_Value> {

   263     public:

   264       typedef typename Graph::template UEdgeMap<_Value> Parent;

   265       explicit UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga)

   266 	: Parent(*ga.graph) {}

   267       UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)

   268 	: Parent(*ga.graph, value) {}

   270       UEdgeMap& operator=(const UEdgeMap& cmap) {

   271 	return operator=<UEdgeMap>(cmap);

   272       }

   274       template <typename CMap>

   275       UEdgeMap& operator=(const CMap& cmap) {

   276         Parent::operator=(cmap);

   277 	return *this;

   278       }

   279     };

   281   };

   283   /// \ingroup graph_adaptors

   284   template <typename _BpUGraph>

   285   class BpUGraphAdaptor

   286     : public BpUGraphAdaptorExtender< BpUGraphAdaptorBase<_BpUGraph> > {

   287   public:

   288     typedef _BpUGraph Graph;

   289     typedef BpUGraphAdaptorExtender<BpUGraphAdaptorBase<_BpUGraph> > Parent;

   290   protected:

   291     BpUGraphAdaptor() : Parent() {}

   293   public:

   294     explicit BpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }

   295   };

   297   template <typename _BpUGraph>

   298   class SwapBpUGraphAdaptorBase : public BpUGraphAdaptorBase<_BpUGraph> {

   299   public:

   301     typedef _BpUGraph Graph;

   302     typedef BpUGraphAdaptorBase<_BpUGraph> Parent;

   304   protected:

   306     SwapBpUGraphAdaptorBase() {}

   308   public:

   310     typedef typename Parent::Node Node;

   311     typedef typename Parent::BNode ANode;

   312     typedef typename Parent::ANode BNode;

   314     void firstANode(Node& i) const { Parent::firstBNode(i); }

   315     void firstBNode(Node& i) const { Parent::firstANode(i); }

   317     void nextANode(Node& i) const { Parent::nextBNode(i); }

   318     void nextBNode(Node& i) const { Parent::nextANode(i); }

   320     int id(const ANode& v) const { return Parent::id(v); }

   321     int id(const BNode& v) const { return Parent::id(v); }

   323     ANode fromANodeId(int id) const { return Parent::fromBNodeId(id); }

   324     BNode fromBNodeId(int id) const { return Parent::fromANodeId(id); }

   326     int maxANodeId() const { return Parent::maxBNodeId(); }

   327     int maxBNodeId() const { return Parent::maxANodeId(); }

   329     int aNodeNum() const { return Parent::bNodeNum(); }

   330     int bNodeNum() const { return Parent::aNodeNum(); }

   332     typedef typename Parent::BNodeNotifier ANodeNotifier;

   333     ANodeNotifier& getNotifier(ANode) const {

   334       return Parent::getNotifier(typename Parent::BNode());

   335     }

   337     typedef typename Parent::ANodeNotifier BNodeNotifier;

   338     BNodeNotifier& getNotifier(BNode) const {

   339       return Parent::getNotifier(typename Parent::ANode());

   340     }

   342     template <typename _Value>

   343     class ANodeMap : public Graph::template BNodeMap<_Value> {

   344     public:

   345       typedef typename Graph::template BNodeMap<_Value> Parent;

   346       explicit ANodeMap(const SwapBpUGraphAdaptorBase& ga)

   347 	: Parent(*ga.graph) {}

   348       ANodeMap(const SwapBpUGraphAdaptorBase& ga, const _Value& value)

   349 	: Parent(*ga.graph, value) {}

   351       ANodeMap& operator=(const ANodeMap& cmap) {

   352 	return operator=<ANodeMap>(cmap);

   353       }

   355       template <typename CMap>

   356       ANodeMap& operator=(const CMap& cmap) {

   357         Parent::operator=(cmap);

   358 	return *this;

   359       }

   360     };

   362     template <typename _Value>

   363     class BNodeMap : public Graph::template ANodeMap<_Value> {

   364     public:

   365       typedef typename Graph::template ANodeMap<_Value> Parent;

   366       explicit BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga)

   367 	: Parent(*ga.graph) {}

   368       BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga, const _Value& value)

   369 	: Parent(*ga.graph, value) {}

   371       BNodeMap& operator=(const BNodeMap& cmap) {

   372 	return operator=<BNodeMap>(cmap);

   373       }

   375       template <typename CMap>

   376       BNodeMap& operator=(const CMap& cmap) {

   377         Parent::operator=(cmap);

   378 	return *this;

   379       }

   380     };

   382   };

   384   /// \ingroup graph_adaptors

   385   ///

   386   /// \brief Bipartite graph adaptor which swaps the two nodeset.

   387   ///

   388   /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's

   389   /// a-nodeset will be the original graph's b-nodeset and the adaptor's

   390   /// b-nodeset will be the original graph's a-nodeset.

   391   template <typename _BpUGraph>

   392   class SwapBpUGraphAdaptor

   393     : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > {

   394   public:

   396     typedef _BpUGraph Graph;

   397     typedef BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> >

   398     Parent;

   400   protected:

   401     SwapBpUGraphAdaptor() : Parent() {}

   403   public:

   405     explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }

   407   };

   410 }

   412 #endif

author	deba
	Mon, 03 Apr 2006 09:45:23 +0000
changeset 2031	080d51024ac5
child 2040	c7bd55c0d820
permissions	-rw-r--r--