00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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
00066
00067
00068
00069
00070
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
00092
00093
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
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
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
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
00269
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
00372
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 }
01716
01717 #endif