# HG changeset patch # User deba # Date 1112704246 0 # Node ID d4acebef72764831a71d00df38152a7dc0d001b2 # Parent 4ea2147274db6b3687105075a39d9dac951f3a5d Stuffs moved into bits diff -r 4ea2147274db -r d4acebef7276 src/lemon/Makefile.am --- a/src/lemon/Makefile.am Tue Apr 05 09:49:01 2005 +0000 +++ b/src/lemon/Makefile.am Tue Apr 05 12:30:46 2005 +0000 @@ -10,16 +10,13 @@ lp_solver_skeleton.cc pkginclude_HEADERS = \ - array_map.h \ - bezier.h \ + bezier.h \ bfs.h \ dfs.h \ bin_heap.h \ - default_map.h \ dijkstra.h \ dimacs.h \ error.h \ - extended_pair.h \ fib_heap.h \ full_graph.h \ graph_wrapper.h \ @@ -28,8 +25,6 @@ invalid.h \ kruskal.h \ list_graph.h \ - alteration_notifier.h \ - map_iterator.h \ maps.h \ max_matching.h \ min_cost_flow.h \ @@ -40,18 +35,23 @@ smart_graph.h \ time_measure.h \ unionfind.h \ - vector_map.h \ xy.h \ concept_check.h \ utility.h \ - iterable_graph_extender.h \ - extendable_graph_extender.h \ - clearable_graph_extender.h \ - erasable_graph_extender.h \ - undir_graph_extender.h \ graph_reader.h \ graph_writer.h \ - map_utils.h + map_utils.h \ + bits/alteration_notifier.h \ + bits/map_iterator.h \ + bits/array_map.h \ + bits/default_map.h \ + bits/extended_pair.h \ + bits/vector_map.h \ + bits/iterable_graph_extender.h \ + bits/extendable_graph_extender.h \ + bits/clearable_graph_extender.h \ + bits/erasable_graph_extender.h \ + bits/undir_graph_extender.h noinst_HEADERS = \ lp_base.h \ diff -r 4ea2147274db -r d4acebef7276 src/lemon/alteration_notifier.h --- a/src/lemon/alteration_notifier.h Tue Apr 05 09:49:01 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,390 +0,0 @@ -/* -*- C++ -*- - * src/lemon/notifier.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_ALTERATION_OBSERVER_REGISTRY_H -#define LEMON_ALTERATION_OBSERVER_REGISTRY_H - -#include -#include - -///\ingroup graphmaps -///\file -///\brief Observer registry for graph alteration observers. - -using namespace std; - -namespace lemon { - - /// \addtogroup graphmaps - /// @{ - - /// Registry class to register objects observes alterations in the graph. - - /// This class is a registry for the objects which observe the - /// alterations in a container. The alteration observers can be attached - /// to and detached from the registry. The observers have to inherit - /// from the \ref AlterationNotifier::ObserverBase and override - /// the virtual functions in that. - /// - /// The most important application of the alteration observing is the - /// dynamic map implementation when the observers are observing the - /// alterations in the graph. - /// - /// \param _Item The item type what the observers are observing, usually - /// edge or node. - /// - /// \author Balazs Dezso - - template - class AlterationNotifier { - public: - typedef _Item Item; - - /// ObserverBase is the base class for the observers. - - /// ObserverBase is the abstract base class for the observers. - /// It will be notified about an item was inserted into or - /// erased from the graph. - /// - /// The observer interface contains some pure virtual functions - /// to override. The add() and erase() functions are - /// to notify the oberver when one item is added or - /// erased. - /// - /// The build() and clear() members are to notify the observer - /// about the container is built from an empty container or - /// is cleared to an empty container. - /// - /// \author Balazs Dezso - - class ObserverBase { - protected: - typedef AlterationNotifier Registry; - - friend class AlterationNotifier; - - /// Default constructor. - - /// Default constructor for ObserverBase. - /// - ObserverBase() : registry(0) {} - - virtual ~ObserverBase() {} - - /// Attaches the observer into an AlterationNotifier. - - /// This member attaches the observer into an AlterationNotifier. - /// - void attach(AlterationNotifier& r) { - registry = &r; - registry->attach(*this); - } - - /// Detaches the observer into an AlterationNotifier. - - /// This member detaches the observer from an AlterationNotifier. - /// - void detach() { - if (registry) { - registry->detach(*this); - } - } - - - /// Gives back a pointer to the registry what the map attached into. - - /// This function gives back a pointer to the registry what the map - /// attached into. - /// - Registry* getRegistry() const { return const_cast(registry); } - - /// Gives back true when the observer is attached into a registry. - bool attached() const { return registry != 0; } - - private: - - ObserverBase(const ObserverBase& copy); - ObserverBase& operator=(const ObserverBase& copy); - - protected: - - Registry* registry; - int registry_index; - - public: - - /// \brief The member function to notificate the observer about an - /// item is added to the container. - /// - /// The add() member function notificates the observer about an item - /// is added to the container. It have to be overrided in the - /// subclasses. - - virtual void add(const Item&) = 0; - - - /// \brief The member function to notificate the observer about an - /// item is erased from the container. - /// - /// The erase() member function notificates the observer about an - /// item is erased from the container. It have to be overrided in - /// the subclasses. - - virtual void erase(const Item&) = 0; - - /// \brief The member function to notificate the observer about the - /// container is built. - /// - /// The build() member function notificates the observer about the - /// container is built from an empty container. It have to be - /// overrided in the subclasses. - - virtual void build() = 0; - - /// \brief The member function to notificate the observer about all - /// items are erased from the container. - /// - /// The clear() member function notificates the observer about all - /// items are erased from the container. It have to be overrided in - /// the subclasses. - - virtual void clear() = 0; - - }; - - protected: - - - typedef std::vector Container; - - Container container; - - - public: - - /// Default constructor. - - /// - /// The default constructor of the AlterationNotifier. - /// It creates an empty registry. - AlterationNotifier() {} - - /// Copy Constructor of the AlterationNotifier. - - /// Copy constructor of the AlterationNotifier. - /// It creates only an empty registry because the copiable - /// registry's observers have to be registered still into that registry. - AlterationNotifier(const AlterationNotifier&) {} - - /// Assign operator. - - /// Assign operator for the AlterationNotifier. - /// It makes the notifier only empty because the copiable - /// notifier's observers have to be registered still into that registry. - AlterationNotifier& operator=(const AlterationNotifier&) { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->registry = 0; - } - } - - /// Destructor. - - /// Destructor of the AlterationNotifier. - /// - ~AlterationNotifier() { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->registry = 0; - } - } - - - protected: - - void attach(ObserverBase& observer) { - container.push_back(&observer); - observer.registry = this; - observer.registry_index = container.size()-1; - } - - void detach(ObserverBase& base) { - container.back()->registry_index = base.registry_index; - container[base.registry_index] = container.back(); - container.pop_back(); - base.registry = 0; - } - - public: - - /// Notifies all the registered observers about an Item added to the container. - - /// It notifies all the registered observers about an Item added to the container. - /// - void add(const Item& key) { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->add(key); - } - } - - /// Notifies all the registered observers about an Item erased from the container. - - /// It notifies all the registered observers about an Item erased from the container. - /// - void erase(const Item& key) { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->erase(key); - } - } - - - /// Notifies all the registered observers about the container is built. - - /// Notifies all the registered observers about the container is built - /// from an empty container. - void build() { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->build(); - } - } - - - /// Notifies all the registered observers about all Items are erased. - - /// Notifies all the registered observers about all Items are erased - /// from the container. - void clear() { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->clear(); - } - } - }; - - - /// \brief Class to extend a graph with the functionality of alteration - /// observing. - /// - /// AlterableGraphExtender extends the _Base graphs functionality with - /// the possibility of alteration observing. It defines two observer - /// registrys for the nodes and mapes. - /// - /// \todo Document what "alteration observing" is. And probably find a - /// better (shorter) name. - /// - /// \param _Base is the base class to extend. - /// - /// \pre _Base is conform to the BaseGraphComponent concept. - /// - /// \post AlterableGraphExtender<_Base> is conform to the - /// AlterableGraphComponent concept. - /// - /// \author Balazs Dezso - - template - class AlterableGraphExtender : public _Base { - public: - - typedef AlterableGraphExtender Graph; - typedef _Base Parent; - - typedef typename Parent::Node Node; - typedef typename Parent::Edge Edge; - - /// The edge observer registry. - typedef AlterationNotifier EdgeNotifier; - /// The node observer registry. - typedef AlterationNotifier NodeNotifier; - - - protected: - - mutable EdgeNotifier edge_notifier; - - mutable NodeNotifier node_notifier; - - public: - - /// \brief Gives back the edge alteration notifier. - /// - /// Gives back the edge alteration notifier. - EdgeNotifier& getNotifier(Edge) const { - return edge_notifier; - } - - /// \brief Gives back the node alteration notifier. - /// - /// Gives back the node alteration notifier. - NodeNotifier& getNotifier(Node) const { - return node_notifier; - } - - ~AlterableGraphExtender() { - node_notifier.clear(); - edge_notifier.clear(); - } - - }; - - /// \brief Class to extend an undirected graph with the functionality of - /// alteration observing. - /// - /// \todo Document. - /// - /// \sa AlterableGraphExtender - /// - /// \bug This should be done some other way. Possibilities: template - /// specialization (not very easy, if at all possible); some kind of - /// enable_if boost technique? - - template - class AlterableUndirGraphExtender - : public AlterableGraphExtender<_Base> { - public: - - typedef AlterableUndirGraphExtender Graph; - typedef AlterableGraphExtender<_Base> Parent; - - typedef typename Parent::UndirEdge UndirEdge; - - /// The edge observer registry. - typedef AlterationNotifier UndirEdgeNotifier; - - protected: - - mutable UndirEdgeNotifier undir_edge_notifier; - - public: - - using Parent::getNotifier; - UndirEdgeNotifier& getNotifier(UndirEdge) const { - return undir_edge_notifier; - } - - ~AlterableUndirGraphExtender() { - undir_edge_notifier.clear(); - } - }; - -/// @} - - -} - -#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/array_map.h --- a/src/lemon/array_map.h Tue Apr 05 09:49:01 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,377 +0,0 @@ -/* -*- C++ -*- - * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_ARRAY_MAP_H -#define LEMON_ARRAY_MAP_H - -#include -#include - -///\ingroup graphmaps -///\file -///\brief Graph maps that construates and destruates -///their elements dynamically. - -namespace lemon { - - - /// \addtogroup graphmaps - /// @{ - - /** The ArrayMap template class is graph map structure what - * automatically updates the map when a key is added to or erased from - * the map. This map factory uses the allocators to implement - * the container functionality. - * - * The template parameter is the AlterationNotifier that the maps - * will belong to and the Value. - */ - - template - class ArrayMap : public AlterationNotifier<_Item>::ObserverBase { - - typedef _Item Item; - public: - - /// The graph type of the maps. - typedef _Graph Graph; - /// The key type of the maps. - typedef _Item Key; - - typedef AlterationNotifier<_Item> Registry; - - /// The MapBase of the Map which imlements the core regisitry function. - typedef typename Registry::ObserverBase Parent; - - /// The value type of the map. - typedef _Value Value; - - - private: - typedef std::allocator Allocator; - - - public: - - /** Graph and Registry initialized map constructor. - */ - ArrayMap(const Graph& _g) : graph(&_g) { - Item it; - attach(_g.getNotifier(Item())); - allocate_memory(); - for (graph->first(it); it != INVALID; graph->next(it)) { - int id = graph->id(it);; - allocator.construct(&(values[id]), Value()); - } - } - - /// Constructor to use default value to initialize the map. - - /// It constrates a map and initialize all of the the map. - - ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) { - Item it; - attach(_g.getNotifier(_Item())); - allocate_memory(); - for (graph->first(it); it != INVALID; graph->next(it)) { - int id = graph->id(it);; - allocator.construct(&(values[id]), _v); - } - } - - /** Constructor to copy a map of the same map type. - */ - ArrayMap(const ArrayMap& copy) { - if (copy.attached()) { - attach(*copy.getRegistry()); - } - capacity = copy.capacity; - if (capacity == 0) return; - values = allocator.allocate(capacity); - Item it; - for (graph->first(it); it != INVALID; graph->next(it)) { - int id = graph->id(it);; - allocator.construct(&(values[id]), copy.values[id]); - } - } - - using Parent::attach; - using Parent::detach; - using Parent::attached; - - /** Assign operator to copy a map of the same map type. - */ - ArrayMap& operator=(const ArrayMap& copy) { - if (© == this) return *this; - - if (graph != copy.graph) { - if (attached()) { - clear(); - detach(); - } - if (copy.attached()) { - attach(*copy.getRegistry()); - } - capacity = copy.capacity; - if (capacity == 0) return *this; - values = allocator.allocate(capacity); - } - - Item it; - for (graph->first(it); it != INVALID; graph->next(it)) { - int id = graph->id(it);; - allocator.construct(&(values[id]), copy.values[id]); - } - - return *this; - } - - /** The destructor of the map. - */ - virtual ~ArrayMap() { - if (attached()) { - clear(); - detach(); - } - } - - - /** - * The subscript operator. The map can be subscripted by the - * actual keys of the graph. - */ - Value& operator[](const Key& key) { - int id = graph->id(key); - return values[id]; - } - - /** - * The const subscript operator. The map can be subscripted by the - * actual keys of the graph. - */ - const Value& operator[](const Key& key) const { - int id = graph->id(key); - return values[id]; - } - - /** Setter function of the map. Equivalent with map[key] = val. - * This is a compatibility feature with the not dereferable maps. - */ - void set(const Key& key, const Value& val) { - (*this)[key] = val; - } - - /** Add a new key to the map. It called by the map registry. - */ - void add(const Key& key) { - int id = graph->id(key); - if (id >= capacity) { - int new_capacity = (capacity == 0 ? 1 : capacity); - while (new_capacity <= id) { - new_capacity <<= 1; - } - Value* new_values = allocator.allocate(new_capacity); - Item it; - for (graph->first(it); it != INVALID; graph->next(it)) { - int jd = graph->id(it);; - if (id != jd) { - allocator.construct(&(new_values[jd]), values[jd]); - allocator.destroy(&(values[jd])); - } - } - if (capacity != 0) allocator.deallocate(values, capacity); - values = new_values; - capacity = new_capacity; - } - allocator.construct(&(values[id]), Value()); - } - - /** Erase a key from the map. It called by the map registry. - */ - void erase(const Key& key) { - int id = graph->id(key); - allocator.destroy(&(values[id])); - } - - void build() { - allocate_memory(); - Item it; - for (graph->first(it); it != INVALID; graph->next(it)) { - int id = graph->id(it);; - allocator.construct(&(values[id]), Value()); - } - } - - void clear() { - if (capacity != 0) { - Item it; - for (graph->first(it); it != INVALID; graph->next(it)) { - int id = graph->id(it);; - allocator.destroy(&(values[id])); - } - allocator.deallocate(values, capacity); - capacity = 0; - } - } - - const Graph* getGraph() { - return graph; - } - -// /// The stl compatible pair iterator of the map. -// typedef MapIterator Iterator; -// /// The stl compatible const pair iterator of the map. -// typedef MapConstIterator ConstIterator; - -// /** Returns the begin iterator of the map. -// */ -// Iterator begin() { -// return Iterator(*this, KeyIt(*MapBase::getGraph())); -// } - -// /** Returns the end iterator of the map. -// */ -// Iterator end() { -// return Iterator(*this, INVALID); -// } - -// /** Returns the begin ConstIterator of the map. -// */ -// ConstIterator begin() const { -// return ConstIterator(*this, KeyIt(*MapBase::getGraph())); -// } - -// /** Returns the end const_iterator of the map. -// */ -// ConstIterator end() const { -// return ConstIterator(*this, INVALID); -// } - -// /// The KeySet of the Map. -// typedef MapConstKeySet ConstKeySet; - -// /// KeySet getter function. -// ConstKeySet keySet() const { -// return ConstKeySet(*this); -// } - -// /// The ConstValueSet of the Map. -// typedef MapConstValueSet ConstValueSet; - -// /// ConstValueSet getter function. -// ConstValueSet valueSet() const { -// return ConstValueSet(*this); -// } - -// /// The ValueSet of the Map. -// typedef MapValueSet ValueSet; - -// /// ValueSet getter function. -// ValueSet valueSet() { -// return ValueSet(*this); -// } - - private: - - void allocate_memory() { - int max_id = graph->maxId(_Item()); - if (max_id == -1) { - capacity = 0; - values = 0; - return; - } - capacity = 1; - while (capacity <= max_id) { - capacity <<= 1; - } - values = allocator.allocate(capacity); - } - - const Graph* graph; - int capacity; - Value* values; - Allocator allocator; - - }; - - template - class ArrayMappableGraphExtender : public _Base { - public: - - typedef ArrayMappableGraphExtender<_Base> Graph; - typedef _Base Parent; - - typedef typename Parent::Node Node; - typedef typename Parent::NodeIt NodeIt; - typedef typename Parent::NodeNotifier NodeObserverRegistry; - - typedef typename Parent::Edge Edge; - typedef typename Parent::EdgeIt EdgeIt; - typedef typename Parent::EdgeNotifier EdgeObserverRegistry; - - - - template - class NodeMap - : public IterableMapExtender > { - public: - typedef ArrayMappableGraphExtender<_Base> Graph; - - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - - typedef IterableMapExtender > Parent; - - //typedef typename Parent::Graph Graph; - typedef typename Parent::Value Value; - - NodeMap(const Graph& g) - : Parent(g) {} - NodeMap(const Graph& g, const Value& v) - : Parent(g, v) {} - - }; - - template - class EdgeMap - : public IterableMapExtender > { - public: - typedef ArrayMappableGraphExtender<_Base> Graph; - - typedef typename Graph::Edge Edge; - typedef typename Graph::EdgeIt EdgeIt; - - typedef IterableMapExtender > Parent; - - //typedef typename Parent::Graph Graph; - typedef typename Parent::Value Value; - - EdgeMap(const Graph& g) - : Parent(g) {} - EdgeMap(const Graph& g, const Value& v) - : Parent(g, v) {} - - }; - - }; - -/// @} - -} - -#endif //LEMON_ARRAY_MAP_H diff -r 4ea2147274db -r d4acebef7276 src/lemon/bits/alteration_notifier.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/bits/alteration_notifier.h Tue Apr 05 12:30:46 2005 +0000 @@ -0,0 +1,390 @@ +/* -*- C++ -*- + * src/lemon/notifier.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_ALTERATION_OBSERVER_REGISTRY_H +#define LEMON_ALTERATION_OBSERVER_REGISTRY_H + +#include +#include + +///\ingroup graphmaps +///\file +///\brief Observer registry for graph alteration observers. + +using namespace std; + +namespace lemon { + + /// \addtogroup graphmaps + /// @{ + + /// Registry class to register objects observes alterations in the graph. + + /// This class is a registry for the objects which observe the + /// alterations in a container. The alteration observers can be attached + /// to and detached from the registry. The observers have to inherit + /// from the \ref AlterationNotifier::ObserverBase and override + /// the virtual functions in that. + /// + /// The most important application of the alteration observing is the + /// dynamic map implementation when the observers are observing the + /// alterations in the graph. + /// + /// \param _Item The item type what the observers are observing, usually + /// edge or node. + /// + /// \author Balazs Dezso + + template + class AlterationNotifier { + public: + typedef _Item Item; + + /// ObserverBase is the base class for the observers. + + /// ObserverBase is the abstract base class for the observers. + /// It will be notified about an item was inserted into or + /// erased from the graph. + /// + /// The observer interface contains some pure virtual functions + /// to override. The add() and erase() functions are + /// to notify the oberver when one item is added or + /// erased. + /// + /// The build() and clear() members are to notify the observer + /// about the container is built from an empty container or + /// is cleared to an empty container. + /// + /// \author Balazs Dezso + + class ObserverBase { + protected: + typedef AlterationNotifier Registry; + + friend class AlterationNotifier; + + /// Default constructor. + + /// Default constructor for ObserverBase. + /// + ObserverBase() : registry(0) {} + + virtual ~ObserverBase() {} + + /// Attaches the observer into an AlterationNotifier. + + /// This member attaches the observer into an AlterationNotifier. + /// + void attach(AlterationNotifier& r) { + registry = &r; + registry->attach(*this); + } + + /// Detaches the observer into an AlterationNotifier. + + /// This member detaches the observer from an AlterationNotifier. + /// + void detach() { + if (registry) { + registry->detach(*this); + } + } + + + /// Gives back a pointer to the registry what the map attached into. + + /// This function gives back a pointer to the registry what the map + /// attached into. + /// + Registry* getRegistry() const { return const_cast(registry); } + + /// Gives back true when the observer is attached into a registry. + bool attached() const { return registry != 0; } + + private: + + ObserverBase(const ObserverBase& copy); + ObserverBase& operator=(const ObserverBase& copy); + + protected: + + Registry* registry; + int registry_index; + + public: + + /// \brief The member function to notificate the observer about an + /// item is added to the container. + /// + /// The add() member function notificates the observer about an item + /// is added to the container. It have to be overrided in the + /// subclasses. + + virtual void add(const Item&) = 0; + + + /// \brief The member function to notificate the observer about an + /// item is erased from the container. + /// + /// The erase() member function notificates the observer about an + /// item is erased from the container. It have to be overrided in + /// the subclasses. + + virtual void erase(const Item&) = 0; + + /// \brief The member function to notificate the observer about the + /// container is built. + /// + /// The build() member function notificates the observer about the + /// container is built from an empty container. It have to be + /// overrided in the subclasses. + + virtual void build() = 0; + + /// \brief The member function to notificate the observer about all + /// items are erased from the container. + /// + /// The clear() member function notificates the observer about all + /// items are erased from the container. It have to be overrided in + /// the subclasses. + + virtual void clear() = 0; + + }; + + protected: + + + typedef std::vector Container; + + Container container; + + + public: + + /// Default constructor. + + /// + /// The default constructor of the AlterationNotifier. + /// It creates an empty registry. + AlterationNotifier() {} + + /// Copy Constructor of the AlterationNotifier. + + /// Copy constructor of the AlterationNotifier. + /// It creates only an empty registry because the copiable + /// registry's observers have to be registered still into that registry. + AlterationNotifier(const AlterationNotifier&) {} + + /// Assign operator. + + /// Assign operator for the AlterationNotifier. + /// It makes the notifier only empty because the copiable + /// notifier's observers have to be registered still into that registry. + AlterationNotifier& operator=(const AlterationNotifier&) { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->registry = 0; + } + } + + /// Destructor. + + /// Destructor of the AlterationNotifier. + /// + ~AlterationNotifier() { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->registry = 0; + } + } + + + protected: + + void attach(ObserverBase& observer) { + container.push_back(&observer); + observer.registry = this; + observer.registry_index = container.size()-1; + } + + void detach(ObserverBase& base) { + container.back()->registry_index = base.registry_index; + container[base.registry_index] = container.back(); + container.pop_back(); + base.registry = 0; + } + + public: + + /// Notifies all the registered observers about an Item added to the container. + + /// It notifies all the registered observers about an Item added to the container. + /// + void add(const Item& key) { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->add(key); + } + } + + /// Notifies all the registered observers about an Item erased from the container. + + /// It notifies all the registered observers about an Item erased from the container. + /// + void erase(const Item& key) { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->erase(key); + } + } + + + /// Notifies all the registered observers about the container is built. + + /// Notifies all the registered observers about the container is built + /// from an empty container. + void build() { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->build(); + } + } + + + /// Notifies all the registered observers about all Items are erased. + + /// Notifies all the registered observers about all Items are erased + /// from the container. + void clear() { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->clear(); + } + } + }; + + + /// \brief Class to extend a graph with the functionality of alteration + /// observing. + /// + /// AlterableGraphExtender extends the _Base graphs functionality with + /// the possibility of alteration observing. It defines two observer + /// registrys for the nodes and mapes. + /// + /// \todo Document what "alteration observing" is. And probably find a + /// better (shorter) name. + /// + /// \param _Base is the base class to extend. + /// + /// \pre _Base is conform to the BaseGraphComponent concept. + /// + /// \post AlterableGraphExtender<_Base> is conform to the + /// AlterableGraphComponent concept. + /// + /// \author Balazs Dezso + + template + class AlterableGraphExtender : public _Base { + public: + + typedef AlterableGraphExtender Graph; + typedef _Base Parent; + + typedef typename Parent::Node Node; + typedef typename Parent::Edge Edge; + + /// The edge observer registry. + typedef AlterationNotifier EdgeNotifier; + /// The node observer registry. + typedef AlterationNotifier NodeNotifier; + + + protected: + + mutable EdgeNotifier edge_notifier; + + mutable NodeNotifier node_notifier; + + public: + + /// \brief Gives back the edge alteration notifier. + /// + /// Gives back the edge alteration notifier. + EdgeNotifier& getNotifier(Edge) const { + return edge_notifier; + } + + /// \brief Gives back the node alteration notifier. + /// + /// Gives back the node alteration notifier. + NodeNotifier& getNotifier(Node) const { + return node_notifier; + } + + ~AlterableGraphExtender() { + node_notifier.clear(); + edge_notifier.clear(); + } + + }; + + /// \brief Class to extend an undirected graph with the functionality of + /// alteration observing. + /// + /// \todo Document. + /// + /// \sa AlterableGraphExtender + /// + /// \bug This should be done some other way. Possibilities: template + /// specialization (not very easy, if at all possible); some kind of + /// enable_if boost technique? + + template + class AlterableUndirGraphExtender + : public AlterableGraphExtender<_Base> { + public: + + typedef AlterableUndirGraphExtender Graph; + typedef AlterableGraphExtender<_Base> Parent; + + typedef typename Parent::UndirEdge UndirEdge; + + /// The edge observer registry. + typedef AlterationNotifier UndirEdgeNotifier; + + protected: + + mutable UndirEdgeNotifier undir_edge_notifier; + + public: + + using Parent::getNotifier; + UndirEdgeNotifier& getNotifier(UndirEdge) const { + return undir_edge_notifier; + } + + ~AlterableUndirGraphExtender() { + undir_edge_notifier.clear(); + } + }; + +/// @} + + +} + +#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/bits/array_map.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/bits/array_map.h Tue Apr 05 12:30:46 2005 +0000 @@ -0,0 +1,377 @@ +/* -*- C++ -*- + * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_ARRAY_MAP_H +#define LEMON_ARRAY_MAP_H + +#include +#include + +///\ingroup graphmaps +///\file +///\brief Graph maps that construates and destruates +///their elements dynamically. + +namespace lemon { + + + /// \addtogroup graphmaps + /// @{ + + /** The ArrayMap template class is graph map structure what + * automatically updates the map when a key is added to or erased from + * the map. This map factory uses the allocators to implement + * the container functionality. + * + * The template parameter is the AlterationNotifier that the maps + * will belong to and the Value. + */ + + template + class ArrayMap : public AlterationNotifier<_Item>::ObserverBase { + + typedef _Item Item; + public: + + /// The graph type of the maps. + typedef _Graph Graph; + /// The key type of the maps. + typedef _Item Key; + + typedef AlterationNotifier<_Item> Registry; + + /// The MapBase of the Map which imlements the core regisitry function. + typedef typename Registry::ObserverBase Parent; + + /// The value type of the map. + typedef _Value Value; + + + private: + typedef std::allocator Allocator; + + + public: + + /** Graph and Registry initialized map constructor. + */ + ArrayMap(const Graph& _g) : graph(&_g) { + Item it; + attach(_g.getNotifier(Item())); + allocate_memory(); + for (graph->first(it); it != INVALID; graph->next(it)) { + int id = graph->id(it);; + allocator.construct(&(values[id]), Value()); + } + } + + /// Constructor to use default value to initialize the map. + + /// It constrates a map and initialize all of the the map. + + ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) { + Item it; + attach(_g.getNotifier(_Item())); + allocate_memory(); + for (graph->first(it); it != INVALID; graph->next(it)) { + int id = graph->id(it);; + allocator.construct(&(values[id]), _v); + } + } + + /** Constructor to copy a map of the same map type. + */ + ArrayMap(const ArrayMap& copy) { + if (copy.attached()) { + attach(*copy.getRegistry()); + } + capacity = copy.capacity; + if (capacity == 0) return; + values = allocator.allocate(capacity); + Item it; + for (graph->first(it); it != INVALID; graph->next(it)) { + int id = graph->id(it);; + allocator.construct(&(values[id]), copy.values[id]); + } + } + + using Parent::attach; + using Parent::detach; + using Parent::attached; + + /** Assign operator to copy a map of the same map type. + */ + ArrayMap& operator=(const ArrayMap& copy) { + if (© == this) return *this; + + if (graph != copy.graph) { + if (attached()) { + clear(); + detach(); + } + if (copy.attached()) { + attach(*copy.getRegistry()); + } + capacity = copy.capacity; + if (capacity == 0) return *this; + values = allocator.allocate(capacity); + } + + Item it; + for (graph->first(it); it != INVALID; graph->next(it)) { + int id = graph->id(it);; + allocator.construct(&(values[id]), copy.values[id]); + } + + return *this; + } + + /** The destructor of the map. + */ + virtual ~ArrayMap() { + if (attached()) { + clear(); + detach(); + } + } + + + /** + * The subscript operator. The map can be subscripted by the + * actual keys of the graph. + */ + Value& operator[](const Key& key) { + int id = graph->id(key); + return values[id]; + } + + /** + * The const subscript operator. The map can be subscripted by the + * actual keys of the graph. + */ + const Value& operator[](const Key& key) const { + int id = graph->id(key); + return values[id]; + } + + /** Setter function of the map. Equivalent with map[key] = val. + * This is a compatibility feature with the not dereferable maps. + */ + void set(const Key& key, const Value& val) { + (*this)[key] = val; + } + + /** Add a new key to the map. It called by the map registry. + */ + void add(const Key& key) { + int id = graph->id(key); + if (id >= capacity) { + int new_capacity = (capacity == 0 ? 1 : capacity); + while (new_capacity <= id) { + new_capacity <<= 1; + } + Value* new_values = allocator.allocate(new_capacity); + Item it; + for (graph->first(it); it != INVALID; graph->next(it)) { + int jd = graph->id(it);; + if (id != jd) { + allocator.construct(&(new_values[jd]), values[jd]); + allocator.destroy(&(values[jd])); + } + } + if (capacity != 0) allocator.deallocate(values, capacity); + values = new_values; + capacity = new_capacity; + } + allocator.construct(&(values[id]), Value()); + } + + /** Erase a key from the map. It called by the map registry. + */ + void erase(const Key& key) { + int id = graph->id(key); + allocator.destroy(&(values[id])); + } + + void build() { + allocate_memory(); + Item it; + for (graph->first(it); it != INVALID; graph->next(it)) { + int id = graph->id(it);; + allocator.construct(&(values[id]), Value()); + } + } + + void clear() { + if (capacity != 0) { + Item it; + for (graph->first(it); it != INVALID; graph->next(it)) { + int id = graph->id(it);; + allocator.destroy(&(values[id])); + } + allocator.deallocate(values, capacity); + capacity = 0; + } + } + + const Graph* getGraph() { + return graph; + } + +// /// The stl compatible pair iterator of the map. +// typedef MapIterator Iterator; +// /// The stl compatible const pair iterator of the map. +// typedef MapConstIterator ConstIterator; + +// /** Returns the begin iterator of the map. +// */ +// Iterator begin() { +// return Iterator(*this, KeyIt(*MapBase::getGraph())); +// } + +// /** Returns the end iterator of the map. +// */ +// Iterator end() { +// return Iterator(*this, INVALID); +// } + +// /** Returns the begin ConstIterator of the map. +// */ +// ConstIterator begin() const { +// return ConstIterator(*this, KeyIt(*MapBase::getGraph())); +// } + +// /** Returns the end const_iterator of the map. +// */ +// ConstIterator end() const { +// return ConstIterator(*this, INVALID); +// } + +// /// The KeySet of the Map. +// typedef MapConstKeySet ConstKeySet; + +// /// KeySet getter function. +// ConstKeySet keySet() const { +// return ConstKeySet(*this); +// } + +// /// The ConstValueSet of the Map. +// typedef MapConstValueSet ConstValueSet; + +// /// ConstValueSet getter function. +// ConstValueSet valueSet() const { +// return ConstValueSet(*this); +// } + +// /// The ValueSet of the Map. +// typedef MapValueSet ValueSet; + +// /// ValueSet getter function. +// ValueSet valueSet() { +// return ValueSet(*this); +// } + + private: + + void allocate_memory() { + int max_id = graph->maxId(_Item()); + if (max_id == -1) { + capacity = 0; + values = 0; + return; + } + capacity = 1; + while (capacity <= max_id) { + capacity <<= 1; + } + values = allocator.allocate(capacity); + } + + const Graph* graph; + int capacity; + Value* values; + Allocator allocator; + + }; + + template + class ArrayMappableGraphExtender : public _Base { + public: + + typedef ArrayMappableGraphExtender<_Base> Graph; + typedef _Base Parent; + + typedef typename Parent::Node Node; + typedef typename Parent::NodeIt NodeIt; + typedef typename Parent::NodeNotifier NodeObserverRegistry; + + typedef typename Parent::Edge Edge; + typedef typename Parent::EdgeIt EdgeIt; + typedef typename Parent::EdgeNotifier EdgeObserverRegistry; + + + + template + class NodeMap + : public IterableMapExtender > { + public: + typedef ArrayMappableGraphExtender<_Base> Graph; + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + + typedef IterableMapExtender > Parent; + + //typedef typename Parent::Graph Graph; + typedef typename Parent::Value Value; + + NodeMap(const Graph& g) + : Parent(g) {} + NodeMap(const Graph& g, const Value& v) + : Parent(g, v) {} + + }; + + template + class EdgeMap + : public IterableMapExtender > { + public: + typedef ArrayMappableGraphExtender<_Base> Graph; + + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + + typedef IterableMapExtender > Parent; + + //typedef typename Parent::Graph Graph; + typedef typename Parent::Value Value; + + EdgeMap(const Graph& g) + : Parent(g) {} + EdgeMap(const Graph& g, const Value& v) + : Parent(g, v) {} + + }; + + }; + +/// @} + +} + +#endif //LEMON_ARRAY_MAP_H diff -r 4ea2147274db -r d4acebef7276 src/lemon/bits/clearable_graph_extender.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/bits/clearable_graph_extender.h Tue Apr 05 12:30:46 2005 +0000 @@ -0,0 +1,49 @@ +// -*- c++ -*- + +#ifndef LEMON_CLEARABLE_GRAPH_EXTENDER_H +#define LEMON_CLEARABLE_GRAPH_EXTENDER_H + +#include + + +namespace lemon { + + template + class ClearableGraphExtender : public _Base { + public: + + typedef ClearableGraphExtender Graph; + typedef _Base Parent; + typedef typename Parent::Node Node; + typedef typename Parent::Edge Edge; + + void clear() { + Parent::getNotifier(Node()).clear(); + Parent::getNotifier(Edge()).clear(); + Parent::clear(); + } + + }; + + template + class ClearableUndirGraphExtender : public _Base { + public: + + typedef ClearableUndirGraphExtender Graph; + typedef _Base Parent; + typedef typename Parent::Node Node; + typedef typename Parent::UndirEdge UndirEdge; + typedef typename Parent::Edge Edge; + + void clear() { + Parent::getNotifier(Node()).clear(); + Parent::getNotifier(UndirEdge()).clear(); + Parent::getNotifier(Edge()).clear(); + Parent::clear(); + } + + }; + +} + +#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/bits/default_map.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/bits/default_map.h Tue Apr 05 12:30:46 2005 +0000 @@ -0,0 +1,230 @@ +/* -*- C++ -*- + * src/lemon/default_map.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_DEFAULT_MAP_H +#define LEMON_DEFAULT_MAP_H + + +#include +#include + +///\ingroup graphmaps +///\file +///\brief Graph maps that construct and destruct +///their elements dynamically. + +namespace lemon { + +/// \addtogroup graphmaps +/// @{ + + /** The ArrayMap template class is graph map structure what + * automatically updates the map when a key is added to or erased from + * the map. This map uses the VectorMap if the Value is a primitive + * type and the ArrayMap for the other cases. + * + * The template parameter is the MapRegistry that the maps + * will belong to and the Value. + */ + + + + template + struct DefaultMapSelector { + typedef ArrayMap<_Graph, _Item, _Value> Map; + }; + + // bool + template + struct DefaultMapSelector<_Graph, _Item, bool> { + typedef VectorMap<_Graph, _Item, bool> Map; + }; + + // char + template + struct DefaultMapSelector<_Graph, _Item, char> { + typedef VectorMap<_Graph, _Item, char> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, signed char> { + typedef VectorMap<_Graph, _Item, signed char> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, unsigned char> { + typedef VectorMap<_Graph, _Item, unsigned char> Map; + }; + + + // int + template + struct DefaultMapSelector<_Graph, _Item, signed int> { + typedef VectorMap<_Graph, _Item, signed int> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, unsigned int> { + typedef VectorMap<_Graph, _Item, unsigned int> Map; + }; + + + // short + template + struct DefaultMapSelector<_Graph, _Item, signed short> { + typedef VectorMap<_Graph, _Item, signed short> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, unsigned short> { + typedef VectorMap<_Graph, _Item, unsigned short> Map; + }; + + + // long + template + struct DefaultMapSelector<_Graph, _Item, signed long> { + typedef VectorMap<_Graph, _Item, signed long> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, unsigned long> { + typedef VectorMap<_Graph, _Item, unsigned long> Map; + }; + + // \todo handling long long type + + + // float + template + struct DefaultMapSelector<_Graph, _Item, float> { + typedef VectorMap<_Graph, _Item, float> Map; + }; + + + // double + template + struct DefaultMapSelector<_Graph, _Item, double> { + typedef VectorMap<_Graph, _Item, double> Map; + }; + + + // long double + template + struct DefaultMapSelector<_Graph, _Item, long double> { + typedef VectorMap<_Graph, _Item, long double> Map; + }; + + + // pointer + template + struct DefaultMapSelector<_Graph, _Item, _Ptr*> { + typedef VectorMap<_Graph, _Item, _Ptr*> Map; + }; + + + + template < + typename _Graph, + typename _Item, + typename _Value> + class DefaultMap + : public DefaultMapSelector<_Graph, _Item, _Value>::Map { + public: + typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent; + typedef DefaultMap<_Graph, _Item, _Value> Map; + + typedef typename Parent::Graph Graph; + typedef typename Parent::Value Value; + + DefaultMap(const Graph& _g) : Parent(_g) {} + DefaultMap(const Graph& _g, const Value& _v) : Parent(_g, _v) {} + }; + + + + template + class DefaultMappableGraphExtender : public _Base { + public: + + typedef DefaultMappableGraphExtender<_Base> Graph; + typedef _Base Parent; + + typedef typename Parent::Node Node; + typedef typename Parent::NodeIt NodeIt; + + typedef typename Parent::Edge Edge; + typedef typename Parent::EdgeIt EdgeIt; + + + template + class NodeMap + : public IterableMapExtender > { + public: + typedef DefaultMappableGraphExtender Graph; + typedef IterableMapExtender > Parent; + + NodeMap(const Graph& _g) + : Parent(_g) {} + NodeMap(const Graph& _g, const _Value& _v) + : Parent(_g, _v) {} + }; + + template + class EdgeMap + : public IterableMapExtender > { + public: + typedef DefaultMappableGraphExtender Graph; + typedef IterableMapExtender > Parent; + + EdgeMap(const Graph& _g) + : Parent(_g) {} + EdgeMap(const Graph& _g, const _Value& _v) + : Parent(_g, _v) {} + }; + + }; + + template + class MappableUndirGraphExtender : + public DefaultMappableGraphExtender<_Base> { + public: + + typedef MappableUndirGraphExtender Graph; + typedef DefaultMappableGraphExtender<_Base> Parent; + + typedef typename Parent::UndirEdge UndirEdge; + + template + class UndirEdgeMap + : public IterableMapExtender > { + public: + typedef MappableUndirGraphExtender Graph; + typedef IterableMapExtender< + DefaultMap > Parent; + + UndirEdgeMap(const Graph& _g) + : Parent(_g) {} + UndirEdgeMap(const Graph& _g, const _Value& _v) + : Parent(_g, _v) {} + }; + + + }; + +} + +#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/bits/erasable_graph_extender.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/bits/erasable_graph_extender.h Tue Apr 05 12:30:46 2005 +0000 @@ -0,0 +1,80 @@ +// -*- c++ -*- + +#ifndef LEMON_ERASABLE_GRAPH_EXTENDER_H +#define LEMON_ERASABLE_GRAPH_EXTENDER_H + +#include + + +namespace lemon { + + template + class ErasableGraphExtender : public _Base { + public: + + typedef ErasableGraphExtender Graph; + typedef _Base Parent; + + typedef typename Parent::Node Node; + typedef typename Parent::Edge Edge; + + void erase(const Node& node) { + Edge edge; + Parent::firstOut(edge, node); + while (edge != INVALID ) { + erase(edge); + Parent::firstOut(edge, node); + } + + Parent::firstIn(edge, node); + while (edge != INVALID ) { + erase(edge); + Parent::firstIn(edge, node); + } + + Parent::getNotifier(Node()).erase(node); + Parent::erase(node); + } + + void erase(const Edge& edge) { + Parent::getNotifier(Edge()).erase(edge); + Parent::erase(edge); + } + + }; + + template + class ErasableUndirGraphExtender : public _Base { + public: + + typedef ErasableUndirGraphExtender Graph; + typedef _Base Parent; + + typedef typename Parent::Node Node; + typedef typename Parent::UndirEdge UndirEdge; + typedef typename Parent::Edge Edge; + + void erase(const Node& node) { + Edge edge; + Parent::firstOut(edge, node); + while (edge != INVALID ) { + erase(edge); + Parent::firstOut(edge, node); + } + + Parent::getNotifier(Node()).erase(node); + Parent::erase(node); + } + + void erase(const UndirEdge& uedge) { + Parent::getNotifier(Edge()).erase(Edge(uedge,true)); + Parent::getNotifier(Edge()).erase(Edge(uedge,false)); + Parent::getNotifier(UndirEdge()).erase(uedge); + Parent::erase(uedge); + } + + }; + +} + +#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/bits/extendable_graph_extender.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/bits/extendable_graph_extender.h Tue Apr 05 12:30:46 2005 +0000 @@ -0,0 +1,65 @@ +// -*- c++ -*- + +#ifndef LEMON_EXTENDABLE_GRAPH_EXTENDER_H +#define LEMON_EXTENDABLE_GRAPH_EXTENDER_H + +namespace lemon { + + template + class ExtendableGraphExtender : public _Base { + public: + + typedef ExtendableGraphExtender Graph; + typedef _Base Parent; + + typedef typename Parent::Node Node; + typedef typename Parent::Edge Edge; + + Node addNode() { + Node node = Parent::addNode(); + Parent::getNotifier(Node()).add(node); + return node; + } + + Edge addEdge(const Node& from, const Node& to) { + Edge edge = Parent::addEdge(from, to); + Parent::getNotifier(Edge()).add(edge); + return edge; + } + + }; + + template + class ExtendableUndirGraphExtender : public _Base { + public: + + typedef ExtendableUndirGraphExtender Graph; + typedef _Base Parent; + + typedef typename Parent::Node Node; + typedef typename Parent::Edge Edge; + typedef typename Parent::UndirEdge UndirEdge; + + Node addNode() { + Node node = Parent::addNode(); + Parent::getNotifier(Node()).add(node); + return node; + } + + UndirEdge addEdge(const Node& from, const Node& to) { + UndirEdge uedge = Parent::addEdge(from, to); + Parent::getNotifier(UndirEdge()).add(uedge); + + Edge edge_forward(uedge, true); + Edge edge_backward(uedge, false); + Parent::getNotifier(Edge()).add(edge_forward); + Parent::getNotifier(Edge()).add(edge_backward); + + return uedge; + } + + }; + +} + +#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/bits/extended_pair.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/bits/extended_pair.h Tue Apr 05 12:30:46 2005 +0000 @@ -0,0 +1,80 @@ +/* -*- C++ -*- + * src/lemon/extended_pair.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_EXTENDED_PAIR_H +#define LEMON_EXTENDED_PAIR_H + +template +struct extended_pair { + typedef T1 first_type; + typedef T2 second_type; + + extended_pair() : first(), second() {} + + extended_pair(A1 f, A2 s) : first(f), second(s) {} + + template + extended_pair(const Pair& pair) : first(pair.first), second(pair.second) {} + + T1 first; + T2 second; +}; + +template +bool operator==(const extended_pair& left, + const extended_pair& right) { + return left.first == right.first && left.second == right.second; +} + +template +bool operator!=(const extended_pair& left, + const extended_pair& right) { + return !(left == right); +} + +template +bool operator<(const extended_pair& left, + const extended_pair& right) { + return left.first < right.first || + (!(right.first +bool operator>(const extended_pair& left, + const extended_pair& right) { + return right < left; +} + +template +bool operator<=(const extended_pair& left, + const extended_pair& right) { + return !(right > left); +} + +template +bool operator>=(const extended_pair& left, + const extended_pair& right) { + return !(right < left); +} + + +#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/bits/iterable_graph_extender.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/bits/iterable_graph_extender.h Tue Apr 05 12:30:46 2005 +0000 @@ -0,0 +1,250 @@ +// -*- c++ -*- +#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H +#define LEMON_ITERABLE_GRAPH_EXTENDER_H + +#include + +namespace lemon { + + template + class IterableGraphExtender : public _Base { + public: + + typedef _Base Parent; + typedef IterableGraphExtender<_Base> Graph; + + typedef typename Parent::Node Node; + typedef typename Parent::Edge Edge; + + + class NodeIt : public Node { + const Graph* graph; + public: + + NodeIt() {} + + NodeIt(Invalid i) : Node(i) { } + + explicit NodeIt(const Graph& _graph) : graph(&_graph) { + _graph.first(*static_cast(this)); + } + + NodeIt(const Graph& _graph, const Node& node) + : Node(node), graph(&_graph) {} + + NodeIt& operator++() { + graph->next(*this); + return *this; + } + + }; + + + class EdgeIt : public Edge { + const Graph* graph; + public: + + EdgeIt() { } + + EdgeIt(Invalid i) : Edge(i) { } + + explicit EdgeIt(const Graph& _graph) : graph(&_graph) { + _graph.first(*static_cast(this)); + } + + EdgeIt(const Graph& _graph, const Edge& e) : + Edge(e), graph(&_graph) { } + + EdgeIt& operator++() { + graph->next(*this); + return *this; + } + + }; + + + class OutEdgeIt : public Edge { + const Graph* graph; + public: + + OutEdgeIt() { } + + OutEdgeIt(Invalid i) : Edge(i) { } + + OutEdgeIt(const Graph& _graph, const Node& node) + : graph(&_graph) { + _graph.firstOut(*this, node); + } + + OutEdgeIt(const Graph& _graph, const Edge& edge) + : Edge(edge), graph(&_graph) {} + + OutEdgeIt& operator++() { + graph->nextOut(*this); + return *this; + } + + }; + + + class InEdgeIt : public Edge { + const Graph* graph; + public: + + InEdgeIt() { } + + InEdgeIt(Invalid i) : Edge(i) { } + + InEdgeIt(const Graph& _graph, const Node& node) + : graph(&_graph) { + _graph.firstIn(*this, node); + } + + InEdgeIt(const Graph& _graph, const Edge& edge) : + Edge(edge), graph(&_graph) {} + + InEdgeIt& operator++() { + graph->nextIn(*this); + return *this; + } + + }; + + /// Base node of the iterator + /// + /// Returns the base node (ie. the source in this case) of the iterator + /// + /// \todo Document in the concept! + Node baseNode(const OutEdgeIt &e) const { + return source(e); + } + /// Running node of the iterator + /// + /// Returns the running node (ie. the target in this case) of the + /// iterator + /// + /// \todo Document in the concept! + Node runningNode(const OutEdgeIt &e) const { + return target(e); + } + + /// Base node of the iterator + /// + /// Returns the base node (ie. the target in this case) of the iterator + /// + /// \todo Document in the concept! + Node baseNode(const InEdgeIt &e) const { + return target(e); + } + /// Running node of the iterator + /// + /// Returns the running node (ie. the source in this case) of the + /// iterator + /// + /// \todo Document in the concept! + Node runningNode(const InEdgeIt &e) const { + return source(e); + } + + using Parent::first; + + private: + + // /// \todo When (and if) we change the iterators concept to use operator*, + // /// then the following shadowed methods will become superfluous. + // /// But for now these are important safety measures. + + // void first(NodeIt &) const; + // void first(EdgeIt &) const; + // void first(OutEdgeIt &) const; + // void first(InEdgeIt &) const; + + }; + + + + + + + template + class IterableUndirGraphExtender : public IterableGraphExtender<_Base> { + public: + + typedef IterableGraphExtender<_Base> Parent; + typedef IterableUndirGraphExtender<_Base> Graph; + typedef typename Parent::Node Node; + + typedef typename Parent::UndirEdge UndirEdge; + + class UndirEdgeIt : public Parent::UndirEdge { + const Graph* graph; + public: + + UndirEdgeIt() { } + + UndirEdgeIt(Invalid i) : UndirEdge(i) { } + + explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) { + _graph.first(*static_cast(this)); + } + + UndirEdgeIt(const Graph& _graph, const UndirEdge& e) : + UndirEdge(e), graph(&_graph) { } + + UndirEdgeIt& operator++() { + graph->next(*this); + return *this; + } + + }; + + class IncEdgeIt : public Parent::UndirEdge { + const Graph* graph; + bool forward; + friend class IterableUndirGraphExtender; + template + friend class UndirGraphExtender; + public: + + IncEdgeIt() { } + + IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { } + + IncEdgeIt(const Graph& _graph, const Node &n) + : graph(&_graph) + { + _graph._dirFirstOut(*this, n); + } + + IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n) + : graph(&_graph), UndirEdge(ue) + { + forward = (_graph.source(ue) == n); + } + + IncEdgeIt& operator++() { + graph->_dirNextOut(*this); + return *this; + } + }; + + using Parent::baseNode; + using Parent::runningNode; + + /// Base node of the iterator + /// + /// Returns the base node of the iterator + Node baseNode(const IncEdgeIt &e) const { + return _dirSource(e); + } + /// Running node of the iterator + /// + /// Returns the running node of the iterator + Node runningNode(const IncEdgeIt &e) const { + return _dirTarget(e); + } + + }; +} + +#endif // LEMON_GRAPH_EXTENDER_H diff -r 4ea2147274db -r d4acebef7276 src/lemon/bits/map_iterator.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/bits/map_iterator.h Tue Apr 05 12:30:46 2005 +0000 @@ -0,0 +1,855 @@ +/* -*- C++ -*- + * src/lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_MAP_ITERATOR_H +#define LEMON_MAP_ITERATOR_H + +#include + +#include +#include + +///\ingroup graphmaps +///\file +///\brief Iterators on the maps. + +namespace lemon { + + /// \addtogroup graphmaps + /// @{ + + /** The base class all of the map iterators. + * The class defines the typedefs of the iterators, + * simple step functions and equality operators. + */ + + template < + typename _Graph, + typename _Item> + class MapIteratorBase { + + protected: + + /// The key type of the iterator. + typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt; + + ItemIt it; + + /// Default constructor. + MapIteratorBase() {} + + /// ItemIt initialized MapIteratorBase constructor. + MapIteratorBase(const ItemIt _it) : it(_it) {} + + public: + + /// Stepping forward in the map. + void increment() { + ++it; + } + + /// The equality operator of the map. + bool operator==(const MapIteratorBase& _it) const { + return _it.it == it; + } + + /// The not-equality operator of the map. + bool operator!=(const MapIteratorBase& _it) const { + return !(*this == _it); + } + }; + + + template < + typename _Graph, + typename _Item, + typename _Map> + class MapConstIterator; + + /** Compatible iterator with the stl maps' iterators. + * It iterates on pairs of a key and a value. + */ + template < + typename _Graph, + typename _Item, + typename _Map> + class MapIterator : public MapIteratorBase<_Graph, _Item> { + + friend class MapConstIterator<_Graph, _Item, _Map>; + + + public: + + /// The iterator base class. + typedef MapIteratorBase<_Graph, _Item> Parent; + + typedef _Item Item; + typedef _Map Map; + typedef _Graph Graph; + + protected: + + typedef typename Parent::ItemIt ItemIt; + + typedef typename ReferenceMapTraits<_Map>::Value MapValue; + typedef typename ReferenceMapTraits<_Map>::Reference MapReference; + + public: + + /// The value type of the iterator. + typedef extended_pair Value; + + /// The reference type of the iterator. + typedef extended_pair Reference; + + /// Default constructor. + MapIterator() {} + + /// Constructor to initalize the iterators returned + /// by the begin() and end(). + MapIterator(Map& _map, const ItemIt& _it) + : Parent(_it), map(&_map) {} + + /// Dereference operator for the iterator. + Reference operator*() { + return Reference(Parent::it, (*map)[Parent::it]); + } + + /// The pointer type of the iterator. + class Pointer { + friend class MapIterator; + protected: + Reference data; + Pointer(const Item& item, MapReference val) + : data(item, val) {} + public: + Reference* operator->() {return &data;} + }; + + /// Arrow operator for the iterator. + Pointer operator->() { + return Pointer(Parent::it, (*map)[Parent::it]); + } + + /// The pre increment operator of the iterator. + MapIterator& operator++() { + Parent::increment(); + return *this; + } + + /// The post increment operator of the iterator. + MapIterator operator++(int) { + MapIterator tmp(*this); + Parent::increment(); + return tmp; + } + + protected: + + Map* map; + + public: + // STL compatibility typedefs. + typedef std::forward_iterator_tag iterator_category; + typedef int difference_type; + typedef Value value_type; + typedef Reference reference; + typedef Pointer pointer; + }; + + /** Compatible iterator with the stl maps' iterators. + * It iterates on pairs of a key and a value. + */ + template < + typename _Graph, + typename _Item, + typename _Map> + class MapConstIterator : public MapIteratorBase<_Graph, _Item> { + + public: + + /// The iterator base class. + typedef MapIteratorBase<_Graph, _Item> Parent; + + typedef _Graph Graph; + typedef _Item Item; + typedef _Map Map; + + protected: + + typedef typename Parent::ItemIt ItemIt; + + typedef typename ReferenceMapTraits<_Map>::Value MapValue; + typedef typename ReferenceMapTraits<_Map>::ConstReference + MapReference; + + public: + + /// The value type of the iterator. + typedef extended_pair Value; + + /// The reference type of the iterator. + typedef extended_pair Reference; + + /// Default constructor. + MapConstIterator() {} + + /// Constructor to initalize the iterators returned + /// by the begin() and end(). + MapConstIterator(const Map& _map, const ItemIt& _it) + : Parent(_it), map(&_map) {} + + /// Dereference operator for the iterator. + Reference operator*() { + return Reference(Parent::it, (*map)[Parent::it]); + } + + /// The pointer type of the iterator. + class Pointer { + friend class MapConstIterator; + protected: + Reference data; + Pointer(const Item& item, MapReference val) + : data(item, val) {} + public: + Reference* operator->() {return &data;} + }; + + /// Arrow operator for the iterator. + Pointer operator->() { + return Pointer(Parent::it, ((*map)[Parent::it])); + } + + /// The pre increment operator of the iterator. + MapConstIterator& operator++() { + Parent::increment(); + return *this; + } + + /// The post increment operator of the iterator. + MapConstIterator operator++(int) { + MapConstIterator tmp(*this); + Parent::increment(); + return tmp; + } + + protected: + const Map* map; + + public: + // STL compatibility typedefs. + typedef std::forward_iterator_tag iterator_category; + typedef int difference_type; + typedef Value value_type; + typedef Reference reference; + typedef Pointer pointer; + }; + + /** The class makes the ItemIt to an stl compatible iterator + * with dereferencing operator. + */ + template < + typename _Graph, + typename _Item> + class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> { + + public: + + /// The iterator base class. + typedef MapIteratorBase<_Graph, _Item> Parent; + + typedef _Graph Graph; + typedef _Item Item; + + protected: + /// The iterator to iterate on the keys. + typedef typename Parent::ItemIt ItemIt; + + public: + + typedef Item Value; + typedef const Item& Reference; + typedef const Item* Pointer; + + /// Default constructor. + MapConstKeyIterator() {} + + /// ItemIt initialized iterator. + MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {} + + /// The pre increment operator of the iterator. + MapConstKeyIterator& operator++() { + Parent::increment(); + return *this; + } + + /// The post increment operator of the iterator. + MapConstKeyIterator operator++(int) { + MapConstKeyIterator tmp(*this); + Parent::increment(); + return tmp; + } + + /// The dereferencing operator of the iterator. + Item operator*() const { + return static_cast(Parent::it); + } + + public: + // STL compatibility typedefs. + typedef std::input_iterator_tag iterator_category; + typedef int difference_type; + typedef Value value_type; + typedef Reference reference; + typedef Pointer pointer; + }; + + template < + typename _Graph, + typename _Item, + typename _Map> + class MapConstValueIterator; + + /** MapValueIterator creates an stl compatible iterator + * for the values. + */ + template < + typename _Graph, + typename _Item, + typename _Map> + class MapValueIterator : public MapIteratorBase<_Graph, _Item> { + + friend class MapConstValueIterator<_Graph, _Item, _Map>; + + public: + + /// The iterator base class. + typedef MapIteratorBase<_Graph, _Item> Parent; + + typedef _Graph Graph; + typedef _Item Item; + typedef _Map Map; + + protected: + + /// The iterator to iterate on the keys. + typedef typename Parent::ItemIt ItemIt; + + /// The value type of the iterator. + typedef typename ReferenceMapTraits::Value MapValue; + /// The reference type of the iterator. + typedef typename ReferenceMapTraits::Reference MapReference; + /// The pointer type of the iterator. + typedef typename ReferenceMapTraits::Pointer MapPointer; + + public: + + typedef MapValue Value; + typedef MapReference Reference; + typedef MapPointer Pointer; + + /// Default constructor. + MapValueIterator() {} + + /// Map and ItemIt initialized iterator. + MapValueIterator(Map& _map, const ItemIt& _it) + : Parent(_it), map(&_map) {} + + + /// The pre increment operator of the iterator. + MapValueIterator& operator++() { + Parent::increment(); + return *this; + } + + /// The post increment operator of the iterator. + MapValueIterator operator++(int) { + MapValueIterator tmp(*this); + Parent::increment(); + return tmp; + } + + /// The dereferencing operator of the iterator. + Reference operator*() const { + return (*map)[Parent::it]; + } + + /// The arrow operator of the iterator. + Pointer operator->() const { + return &(operator*()); + } + + protected: + + Map* map; + + public: + // STL compatibility typedefs. + typedef std::forward_iterator_tag iterator_category; + typedef int difference_type; + typedef Value value_type; + typedef Reference reference; + typedef Pointer pointer; + }; + + /** MapValueIterator creates an stl compatible iterator + * for the values. + */ + template < + typename _Graph, + typename _Item, + typename _Map> + class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> { + + public: + + /// The iterator base class. + typedef MapIteratorBase<_Graph, _Item> Parent; + + typedef _Graph Graph; + typedef _Item Item; + typedef _Map Map; + + protected: + + /// The iterator to iterate on the keys. + typedef typename Parent::ItemIt ItemIt; + + /// The value type of the iterator. + typedef typename ReferenceMapTraits::Value MapValue; + /// The reference type of the iterator. + typedef typename ReferenceMapTraits::ConstReference MapReference; + /// The pointer type of the iterator. + typedef typename ReferenceMapTraits::ConstPointer MapPointer; + + public: + + typedef MapValue Value; + typedef MapReference Reference; + typedef MapPointer Pointer; + + /// Default constructor. + MapConstValueIterator() {} + + /// Map and ItemIt initialized iterator. + MapConstValueIterator(const Map& _map, const ItemIt& _it) + : Parent(_it), map(&_map) {} + + + /// The pre increment operator of the iterator. + MapConstValueIterator& operator++() { + Parent::increment(); + return *this; + } + + /// The post increment operator of the iterator. + MapConstValueIterator operator++(int) { + MapConstValueIterator tmp(*this); + Parent::increment(); + return tmp; + } + + /// The dereferencing operator of the iterator. + Reference operator*() const { + return (*map)[Parent::it]; + } + + /// The arrow operator of the iterator. + Pointer operator->() const { + return &(operator*()); + } + + protected: + + const Map* map; + + public: + // STL compatibility typedefs. + typedef std::forward_iterator_tag iterator_category; + typedef int difference_type; + typedef Value value_type; + typedef Reference reference; + typedef Pointer pointer; + }; + + + /** This class makes from a map an iteratable set + * which contains all the keys of the map. + */ + template + class MapConstKeySet { + + public: + + typedef _Graph Graph; + /// The key type of the iterator. + typedef _Item Item; + /// The iterator to iterate on the keys. + + protected: + + typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt; + + public: + + /// The map initialized const key set. + MapConstKeySet(const Graph& _graph) : graph(&_graph) {} + + /// The const iterator of the set. + typedef MapConstKeyIterator<_Graph, _Item> ConstIterator; + + typedef typename ConstIterator::Value Value; + /// The reference type of the iterator. + typedef typename ConstIterator::Reference ConstReference; + /// The pointer type of the iterator. + typedef typename ConstIterator::Pointer ConstPointer; + + /// It gives back the const iterator pointed to the first element. + ConstIterator begin() const { + return ConstIterator(ItemIt(*graph)); + } + + /// It gives back the const iterator pointed to the first ivalid element. + ConstIterator end() const { + return ConstIterator(ItemIt(INVALID)); + } + + protected: + + const Graph* graph; + + public: + // STL compatibility typedefs. + typedef Value value_type; + typedef ConstIterator const_iterator; + typedef ConstReference const_reference; + typedef ConstPointer const_pointer; + typedef int difference_type; + }; + + /** This class makes from a map an iteratable set + * which contains all the values of the map. + * The values cannot be modified. + */ + template + class MapConstValueSet { + + public: + + typedef _Graph Graph; + typedef _Item Item; + typedef _Map Map; + + protected: + + /// The iterator to iterate on the keys. + typedef typename ItemSetTraits::ItemIt ItemIt; + + public: + + /// The map initialized const value set. + MapConstValueSet(const Graph& _graph, const Map& _map) + : graph(&_graph), map(&_map) {} + + /// The const iterator of the set. + typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator; + + typedef typename ConstIterator::Value Value; + typedef typename ConstIterator::Reference ConstReference; + typedef typename ConstIterator::Pointer ConstPointer; + + /// It gives back the const iterator pointed to the first element. + ConstIterator begin() const { + return ConstIterator(*map, ItemIt(*graph)); + } + + /// It gives back the const iterator pointed to the first invalid element. + ConstIterator end() const { + return ConstIterator(*map, ItemIt(INVALID)); + } + + protected: + + const Map* map; + const Graph * graph; + + public: + // STL compatibility typedefs. + typedef Value value_type; + typedef ConstIterator const_iterator; + typedef ConstReference const_reference; + typedef ConstPointer const_pointer; + typedef int difference_type; + }; + + + /** This class makes from a map an iteratable set + * which contains all the values of the map. + * The values can be modified. + */ + template + class MapValueSet { + + public: + + typedef _Graph Graph; + typedef _Item Item; + typedef _Map Map; + + protected: + + /// The iterator to iterate on the keys. + typedef typename ItemSetTraits::ItemIt ItemIt; + + public: + + /// The map initialized const value set. + MapValueSet(const Graph& _graph, Map& _map) + : map(&_map), graph(&_graph) {} + + /// The const iterator of the set. + typedef MapValueIterator<_Graph, _Item, _Map> Iterator; + /// The const iterator of the set. + typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator; + + typedef typename ConstIterator::Value Value; + typedef typename Iterator::Reference Reference; + typedef typename Iterator::Pointer Pointer; + typedef typename ConstIterator::Reference ConstReference; + typedef typename ConstIterator::Pointer ConstPointer; + + /// It gives back the const iterator pointed to the first element. + ConstIterator begin() const { + return ConstIterator(*map, ItemIt(*graph)); + } + + /// It gives back the const iterator pointed to the first invalid element. + ConstIterator end() const { + return ConstIterator(*map, ItemIt(INVALID)); + } + + /// It gives back the iterator pointed to the first element. + Iterator begin() { + return Iterator(*map, ItemIt(*graph)); + } + + /// It gives back the iterator pointed to the first invalid element. + Iterator end() { + return Iterator(*map, ItemIt(INVALID)); + } + + protected: + + Map* map; + const Graph * graph; + + public: + // STL compatibility typedefs. + typedef Value value_type; + typedef Iterator iterator; + typedef ConstIterator const_iterator; + typedef Reference reference; + typedef ConstReference const_reference; + typedef Pointer pointer; + typedef ConstPointer const_pointer; + typedef int difference_type; + + }; + + /** This class makes from a map an iteratable set + * which contains all the values of the map. + * The values can be modified. + */ + template < + typename _Graph, + typename _Item, + typename _Map + > + class MapSet { + public: + + typedef _Graph Graph; + typedef _Item Item; + typedef _Map Map; + + protected: + + typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt; + + public: + + /// The map initialized value set. + MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {} + + /// The const iterator of the set. + typedef MapIterator<_Graph, _Item, _Map> Iterator; + typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator; + + typedef typename ConstIterator::Value Value; + typedef typename Iterator::Reference Reference; + typedef typename Iterator::Pointer Pointer; + typedef typename ConstIterator::Reference ConstReference; + typedef typename ConstIterator::Pointer ConstPointer; + + + /// It gives back the const iterator pointed to the first element. + ConstIterator begin() const { + return ConstIterator(*map, ItemIt(*graph)); + } + + /// It gives back the const iterator pointed to the first invalid element. + ConstIterator end() const { + return ConstIterator(*map, ItemIt(INVALID)); + } + + /// The iterator of the set. + + /// It gives back the iterator pointed to the first element. + Iterator begin() { + return Iterator(*map, ItemIt(*graph)); + } + + /// It gives back the iterator pointed to the first invalid element. + Iterator end() { + return Iterator(*map, ItemIt(INVALID)); + } + + protected: + + const Graph* graph; + Map* map; + + public: + // STL compatibility typedefs. + typedef Value value_type; + typedef Iterator iterator; + typedef ConstIterator const_iterator; + typedef Reference reference; + typedef ConstReference const_reference; + typedef Pointer pointer; + typedef ConstPointer const_pointer; + typedef int difference_type; + + }; + + template < + typename _Graph, + typename _Item, + typename _Map + > + class ConstMapSet { + + typedef _Graph Graph; + typedef _Map Map; + + const Graph* graph; + const Map* map; + + public: + + typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt; + + + /// The map initialized value set. + ConstMapSet(const Graph& _graph, const Map& _map) + : graph(&_graph), map(&_map) {} + + /// The const iterator of the set. + typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator; + + typedef typename ConstIterator::Value Value; + typedef typename ConstIterator::Reference ConstReference; + typedef typename ConstIterator::Pointer ConstPointer; + + + /// It gives back the const iterator pointed to the first element. + ConstIterator begin() const { + return ConstIterator(*map, ItemIt(*graph)); + } + + /// It gives back the const iterator pointed to the first invalid element. + ConstIterator end() const { + return ConstIterator(*map, ItemIt(INVALID)); + } + + public: + // STL compatibility typedefs. + typedef Value value_type; + typedef ConstIterator const_iterator; + typedef ConstReference const_reference; + typedef ConstPointer const_pointer; + typedef int difference_type; + + }; + + template + class IterableMapExtender : public _Map { + public: + + typedef _Map Parent; + typedef Parent Map; + typedef typename Map::Graph Graph; + typedef typename Map::Key Item; + typedef typename Map::Value Value; + + typedef MapSet MapSet; + + IterableMapExtender() : Parent() {} + + IterableMapExtender(const Graph& graph) : Parent(graph) {} + + IterableMapExtender(const Graph& graph, const Value& value) + : Parent(graph, value) {} + + MapSet mapSet() { + return MapSet(*Parent::getGraph(), *this); + } + + typedef ConstMapSet ConstMapSet; + + ConstMapSet mapSet() const { + return ConstMapSet(*Parent::getGraph(), *this); + } + + typedef MapConstKeySet ConstKeySet; + + ConstKeySet keySet() const { + return ConstKeySet(*Parent::getGraph()); + } + + typedef MapValueSet ValueSet; + + ValueSet valueSet() { + return ValueSet(*Parent::getGraph(), *this); + } + + typedef MapConstValueSet ConstValueSet; + + ConstValueSet valueSet() const { + return ConstValueSet(*Parent::getGraph(), *this); + } + + }; + + /// @} + +} + +#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/bits/undir_graph_extender.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/bits/undir_graph_extender.h Tue Apr 05 12:30:46 2005 +0000 @@ -0,0 +1,278 @@ +/* -*- C++ -*- + * + * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++ + * optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi + * Kutatocsoport (Egervary Combinatorial Optimization Research Group, + * EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_UNDIR_GRAPH_EXTENDER_H +#define LEMON_UNDIR_GRAPH_EXTENDER_H + +#include + +namespace lemon { + + template + class UndirGraphExtender : public _Base { + typedef _Base Parent; + typedef UndirGraphExtender Graph; + + public: + + typedef typename Parent::Edge UndirEdge; + typedef typename Parent::Node Node; + + class Edge : public UndirEdge { + friend class UndirGraphExtender; + + protected: + // FIXME: Marci use opposite logic in his graph wrappers. It would + // be reasonable to syncronize... + bool forward; + + public: + Edge() {} + + /// \brief Directed edge from undirected edge and a direction. + /// + /// This constructor is not a part of the concept interface of + /// undirected graph, so please avoid using it if possible! + Edge(const UndirEdge &ue, bool _forward) : + UndirEdge(ue), forward(_forward) {} + + /// \brief Directed edge from undirected edge and a source node. + /// + /// Constructs a directed edge from undirected edge and a source node. + /// + /// \note You have to specify the graph for this constructor. + Edge(const Graph &g, const UndirEdge &ue, const Node &n) : + UndirEdge(ue) { forward = (g.source(ue) == n); } + + /// Invalid edge constructor + Edge(Invalid i) : UndirEdge(i), forward(true) {} + + bool operator==(const Edge &that) const { + return forward==that.forward && UndirEdge(*this)==UndirEdge(that); + } + bool operator!=(const Edge &that) const { + return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that); + } + bool operator<(const Edge &that) const { + return forward + Node _dirSource(const E &e) const { + return e.forward ? Parent::source(e) : Parent::target(e); + } + + template + Node _dirTarget(const E &e) const { + return e.forward ? Parent::target(e) : Parent::source(e); + } + + public: + /// \todo Shouldn't the "source" of an undirected edge be called "aNode" + /// or something??? + using Parent::source; + + /// Source of the given Edge. + Node source(const Edge &e) const { + return _dirSource(e); + } + + /// \todo Shouldn't the "target" of an undirected edge be called "bNode" + /// or something??? + using Parent::target; + + /// Target of the given Edge. + Node target(const Edge &e) const { + return _dirTarget(e); + } + + /// Returns whether the given directed edge is same orientation as the + /// corresponding undirected edge. + /// + /// \todo reference to the corresponding point of the undirected graph + /// concept. "What does the direction of an undirected edge mean?" + bool forward(const Edge &e) const { return e.forward; } + + Node oppositeNode(const Node &n, const UndirEdge &e) const { + if( n == Parent::source(e)) + return Parent::target(e); + else if( n == Parent::target(e)) + return Parent::source(e); + else + return INVALID; + } + + /// Directed edge from an undirected edge and a source node. + /// + /// Returns a (directed) Edge corresponding to the specified UndirEdge + /// and source Node. + /// + ///\todo Do we need this? + /// + ///\todo Better name... + Edge edgeWithSource(const UndirEdge &ue, const Node &s) const { + return Edge(*this, ue, s); + } + + using Parent::first; + void first(Edge &e) const { + Parent::first(e); + e.forward=true; + } + + using Parent::next; + void next(Edge &e) const { + if( e.forward ) { + e.forward = false; + } + else { + Parent::next(e); + e.forward = true; + } + } + + + protected: + + template + void _dirFirstOut(E &e, const Node &n) const { + Parent::firstIn(e,n); + if( UndirEdge(e) != INVALID ) { + e.forward = false; + } + else { + Parent::firstOut(e,n); + e.forward = true; + } + } + template + void _dirFirstIn(E &e, const Node &n) const { + Parent::firstOut(e,n); + if( UndirEdge(e) != INVALID ) { + e.forward = false; + } + else { + Parent::firstIn(e,n); + e.forward = true; + } + } + + template + void _dirNextOut(E &e) const { + if( ! e.forward ) { + Node n = Parent::target(e); + Parent::nextIn(e); + if( UndirEdge(e) == INVALID ) { + Parent::firstOut(e, n); + e.forward = true; + } + } + else { + Parent::nextOut(e); + } + } + template + void _dirNextIn(E &e) const { + if( ! e.forward ) { + Node n = Parent::source(e); + Parent::nextOut(e); + if( UndirEdge(e) == INVALID ) { + Parent::firstIn(e, n); + e.forward = true; + } + } + else { + Parent::nextIn(e); + } + } + + public: + + void firstOut(Edge &e, const Node &n) const { + _dirFirstOut(e, n); + } + void firstIn(Edge &e, const Node &n) const { + _dirFirstIn(e, n); + } + + void nextOut(Edge &e) const { + _dirNextOut(e); + } + void nextIn(Edge &e) const { + _dirNextIn(e); + } + + // Miscellaneous stuff: + + /// \todo these methods (id, maxEdgeId) should be moved into separate + /// Extender + + // using Parent::id; + // Using "using" is not a good idea, cause it could be that there is + // no "id" in Parent... + + int id(const Node &n) const { + return Parent::id(n); + } + + int id(const UndirEdge &e) const { + return Parent::id(e); + } + + int id(const Edge &e) const { + return 2 * Parent::id(e) + int(e.forward); + } + + + int maxId(Node) const { + return Parent::maxId(Node()); + } + + int maxId(Edge) const { + return 2 * Parent::maxId(typename Parent::Edge()) + 1; + } + int maxId(UndirEdge) const { + return Parent::maxId(typename Parent::Edge()); + } + + + int edgeNum() const { + return 2 * Parent::edgeNum(); + } + int undirEdgeNum() const { + return Parent::edgeNum(); + } + + }; + +} + +#endif // LEMON_UNDIR_GRAPH_EXTENDER_H diff -r 4ea2147274db -r d4acebef7276 src/lemon/bits/vector_map.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/bits/vector_map.h Tue Apr 05 12:30:46 2005 +0000 @@ -0,0 +1,287 @@ +/* -*- C++ -*- + * src/lemon/vector_map.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_VECTOR_MAP_H +#define LEMON_VECTOR_MAP_H + +#include +#include + +#include +#include +#include + +///\ingroup graphmaps +///\file +///\brief Vector based graph maps. + +namespace lemon { + + /// \addtogroup graphmaps + /// @{ + + /// The VectorMap template class is graph map structure what + /// automatically updates the map when a key is added to or erased from + /// the map. This map factory uses the allocators to implement + /// the container functionality. This map factory + /// uses the std::vector to implement the container function. + /// + /// \param Registry The AlterationNotifier that will notify this map. + /// \param IdMap The IdMap type of the graph items. + /// \param Value The value type of the map. + /// + /// \author Balazs Dezso + + + template < + typename _Graph, + typename _Item, + typename _Value + > + class VectorMap : public AlterationNotifier<_Item>::ObserverBase { + public: + + /// The graph type of the map. + typedef _Graph Graph; + /// The key type of the map. + typedef _Item Key; + /// The id map type of the map. + typedef AlterationNotifier<_Item> Registry; + /// The value type of the map. + typedef _Value Value; + + /// The map type. + typedef VectorMap Map; + /// The base class of the map. + typedef typename Registry::ObserverBase Parent; + + private: + + /// The container type of the map. + typedef std::vector Container; + + public: + + /// The reference type of the map; + typedef typename Container::reference Reference; + /// The pointer type of the map; + typedef typename Container::pointer Pointer; + + /// The const value type of the map. + typedef const Value ConstValue; + /// The const reference type of the map; + typedef typename Container::const_reference ConstReference; + /// The pointer type of the map; + typedef typename Container::const_pointer ConstPointer; + + typedef True FullTypeTag; + + /// Constructor to attach the new map into the registry. + + /// It construates a map and attachs it into the registry. + /// It adds all the items of the graph to the map. + + VectorMap(const Graph& _g) : graph(&_g) { + attach(_g.getNotifier(_Item())); + build(); + } + + /// Constructor uses given value to initialize the map. + + /// It construates a map uses a given value to initialize the map. + /// It adds all the items of the graph to the map. + + VectorMap(const Graph& _g, const Value& _v) : graph(&_g) { + attach(_g.getNotifier(_Item())); + container.resize(graph->maxId(_Item()) + 1, _v); + } + + VectorMap(const VectorMap& _copy) : graph(_copy.getGraph()) { + if (_copy.attached()) { + attach(*_copy.getRegistry()); + container = _copy.container; + } + } + + using Parent::attach; + using Parent::detach; + using Parent::attached; + + /** Assign operator to copy a map of the same map type. + */ + VectorMap& operator=(const VectorMap& copy) { + if (© == this) return *this; + + if (graph != copy.graph) { + if (attached()) { + detach(); + } + if (copy.attached()) { + attach(*copy.getRegistry()); + } + } + container = copy.container; + + return *this; + } + + + virtual ~VectorMap() { + if (attached()) { + detach(); + } + } + + const Graph* getGraph() const { + return graph; + } + + /// The subcript operator. + + /// The subscript operator. The map can be subscripted by the + /// actual items of the graph. + + Reference operator[](const Key& key) { + return container[graph->id(key)]; + } + + /// The const subcript operator. + + /// The const subscript operator. The map can be subscripted by the + /// actual items of the graph. + + ConstReference operator[](const Key& key) const { + return container[graph->id(key)]; + } + + + /// The setter function of the map. + + /// It the same as operator[](key) = value expression. + /// + + void set(const Key& key, const Value& value) { + (*this)[key] = value; + } + + /// Adds a new key to the map. + + /// It adds a new key to the map. It called by the observer registry + /// and it overrides the add() member function of the observer base. + + void add(const Key& key) { + int id = graph->id(key); + if (id >= (int)container.size()) { + container.resize(id + 1); + } + } + + /// Erases a key from the map. + + /// Erase a key from the map. It called by the observer registry + /// and it overrides the erase() member function of the observer base. + void erase(const Key&) {} + + /// Buildes the map. + + /// It buildes the map. It called by the observer registry + /// and it overrides the build() member function of the observer base. + + void build() { + container.resize(graph->maxId(_Item()) + 1); + } + + /// Clear the map. + + /// It erase all items from the map. It called by the observer registry + /// and it overrides the clear() member function of the observer base. + void clear() { + container.clear(); + } + + private: + + Container container; + const Graph *graph; + + }; + + + template + class VectorMappableGraphExtender : public _Base { + public: + + typedef VectorMappableGraphExtender<_Base> Graph; + typedef _Base Parent; + + typedef typename Parent::Node Node; + typedef typename Parent::NodeIt NodeIt; + typedef typename Parent::NodeIdMap NodeIdMap; + typedef typename Parent::NodeNotifier NodeObserverRegistry; + + typedef typename Parent::Edge Edge; + typedef typename Parent::EdgeIt EdgeIt; + typedef typename Parent::EdgeIdMap EdgeIdMap; + typedef typename Parent::EdgeNotifier EdgeObserverRegistry; + + + template + class NodeMap : + public IterableMapExtender > { + public: + typedef VectorMappableGraphExtender<_Base> Graph; + + typedef typename Graph::Node Node; + + typedef IterableMapExtender > Parent; + + //typedef typename Parent::Graph Graph; + typedef typename Parent::Value Value; + + NodeMap(const Graph& g) + : Parent(g) {} + NodeMap(const Graph& g, const Value& v) + : Parent(g, v) {} + + }; + + template + class EdgeMap + : public IterableMapExtender > { + public: + typedef VectorMappableGraphExtender<_Base> Graph; + + typedef typename Graph::Edge Edge; + + typedef IterableMapExtender > Parent; + + //typedef typename Parent::Graph Graph; + typedef typename Parent::Value Value; + + EdgeMap(const Graph& g) + : Parent(g) {} + EdgeMap(const Graph& g, const Value& v) + : Parent(g, v) {} + + }; + + }; + + /// @} + +} + +#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/clearable_graph_extender.h --- a/src/lemon/clearable_graph_extender.h Tue Apr 05 09:49:01 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,49 +0,0 @@ -// -*- c++ -*- - -#ifndef LEMON_CLEARABLE_GRAPH_EXTENDER_H -#define LEMON_CLEARABLE_GRAPH_EXTENDER_H - -#include - - -namespace lemon { - - template - class ClearableGraphExtender : public _Base { - public: - - typedef ClearableGraphExtender Graph; - typedef _Base Parent; - typedef typename Parent::Node Node; - typedef typename Parent::Edge Edge; - - void clear() { - Parent::getNotifier(Node()).clear(); - Parent::getNotifier(Edge()).clear(); - Parent::clear(); - } - - }; - - template - class ClearableUndirGraphExtender : public _Base { - public: - - typedef ClearableUndirGraphExtender Graph; - typedef _Base Parent; - typedef typename Parent::Node Node; - typedef typename Parent::UndirEdge UndirEdge; - typedef typename Parent::Edge Edge; - - void clear() { - Parent::getNotifier(Node()).clear(); - Parent::getNotifier(UndirEdge()).clear(); - Parent::getNotifier(Edge()).clear(); - Parent::clear(); - } - - }; - -} - -#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/concept/graph_component.h --- a/src/lemon/concept/graph_component.h Tue Apr 05 09:49:01 2005 +0000 +++ b/src/lemon/concept/graph_component.h Tue Apr 05 12:30:46 2005 +0000 @@ -25,7 +25,7 @@ #include #include -#include +#include namespace lemon { namespace concept { diff -r 4ea2147274db -r d4acebef7276 src/lemon/default_map.h --- a/src/lemon/default_map.h Tue Apr 05 09:49:01 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,230 +0,0 @@ -/* -*- C++ -*- - * src/lemon/default_map.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_DEFAULT_MAP_H -#define LEMON_DEFAULT_MAP_H - - -#include -#include - -///\ingroup graphmaps -///\file -///\brief Graph maps that construct and destruct -///their elements dynamically. - -namespace lemon { - -/// \addtogroup graphmaps -/// @{ - - /** The ArrayMap template class is graph map structure what - * automatically updates the map when a key is added to or erased from - * the map. This map uses the VectorMap if the Value is a primitive - * type and the ArrayMap for the other cases. - * - * The template parameter is the MapRegistry that the maps - * will belong to and the Value. - */ - - - - template - struct DefaultMapSelector { - typedef ArrayMap<_Graph, _Item, _Value> Map; - }; - - // bool - template - struct DefaultMapSelector<_Graph, _Item, bool> { - typedef VectorMap<_Graph, _Item, bool> Map; - }; - - // char - template - struct DefaultMapSelector<_Graph, _Item, char> { - typedef VectorMap<_Graph, _Item, char> Map; - }; - - template - struct DefaultMapSelector<_Graph, _Item, signed char> { - typedef VectorMap<_Graph, _Item, signed char> Map; - }; - - template - struct DefaultMapSelector<_Graph, _Item, unsigned char> { - typedef VectorMap<_Graph, _Item, unsigned char> Map; - }; - - - // int - template - struct DefaultMapSelector<_Graph, _Item, signed int> { - typedef VectorMap<_Graph, _Item, signed int> Map; - }; - - template - struct DefaultMapSelector<_Graph, _Item, unsigned int> { - typedef VectorMap<_Graph, _Item, unsigned int> Map; - }; - - - // short - template - struct DefaultMapSelector<_Graph, _Item, signed short> { - typedef VectorMap<_Graph, _Item, signed short> Map; - }; - - template - struct DefaultMapSelector<_Graph, _Item, unsigned short> { - typedef VectorMap<_Graph, _Item, unsigned short> Map; - }; - - - // long - template - struct DefaultMapSelector<_Graph, _Item, signed long> { - typedef VectorMap<_Graph, _Item, signed long> Map; - }; - - template - struct DefaultMapSelector<_Graph, _Item, unsigned long> { - typedef VectorMap<_Graph, _Item, unsigned long> Map; - }; - - // \todo handling long long type - - - // float - template - struct DefaultMapSelector<_Graph, _Item, float> { - typedef VectorMap<_Graph, _Item, float> Map; - }; - - - // double - template - struct DefaultMapSelector<_Graph, _Item, double> { - typedef VectorMap<_Graph, _Item, double> Map; - }; - - - // long double - template - struct DefaultMapSelector<_Graph, _Item, long double> { - typedef VectorMap<_Graph, _Item, long double> Map; - }; - - - // pointer - template - struct DefaultMapSelector<_Graph, _Item, _Ptr*> { - typedef VectorMap<_Graph, _Item, _Ptr*> Map; - }; - - - - template < - typename _Graph, - typename _Item, - typename _Value> - class DefaultMap - : public DefaultMapSelector<_Graph, _Item, _Value>::Map { - public: - typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent; - typedef DefaultMap<_Graph, _Item, _Value> Map; - - typedef typename Parent::Graph Graph; - typedef typename Parent::Value Value; - - DefaultMap(const Graph& _g) : Parent(_g) {} - DefaultMap(const Graph& _g, const Value& _v) : Parent(_g, _v) {} - }; - - - - template - class DefaultMappableGraphExtender : public _Base { - public: - - typedef DefaultMappableGraphExtender<_Base> Graph; - typedef _Base Parent; - - typedef typename Parent::Node Node; - typedef typename Parent::NodeIt NodeIt; - - typedef typename Parent::Edge Edge; - typedef typename Parent::EdgeIt EdgeIt; - - - template - class NodeMap - : public IterableMapExtender > { - public: - typedef DefaultMappableGraphExtender Graph; - typedef IterableMapExtender > Parent; - - NodeMap(const Graph& _g) - : Parent(_g) {} - NodeMap(const Graph& _g, const _Value& _v) - : Parent(_g, _v) {} - }; - - template - class EdgeMap - : public IterableMapExtender > { - public: - typedef DefaultMappableGraphExtender Graph; - typedef IterableMapExtender > Parent; - - EdgeMap(const Graph& _g) - : Parent(_g) {} - EdgeMap(const Graph& _g, const _Value& _v) - : Parent(_g, _v) {} - }; - - }; - - template - class MappableUndirGraphExtender : - public DefaultMappableGraphExtender<_Base> { - public: - - typedef MappableUndirGraphExtender Graph; - typedef DefaultMappableGraphExtender<_Base> Parent; - - typedef typename Parent::UndirEdge UndirEdge; - - template - class UndirEdgeMap - : public IterableMapExtender > { - public: - typedef MappableUndirGraphExtender Graph; - typedef IterableMapExtender< - DefaultMap > Parent; - - UndirEdgeMap(const Graph& _g) - : Parent(_g) {} - UndirEdgeMap(const Graph& _g, const _Value& _v) - : Parent(_g, _v) {} - }; - - - }; - -} - -#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/erasable_graph_extender.h --- a/src/lemon/erasable_graph_extender.h Tue Apr 05 09:49:01 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,80 +0,0 @@ -// -*- c++ -*- - -#ifndef LEMON_ERASABLE_GRAPH_EXTENDER_H -#define LEMON_ERASABLE_GRAPH_EXTENDER_H - -#include - - -namespace lemon { - - template - class ErasableGraphExtender : public _Base { - public: - - typedef ErasableGraphExtender Graph; - typedef _Base Parent; - - typedef typename Parent::Node Node; - typedef typename Parent::Edge Edge; - - void erase(const Node& node) { - Edge edge; - Parent::firstOut(edge, node); - while (edge != INVALID ) { - erase(edge); - Parent::firstOut(edge, node); - } - - Parent::firstIn(edge, node); - while (edge != INVALID ) { - erase(edge); - Parent::firstIn(edge, node); - } - - Parent::getNotifier(Node()).erase(node); - Parent::erase(node); - } - - void erase(const Edge& edge) { - Parent::getNotifier(Edge()).erase(edge); - Parent::erase(edge); - } - - }; - - template - class ErasableUndirGraphExtender : public _Base { - public: - - typedef ErasableUndirGraphExtender Graph; - typedef _Base Parent; - - typedef typename Parent::Node Node; - typedef typename Parent::UndirEdge UndirEdge; - typedef typename Parent::Edge Edge; - - void erase(const Node& node) { - Edge edge; - Parent::firstOut(edge, node); - while (edge != INVALID ) { - erase(edge); - Parent::firstOut(edge, node); - } - - Parent::getNotifier(Node()).erase(node); - Parent::erase(node); - } - - void erase(const UndirEdge& uedge) { - Parent::getNotifier(Edge()).erase(Edge(uedge,true)); - Parent::getNotifier(Edge()).erase(Edge(uedge,false)); - Parent::getNotifier(UndirEdge()).erase(uedge); - Parent::erase(uedge); - } - - }; - -} - -#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/extendable_graph_extender.h --- a/src/lemon/extendable_graph_extender.h Tue Apr 05 09:49:01 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,65 +0,0 @@ -// -*- c++ -*- - -#ifndef LEMON_EXTENDABLE_GRAPH_EXTENDER_H -#define LEMON_EXTENDABLE_GRAPH_EXTENDER_H - -namespace lemon { - - template - class ExtendableGraphExtender : public _Base { - public: - - typedef ExtendableGraphExtender Graph; - typedef _Base Parent; - - typedef typename Parent::Node Node; - typedef typename Parent::Edge Edge; - - Node addNode() { - Node node = Parent::addNode(); - Parent::getNotifier(Node()).add(node); - return node; - } - - Edge addEdge(const Node& from, const Node& to) { - Edge edge = Parent::addEdge(from, to); - Parent::getNotifier(Edge()).add(edge); - return edge; - } - - }; - - template - class ExtendableUndirGraphExtender : public _Base { - public: - - typedef ExtendableUndirGraphExtender Graph; - typedef _Base Parent; - - typedef typename Parent::Node Node; - typedef typename Parent::Edge Edge; - typedef typename Parent::UndirEdge UndirEdge; - - Node addNode() { - Node node = Parent::addNode(); - Parent::getNotifier(Node()).add(node); - return node; - } - - UndirEdge addEdge(const Node& from, const Node& to) { - UndirEdge uedge = Parent::addEdge(from, to); - Parent::getNotifier(UndirEdge()).add(uedge); - - Edge edge_forward(uedge, true); - Edge edge_backward(uedge, false); - Parent::getNotifier(Edge()).add(edge_forward); - Parent::getNotifier(Edge()).add(edge_backward); - - return uedge; - } - - }; - -} - -#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/extended_pair.h --- a/src/lemon/extended_pair.h Tue Apr 05 09:49:01 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,80 +0,0 @@ -/* -*- C++ -*- - * src/lemon/extended_pair.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_EXTENDED_PAIR_H -#define LEMON_EXTENDED_PAIR_H - -template -struct extended_pair { - typedef T1 first_type; - typedef T2 second_type; - - extended_pair() : first(), second() {} - - extended_pair(A1 f, A2 s) : first(f), second(s) {} - - template - extended_pair(const Pair& pair) : first(pair.first), second(pair.second) {} - - T1 first; - T2 second; -}; - -template -bool operator==(const extended_pair& left, - const extended_pair& right) { - return left.first == right.first && left.second == right.second; -} - -template -bool operator!=(const extended_pair& left, - const extended_pair& right) { - return !(left == right); -} - -template -bool operator<(const extended_pair& left, - const extended_pair& right) { - return left.first < right.first || - (!(right.first -bool operator>(const extended_pair& left, - const extended_pair& right) { - return right < left; -} - -template -bool operator<=(const extended_pair& left, - const extended_pair& right) { - return !(right > left); -} - -template -bool operator>=(const extended_pair& left, - const extended_pair& right) { - return !(right < left); -} - - -#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/full_graph.h --- a/src/lemon/full_graph.h Tue Apr 05 09:49:01 2005 +0000 +++ b/src/lemon/full_graph.h Tue Apr 05 12:30:46 2005 +0000 @@ -20,9 +20,9 @@ #include -#include -#include -#include +#include +#include +#include #include #include diff -r 4ea2147274db -r d4acebef7276 src/lemon/graph_wrapper.h --- a/src/lemon/graph_wrapper.h Tue Apr 05 09:49:01 2005 +0000 +++ b/src/lemon/graph_wrapper.h Tue Apr 05 12:30:46 2005 +0000 @@ -27,7 +27,7 @@ #include #include -#include +#include #include namespace lemon { diff -r 4ea2147274db -r d4acebef7276 src/lemon/iterable_graph_extender.h --- a/src/lemon/iterable_graph_extender.h Tue Apr 05 09:49:01 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,250 +0,0 @@ -// -*- c++ -*- -#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H -#define LEMON_ITERABLE_GRAPH_EXTENDER_H - -#include - -namespace lemon { - - template - class IterableGraphExtender : public _Base { - public: - - typedef _Base Parent; - typedef IterableGraphExtender<_Base> Graph; - - typedef typename Parent::Node Node; - typedef typename Parent::Edge Edge; - - - class NodeIt : public Node { - const Graph* graph; - public: - - NodeIt() {} - - NodeIt(Invalid i) : Node(i) { } - - explicit NodeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); - } - - NodeIt(const Graph& _graph, const Node& node) - : Node(node), graph(&_graph) {} - - NodeIt& operator++() { - graph->next(*this); - return *this; - } - - }; - - - class EdgeIt : public Edge { - const Graph* graph; - public: - - EdgeIt() { } - - EdgeIt(Invalid i) : Edge(i) { } - - explicit EdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); - } - - EdgeIt(const Graph& _graph, const Edge& e) : - Edge(e), graph(&_graph) { } - - EdgeIt& operator++() { - graph->next(*this); - return *this; - } - - }; - - - class OutEdgeIt : public Edge { - const Graph* graph; - public: - - OutEdgeIt() { } - - OutEdgeIt(Invalid i) : Edge(i) { } - - OutEdgeIt(const Graph& _graph, const Node& node) - : graph(&_graph) { - _graph.firstOut(*this, node); - } - - OutEdgeIt(const Graph& _graph, const Edge& edge) - : Edge(edge), graph(&_graph) {} - - OutEdgeIt& operator++() { - graph->nextOut(*this); - return *this; - } - - }; - - - class InEdgeIt : public Edge { - const Graph* graph; - public: - - InEdgeIt() { } - - InEdgeIt(Invalid i) : Edge(i) { } - - InEdgeIt(const Graph& _graph, const Node& node) - : graph(&_graph) { - _graph.firstIn(*this, node); - } - - InEdgeIt(const Graph& _graph, const Edge& edge) : - Edge(edge), graph(&_graph) {} - - InEdgeIt& operator++() { - graph->nextIn(*this); - return *this; - } - - }; - - /// Base node of the iterator - /// - /// Returns the base node (ie. the source in this case) of the iterator - /// - /// \todo Document in the concept! - Node baseNode(const OutEdgeIt &e) const { - return source(e); - } - /// Running node of the iterator - /// - /// Returns the running node (ie. the target in this case) of the - /// iterator - /// - /// \todo Document in the concept! - Node runningNode(const OutEdgeIt &e) const { - return target(e); - } - - /// Base node of the iterator - /// - /// Returns the base node (ie. the target in this case) of the iterator - /// - /// \todo Document in the concept! - Node baseNode(const InEdgeIt &e) const { - return target(e); - } - /// Running node of the iterator - /// - /// Returns the running node (ie. the source in this case) of the - /// iterator - /// - /// \todo Document in the concept! - Node runningNode(const InEdgeIt &e) const { - return source(e); - } - - using Parent::first; - - private: - - // /// \todo When (and if) we change the iterators concept to use operator*, - // /// then the following shadowed methods will become superfluous. - // /// But for now these are important safety measures. - - // void first(NodeIt &) const; - // void first(EdgeIt &) const; - // void first(OutEdgeIt &) const; - // void first(InEdgeIt &) const; - - }; - - - - - - - template - class IterableUndirGraphExtender : public IterableGraphExtender<_Base> { - public: - - typedef IterableGraphExtender<_Base> Parent; - typedef IterableUndirGraphExtender<_Base> Graph; - typedef typename Parent::Node Node; - - typedef typename Parent::UndirEdge UndirEdge; - - class UndirEdgeIt : public Parent::UndirEdge { - const Graph* graph; - public: - - UndirEdgeIt() { } - - UndirEdgeIt(Invalid i) : UndirEdge(i) { } - - explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); - } - - UndirEdgeIt(const Graph& _graph, const UndirEdge& e) : - UndirEdge(e), graph(&_graph) { } - - UndirEdgeIt& operator++() { - graph->next(*this); - return *this; - } - - }; - - class IncEdgeIt : public Parent::UndirEdge { - const Graph* graph; - bool forward; - friend class IterableUndirGraphExtender; - template - friend class UndirGraphExtender; - public: - - IncEdgeIt() { } - - IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { } - - IncEdgeIt(const Graph& _graph, const Node &n) - : graph(&_graph) - { - _graph._dirFirstOut(*this, n); - } - - IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n) - : graph(&_graph), UndirEdge(ue) - { - forward = (_graph.source(ue) == n); - } - - IncEdgeIt& operator++() { - graph->_dirNextOut(*this); - return *this; - } - }; - - using Parent::baseNode; - using Parent::runningNode; - - /// Base node of the iterator - /// - /// Returns the base node of the iterator - Node baseNode(const IncEdgeIt &e) const { - return _dirSource(e); - } - /// Running node of the iterator - /// - /// Returns the running node of the iterator - Node runningNode(const IncEdgeIt &e) const { - return _dirTarget(e); - } - - }; -} - -#endif // LEMON_GRAPH_EXTENDER_H diff -r 4ea2147274db -r d4acebef7276 src/lemon/list_graph.h --- a/src/lemon/list_graph.h Tue Apr 05 09:49:01 2005 +0000 +++ b/src/lemon/list_graph.h Tue Apr 05 12:30:46 2005 +0000 @@ -21,14 +21,14 @@ ///\file ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes. -#include -#include -#include -#include -#include -#include +#include +#include +#include +#include +#include +#include -#include +#include #include diff -r 4ea2147274db -r d4acebef7276 src/lemon/map_iterator.h --- a/src/lemon/map_iterator.h Tue Apr 05 09:49:01 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,855 +0,0 @@ -/* -*- C++ -*- - * src/lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_MAP_ITERATOR_H -#define LEMON_MAP_ITERATOR_H - -#include - -#include -#include - -///\ingroup graphmaps -///\file -///\brief Iterators on the maps. - -namespace lemon { - - /// \addtogroup graphmaps - /// @{ - - /** The base class all of the map iterators. - * The class defines the typedefs of the iterators, - * simple step functions and equality operators. - */ - - template < - typename _Graph, - typename _Item> - class MapIteratorBase { - - protected: - - /// The key type of the iterator. - typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt; - - ItemIt it; - - /// Default constructor. - MapIteratorBase() {} - - /// ItemIt initialized MapIteratorBase constructor. - MapIteratorBase(const ItemIt _it) : it(_it) {} - - public: - - /// Stepping forward in the map. - void increment() { - ++it; - } - - /// The equality operator of the map. - bool operator==(const MapIteratorBase& _it) const { - return _it.it == it; - } - - /// The not-equality operator of the map. - bool operator!=(const MapIteratorBase& _it) const { - return !(*this == _it); - } - }; - - - template < - typename _Graph, - typename _Item, - typename _Map> - class MapConstIterator; - - /** Compatible iterator with the stl maps' iterators. - * It iterates on pairs of a key and a value. - */ - template < - typename _Graph, - typename _Item, - typename _Map> - class MapIterator : public MapIteratorBase<_Graph, _Item> { - - friend class MapConstIterator<_Graph, _Item, _Map>; - - - public: - - /// The iterator base class. - typedef MapIteratorBase<_Graph, _Item> Parent; - - typedef _Item Item; - typedef _Map Map; - typedef _Graph Graph; - - protected: - - typedef typename Parent::ItemIt ItemIt; - - typedef typename ReferenceMapTraits<_Map>::Value MapValue; - typedef typename ReferenceMapTraits<_Map>::Reference MapReference; - - public: - - /// The value type of the iterator. - typedef extended_pair Value; - - /// The reference type of the iterator. - typedef extended_pair Reference; - - /// Default constructor. - MapIterator() {} - - /// Constructor to initalize the iterators returned - /// by the begin() and end(). - MapIterator(Map& _map, const ItemIt& _it) - : Parent(_it), map(&_map) {} - - /// Dereference operator for the iterator. - Reference operator*() { - return Reference(Parent::it, (*map)[Parent::it]); - } - - /// The pointer type of the iterator. - class Pointer { - friend class MapIterator; - protected: - Reference data; - Pointer(const Item& item, MapReference val) - : data(item, val) {} - public: - Reference* operator->() {return &data;} - }; - - /// Arrow operator for the iterator. - Pointer operator->() { - return Pointer(Parent::it, (*map)[Parent::it]); - } - - /// The pre increment operator of the iterator. - MapIterator& operator++() { - Parent::increment(); - return *this; - } - - /// The post increment operator of the iterator. - MapIterator operator++(int) { - MapIterator tmp(*this); - Parent::increment(); - return tmp; - } - - protected: - - Map* map; - - public: - // STL compatibility typedefs. - typedef std::forward_iterator_tag iterator_category; - typedef int difference_type; - typedef Value value_type; - typedef Reference reference; - typedef Pointer pointer; - }; - - /** Compatible iterator with the stl maps' iterators. - * It iterates on pairs of a key and a value. - */ - template < - typename _Graph, - typename _Item, - typename _Map> - class MapConstIterator : public MapIteratorBase<_Graph, _Item> { - - public: - - /// The iterator base class. - typedef MapIteratorBase<_Graph, _Item> Parent; - - typedef _Graph Graph; - typedef _Item Item; - typedef _Map Map; - - protected: - - typedef typename Parent::ItemIt ItemIt; - - typedef typename ReferenceMapTraits<_Map>::Value MapValue; - typedef typename ReferenceMapTraits<_Map>::ConstReference - MapReference; - - public: - - /// The value type of the iterator. - typedef extended_pair Value; - - /// The reference type of the iterator. - typedef extended_pair Reference; - - /// Default constructor. - MapConstIterator() {} - - /// Constructor to initalize the iterators returned - /// by the begin() and end(). - MapConstIterator(const Map& _map, const ItemIt& _it) - : Parent(_it), map(&_map) {} - - /// Dereference operator for the iterator. - Reference operator*() { - return Reference(Parent::it, (*map)[Parent::it]); - } - - /// The pointer type of the iterator. - class Pointer { - friend class MapConstIterator; - protected: - Reference data; - Pointer(const Item& item, MapReference val) - : data(item, val) {} - public: - Reference* operator->() {return &data;} - }; - - /// Arrow operator for the iterator. - Pointer operator->() { - return Pointer(Parent::it, ((*map)[Parent::it])); - } - - /// The pre increment operator of the iterator. - MapConstIterator& operator++() { - Parent::increment(); - return *this; - } - - /// The post increment operator of the iterator. - MapConstIterator operator++(int) { - MapConstIterator tmp(*this); - Parent::increment(); - return tmp; - } - - protected: - const Map* map; - - public: - // STL compatibility typedefs. - typedef std::forward_iterator_tag iterator_category; - typedef int difference_type; - typedef Value value_type; - typedef Reference reference; - typedef Pointer pointer; - }; - - /** The class makes the ItemIt to an stl compatible iterator - * with dereferencing operator. - */ - template < - typename _Graph, - typename _Item> - class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> { - - public: - - /// The iterator base class. - typedef MapIteratorBase<_Graph, _Item> Parent; - - typedef _Graph Graph; - typedef _Item Item; - - protected: - /// The iterator to iterate on the keys. - typedef typename Parent::ItemIt ItemIt; - - public: - - typedef Item Value; - typedef const Item& Reference; - typedef const Item* Pointer; - - /// Default constructor. - MapConstKeyIterator() {} - - /// ItemIt initialized iterator. - MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {} - - /// The pre increment operator of the iterator. - MapConstKeyIterator& operator++() { - Parent::increment(); - return *this; - } - - /// The post increment operator of the iterator. - MapConstKeyIterator operator++(int) { - MapConstKeyIterator tmp(*this); - Parent::increment(); - return tmp; - } - - /// The dereferencing operator of the iterator. - Item operator*() const { - return static_cast(Parent::it); - } - - public: - // STL compatibility typedefs. - typedef std::input_iterator_tag iterator_category; - typedef int difference_type; - typedef Value value_type; - typedef Reference reference; - typedef Pointer pointer; - }; - - template < - typename _Graph, - typename _Item, - typename _Map> - class MapConstValueIterator; - - /** MapValueIterator creates an stl compatible iterator - * for the values. - */ - template < - typename _Graph, - typename _Item, - typename _Map> - class MapValueIterator : public MapIteratorBase<_Graph, _Item> { - - friend class MapConstValueIterator<_Graph, _Item, _Map>; - - public: - - /// The iterator base class. - typedef MapIteratorBase<_Graph, _Item> Parent; - - typedef _Graph Graph; - typedef _Item Item; - typedef _Map Map; - - protected: - - /// The iterator to iterate on the keys. - typedef typename Parent::ItemIt ItemIt; - - /// The value type of the iterator. - typedef typename ReferenceMapTraits::Value MapValue; - /// The reference type of the iterator. - typedef typename ReferenceMapTraits::Reference MapReference; - /// The pointer type of the iterator. - typedef typename ReferenceMapTraits::Pointer MapPointer; - - public: - - typedef MapValue Value; - typedef MapReference Reference; - typedef MapPointer Pointer; - - /// Default constructor. - MapValueIterator() {} - - /// Map and ItemIt initialized iterator. - MapValueIterator(Map& _map, const ItemIt& _it) - : Parent(_it), map(&_map) {} - - - /// The pre increment operator of the iterator. - MapValueIterator& operator++() { - Parent::increment(); - return *this; - } - - /// The post increment operator of the iterator. - MapValueIterator operator++(int) { - MapValueIterator tmp(*this); - Parent::increment(); - return tmp; - } - - /// The dereferencing operator of the iterator. - Reference operator*() const { - return (*map)[Parent::it]; - } - - /// The arrow operator of the iterator. - Pointer operator->() const { - return &(operator*()); - } - - protected: - - Map* map; - - public: - // STL compatibility typedefs. - typedef std::forward_iterator_tag iterator_category; - typedef int difference_type; - typedef Value value_type; - typedef Reference reference; - typedef Pointer pointer; - }; - - /** MapValueIterator creates an stl compatible iterator - * for the values. - */ - template < - typename _Graph, - typename _Item, - typename _Map> - class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> { - - public: - - /// The iterator base class. - typedef MapIteratorBase<_Graph, _Item> Parent; - - typedef _Graph Graph; - typedef _Item Item; - typedef _Map Map; - - protected: - - /// The iterator to iterate on the keys. - typedef typename Parent::ItemIt ItemIt; - - /// The value type of the iterator. - typedef typename ReferenceMapTraits::Value MapValue; - /// The reference type of the iterator. - typedef typename ReferenceMapTraits::ConstReference MapReference; - /// The pointer type of the iterator. - typedef typename ReferenceMapTraits::ConstPointer MapPointer; - - public: - - typedef MapValue Value; - typedef MapReference Reference; - typedef MapPointer Pointer; - - /// Default constructor. - MapConstValueIterator() {} - - /// Map and ItemIt initialized iterator. - MapConstValueIterator(const Map& _map, const ItemIt& _it) - : Parent(_it), map(&_map) {} - - - /// The pre increment operator of the iterator. - MapConstValueIterator& operator++() { - Parent::increment(); - return *this; - } - - /// The post increment operator of the iterator. - MapConstValueIterator operator++(int) { - MapConstValueIterator tmp(*this); - Parent::increment(); - return tmp; - } - - /// The dereferencing operator of the iterator. - Reference operator*() const { - return (*map)[Parent::it]; - } - - /// The arrow operator of the iterator. - Pointer operator->() const { - return &(operator*()); - } - - protected: - - const Map* map; - - public: - // STL compatibility typedefs. - typedef std::forward_iterator_tag iterator_category; - typedef int difference_type; - typedef Value value_type; - typedef Reference reference; - typedef Pointer pointer; - }; - - - /** This class makes from a map an iteratable set - * which contains all the keys of the map. - */ - template - class MapConstKeySet { - - public: - - typedef _Graph Graph; - /// The key type of the iterator. - typedef _Item Item; - /// The iterator to iterate on the keys. - - protected: - - typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt; - - public: - - /// The map initialized const key set. - MapConstKeySet(const Graph& _graph) : graph(&_graph) {} - - /// The const iterator of the set. - typedef MapConstKeyIterator<_Graph, _Item> ConstIterator; - - typedef typename ConstIterator::Value Value; - /// The reference type of the iterator. - typedef typename ConstIterator::Reference ConstReference; - /// The pointer type of the iterator. - typedef typename ConstIterator::Pointer ConstPointer; - - /// It gives back the const iterator pointed to the first element. - ConstIterator begin() const { - return ConstIterator(ItemIt(*graph)); - } - - /// It gives back the const iterator pointed to the first ivalid element. - ConstIterator end() const { - return ConstIterator(ItemIt(INVALID)); - } - - protected: - - const Graph* graph; - - public: - // STL compatibility typedefs. - typedef Value value_type; - typedef ConstIterator const_iterator; - typedef ConstReference const_reference; - typedef ConstPointer const_pointer; - typedef int difference_type; - }; - - /** This class makes from a map an iteratable set - * which contains all the values of the map. - * The values cannot be modified. - */ - template - class MapConstValueSet { - - public: - - typedef _Graph Graph; - typedef _Item Item; - typedef _Map Map; - - protected: - - /// The iterator to iterate on the keys. - typedef typename ItemSetTraits::ItemIt ItemIt; - - public: - - /// The map initialized const value set. - MapConstValueSet(const Graph& _graph, const Map& _map) - : graph(&_graph), map(&_map) {} - - /// The const iterator of the set. - typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator; - - typedef typename ConstIterator::Value Value; - typedef typename ConstIterator::Reference ConstReference; - typedef typename ConstIterator::Pointer ConstPointer; - - /// It gives back the const iterator pointed to the first element. - ConstIterator begin() const { - return ConstIterator(*map, ItemIt(*graph)); - } - - /// It gives back the const iterator pointed to the first invalid element. - ConstIterator end() const { - return ConstIterator(*map, ItemIt(INVALID)); - } - - protected: - - const Map* map; - const Graph * graph; - - public: - // STL compatibility typedefs. - typedef Value value_type; - typedef ConstIterator const_iterator; - typedef ConstReference const_reference; - typedef ConstPointer const_pointer; - typedef int difference_type; - }; - - - /** This class makes from a map an iteratable set - * which contains all the values of the map. - * The values can be modified. - */ - template - class MapValueSet { - - public: - - typedef _Graph Graph; - typedef _Item Item; - typedef _Map Map; - - protected: - - /// The iterator to iterate on the keys. - typedef typename ItemSetTraits::ItemIt ItemIt; - - public: - - /// The map initialized const value set. - MapValueSet(const Graph& _graph, Map& _map) - : map(&_map), graph(&_graph) {} - - /// The const iterator of the set. - typedef MapValueIterator<_Graph, _Item, _Map> Iterator; - /// The const iterator of the set. - typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator; - - typedef typename ConstIterator::Value Value; - typedef typename Iterator::Reference Reference; - typedef typename Iterator::Pointer Pointer; - typedef typename ConstIterator::Reference ConstReference; - typedef typename ConstIterator::Pointer ConstPointer; - - /// It gives back the const iterator pointed to the first element. - ConstIterator begin() const { - return ConstIterator(*map, ItemIt(*graph)); - } - - /// It gives back the const iterator pointed to the first invalid element. - ConstIterator end() const { - return ConstIterator(*map, ItemIt(INVALID)); - } - - /// It gives back the iterator pointed to the first element. - Iterator begin() { - return Iterator(*map, ItemIt(*graph)); - } - - /// It gives back the iterator pointed to the first invalid element. - Iterator end() { - return Iterator(*map, ItemIt(INVALID)); - } - - protected: - - Map* map; - const Graph * graph; - - public: - // STL compatibility typedefs. - typedef Value value_type; - typedef Iterator iterator; - typedef ConstIterator const_iterator; - typedef Reference reference; - typedef ConstReference const_reference; - typedef Pointer pointer; - typedef ConstPointer const_pointer; - typedef int difference_type; - - }; - - /** This class makes from a map an iteratable set - * which contains all the values of the map. - * The values can be modified. - */ - template < - typename _Graph, - typename _Item, - typename _Map - > - class MapSet { - public: - - typedef _Graph Graph; - typedef _Item Item; - typedef _Map Map; - - protected: - - typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt; - - public: - - /// The map initialized value set. - MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {} - - /// The const iterator of the set. - typedef MapIterator<_Graph, _Item, _Map> Iterator; - typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator; - - typedef typename ConstIterator::Value Value; - typedef typename Iterator::Reference Reference; - typedef typename Iterator::Pointer Pointer; - typedef typename ConstIterator::Reference ConstReference; - typedef typename ConstIterator::Pointer ConstPointer; - - - /// It gives back the const iterator pointed to the first element. - ConstIterator begin() const { - return ConstIterator(*map, ItemIt(*graph)); - } - - /// It gives back the const iterator pointed to the first invalid element. - ConstIterator end() const { - return ConstIterator(*map, ItemIt(INVALID)); - } - - /// The iterator of the set. - - /// It gives back the iterator pointed to the first element. - Iterator begin() { - return Iterator(*map, ItemIt(*graph)); - } - - /// It gives back the iterator pointed to the first invalid element. - Iterator end() { - return Iterator(*map, ItemIt(INVALID)); - } - - protected: - - const Graph* graph; - Map* map; - - public: - // STL compatibility typedefs. - typedef Value value_type; - typedef Iterator iterator; - typedef ConstIterator const_iterator; - typedef Reference reference; - typedef ConstReference const_reference; - typedef Pointer pointer; - typedef ConstPointer const_pointer; - typedef int difference_type; - - }; - - template < - typename _Graph, - typename _Item, - typename _Map - > - class ConstMapSet { - - typedef _Graph Graph; - typedef _Map Map; - - const Graph* graph; - const Map* map; - - public: - - typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt; - - - /// The map initialized value set. - ConstMapSet(const Graph& _graph, const Map& _map) - : graph(&_graph), map(&_map) {} - - /// The const iterator of the set. - typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator; - - typedef typename ConstIterator::Value Value; - typedef typename ConstIterator::Reference ConstReference; - typedef typename ConstIterator::Pointer ConstPointer; - - - /// It gives back the const iterator pointed to the first element. - ConstIterator begin() const { - return ConstIterator(*map, ItemIt(*graph)); - } - - /// It gives back the const iterator pointed to the first invalid element. - ConstIterator end() const { - return ConstIterator(*map, ItemIt(INVALID)); - } - - public: - // STL compatibility typedefs. - typedef Value value_type; - typedef ConstIterator const_iterator; - typedef ConstReference const_reference; - typedef ConstPointer const_pointer; - typedef int difference_type; - - }; - - template - class IterableMapExtender : public _Map { - public: - - typedef _Map Parent; - typedef Parent Map; - typedef typename Map::Graph Graph; - typedef typename Map::Key Item; - typedef typename Map::Value Value; - - typedef MapSet MapSet; - - IterableMapExtender() : Parent() {} - - IterableMapExtender(const Graph& graph) : Parent(graph) {} - - IterableMapExtender(const Graph& graph, const Value& value) - : Parent(graph, value) {} - - MapSet mapSet() { - return MapSet(*Parent::getGraph(), *this); - } - - typedef ConstMapSet ConstMapSet; - - ConstMapSet mapSet() const { - return ConstMapSet(*Parent::getGraph(), *this); - } - - typedef MapConstKeySet ConstKeySet; - - ConstKeySet keySet() const { - return ConstKeySet(*Parent::getGraph()); - } - - typedef MapValueSet ValueSet; - - ValueSet valueSet() { - return ValueSet(*Parent::getGraph(), *this); - } - - typedef MapConstValueSet ConstValueSet; - - ConstValueSet valueSet() const { - return ConstValueSet(*Parent::getGraph(), *this); - } - - }; - - /// @} - -} - -#endif diff -r 4ea2147274db -r d4acebef7276 src/lemon/smart_graph.h --- a/src/lemon/smart_graph.h Tue Apr 05 09:49:01 2005 +0000 +++ b/src/lemon/smart_graph.h Tue Apr 05 12:30:46 2005 +0000 @@ -25,13 +25,13 @@ #include -#include -#include -#include -#include -#include +#include +#include +#include +#include +#include -#include +#include #include diff -r 4ea2147274db -r d4acebef7276 src/lemon/undir_graph_extender.h --- a/src/lemon/undir_graph_extender.h Tue Apr 05 09:49:01 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,278 +0,0 @@ -/* -*- C++ -*- - * - * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++ - * optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi - * Kutatocsoport (Egervary Combinatorial Optimization Research Group, - * EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_UNDIR_GRAPH_EXTENDER_H -#define LEMON_UNDIR_GRAPH_EXTENDER_H - -#include - -namespace lemon { - - template - class UndirGraphExtender : public _Base { - typedef _Base Parent; - typedef UndirGraphExtender Graph; - - public: - - typedef typename Parent::Edge UndirEdge; - typedef typename Parent::Node Node; - - class Edge : public UndirEdge { - friend class UndirGraphExtender; - - protected: - // FIXME: Marci use opposite logic in his graph wrappers. It would - // be reasonable to syncronize... - bool forward; - - public: - Edge() {} - - /// \brief Directed edge from undirected edge and a direction. - /// - /// This constructor is not a part of the concept interface of - /// undirected graph, so please avoid using it if possible! - Edge(const UndirEdge &ue, bool _forward) : - UndirEdge(ue), forward(_forward) {} - - /// \brief Directed edge from undirected edge and a source node. - /// - /// Constructs a directed edge from undirected edge and a source node. - /// - /// \note You have to specify the graph for this constructor. - Edge(const Graph &g, const UndirEdge &ue, const Node &n) : - UndirEdge(ue) { forward = (g.source(ue) == n); } - - /// Invalid edge constructor - Edge(Invalid i) : UndirEdge(i), forward(true) {} - - bool operator==(const Edge &that) const { - return forward==that.forward && UndirEdge(*this)==UndirEdge(that); - } - bool operator!=(const Edge &that) const { - return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that); - } - bool operator<(const Edge &that) const { - return forward - Node _dirSource(const E &e) const { - return e.forward ? Parent::source(e) : Parent::target(e); - } - - template - Node _dirTarget(const E &e) const { - return e.forward ? Parent::target(e) : Parent::source(e); - } - - public: - /// \todo Shouldn't the "source" of an undirected edge be called "aNode" - /// or something??? - using Parent::source; - - /// Source of the given Edge. - Node source(const Edge &e) const { - return _dirSource(e); - } - - /// \todo Shouldn't the "target" of an undirected edge be called "bNode" - /// or something??? - using Parent::target; - - /// Target of the given Edge. - Node target(const Edge &e) const { - return _dirTarget(e); - } - - /// Returns whether the given directed edge is same orientation as the - /// corresponding undirected edge. - /// - /// \todo reference to the corresponding point of the undirected graph - /// concept. "What does the direction of an undirected edge mean?" - bool forward(const Edge &e) const { return e.forward; } - - Node oppositeNode(const Node &n, const UndirEdge &e) const { - if( n == Parent::source(e)) - return Parent::target(e); - else if( n == Parent::target(e)) - return Parent::source(e); - else - return INVALID; - } - - /// Directed edge from an undirected edge and a source node. - /// - /// Returns a (directed) Edge corresponding to the specified UndirEdge - /// and source Node. - /// - ///\todo Do we need this? - /// - ///\todo Better name... - Edge edgeWithSource(const UndirEdge &ue, const Node &s) const { - return Edge(*this, ue, s); - } - - using Parent::first; - void first(Edge &e) const { - Parent::first(e); - e.forward=true; - } - - using Parent::next; - void next(Edge &e) const { - if( e.forward ) { - e.forward = false; - } - else { - Parent::next(e); - e.forward = true; - } - } - - - protected: - - template - void _dirFirstOut(E &e, const Node &n) const { - Parent::firstIn(e,n); - if( UndirEdge(e) != INVALID ) { - e.forward = false; - } - else { - Parent::firstOut(e,n); - e.forward = true; - } - } - template - void _dirFirstIn(E &e, const Node &n) const { - Parent::firstOut(e,n); - if( UndirEdge(e) != INVALID ) { - e.forward = false; - } - else { - Parent::firstIn(e,n); - e.forward = true; - } - } - - template - void _dirNextOut(E &e) const { - if( ! e.forward ) { - Node n = Parent::target(e); - Parent::nextIn(e); - if( UndirEdge(e) == INVALID ) { - Parent::firstOut(e, n); - e.forward = true; - } - } - else { - Parent::nextOut(e); - } - } - template - void _dirNextIn(E &e) const { - if( ! e.forward ) { - Node n = Parent::source(e); - Parent::nextOut(e); - if( UndirEdge(e) == INVALID ) { - Parent::firstIn(e, n); - e.forward = true; - } - } - else { - Parent::nextIn(e); - } - } - - public: - - void firstOut(Edge &e, const Node &n) const { - _dirFirstOut(e, n); - } - void firstIn(Edge &e, const Node &n) const { - _dirFirstIn(e, n); - } - - void nextOut(Edge &e) const { - _dirNextOut(e); - } - void nextIn(Edge &e) const { - _dirNextIn(e); - } - - // Miscellaneous stuff: - - /// \todo these methods (id, maxEdgeId) should be moved into separate - /// Extender - - // using Parent::id; - // Using "using" is not a good idea, cause it could be that there is - // no "id" in Parent... - - int id(const Node &n) const { - return Parent::id(n); - } - - int id(const UndirEdge &e) const { - return Parent::id(e); - } - - int id(const Edge &e) const { - return 2 * Parent::id(e) + int(e.forward); - } - - - int maxId(Node) const { - return Parent::maxId(Node()); - } - - int maxId(Edge) const { - return 2 * Parent::maxId(typename Parent::Edge()) + 1; - } - int maxId(UndirEdge) const { - return Parent::maxId(typename Parent::Edge()); - } - - - int edgeNum() const { - return 2 * Parent::edgeNum(); - } - int undirEdgeNum() const { - return Parent::edgeNum(); - } - - }; - -} - -#endif // LEMON_UNDIR_GRAPH_EXTENDER_H diff -r 4ea2147274db -r d4acebef7276 src/lemon/vector_map.h --- a/src/lemon/vector_map.h Tue Apr 05 09:49:01 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,287 +0,0 @@ -/* -*- C++ -*- - * src/lemon/vector_map.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_VECTOR_MAP_H -#define LEMON_VECTOR_MAP_H - -#include -#include - -#include -#include -#include - -///\ingroup graphmaps -///\file -///\brief Vector based graph maps. - -namespace lemon { - - /// \addtogroup graphmaps - /// @{ - - /// The VectorMap template class is graph map structure what - /// automatically updates the map when a key is added to or erased from - /// the map. This map factory uses the allocators to implement - /// the container functionality. This map factory - /// uses the std::vector to implement the container function. - /// - /// \param Registry The AlterationNotifier that will notify this map. - /// \param IdMap The IdMap type of the graph items. - /// \param Value The value type of the map. - /// - /// \author Balazs Dezso - - - template < - typename _Graph, - typename _Item, - typename _Value - > - class VectorMap : public AlterationNotifier<_Item>::ObserverBase { - public: - - /// The graph type of the map. - typedef _Graph Graph; - /// The key type of the map. - typedef _Item Key; - /// The id map type of the map. - typedef AlterationNotifier<_Item> Registry; - /// The value type of the map. - typedef _Value Value; - - /// The map type. - typedef VectorMap Map; - /// The base class of the map. - typedef typename Registry::ObserverBase Parent; - - private: - - /// The container type of the map. - typedef std::vector Container; - - public: - - /// The reference type of the map; - typedef typename Container::reference Reference; - /// The pointer type of the map; - typedef typename Container::pointer Pointer; - - /// The const value type of the map. - typedef const Value ConstValue; - /// The const reference type of the map; - typedef typename Container::const_reference ConstReference; - /// The pointer type of the map; - typedef typename Container::const_pointer ConstPointer; - - typedef True FullTypeTag; - - /// Constructor to attach the new map into the registry. - - /// It construates a map and attachs it into the registry. - /// It adds all the items of the graph to the map. - - VectorMap(const Graph& _g) : graph(&_g) { - attach(_g.getNotifier(_Item())); - build(); - } - - /// Constructor uses given value to initialize the map. - - /// It construates a map uses a given value to initialize the map. - /// It adds all the items of the graph to the map. - - VectorMap(const Graph& _g, const Value& _v) : graph(&_g) { - attach(_g.getNotifier(_Item())); - container.resize(graph->maxId(_Item()) + 1, _v); - } - - VectorMap(const VectorMap& _copy) : graph(_copy.getGraph()) { - if (_copy.attached()) { - attach(*_copy.getRegistry()); - container = _copy.container; - } - } - - using Parent::attach; - using Parent::detach; - using Parent::attached; - - /** Assign operator to copy a map of the same map type. - */ - VectorMap& operator=(const VectorMap& copy) { - if (© == this) return *this; - - if (graph != copy.graph) { - if (attached()) { - detach(); - } - if (copy.attached()) { - attach(*copy.getRegistry()); - } - } - container = copy.container; - - return *this; - } - - - virtual ~VectorMap() { - if (attached()) { - detach(); - } - } - - const Graph* getGraph() const { - return graph; - } - - /// The subcript operator. - - /// The subscript operator. The map can be subscripted by the - /// actual items of the graph. - - Reference operator[](const Key& key) { - return container[graph->id(key)]; - } - - /// The const subcript operator. - - /// The const subscript operator. The map can be subscripted by the - /// actual items of the graph. - - ConstReference operator[](const Key& key) const { - return container[graph->id(key)]; - } - - - /// The setter function of the map. - - /// It the same as operator[](key) = value expression. - /// - - void set(const Key& key, const Value& value) { - (*this)[key] = value; - } - - /// Adds a new key to the map. - - /// It adds a new key to the map. It called by the observer registry - /// and it overrides the add() member function of the observer base. - - void add(const Key& key) { - int id = graph->id(key); - if (id >= (int)container.size()) { - container.resize(id + 1); - } - } - - /// Erases a key from the map. - - /// Erase a key from the map. It called by the observer registry - /// and it overrides the erase() member function of the observer base. - void erase(const Key&) {} - - /// Buildes the map. - - /// It buildes the map. It called by the observer registry - /// and it overrides the build() member function of the observer base. - - void build() { - container.resize(graph->maxId(_Item()) + 1); - } - - /// Clear the map. - - /// It erase all items from the map. It called by the observer registry - /// and it overrides the clear() member function of the observer base. - void clear() { - container.clear(); - } - - private: - - Container container; - const Graph *graph; - - }; - - - template - class VectorMappableGraphExtender : public _Base { - public: - - typedef VectorMappableGraphExtender<_Base> Graph; - typedef _Base Parent; - - typedef typename Parent::Node Node; - typedef typename Parent::NodeIt NodeIt; - typedef typename Parent::NodeIdMap NodeIdMap; - typedef typename Parent::NodeNotifier NodeObserverRegistry; - - typedef typename Parent::Edge Edge; - typedef typename Parent::EdgeIt EdgeIt; - typedef typename Parent::EdgeIdMap EdgeIdMap; - typedef typename Parent::EdgeNotifier EdgeObserverRegistry; - - - template - class NodeMap : - public IterableMapExtender > { - public: - typedef VectorMappableGraphExtender<_Base> Graph; - - typedef typename Graph::Node Node; - - typedef IterableMapExtender > Parent; - - //typedef typename Parent::Graph Graph; - typedef typename Parent::Value Value; - - NodeMap(const Graph& g) - : Parent(g) {} - NodeMap(const Graph& g, const Value& v) - : Parent(g, v) {} - - }; - - template - class EdgeMap - : public IterableMapExtender > { - public: - typedef VectorMappableGraphExtender<_Base> Graph; - - typedef typename Graph::Edge Edge; - - typedef IterableMapExtender > Parent; - - //typedef typename Parent::Graph Graph; - typedef typename Parent::Value Value; - - EdgeMap(const Graph& g) - : Parent(g) {} - EdgeMap(const Graph& g, const Value& v) - : Parent(g, v) {} - - }; - - }; - - /// @} - -} - -#endif diff -r 4ea2147274db -r d4acebef7276 src/test/undir_graph_test.cc --- a/src/test/undir_graph_test.cc Tue Apr 05 09:49:01 2005 +0000 +++ b/src/test/undir_graph_test.cc Tue Apr 05 12:30:46 2005 +0000 @@ -1,6 +1,6 @@ // -*- C++ -*- -#include +#include #include #include #include