1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/graph_utils.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,861 @@
1.4 +/* -*- C++ -*-
1.5 + * 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