1.1 --- a/src/lemon/graph_utils.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,861 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#ifndef LEMON_GRAPH_UTILS_H
1.21 -#define LEMON_GRAPH_UTILS_H
1.22 -
1.23 -#include <iterator>
1.24 -#include <vector>
1.25 -#include <map>
1.26 -
1.27 -#include <lemon/invalid.h>
1.28 -#include <lemon/utility.h>
1.29 -#include <lemon/maps.h>
1.30 -
1.31 -///\ingroup gutils
1.32 -///\file
1.33 -///\brief Graph utilities.
1.34 -///
1.35 -///\todo Please
1.36 -///revise the documentation.
1.37 -///
1.38 -
1.39 -
1.40 -namespace lemon {
1.41 -
1.42 - /// \addtogroup gutils
1.43 - /// @{
1.44 -
1.45 - /// \brief Function to count the items in the graph.
1.46 - ///
1.47 - /// This function counts the items in the graph.
1.48 - /// The complexity of the function is O(n) because
1.49 - /// it iterates on all of the items.
1.50 -
1.51 - template <typename Graph, typename ItemIt>
1.52 - inline int countItems(const Graph& g) {
1.53 - int num = 0;
1.54 - for (ItemIt it(g); it != INVALID; ++it) {
1.55 - ++num;
1.56 - }
1.57 - return num;
1.58 - }
1.59 -
1.60 - // Node counting:
1.61 -
1.62 - template <typename Graph>
1.63 - inline
1.64 - typename enable_if<typename Graph::NodeNumTag, int>::type
1.65 - _countNodes(const Graph &g) {
1.66 - return g.nodeNum();
1.67 - }
1.68 -
1.69 - template <typename Graph>
1.70 - inline int _countNodes(Wrap<Graph> w) {
1.71 - return countItems<Graph, typename Graph::NodeIt>(w.value);
1.72 - }
1.73 -
1.74 - /// \brief Function to count the nodes in the graph.
1.75 - ///
1.76 - /// This function counts the nodes in the graph.
1.77 - /// The complexity of the function is O(n) but for some
1.78 - /// graph structure it is specialized to run in O(1).
1.79 - ///
1.80 - /// \todo refer how to specialize it
1.81 -
1.82 - template <typename Graph>
1.83 - inline int countNodes(const Graph& g) {
1.84 - return _countNodes<Graph>(g);
1.85 - }
1.86 -
1.87 - // Edge counting:
1.88 -
1.89 - template <typename Graph>
1.90 - inline
1.91 - typename enable_if<typename Graph::EdgeNumTag, int>::type
1.92 - _countEdges(const Graph &g) {
1.93 - return g.edgeNum();
1.94 - }
1.95 -
1.96 - template <typename Graph>
1.97 - inline int _countEdges(Wrap<Graph> w) {
1.98 - return countItems<Graph, typename Graph::EdgeIt>(w.value);
1.99 - }
1.100 -
1.101 - /// \brief Function to count the edges in the graph.
1.102 - ///
1.103 - /// This function counts the edges in the graph.
1.104 - /// The complexity of the function is O(e) but for some
1.105 - /// graph structure it is specialized to run in O(1).
1.106 -
1.107 - template <typename Graph>
1.108 - inline int countEdges(const Graph& g) {
1.109 - return _countEdges<Graph>(g);
1.110 - }
1.111 -
1.112 - // Undirected edge counting:
1.113 -
1.114 - template <typename Graph>
1.115 - inline
1.116 - typename enable_if<typename Graph::EdgeNumTag, int>::type
1.117 - _countUndirEdges(const Graph &g) {
1.118 - return g.undirEdgeNum();
1.119 - }
1.120 -
1.121 - template <typename Graph>
1.122 - inline int _countUndirEdges(Wrap<Graph> w) {
1.123 - return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
1.124 - }
1.125 -
1.126 - /// \brief Function to count the edges in the graph.
1.127 - ///
1.128 - /// This function counts the edges in the graph.
1.129 - /// The complexity of the function is O(e) but for some
1.130 - /// graph structure it is specialized to run in O(1).
1.131 -
1.132 - template <typename Graph>
1.133 - inline int countUndirEdges(const Graph& g) {
1.134 - return _countUndirEdges<Graph>(g);
1.135 - }
1.136 -
1.137 -
1.138 -
1.139 - template <typename Graph, typename DegIt>
1.140 - inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
1.141 - int num = 0;
1.142 - for (DegIt it(_g, _n); it != INVALID; ++it) {
1.143 - ++num;
1.144 - }
1.145 - return num;
1.146 - }
1.147 -
1.148 - /// Finds an edge between two nodes of a graph.
1.149 -
1.150 - /// Finds an edge from node \c u to node \c v in graph \c g.
1.151 - ///
1.152 - /// If \c prev is \ref INVALID (this is the default value), then
1.153 - /// it finds the first edge from \c u to \c v. Otherwise it looks for
1.154 - /// the next edge from \c u to \c v after \c prev.
1.155 - /// \return The found edge or \ref INVALID if there is no such an edge.
1.156 - ///
1.157 - /// Thus you can iterate through each edge from \c u to \c v as it follows.
1.158 - /// \code
1.159 - /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
1.160 - /// ...
1.161 - /// }
1.162 - /// \endcode
1.163 - /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
1.164 - /// interface here...
1.165 - /// \bug Untested ...
1.166 - template <typename Graph>
1.167 - typename Graph::Edge findEdge(const Graph &g,
1.168 - typename Graph::Node u, typename Graph::Node v,
1.169 - typename Graph::Edge prev = INVALID)
1.170 - {
1.171 - typename Graph::OutEdgeIt e(g,prev);
1.172 - // if(prev==INVALID) g.first(e,u);
1.173 - if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);
1.174 - else ++e;
1.175 - while(e!=INVALID && g.target(e)!=v) ++e;
1.176 - return e;
1.177 - }
1.178 -
1.179 - ///\e
1.180 -
1.181 - ///\todo Please document.
1.182 - ///
1.183 - template <typename Graph>
1.184 - inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
1.185 - return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
1.186 - }
1.187 -
1.188 - ///\e
1.189 -
1.190 - ///\todo Please document.
1.191 - ///
1.192 - template <typename Graph>
1.193 - inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
1.194 - return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
1.195 - }
1.196 -
1.197 - // graph copy
1.198 -
1.199 - template <
1.200 - typename DestinationGraph,
1.201 - typename SourceGraph,
1.202 - typename NodeBijection>
1.203 - void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
1.204 - NodeBijection& _nb) {
1.205 - for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
1.206 - _nb[it] = _d.addNode();
1.207 - }
1.208 - }
1.209 -
1.210 - template <
1.211 - typename DestinationGraph,
1.212 - typename SourceGraph,
1.213 - typename NodeBijection,
1.214 - typename EdgeBijection>
1.215 - void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
1.216 - const NodeBijection& _nb, EdgeBijection& _eb) {
1.217 - for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
1.218 - _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
1.219 - }
1.220 - }
1.221 -
1.222 - template <
1.223 - typename DestinationGraph,
1.224 - typename SourceGraph,
1.225 - typename NodeBijection,
1.226 - typename EdgeBijection>
1.227 - void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
1.228 - NodeBijection& _nb, EdgeBijection& _eb) {
1.229 - nodeCopy(_d, _s, _nb);
1.230 - edgeCopy(_d, _s, _nb, _eb);
1.231 - }
1.232 -
1.233 - template <
1.234 - typename _DestinationGraph,
1.235 - typename _SourceGraph,
1.236 - typename _NodeBijection
1.237 - =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
1.238 - typename _EdgeBijection
1.239 - = typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
1.240 - >
1.241 - class GraphCopy {
1.242 - public:
1.243 -
1.244 - typedef _DestinationGraph DestinationGraph;
1.245 - typedef _SourceGraph SourceGraph;
1.246 -
1.247 - typedef _NodeBijection NodeBijection;
1.248 - typedef _EdgeBijection EdgeBijection;
1.249 -
1.250 - protected:
1.251 -
1.252 - NodeBijection node_bijection;
1.253 - EdgeBijection edge_bijection;
1.254 -
1.255 - public:
1.256 -
1.257 - GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
1.258 - copyGraph(_d, _s, node_bijection, edge_bijection);
1.259 - }
1.260 -
1.261 - const NodeBijection& getNodeBijection() const {
1.262 - return node_bijection;
1.263 - }
1.264 -
1.265 - const EdgeBijection& getEdgeBijection() const {
1.266 - return edge_bijection;
1.267 - }
1.268 -
1.269 - };
1.270 -
1.271 -
1.272 - template <typename _Graph, typename _Item>
1.273 - class ItemSetTraits {};
1.274 -
1.275 - template <typename _Graph>
1.276 - class ItemSetTraits<_Graph, typename _Graph::Node> {
1.277 - public:
1.278 -
1.279 - typedef _Graph Graph;
1.280 -
1.281 - typedef typename Graph::Node Item;
1.282 - typedef typename Graph::NodeIt ItemIt;
1.283 -
1.284 - template <typename _Value>
1.285 - class Map : public Graph::template NodeMap<_Value> {
1.286 - public:
1.287 - typedef typename Graph::template NodeMap<_Value> Parent;
1.288 - typedef typename Parent::Value Value;
1.289 -
1.290 - Map(const Graph& _graph) : Parent(_graph) {}
1.291 - Map(const Graph& _graph, const Value& _value)
1.292 - : Parent(_graph, _value) {}
1.293 - };
1.294 -
1.295 - };
1.296 -
1.297 - template <typename _Graph>
1.298 - class ItemSetTraits<_Graph, typename _Graph::Edge> {
1.299 - public:
1.300 -
1.301 - typedef _Graph Graph;
1.302 -
1.303 - typedef typename Graph::Edge Item;
1.304 - typedef typename Graph::EdgeIt ItemIt;
1.305 -
1.306 - template <typename _Value>
1.307 - class Map : public Graph::template EdgeMap<_Value> {
1.308 - public:
1.309 - typedef typename Graph::template EdgeMap<_Value> Parent;
1.310 - typedef typename Parent::Value Value;
1.311 -
1.312 - Map(const Graph& _graph) : Parent(_graph) {}
1.313 - Map(const Graph& _graph, const Value& _value)
1.314 - : Parent(_graph, _value) {}
1.315 - };
1.316 -
1.317 - };
1.318 -
1.319 - template <typename _Graph>
1.320 - class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
1.321 - public:
1.322 -
1.323 - typedef _Graph Graph;
1.324 -
1.325 - typedef typename Graph::UndirEdge Item;
1.326 - typedef typename Graph::UndirEdgeIt ItemIt;
1.327 -
1.328 - template <typename _Value>
1.329 - class Map : public Graph::template UndirEdgeMap<_Value> {
1.330 - public:
1.331 - typedef typename Graph::template UndirEdgeMap<_Value> Parent;
1.332 - typedef typename Parent::Value Value;
1.333 -
1.334 - Map(const Graph& _graph) : Parent(_graph) {}
1.335 - Map(const Graph& _graph, const Value& _value)
1.336 - : Parent(_graph, _value) {}
1.337 - };
1.338 -
1.339 - };
1.340 -
1.341 - /// @}
1.342 -
1.343 - /// \addtogroup graph_maps
1.344 - /// @{
1.345 -
1.346 - template <typename Map, typename Enable = void>
1.347 - struct ReferenceMapTraits {
1.348 - typedef typename Map::Value Value;
1.349 - typedef typename Map::Value& Reference;
1.350 - typedef const typename Map::Value& ConstReference;
1.351 - typedef typename Map::Value* Pointer;
1.352 - typedef const typename Map::Value* ConstPointer;
1.353 - };
1.354 -
1.355 - template <typename Map>
1.356 - struct ReferenceMapTraits<
1.357 - Map,
1.358 - typename enable_if<typename Map::FullTypeTag, void>::type
1.359 - > {
1.360 - typedef typename Map::Value Value;
1.361 - typedef typename Map::Reference Reference;
1.362 - typedef typename Map::ConstReference ConstReference;
1.363 - typedef typename Map::Pointer Pointer;
1.364 - typedef typename Map::ConstPointer ConstPointer;
1.365 - };
1.366 -
1.367 - /// Provides an immutable and unique id for each item in the graph.
1.368 -
1.369 - /// The IdMap class provides an unique and immutable mapping for each item
1.370 - /// in the graph.
1.371 - ///
1.372 - template <typename _Graph, typename _Item>
1.373 - class IdMap {
1.374 - public:
1.375 - typedef _Graph Graph;
1.376 - typedef int Value;
1.377 - typedef _Item Item;
1.378 - typedef _Item Key;
1.379 -
1.380 - typedef True NeedCopy;
1.381 -
1.382 - /// \brief Constructor.
1.383 - ///
1.384 - /// Constructor for creating id map.
1.385 - IdMap(const Graph& _graph) : graph(&_graph) {}
1.386 -
1.387 - /// \brief Gives back the \e id of the item.
1.388 - ///
1.389 - /// Gives back the immutable and unique \e id of the map.
1.390 - int operator[](const Item& item) const { return graph->id(item);}
1.391 -
1.392 -
1.393 - private:
1.394 - const Graph* graph;
1.395 -
1.396 - public:
1.397 -
1.398 - /// \brief The class represents the inverse of the map.
1.399 - ///
1.400 - /// The class represents the inverse of the map.
1.401 - /// \see inverse()
1.402 - class InverseMap {
1.403 - public:
1.404 -
1.405 - typedef True NeedCopy;
1.406 -
1.407 - /// \brief Constructor.
1.408 - ///
1.409 - /// Constructor for creating an id-to-item map.
1.410 - InverseMap(const Graph& _graph) : graph(&_graph) {}
1.411 -
1.412 - /// \brief Constructor.
1.413 - ///
1.414 - /// Constructor for creating an id-to-item map.
1.415 - InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
1.416 -
1.417 - /// \brief Gives back the given item from its id.
1.418 - ///
1.419 - /// Gives back the given item from its id.
1.420 - ///
1.421 - Item operator[](int id) const { return graph->fromId(id, Item());}
1.422 - private:
1.423 - const Graph* graph;
1.424 - };
1.425 -
1.426 - /// \brief Gives back the inverse of the map.
1.427 - ///
1.428 - /// Gives back the inverse of the map.
1.429 - InverseMap inverse() const { return InverseMap(*graph);}
1.430 -
1.431 - };
1.432 -
1.433 -
1.434 - /// \brief General inversable graph-map type.
1.435 -
1.436 - /// This type provides simple inversable map functions.
1.437 - /// The InversableMap wraps an arbitrary ReadWriteMap
1.438 - /// and if a key is setted to a new value then store it
1.439 - /// in the inverse map.
1.440 - /// \param _Graph The graph type.
1.441 - /// \param _Map The map to extend with inversable functionality.
1.442 - template <
1.443 - typename _Graph,
1.444 - typename _Item,
1.445 - typename _Value,
1.446 - typename _Map
1.447 - = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
1.448 - >
1.449 - class InvertableMap : protected _Map {
1.450 -
1.451 - public:
1.452 -
1.453 - typedef _Map Map;
1.454 - typedef _Graph Graph;
1.455 -
1.456 - /// The key type of InvertableMap (Node, Edge, UndirEdge).
1.457 - typedef typename _Map::Key Key;
1.458 - /// The value type of the InvertableMap.
1.459 - typedef typename _Map::Value Value;
1.460 -
1.461 - /// \brief Constructor.
1.462 - ///
1.463 - /// Construct a new InvertableMap for the graph.
1.464 - ///
1.465 - InvertableMap(const Graph& graph) : Map(graph) {}
1.466 -
1.467 - /// \brief The setter function of the map.
1.468 - ///
1.469 - /// Sets the mapped value.
1.470 - void set(const Key& key, const Value& val) {
1.471 - Value oldval = Map::operator[](key);
1.472 - typename Container::iterator it = invMap.find(oldval);
1.473 - if (it != invMap.end() && it->second == key) {
1.474 - invMap.erase(it);
1.475 - }
1.476 - invMap.insert(make_pair(val, key));
1.477 - Map::set(key, val);
1.478 - }
1.479 -
1.480 - /// \brief The getter function of the map.
1.481 - ///
1.482 - /// It gives back the value associated with the key.
1.483 - const Value operator[](const Key& key) const {
1.484 - return Map::operator[](key);
1.485 - }
1.486 -
1.487 - /// \brief Add a new key to the map.
1.488 - ///
1.489 - /// Add a new key to the map. It is called by the
1.490 - /// \c AlterationNotifier.
1.491 - virtual void add(const Key& key) {
1.492 - Map::add(key);
1.493 - }
1.494 -
1.495 - /// \brief Erase the key from the map.
1.496 - ///
1.497 - /// Erase the key to the map. It is called by the
1.498 - /// \c AlterationNotifier.
1.499 - virtual void erase(const Key& key) {
1.500 - Value val = Map::operator[](key);
1.501 - typename Container::iterator it = invMap.find(val);
1.502 - if (it != invMap.end() && it->second == key) {
1.503 - invMap.erase(it);
1.504 - }
1.505 - Map::erase(key);
1.506 - }
1.507 -
1.508 - /// \brief Clear the keys from the map and inverse map.
1.509 - ///
1.510 - /// Clear the keys from the map and inverse map. It is called by the
1.511 - /// \c AlterationNotifier.
1.512 - virtual void clear() {
1.513 - invMap.clear();
1.514 - Map::clear();
1.515 - }
1.516 -
1.517 - private:
1.518 -
1.519 - typedef std::map<Value, Key> Container;
1.520 - Container invMap;
1.521 -
1.522 - public:
1.523 -
1.524 - /// \brief The inverse map type.
1.525 - ///
1.526 - /// The inverse of this map. The subscript operator of the map
1.527 - /// gives back always the item what was last assigned to the value.
1.528 - class InverseMap {
1.529 - public:
1.530 - /// \brief Constructor of the InverseMap.
1.531 - ///
1.532 - /// Constructor of the InverseMap.
1.533 - InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
1.534 -
1.535 - /// The value type of the InverseMap.
1.536 - typedef typename InvertableMap::Key Value;
1.537 - /// The key type of the InverseMap.
1.538 - typedef typename InvertableMap::Value Key;
1.539 -
1.540 - /// \brief Subscript operator.
1.541 - ///
1.542 - /// Subscript operator. It gives back always the item
1.543 - /// what was last assigned to the value.
1.544 - Value operator[](const Key& key) const {
1.545 - typename Container::const_iterator it = inverted.invMap.find(key);
1.546 - return it->second;
1.547 - }
1.548 -
1.549 - private:
1.550 - const InvertableMap& inverted;
1.551 - };
1.552 -
1.553 - /// \brief It gives back the just readeable inverse map.
1.554 - ///
1.555 - /// It gives back the just readeable inverse map.
1.556 - InverseMap inverse() const {
1.557 - return InverseMap(*this);
1.558 - }
1.559 -
1.560 -
1.561 -
1.562 - };
1.563 -
1.564 - /// \brief Provides a mutable, continuous and unique descriptor for each
1.565 - /// item in the graph.
1.566 - ///
1.567 - /// The DescriptorMap class provides a mutable, continuous and immutable
1.568 - /// mapping for each item in the graph. The value for an item may mutated
1.569 - /// on each operation when the an item erased or added to graph.
1.570 - ///
1.571 - /// \param _Graph The graph class the \c DescriptorMap belongs to.
1.572 - /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1.573 - /// UndirEdge.
1.574 - /// \param _Map A ReadWriteMap mapping from the item type to integer.
1.575 - template <
1.576 - typename _Graph,
1.577 - typename _Item,
1.578 - typename _Map
1.579 - = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
1.580 - >
1.581 - class DescriptorMap : protected _Map {
1.582 -
1.583 - typedef _Item Item;
1.584 - typedef _Map Map;
1.585 -
1.586 - public:
1.587 - /// The graph class of DescriptorMap.
1.588 - typedef _Graph Graph;
1.589 -
1.590 - /// The key type of DescriptorMap (Node, Edge, UndirEdge).
1.591 - typedef typename _Map::Key Key;
1.592 - /// The value type of DescriptorMap.
1.593 - typedef typename _Map::Value Value;
1.594 -
1.595 - /// \brief Constructor.
1.596 - ///
1.597 - /// Constructor for descriptor map.
1.598 - DescriptorMap(const Graph& _graph) : Map(_graph) {
1.599 - build();
1.600 - }
1.601 -
1.602 - /// \brief Add a new key to the map.
1.603 - ///
1.604 - /// Add a new key to the map. It is called by the
1.605 - /// \c AlterationNotifier.
1.606 - virtual void add(const Item& item) {
1.607 - Map::add(item);
1.608 - Map::set(item, invMap.size());
1.609 - invMap.push_back(item);
1.610 - }
1.611 -
1.612 - /// \brief Erase the key from the map.
1.613 - ///
1.614 - /// Erase the key to the map. It is called by the
1.615 - /// \c AlterationNotifier.
1.616 - virtual void erase(const Item& item) {
1.617 - Map::set(invMap.back(), Map::operator[](item));
1.618 - invMap[Map::operator[](item)] = invMap.back();
1.619 - invMap.pop_back();
1.620 - Map::erase(item);
1.621 - }
1.622 -
1.623 - /// \brief Build the unique map.
1.624 - ///
1.625 - /// Build the unique map. It is called by the
1.626 - /// \c AlterationNotifier.
1.627 - virtual void build() {
1.628 - Map::build();
1.629 - Item it;
1.630 - const typename Map::Graph* graph = Map::getGraph();
1.631 - for (graph->first(it); it != INVALID; graph->next(it)) {
1.632 - Map::set(it, invMap.size());
1.633 - invMap.push_back(it);
1.634 - }
1.635 - }
1.636 -
1.637 - /// \brief Clear the keys from the map.
1.638 - ///
1.639 - /// Clear the keys from the map. It is called by the
1.640 - /// \c AlterationNotifier.
1.641 - virtual void clear() {
1.642 - invMap.clear();
1.643 - Map::clear();
1.644 - }
1.645 -
1.646 - /// \brief Gives back the \e descriptor of the item.
1.647 - ///
1.648 - /// Gives back the mutable and unique \e descriptor of the map.
1.649 - int operator[](const Item& item) const {
1.650 - return Map::operator[](item);
1.651 - }
1.652 -
1.653 - private:
1.654 -
1.655 - typedef std::vector<Item> Container;
1.656 - Container invMap;
1.657 -
1.658 - public:
1.659 - /// \brief The inverse map type.
1.660 - ///
1.661 - /// The inverse map type.
1.662 - class InverseMap {
1.663 - public:
1.664 - /// \brief Constructor of the InverseMap.
1.665 - ///
1.666 - /// Constructor of the InverseMap.
1.667 - InverseMap(const DescriptorMap& _inverted)
1.668 - : inverted(_inverted) {}
1.669 -
1.670 -
1.671 - /// The value type of the InverseMap.
1.672 - typedef typename DescriptorMap::Key Value;
1.673 - /// The key type of the InverseMap.
1.674 - typedef typename DescriptorMap::Value Key;
1.675 -
1.676 - /// \brief Subscript operator.
1.677 - ///
1.678 - /// Subscript operator. It gives back the item
1.679 - /// that the descriptor belongs to currently.
1.680 - Value operator[](const Key& key) const {
1.681 - return inverted.invMap[key];
1.682 - }
1.683 -
1.684 - private:
1.685 - const DescriptorMap& inverted;
1.686 - };
1.687 -
1.688 - /// \brief Gives back the inverse of the map.
1.689 - ///
1.690 - /// Gives back the inverse of the map.
1.691 - const InverseMap inverse() const {
1.692 - return InverseMap(*this);
1.693 - }
1.694 - };
1.695 -
1.696 - /// \brief Returns the source of the given edge.
1.697 - ///
1.698 - /// The SourceMap gives back the source Node of the given edge.
1.699 - /// \author Balazs Dezso
1.700 - template <typename Graph>
1.701 - class SourceMap {
1.702 - public:
1.703 -
1.704 - typedef True NeedCopy;
1.705 -
1.706 - typedef typename Graph::Node Value;
1.707 - typedef typename Graph::Edge Key;
1.708 -
1.709 - /// \brief Constructor
1.710 - ///
1.711 - /// Constructor
1.712 - /// \param _graph The graph that the map belongs to.
1.713 - SourceMap(const Graph& _graph) : graph(_graph) {}
1.714 -
1.715 - /// \brief The subscript operator.
1.716 - ///
1.717 - /// The subscript operator.
1.718 - /// \param edge The edge
1.719 - /// \return The source of the edge
1.720 - Value operator[](const Key& edge) {
1.721 - return graph.source(edge);
1.722 - }
1.723 -
1.724 - private:
1.725 - const Graph& graph;
1.726 - };
1.727 -
1.728 - /// \brief Returns a \ref SourceMap class
1.729 - ///
1.730 - /// This function just returns an \ref SourceMap class.
1.731 - /// \relates SourceMap
1.732 - template <typename Graph>
1.733 - inline SourceMap<Graph> sourceMap(const Graph& graph) {
1.734 - return SourceMap<Graph>(graph);
1.735 - }
1.736 -
1.737 - /// \brief Returns the target of the given edge.
1.738 - ///
1.739 - /// The TargetMap gives back the target Node of the given edge.
1.740 - /// \author Balazs Dezso
1.741 - template <typename Graph>
1.742 - class TargetMap {
1.743 - public:
1.744 -
1.745 - typedef True NeedCopy;
1.746 -
1.747 - typedef typename Graph::Node Value;
1.748 - typedef typename Graph::Edge Key;
1.749 -
1.750 - /// \brief Constructor
1.751 - ///
1.752 - /// Constructor
1.753 - /// \param _graph The graph that the map belongs to.
1.754 - TargetMap(const Graph& _graph) : graph(_graph) {}
1.755 -
1.756 - /// \brief The subscript operator.
1.757 - ///
1.758 - /// The subscript operator.
1.759 - /// \param edge The edge
1.760 - /// \return The target of the edge
1.761 - Value operator[](const Key& key) {
1.762 - return graph.target(key);
1.763 - }
1.764 -
1.765 - private:
1.766 - const Graph& graph;
1.767 - };
1.768 -
1.769 - /// \brief Returns a \ref TargetMap class
1.770 -
1.771 - /// This function just returns an \ref TargetMap class.
1.772 - /// \relates TargetMap
1.773 - template <typename Graph>
1.774 - inline TargetMap<Graph> targetMap(const Graph& graph) {
1.775 - return TargetMap<Graph>(graph);
1.776 - }
1.777 -
1.778 - /// \brief Returns the "forward" directed edge view of undirected edge.
1.779 - ///
1.780 - /// Returns the "forward" directed edge view of undirected edge.
1.781 - /// \author Balazs Dezso
1.782 - template <typename Graph>
1.783 - class ForwardMap {
1.784 - public:
1.785 -
1.786 - typedef True NeedCopy;
1.787 -
1.788 - typedef typename Graph::Edge Value;
1.789 - typedef typename Graph::UndirEdge Key;
1.790 -
1.791 - /// \brief Constructor
1.792 - ///
1.793 - /// Constructor
1.794 - /// \param _graph The graph that the map belongs to.
1.795 - ForwardMap(const Graph& _graph) : graph(_graph) {}
1.796 -
1.797 - /// \brief The subscript operator.
1.798 - ///
1.799 - /// The subscript operator.
1.800 - /// \param key An undirected edge
1.801 - /// \return The "forward" directed edge view of undirected edge
1.802 - Value operator[](const Key& key) const {
1.803 - return graph.edgeWithSource(key, graph.source(key));
1.804 - }
1.805 -
1.806 - private:
1.807 - const Graph& graph;
1.808 - };
1.809 -
1.810 - /// \brief Returns a \ref ForwardMap class
1.811 -
1.812 - /// This function just returns an \ref ForwardMap class.
1.813 - /// \relates ForwardMap
1.814 - template <typename Graph>
1.815 - inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1.816 - return ForwardMap<Graph>(graph);
1.817 - }
1.818 -
1.819 - /// \brief Returns the "backward" directed edge view of undirected edge.
1.820 - ///
1.821 - /// Returns the "backward" directed edge view of undirected edge.
1.822 - /// \author Balazs Dezso
1.823 - template <typename Graph>
1.824 - class BackwardMap {
1.825 - public:
1.826 - typedef True NeedCopy;
1.827 -
1.828 - typedef typename Graph::Edge Value;
1.829 - typedef typename Graph::UndirEdge Key;
1.830 -
1.831 - /// \brief Constructor
1.832 - ///
1.833 - /// Constructor
1.834 - /// \param _graph The graph that the map belongs to.
1.835 - BackwardMap(const Graph& _graph) : graph(_graph) {}
1.836 -
1.837 - /// \brief The subscript operator.
1.838 - ///
1.839 - /// The subscript operator.
1.840 - /// \param key An undirected edge
1.841 - /// \return The "backward" directed edge view of undirected edge
1.842 - Value operator[](const Key& key) const {
1.843 - return graph.edgeWithSource(key, graph.target(key));
1.844 - }
1.845 -
1.846 - private:
1.847 - const Graph& graph;
1.848 - };
1.849 -
1.850 - /// \brief Returns a \ref BackwardMap class
1.851 -
1.852 - /// This function just returns an \ref BackwardMap class.
1.853 - /// \relates BackwardMap
1.854 - template <typename Graph>
1.855 - inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1.856 - return BackwardMap<Graph>(graph);
1.857 - }
1.858 -
1.859 -
1.860 - /// @}
1.861 -
1.862 -} //END OF NAMESPACE LEMON
1.863 -
1.864 -#endif