graph_utils.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_GRAPH_UTILS_H
00020 #define LEMON_GRAPH_UTILS_H
00021 
00022 #include <iterator>
00023 #include <vector>
00024 #include <map>
00025 #include <cmath>
00026 
00027 #include <lemon/invalid.h>
00028 #include <lemon/utility.h>
00029 #include <lemon/maps.h>
00030 #include <lemon/traits.h>
00031 #include <lemon/bits/alteration_notifier.h>
00032 
00038 
00039 
00040 namespace lemon {
00041 
00044 
00046 
00058 #define GRAPH_TYPEDEFS(Graph)                           \
00059   typedef Graph::     Node      Node;                   \
00060     typedef Graph::   NodeIt    NodeIt;                 \
00061     typedef Graph::   Edge      Edge;                   \
00062     typedef Graph::   EdgeIt    EdgeIt;                 \
00063     typedef Graph:: InEdgeIt  InEdgeIt;                 \
00064     typedef Graph::OutEdgeIt OutEdgeIt;                 
00065 //     typedef Graph::template NodeMap<bool> BoolNodeMap;              
00066 //     typedef Graph::template NodeMap<int> IntNodeMap;        
00067 //     typedef Graph::template NodeMap<double> DoubleNodeMap;  
00068 //     typedef Graph::template EdgeMap<bool> BoolEdgeMap;              
00069 //     typedef Graph::template EdgeMap<int> IntEdgeMap;        
00070 //     typedef Graph::template EdgeMap<double> DoubleEdgeMap;
00071   
00073 
00086 #define UNDIRGRAPH_TYPEDEFS(Graph)                              \
00087   GRAPH_TYPEDEFS(Graph)                                         \
00088     typedef Graph:: UEdge   UEdge;                      \
00089     typedef Graph:: UEdgeIt UEdgeIt;                    \
00090     typedef Graph:: IncEdgeIt   IncEdgeIt;                     
00091 //     typedef Graph::template UEdgeMap<bool> BoolUEdgeMap;      
00092 //     typedef Graph::template UEdgeMap<int> IntUEdgeMap;
00093 //     typedef Graph::template UEdgeMap<double> DoubleUEdgeMap;
00094   
00095 
00096 
00102 
00103   template <typename Graph, typename ItemIt>
00104   inline int countItems(const Graph& g) {
00105     int num = 0;
00106     for (ItemIt it(g); it != INVALID; ++it) {
00107       ++num;
00108     }
00109     return num;
00110   }
00111 
00112   // Node counting:
00113 
00114   template <typename Graph>
00115   inline typename enable_if<typename Graph::NodeNumTag, int>::type
00116   _countNodes(const Graph &g) {
00117     return g.nodeNum();
00118   }
00119 
00120   template <typename Graph>
00121   inline int _countNodes(Wrap<Graph> w) {
00122     return countItems<Graph, typename Graph::NodeIt>(w.value);
00123   }
00124 
00132 
00133   template <typename Graph>
00134   inline int countNodes(const Graph& g) {
00135     return _countNodes<Graph>(g);
00136   }
00137 
00138   // Edge counting:
00139 
00140   template <typename Graph>
00141   inline typename enable_if<typename Graph::EdgeNumTag, int>::type
00142   _countEdges(const Graph &g) {
00143     return g.edgeNum();
00144   }
00145 
00146   template <typename Graph>
00147   inline int _countEdges(Wrap<Graph> w) {
00148     return countItems<Graph, typename Graph::EdgeIt>(w.value);
00149   }
00150 
00156 
00157   template <typename Graph>
00158   inline int countEdges(const Graph& g) {
00159     return _countEdges<Graph>(g);
00160   }
00161 
00162   // Undirected edge counting:
00163 
00164   template <typename Graph>
00165   inline
00166   typename enable_if<typename Graph::EdgeNumTag, int>::type
00167   _countUEdges(const Graph &g) {
00168     return g.uEdgeNum();
00169   }
00170 
00171   template <typename Graph>
00172   inline int _countUEdges(Wrap<Graph> w) {
00173     return countItems<Graph, typename Graph::UEdgeIt>(w.value);
00174   }
00175 
00181 
00182   template <typename Graph>
00183   inline int countUEdges(const Graph& g) {
00184     return _countUEdges<Graph>(g);
00185   }
00186 
00187 
00188 
00189   template <typename Graph, typename DegIt>
00190   inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
00191     int num = 0;
00192     for (DegIt it(_g, _n); it != INVALID; ++it) {
00193       ++num;
00194     }
00195     return num;
00196   }
00197 
00202   template <typename Graph>
00203   inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
00204     return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
00205   }
00206 
00211   template <typename Graph>
00212   inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
00213     return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
00214   }
00215 
00220   template <typename Graph>
00221   inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
00222     return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
00223   }
00224 
00225 
00226   template <typename Graph>
00227   inline
00228   typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type 
00229   _findEdge(const Graph &g,
00230             typename Graph::Node u, typename Graph::Node v,
00231             typename Graph::Edge prev = INVALID) {
00232     return g.findEdge(u, v, prev);
00233   }
00234 
00235   template <typename Graph>
00236   inline typename Graph::Edge 
00237   _findEdge(Wrap<Graph> w,
00238             typename Graph::Node u, 
00239             typename Graph::Node v,
00240             typename Graph::Edge prev = INVALID) {
00241     const Graph& g = w.value;
00242     if (prev == INVALID) {
00243       typename Graph::OutEdgeIt e(g, u);
00244       while (e != INVALID && g.target(e) != v) ++e;
00245       return e;
00246     } else {
00247       typename Graph::OutEdgeIt e(g, prev); ++e;
00248       while (e != INVALID && g.target(e) != v) ++e;
00249       return e;
00250     }
00251   }
00252 
00268   // /// \todo We may want to use the "GraphBase" 
00269   // /// interface here...
00270   template <typename Graph>
00271   inline typename Graph::Edge findEdge(const Graph &g,
00272                                        typename Graph::Node u, 
00273                                        typename Graph::Node v,
00274                                        typename Graph::Edge prev = INVALID) {
00275     return _findEdge<Graph>(g, u, v, prev);
00276   }
00277 
00290   template <typename _Graph>
00291   class ConEdgeIt : public _Graph::Edge {
00292   public:
00293 
00294     typedef _Graph Graph;
00295     typedef typename Graph::Edge Parent;
00296 
00297     typedef typename Graph::Edge Edge;
00298     typedef typename Graph::Node Node;
00299 
00304     ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
00305       Parent::operator=(findEdge(graph, u, v));
00306     }
00307 
00312     ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
00313     
00317     ConEdgeIt& operator++() {
00318       Parent::operator=(findEdge(graph, graph.source(*this), 
00319                                  graph.target(*this), *this));
00320       return *this;
00321     }
00322   private:
00323     const Graph& graph;
00324   };
00325 
00326   template <typename Graph>
00327   inline
00328   typename enable_if<
00329     typename Graph::FindEdgeTag, 
00330     typename Graph::UEdge>::type 
00331   _findUEdge(const Graph &g,
00332             typename Graph::Node u, typename Graph::Node v,
00333             typename Graph::UEdge prev = INVALID) {
00334     return g.findUEdge(u, v, prev);
00335   }
00336 
00337   template <typename Graph>
00338   inline typename Graph::UEdge 
00339   _findUEdge(Wrap<Graph> w,
00340             typename Graph::Node u, 
00341             typename Graph::Node v,
00342             typename Graph::UEdge prev = INVALID) {
00343     const Graph& g = w.value;
00344     if (prev == INVALID) {
00345       typename Graph::OutEdgeIt e(g, u);
00346       while (e != INVALID && g.target(e) != v) ++e;
00347       return e;
00348     } else {
00349       typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
00350       while (e != INVALID && g.target(e) != v) ++e;
00351       return e;
00352     }
00353   }
00354 
00371   // /// \todo We may want to use the "GraphBase" 
00372   // /// interface here...
00373   template <typename Graph>
00374   inline typename Graph::UEdge 
00375   findUEdge(const Graph &g,
00376                 typename Graph::Node u, 
00377                 typename Graph::Node v,
00378                 typename Graph::UEdge prev = INVALID) {
00379     return _findUEdge<Graph>(g, u, v, prev);
00380   }
00381 
00394   template <typename _Graph>
00395   class ConUEdgeIt : public _Graph::UEdge {
00396   public:
00397 
00398     typedef _Graph Graph;
00399     typedef typename Graph::UEdge Parent;
00400 
00401     typedef typename Graph::UEdge UEdge;
00402     typedef typename Graph::Node Node;
00403 
00408     ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
00409       Parent::operator=(findUEdge(graph, u, v));
00410     }
00411 
00416     ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
00417     
00421     ConUEdgeIt& operator++() {
00422       Parent::operator=(findUEdge(graph, graph.source(*this), 
00423                                       graph.target(*this), *this));
00424       return *this;
00425     }
00426   private:
00427     const Graph& graph;
00428   };
00429 
00435   template <typename Target, typename Source, 
00436             typename ItemIt, typename Ref>          
00437   void copyMap(Target& target, const Source& source, 
00438                ItemIt it, const Ref& ref) {
00439     for (; it != INVALID; ++it) {
00440       target[ref[it]] = source[it];
00441     }
00442   }
00443 
00448   template <typename Target, typename Source, typename ItemIt>      
00449   void copyMap(Target& target, const Source& source, ItemIt it) {
00450     for (; it != INVALID; ++it) {
00451       target[it] = source[it];
00452     }
00453   }
00454 
00459   template <typename Target, typename Source>
00460   class GraphCopy {
00461   public: 
00462     typedef typename Source::Node Node;
00463     typedef typename Source::NodeIt NodeIt;
00464     typedef typename Source::Edge Edge;
00465     typedef typename Source::EdgeIt EdgeIt;
00466 
00467     typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
00468     typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
00469 
00475     GraphCopy(Target& _target, const Source& _source) 
00476       : source(_source), target(_target), 
00477         nodeRefMap(_source), edgeRefMap(_source) {
00478       for (NodeIt it(source); it != INVALID; ++it) {
00479         nodeRefMap[it] = target.addNode();
00480       }
00481       for (EdgeIt it(source); it != INVALID; ++it) {
00482         edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
00483                                         nodeRefMap[source.target(it)]);
00484       }
00485     }
00486 
00490     template <typename NodeRef>
00491     const GraphCopy& nodeRef(NodeRef& map) const {
00492       for (NodeIt it(source); it != INVALID; ++it) {
00493         map.set(it, nodeRefMap[it]);
00494       }
00495       return *this;
00496     }
00497 
00501     template <typename NodeRef>
00502     const GraphCopy& nodeCrossRef(NodeRef& map) const {
00503       for (NodeIt it(source); it != INVALID; ++it) {
00504         map.set(nodeRefMap[it], it);
00505       }
00506       return *this;
00507     }
00508 
00512     template <typename EdgeRef>
00513     const GraphCopy& edgeRef(EdgeRef& map) const {
00514       for (EdgeIt it(source); it != INVALID; ++it) {
00515         map.set(it, edgeRefMap[it]);
00516       }
00517       return *this;
00518     }
00519 
00523     template <typename EdgeRef>
00524     const GraphCopy& edgeCrossRef(EdgeRef& map) const {
00525       for (EdgeIt it(source); it != INVALID; ++it) {
00526         map.set(edgeRefMap[it], it);
00527       }
00528       return *this;
00529     }
00530 
00537     template <typename TargetMap, typename SourceMap>
00538     const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
00539       copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
00540       return *this;
00541     }
00542 
00549     template <typename TargetMap, typename SourceMap>
00550     const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
00551       copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
00552       return *this;
00553     }
00554 
00558     const NodeRefMap& nodeRef() const {
00559       return nodeRefMap;
00560     }
00561 
00565     const EdgeRefMap& edgeRef() const {
00566       return edgeRefMap;
00567     }
00568 
00569     void run() {}
00570 
00571   private:
00572     
00573     const Source& source;
00574     Target& target;
00575 
00576     NodeRefMap nodeRefMap;
00577     EdgeRefMap edgeRefMap;
00578   };
00579 
00593   template <typename Target, typename Source>
00594   GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
00595     return GraphCopy<Target, Source>(target, source);
00596   }
00597 
00602   template <typename Target, typename Source>
00603   class UGraphCopy {
00604   public: 
00605     typedef typename Source::Node Node;
00606     typedef typename Source::NodeIt NodeIt;
00607     typedef typename Source::Edge Edge;
00608     typedef typename Source::EdgeIt EdgeIt;
00609     typedef typename Source::UEdge UEdge;
00610     typedef typename Source::UEdgeIt UEdgeIt;
00611 
00612     typedef typename Source::
00613     template NodeMap<typename Target::Node> NodeRefMap;
00614     
00615     typedef typename Source::
00616     template UEdgeMap<typename Target::UEdge> UEdgeRefMap;
00617 
00618   private:
00619 
00620     struct EdgeRefMap {
00621       EdgeRefMap(UGraphCopy& _gc) : gc(_gc) {}
00622       typedef typename Source::Edge Key;
00623       typedef typename Target::Edge Value;
00624 
00625       Value operator[](const Key& key) {
00626         return gc.target.direct(gc.uEdgeRef[key], 
00627                                 gc.target.direction(key));
00628       }
00629       
00630       UGraphCopy& gc;
00631     };
00632     
00633   public:
00634 
00640     UGraphCopy(Target& _target, const Source& _source) 
00641       : source(_source), target(_target), 
00642         nodeRefMap(_source), edgeRefMap(*this), uEdgeRefMap(_source) {
00643       for (NodeIt it(source); it != INVALID; ++it) {
00644         nodeRefMap[it] = target.addNode();
00645       }
00646       for (UEdgeIt it(source); it != INVALID; ++it) {
00647         uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
00648                                         nodeRefMap[source.target(it)]);
00649       }
00650     }
00651 
00655     template <typename NodeRef>
00656     const UGraphCopy& nodeRef(NodeRef& map) const {
00657       for (NodeIt it(source); it != INVALID; ++it) {
00658         map.set(it, nodeRefMap[it]);
00659       }
00660       return *this;
00661     }
00662 
00666     template <typename NodeRef>
00667     const UGraphCopy& nodeCrossRef(NodeRef& map) const {
00668       for (NodeIt it(source); it != INVALID; ++it) {
00669         map.set(nodeRefMap[it], it);
00670       }
00671       return *this;
00672     }
00673 
00677     template <typename EdgeRef>
00678     const UGraphCopy& edgeRef(EdgeRef& map) const {
00679       for (EdgeIt it(source); it != INVALID; ++it) {
00680         map.set(edgeRefMap[it], it);
00681       }
00682       return *this;
00683     }
00684 
00689     template <typename EdgeRef>
00690     const UGraphCopy& edgeCrossRef(EdgeRef& map) const {
00691       for (EdgeIt it(source); it != INVALID; ++it) {
00692         map.set(it, edgeRefMap[it]);
00693       }
00694       return *this;
00695     }
00696 
00700     template <typename EdgeRef>
00701     const UGraphCopy& uEdgeRef(EdgeRef& map) const {
00702       for (UEdgeIt it(source); it != INVALID; ++it) {
00703         map.set(it, uEdgeRefMap[it]);
00704       }
00705       return *this;
00706     }
00707 
00712     template <typename EdgeRef>
00713     const UGraphCopy& uEdgeCrossRef(EdgeRef& map) const {
00714       for (UEdgeIt it(source); it != INVALID; ++it) {
00715         map.set(uEdgeRefMap[it], it);
00716       }
00717       return *this;
00718     }
00719 
00726     template <typename TargetMap, typename SourceMap>
00727     const UGraphCopy& nodeMap(TargetMap& tMap, 
00728                                   const SourceMap& sMap) const {
00729       copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
00730       return *this;
00731     }
00732 
00739     template <typename TargetMap, typename SourceMap>
00740     const UGraphCopy& edgeMap(TargetMap& tMap, 
00741                                   const SourceMap& sMap) const {
00742       copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
00743       return *this;
00744     }
00745 
00752     template <typename TargetMap, typename SourceMap>
00753     const UGraphCopy& uEdgeMap(TargetMap& tMap, 
00754                                   const SourceMap& sMap) const {
00755       copyMap(tMap, sMap, UEdgeIt(source), uEdgeRefMap);
00756       return *this;
00757     }
00758 
00762     const NodeRefMap& nodeRef() const {
00763       return nodeRefMap;
00764     }
00765 
00769     const EdgeRefMap& edgeRef() const {
00770       return edgeRefMap;
00771     }
00772 
00776     const UEdgeRefMap& uEdgeRef() const {
00777       return uEdgeRefMap;
00778     }
00779 
00780     void run() {}
00781 
00782   private:
00783     
00784     const Source& source;
00785     Target& target;
00786 
00787     NodeRefMap nodeRefMap;
00788     EdgeRefMap edgeRefMap;
00789     UEdgeRefMap uEdgeRefMap;
00790   };
00791 
00805   template <typename Target, typename Source>
00806   UGraphCopy<Target, Source> 
00807   copyUGraph(Target& target, const Source& source) {
00808     return UGraphCopy<Target, Source>(target, source);
00809   }
00810 
00811 
00813 
00816 
00818 
00827   template <typename _Graph, typename _Item>
00828   class IdMap {
00829   public:
00830     typedef _Graph Graph;
00831     typedef int Value;
00832     typedef _Item Item;
00833     typedef _Item Key;
00834 
00838     IdMap(const Graph& _graph) : graph(&_graph) {}
00839 
00843     int operator[](const Item& item) const { return graph->id(item);}
00844 
00845 
00846   private:
00847     const Graph* graph;
00848 
00849   public:
00850 
00855     class InverseMap {
00856     public:
00857 
00861       InverseMap(const Graph& _graph) : graph(&_graph) {}
00862 
00866       InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
00867 
00872       Item operator[](int id) const { return graph->fromId(id, Item());}
00873     private:
00874       const Graph* graph;
00875     };
00876 
00880     InverseMap inverse() const { return InverseMap(*graph);} 
00881 
00882   };
00883 
00884   
00886 
00900 #ifndef DOXYGEN
00901 
00902   template <
00903     typename _Graph, typename _Item, typename _Value, typename _Map 
00904     = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent 
00905   >
00906 #else
00907   template <typename _Graph, typename _Item, typename _Value>
00908 #endif
00909   class InvertableMap : protected _Map {
00910   public:
00911 
00913     typedef typename _Map::Key Key;
00915     typedef typename _Map::Value Value;
00916 
00917   private:
00918     
00919     typedef _Map Map;
00920     typedef _Graph Graph;
00921 
00922     typedef std::map<Value, Key> Container;
00923     Container invMap;    
00924 
00925   public:
00926  
00927 
00928 
00933     InvertableMap(const Graph& graph) : Map(graph) {} 
00934 
00941     class ValueIterator 
00942       : public std::iterator<std::forward_iterator_tag, Value> {
00943       friend class InvertableMap;
00944     private:
00945       ValueIterator(typename Container::const_iterator _it) 
00946         : it(_it) {}
00947     public:
00948       
00949       ValueIterator() {}
00950 
00951       ValueIterator& operator++() { ++it; return *this; }
00952       ValueIterator operator++(int) { 
00953         ValueIterator tmp(*this); 
00954         operator++();
00955         return tmp; 
00956       }
00957 
00958       const Value& operator*() const { return it->first; }
00959       const Value* operator->() const { return &(it->first); }
00960 
00961       bool operator==(ValueIterator jt) const { return it == jt.it; }
00962       bool operator!=(ValueIterator jt) const { return it != jt.it; }
00963       
00964     private:
00965       typename Container::const_iterator it;
00966     };
00967 
00974     ValueIterator beginValue() const {
00975       return ValueIterator(invMap.begin());
00976     }
00977 
00984     ValueIterator endValue() const {
00985       return ValueIterator(invMap.end());
00986     }
00987     
00991     void set(const Key& key, const Value& val) {
00992       Value oldval = Map::operator[](key);
00993       typename Container::iterator it = invMap.find(oldval);
00994       if (it != invMap.end() && it->second == key) {
00995         invMap.erase(it);
00996       }      
00997       invMap.insert(make_pair(val, key));
00998       Map::set(key, val);
00999     }
01000 
01004     typename MapTraits<Map>::ConstReturnValue 
01005     operator[](const Key& key) const {
01006       return Map::operator[](key);
01007     }
01008 
01009   protected:
01010 
01015     virtual void erase(const Key& key) {
01016       Value val = Map::operator[](key);
01017       typename Container::iterator it = invMap.find(val);
01018       if (it != invMap.end() && it->second == key) {
01019         invMap.erase(it);
01020       }
01021       Map::erase(key);
01022     }
01023 
01028     virtual void erase(const std::vector<Key>& keys) {
01029       for (int i = 0; i < (int)keys.size(); ++i) {
01030         Value val = Map::operator[](keys[i]);
01031         typename Container::iterator it = invMap.find(val);
01032         if (it != invMap.end() && it->second == keys[i]) {
01033           invMap.erase(it);
01034         }
01035       }
01036       Map::erase(keys);
01037     }
01038 
01043     virtual void clear() {
01044       invMap.clear();
01045       Map::clear();
01046     }
01047 
01048   public:
01049 
01054     class InverseMap {
01055     public:
01059       InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
01060 
01062       typedef typename InvertableMap::Key Value;
01064       typedef typename InvertableMap::Value Key; 
01065 
01070       Value operator[](const Key& key) const {
01071         typename Container::const_iterator it = inverted.invMap.find(key);
01072         return it->second;
01073       }
01074       
01075     private:
01076       const InvertableMap& inverted;
01077     };
01078 
01082     InverseMap inverse() const {
01083       return InverseMap(*this);
01084     } 
01085 
01086 
01087     
01088   };
01089 
01105 #ifndef DOXYGEN
01106 
01107   template <
01108     typename _Graph, typename _Item, typename _Map 
01109     = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent 
01110   >
01111 #else
01112   template <typename _Graph, typename _Item>
01113 #endif
01114   class DescriptorMap : protected _Map {
01115 
01116     typedef _Item Item;
01117     typedef _Map Map;
01118 
01119   public:
01121     typedef _Graph Graph;
01122 
01124     typedef typename _Map::Key Key;
01126     typedef typename _Map::Value Value;
01127 
01131     DescriptorMap(const Graph& _graph) : Map(_graph) {
01132       build();
01133     }
01134 
01135   protected:
01136 
01141     virtual void add(const Item& item) {
01142       Map::add(item);
01143       Map::set(item, invMap.size());
01144       invMap.push_back(item);
01145     }
01146 
01151     virtual void add(const std::vector<Item>& items) {
01152       Map::add(items);
01153       for (int i = 0; i < (int)items.size(); ++i) {
01154         Map::set(items[i], invMap.size());
01155         invMap.push_back(items[i]);
01156       }
01157     }
01158 
01163     virtual void erase(const Item& item) {
01164       Map::set(invMap.back(), Map::operator[](item));
01165       invMap[Map::operator[](item)] = invMap.back();
01166       invMap.pop_back();
01167       Map::erase(item);
01168     }
01169 
01174     virtual void erase(const std::vector<Item>& items) {
01175       for (int i = 0; i < (int)items.size(); ++i) {
01176         Map::set(invMap.back(), Map::operator[](items[i]));
01177         invMap[Map::operator[](items[i])] = invMap.back();
01178         invMap.pop_back();
01179       }
01180       Map::erase(items);
01181     }
01182 
01187     virtual void build() {
01188       Map::build();
01189       Item it;
01190       const typename Map::Graph* graph = Map::getGraph(); 
01191       for (graph->first(it); it != INVALID; graph->next(it)) {
01192         Map::set(it, invMap.size());
01193         invMap.push_back(it);   
01194       }      
01195     }
01196     
01201     virtual void clear() {
01202       invMap.clear();
01203       Map::clear();
01204     }
01205 
01206   public:
01207 
01211     unsigned int size() const {
01212       return invMap.size();
01213     }
01214 
01218     void swap(const Item& p, const Item& q) {
01219       int pi = Map::operator[](p);
01220       int qi = Map::operator[](q);
01221       Map::set(p, qi);
01222       invMap[qi] = p;
01223       Map::set(q, pi);
01224       invMap[pi] = q;
01225     }
01226 
01230     int operator[](const Item& item) const {
01231       return Map::operator[](item);
01232     }
01233     
01234   private:
01235 
01236     typedef std::vector<Item> Container;
01237     Container invMap;
01238 
01239   public:
01243     class InverseMap {
01244     public:
01248       InverseMap(const DescriptorMap& _inverted) 
01249         : inverted(_inverted) {}
01250 
01251 
01253       typedef typename DescriptorMap::Key Value;
01255       typedef typename DescriptorMap::Value Key; 
01256 
01261       Value operator[](const Key& key) const {
01262         return inverted.invMap[key];
01263       }
01264 
01268       unsigned int size() const {
01269         return inverted.invMap.size();
01270       }
01271       
01272     private:
01273       const DescriptorMap& inverted;
01274     };
01275 
01279     const InverseMap inverse() const {
01280       return InverseMap(*this);
01281     }
01282   };
01283 
01288   template <typename Graph>
01289   class SourceMap {
01290   public:
01291 
01292     typedef typename Graph::Node Value;
01293     typedef typename Graph::Edge Key;
01294 
01299     SourceMap(const Graph& _graph) : graph(_graph) {}
01300 
01306     Value operator[](const Key& edge) const {
01307       return graph.source(edge);
01308     }
01309 
01310   private:
01311     const Graph& graph;
01312   };
01313 
01318   template <typename Graph>
01319   inline SourceMap<Graph> sourceMap(const Graph& graph) {
01320     return SourceMap<Graph>(graph);
01321   } 
01322 
01327   template <typename Graph>
01328   class TargetMap {
01329   public:
01330 
01331     typedef typename Graph::Node Value;
01332     typedef typename Graph::Edge Key;
01333 
01338     TargetMap(const Graph& _graph) : graph(_graph) {}
01339 
01345     Value operator[](const Key& e) const {
01346       return graph.target(e);
01347     }
01348 
01349   private:
01350     const Graph& graph;
01351   };
01352 
01357   template <typename Graph>
01358   inline TargetMap<Graph> targetMap(const Graph& graph) {
01359     return TargetMap<Graph>(graph);
01360   }
01361 
01366   template <typename Graph>
01367   class ForwardMap {
01368   public:
01369 
01370     typedef typename Graph::Edge Value;
01371     typedef typename Graph::UEdge Key;
01372 
01377     ForwardMap(const Graph& _graph) : graph(_graph) {}
01378 
01384     Value operator[](const Key& key) const {
01385       return graph.direct(key, true);
01386     }
01387 
01388   private:
01389     const Graph& graph;
01390   };
01391 
01396   template <typename Graph>
01397   inline ForwardMap<Graph> forwardMap(const Graph& graph) {
01398     return ForwardMap<Graph>(graph);
01399   }
01400 
01405   template <typename Graph>
01406   class BackwardMap {
01407   public:
01408 
01409     typedef typename Graph::Edge Value;
01410     typedef typename Graph::UEdge Key;
01411 
01416     BackwardMap(const Graph& _graph) : graph(_graph) {}
01417 
01423     Value operator[](const Key& key) const {
01424       return graph.direct(key, false);
01425     }
01426 
01427   private:
01428     const Graph& graph;
01429   };
01430 
01432 
01435   template <typename Graph>
01436   inline BackwardMap<Graph> backwardMap(const Graph& graph) {
01437     return BackwardMap<Graph>(graph);
01438   }
01439 
01445   template <typename Graph, typename NodeMap>
01446   class PotentialDifferenceMap {
01447   public:
01448     typedef typename Graph::Edge Key;
01449     typedef typename NodeMap::Value Value;
01450 
01454     PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential) 
01455       : graph(_graph), potential(_potential) {}
01456 
01460     Value operator[](const Key& edge) const {
01461       return potential[graph.target(edge)] - potential[graph.source(edge)];
01462     }
01463 
01464   private:
01465     const Graph& graph;
01466     const NodeMap& potential;
01467   };
01468 
01473   template <typename Graph, typename NodeMap>
01474   PotentialDifferenceMap<Graph, NodeMap> 
01475   potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
01476     return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
01477   }
01478 
01495 
01496   template <typename _Graph>
01497   class InDegMap  
01498     : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
01499 
01500   public:
01501     
01502     typedef _Graph Graph;
01503     typedef int Value;
01504     typedef typename Graph::Node Key;
01505 
01506   private:
01507 
01508     class AutoNodeMap : public Graph::template NodeMap<int> {
01509     public:
01510 
01511       typedef typename Graph::template NodeMap<int> Parent;
01512 
01513       typedef typename Parent::Key Key;
01514       typedef typename Parent::Value Value;
01515       
01516       AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
01517       
01518       virtual void add(const Key& key) {
01519         Parent::add(key);
01520         Parent::set(key, 0);
01521       }
01522 
01523       virtual void add(const std::vector<Key>& keys) {
01524         Parent::add(keys);
01525         for (int i = 0; i < (int)keys.size(); ++i) {
01526           Parent::set(keys[i], 0);
01527         }
01528       }
01529     };
01530 
01531   public:
01532 
01536     InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
01537       AlterationNotifier<typename _Graph::Edge>
01538 	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
01539       
01540       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
01541         deg[it] = countInEdges(graph, it);
01542       }
01543     }
01544 
01545     virtual ~InDegMap() {
01546       AlterationNotifier<typename _Graph::Edge>::
01547         ObserverBase::detach();
01548     }
01549     
01551     int operator[](const Key& key) const {
01552       return deg[key];
01553     }
01554 
01555   protected:
01556     
01557     typedef typename Graph::Edge Edge;
01558 
01559     virtual void add(const Edge& edge) {
01560       ++deg[graph.target(edge)];
01561     }
01562 
01563     virtual void add(const std::vector<Edge>& edges) {
01564       for (int i = 0; i < (int)edges.size(); ++i) {
01565         ++deg[graph.target(edges[i])];
01566       }
01567     }
01568 
01569     virtual void erase(const Edge& edge) {
01570       --deg[graph.target(edge)];
01571     }
01572 
01573     virtual void erase(const std::vector<Edge>& edges) {
01574       for (int i = 0; i < (int)edges.size(); ++i) {
01575         --deg[graph.target(edges[i])];
01576       }
01577     }
01578 
01579     virtual void build() {
01580       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
01581         deg[it] = countInEdges(graph, it);
01582       }      
01583     }
01584 
01585     virtual void clear() {
01586       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
01587         deg[it] = 0;
01588       }
01589     }
01590   private:
01591     
01592     const _Graph& graph;
01593     AutoNodeMap deg;
01594   };
01595 
01612 
01613   template <typename _Graph>
01614   class OutDegMap  
01615     : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
01616 
01617   public:
01618     
01619     typedef _Graph Graph;
01620     typedef int Value;
01621     typedef typename Graph::Node Key;
01622 
01623   private:
01624 
01625     class AutoNodeMap : public Graph::template NodeMap<int> {
01626     public:
01627 
01628       typedef typename Graph::template NodeMap<int> Parent;
01629 
01630       typedef typename Parent::Key Key;
01631       typedef typename Parent::Value Value;
01632       
01633       AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
01634       
01635       virtual void add(const Key& key) {
01636         Parent::add(key);
01637         Parent::set(key, 0);
01638       }
01639       virtual void add(const std::vector<Key>& keys) {
01640         Parent::add(keys);
01641         for (int i = 0; i < (int)keys.size(); ++i) {
01642           Parent::set(keys[i], 0);
01643         }
01644       }
01645     };
01646 
01647   public:
01648 
01652     OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
01653       AlterationNotifier<typename _Graph::Edge>
01654 	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
01655       
01656       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
01657         deg[it] = countOutEdges(graph, it);
01658       }
01659     }
01660 
01661     virtual ~OutDegMap() {
01662       AlterationNotifier<typename _Graph::Edge>::
01663         ObserverBase::detach();
01664     }
01665     
01667     int operator[](const Key& key) const {
01668       return deg[key];
01669     }
01670 
01671   protected:
01672     
01673     typedef typename Graph::Edge Edge;
01674 
01675     virtual void add(const Edge& edge) {
01676       ++deg[graph.source(edge)];
01677     }
01678 
01679     virtual void add(const std::vector<Edge>& edges) {
01680       for (int i = 0; i < (int)edges.size(); ++i) {
01681         ++deg[graph.source(edges[i])];
01682       }
01683     }
01684 
01685     virtual void erase(const Edge& edge) {
01686       --deg[graph.source(edge)];
01687     }
01688 
01689     virtual void erase(const std::vector<Edge>& edges) {
01690       for (int i = 0; i < (int)edges.size(); ++i) {
01691         --deg[graph.source(edges[i])];
01692       }
01693     }
01694 
01695     virtual void build() {
01696       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
01697         deg[it] = countOutEdges(graph, it);
01698       }      
01699     }
01700 
01701     virtual void clear() {
01702       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
01703         deg[it] = 0;
01704       }
01705     }
01706   private:
01707     
01708     const _Graph& graph;
01709     AutoNodeMap deg;
01710   };
01711 
01712 
01714 
01715 } //END OF NAMESPACE LEMON
01716 
01717 #endif

Generated on Fri Feb 3 18:37:36 2006 for LEMON by  doxygen 1.4.6