1.1 --- a/lemon/bits/array_map.h Mon Oct 03 14:22:10 2005 +0000
1.2 +++ b/lemon/bits/array_map.h Wed Oct 05 13:15:47 2005 +0000
1.3 @@ -48,6 +48,7 @@
1.4
1.5 typedef _Item Item;
1.6 public:
1.7 + typedef True AdaptibleTag;
1.8
1.9 /// The graph type of the maps.
1.10 typedef _Graph Graph;
1.11 @@ -69,6 +70,8 @@
1.12
1.13 public:
1.14
1.15 + /// \brief Graph and Registry initialized map constructor.
1.16 + ///
1.17 /// Graph and Registry initialized map constructor.
1.18 ArrayMap(const Graph& _g) : graph(&_g) {
1.19 Item it;
1.20 @@ -80,10 +83,9 @@
1.21 }
1.22 }
1.23
1.24 - /// Constructor to use default value to initialize the map.
1.25 -
1.26 - /// It constrates a map and initialize all of the the map.
1.27 -
1.28 + /// \brief Constructor to use default value to initialize the map.
1.29 + ///
1.30 + /// It constructs a map and initialize all of the the map.
1.31 ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
1.32 Item it;
1.33 attach(_g.getNotifier(_Item()));
1.34 @@ -94,8 +96,9 @@
1.35 }
1.36 }
1.37
1.38 - /// Constructor to copy a map of the same map type.
1.39 -
1.40 + /// \brief Constructor to copy a map of the same map type.
1.41 + ///
1.42 + /// Constructor to copy a map of the same map type.
1.43 ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
1.44 if (copy.attached()) {
1.45 attach(*copy.getRegistry());
1.46 @@ -137,35 +140,37 @@
1.47
1.48 public:
1.49
1.50 - ///The subscript operator. The map can be subscripted by the
1.51 - ///actual keys of the graph.
1.52 -
1.53 + /// \brief The subscript operator.
1.54 + ///
1.55 + /// The subscript operator. The map can be subscripted by the
1.56 + /// actual keys of the graph.
1.57 Value& operator[](const Key& key) {
1.58 int id = graph->id(key);
1.59 return values[id];
1.60 }
1.61
1.62 -
1.63 - ///The const subscript operator. The map can be subscripted by the
1.64 - ///actual keys of the graph.
1.65 -
1.66 + /// \brief The const subscript operator.
1.67 + ///
1.68 + /// The const subscript operator. The map can be subscripted by the
1.69 + /// actual keys of the graph.
1.70 const Value& operator[](const Key& key) const {
1.71 int id = graph->id(key);
1.72 return values[id];
1.73 }
1.74 -
1.75 +
1.76 + /// \brief Setter function of the map.
1.77 + ///
1.78 /// Setter function of the map. Equivalent with map[key] = val.
1.79 /// This is a compatibility feature with the not dereferable maps.
1.80 -
1.81 void set(const Key& key, const Value& val) {
1.82 (*this)[key] = val;
1.83 }
1.84
1.85 protected:
1.86 -
1.87 +
1.88 /// Add a new key to the map. It called by the map registry.
1.89 -
1.90 - void add(const Key& key) {
1.91 +
1.92 + virtual void add(const Key& key) {
1.93 int id = graph->id(key);
1.94 if (id >= capacity) {
1.95 int new_capacity = (capacity == 0 ? 1 : capacity);
1.96 @@ -188,7 +193,7 @@
1.97 allocator.construct(&(values[id]), Value());
1.98 }
1.99
1.100 - void add(const std::vector<Key>& keys) {
1.101 + virtual void add(const std::vector<Key>& keys) {
1.102 int max_id = -1;
1.103 for (int i = 0; i < (int)keys.size(); ++i) {
1.104 int id = graph->id(keys[i]);
1.105 @@ -229,19 +234,19 @@
1.106
1.107 /// Erase a key from the map. It called by the map registry.
1.108
1.109 - void erase(const Key& key) {
1.110 + virtual void erase(const Key& key) {
1.111 int id = graph->id(key);
1.112 allocator.destroy(&(values[id]));
1.113 }
1.114
1.115 - void erase(const std::vector<Key>& keys) {
1.116 + virtual void erase(const std::vector<Key>& keys) {
1.117 for (int i = 0; i < (int)keys.size(); ++i) {
1.118 int id = graph->id(keys[i]);
1.119 allocator.destroy(&(values[id]));
1.120 }
1.121 }
1.122
1.123 - void build() {
1.124 + virtual void build() {
1.125 allocate_memory();
1.126 Item it;
1.127 for (graph->first(it); it != INVALID; graph->next(it)) {
1.128 @@ -250,7 +255,7 @@
1.129 }
1.130 }
1.131
1.132 - void clear() {
1.133 + virtual void clear() {
1.134 if (capacity != 0) {
1.135 Item it;
1.136 for (graph->first(it); it != INVALID; graph->next(it)) {
2.1 --- a/lemon/bits/default_map.h Mon Oct 03 14:22:10 2005 +0000
2.2 +++ b/lemon/bits/default_map.h Wed Oct 05 13:15:47 2005 +0000
2.3 @@ -28,8 +28,6 @@
2.4
2.5 namespace lemon {
2.6
2.7 - /// \addtogroup graphmapfactory
2.8 - /// @{
2.9
2.10 template <typename _Graph, typename _Item, typename _Value>
2.11 struct DefaultMapSelector {
2.12 @@ -268,7 +266,6 @@
2.13
2.14 };
2.15
2.16 - /// @}
2.17 }
2.18
2.19 #endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/bits/static_map.h Wed Oct 05 13:15:47 2005 +0000
3.3 @@ -0,0 +1,348 @@
3.4 +/* -*- C++ -*-
3.5 + * lemon/static_map.h - Part of LEMON, a generic C++ optimization library
3.6 + *
3.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.9 + *
3.10 + * Permission to use, modify and distribute this software is granted
3.11 + * provided that this copyright notice appears in all copies. For
3.12 + * precise terms see the accompanying LICENSE file.
3.13 + *
3.14 + * This software is provided "AS IS" with no warranty of any kind,
3.15 + * express or implied, and with no claim as to its suitability for any
3.16 + * purpose.
3.17 + *
3.18 + */
3.19 +
3.20 +#ifndef LEMON_STATIC_MAP_H
3.21 +#define LEMON_STATIC_MAP_H
3.22 +
3.23 +#include <algorithm>
3.24 +#include <iostream>
3.25 +
3.26 +#include <lemon/utility.h>
3.27 +#include <lemon/bits/map_iterator.h>
3.28 +#include <lemon/bits/alteration_notifier.h>
3.29 +#include <lemon/error.h>
3.30 +#include <lemon/concept_check.h>
3.31 +#include <lemon/concept/maps.h>
3.32 +
3.33 +/// \ingroup graphmaps
3.34 +///
3.35 +///\file
3.36 +///\brief Static sized graph maps.
3.37 +
3.38 +namespace lemon {
3.39 +
3.40 + /// \ingroup graphmaps
3.41 + ///
3.42 + /// \brief Graph map with static sized storage.
3.43 + ///
3.44 + /// The StaticMap template class is graph map structure what
3.45 + /// does not update automatically the map when a key is added to or
3.46 + /// erased from the map rather it throws an exception. This map factory
3.47 + /// uses the allocators to implement the container functionality.
3.48 + ///
3.49 + /// \param Registry The AlterationNotifier that will notify this map.
3.50 + /// \param Item The item type of the graph items.
3.51 + /// \param Value The value type of the map.
3.52 + ///
3.53 + /// \author Balazs Dezso
3.54 +
3.55 +
3.56 + template <typename _Graph, typename _Item, typename _Value>
3.57 + class StaticMap : public AlterationNotifier<_Item>::ObserverBase {
3.58 + public:
3.59 +
3.60 + /// \brief Exception class for unsupported exceptions.
3.61 + class UnsupportedOperation : public lemon::LogicError {
3.62 + public:
3.63 + virtual const char* exceptionName() const {
3.64 + return "lemon::StaticMap::UnsupportedOperation";
3.65 + }
3.66 + };
3.67 +
3.68 + typedef True AdaptibleTag;
3.69 +
3.70 + /// The graph type of the map.
3.71 + typedef _Graph Graph;
3.72 + /// The key type of the map.
3.73 + typedef _Item Key;
3.74 + /// The id map type of the map.
3.75 + typedef AlterationNotifier<_Item> Registry;
3.76 + /// The value type of the map.
3.77 + typedef _Value Value;
3.78 +
3.79 + /// The map type.
3.80 + typedef StaticMap Map;
3.81 + /// The base class of the map.
3.82 + typedef typename Registry::ObserverBase Parent;
3.83 +
3.84 + private:
3.85 +
3.86 + typedef std::vector<Value> Container;
3.87 +
3.88 + public:
3.89 +
3.90 + /// \brief Constructor to attach the new map into the registry.
3.91 + ///
3.92 + /// It constructs a map and attachs it into the registry.
3.93 + /// It adds all the items of the graph to the map.
3.94 + StaticMap(const Graph& _g) : graph(&_g) {
3.95 + attach(_g.getNotifier(_Item()));
3.96 + build();
3.97 + }
3.98 +
3.99 + /// \brief Constructor uses given value to initialize the map.
3.100 + ///
3.101 + /// It constructs a map uses a given value to initialize the map.
3.102 + /// It adds all the items of the graph to the map.
3.103 + StaticMap(const Graph& _g, const Value& _v) : graph(&_g) {
3.104 + attach(_g.getNotifier(_Item()));
3.105 + unsigned size = graph->maxId(_Item()) + 1;
3.106 + container.reserve(size);
3.107 + container.resize(size, _v);
3.108 + }
3.109 +
3.110 + /// \brief Copy constructor
3.111 + ///
3.112 + /// Copy constructor.
3.113 + StaticMap(const StaticMap& _copy) : Parent(), graph(_copy.getGraph()) {
3.114 + if (_copy.attached()) {
3.115 + attach(*_copy.getRegistry());
3.116 + container = _copy.container;
3.117 + }
3.118 + }
3.119 +
3.120 + /// \brief Destrcutor
3.121 + ///
3.122 + /// Destructor.
3.123 + virtual ~StaticMap() {
3.124 + clear();
3.125 + if (attached()) {
3.126 + detach();
3.127 + }
3.128 + }
3.129 +
3.130 +
3.131 + private:
3.132 +
3.133 + StaticMap& operator=(const StaticMap&);
3.134 +
3.135 + protected:
3.136 +
3.137 + using Parent::attach;
3.138 + using Parent::detach;
3.139 + using Parent::attached;
3.140 +
3.141 + const Graph* getGraph() const {
3.142 + return graph;
3.143 + }
3.144 +
3.145 + public:
3.146 +
3.147 + typedef typename Container::reference Reference;
3.148 + typedef typename Container::pointer Pointer;
3.149 + typedef const Value ConstValue;
3.150 + typedef typename Container::const_reference ConstReference;
3.151 + typedef typename Container::const_pointer ConstPointer;
3.152 +
3.153 + /// \brief The subcript operator.
3.154 + ///
3.155 + /// The subscript operator. The map can be subscripted by the
3.156 + /// actual items of the graph.
3.157 +
3.158 + Reference operator[](const Key& key) {
3.159 + return container[graph->id(key)];
3.160 + }
3.161 +
3.162 + /// \brief The const subcript operator.
3.163 + ///
3.164 + /// The const subscript operator. The map can be subscripted by the
3.165 + /// actual items of the graph.
3.166 +
3.167 + ConstReference operator[](const Key& key) const {
3.168 + return container[graph->id(key)];
3.169 + }
3.170 +
3.171 +
3.172 + /// \brief The setter function of the map.
3.173 + ///
3.174 + /// It the same as operator[](key) = value expression.
3.175 + ///
3.176 + void set(const Key& key, const Value& value) {
3.177 + (*this)[key] = value;
3.178 + }
3.179 +
3.180 + protected:
3.181 +
3.182 + /// \brief Adds a new key to the map.
3.183 + ///
3.184 + /// It adds a new key to the map. It called by the observer registry
3.185 + /// and it overrides the add() member function of the observer base.
3.186 +
3.187 + void add(const Key&) {
3.188 + throw UnsupportedOperation();
3.189 + }
3.190 +
3.191 + /// \brief Erases a key from the map.
3.192 + ///
3.193 + /// Erase a key from the map. It called by the observer registry
3.194 + /// and it overrides the erase() member function of the observer base.
3.195 + void erase(const Key&) {
3.196 + throw UnsupportedOperation();
3.197 + }
3.198 +
3.199 + /// Buildes the map.
3.200 +
3.201 + /// It buildes the map. It called by the observer registry
3.202 + /// and it overrides the build() member function of the observer base.
3.203 +
3.204 + void build() {
3.205 + int size = graph->maxId(_Item()) + 1;
3.206 + container.reserve(size);
3.207 + container.resize(size);
3.208 + }
3.209 +
3.210 + /// Clear the map.
3.211 +
3.212 + /// It erase all items from the map. It called by the observer registry
3.213 + /// and it overrides the clear() member function of the observer base.
3.214 + void clear() {
3.215 + container.clear();
3.216 + }
3.217 +
3.218 + private:
3.219 +
3.220 + Container container;
3.221 + const Graph *graph;
3.222 +
3.223 + };
3.224 +
3.225 + /// \e
3.226 + template <typename _Base>
3.227 + class StaticMappableGraphExtender : public _Base {
3.228 + public:
3.229 +
3.230 + typedef StaticMappableGraphExtender<_Base> Graph;
3.231 + typedef _Base Parent;
3.232 +
3.233 + typedef typename Parent::Node Node;
3.234 + typedef typename Parent::NodeIt NodeIt;
3.235 +
3.236 + typedef typename Parent::Edge Edge;
3.237 + typedef typename Parent::EdgeIt EdgeIt;
3.238 +
3.239 +
3.240 + template <typename _Value>
3.241 + class NodeMap
3.242 + : public IterableMapExtender<StaticMap<Graph, Node, _Value> > {
3.243 + public:
3.244 + typedef StaticMappableGraphExtender Graph;
3.245 + typedef IterableMapExtender<StaticMap<Graph, Node, _Value> > Parent;
3.246 +
3.247 + NodeMap(const Graph& _g)
3.248 + : Parent(_g) {}
3.249 + NodeMap(const Graph& _g, const _Value& _v)
3.250 + : Parent(_g, _v) {}
3.251 +
3.252 + NodeMap& operator=(const NodeMap& cmap) {
3.253 + return operator=<NodeMap>(cmap);
3.254 + }
3.255 +
3.256 +
3.257 + /// \brief Template assign operator.
3.258 + ///
3.259 + /// The given parameter should be conform to the ReadMap
3.260 + /// concecpt and could be indiced by the current item set of
3.261 + /// the NodeMap. In this case the value for each item
3.262 + /// is assigned by the value of the given ReadMap.
3.263 + template <typename CMap>
3.264 + NodeMap& operator=(const CMap& cmap) {
3.265 + checkConcept<concept::ReadMap<Node, _Value>, CMap>();
3.266 + const typename Parent::Graph* graph = Parent::getGraph();
3.267 + Node it;
3.268 + for (graph->first(it); it != INVALID; graph->next(it)) {
3.269 + Parent::set(it, cmap[it]);
3.270 + }
3.271 + return *this;
3.272 + }
3.273 +
3.274 + };
3.275 +
3.276 + template <typename _Value>
3.277 + class EdgeMap
3.278 + : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
3.279 + public:
3.280 + typedef StaticMappableGraphExtender Graph;
3.281 + typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
3.282 +
3.283 + EdgeMap(const Graph& _g)
3.284 + : Parent(_g) {}
3.285 + EdgeMap(const Graph& _g, const _Value& _v)
3.286 + : Parent(_g, _v) {}
3.287 +
3.288 + EdgeMap& operator=(const EdgeMap& cmap) {
3.289 + return operator=<EdgeMap>(cmap);
3.290 + }
3.291 +
3.292 + template <typename CMap>
3.293 + EdgeMap& operator=(const CMap& cmap) {
3.294 + checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
3.295 + const typename Parent::Graph* graph = Parent::getGraph();
3.296 + Edge it;
3.297 + for (graph->first(it); it != INVALID; graph->next(it)) {
3.298 + Parent::set(it, cmap[it]);
3.299 + }
3.300 + return *this;
3.301 + }
3.302 + };
3.303 +
3.304 + };
3.305 +
3.306 + /// \e
3.307 + template <typename _Base>
3.308 + class StaticMappableUndirGraphExtender :
3.309 + public StaticMappableGraphExtender<_Base> {
3.310 + public:
3.311 +
3.312 + typedef StaticMappableUndirGraphExtender Graph;
3.313 + typedef StaticMappableGraphExtender<_Base> Parent;
3.314 +
3.315 + typedef typename Parent::UndirEdge UndirEdge;
3.316 +
3.317 + template <typename _Value>
3.318 + class UndirEdgeMap
3.319 + : public IterableMapExtender<StaticMap<Graph, UndirEdge, _Value> > {
3.320 + public:
3.321 + typedef StaticMappableUndirGraphExtender Graph;
3.322 + typedef IterableMapExtender<
3.323 + StaticMap<Graph, UndirEdge, _Value> > Parent;
3.324 +
3.325 + UndirEdgeMap(const Graph& _g)
3.326 + : Parent(_g) {}
3.327 + UndirEdgeMap(const Graph& _g, const _Value& _v)
3.328 + : Parent(_g, _v) {}
3.329 +
3.330 + UndirEdgeMap& operator=(const UndirEdgeMap& cmap) {
3.331 + return operator=<UndirEdgeMap>(cmap);
3.332 + }
3.333 +
3.334 + template <typename CMap>
3.335 + UndirEdgeMap& operator=(const CMap& cmap) {
3.336 + checkConcept<concept::ReadMap<UndirEdge, _Value>, CMap>();
3.337 + const typename Parent::Graph* graph = Parent::getGraph();
3.338 + UndirEdge it;
3.339 + for (graph->first(it); it != INVALID; graph->next(it)) {
3.340 + Parent::set(it, cmap[it]);
3.341 + }
3.342 + return *this;
3.343 + }
3.344 + };
3.345 +
3.346 +
3.347 + };
3.348 +
3.349 +}
3.350 +
3.351 +#endif
4.1 --- a/lemon/bits/vector_map.h Mon Oct 03 14:22:10 2005 +0000
4.2 +++ b/lemon/bits/vector_map.h Wed Oct 05 13:15:47 2005 +0000
4.3 @@ -44,12 +44,11 @@
4.4 /// uses the std::vector to implement the container function.
4.5 ///
4.6 /// \param Registry The AlterationNotifier that will notify this map.
4.7 - /// \param IdMap The IdMap type of the graph items.
4.8 + /// \param Item The item type of the graph items.
4.9 /// \param Value The value type of the map.
4.10 ///
4.11 /// \author Balazs Dezso
4.12
4.13 -
4.14 template <
4.15 typename _Graph,
4.16 typename _Item,
4.17 @@ -57,6 +56,8 @@
4.18 >
4.19 class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
4.20 public:
4.21 +
4.22 + typedef True AdaptibleTag;
4.23
4.24 /// The graph type of the map.
4.25 typedef _Graph Graph;
4.26 @@ -93,26 +94,27 @@
4.27
4.28 typedef True FullTypeTag;
4.29
4.30 - /// Constructor to attach the new map into the registry.
4.31 -
4.32 - /// It construates a map and attachs it into the registry.
4.33 + /// \brief Constructor to attach the new map into the registry.
4.34 + ///
4.35 + /// It constructs a map and attachs it into the registry.
4.36 /// It adds all the items of the graph to the map.
4.37 -
4.38 VectorMap(const Graph& _g) : graph(&_g) {
4.39 attach(_g.getNotifier(_Item()));
4.40 build();
4.41 }
4.42
4.43 - /// Constructor uses given value to initialize the map.
4.44 -
4.45 - /// It construates a map uses a given value to initialize the map.
4.46 + /// \brief Constructor uses given value to initialize the map.
4.47 + ///
4.48 + /// It constructs a map uses a given value to initialize the map.
4.49 /// It adds all the items of the graph to the map.
4.50 -
4.51 VectorMap(const Graph& _g, const Value& _v) : graph(&_g) {
4.52 attach(_g.getNotifier(_Item()));
4.53 container.resize(graph->maxId(_Item()) + 1, _v);
4.54 }
4.55
4.56 + /// \brief Copy constructor
4.57 + ///
4.58 + /// Copy constructor.
4.59 VectorMap(const VectorMap& _copy)
4.60 : Parent(), graph(_copy.getGraph()) {
4.61 if (_copy.attached()) {
4.62 @@ -121,6 +123,9 @@
4.63 }
4.64 }
4.65
4.66 + /// \brief Destrcutor
4.67 + ///
4.68 + /// Destructor.
4.69 virtual ~VectorMap() {
4.70 if (attached()) {
4.71 detach();
4.72 @@ -144,29 +149,26 @@
4.73
4.74 public:
4.75
4.76 - /// The subcript operator.
4.77 -
4.78 + /// \brief The subcript operator.
4.79 + ///
4.80 /// The subscript operator. The map can be subscripted by the
4.81 - /// actual items of the graph.
4.82 -
4.83 + /// actual items of the graph.
4.84 Reference operator[](const Key& key) {
4.85 return container[graph->id(key)];
4.86 }
4.87
4.88 - /// The const subcript operator.
4.89 -
4.90 + /// \brief The const subcript operator.
4.91 + ///
4.92 /// The const subscript operator. The map can be subscripted by the
4.93 /// actual items of the graph.
4.94 -
4.95 ConstReference operator[](const Key& key) const {
4.96 return container[graph->id(key)];
4.97 }
4.98
4.99
4.100 - /// The setter function of the map.
4.101 -
4.102 + /// \brief The setter function of the map.
4.103 + ///
4.104 /// It the same as operator[](key) = value expression.
4.105 - ///
4.106 void set(const Key& key, const Value& value) {
4.107 (*this)[key] = value;
4.108 }
4.109 @@ -176,35 +178,33 @@
4.110 /// \brief Adds a new key to the map.
4.111 ///
4.112 /// It adds a new key to the map. It called by the observer registry
4.113 - /// and it overrides the add() member function of the observer base.
4.114 -
4.115 - void add(const Key& key) {
4.116 + /// and it overrides the add() member function of the observer base.
4.117 + virtual void add(const Key& key) {
4.118 int id = graph->id(key);
4.119 if (id >= (int)container.size()) {
4.120 container.resize(id + 1);
4.121 }
4.122 }
4.123
4.124 - /// Erases a key from the map.
4.125 -
4.126 + /// \brief Erase a key from the map.
4.127 + ///
4.128 /// Erase a key from the map. It called by the observer registry
4.129 /// and it overrides the erase() member function of the observer base.
4.130 - void erase(const Key&) {}
4.131 + virtual void erase(const Key&) {}
4.132
4.133 - /// Buildes the map.
4.134 -
4.135 + /// \brief Buildes the map.
4.136 + ///
4.137 /// It buildes the map. It called by the observer registry
4.138 /// and it overrides the build() member function of the observer base.
4.139 -
4.140 - void build() {
4.141 + virtual void build() {
4.142 container.resize(graph->maxId(_Item()) + 1);
4.143 }
4.144
4.145 - /// Clear the map.
4.146 -
4.147 + /// \brief Clear the map.
4.148 + ///
4.149 /// It erase all items from the map. It called by the observer registry
4.150 /// and it overrides the clear() member function of the observer base.
4.151 - void clear() {
4.152 + virtual void clear() {
4.153 container.clear();
4.154 }
4.155
5.1 --- a/lemon/full_graph.h Mon Oct 03 14:22:10 2005 +0000
5.2 +++ b/lemon/full_graph.h Wed Oct 05 13:15:47 2005 +0000
5.3 @@ -22,7 +22,7 @@
5.4
5.5 #include <lemon/bits/iterable_graph_extender.h>
5.6 #include <lemon/bits/alteration_notifier.h>
5.7 -#include <lemon/bits/default_map.h>
5.8 +#include <lemon/bits/static_map.h>
5.9
5.10 #include <lemon/bits/undir_graph_extender.h>
5.11
5.12 @@ -195,7 +195,7 @@
5.13 AlterableFullGraphBase;
5.14 typedef IterableGraphExtender<AlterableFullGraphBase>
5.15 IterableFullGraphBase;
5.16 - typedef MappableGraphExtender<
5.17 + typedef StaticMappableGraphExtender<
5.18 IterableGraphExtender<
5.19 AlterableGraphExtender<FullGraphBase> > > ExtendedFullGraphBase;
5.20
5.21 @@ -298,10 +298,12 @@
5.22 /// It finds the first edge from \c u to \c v. Otherwise it looks for
5.23 /// the next edge from \c u to \c v after \c prev.
5.24 /// \return The found edge or INVALID if there is no such an edge.
5.25 - Edge findEdge(Node u,Node v, Edge prev = INVALID)
5.26 - {
5.27 - return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
5.28 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
5.29 + if (prev.id != -1 || u.id <= v.id) return -1;
5.30 + return Edge(u.id * (u.id - 1) / 2 + v.id);
5.31 }
5.32 +
5.33 + typedef True FindEdgeTag;
5.34
5.35
5.36 class Node {
5.37 @@ -328,8 +330,6 @@
5.38
5.39 Edge(int _id) : id(_id) {}
5.40
5.41 - Edge(const UndirFullGraphBase& _graph, int source, int target)
5.42 - : id(_graph._nodeNum * target+source) {}
5.43 public:
5.44 Edge() { }
5.45 Edge (Invalid) { id = -1; }
5.46 @@ -339,7 +339,7 @@
5.47 };
5.48
5.49 void first(Node& node) const {
5.50 - node.id = _nodeNum-1;
5.51 + node.id = _nodeNum - 1;
5.52 }
5.53
5.54 static void next(Node& node) {
5.55 @@ -347,7 +347,7 @@
5.56 }
5.57
5.58 void first(Edge& edge) const {
5.59 - edge.id = _edgeNum-1;
5.60 + edge.id = _edgeNum - 1;
5.61 }
5.62
5.63 static void next(Edge& edge) {
5.64 @@ -355,31 +355,35 @@
5.65 }
5.66
5.67 void firstOut(Edge& edge, const Node& node) const {
5.68 - edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;
5.69 + int src = node.id;
5.70 + int trg = 0;
5.71 + edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
5.72 }
5.73
5.74 /// \todo with specialized iterators we can make faster iterating
5.75 - void nextOut(Edge& e) const {
5.76 - int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
5.77 - int target = e.id - (source) * (source - 1) / 2;
5.78 - ++target;
5.79 - e.id = target < source ? source * (source - 1) / 2 + target : -1;
5.80 + void nextOut(Edge& edge) const {
5.81 + int src = source(edge).id;
5.82 + int trg = target(edge).id;
5.83 + ++trg;
5.84 + edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
5.85 }
5.86
5.87 void firstIn(Edge& edge, const Node& node) const {
5.88 - edge.id = node.id * (node.id + 1) / 2 - 1;
5.89 + int src = node.id + 1;
5.90 + int trg = node.id;
5.91 + edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
5.92 }
5.93
5.94 - void nextIn(Edge& e) const {
5.95 - int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
5.96 - int target = e.id - (source) * (source - 1) / 2; ++target;
5.97 - ++source;
5.98 - e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1;
5.99 + void nextIn(Edge& edge) const {
5.100 + int src = source(edge).id;
5.101 + int trg = target(edge).id;
5.102 + ++src;
5.103 + edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
5.104 }
5.105
5.106 };
5.107
5.108 - typedef MappableUndirGraphExtender<
5.109 + typedef StaticMappableUndirGraphExtender<
5.110 IterableUndirGraphExtender<
5.111 AlterableUndirGraphExtender<
5.112 UndirGraphExtender<UndirFullGraphBase> > > > ExtendedUndirFullGraphBase;
6.1 --- a/lemon/grid_graph.h Mon Oct 03 14:22:10 2005 +0000
6.2 +++ b/lemon/grid_graph.h Wed Oct 05 13:15:47 2005 +0000
6.3 @@ -23,7 +23,7 @@
6.4
6.5 #include <lemon/bits/iterable_graph_extender.h>
6.6 #include <lemon/bits/alteration_notifier.h>
6.7 -#include <lemon/bits/default_map.h>
6.8 +#include <lemon/bits/static_map.h>
6.9
6.10 #include <lemon/bits/undir_graph_extender.h>
6.11
6.12 @@ -339,7 +339,7 @@
6.13 };
6.14
6.15
6.16 - typedef MappableUndirGraphExtender<
6.17 + typedef StaticMappableUndirGraphExtender<
6.18 IterableUndirGraphExtender<
6.19 AlterableUndirGraphExtender<
6.20 UndirGraphExtender<GridGraphBase> > > > ExtendedGridGraphBase;
7.1 --- a/lemon/hypercube_graph.h Mon Oct 03 14:22:10 2005 +0000
7.2 +++ b/lemon/hypercube_graph.h Wed Oct 05 13:15:47 2005 +0000
7.3 @@ -232,7 +232,7 @@
7.4 };
7.5
7.6
7.7 - typedef MappableGraphExtender<
7.8 + typedef StaticMappableGraphExtender<
7.9 IterableGraphExtender<
7.10 AlterableGraphExtender<
7.11 HyperCubeGraphBase > > > ExtendedHyperCubeGraphBase;