# HG changeset patch # User klao # Date 1098916730 0 # Node ID c94ef40a22ce54a7535456ad38d8026346e1420a # Parent f2ea4aac9ada0181dbd64d5ba35fa7e29515287a The graph_factory branch (@ 1321) has been merged to trunk. diff -r f2ea4aac9ada -r c94ef40a22ce src/benchmark/hcube.cc --- a/src/benchmark/hcube.cc Mon Oct 25 13:29:46 2004 +0000 +++ b/src/benchmark/hcube.cc Wed Oct 27 22:38:50 2004 +0000 @@ -66,12 +66,15 @@ for(int i=0;i +#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 AlterationObserverRegistry::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 AlterationObserverRegistry { + 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 builded from an empty container or + /// is cleared to an empty container. + /// + /// \author Balazs Dezso + + class ObserverBase { + protected: + typedef AlterationObserverRegistry Registry; + + friend class Registry; + + /// Default constructor. + + /// Default constructor for ObserverBase. + /// + ObserverBase() : registry(0) {} + + virtual ~ObserverBase() {} + + /// Attaches the observer into an AlterationObserverRegistry. + + /// This member attaches the observer into an AlterationObserverRegistry. + /// + void attach(AlterationObserverRegistry& r) { + registry = &r; + registry->attach(*this); + } + + /// Detaches the observer into an AlterationObserverRegistry. + + /// This member detaches the observer from an AlterationObserverRegistry. + /// + 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 builded. + /// + /// The build() member function notificates the observer about the + /// container is builded 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 AlterationObserverRegistry. + /// It creates an empty registry. + AlterationObserverRegistry() {} + + /// Copy Constructor of the AlterationObserverRegistry. + + /// Copy constructor of the AlterationObserverRegistry. + /// It creates only an empty registry because the copiable + /// registry's observers have to be registered still into that registry. + AlterationObserverRegistry(const AlterationObserverRegistry&) {} + + /// Assign operator. + + /// Assign operator for the AlterationObserverRegistry. + /// It makes the registry only empty because the copiable + /// registry's observers have to be registered still into that registry. + AlterationObserverRegistry& operator=(const AlterationObserverRegistry&) { + typename Container::iterator it; + for (it = container.begin(); it != container.end(); ++it) { + (*it)->registry = 0; + } + } + + /// Destructor. + + /// Destructor of the AlterationObserverRegistry. + /// + ~AlterationObserverRegistry() { + 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 builded. + + /// Notifies all the registered observers about the container is builded + /// 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(); + } + } + }; + + + /// Class to extend a graph functionality with the possibility 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. + /// + /// \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 node observer registry. + typedef AlterationObserverRegistry EdgeObserverRegistry; + /// The edge observer registry. + typedef AlterationObserverRegistry NodeObserverRegistry; + + + protected: + + mutable EdgeObserverRegistry edge_observers; + + mutable NodeObserverRegistry node_observers; + + public: + + EdgeObserverRegistry& getEdgeObserverRegistry() const { + return edge_observers; + } + + NodeObserverRegistry& getNodeObserverRegistry() const { + return node_observers; + } + + ~AlterableGraphExtender() { + node_observers.clear(); + edge_observers.clear(); + } + + }; + + +/// @} + + +} + +#endif diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/array_map.h --- a/src/lemon/array_map.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/lemon/array_map.h Wed Oct 27 22:38:50 2004 +0000 @@ -20,7 +20,6 @@ #include #include -#include ///\ingroup graphmaps ///\file @@ -42,22 +41,32 @@ * will belong to and the ValueType. */ - template - class ArrayMap : public MapRegistry::MapBase { + template + class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase { - template friend class ArrayMap; - public: /// The graph type of the maps. - typedef typename MapRegistry::Graph Graph; + typedef _Graph Graph; /// The key type of the maps. - typedef typename MapRegistry::KeyType KeyType; + typedef _Item KeyType; + + typedef AlterationObserverRegistry<_Item> Registry; + + private: /// The iterator to iterate on the keys. - typedef typename MapRegistry::KeyIt KeyIt; + typedef _ItemIt KeyIt; + + typedef _IdMap IdMap; + + typedef _Value Value; /// The MapBase of the Map which imlements the core regisitry function. - typedef typename MapRegistry::MapBase MapBase; + typedef typename Registry::ObserverBase Parent; public: @@ -77,52 +86,47 @@ typedef const Value* ConstPointerType; + private: typedef std::allocator Allocator; - + + public: + /** Graph and Registry initialized map constructor. */ - ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) { + ArrayMap(const Graph& _g, Registry& _r) : graph(&_g) { + attach(_r); allocate_memory(); - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); + for (KeyIt it(*graph); it != INVALID; ++it) { + int id = IdMap(*graph)[it]; allocator.construct(&(values[id]), Value()); } } - /** Constructor to use default value to initialize the map. - */ - ArrayMap(const Graph& g, MapRegistry& r, const Value& v) - : MapBase(g, r) { + /// Constructor to use default value to initialize the map. + + /// It constrates a map and initialize all of the the map. + + ArrayMap(const Graph& _g, Registry& _r, const Value& _v) : graph(&_g) { + attach(_r); allocate_memory(); - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); - allocator.construct(&(values[id]), v); + for (KeyIt it(*graph); it != INVALID; ++it) { + int id = IdMap(*graph)[it]; + allocator.construct(&(values[id]), _v); } } /** Constructor to copy a map of the same map type. */ - ArrayMap(const ArrayMap& copy) : MapBase(copy) { + ArrayMap(const ArrayMap& copy) { + if (copy.attached()) { + attach(*copy.getRegistry()); + } capacity = copy.capacity; if (capacity == 0) return; values = allocator.allocate(capacity); - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); - allocator.construct(&(values[id]), copy.values[id]); - } - } - - /** Constructor to copy a map of an other map type. - */ - template - ArrayMap(const ArrayMap& copy) - : MapBase(copy) { - capacity = copy.capacity; - if (capacity == 0) return; - values = allocator.allocate(capacity); - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); + for (KeyIt it(*graph); it != INVALID; ++it) { + int id = IdMap(*graph)[it]; allocator.construct(&(values[id]), copy.values[id]); } } @@ -132,58 +136,33 @@ ArrayMap& operator=(const ArrayMap& copy) { if (© == this) return *this; - if (MapBase::getGraph() != copy.getGraph()) { - if (capacity != 0) { - MapBase::destroy(); - allocator.deallocate(values, capacity); + if (graph != copy.graph) { + if (attached()) { + clear(); + detach(); } - - MapBase::operator=(copy); + if (copy.attached()) { + attach(*copy.getRegistry()); + } capacity = copy.capacity; if (capacity == 0) return *this; values = allocator.allocate(capacity); } - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); + for (KeyIt it(*graph); it != INVALID; ++it) { + int id = IdMap(*graph)[it]; allocator.construct(&(values[id]), copy.values[id]); } return *this; } - /** Assign operator to copy a map of an other map type. - */ - template - ArrayMap& operator=(const ArrayMap& copy) { - - if (MapBase::getGraph() != copy.getGraph()) { - if (capacity != 0) { - MapBase::destroy(); - allocator.deallocate(values, capacity); - } - - MapBase::operator=(copy); - - capacity = copy.capacity; - if (capacity == 0) return *this; - values = allocator.allocate(capacity); - } - - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); - allocator.construct(&(values[id]), copy.values[id]); - } - - return *this; - } - /** The destructor of the map. */ - virtual ~ArrayMap() { - if (capacity != 0) { - MapBase::destroy(); - allocator.deallocate(values, capacity); + virtual ~ArrayMap() { + if (attached()) { + clear(); + detach(); } } @@ -193,7 +172,7 @@ * actual keys of the graph. */ ReferenceType operator[](const KeyType& key) { - int id = KeyInfo::id(*MapBase::getGraph(), key); + int id = IdMap(*graph)[key]; return values[id]; } @@ -202,7 +181,7 @@ * actual keys of the graph. */ ConstReferenceType operator[](const KeyType& key) const { - int id = KeyInfo::id(*MapBase::getGraph(), key); + int id = IdMap(*graph)[key]; return values[id]; } @@ -210,22 +189,21 @@ * This is a compatibility feature with the not dereferable maps. */ void set(const KeyType& key, const ValueType& val) { - int id = KeyInfo::id(*MapBase::getGraph(), key); - values[id] = val; + (*this)[key] = val; } /** Add a new key to the map. It called by the map registry. */ void add(const KeyType& key) { - int id = KeyInfo::id(*MapBase::getGraph(), key); + int id = IdMap(*graph)[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);; - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int jd = KeyInfo::id(*MapBase::getGraph(), it); + Value* new_values = allocator.allocate(new_capacity); + for (KeyIt it(*graph); it != INVALID; ++it) { + int jd = IdMap(*graph)[it]; if (id != jd) { allocator.construct(&(new_values[jd]), values[jd]); allocator.destroy(&(values[jd])); @@ -241,77 +219,86 @@ /** Erase a key from the map. It called by the map registry. */ void erase(const KeyType& key) { - int id = KeyInfo::id(*MapBase::getGraph(), key); + int id = IdMap(*graph)[key]; allocator.destroy(&(values[id])); } - /** Clear the data structure. - */ + void build() { + allocate_memory(); + for (KeyIt it(*graph); it != INVALID; ++it) { + int id = IdMap(*graph)[it]; + allocator.construct(&(values[id]), Value()); + } + } + void clear() { if (capacity != 0) { - MapBase::destroy(); + for (KeyIt it(*graph); it != INVALID; ++it) { + int id = IdMap(*graph)[it]; + allocator.destroy(&(values[id])); + } allocator.deallocate(values, capacity); capacity = 0; } } - /// The stl compatible pair iterator of the map. - typedef MapIterator Iterator; - /// The stl compatible const pair iterator of the map. - typedef MapConstIterator ConstIterator; +// /// 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 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 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 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); - } +// /** Returns the end const_iterator of the map. +// */ +// ConstIterator end() const { +// return ConstIterator(*this, INVALID); +// } - /// The KeySet of the Map. - typedef MapConstKeySet ConstKeySet; +// /// The KeySet of the Map. +// typedef MapConstKeySet ConstKeySet; - /// KeySet getter function. - ConstKeySet keySet() const { - return ConstKeySet(*this); - } +// /// KeySet getter function. +// ConstKeySet keySet() const { +// return ConstKeySet(*this); +// } - /// The ConstValueSet of the Map. - typedef MapConstValueSet ConstValueSet; +// /// The ConstValueSet of the Map. +// typedef MapConstValueSet ConstValueSet; - /// ConstValueSet getter function. - ConstValueSet valueSet() const { - return ConstValueSet(*this); - } +// /// ConstValueSet getter function. +// ConstValueSet valueSet() const { +// return ConstValueSet(*this); +// } - /// The ValueSet of the Map. - typedef MapValueSet ValueSet; +// /// The ValueSet of the Map. +// typedef MapValueSet ValueSet; - /// ValueSet getter function. - ValueSet valueSet() { - return ValueSet(*this); - } +// /// ValueSet getter function. +// ValueSet valueSet() { +// return ValueSet(*this); +// } private: void allocate_memory() { - int max_id = KeyInfo::maxId(*MapBase::getGraph()); + int max_id = IdMap(*graph).maxId(); if (max_id == -1) { capacity = 0; values = 0; @@ -324,24 +311,88 @@ values = allocator.allocate(capacity); } + const Graph* graph; int capacity; Value* values; Allocator allocator; public: - // STL compatibility typedefs. - typedef Iterator iterator; - typedef ConstIterator const_iterator; - typedef typename Iterator::PairValueType value_type; - typedef typename Iterator::KeyType key_type; - typedef typename Iterator::ValueType data_type; - typedef typename Iterator::PairReferenceType reference; - typedef typename Iterator::PairPointerType pointer; - typedef typename ConstIterator::PairReferenceType const_reference; - typedef typename ConstIterator::PairPointerType const_pointer; - typedef int difference_type; +// // STL compatibility typedefs. +// typedef Iterator iterator; +// typedef ConstIterator const_iterator; +// typedef typename Iterator::PairValueType value_type; +// typedef typename Iterator::KeyType key_type; +// typedef typename Iterator::ValueType data_type; +// typedef typename Iterator::PairReferenceType reference; +// typedef typename Iterator::PairPointerType pointer; +// typedef typename ConstIterator::PairReferenceType const_reference; +// typedef typename ConstIterator::PairPointerType const_pointer; +// typedef int difference_type; }; + 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::NodeIdMap NodeIdMap; + typedef typename Parent::NodeObserverRegistry NodeObserverRegistry; + + typedef typename Parent::Edge Edge; + typedef typename Parent::EdgeIt EdgeIt; + typedef typename Parent::EdgeIdMap EdgeIdMap; + typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry; + + + + template + class NodeMap : public ArrayMap { + public: + typedef ArrayMappableGraphExtender<_Base> Graph; + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::NodeIdMap NodeIdMap; + + typedef ArrayMap Parent; + + typedef typename Parent::Graph Graph; + typedef typename Parent::Value Value; + + NodeMap(const Graph& g) + : Parent(g, g.getNodeObserverRegistry()) {} + NodeMap(const Graph& g, const Value& v) + : Parent(g, g.getNodeObserverRegistry(), v) {} + + }; + + template + class EdgeMap : public ArrayMap { + public: + typedef ArrayMappableGraphExtender<_Base> Graph; + + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::EdgeIdMap EdgeIdMap; + + typedef ArrayMap Parent; + + typedef typename Parent::Graph Graph; + typedef typename Parent::Value Value; + + EdgeMap(const Graph& g) + : Parent(g, g.getEdgeObserverRegistry()) {} + EdgeMap(const Graph& g, const Value& v) + : Parent(g, g.getEdgeObserverRegistry(), v) {} + + }; + + }; + /// @} } diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/bfs.h --- a/src/lemon/bfs.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/lemon/bfs.h Wed Oct 27 22:38:50 2004 +0000 @@ -195,7 +195,7 @@ pred_node->set(u,INVALID); } - int N=G->nodeNum(); + int N = countNodes(*G); std::vector Q(N); int Qh=0; int Qt=0; diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/clearable_graph_extender.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/clearable_graph_extender.h Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,28 @@ +// -*- 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; + + void clear() { + Parent::getNodeObserverRegistry().clear(); + Parent::getEdgeObserverRegistry().clear(); + Parent::clear(); + } + + }; + +} + +#endif diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/concept_check.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/concept_check.h Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,80 @@ +// -*- C++ -*- +// Modified for use in LEMON. +// We should really consider using Boost... + + +// +// (C) Copyright Jeremy Siek 2000. +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// Revision History: +// 05 May 2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek) +// 02 April 2001: Removed limits header altogether. (Jeremy Siek) +// 01 April 2001: Modified to use new header. (JMaddock) +// + +// See http://www.boost.org/libs/concept_check for documentation. + +#ifndef LEMON_BOOST_CONCEPT_CHECKS_HPP +#define LEMON_BOOST_CONCEPT_CHECKS_HPP + +namespace lemon { + + /* + "inline" is used for ignore_unused_variable_warning() + and function_requires() to make sure there is no + overhead with g++. + */ + + template inline void ignore_unused_variable_warning(const T&) { } + + template + inline void function_requires() + { +#if !defined(NDEBUG) + void (Concept::*x)() = & Concept::constraints; + ignore_unused_variable_warning(x); +#endif + } + +#define BOOST_CLASS_REQUIRE(type_var, ns, concept) \ + typedef void (ns::concept ::* func##type_var##concept)(); \ + template \ + struct concept_checking_##type_var##concept { }; \ + typedef concept_checking_##type_var##concept< \ + BOOST_FPTR ns::concept::constraints> \ + concept_checking_typedef_##type_var##concept + +#define BOOST_CLASS_REQUIRE2(type_var1, type_var2, ns, concept) \ + typedef void (ns::concept ::* \ + func##type_var1##type_var2##concept)(); \ + template \ + struct concept_checking_##type_var1##type_var2##concept { }; \ + typedef concept_checking_##type_var1##type_var2##concept< \ + BOOST_FPTR ns::concept::constraints> \ + concept_checking_typedef_##type_var1##type_var2##concept + +#define BOOST_CLASS_REQUIRE3(tv1, tv2, tv3, ns, concept) \ + typedef void (ns::concept ::* \ + func##tv1##tv2##tv3##concept)(); \ + template \ + struct concept_checking_##tv1##tv2##tv3##concept { }; \ + typedef concept_checking_##tv1##tv2##tv3##concept< \ + BOOST_FPTR ns::concept::constraints> \ + concept_checking_typedef_##tv1##tv2##tv3##concept + +#define BOOST_CLASS_REQUIRE4(tv1, tv2, tv3, tv4, ns, concept) \ + typedef void (ns::concept ::* \ + func##tv1##tv2##tv3##tv4##concept)(); \ + template \ + struct concept_checking_##tv1##tv2##tv3##tv4##concept { }; \ + typedef concept_checking_##tv1##tv2##tv3##tv4##concept< \ + BOOST_FPTR ns::concept::constraints> \ + concept_checking_typedef_##tv1##tv2##tv3##tv4##concept + + +} // namespace lemon + +#endif // LEMON_BOOST_CONCEPT_CHECKS_HPP diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/default_map.h --- a/src/lemon/default_map.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/lemon/default_map.h Wed Oct 27 22:38:50 2004 +0000 @@ -23,7 +23,7 @@ ///\ingroup graphmaps ///\file -///\brief Graph maps that construates and destruates +///\brief Graph maps that construct and destruct ///their elements dynamically. namespace lemon { @@ -41,100 +41,185 @@ */ - /** Macro to implement the DefaultMap. - */ -#define DEFAULT_MAP_BODY(DynMap, Value) \ -{ \ -\ -public: \ -\ -typedef DynMap Parent; \ -\ -typedef typename MapRegistry::Graph Graph; \ -\ -DefaultMap(const Graph& g, MapRegistry& r) : Parent(g, r) {} \ -DefaultMap(const Graph& g, MapRegistry& r, const Value& v) \ - : Parent(g, r, v) {} \ -DefaultMap(const DefaultMap& copy) \ - : Parent(static_cast(copy)) {} \ -template \ -DefaultMap(const DefaultMap& copy) \ - : Parent(*copy.getGraph()) { \ - if (Parent::getGraph()) { \ - for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\ - Parent::operator[](it) = copy[it]; \ - } \ - } \ -} \ -DefaultMap& operator=(const DefaultMap& copy) { \ - Parent::operator=(static_cast(copy)); \ - return *this; \ -} \ -template \ -DefaultMap& operator=(const DefaultMap& copy) { \ - if (Parent::getGraph() != copy.getGraph()) { \ - Parent::clear(); \ - Parent::MapBase::operator=(copy); \ - Parent::construct(); \ - } \ - if (Parent::getGraph()) { \ - for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\ - Parent::operator[](it) = copy[it]; \ - } \ - } \ - return *this; \ -} \ -}; + template + struct DefaultMapSelector { + typedef ArrayMap<_Graph, _Item, _ItemIt, _IdMap, _Value> Map; + }; - template - class DefaultMap : public ArrayMap - DEFAULT_MAP_BODY(ArrayMap, Type); + // bool + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, bool> { + typedef VectorMap<_Graph, _Item, _IdMap, bool> Map; + }; - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, bool); + // char + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, char> { + typedef VectorMap<_Graph, _Item, _IdMap, char> Map; + }; - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, char); + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed char> { + typedef VectorMap<_Graph, _Item, _IdMap, signed char> Map; + }; - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, int); + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned char> { + typedef VectorMap<_Graph, _Item, _IdMap, unsigned char> Map; + }; - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, short); - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, long); + // int + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed int> { + typedef VectorMap<_Graph, _Item, _IdMap, signed int> Map; + }; - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, float); + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned int> { + typedef VectorMap<_Graph, _Item, _IdMap, unsigned int> Map; + }; - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, double); - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, long double); + // short + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed short> { + typedef VectorMap<_Graph, _Item, _IdMap, signed short> Map; + }; - template - class DefaultMap - : public VectorMap - DEFAULT_MAP_BODY(VectorMap, Type*); + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned short> { + typedef VectorMap<_Graph, _Item, _IdMap, unsigned short> Map; + }; + + + // long + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed long> { + typedef VectorMap<_Graph, _Item, _IdMap, signed long> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned long> { + typedef VectorMap<_Graph, _Item, _IdMap, unsigned long> Map; + }; + + // \todo handling long long type + + + // float + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, float> { + typedef VectorMap<_Graph, _Item, _IdMap, float> Map; + }; + + + // double + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, double> { + typedef VectorMap<_Graph, _Item, _IdMap, double> Map; + }; + + + // long double + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, long double> { + typedef VectorMap<_Graph, _Item, _IdMap, long double> Map; + }; + + + // pointer + template + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Ptr*> { + typedef VectorMap<_Graph, _Item, _IdMap, _Ptr*> Map; + }; + + + + template + class DefaultMap : public DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Value>::Map { + public: + typedef typename DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Value>::Map Parent; + typedef DefaultMap<_Graph, _Item, _ItemIt, _IdMap, bool> Map; + + typedef typename Parent::Graph Graph; + typedef typename Parent::Registry Registry; + typedef typename Parent::ValueType ValueType; + + DefaultMap(const Graph& _g, Registry& _r) : Parent(_g, _r) {} + DefaultMap(const Graph& _g, Registry& _r, const ValueType& _v) : Parent(_g, _r, _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::NodeIdMap NodeIdMap; + typedef typename Parent::NodeObserverRegistry NodeObserverRegistry; + + typedef typename Parent::Edge Edge; + typedef typename Parent::EdgeIt EdgeIt; + typedef typename Parent::EdgeIdMap EdgeIdMap; + typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry; + + + + template + class NodeMap : public DefaultMap { + public: + typedef DefaultMappableGraphExtender<_Base> Graph; + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::NodeIdMap NodeIdMap; + + typedef DefaultMap Parent; + + typedef typename Parent::Graph Graph; + typedef typename Parent::ValueType ValueType; + + NodeMap(const Graph& g) + : Parent(g, g.getNodeObserverRegistry()) {} + NodeMap(const Graph& g, const ValueType& v) + : Parent(g, g.getNodeObserverRegistry(), v) {} + + }; + + template + class EdgeMap : public DefaultMap { + public: + typedef DefaultMappableGraphExtender<_Base> Graph; + + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::EdgeIdMap EdgeIdMap; + + typedef DefaultMap Parent; + + typedef typename Parent::Graph Graph; + typedef typename Parent::ValueType ValueType; + + EdgeMap(const Graph& g) + : Parent(g, g.getEdgeObserverRegistry()) {} + EdgeMap(const Graph& g, const ValueType& v) + : Parent(g, g.getEdgeObserverRegistry(), v) {} + + }; + + }; + } diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/dfs.h --- a/src/lemon/dfs.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/lemon/dfs.h Wed Oct 27 22:38:50 2004 +0000 @@ -23,7 +23,7 @@ /// ///\todo Revise Manual. -#include +#include #include namespace lemon { @@ -193,12 +193,12 @@ pred_node->set(u,INVALID); } - int N=G->nodeNum(); + int N = countNodes(*G); std::vector Q(N); int Qh=0; - G->first(Q[Qh],s); + Q[Qh] = OutEdgeIt(*G, s); distance->set(s, 0); Node n=s; @@ -209,7 +209,7 @@ if((m=G->head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) { predecessor->set(m,e); pred_node->set(m,n); - G->first(Q[++Qh],m); + Q[++Qh] = OutEdgeIt(*G, m); distance->set(m,Qh); n=m; } diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/erasable_graph_extender.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/erasable_graph_extender.h Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,48 @@ +// -*- 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::getNodeObserverRegistry().erase(node); + Parent::erase(node); + } + + void erase(const Edge& edge) { + Parent::getEdgeObserverRegistry().erase(edge); + Parent::erase(edge); + } + + }; + +} + +#endif diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/extendable_graph_extender.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/extendable_graph_extender.h Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,34 @@ +// -*- 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::getNodeObserverRegistry().add(node); + return node; + } + + Edge addEdge(const Node& from, const Node& to) { + Edge edge = Parent::addEdge(from, to); + Parent::getEdgeObserverRegistry().add(edge); + return edge; + } + + }; + +} + +#endif diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/full_graph.h --- a/src/lemon/full_graph.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/lemon/full_graph.h Wed Oct 27 22:38:50 2004 +0000 @@ -17,20 +17,21 @@ #ifndef LEMON_FULL_GRAPH_H #define LEMON_FULL_GRAPH_H + +#include + +#include + +#include +#include + ///\ingroup graphs ///\file ///\brief FullGraph and SymFullGraph classes. -#include -#include #include -#include -#include - -#include - namespace lemon { /// \addtogroup graphs @@ -48,34 +49,26 @@ ///\todo Don't we need SymEdgeMap? /// ///\author Alpar Juttner - class FullGraph { + class FullGraphBase { int NodeNum; int EdgeNum; public: - typedef FullGraph Graph; + typedef FullGraphBase Graph; class Node; class Edge; - class NodeIt; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; - - - // Create map registries. - CREATE_MAP_REGISTRIES; - // Create node and edge maps. - CREATE_MAPS(ArrayMap); - public: + FullGraphBase() {} + + ///Creates a full graph with \c n nodes. - FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { } + void construct(int n) { NodeNum = n; EdgeNum = n * n; } /// - FullGraph(const FullGraph &_g) - : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } + // FullGraphBase(const FullGraphBase &_g) + // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } ///Number of nodes. int nodeNum() const { return NodeNum; } @@ -93,17 +86,9 @@ ///\sa id(Edge) int maxEdgeId() const { return EdgeNum-1; } - Node tail(Edge e) const { return e.n%NodeNum; } - Node head(Edge e) const { return e.n/NodeNum; } + Node tail(Edge e) const { return e.id % NodeNum; } + Node head(Edge e) const { return e.id / NodeNum; } - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } /// Node ID. @@ -113,7 +98,8 @@ /// /// The ID of the \ref INVALID node is -1. ///\return The ID of the node \c v. - static int id(Node v) { return v.n; } + + static int id(Node v) { return v.id; } /// Edge ID. /// The ID of a valid Edge is a nonnegative integer not greater than @@ -122,7 +108,7 @@ /// /// The ID of the \ref INVALID edge is -1. ///\return The ID of the edge \c e. - static int id(Edge e) { return e.n; } + static int id(Edge e) { return e.id; } /// Finds an edge between two nodes. @@ -134,110 +120,102 @@ /// \return The found edge or INVALID if there is no such an edge. Edge findEdge(Node u,Node v, Edge prev = INVALID) { - return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID; + return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; } class Node { - friend class FullGraph; - template friend class NodeMap; - - friend class Edge; - friend class OutEdgeIt; - friend class InEdgeIt; - friend class SymEdge; + friend class FullGraphBase; protected: - int n; - friend int FullGraph::id(Node v); - Node(int nn) {n=nn;} + int id; + Node(int _id) { id = _id;} public: Node() {} - Node (Invalid) { n=-1; } - bool operator==(const Node i) const {return n==i.n;} - bool operator!=(const Node i) const {return n!=i.n;} - bool operator<(const Node i) const {return n NodeIt. - NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; } + Edge() { } + Edge (Invalid) { id = -1; } + bool operator==(const Edge edge) const {return id == edge.id;} + bool operator!=(const Edge edge) const {return id != edge.id;} + bool operator<(const Edge edge) const {return id < edge.id;} }; - class Edge { - friend class FullGraph; - template friend class EdgeMap; - - friend class Node; - friend class NodeIt; - protected: - int n; //NodeNum*head+tail; - friend int FullGraph::id(Edge e); + void first(Node& node) const { + node.id = NodeNum-1; + } - Edge(int nn) : n(nn) {} - Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {} - public: - Edge() { } - Edge (Invalid) { n=-1; } - bool operator==(const Edge i) const {return n==i.n;} - bool operator!=(const Edge i) const {return n!=i.n;} - bool operator<(const Edge i) const {return nNodeNum; if(n>=G->EdgeNum) n=-1; return *this; } - - }; - - class InEdgeIt : public Edge { - const FullGraph *G; - friend class FullGraph; - public: - InEdgeIt() : Edge() { } - InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { } - InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {} - InEdgeIt& operator++() - { if(!((++n)%G->NodeNum)) n=-1; return *this; } - }; + void nextIn(Edge& edge) const { + ++edge.id; + if (edge.id % NodeNum == 0) edge.id = -1; + } }; + + typedef AlterableGraphExtender AlterableFullGraphBase; + typedef IterableGraphExtender IterableFullGraphBase; + typedef IdMappableGraphExtender IdMappableFullGraphBase; + typedef DefaultMappableGraphExtender MappableFullGraphBase; + + class FullGraph : public MappableFullGraphBase { + public: + + FullGraph(int n) { construct(n); } + }; + + template <> + int countNodes(const FullGraph& graph) { + return graph.nodeNum(); + } + + template <> + int countEdges(const FullGraph& graph) { + return graph.edgeNum(); + } + /// @} } //namespace lemon diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/graph_utils.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/graph_utils.h Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,174 @@ +/* -*- C++ -*- + * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 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_GRAPH_UTILS_H +#define LEMON_GRAPH_UTILS_H + +#include + +#include + +///\ingroup utils +///\file +///\brief Graph utils. +/// + + +namespace lemon { + + // counters in the graph + /// \brief Function to count the items in the graph. + /// + /// This function counts the items in the graph. + /// The complexity of the function is O(n) because + /// it iterates on all of the items. + + template + inline int countItems(const Graph& _g) { + int num = 0; + for (ItemIt it(_g); it != INVALID; ++it) { + ++num; + } + return num; + } + + /// \brief Function to count the nodes in the graph. + /// + /// This function counts the nodes in the graph. + /// The complexity of the function is O(n) but for some + /// graph structure it is specialized to O(1). + + template + inline int countNodes(const Graph& _g) { + return countItems(_g); + } + + /// \brief Function to count the edges in the graph. + /// + /// This function counts the edges in the graph. + /// The complexity of the function is O(e) but for some + /// graph structure it is specialized to O(1). + template + inline int countEdges(const Graph& _g) { + return countItems(_g); + } + + /// \brief Function to count the symmetric edges in the graph. + /// + /// This function counts the symmetric edges in the graph. + /// The complexity of the function is O(e) but for some + /// graph structure it is specialized to O(1). + template + inline int countSymEdges(const Graph& _g) { + return countItems(_g); + } + + template + inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { + int num = 0; + for (DegIt it(_g, _n); it != INVALID; ++it) { + ++num; + } + return num; + } + + template + inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) { + return countNodeDegree(_g, _n); + } + + template + inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { + return countNodeDegree(_g, _n); + } + + // graph copy + + template < + typename DestinationGraph, + typename SourceGraph, + typename NodeBijection> + void copyNodes(DestinationGraph& _d, const SourceGraph& _s, + NodeBijection& _nb) { + for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) { + _nb[it] = _d.addNode(); + } + } + + template < + typename DestinationGraph, + typename SourceGraph, + typename NodeBijection, + typename EdgeBijection> + void copyEdges(DestinationGraph& _d, const SourceGraph& _s, + const NodeBijection& _nb, EdgeBijection& _eb) { + for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) { + _eb[it] = _d.addEdge(_nb[_s.tail(it)], _nb[_s.head(it)]); + } + } + + template < + typename DestinationGraph, + typename SourceGraph, + typename NodeBijection, + typename EdgeBijection> + void copyGraph(DestinationGraph& _d, const SourceGraph& _s, + NodeBijection& _nb, EdgeBijection& _eb) { + nodeCopy(_d, _s, _nb); + edgeCopy(_d, _s, _nb, _eb); + } + + template < + typename _DestinationGraph, + typename _SourceGraph, + typename _NodeBijection + =typename _SourceGraph::template NodeMap, + typename _EdgeBijection + =typename _SourceGraph::template EdgeMap + > + class GraphCopy { + public: + + typedef _DestinationGraph DestinationGraph; + typedef _SourceGraph SourceGraph; + + typedef _NodeBijection NodeBijection; + typedef _EdgeBijection EdgeBijection; + + protected: + + NodeBijection node_bijection; + EdgeBijection edge_bijection; + + public: + + GraphCopy(DestinationGraph& _d, const SourceGraph& _s) { + copyGraph(_d, _s, node_bijection, edge_bijection); + } + + const NodeBijection& getNodeBijection() const { + return node_bijection; + } + + const EdgeBijection& getEdgeBijection() const { + return edge_bijection; + } + + }; + +} + +#endif diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/idmappable_graph_extender.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/idmappable_graph_extender.h Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,52 @@ +// -*- c++ -*- + +#ifndef LEMON_IDMAPPABLE_GRAPH_EXTENDER_H +#define LEMON_IDMAPPABLE_GRAPH_EXTENDER_H + + +namespace lemon { + + template + class IdMappableGraphExtender : public Base { + public: + + typedef IdMappableGraphExtender Graph; + typedef Base Parent; + + typedef typename Parent::Node Node; + typedef typename Parent::Edge Edge; + + + public: + + class NodeIdMap { + private: + const Graph* graph; + + public: + NodeIdMap(const Graph& g) : graph(&g) {} + + int operator[](const Node& node) const { return graph->id(node); } + + int maxId() const {return graph->maxNodeId(); } + + }; + + class EdgeIdMap { + private: + const Graph* graph; + + public: + EdgeIdMap(const Graph& g) : graph(&g) {} + + int operator[](const Edge& edge) const { return graph->id(edge); } + + int maxId() const {return graph->maxEdgeId(); } + + }; + + }; + +} + +#endif diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/iterable_graph_extender.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/iterable_graph_extender.h Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,131 @@ +// -*- c++ -*- +#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H +#define LEMON_ITERABLE_GRAPH_EXTENDER_H + +#include + +namespace lemon { + + template + class IterableGraphExtender : public _Base { + + typedef _Base Parent; + typedef IterableGraphExtender<_Base> Graph; + + public: + + 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) : Node(), 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) : Edge(), 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) + : Edge(), 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) + : Edge(), graph(&_graph) { + _graph.firstIn(*this, node); + } + + InEdgeIt(const Graph& _graph, const Edge& edge) : + Edge(edge), graph(&_graph) {} + + InEdgeIt& operator++() { + graph->nextIn(*this); + return *this; + } + + }; + + 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; + + }; + +} + +#endif // LEMON_GRAPH_EXTENDER_H diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/list_graph.h --- a/src/lemon/list_graph.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/lemon/list_graph.h Wed Oct 27 22:38:50 2004 +0000 @@ -1,117 +1,87 @@ -/* -*- C++ -*- - * src/lemon/list_graph.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2004 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. - * - */ +// -*- c++ -*- #ifndef LEMON_LIST_GRAPH_H #define LEMON_LIST_GRAPH_H -///\ingroup graphs -///\file -///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes. +#include +#include +#include -#include -#include +#include -#include +#include -#include -#include +#include -#include +#include namespace lemon { -/// \addtogroup graphs -/// @{ + class ListGraphBase { - ///A list graph class. - - ///This is a simple and fast erasable graph implementation. - /// - ///It conforms to the - ///\ref skeleton::ErasableGraph "ErasableGraph" concept. - ///\sa skeleton::ErasableGraph. - class ListGraph { - - //Nodes are double linked. - //The free nodes are only single linked using the "next" field. - struct NodeT - { + struct NodeT { int first_in,first_out; int prev, next; }; - //Edges are double linked. - //The free edges are only single linked using the "next_in" field. - struct EdgeT - { + + struct EdgeT { int head, tail; int prev_in, prev_out; int next_in, next_out; }; std::vector nodes; - //The first node + int first_node; - //The first free node + int first_free_node; + std::vector edges; - //The first free edge + int first_free_edge; public: - typedef ListGraph Graph; + typedef ListGraphBase Graph; - class Node; - class Edge; + class Node { + friend class Graph; + protected: - - public: + int id; + Node(int pid) { id = pid;} - class NodeIt; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; + public: + Node() {} + Node (Invalid) { id = -1; } + bool operator==(const Node& node) const {return id == node.id;} + bool operator!=(const Node& node) const {return id != node.id;} + bool operator<(const Node& node) const {return id < node.id;} + }; - // Create map registries. - CREATE_MAP_REGISTRIES; - // Create node and edge maps. - CREATE_MAPS(ArrayMap); + class Edge { + friend class Graph; + protected: - public: + int id; + Edge(int pid) { id = pid;} - ListGraph() + public: + Edge() {} + Edge (Invalid) { id = -1; } + bool operator==(const Edge& edge) const {return id == edge.id;} + bool operator!=(const Edge& edge) const {return id != edge.id;} + bool operator<(const Edge& edge) const {return id < edge.id;} + }; + + + + ListGraphBase() : nodes(), first_node(-1), first_free_node(-1), edges(), first_free_edge(-1) {} - ListGraph(const ListGraph &_g) - : nodes(_g.nodes), first_node(_g.first_node), - first_free_node(_g.first_free_node), edges(_g.edges), - first_free_edge(_g.first_free_edge) {} - /// \bug In the vector can be hole if a node is erased from the graph. - ///Number of nodes. - int nodeNum() const { return nodes.size(); } - ///Number of edges. - int edgeNum() const { return edges.size(); } - - ///Set the expected maximum number of edges. - - ///With this function, it is possible to set the expected number of edges. - ///The use of this fasten the building of the graph and makes ///it possible to avoid the superfluous memory allocation. void reserveEdge(int n) { edges.reserve(n); }; @@ -120,56 +90,75 @@ /// Maximum node ID. ///\sa id(Node) int maxNodeId() const { return nodes.size()-1; } + /// Maximum edge ID. /// Maximum edge ID. ///\sa id(Edge) int maxEdgeId() const { return edges.size()-1; } - Node tail(Edge e) const { return edges[e.n].tail; } - Node head(Edge e) const { return edges[e.n].head; } + Node tail(Edge e) const { return edges[e.id].tail; } + Node head(Edge e) const { return edges[e.id].head; } - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } - /// Node ID. + void first(Node& node) const { + node.id = first_node; + } + + void next(Node& node) const { + node.id = nodes[node.id].next; + } + + + void first(Edge& e) const { + int n; + for(n = first_node; + n!=-1 && nodes[n].first_in == -1; + n = nodes[n].next); + e.id = (n == -1) ? -1 : nodes[n].first_in; + } + + void next(Edge& edge) const { + if (edges[edge.id].next_in != -1) { + edge.id = edges[edge.id].next_in; + } else { + int n; + for(n = nodes[edges[edge.id].head].next; + n!=-1 && nodes[n].first_in == -1; + n = nodes[n].next); + edge.id = (n == -1) ? -1 : nodes[n].first_in; + } + } + + void firstOut(Edge &e, const Node& v) const { + e.id = nodes[v.id].first_out; + } + void nextOut(Edge &e) const { + e.id=edges[e.id].next_out; + } + + void firstIn(Edge &e, const Node& v) const { + e.id = nodes[v.id].first_in; + } + void nextIn(Edge &e) const { + e.id=edges[e.id].next_in; + } + - /// The ID of a valid Node is a nonnegative integer not greater than - /// \ref maxNodeId(). The range of the ID's is not surely continuous - /// and the greatest node ID can be actually less then \ref maxNodeId(). - /// - /// The ID of the \ref INVALID node is -1. - ///\return The ID of the node \c v. - static int id(Node v) { return v.n; } - /// Edge ID. - - /// The ID of a valid Edge is a nonnegative integer not greater than - /// \ref maxEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxEdgeId(). - /// - /// The ID of the \ref INVALID edge is -1. - ///\return The ID of the edge \c e. - static int id(Edge e) { return e.n; } + static int id(Node v) { return v.id; } + static int id(Edge e) { return e.id; } /// Adds a new node to the graph. /// \warning It adds the new node to the front of the list. /// (i.e. the lastly added node becomes the first.) - Node addNode() { + Node addNode() { int n; - if(first_free_node==-1) - { - n = nodes.size(); - nodes.push_back(NodeT()); - } - else { + if(first_free_node==-1) { + n = nodes.size(); + nodes.push_back(NodeT()); + } else { n = first_free_node; first_free_node = nodes[n].next; } @@ -181,1319 +170,108 @@ nodes[n].first_in = nodes[n].first_out = -1; - Node nn; nn.n=n; - - //Update dynamic maps - node_maps.add(nn); - - return nn; + return Node(n); } Edge addEdge(Node u, Node v) { - int n; - - if(first_free_edge==-1) - { - n = edges.size(); - edges.push_back(EdgeT()); - } - else { + int n; + + if (first_free_edge == -1) { + n = edges.size(); + edges.push_back(EdgeT()); + } else { n = first_free_edge; first_free_edge = edges[n].next_in; } - edges[n].tail = u.n; edges[n].head = v.n; + edges[n].tail = u.id; + edges[n].head = v.id; - edges[n].next_out = nodes[u.n].first_out; - if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n; - edges[n].next_in = nodes[v.n].first_in; - if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n; + edges[n].next_out = nodes[u.id].first_out; + if(nodes[u.id].first_out != -1) { + edges[nodes[u.id].first_out].prev_out = n; + } + + edges[n].next_in = nodes[v.id].first_in; + if(nodes[v.id].first_in != -1) { + edges[nodes[v.id].first_in].prev_in = n; + } + edges[n].prev_in = edges[n].prev_out = -1; - nodes[u.n].first_out = nodes[v.n].first_in = n; + nodes[u.id].first_out = nodes[v.id].first_in = n; - Edge e; e.n=n; - - //Update dynamic maps - edge_maps.add(e); - - return e; + return Edge(n); } - /// Finds an edge between two nodes. + void erase(const Node& node) { + int n = node.id; + + if(nodes[n].next != -1) { + nodes[nodes[n].next].prev = nodes[n].prev; + } + + if(nodes[n].prev != -1) { + nodes[nodes[n].prev].next = nodes[n].next; + } else { + first_node = nodes[n].next; + } + + nodes[n].next = first_free_node; + first_free_node = n; - /// Finds an edge from node \c u to node \c v. - /// - /// If \c prev is \ref INVALID (this is the default value), then - /// It finds the first edge from \c u to \c v. Otherwise it looks for - /// the next edge from \c u to \c v after \c prev. - /// \return The found edge or INVALID if there is no such an edge. - Edge findEdge(Node u,Node v, Edge prev = INVALID) - { - int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; - while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; - prev.n=e; - return prev; } - private: - void eraseEdge(int n) { + void erase(const Edge& edge) { + int n = edge.id; - if(edges[n].next_in!=-1) + if(edges[n].next_in!=-1) { edges[edges[n].next_in].prev_in = edges[n].prev_in; - if(edges[n].prev_in!=-1) + } + + if(edges[n].prev_in!=-1) { edges[edges[n].prev_in].next_in = edges[n].next_in; - else nodes[edges[n].head].first_in = edges[n].next_in; + } else { + nodes[edges[n].head].first_in = edges[n].next_in; + } + - if(edges[n].next_out!=-1) + if(edges[n].next_out!=-1) { edges[edges[n].next_out].prev_out = edges[n].prev_out; - if(edges[n].prev_out!=-1) + } + + if(edges[n].prev_out!=-1) { edges[edges[n].prev_out].next_out = edges[n].next_out; - else nodes[edges[n].tail].first_out = edges[n].next_out; + } else { + nodes[edges[n].tail].first_out = edges[n].next_out; + } edges[n].next_in = first_free_edge; first_free_edge = n; - //Update dynamic maps - Edge e; e.n=n; - edge_maps.erase(e); - } - - public: - - void erase(Node nn) { - int n=nn.n; - - int m; - while((m=nodes[n].first_in)!=-1) eraseEdge(m); - while((m=nodes[n].first_out)!=-1) eraseEdge(m); - - if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev; - if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next; - else first_node = nodes[n].next; - - nodes[n].next = first_free_node; - first_free_node = n; - - //Update dynamic maps - node_maps.erase(nn); - - } - - void erase(Edge e) { eraseEdge(e.n); } void clear() { - edge_maps.clear(); edges.clear(); - node_maps.clear(); nodes.clear(); - first_node=first_free_node=first_free_edge=-1; - } - - class Node { - friend class ListGraph; - template friend class NodeMap; - - friend class Edge; - friend class OutEdgeIt; - friend class InEdgeIt; - friend class SymEdge; - - protected: - int n; - friend int ListGraph::id(Node v); - Node(int nn) {n=nn;} - public: - Node() {} - Node (Invalid) { n=-1; } - bool operator==(const Node i) const {return n==i.n;} - bool operator!=(const Node i) const {return n!=i.n;} - bool operator<(const Node i) const {return nnodes[n].next; - return *this; - } - // ///Validity check - // operator bool() { return Node::operator bool(); } - }; - - class Edge { - friend class ListGraph; - template friend class EdgeMap; - - friend class SymListGraph; - - friend class Node; - friend class NodeIt; - protected: - int n; - friend int ListGraph::id(Edge e); - - public: - /// An Edge with id \c n. - - /// \bug It should be - /// obtained by a member function of the Graph. - Edge(int nn) {n=nn;} - - Edge() { } - Edge (Invalid) { n=-1; } - bool operator==(const Edge i) const {return n==i.n;} - bool operator!=(const Edge i) const {return n!=i.n;} - bool operator<(const Edge i) const {return nedges[n].next_in!=-1) n=G->edges[n].next_in; - else { - int nn; - for(nn=G->nodes[G->edges[n].head].next; - nn!=-1 && G->nodes[nn].first_in == -1; - nn = G->nodes[nn].next) ; - n = (nn==-1)?-1:G->nodes[nn].first_in; - } - return *this; - } - // ///Validity check - // operator bool() { return Edge::operator bool(); } - }; - - class OutEdgeIt : public Edge { - const ListGraph *G; - friend class ListGraph; - public: - OutEdgeIt() : Edge() { } - OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } - OutEdgeIt (Invalid i) : Edge(i) { } - - OutEdgeIt(const ListGraph& _G,const Node v) - : Edge(_G.nodes[v.n].first_out), G(&_G) {} - OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; } - // ///Validity check - // operator bool() { return Edge::operator bool(); } - }; - - class InEdgeIt : public Edge { - const ListGraph *G; - friend class ListGraph; - public: - InEdgeIt() : Edge() { } - InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } - InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const ListGraph& _G,Node v) - : Edge(_G.nodes[v.n].first_in), G(&_G) { } - InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } - // ///Validity check - // operator bool() { return Edge::operator bool(); } - }; - }; - - ///Graph for bidirectional edges. - - ///The purpose of this graph structure is to handle graphs - ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair - ///of oppositely directed edges. - ///There is a new edge map type called - ///\ref lemon::SymListGraph::SymEdgeMap "SymEdgeMap" - ///that complements this - ///feature by - ///storing shared values for the edge pairs. The usual - ///\ref lemon::skeleton::StaticGraph::EdgeMap "EdgeMap" - ///can be used - ///as well. - /// - ///The oppositely directed edge can also be obtained easily - ///using \ref lemon::SymListGraph::opposite() "opposite()" member function. - /// - ///Here erase(Edge) deletes a pair of edges. - /// - ///\todo this date structure need some reconsiderations. Maybe it - ///should be implemented independently from ListGraph. - /* - class SymListGraph : public ListGraph - { - public: - - typedef SymListGraph Graph; - - // Create symmetric map registry. - CREATE_SYM_EDGE_MAP_REGISTRY; - // Create symmetric edge map. - CREATE_SYM_EDGE_MAP(ArrayMap); - - SymListGraph() : ListGraph() { } - SymListGraph(const ListGraph &_g) : ListGraph(_g) { } - ///Adds a pair of oppositely directed edges to the graph. - Edge addEdge(Node u, Node v) - { - Edge e = ListGraph::addEdge(u,v); - Edge f = ListGraph::addEdge(v,u); - sym_edge_maps.add(e); - sym_edge_maps.add(f); - - return e; - } - - void erase(Node n) { ListGraph::erase(n);} - ///The oppositely directed edge. - - ///Returns the oppositely directed - ///pair of the edge \c e. - static Edge opposite(Edge e) - { - Edge f; - f.n = e.n - 2*(e.n%2) + 1; - return f; - } - - ///Removes a pair of oppositely directed edges to the graph. - void erase(Edge e) { - Edge f = opposite(e); - sym_edge_maps.erase(e); - sym_edge_maps.erase(f); - ListGraph::erase(f); - ListGraph::erase(e); - } - };*/ - - class SymListGraph : public ListGraph { - typedef ListGraph Parent; - public: - - typedef SymListGraph Graph; - - typedef ListGraph::Node Node; - typedef ListGraph::NodeIt NodeIt; - - class SymEdge; - class SymEdgeIt; - - class Edge; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; - - template - class NodeMap : public Parent::NodeMap { - public: - NodeMap(const SymListGraph& g) - : SymListGraph::Parent::NodeMap(g) {} - NodeMap(const SymListGraph& g, Value v) - : SymListGraph::Parent::NodeMap(g, v) {} - template - NodeMap(const NodeMap& copy) - : SymListGraph::Parent::NodeMap(copy) { } - }; - - template - class SymEdgeMap : public Parent::EdgeMap { - public: - typedef SymEdge KeyType; - - SymEdgeMap(const SymListGraph& g) - : SymListGraph::Parent::EdgeMap(g) {} - SymEdgeMap(const SymListGraph& g, Value v) - : SymListGraph::Parent::EdgeMap(g, v) {} - template - SymEdgeMap(const SymEdgeMap& copy) - : SymListGraph::Parent::EdgeMap(copy) { } - - }; - - // Create edge map registry. - CREATE_EDGE_MAP_REGISTRY; - // Create edge maps. - CREATE_EDGE_MAP(ArrayMap); - - class Edge { - friend class SymListGraph; - friend class SymListGraph::EdgeIt; - friend class SymListGraph::OutEdgeIt; - friend class SymListGraph::InEdgeIt; - - protected: - int id; - - Edge(int pid) { id = pid; } - - public: - /// An Edge with id \c n. - - Edge() { } - Edge (Invalid) { id = -1; } - - operator SymEdge(){ return SymEdge(id >> 1);} - - bool operator==(const Edge i) const {return id == i.id;} - bool operator!=(const Edge i) const {return id != i.id;} - bool operator<(const Edge i) const {return id < i.id;} - // ///Validity check - // operator bool() { return n!=-1; } - }; - - class SymEdge : public ListGraph::Edge { - friend class SymListGraph; - friend class SymListGraph::Edge; - typedef ListGraph::Edge Parent; - - protected: - SymEdge(int pid) : Parent(pid) {} - public: - - SymEdge() { } - SymEdge(const ListGraph::Edge& i) : Parent(i) {} - SymEdge (Invalid) : Parent(INVALID) {} - - }; - - class OutEdgeIt { - Parent::OutEdgeIt out; - Parent::InEdgeIt in; - public: - OutEdgeIt() {} - OutEdgeIt(const SymListGraph& g, Edge e) { - if ((e.id & 1) == 0) { - out = Parent::OutEdgeIt(g, SymEdge(e)); - in = Parent::InEdgeIt(g, g.tail(e)); - } else { - out = Parent::OutEdgeIt(INVALID); - in = Parent::InEdgeIt(g, SymEdge(e)); - } - } - OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } - - OutEdgeIt(const SymListGraph& g, const Node v) - : out(g, v), in(g, v) {} - OutEdgeIt &operator++() { - if (out != INVALID) { - ++out; - } else { - ++in; - } - return *this; - } - - operator Edge() const { - if (out == INVALID && in == INVALID) return INVALID; - return out != INVALID ? forward(out) : backward(in); - } - - bool operator==(const Edge i) const {return Edge(*this) == i;} - bool operator!=(const Edge i) const {return Edge(*this) != i;} - bool operator<(const Edge i) const {return Edge(*this) < i;} - }; - - class InEdgeIt { - Parent::OutEdgeIt out; - Parent::InEdgeIt in; - public: - InEdgeIt() {} - InEdgeIt(const SymListGraph& g, Edge e) { - if ((e.id & 1) == 0) { - out = Parent::OutEdgeIt(g, SymEdge(e)); - in = Parent::InEdgeIt(g, g.tail(e)); - } else { - out = Parent::OutEdgeIt(INVALID); - in = Parent::InEdgeIt(g, SymEdge(e)); - } - } - InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } - - InEdgeIt(const SymListGraph& g, const Node v) - : out(g, v), in(g, v) {} - - InEdgeIt &operator++() { - if (out != INVALID) { - ++out; - } else { - ++in; - } - return *this; - } - - operator Edge() const { - if (out == INVALID && in == INVALID) return INVALID; - return out != INVALID ? backward(out) : forward(in); - } - - bool operator==(const Edge i) const {return Edge(*this) == i;} - bool operator!=(const Edge i) const {return Edge(*this) != i;} - bool operator<(const Edge i) const {return Edge(*this) < i;} - }; - - class SymEdgeIt : public Parent::EdgeIt { - - public: - SymEdgeIt() {} - - SymEdgeIt(const SymListGraph& g) - : SymListGraph::Parent::EdgeIt(g) {} - - SymEdgeIt(const SymListGraph& g, SymEdge e) - : SymListGraph::Parent::EdgeIt(g, e) {} - - SymEdgeIt(Invalid i) - : SymListGraph::Parent::EdgeIt(INVALID) {} - - SymEdgeIt& operator++() { - SymListGraph::Parent::EdgeIt::operator++(); - return *this; - } - - operator SymEdge() const { - return SymEdge - (static_cast(*this)); - } - bool operator==(const SymEdge i) const {return SymEdge(*this) == i;} - bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;} - bool operator<(const SymEdge i) const {return SymEdge(*this) < i;} - }; - - class EdgeIt { - SymEdgeIt it; - bool fw; - public: - EdgeIt(const SymListGraph& g) : it(g), fw(true) {} - EdgeIt (Invalid i) : it(i) { } - EdgeIt(const SymListGraph& g, Edge e) - : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { } - EdgeIt() { } - EdgeIt& operator++() { - fw = !fw; - if (fw) ++it; - return *this; - } - operator Edge() const { - if (it == INVALID) return INVALID; - return fw ? forward(it) : backward(it); - } - bool operator==(const Edge i) const {return Edge(*this) == i;} - bool operator!=(const Edge i) const {return Edge(*this) != i;} - bool operator<(const Edge i) const {return Edge(*this) < i;} - - }; - - ///Number of nodes. - int nodeNum() const { return Parent::nodeNum(); } - ///Number of edges. - int edgeNum() const { return 2*Parent::edgeNum(); } - ///Number of symmetric edges. - int symEdgeNum() const { return Parent::edgeNum(); } - - ///Set the expected maximum number of edges. - - ///With this function, it is possible to set the expected number of edges. - ///The use of this fasten the building of the graph and makes - ///it possible to avoid the superfluous memory allocation. - void reserveSymEdge(int n) { Parent::reserveEdge(n); }; - - /// Maximum node ID. - - /// Maximum node ID. - ///\sa id(Node) - int maxNodeId() const { return Parent::maxNodeId(); } - /// Maximum edge ID. - - /// Maximum edge ID. - ///\sa id(Edge) - int maxEdgeId() const { return 2*Parent::maxEdgeId(); } - /// Maximum symmetric edge ID. - - /// Maximum symmetric edge ID. - ///\sa id(SymEdge) - int maxSymEdgeId() const { return Parent::maxEdgeId(); } - - - Node tail(Edge e) const { - return (e.id & 1) == 0 ? - Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e)); - } - - Node head(Edge e) const { - return (e.id & 1) == 0 ? - Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e)); - } - - Node tail(SymEdge e) const { - return Parent::tail(e); - } - - Node head(SymEdge e) const { - return Parent::head(e); - } - - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - SymEdgeIt& first(SymEdgeIt& e) const { - e=SymEdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } - - /// Node ID. - - /// The ID of a valid Node is a nonnegative integer not greater than - /// \ref maxNodeId(). The range of the ID's is not surely continuous - /// and the greatest node ID can be actually less then \ref maxNodeId(). - /// - /// The ID of the \ref INVALID node is -1. - ///\return The ID of the node \c v. - static int id(Node v) { return Parent::id(v); } - /// Edge ID. - - /// The ID of a valid Edge is a nonnegative integer not greater than - /// \ref maxEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxEdgeId(). - /// - /// The ID of the \ref INVALID edge is -1. - ///\return The ID of the edge \c e. - static int id(Edge e) { return e.id; } - - /// The ID of a valid SymEdge is a nonnegative integer not greater than - /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxSymEdgeId(). - /// - /// The ID of the \ref INVALID symmetric edge is -1. - ///\return The ID of the edge \c e. - static int id(SymEdge e) { return Parent::id(e); } - - /// Adds a new node to the graph. - - /// \warning It adds the new node to the front of the list. - /// (i.e. the lastly added node becomes the first.) - Node addNode() { - return Parent::addNode(); - } - - SymEdge addEdge(Node u, Node v) { - SymEdge se = Parent::addEdge(u, v); - edge_maps.add(forward(se)); - edge_maps.add(backward(se)); - return se; - } - - /// Finds an edge between two nodes. - - /// Finds an edge from node \c u to node \c v. - /// - /// If \c prev is \ref INVALID (this is the default value), then - /// It finds the first edge from \c u to \c v. Otherwise it looks for - /// the next edge from \c u to \c v after \c prev. - /// \return The found edge or INVALID if there is no such an edge. - Edge findEdge(Node u, Node v, Edge prev = INVALID) - { - if (prev == INVALID || id(prev) & 1 == 0) { - SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); - if (se != INVALID) return forward(se); - } else { - SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); - if (se != INVALID) return backward(se); - } - return INVALID; - } - -// /// Finds an symmetric edge between two nodes. - -// /// Finds an symmetric edge from node \c u to node \c v. -// /// -// /// If \c prev is \ref INVALID (this is the default value), then -// /// It finds the first edge from \c u to \c v. Otherwise it looks for -// /// the next edge from \c u to \c v after \c prev. -// /// \return The found edge or INVALID if there is no such an edge. - -// SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID) -// { -// if (prev == INVALID || id(prev) & 1 == 0) { -// SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); -// if (se != INVALID) return se; -// } else { -// SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); -// if (se != INVALID) return se; -// } -// return INVALID; -// } - - public: - - void erase(Node n) { - for (OutEdgeIt it(*this, n); it != INVALID; ++it) { - edge_maps.erase(it); - edge_maps.erase(opposite(it)); - } - Parent::erase(n); - } - - void erase(SymEdge e) { - edge_maps.erase(forward(e)); - edge_maps.erase(backward(e)); - Parent::erase(e); - }; - - void clear() { - edge_maps.clear(); - Parent::clear(); - } - - static Edge opposite(Edge e) { - return Edge(id(e) ^ 1); - } - - static Edge forward(SymEdge e) { - return Edge(id(e) << 1); - } - - static Edge backward(SymEdge e) { - return Edge((id(e) << 1) | 1); + first_node = first_free_node = first_free_edge = -1; } }; - ///A graph class containing only nodes. + typedef AlterableGraphExtender AlterableListGraphBase; + typedef IterableGraphExtender IterableListGraphBase; + typedef IdMappableGraphExtender IdMappableListGraphBase; + typedef DefaultMappableGraphExtender MappableListGraphBase; + typedef ExtendableGraphExtender ExtendableListGraphBase; + typedef ClearableGraphExtender ClearableListGraphBase; + typedef ErasableGraphExtender ErasableListGraphBase; - ///This class implements a graph structure without edges. - ///The most useful application of this class is to be the node set of an - ///\ref EdgeSet class. - /// - ///It conforms to - ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept - ///with the exception that you cannot - ///add (or delete) edges. The usual edge iterators are exists, but they are - ///always \ref INVALID. - ///\sa skeleton::ExtendableGraph - ///\sa EdgeSet - class NodeSet { + typedef ErasableListGraphBase ListGraph; - //Nodes are double linked. - //The free nodes are only single linked using the "next" field. - struct NodeT - { - int first_in,first_out; - int prev, next; - // NodeT() {} - }; +} - std::vector nodes; - //The first node - int first_node; - //The first free node - int first_free_node; - - public: - typedef NodeSet Graph; - - class Node; - class Edge; + - public: - - class NodeIt; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; - - // Create node map registry. - CREATE_NODE_MAP_REGISTRY; - // Create node maps. - CREATE_NODE_MAP(ArrayMap); - - /// Creating empty map structure for edges. - template - class EdgeMap { - public: - EdgeMap(const Graph&) {} - EdgeMap(const Graph&, const Value&) {} - - EdgeMap(const EdgeMap&) {} - template EdgeMap(const CMap&) {} - - EdgeMap& operator=(const EdgeMap&) {} - template EdgeMap& operator=(const CMap&) {} - - class ConstIterator { - public: - bool operator==(const ConstIterator&) {return true;} - bool operator!=(const ConstIterator&) {return false;} - }; - - typedef ConstIterator Iterator; - - Iterator begin() { return Iterator();} - Iterator end() { return Iterator();} - - ConstIterator begin() const { return ConstIterator();} - ConstIterator end() const { return ConstIterator();} - - }; - - public: - - ///Default constructor - NodeSet() - : nodes(), first_node(-1), first_free_node(-1) {} - ///Copy constructor - NodeSet(const NodeSet &_g) - : nodes(_g.nodes), first_node(_g.first_node), - first_free_node(_g.first_free_node) {} - - ///Number of nodes. - int nodeNum() const { return nodes.size(); } - ///Number of edges. - int edgeNum() const { return 0; } - - /// Maximum node ID. - - /// Maximum node ID. - ///\sa id(Node) - int maxNodeId() const { return nodes.size()-1; } - /// Maximum edge ID. - - /// Maximum edge ID. - ///\sa id(Edge) - int maxEdgeId() const { return 0; } - - Node tail(Edge e) const { return INVALID; } - Node head(Edge e) const { return INVALID; } - - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } - - /// Node ID. - - /// The ID of a valid Node is a nonnegative integer not greater than - /// \ref maxNodeId(). The range of the ID's is not surely continuous - /// and the greatest node ID can be actually less then \ref maxNodeId(). - /// - /// The ID of the \ref INVALID node is -1. - ///\return The ID of the node \c v. - static int id(Node v) { return v.n; } - /// Edge ID. - - /// The ID of a valid Edge is a nonnegative integer not greater than - /// \ref maxEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxEdgeId(). - /// - /// The ID of the \ref INVALID edge is -1. - ///\return The ID of the edge \c e. - static int id(Edge e) { return -1; } - - /// Adds a new node to the graph. - - /// \warning It adds the new node to the front of the list. - /// (i.e. the lastly added node becomes the first.) - Node addNode() { - int n; - - if(first_free_node==-1) - { - n = nodes.size(); - nodes.push_back(NodeT()); - } - else { - n = first_free_node; - first_free_node = nodes[n].next; - } - - nodes[n].next = first_node; - if(first_node != -1) nodes[first_node].prev = n; - first_node = n; - nodes[n].prev = -1; - - nodes[n].first_in = nodes[n].first_out = -1; - - Node nn; nn.n=n; - - //Update dynamic maps - node_maps.add(nn); - - return nn; - } - - void erase(Node nn) { - int n=nn.n; - - if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev; - if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next; - else first_node = nodes[n].next; - - nodes[n].next = first_free_node; - first_free_node = n; - - //Update dynamic maps - node_maps.erase(nn); - } - - - Edge findEdge(Node u,Node v, Edge prev = INVALID) - { - return INVALID; - } - - void clear() { - node_maps.clear(); - nodes.clear(); - first_node = first_free_node = -1; - } - - class Node { - friend class NodeSet; - template friend class NodeMap; - - friend class Edge; - friend class OutEdgeIt; - friend class InEdgeIt; - - protected: - int n; - friend int NodeSet::id(Node v); - Node(int nn) {n=nn;} - public: - Node() {} - Node (Invalid i) { n=-1; } - bool operator==(const Node i) const {return n==i.n;} - bool operator!=(const Node i) const {return n!=i.n;} - bool operator<(const Node i) const {return nnodes[n].next; - return *this; - } - }; - - class Edge { - public: - Edge() { } - Edge (Invalid) { } - bool operator==(const Edge i) const {return true;} - bool operator!=(const Edge i) const {return false;} - bool operator<(const Edge i) const {return false;} - }; - - class EdgeIt : public Edge { - public: - EdgeIt(const NodeSet& G) : Edge() { } - EdgeIt(const NodeSet&, Edge) : Edge() { } - EdgeIt (Invalid i) : Edge(i) { } - EdgeIt() : Edge() { } - EdgeIt operator++() { return INVALID; } - }; - - class OutEdgeIt : public Edge { - friend class NodeSet; - public: - OutEdgeIt() : Edge() { } - OutEdgeIt(const NodeSet&, Edge) : Edge() { } - OutEdgeIt (Invalid i) : Edge(i) { } - OutEdgeIt(const NodeSet& G,const Node v) : Edge() {} - OutEdgeIt operator++() { return INVALID; } - }; - - class InEdgeIt : public Edge { - friend class NodeSet; - public: - InEdgeIt() : Edge() { } - InEdgeIt(const NodeSet&, Edge) : Edge() { } - InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const NodeSet& G,Node v) :Edge() {} - InEdgeIt operator++() { return INVALID; } - }; - - }; - - - - ///Graph structure using a node set of another graph. - - ///This structure can be used to establish another graph over a node set - /// of an existing one. The node iterator will go through the nodes of the - /// original graph, and the NodeMap's of both graphs will convert to - /// each other. - /// - ///\warning Adding or deleting nodes from the graph is not safe if an - ///\ref EdgeSet is currently attached to it! - /// - ///\todo Make it possible to add/delete edges from the base graph - ///(and from \ref EdgeSet, as well) - /// - ///\param GG The type of the graph which shares its node set with this class. - ///Its interface must conform to the - ///\ref skeleton::StaticGraph "StaticGraph" concept. - /// - ///It conforms to the - ///\ref skeleton::ExtendableGraph "ExtendableGraph" concept. - ///\sa skeleton::ExtendableGraph. - ///\sa NodeSet. - template - class EdgeSet { - - typedef GG NodeGraphType; - - NodeGraphType &G; - - public: - - class Node; - class Edge; - class OutEdgeIt; - class InEdgeIt; - class SymEdge; - - typedef EdgeSet Graph; - - int id(Node v) const; - - class Node : public NodeGraphType::Node { - friend class EdgeSet; - - friend class Edge; - friend class OutEdgeIt; - friend class InEdgeIt; - friend class SymEdge; - - public: - friend int EdgeSet::id(Node v) const; - public: - Node() : NodeGraphType::Node() {} - Node (Invalid i) : NodeGraphType::Node(i) {} - Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {} - }; - - class NodeIt : public NodeGraphType::NodeIt { - friend class EdgeSet; - public: - NodeIt() : NodeGraphType::NodeIt() { } - NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { } - NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} - NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { } - NodeIt(const typename NodeGraphType::NodeIt &n) - : NodeGraphType::NodeIt(n) {} - - operator Node() { return Node(*this);} - NodeIt &operator++() - { this->NodeGraphType::NodeIt::operator++(); return *this;} - }; - - private: - //Edges are double linked. - //The free edges are only single linked using the "next_in" field. - struct NodeT - { - int first_in,first_out; - NodeT() : first_in(-1), first_out(-1) { } - }; - - struct EdgeT - { - Node head, tail; - int prev_in, prev_out; - int next_in, next_out; - }; - - - typename NodeGraphType::template NodeMap nodes; - - std::vector edges; - //The first free edge - int first_free_edge; - - public: - - class Node; - class Edge; - - class NodeIt; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; - - - // Create edge map registry. - CREATE_EDGE_MAP_REGISTRY; - // Create edge maps. - CREATE_EDGE_MAP(ArrayMap); - - // Import node maps from the NodeGraphType. - IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph); - - - public: - - ///Constructor - - ///Construates a new graph based on the nodeset of an existing one. - ///\param _G the base graph. - explicit EdgeSet(NodeGraphType &_G) - : G(_G), nodes(_G), edges(), - first_free_edge(-1) {} - ///Copy constructor - - ///Makes a copy of an EdgeSet. - ///It will be based on the same graph. - explicit EdgeSet(const EdgeSet &_g) - : G(_g.G), nodes(_g.G), edges(_g.edges), - first_free_edge(_g.first_free_edge) {} - - ///Number of nodes. - int nodeNum() const { return G.nodeNum(); } - ///Number of edges. - int edgeNum() const { return edges.size(); } - - /// Maximum node ID. - - /// Maximum node ID. - ///\sa id(Node) - int maxNodeId() const { return G.maxNodeId(); } - /// Maximum edge ID. - - /// Maximum edge ID. - ///\sa id(Edge) - int maxEdgeId() const { return edges.size()-1; } - - Node tail(Edge e) const { return edges[e.n].tail; } - Node head(Edge e) const { return edges[e.n].head; } - - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } - - /// Node ID. - - /// The ID of a valid Node is a nonnegative integer not greater than - /// \ref maxNodeId(). The range of the ID's is not surely continuous - /// and the greatest node ID can be actually less then \ref maxNodeId(). - /// - /// The ID of the \ref INVALID node is -1. - ///\return The ID of the node \c v. - int id(Node v) { return G.id(v); } - /// Edge ID. - - /// The ID of a valid Edge is a nonnegative integer not greater than - /// \ref maxEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxEdgeId(). - /// - /// The ID of the \ref INVALID edge is -1. - ///\return The ID of the edge \c e. - static int id(Edge e) { return e.n; } - - /// Adds a new node to the graph. - Node addNode() { return G.addNode(); } - - Edge addEdge(Node u, Node v) { - int n; - - if(first_free_edge==-1) - { - n = edges.size(); - edges.push_back(EdgeT()); - } - else { - n = first_free_edge; - first_free_edge = edges[n].next_in; - } - - edges[n].tail = u; edges[n].head = v; - - edges[n].next_out = nodes[u].first_out; - if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n; - edges[n].next_in = nodes[v].first_in; - if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n; - edges[n].prev_in = edges[n].prev_out = -1; - - nodes[u].first_out = nodes[v].first_in = n; - - Edge e; e.n=n; - - //Update dynamic maps - edge_maps.add(e); - - return e; - } - - /// Finds an edge between two nodes. - - /// Finds an edge from node \c u to node \c v. - /// - /// If \c prev is \ref INVALID (this is the default value), then - /// It finds the first edge from \c u to \c v. Otherwise it looks for - /// the next edge from \c u to \c v after \c prev. - /// \return The found edge or INVALID if there is no such an edge. - Edge findEdge(Node u,Node v, Edge prev = INVALID) - { - int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out; - while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out; - prev.n=e; - return prev; - } - - private: - void eraseEdge(int n) { - - if(edges[n].next_in!=-1) - edges[edges[n].next_in].prev_in = edges[n].prev_in; - if(edges[n].prev_in!=-1) - edges[edges[n].prev_in].next_in = edges[n].next_in; - else nodes[edges[n].head].first_in = edges[n].next_in; - - if(edges[n].next_out!=-1) - edges[edges[n].next_out].prev_out = edges[n].prev_out; - if(edges[n].prev_out!=-1) - edges[edges[n].prev_out].next_out = edges[n].next_out; - else nodes[edges[n].tail].first_out = edges[n].next_out; - - edges[n].next_in = first_free_edge; - first_free_edge = -1; - - //Update dynamic maps - Edge e; e.n = n; - edge_maps.erase(e); - } - - public: - - void erase(Edge e) { eraseEdge(e.n); } - - ///Clear all edges. (Doesn't clear the nodes!) - void clear() { - edge_maps.clear(); - edges.clear(); - first_free_edge=-1; - } - - - class Edge { - public: - friend class EdgeSet; - template friend class EdgeMap; - - friend class Node; - friend class NodeIt; - protected: - int n; - friend int EdgeSet::id(Edge e) const; - - Edge(int nn) {n=nn;} - public: - Edge() { } - Edge (Invalid) { n=-1; } - bool operator==(const Edge i) const {return n==i.n;} - bool operator!=(const Edge i) const {return n!=i.n;} - bool operator<(const Edge i) const {return n friend class EdgeMap; - - const EdgeSet *G; - public: - EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) { - NodeIt m; - for(G->first(m); - m!=INVALID && G->nodes[m].first_in == -1; ++m); - ///\bug AJJAJ! This is a non sense!!!!!!! - this->n = m!=INVALID?-1:G->nodes[m].first_in; - } - EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } - EdgeIt (Invalid i) : Edge(i) { } - EdgeIt() : Edge() { } - ///. - - ///\bug UNIMPLEMENTED!!!!! - // - EdgeIt &operator++() { - return *this; - } - }; - - class OutEdgeIt : public Edge { - const EdgeSet *G; - friend class EdgeSet; - public: - OutEdgeIt() : Edge() { } - OutEdgeIt (Invalid i) : Edge(i) { } - OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } - - OutEdgeIt(const EdgeSet& _G,const Node v) : - Edge(_G.nodes[v].first_out), G(&_G) { } - OutEdgeIt &operator++() { - Edge::n = G->edges[Edge::n].next_out; - return *this; - } - }; - - class InEdgeIt : public Edge { - const EdgeSet *G; - friend class EdgeSet; - public: - InEdgeIt() : Edge() { } - InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } - InEdgeIt(const EdgeSet& _G,Node v) - : Edge(_G.nodes[v].first_in), G(&_G) { } - InEdgeIt &operator++() { - Edge::n = G->edges[Edge::n].next_in; - return *this; - } - }; - - }; - - template - inline int EdgeSet::id(Node v) const { return G.id(v); } - -/// @} - -} //namespace lemon - -#endif //LEMON_LIST_GRAPH_H +#endif diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/map_registry.h --- a/src/lemon/map_registry.h Mon Oct 25 13:29:46 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,359 +0,0 @@ -/* -*- C++ -*- - * src/lemon/map_registry.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2004 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_REGISTRY_H -#define LEMON_MAP_REGISTRY_H - -#include - -///\ingroup graphmapfactory -///\file -///\brief Map registry for graph maps. - -namespace lemon { - - /// \addtogroup graphmapfactory - /// @{ - - /// Map registry for graph maps. - - /** - * Registry class to register edge or node maps into the graph. The - * registry helps you to implement an observer pattern. If you add - * or erase an edge or node you must notify all the maps about the - * event. - * - * \param G The graph type to register maps. - * \param K The key type of the maps registered into the registry. - * \param KIt The key iterator type iterates on the keys. - * - * \author Balazs Dezso - */ - - template - class MapRegistry { - public: - typedef G Graph; - typedef K KeyType; - typedef KIt KeyIt; - - /// MapBase is the base class of the dynamic maps. - - /** - * MapBase is the base class of the dynamic maps. - * It defines the core modification operations on the maps and - * implements some helper functions. - */ - class MapBase { - public: - typedef G Graph; - typedef K KeyType; - typedef KIt KeyIt; - - typedef MapRegistry Registry; - - friend class MapRegistry; - - /// Default constructor. - - /** - * Default constructor for MapBase. - */ - - MapBase() : graph(0), registry(0) {} - - /// Constructor to register map into a graph registry. - - /** - * Simple constructor to register dynamic map into a graph registry. - */ - - MapBase(const Graph& g, Registry& r) : graph(&g), registry(0) { - r.attach(*this); - } - - /// Copy constructor. - - /** - * Copy constructor to register into the registry. - * If the copiable map is registered into a registry - * the construated map will be registered to the same registry. - */ - - MapBase(const MapBase& copy) : graph(copy.graph), registry(0) { - if (copy.registry) { - copy.registry->attach(*this); - } - } - - /// Assign operator. - - /** - * Assign operator. This member detach first the map - * from the current registry and then it attach to the - * copiable map's registry if it exists. - */ - const MapBase& operator=(const MapBase& copy) { - if (registry) { - registry->detach(*this); - } - graph = copy.graph; - if (copy.registry) { - copy.registry->attach(*this); - } - return *this; - } - - /// Destructor - - /** - * This member detach the map from the its registry if the - * registry exists. - */ - - virtual ~MapBase() { - if (registry) { - registry->detach(*this); - } - } - - /// The graph of the map. - - /* - * Returns the graph that the map belongs to. - */ - - const Graph* getGraph() const { return graph; } - - protected: - - const Graph* graph; - Registry* registry; - - int registry_index; - - protected: - - /// Helper function to implement constructors in the subclasses. - - /** - * Helper function to implement constructors in the subclasses. - * It adds all of the nodes or edges to the map via the - * \ref MapRegistry::MapBase::add add - * member function. - */ - - virtual void init() { - for (KeyIt it(*graph); it != INVALID; ++it) { - add(it); - } - } - - - /// Helper function to implement destructors in the subclasses. - - /** - * Helper function to implement destructors in the subclasses. - * It erases all of the nodes or edges of the map via the - * \ref MapRegistry::MapBase::erase erase - * member function. It can be used by the clear function also. - */ - - virtual void destroy() { - for (KeyIt it(*getGraph()); it != INVALID; ++it) { - erase(it); - } - } - - /// The member function to add new node or edge to the map. - - /** - The add member function should be overloaded in the subclasses. - \e Add extends the map with the new node or edge. - */ - - virtual void add(const KeyType&) = 0; - - - /// The member function to erase a node or edge from the map. - - /** - The erase member function should be overloaded in the subclasses. - \e Erase removes the node or edge from the map. - */ - - virtual void erase(const KeyType&) = 0; - - /** - * The clear member function should be overloaded in the subclasses. - * \e Clear makes empty the data structure. - */ - - virtual void clear() = 0; - - /// Exception class to throw at unsupported operation. - - /** - * Exception class to throw at unsupported operation. - * If the map does not support erasing or adding new - * node or key it must be throwed. - */ - - class NotSupportedOperationException {}; - - }; - - protected: - - - typedef std::vector Container; - - Container container; - - - public: - - /// Default constructor. - - /** - * Default constructor of the \e MapRegistry. - * It creates an empty registry. - */ - MapRegistry() {} - - /// Copy Constructor of the MapRegistry. - - /** - * Copy constructor of the \e MapRegistry. - * The new registry does not steal - * the maps from the copiable registry. - * The new registry will be empty. - */ - MapRegistry(const MapRegistry&) {} - - /// Assign operator. - - /** - * Assign operator. This registry does not steal the maps - * from the copiable registry. This registry will be an empty registry. - * This operator will be called when a graph is assigned. - */ - MapRegistry& operator=(const MapRegistry&) { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->clear(); - (*it)->graph = 0; - (*it)->registry = 0; - } - } - - /// Destructor. - - /** - * Destructor of the MapRegistry. It makes empty the attached map - * first then detachs them. - */ - ~MapRegistry() { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->clear(); - (*it)->registry = 0; - (*it)->graph = 0; - } - } - - - public: - - /// Attachs a map to the \e MapRegistry. - - /** - * Attachs a map into thr registry. If the map has been attached - * into an other registry it is detached from that automaticly. - */ - void attach(MapBase& map) { - if (map.registry) { - map.registry->detach(map); - } - container.push_back(&map); - map.registry = this; - map.registry_index = container.size()-1; - } - - /// Detachs a map from the \e MapRegistry. - - /** - * Detachs a map from the \e MapRegistry. - */ - void detach(MapBase& map) { - container.back()->registry_index = map.registry_index; - container[map.registry_index] = container.back(); - container.pop_back(); - map.registry = 0; - map.graph = 0; - } - - /// Notify all the registered maps about a Key added. - - /** - * Notify all the registered maps about a Key added. - * This member should be called whenever a node or edge - * is added to the graph. - */ - void add(const KeyType& key) { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->add(key); - } - } - - /// Notify all the registered maps about a Key erased. - - /** - * Notify all the registered maps about a Key erased. - * This member should be called whenever a node or edge - * is erased from the graph. - */ - void erase(const KeyType& key) { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->erase(key); - } - } - - - /// Notify all the registered maps about all the Keys are erased. - - /** - * Notify all the registered maps about the map should be cleared. - * This member should be called whenever all of the nodes or edges - * are erased from the graph. - */ - void clear() { - typename Container::iterator it; - for (it = container.begin(); it != container.end(); ++it) { - (*it)->clear(); - } - } - }; - - -/// @} - - -} - -#endif diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/mappable_graph_extender.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/mappable_graph_extender.h Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,97 @@ +// -*- c++ -*- + +#ifndef LEMON_MAPPABLE_GRAPH_EXTENDER_H +#define LEMON_MAPPABLE_GRAPH_EXTENDER_H + +namespace lemon { + + template class DynMap> + class MappableGraphExtender : public Base { + public: + + typedef MappableGraphExtender Graph; + typedef Base Parent; + + typedef typename Parent::Node Node; + typedef typename Parent::NodeIt NodeIt; + typedef typename Parent::NodeObserverRegistry NodeObserverRegistry; + + typedef typename Parent::Edge Edge; + typedef typename Parent::EdgeIt EdgeIt; + typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry; + + public: + + class NodeIdMap { + private: + const Graph* graph; + + public: + NodeIdMap(const Graph& g) : graph(&g) {} + + int operator[](const Node& node) { return graph->id(node); } + + int maxId() const {return graph->maxNodeId(); } + + }; + + // template + // friend class DynMap; + + class EdgeIdMap { + private: + const Graph* graph; + + public: + EdgeIdMap(const Graph& g) : graph(&g) {} + + int operator[](const Edge& edge) const { return graph->id(edge); } + + int maxId() const {return graph->maxEdgeId(); } + + }; + + // template + // friend class DynMap; + + public: + + template + class NodeMap + : public DynMap { + public: + typedef DynMap Parent; + + NodeMap(const Graph& g) + : Parent(g, g.Graph::Parent::getNodeObserverRegistry()) {} + NodeMap(const Graph& g, const Value& v) + : Parent(g, g.Graph::Parent::getNodeObserverRegistry(), v) {} + + }; + + template + class EdgeMap + : public DynMap { + public: + typedef DynMap Parent; + + EdgeMap(const Graph& g) + : Parent(g, g.Graph::Parent::getEdgeObserverRegistry()) {} + EdgeMap(const Graph& g, const Value& v) + : Parent(g, g.Graph::Parent::getEdgeObserverRegistry(), v) {} + + }; + + + }; + +} + +#endif + diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/preflow.h --- a/src/lemon/preflow.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/lemon/preflow.h Wed Oct 27 22:38:50 2004 +0000 @@ -140,7 +140,7 @@ Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, FlowMap& _flow) : g(&_G), s(_s), t(_t), capacity(&_capacity), - flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0), + flow(&_flow), n(countNodes(_G)), level(_G), excess(_G,0), flow_prop(NO_FLOW), status(AFTER_NOTHING) { } diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/skeletons/graph.h --- a/src/lemon/skeletons/graph.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/lemon/skeletons/graph.h Wed Oct 27 22:38:50 2004 +0000 @@ -23,6 +23,8 @@ #include #include +#include +#include namespace lemon { namespace skeleton { @@ -30,734 +32,883 @@ /// \addtogroup skeletons /// @{ - /// An empty static graph class. +// /// An empty static graph class. - /// This class provides all the common features of a graph structure, - /// however completely without implementations and real data structures - /// behind the interface. - /// All graph algorithms should compile with this class, but it will not - /// run properly, of course. - /// - /// It can be used for checking the interface compatibility, - /// or it can serve as a skeleton of a new graph structure. - /// - /// Also, you will find here the full documentation of a certain graph - /// feature, the documentation of a real graph imlementation - /// like @ref ListGraph or - /// @ref SmartGraph will just refer to this structure. - /// - /// \todo A pages describing the concept of concept description would - /// be nice. - class StaticGraph - { +// /// This class provides all the common features of a graph structure, +// /// however completely without implementations and real data structures +// /// behind the interface. +// /// All graph algorithms should compile with this class, but it will not +// /// run properly, of course. +// /// +// /// It can be used for checking the interface compatibility, +// /// or it can serve as a skeleton of a new graph structure. +// /// +// /// Also, you will find here the full documentation of a certain graph +// /// feature, the documentation of a real graph imlementation +// /// like @ref ListGraph or +// /// @ref SmartGraph will just refer to this structure. +// /// +// /// \todo A pages describing the concept of concept description would +// /// be nice. +// class StaticGraph +// { +// public: +// /// Defalult constructor. + +// /// Defalult constructor. +// /// +// StaticGraph() { } +// ///Copy consructor. + +// // ///\todo It is not clear, what we expect from a copy constructor. +// // ///E.g. How to assign the nodes/edges to each other? What about maps? +// // StaticGraph(const StaticGraph& g) { } + +// /// The base type of node iterators, +// /// or in other words, the trivial node iterator. + +// /// This is the base type of each node iterator, +// /// thus each kind of node iterator converts to this. +// /// More precisely each kind of node iterator should be inherited +// /// from the trivial node iterator. +// class Node { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// Node() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// Node(const Node&) { } + +// /// Invalid constructor \& conversion. + +// /// This constructor initializes the iterator to be invalid. +// /// \sa Invalid for more details. +// Node(Invalid) { } +// /// Equality operator + +// /// Two iterators are equal if and only if they point to the +// /// same object or both are invalid. +// bool operator==(Node) const { return true; } + +// /// Inequality operator + +// /// \sa operator==(Node n) +// /// +// bool operator!=(Node) const { return true; } + +// ///Comparison operator. + +// ///This is a strict ordering between the nodes. +// /// +// ///This ordering can be different from the order in which NodeIt +// ///goes through the nodes. +// ///\todo Possibly we don't need it. +// bool operator<(Node) const { return true; } +// }; + +// /// This iterator goes through each node. + +// /// This iterator goes through each node. +// /// Its usage is quite simple, for example you can count the number +// /// of nodes in graph \c g of type \c Graph like this: +// /// \code +// /// int count=0; +// /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count; +// /// \endcode +// class NodeIt : public Node { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// NodeIt() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// NodeIt(const NodeIt&) { } +// /// Invalid constructor \& conversion. + +// /// Initialize the iterator to be invalid. +// /// \sa Invalid for more details. +// NodeIt(Invalid) { } +// /// Sets the iterator to the first node. + +// /// Sets the iterator to the first node of \c g. +// /// +// NodeIt(const StaticGraph& g) { } +// /// Node -> NodeIt conversion. + +// /// Sets the iterator to the node of \c g pointed by the trivial +// /// iterator n. +// /// This feature necessitates that each time we +// /// iterate the edge-set, the iteration order is the same. +// NodeIt(const StaticGraph& g, const Node& n) { } +// /// Next node. + +// /// Assign the iterator to the next node. +// /// +// NodeIt& operator++() { return *this; } +// }; + + +// /// The base type of the edge iterators. + +// /// The base type of the edge iterators. +// /// +// class Edge { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// Edge() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// Edge(const Edge&) { } +// /// Initialize the iterator to be invalid. + +// /// Initialize the iterator to be invalid. +// /// +// Edge(Invalid) { } +// /// Equality operator + +// /// Two iterators are equal if and only if they point to the +// /// same object or both are invalid. +// bool operator==(Edge) const { return true; } +// /// Inequality operator + +// /// \sa operator==(Node n) +// /// +// bool operator!=(Edge) const { return true; } +// ///Comparison operator. + +// ///This is a strict ordering between the nodes. +// /// +// ///This ordering can be different from the order in which NodeIt +// ///goes through the nodes. +// ///\todo Possibly we don't need it. +// bool operator<(Edge) const { return true; } +// }; + +// /// This iterator goes trough the outgoing edges of a node. + +// /// This iterator goes trough the \e outgoing edges of a certain node +// /// of a graph. +// /// Its usage is quite simple, for example you can count the number +// /// of outgoing edges of a node \c n +// /// in graph \c g of type \c Graph as follows. +// /// \code +// /// int count=0; +// /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; +// /// \endcode + +// class OutEdgeIt : public Edge { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// OutEdgeIt() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// OutEdgeIt(const OutEdgeIt&) { } +// /// Initialize the iterator to be invalid. + +// /// Initialize the iterator to be invalid. +// /// +// OutEdgeIt(Invalid) { } +// /// This constructor sets the iterator to first outgoing edge. + +// /// This constructor set the iterator to the first outgoing edge of +// /// node +// ///@param n the node +// ///@param g the graph +// OutEdgeIt(const StaticGraph& g, const Node& n) { } +// /// Edge -> OutEdgeIt conversion + +// /// Sets the iterator to the value of the trivial iterator \c e. +// /// This feature necessitates that each time we +// /// iterate the edge-set, the iteration order is the same. +// OutEdgeIt(const StaticGraph& g, const Edge& e) { } +// ///Next outgoing edge + +// /// Assign the iterator to the next +// /// outgoing edge of the corresponding node. +// OutEdgeIt& operator++() { return *this; } +// }; + +// /// This iterator goes trough the incoming edges of a node. + +// /// This iterator goes trough the \e incoming edges of a certain node +// /// of a graph. +// /// Its usage is quite simple, for example you can count the number +// /// of outgoing edges of a node \c n +// /// in graph \c g of type \c Graph as follows. +// /// \code +// /// int count=0; +// /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; +// /// \endcode + +// class InEdgeIt : public Edge { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// InEdgeIt() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// InEdgeIt(const InEdgeIt&) { } +// /// Initialize the iterator to be invalid. + +// /// Initialize the iterator to be invalid. +// /// +// InEdgeIt(Invalid) { } +// /// This constructor sets the iterator to first incoming edge. + +// /// This constructor set the iterator to the first incoming edge of +// /// node +// ///@param n the node +// ///@param g the graph +// InEdgeIt(const StaticGraph& g, const Node& n) { } +// /// Edge -> InEdgeIt conversion + +// /// Sets the iterator to the value of the trivial iterator \c e. +// /// This feature necessitates that each time we +// /// iterate the edge-set, the iteration order is the same. +// InEdgeIt(const StaticGraph& g, const Edge& n) { } +// /// Next incoming edge + +// /// Assign the iterator to the next inedge of the corresponding node. +// /// +// InEdgeIt& operator++() { return *this; } +// }; +// /// This iterator goes through each edge. + +// /// This iterator goes through each edge of a graph. +// /// Its usage is quite simple, for example you can count the number +// /// of edges in a graph \c g of type \c Graph as follows: +// /// \code +// /// int count=0; +// /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; +// /// \endcode +// class EdgeIt : public Edge { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// EdgeIt() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// EdgeIt(const EdgeIt&) { } +// /// Initialize the iterator to be invalid. + +// /// Initialize the iterator to be invalid. +// /// +// EdgeIt(Invalid) { } +// /// This constructor sets the iterator to first edge. + +// /// This constructor set the iterator to the first edge of +// /// node +// ///@param g the graph +// EdgeIt(const StaticGraph& g) { } +// /// Edge -> EdgeIt conversion + +// /// Sets the iterator to the value of the trivial iterator \c e. +// /// This feature necessitates that each time we +// /// iterate the edge-set, the iteration order is the same. +// EdgeIt(const StaticGraph&, const Edge&) { } +// ///Next edge + +// /// Assign the iterator to the next +// /// edge of the corresponding node. +// EdgeIt& operator++() { return *this; } +// }; + +// /// First node of the graph. + +// /// \retval i the first node. +// /// \return the first node. +// /// +// NodeIt& first(NodeIt& i) const { return i; } + +// /// The first incoming edge. + +// /// The first incoming edge. +// /// +// InEdgeIt& first(InEdgeIt &i, Node) const { return i; } +// /// The first outgoing edge. + +// /// The first outgoing edge. +// /// +// OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } +// /// The first edge of the Graph. + +// /// The first edge of the Graph. +// /// +// EdgeIt& first(EdgeIt& i) const { return i; } + +// ///Gives back the head node of an edge. + +// ///Gives back the head node of an edge. +// /// +// Node head(Edge) const { return INVALID; } +// ///Gives back the tail node of an edge. + +// ///Gives back the tail node of an edge. +// /// +// Node tail(Edge) const { return INVALID; } + +// ///Gives back the \e id of a node. + +// ///\warning Not all graph structures provide this feature. +// /// +// ///\todo Should each graph provide \c id? +// int id(const Node&) const { return 0; } +// ///Gives back the \e id of an edge. + +// ///\warning Not all graph structures provide this feature. +// /// +// ///\todo Should each graph provide \c id? +// int id(const Edge&) const { return 0; } + +// ///\e + +// ///\todo Should it be in the concept? +// /// +// int nodeNum() const { return 0; } +// ///\e + +// ///\todo Should it be in the concept? +// /// +// int edgeNum() const { return 0; } + + +// ///Reference map of the nodes to type \c T. + +// /// \ingroup skeletons +// ///Reference map of the nodes to type \c T. +// /// \sa Reference +// /// \warning Making maps that can handle bool type (NodeMap) +// /// needs some extra attention! +// template class NodeMap : public ReferenceMap< Node, T > +// { +// public: + +// ///\e +// NodeMap(const StaticGraph&) { } +// ///\e +// NodeMap(const StaticGraph&, T) { } + +// ///Copy constructor +// template NodeMap(const NodeMap&) { } +// ///Assignment operator +// template NodeMap& operator=(const NodeMap&) +// { return *this; } +// }; + +// ///Reference map of the edges to type \c T. + +// /// \ingroup skeletons +// ///Reference map of the edges to type \c T. +// /// \sa Reference +// /// \warning Making maps that can handle bool type (EdgeMap) +// /// needs some extra attention! +// template class EdgeMap +// : public ReferenceMap +// { +// public: + +// ///\e +// EdgeMap(const StaticGraph&) { } +// ///\e +// EdgeMap(const StaticGraph&, T) { } + +// ///Copy constructor +// template EdgeMap(const EdgeMap&) { } +// ///Assignment operator +// template EdgeMap &operator=(const EdgeMap&) +// { return *this; } +// }; +// }; + +// struct DummyType { +// int value; +// DummyType() {} +// DummyType(int p) : value(p) {} +// DummyType& operator=(int p) { value = p; return *this;} +// }; + +// ///\brief Checks whether \c G meets the +// ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept +// template void checkCompileStaticGraph(Graph &G) +// { +// typedef typename Graph::Node Node; +// typedef typename Graph::NodeIt NodeIt; +// typedef typename Graph::Edge Edge; +// typedef typename Graph::EdgeIt EdgeIt; +// typedef typename Graph::InEdgeIt InEdgeIt; +// typedef typename Graph::OutEdgeIt OutEdgeIt; + +// { +// Node i; Node j(i); Node k(INVALID); +// i=j; +// bool b; b=true; +// b=(i==INVALID); b=(i!=INVALID); +// b=(i==j); b=(i!=j); b=(iNodeIt conversion +// NodeIt ni(G,n); +// } +// { +// Edge i; Edge j(i); Edge k(INVALID); +// i=j; +// bool b; b=true; +// b=(i==INVALID); b=(i!=INVALID); +// b=(i==j); b=(i!=j); b=(iEdgeIt conversion +// EdgeIt ei(G,e); +// } +// { +// Node n; +// InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); +// i=j; +// j=G.first(i,n); +// j=++i; +// bool b; b=true; +// b=(i==INVALID); b=(i!=INVALID); +// Edge e(i); +// e=i; +// b=(i==j); b=(i!=j); b=(iInEdgeIt conversion +// InEdgeIt ei(G,e); +// } +// { +// Node n; +// OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); +// i=j; +// j=G.first(i,n); +// j=++i; +// bool b; b=true; +// b=(i==INVALID); b=(i!=INVALID); +// Edge e(i); +// e=i; +// b=(i==j); b=(i!=j); b=(iOutEdgeIt conversion +// OutEdgeIt ei(G,e); +// } +// { +// Node n,m; +// n=m=INVALID; +// Edge e; +// e=INVALID; +// n=G.tail(e); +// n=G.head(e); +// } +// // id tests +// { Node n; int i=G.id(n); i=i; } +// { Edge e; int i=G.id(e); i=i; } +// //NodeMap tests +// { +// Node k; +// typename Graph::template NodeMap m(G); +// //Const map +// typename Graph::template NodeMap const &cm = m; +// //Inicialize with default value +// typename Graph::template NodeMap mdef(G,12); +// //Copy +// typename Graph::template NodeMap mm(cm); +// //Copy from another type +// typename Graph::template NodeMap dm(cm); +// //Copy to more complex type +// typename Graph::template NodeMap em(cm); +// int v; +// v=m[k]; m[k]=v; m.set(k,v); +// v=cm[k]; + +// m=cm; +// dm=cm; //Copy from another type +// em=cm; //Copy to more complex type +// { +// //Check the typedef's +// typename Graph::template NodeMap::ValueType val; +// val=1; +// typename Graph::template NodeMap::KeyType key; +// key = typename Graph::NodeIt(G); +// } +// } +// { //bool NodeMap +// Node k; +// typename Graph::template NodeMap m(G); +// typename Graph::template NodeMap const &cm = m; //Const map +// //Inicialize with default value +// typename Graph::template NodeMap mdef(G,12); +// typename Graph::template NodeMap mm(cm); //Copy +// typename Graph::template NodeMap dm(cm); //Copy from another type +// bool v; +// v=m[k]; m[k]=v; m.set(k,v); +// v=cm[k]; + +// m=cm; +// dm=cm; //Copy from another type +// m=dm; //Copy to another type + +// { +// //Check the typedef's +// typename Graph::template NodeMap::ValueType val; +// val=true; +// typename Graph::template NodeMap::KeyType key; +// key= typename Graph::NodeIt(G); +// } +// } +// //EdgeMap tests +// { +// Edge k; +// typename Graph::template EdgeMap m(G); +// typename Graph::template EdgeMap const &cm = m; //Const map +// //Inicialize with default value +// typename Graph::template EdgeMap mdef(G,12); +// typename Graph::template EdgeMap mm(cm); //Copy +// typename Graph::template EdgeMap dm(cm);//Copy from another type +// int v; +// v=m[k]; m[k]=v; m.set(k,v); +// v=cm[k]; + +// m=cm; +// dm=cm; //Copy from another type +// { +// //Check the typedef's +// typename Graph::template EdgeMap::ValueType val; +// val=1; +// typename Graph::template EdgeMap::KeyType key; +// key= typename Graph::EdgeIt(G); +// } +// } +// { //bool EdgeMap +// Edge k; +// typename Graph::template EdgeMap m(G); +// typename Graph::template EdgeMap const &cm = m; //Const map +// //Inicialize with default value +// typename Graph::template EdgeMap mdef(G,12); +// typename Graph::template EdgeMap mm(cm); //Copy +// typename Graph::template EdgeMap dm(cm); //Copy from another type +// bool v; +// v=m[k]; m[k]=v; m.set(k,v); +// v=cm[k]; + +// m=cm; +// dm=cm; //Copy from another type +// m=dm; //Copy to another type +// { +// //Check the typedef's +// typename Graph::template EdgeMap::ValueType val; +// val=true; +// typename Graph::template EdgeMap::KeyType key; +// key= typename Graph::EdgeIt(G); +// } +// } +// } + +// /// An empty non-static graph class. + +// /// This class provides everything that \ref StaticGraph +// /// with additional functionality which enables to build a +// /// graph from scratch. +// class ExtendableGraph : public StaticGraph +// { +// public: +// /// Defalult constructor. + +// /// Defalult constructor. +// /// +// ExtendableGraph() { } +// ///Add a new node to the graph. + +// /// \return the new node. +// /// +// Node addNode() { return INVALID; } +// ///Add a new edge to the graph. + +// ///Add a new edge to the graph with tail node \c t +// ///and head node \c h. +// ///\return the new edge. +// Edge addEdge(Node h, Node t) { return INVALID; } + +// /// Resets the graph. + +// /// This function deletes all edges and nodes of the graph. +// /// It also frees the memory allocated to store them. +// /// \todo It might belong to \ref ErasableGraph. +// void clear() { } +// }; + + +// ///\brief Checks whether \c G meets the +// ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept +// template void checkCompileExtendableGraph(Graph &G) +// { +// checkCompileStaticGraph(G); + +// typedef typename Graph::Node Node; +// typedef typename Graph::NodeIt NodeIt; +// typedef typename Graph::Edge Edge; +// typedef typename Graph::EdgeIt EdgeIt; +// typedef typename Graph::InEdgeIt InEdgeIt; +// typedef typename Graph::OutEdgeIt OutEdgeIt; + +// Node n,m; +// n=G.addNode(); +// m=G.addNode(); +// Edge e; +// e=G.addEdge(n,m); + +// // G.clear(); +// } + + +// /// An empty erasable graph class. + +// /// This class is an extension of \ref ExtendableGraph. It also makes it +// /// possible to erase edges or nodes. +// class ErasableGraph : public ExtendableGraph +// { +// public: +// /// Defalult constructor. + +// /// Defalult constructor. +// /// +// ErasableGraph() { } +// /// Deletes a node. + +// /// Deletes node \c n node. +// /// +// void erase(Node n) { } +// /// Deletes an edge. + +// /// Deletes edge \c e edge. +// /// +// void erase(Edge e) { } +// }; + +// template void checkCompileGraphEraseEdge(Graph &G) +// { +// typename Graph::Edge e; +// G.erase(e); +// } + +// template void checkCompileGraphEraseNode(Graph &G) +// { +// typename Graph::Node n; +// G.erase(n); +// } + +// ///\brief Checks whether \c G meets the +// ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept +// template void checkCompileErasableGraph(Graph &G) +// { +// checkCompileExtendableGraph(G); +// checkCompileGraphEraseNode(G); +// checkCompileGraphEraseEdge(G); +// } + +// ///Checks whether a graph has findEdge() member function. + +// ///\todo findEdge() might be a global function. +// /// +// template void checkCompileGraphFindEdge(Graph &G) +// { +// typedef typename Graph::NodeIt Node; +// typedef typename Graph::NodeIt NodeIt; + +// G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G))); +// G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); +// } + + + + /************* New GraphBase stuff **************/ + + + /// \bug The nodes and edges are not allowed to inherit from the + /// same baseclass. + + class BaseGraphItem { public: - /// Defalult constructor. + BaseGraphItem() {} + BaseGraphItem(Invalid) {} - /// Defalult constructor. - /// - StaticGraph() { } - ///Copy consructor. + // We explicitely list these: + BaseGraphItem(BaseGraphItem const&) {} + BaseGraphItem& operator=(BaseGraphItem const&) { return *this; } -// ///\todo It is not clear, what we expect from a copy constructor. -// ///E.g. How to assign the nodes/edges to each other? What about maps? -// StaticGraph(const StaticGraph& g) { } + bool operator==(BaseGraphItem) const { return false; } + bool operator!=(BaseGraphItem) const { return false; } - /// The base type of node iterators, - /// or in other words, the trivial node iterator. - - /// This is the base type of each node iterator, - /// thus each kind of node iterator converts to this. - /// More precisely each kind of node iterator should be inherited - /// from the trivial node iterator. - class Node { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - Node() { } - /// Copy constructor. - - /// Copy constructor. - /// - Node(const Node&) { } - - /// Invalid constructor \& conversion. - - /// This constructor initializes the iterator to be invalid. - /// \sa Invalid for more details. - Node(Invalid) { } - /// Equality operator - - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(Node) const { return true; } - - /// Inequality operator - - /// \sa operator==(Node n) - /// - bool operator!=(Node) const { return true; } - - ///Comparison operator. - - ///This is a strict ordering between the nodes. - /// - ///This ordering can be different from the order in which NodeIt - ///goes through the nodes. - ///\todo Possibly we don't need it. - bool operator<(Node) const { return true; } - }; - - /// This iterator goes through each node. - - /// This iterator goes through each node. - /// Its usage is quite simple, for example you can count the number - /// of nodes in graph \c g of type \c Graph like this: - /// \code - /// int count=0; - /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; - /// \endcode - class NodeIt : public Node { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - NodeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - NodeIt(const NodeIt&) { } - /// Invalid constructor \& conversion. - - /// Initialize the iterator to be invalid. - /// \sa Invalid for more details. - NodeIt(Invalid) { } - /// Sets the iterator to the first node. - - /// Sets the iterator to the first node of \c g. - /// - NodeIt(const StaticGraph& g) { } - /// Node -> NodeIt conversion. - - /// Sets the iterator to the node of \c g pointed by the trivial - /// iterator n. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - NodeIt(const StaticGraph& g, const Node& n) { } - /// Next node. - - /// Assign the iterator to the next node. - /// - NodeIt& operator++() { return *this; } - }; - - - /// The base type of the edge iterators. - - /// The base type of the edge iterators. - /// - class Edge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - Edge() { } - /// Copy constructor. - - /// Copy constructor. - /// - Edge(const Edge&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - Edge(Invalid) { } - /// Equality operator - - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(Edge) const { return true; } - /// Inequality operator - - /// \sa operator==(Node n) - /// - bool operator!=(Edge) const { return true; } - ///Comparison operator. - - ///This is a strict ordering between the nodes. - /// - ///This ordering can be different from the order in which NodeIt - ///goes through the nodes. - ///\todo Possibly we don't need it. - bool operator<(Edge) const { return true; } - }; - - /// This iterator goes trough the outgoing edges of a node. - - /// This iterator goes trough the \e outgoing edges of a certain node - /// of a graph. - /// Its usage is quite simple, for example you can count the number - /// of outgoing edges of a node \c n - /// in graph \c g of type \c Graph as follows. - /// \code - /// int count=0; - /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; - /// \endcode - - class OutEdgeIt : public Edge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - OutEdgeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - OutEdgeIt(const OutEdgeIt&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - OutEdgeIt(Invalid) { } - /// This constructor sets the iterator to first outgoing edge. - - /// This constructor set the iterator to the first outgoing edge of - /// node - ///@param n the node - ///@param g the graph - OutEdgeIt(const StaticGraph& g, const Node& n) { } - /// Edge -> OutEdgeIt conversion - - /// Sets the iterator to the value of the trivial iterator \c e. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - OutEdgeIt(const StaticGraph& g, const Edge& e) { } - ///Next outgoing edge - - /// Assign the iterator to the next - /// outgoing edge of the corresponding node. - OutEdgeIt& operator++() { return *this; } - }; - - /// This iterator goes trough the incoming edges of a node. - - /// This iterator goes trough the \e incoming edges of a certain node - /// of a graph. - /// Its usage is quite simple, for example you can count the number - /// of outgoing edges of a node \c n - /// in graph \c g of type \c Graph as follows. - /// \code - /// int count=0; - /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; - /// \endcode - - class InEdgeIt : public Edge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - InEdgeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - InEdgeIt(const InEdgeIt&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - InEdgeIt(Invalid) { } - /// This constructor sets the iterator to first incoming edge. - - /// This constructor set the iterator to the first incoming edge of - /// node - ///@param n the node - ///@param g the graph - InEdgeIt(const StaticGraph& g, const Node& n) { } - /// Edge -> InEdgeIt conversion - - /// Sets the iterator to the value of the trivial iterator \c e. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - InEdgeIt(const StaticGraph& g, const Edge& n) { } - /// Next incoming edge - - /// Assign the iterator to the next inedge of the corresponding node. - /// - InEdgeIt& operator++() { return *this; } - }; - /// This iterator goes through each edge. - - /// This iterator goes through each edge of a graph. - /// Its usage is quite simple, for example you can count the number - /// of edges in a graph \c g of type \c Graph as follows: - /// \code - /// int count=0; - /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; - /// \endcode - class EdgeIt : public Edge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - EdgeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - EdgeIt(const EdgeIt&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - EdgeIt(Invalid) { } - /// This constructor sets the iterator to first edge. - - /// This constructor set the iterator to the first edge of - /// node - ///@param g the graph - EdgeIt(const StaticGraph& g) { } - /// Edge -> EdgeIt conversion - - /// Sets the iterator to the value of the trivial iterator \c e. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - EdgeIt(const StaticGraph&, const Edge&) { } - ///Next edge - - /// Assign the iterator to the next - /// edge of the corresponding node. - EdgeIt& operator++() { return *this; } - }; - - /// First node of the graph. - - /// \retval i the first node. - /// \return the first node. - /// - NodeIt& first(NodeIt& i) const { return i; } - - /// The first incoming edge. - - /// The first incoming edge. - /// - InEdgeIt& first(InEdgeIt &i, Node) const { return i; } - /// The first outgoing edge. - - /// The first outgoing edge. - /// - OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } - /// The first edge of the Graph. - - /// The first edge of the Graph. - /// - EdgeIt& first(EdgeIt& i) const { return i; } - - ///Gives back the head node of an edge. - - ///Gives back the head node of an edge. - /// - Node head(Edge) const { return INVALID; } - ///Gives back the tail node of an edge. - - ///Gives back the tail node of an edge. - /// - Node tail(Edge) const { return INVALID; } - - ///Gives back the \e id of a node. - - ///\warning Not all graph structures provide this feature. - /// - ///\todo Should each graph provide \c id? - int id(const Node&) const { return 0; } - ///Gives back the \e id of an edge. - - ///\warning Not all graph structures provide this feature. - /// - ///\todo Should each graph provide \c id? - int id(const Edge&) const { return 0; } - - ///\e - - ///\todo Should it be in the concept? - /// - int nodeNum() const { return 0; } - ///\e - - ///\todo Should it be in the concept? - /// - int edgeNum() const { return 0; } - - - ///Reference map of the nodes to type \c T. - - /// \ingroup skeletons - ///Reference map of the nodes to type \c T. - /// \sa Reference - /// \warning Making maps that can handle bool type (NodeMap) - /// needs some extra attention! - template class NodeMap : public ReferenceMap< Node, T > - { - public: - - ///\e - NodeMap(const StaticGraph&) { } - ///\e - NodeMap(const StaticGraph&, T) { } - - ///Copy constructor - template NodeMap(const NodeMap&) { } - ///Assignment operator - template NodeMap& operator=(const NodeMap&) - { return *this; } - }; - - ///Reference map of the edges to type \c T. - - /// \ingroup skeletons - ///Reference map of the edges to type \c T. - /// \sa Reference - /// \warning Making maps that can handle bool type (EdgeMap) - /// needs some extra attention! - template class EdgeMap - : public ReferenceMap - { - public: - - ///\e - EdgeMap(const StaticGraph&) { } - ///\e - EdgeMap(const StaticGraph&, T) { } - - ///Copy constructor - template EdgeMap(const EdgeMap&) { } - ///Assignment operator - template EdgeMap &operator=(const EdgeMap&) - { return *this; } - }; + // Technical requirement. Do we really need this? + bool operator<(BaseGraphItem) const { return false; } }; - struct DummyType { - int value; - DummyType() {} - DummyType(int p) : value(p) {} - DummyType& operator=(int p) { value = p; return *this;} + + /// A minimal GraphBase concept + + /// This class describes a minimal concept which can be extended to a + /// full-featured graph with \ref GraphFactory. + class GraphBase { + public: + + GraphBase() {} + + + /// \bug Nodes and Edges are comparable each other + + class Node : public BaseGraphItem {}; + class Edge : public BaseGraphItem {}; + + // Graph operation + void firstNode(Node &n) const { } + void firstEdge(Edge &e) const { } + + void firstOutEdge(Edge &e, Node) const { } + void firstInEdge(Edge &e, Node) const { } + + void nextNode(Node &n) const { } + void nextEdge(Edge &e) const { } + + + // Question: isn't it reasonable if this methods have a Node + // parameter? Like this: + // Edge& nextOut(Edge &e, Node) const { return e; } + void nextOutEdge(Edge &e) const { } + void nextInEdge(Edge &e) const { } + + Node head(Edge) const { return Node(); } + Node tail(Edge) const { return Node(); } + + + // Do we need id, nodeNum, edgeNum and co. in this basic graphbase + // concept? + + + // Maps. + // + // We need a special slimer concept which does not provide maps (it + // wouldn't be strictly slimer, cause for map-factory id() & friends + // a required...) + + template + class NodeMap : public GraphMap {}; + + template + class EdgeMap : public GraphMap {}; }; - - ///\brief Checks whether \c G meets the - ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept - template void checkCompileStaticGraph(Graph &G) - { - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::Edge Edge; - typedef typename Graph::EdgeIt EdgeIt; - typedef typename Graph::InEdgeIt InEdgeIt; - typedef typename Graph::OutEdgeIt OutEdgeIt; - - { - Node i; Node j(i); Node k(INVALID); - i=j; - bool b; b=true; - b=(i==INVALID); b=(i!=INVALID); - b=(i==j); b=(i!=j); b=(iNodeIt conversion - NodeIt ni(G,n); - } - { - Edge i; Edge j(i); Edge k(INVALID); - i=j; - bool b; b=true; - b=(i==INVALID); b=(i!=INVALID); - b=(i==j); b=(i!=j); b=(iEdgeIt conversion - EdgeIt ei(G,e); - } - { - Node n; - InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); - i=j; - j=G.first(i,n); - j=++i; - bool b; b=true; - b=(i==INVALID); b=(i!=INVALID); - Edge e(i); - e=i; - b=(i==j); b=(i!=j); b=(iInEdgeIt conversion - InEdgeIt ei(G,e); - } - { - Node n; - OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); - i=j; - j=G.first(i,n); - j=++i; - bool b; b=true; - b=(i==INVALID); b=(i!=INVALID); - Edge e(i); - e=i; - b=(i==j); b=(i!=j); b=(iOutEdgeIt conversion - OutEdgeIt ei(G,e); - } - { - Node n,m; - n=m=INVALID; - Edge e; - e=INVALID; - n=G.tail(e); - n=G.head(e); - } - // id tests - { Node n; int i=G.id(n); i=i; } - { Edge e; int i=G.id(e); i=i; } - //NodeMap tests - { - Node k; - typename Graph::template NodeMap m(G); - //Const map - typename Graph::template NodeMap const &cm = m; - //Inicialize with default value - typename Graph::template NodeMap mdef(G,12); - //Copy - typename Graph::template NodeMap mm(cm); - //Copy from another type - typename Graph::template NodeMap dm(cm); - //Copy to more complex type - typename Graph::template NodeMap em(cm); - int v; - v=m[k]; m[k]=v; m.set(k,v); - v=cm[k]; - - m=cm; - dm=cm; //Copy from another type - em=cm; //Copy to more complex type - { - //Check the typedef's - typename Graph::template NodeMap::ValueType val; - val=1; - typename Graph::template NodeMap::KeyType key; - key = typename Graph::NodeIt(G); - } - } - { //bool NodeMap - Node k; - typename Graph::template NodeMap m(G); - typename Graph::template NodeMap const &cm = m; //Const map - //Inicialize with default value - typename Graph::template NodeMap mdef(G,12); - typename Graph::template NodeMap mm(cm); //Copy - typename Graph::template NodeMap dm(cm); //Copy from another type - bool v; - v=m[k]; m[k]=v; m.set(k,v); - v=cm[k]; - - m=cm; - dm=cm; //Copy from another type - m=dm; //Copy to another type - { - //Check the typedef's - typename Graph::template NodeMap::ValueType val; - val=true; - typename Graph::template NodeMap::KeyType key; - key= typename Graph::NodeIt(G); + + + /**************** Concept checking classes ****************/ + + template + struct BaseGraphItemConcept { + void constraints() { + BGI i1; + BGI i2 = i1; + BGI i3 = INVALID; + + i1 = i3; + if( i1 == i3 ) { + if ( i2 != i3 && i3 < i2 ) + return; } } - //EdgeMap tests - { - Edge k; - typename Graph::template EdgeMap m(G); - typename Graph::template EdgeMap const &cm = m; //Const map - //Inicialize with default value - typename Graph::template EdgeMap mdef(G,12); - typename Graph::template EdgeMap mm(cm); //Copy - typename Graph::template EdgeMap dm(cm);//Copy from another type - int v; - v=m[k]; m[k]=v; m.set(k,v); - v=cm[k]; - - m=cm; - dm=cm; //Copy from another type - { - //Check the typedef's - typename Graph::template EdgeMap::ValueType val; - val=1; - typename Graph::template EdgeMap::KeyType key; - key= typename Graph::EdgeIt(G); - } - } - { //bool EdgeMap - Edge k; - typename Graph::template EdgeMap m(G); - typename Graph::template EdgeMap const &cm = m; //Const map - //Inicialize with default value - typename Graph::template EdgeMap mdef(G,12); - typename Graph::template EdgeMap mm(cm); //Copy - typename Graph::template EdgeMap dm(cm); //Copy from another type - bool v; - v=m[k]; m[k]=v; m.set(k,v); - v=cm[k]; - - m=cm; - dm=cm; //Copy from another type - m=dm; //Copy to another type - { - //Check the typedef's - typename Graph::template EdgeMap::ValueType val; - val=true; - typename Graph::template EdgeMap::KeyType key; - key= typename Graph::EdgeIt(G); - } - } - } - - /// An empty non-static graph class. - - /// This class provides everything that \ref StaticGraph - /// with additional functionality which enables to build a - /// graph from scratch. - class ExtendableGraph : public StaticGraph - { - public: - /// Defalult constructor. - - /// Defalult constructor. - /// - ExtendableGraph() { } - ///Add a new node to the graph. - - /// \return the new node. - /// - Node addNode() { return INVALID; } - ///Add a new edge to the graph. - - ///Add a new edge to the graph with tail node \c t - ///and head node \c h. - ///\return the new edge. - Edge addEdge(Node h, Node t) { return INVALID; } - - /// Resets the graph. - - /// This function deletes all edges and nodes of the graph. - /// It also frees the memory allocated to store them. - /// \todo It might belong to \ref ErasableGraph. - void clear() { } }; - ///\brief Checks whether \c G meets the - ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept - template void checkCompileExtendableGraph(Graph &G) - { - checkCompileStaticGraph(G); + + class StaticGraph + : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent { + public: + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + }; - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::Edge Edge; - typedef typename Graph::EdgeIt EdgeIt; - typedef typename Graph::InEdgeIt InEdgeIt; - typedef typename Graph::OutEdgeIt OutEdgeIt; - - Node n,m; - n=G.addNode(); - m=G.addNode(); - Edge e; - e=G.addEdge(n,m); - - // G.clear(); - } + template + struct StaticGraphConcept { + void constraints() { + function_requires >(); + function_requires >(); + function_requires >(); + } + Graph& graph; + }; + class ExtendableGraph + : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent { + public: + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + }; - /// An empty erasable graph class. - - /// This class is an extension of \ref ExtendableGraph. It also makes it - /// possible to erase edges or nodes. - class ErasableGraph : public ExtendableGraph - { + template + struct ExtendableGraphConcept { + void constraints() { + function_requires >(); + function_requires >(); + function_requires >(); + } + Graph& graph; + }; + + class ErasableGraph + : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent { public: - /// Defalult constructor. + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + }; - /// Defalult constructor. - /// - ErasableGraph() { } - /// Deletes a node. + template + struct ErasableGraphConcept { + void constraints() { + function_requires >(); + function_requires >(); + } + Graph& graph; + }; - /// Deletes node \c n node. - /// - void erase(Node n) { } - /// Deletes an edge. - - /// Deletes edge \c e edge. - /// - void erase(Edge e) { } - }; - - template void checkCompileGraphEraseEdge(Graph &G) - { - typename Graph::Edge e; - G.erase(e); - } - - template void checkCompileGraphEraseNode(Graph &G) - { - typename Graph::Node n; - G.erase(n); - } - - ///\brief Checks whether \c G meets the - ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept - template void checkCompileErasableGraph(Graph &G) - { - checkCompileExtendableGraph(G); - checkCompileGraphEraseNode(G); - checkCompileGraphEraseEdge(G); - } - - ///Checks whether a graph has findEdge() member function. - - ///\todo findEdge() might be a global function. - /// - template void checkCompileGraphFindEdge(Graph &G) - { - typedef typename Graph::NodeIt Node; - typedef typename Graph::NodeIt NodeIt; - - G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G))); - G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); - } - // @} } //namespace skeleton } //namespace lemon diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/skeletons/graph_component.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/skeletons/graph_component.h Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,827 @@ +/* -*- C++ -*- + * src/lemon/skeletons/graph_component.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 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. + * + */ + +///\ingroup skeletons +///\file +///\brief The graph components. + + +#ifndef LEMON_SKELETON_GRAPH_COMPONENT_H +#define LEMON_SKELETON_GRAPH_COMPONENT_H + +#include +#include + +namespace lemon { + namespace skeleton { + + /// An empty base graph class. + + /// This class provides the most minimal features of a graph structure. + /// All the graph concepts have to be conform to this base graph. + + class BaseGraphComponent { + public: + + typedef BaseGraphComponent Graph; + + /// Node class of the graph. + + /// This class represents the Nodes of the graph. + /// + class Node { + public: + + /// Default constructor. + + /// @warning The default constructor sets the iterator + /// to an undefined value. + + Node() {} + /// Copy constructor. + + /// Copy constructor. + /// + Node(const Node&) {} + + /// Invalid constructor \& conversion. + + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + Node(Invalid) {} + + + Node& operator=(const Node&) { return *this;} + + /// Equality operator. + + /// Two iterators are equal if and only if they represents the + /// same node in the graph or both are invalid. + bool operator==(const Node&) { return true;} + + + /// Inequality operator. + + /// \sa operator==(const Node& n) + /// + bool operator!=(const Node&) { return true;} + + /// Comparison operator. + + /// This is a strict ordering between the nodes. + /// + /// This ordering can be different from the iterating order of nodes. + /// \todo Possibly we don't need it. + bool operator<(const Node&) { return true;} + }; + + /// Edge class of the graph. + + /// This class represents the Edges of the graph. + /// + class Edge { + public: + + /// Default constructor. + + /// @warning The default constructor sets the iterator + /// to an undefined value. + + Edge() {} + /// Copy constructor. + + /// Copy constructor. + /// + Edge(const Edge&) {} + + /// Invalid constructor \& conversion. + + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + Edge(Invalid) {} + + + Edge& operator=(const Edge&) { return *this;} + + /// Equality operator. + + /// Two iterators are equal if and only if they represents the + /// same edge in the graph or both are invalid. + bool operator==(const Edge&) { return true;} + + + /// Inequality operator. + + /// \sa operator==(const Edge& n) + /// + bool operator!=(const Edge&) { return true;} + + /// Comparison operator. + + /// This is a strict ordering between the edges. + /// + /// This ordering can be different from the iterating order of edges. + /// \todo Possibly we don't need it. + bool operator<(const Edge&) { return true;} + }; + + ///Gives back the head node of an edge. + + ///Gives back the head node of an edge. + /// + Node head(const Edge&) const { return INVALID;} + + ///Gives back the tail node of an edge. + + ///Gives back the tail node of an edge. + /// + Node tail(const Edge&) const { return INVALID;} + }; + + /// Concept check structure for BaseGraph. + + /// Concept check structure for BaseGraph. + /// + + template + struct BaseGraphComponentConcept { + typedef typename Graph::Node Node; + typedef typename Graph::Edge Edge; + + void constraints() { + { + Node ni; + Node nj(ni); + Node nk(INVALID); + ni = nj; + bool b; b = true; + b = (ni == INVALID); b = (ni != INVALID); + b = (ni==nj); b = (ni != nj); b=( ni < nj); + } + { + Edge ei; + Edge ej(ei); + Edge ek(INVALID); + ei = ej; + bool b; b = true; + b = (ei == INVALID); b = (ei != INVALID); + b = (ei==ej); b = (ei != ej); b=( ei < ej); + } + { + const Graph& const_graph = graph; + Node n; + Edge e; + n = const_graph.tail(e); + n = const_graph.head(e); + } + } + + Graph& graph; + }; + + /// An empty iterable base graph class. + + /// This class provides beside the core graph features + /// core iterable interface for the graph structure. + /// The most of the base graphs should be conform to this concept. + + class BaseIterableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + /// Gives back the first Node in the iterating order. + + /// Gives back the first Node in the iterating order. + /// + void first(Node&) const {} + + /// Gives back the next Node in the iterating order. + + /// Gives back the next Node in the iterating order. + /// + void next(Node&) const {} + + /// Gives back the first Edge in the iterating order. + + /// Gives back the first Edge in the iterating order. + /// + void first(Edge&) const {} + /// Gives back the next Edge in the iterating order. + + /// Gives back the next Edge in the iterating order. + /// + void next(Edge&) const {} + + + /// Gives back the first of the Edges point to the given Node. + + /// Gives back the first of the Edges point to the given Node. + /// + void firstIn(Edge&, const Node&) const {} + + /// Gives back the next of the Edges points to the given Node. + + + /// Gives back the next of the Edges points to the given Node. + /// + void nextIn(Edge&) const {} + + /// Gives back the first of the Edges start from the given Node. + + /// Gives back the first of the Edges start from the given Node. + /// + void firstOut(Edge&, const Node&) const {} + + /// Gives back the next of the Edges start from the given Node. + + /// Gives back the next of the Edges start from the given Node. + /// + void nextOut(Edge&) const {} + }; + + + /// Concept check structure for IterableBaseGraph. + + /// Concept check structure for IterableBaseGraph. + /// + template + struct BaseIterableGraphComponentConcept { + + void constraints() { + const Graph& const_graph = graph; + typename Graph::Node node; + typename Graph::Edge edge; + { + const_graph.first(node); + const_graph.next(node); + } + { + const_graph.first(edge); + const_graph.next(edge); + } + { + const_graph.firstIn(edge, node); + const_graph.nextIn(edge); + } + { + const_graph.firstOut(edge, node); + const_graph.nextOut(edge); + } + } + + Graph& graph; + }; + + /// An empty idable base graph class. + + /// This class provides beside the core graph features + /// core id functions for the graph structure. + /// The most of the base graphs should be conform to this concept. + /// The id's are unique and immutable. + + class IDableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + /// Gives back an unique integer id for the Node. + + /// Gives back an unique integer id for the Node. + /// + int id(const Node&) const { return -1;} + + /// Gives back an unique integer id for the Edge. + + /// Gives back an unique integer id for the Edge. + /// + int id(const Edge&) const { return -1;} + }; + + + /// Concept check structure for IdableBaseGraph. + + /// Concept check structure for IdableBaseGraph. + /// + template + struct IDableGraphComponentConcept { + + void constraints() { + const Graph& const_graph = graph; + typename Graph::Node node; + int nid = const_graph.id(node); + nid = const_graph.id(node); + typename Graph::Edge edge; + int eid = const_graph.id(edge); + eid = const_graph.id(edge); + } + + Graph& graph; + }; + + + /// An empty max-idable base graph class. + + /// This class provides beside the core graph features + /// core max id functions for the graph structure. + /// The most of the base graphs should be conform to this concept. + /// The id's are unique and immutable. + class MaxIDableGraphComponent : virtual public BaseGraphComponent { + public: + + /// Gives back an integer greater or equal to the maximum Node id. + + /// Gives back an integer greater or equal to the maximum Node id. + /// + int maxEdgeId() const { return -1;} + + /// Gives back an integer greater or equal to the maximum Edge id. + + /// Gives back an integer greater or equal to the maximum Edge id. + /// + int maxNodeId() const { return -1;} + }; + + /// Concept check structure for MaxIdableBaseGraph. + + /// Concept check structure for MaxIdableBaseGraph. + /// + template + struct MaxIDableGraphComponentConcept { + + void constraints() { + const Graph& const_graph = graph; + int nid = const_graph.maxEdgeId(); + ignore_unused_variable_warning(nid); + int eid = const_graph.maxNodeId(); + ignore_unused_variable_warning(eid); + } + + Graph& graph; + }; + + /// An empty extendable base graph class. + + /// This class provides beside the core graph features + /// core graph extend interface for the graph structure. + /// The most of the base graphs should be conform to this concept. + class BaseExtendableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + /// Adds a new Node to the graph. + + /// Adds a new Node to the graph. + /// + Node addNode() { + return INVALID; + } + + /// Adds a new Edge connects the two Nodes to the graph. + + /// Adds a new Edge connects the two Nodes to the graph. + /// + Edge addEdge(const Node& from, const Node& to) { + return INVALID; + } + + }; + + /// Concept check structure for ExtendableBaseGraph. + + /// Concept check structure for ExtendableBaseGraph. + /// + template + struct BaseExtendableGraphComponentConcept { + void constraints() { + typename Graph::Node node_a, node_b; + node_a = graph.addNode(); + typename Graph::Edge edge; + edge = graph.addEdge(node_a, node_b); + } + + Graph& graph; + }; + + /// An empty erasable base graph class. + + /// This class provides beside the core graph features + /// core erase functions for the graph structure. + /// The most of the base graphs should be conform to this concept. + class BaseErasableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + /// Erase a Node from the graph. + + /// Erase a Node from the graph. This function should not + /// erase edges connecting to the Node. + void erase(const Node&) {} + + /// Erase an Edge from the graph. + + /// Erase an Edge from the graph. + /// + void erase(const Edge&) {} + + }; + + /// Concept check structure for ErasableBaseGraph. + + /// Concept check structure for ErasableBaseGraph. + /// + template + struct BaseErasableGraphComponentConcept { + void constraints() { + typename Graph::Node node; + graph.erase(node); + typename Graph::Edge edge; + graph.erase(edge); + } + + Graph& graph; + }; + + /// An empty clearable base graph class. + + /// This class provides beside the core graph features + /// core clear functions for the graph structure. + /// The most of the base graphs should be conform to this concept. + class BaseClearableGraphComponent : virtual public BaseGraphComponent { + public: + + /// Erase all the Nodes and Edges from the graph. + + /// Erase all the Nodes and Edges from the graph. + /// + void clear() {} + }; + + /// Concept check function for ErasableBaseGraph. + + /// Concept check function for ErasableBaseGraph. + /// + template + struct BaseClearableGraphComponentConcept { + void constraints() { + graph.clear(); + } + + Graph& graph; + }; + + + class IterableGraphComponent : virtual public BaseGraphComponent { + + public: + + typedef IterableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + class NodeIt : public Node { + public: + NodeIt() {} + NodeIt(Invalid) {} + NodeIt(const Graph&) {} + + NodeIt& operator++() { return *this; } + // Node operator*() const { return INVALID; } + + bool operator==(const NodeIt&) { return true;} + bool operator!=(const NodeIt&) { return true;} + }; + + class EdgeIt : public Edge { + public: + EdgeIt() {} + EdgeIt(Invalid) {} + EdgeIt(const Graph&) {} + + EdgeIt& operator++() { return *this; } + // Edge operator*() const { return INVALID; } + + bool operator==(const EdgeIt&) { return true;} + bool operator!=(const EdgeIt&) { return true;} + }; + + class InEdgeIt : public Edge { + public: + InEdgeIt() {} + InEdgeIt(Invalid) {} + InEdgeIt(const Graph&, const Node&) {} + + InEdgeIt& operator++() { return *this; } + // Edge operator*() const { return INVALID; } + + bool operator==(const InEdgeIt&) { return true;} + bool operator!=(const InEdgeIt&) { return true;} + }; + + class OutEdgeIt : public Edge { + public: + OutEdgeIt() {} + OutEdgeIt(Invalid) {} + OutEdgeIt(const Graph&, const Node&) {} + + OutEdgeIt& operator++() { return *this; } + // Edge operator*() const { return INVALID; } + + bool operator==(const OutEdgeIt&) { return true;} + bool operator!=(const OutEdgeIt&) { return true;} + }; + + }; + + template + struct IterableGraphComponentConcept { + + void constraints() { + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::InEdgeIt InEdgeIt; + typedef typename Graph::OutEdgeIt OutEdgeIt; + + { + NodeIt it; + NodeIt jt(it); + NodeIt kt(INVALID); + NodeIt lt(graph); + it = jt; + jt = ++it; + bool b; + b = (it == INVALID); + b = (it != INVALID); + b = (it == jt); + b = (it != jt); + Node node = it; + node = it; + } + { + EdgeIt it; + EdgeIt jt(it); + EdgeIt kt(INVALID); + EdgeIt lt(graph); + it = jt; + jt = ++it; + bool b; + b = (it == INVALID); + b = (it != INVALID); + b = (it == jt); + b = (it != jt); + Edge edge = it; + edge = it; + } + { + InEdgeIt it; + InEdgeIt jt(it); + InEdgeIt kt(INVALID); + Node node; + InEdgeIt lt(graph, node); + it = jt; + jt = ++it; + bool b; + b = (it == INVALID); + b = (it != INVALID); + b = (it == jt); + b = (it != jt); + Edge edge = it; + edge = it; + } + { + OutEdgeIt it; + OutEdgeIt jt(it); + OutEdgeIt kt(INVALID); + Node node; + OutEdgeIt lt(graph, node); + it = jt; + jt = ++it; + bool b; + b = (it == INVALID); + b = (it != INVALID); + b = (it == jt); + b = (it != jt); + Edge edge = it; + edge = it; + } + } + Graph& graph; + }; + + + class IdMappableGraphComponent : virtual public BaseGraphComponent { + + typedef IdMappableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + public: + + class NodeIdMap : public ReadMap { + public: + NodeIdMap(const Graph&) {} + int maxId() const { return -1;} + }; + + class EdgeIdMap : public ReadMap { + public: + EdgeIdMap(const Graph&) {} + int maxId() const { return -1;} + }; + + }; + + template + struct IdMappableGraphComponentConcept { + void constraints() { + { + typedef typename Graph::EdgeIdMap EdgeIdMap; + function_requires >(); + EdgeIdMap edge_map(graph); + int n = edge_map.maxId(); + ignore_unused_variable_warning(n); + } + { + typedef typename Graph::NodeIdMap NodeIdMap; + function_requires >(); + NodeIdMap node_map(graph); + int n = node_map.maxId(); + ignore_unused_variable_warning(n); + } + } + Graph& graph; + }; + + + class MappableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef MappableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + template + class NodeMap : public ReferenceMap { + public: + NodeMap(const Graph&) {} + NodeMap(const Graph&, const Value&) {} + NodeMap(const NodeMap&) {} + + NodeMap& operator=(const NodeMap&) { return *this;} + + }; + + template + class EdgeMap : public ReferenceMap { + public: + EdgeMap(const Graph&) {} + EdgeMap(const Graph&, const Value&) {} + EdgeMap(const EdgeMap&) {} + + EdgeMap& operator=(const EdgeMap&) { return *this;} + + }; + + }; + + template + struct MappableGraphComponentConcept { + + struct Type { + int value; + Type() : value(0) {} + Type(int _v) : value(_v) {} + }; + + void constraints() { + { // int map test + typedef typename Graph::template NodeMap IntNodeMap; + function_requires >(); + } { // bool map test + typedef typename Graph::template NodeMap BoolNodeMap; + function_requires >(); + } { // Type map test + typedef typename Graph::template NodeMap TypeNodeMap; + function_requires >(); + } + + { // int map test + typedef typename Graph::template EdgeMap IntEdgeMap; + function_requires >(); + } { // bool map test + typedef typename Graph::template EdgeMap BoolEdgeMap; + function_requires >(); + } { // Type map test + typedef typename Graph::template EdgeMap TypeEdgeMap; + function_requires >(); + } + } + + Graph& graph; + }; + + + class ExtendableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef ExtendableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + Node addNode() { + return INVALID; + } + + Edge addEdge(const Node& from, const Node& to) { + return INVALID; + } + + }; + + template + struct ExtendableGraphComponentConcept { + void constraints() { + typename Graph::Node node_a, node_b; + node_a = graph.addNode(); + typename Graph::Edge edge; + edge = graph.addEdge(node_a, node_b); + } + Graph& graph; + }; + + class ErasableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef ErasableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + void erase(const Node&) {} + void erase(const Edge&) {} + + }; + + template + struct ErasableGraphComponentConcept { + void constraints() { + typename Graph::Node node; + graph.erase(node); + typename Graph::Edge edge; + graph.erase(edge); + } + + Graph& graph; + }; + + class ClearableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef ClearableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + void clear() {} + + }; + + template + struct ClearableGraphComponentConcept { + void constraints() { + graph.clear(); + } + Graph& graph; + }; + + } + +} + +#endif diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/skeletons/maps.h --- a/src/lemon/skeletons/maps.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/lemon/skeletons/maps.h Wed Oct 27 22:38:50 2004 +0000 @@ -17,6 +17,8 @@ #ifndef LEMON_MAPSKELETON_H #define LEMON_MAPSKELETON_H +#include + ///\ingroup skeletons ///\file ///\brief Map concepts checking classes for testing and documenting. @@ -113,6 +115,130 @@ ReferenceMap() {} }; + + template + class GraphMap : public ReadWriteMap { + // I really, really don't like the idea that every graph should have + // reference maps! --klao + + private: + // We state explicitly that graph maps have no default constructor? + GraphMap(); + + public: + explicit GraphMap(Graph const&) {} + // value for initializing + GraphMap(Graph const&, T) {} + + // this probably should be required: + GraphMap(GraphMap const&) {} + GraphMap& operator=(GraphMap const&) { return *this; } + + // but this is a absolute no-op! We should provide a more generic + // graph-map-copy operation. + // + // template + // GraphMap(GraphMap const&); + // + // template + // GraphMap& operator=(const GraphMap&); + }; + + + /**************** Concept-checking classes ****************/ + + template + struct ReadMapConcept { + typedef typename ReadMap::KeyType KeyType; + typedef typename ReadMap::ValueType ValueType; + + void constraints() { + // No constraints for constructor. + + // What are the requirement for the ValueType? + // CopyConstructible? Assignable? None of these? + ValueType v = m[k]; + v = m[k]; + + // FIXME: + ignore_unused_variable_warning(v); + } + + ReadMap m; + KeyType k; + }; + + template + struct WriteMapConcept { + typedef typename WriteMap::KeyType KeyType; + typedef typename WriteMap::ValueType ValueType; + + void constraints() { + // No constraints for constructor. + + m.set(k, v); + } + + WriteMap m; + KeyType k; + ValueType v; + }; + + template + struct ReadWriteMapConcept { + void constraints() { + function_requires< ReadMapConcept >(); + function_requires< WriteMapConcept >(); + } + }; + + template + struct ReferenceMapConcept { + typedef typename ReferenceMap::KeyType KeyType; + typedef typename ReferenceMap::ValueType ValueType; + typedef typename ReferenceMap::ReferenceType ReferenceType; + + // What for is this? + typedef typename ReferenceMap::ConstReferenceType ConstReferenceType; + + void constraints() { + function_requires< ReadWriteMapConcept >(); + + m[k] = v; + // Or should we require real reference? + // Like this: + // ValueType &vv = m[k]; + // ignore_unused_variable_warning(vv); + } + + ReferenceMap m; + KeyType k; + ValueType v; + }; + + /// \todo GraphMapConceptCheck + + template + struct GraphMapConcept { + void constraints() { + function_requires< ReadWriteMapConcept >(); + // Construction with a graph parameter + GraphMap a(g); + // Ctor with a graph and a default value parameter + GraphMap a2(g,t); + // Copy ctor. Do we need it? + GraphMap b=c; + // Copy operator. Do we need it? + a=b; + + ignore_unused_variable_warning(a2); + } + const GraphMap &c; + const Graph &g; + const typename GraphMap::ValueType &t; + }; + + // @} } //namespace skeleton diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/smart_graph.h --- a/src/lemon/smart_graph.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/lemon/smart_graph.h Wed Oct 27 22:38:50 2004 +0000 @@ -22,22 +22,28 @@ ///\brief SmartGraph and SymSmartGraph classes. #include -#include #include +#include +#include +#include -#include +#include -#include +#include -#include +#include +#include + + +#include + namespace lemon { -/// \addtogroup graphs -/// @{ -// class SymSmartGraph; + /// \addtogroup graphs + /// @{ ///A smart graph class. @@ -56,7 +62,7 @@ ///Of course it should be used as a stack. (Maybe X is not necessary.) /// ///\author Alpar Juttner - class SmartGraph { + class SmartGraphBase { struct NodeT { @@ -77,25 +83,16 @@ public: - typedef SmartGraph Graph; + typedef SmartGraphBase Graph; class Node; class Edge; - class NodeIt; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; - - // Create map registries. - CREATE_MAP_REGISTRIES; - // Create node and edge maps. - CREATE_MAPS(ArrayMap); public: - SmartGraph() : nodes(), edges() { } - SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { } + SmartGraphBase() : nodes(), edges() { } + SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { } ///Number of nodes. int nodeNum() const { return nodes.size(); } @@ -116,15 +113,6 @@ Node tail(Edge e) const { return edges[e.n].tail; } Node head(Edge e) const { return edges[e.n].head; } - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } - /// Node ID. /// The ID of a valid Node is a nonnegative integer not greater than @@ -147,9 +135,6 @@ Node addNode() { Node n; n.n=nodes.size(); nodes.push_back(NodeT()); //FIXME: Hmmm... - - - node_maps.add(n); return n; } @@ -160,8 +145,6 @@ edges[e.n].next_in=nodes[v.n].first_in; nodes[u.n].first_out=nodes[v.n].first_in=e.n; - edge_maps.add(e); - return e; } @@ -182,24 +165,16 @@ } void clear() { - edge_maps.clear(); edges.clear(); - node_maps.clear(); nodes.clear(); } + class Node { - friend class SmartGraph; - template friend class NodeMap; - - friend class Edge; - friend class OutEdgeIt; - friend class InEdgeIt; - friend class SymEdge; + friend class SmartGraphBase; protected: int n; - friend int SmartGraph::id(Node v); Node(int nn) {n=nn;} public: Node() {} @@ -207,529 +182,77 @@ bool operator==(const Node i) const {return n==i.n;} bool operator!=(const Node i) const {return n!=i.n;} bool operator<(const Node i) const {return nnodes.size()+1)-1; - return *this; - } -// ///Validity check -// operator bool() { return Node::operator bool(); } - }; class Edge { - friend class SmartGraph; - template friend class EdgeMap; + friend class SmartGraphBase; - friend class SymSmartGraph; - - friend class Node; - friend class NodeIt; protected: int n; - friend int SmartGraph::id(Edge e); Edge(int nn) {n=nn;} public: - /// An Edge with id \c n. - Edge() { } Edge (Invalid) { n=-1; } bool operator==(const Edge i) const {return n==i.n;} bool operator!=(const Edge i) const {return n!=i.n;} bool operator<(const Edge i) const {return nedges[n].next_out; return *this; } -// ///Validity check -// operator bool() { return Edge::operator bool(); } - }; - - class InEdgeIt : public Edge { - const SmartGraph *G; - friend class SmartGraph; - public: - InEdgeIt() : Edge() { } - InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { } - InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const SmartGraph& _G,Node v) - : Edge(_G.nodes[v.n].first_in), G(&_G) { } - InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } -// ///Validity check -// operator bool() { return Edge::operator bool(); } - }; + void nextIn(Edge& edge) const { + edge.n = edges[edge.n].next_in; + } }; + typedef AlterableGraphExtender AlterableSmartGraphBase; + typedef IterableGraphExtender IterableSmartGraphBase; + typedef IdMappableGraphExtender IdMappableSmartGraphBase; + typedef DefaultMappableGraphExtender MappableSmartGraphBase; + typedef ExtendableGraphExtender ExtendableSmartGraphBase; + typedef ClearableGraphExtender ClearableSmartGraphBase; + typedef ClearableSmartGraphBase SmartGraph; - class SymSmartGraph : public SmartGraph { - typedef SmartGraph Parent; - public: - typedef SymSmartGraph Graph; + template <> + int countNodes(const SmartGraph& graph) { + return graph.nodeNum(); + } - typedef SmartGraph::Node Node; - typedef SmartGraph::NodeIt NodeIt; + template <> + int countEdges(const SmartGraph& graph) { + return graph.edgeNum(); + } - class SymEdge; - class SymEdgeIt; - - class Edge; - class EdgeIt; - class OutEdgeIt; - class InEdgeIt; - - template - class NodeMap : public Parent::NodeMap { - public: - NodeMap(const SymSmartGraph& g) - : SymSmartGraph::Parent::NodeMap(g) {} - NodeMap(const SymSmartGraph& g, Value v) - : SymSmartGraph::Parent::NodeMap(g, v) {} - template - NodeMap(const NodeMap& copy) - : SymSmartGraph::Parent::NodeMap(copy) { } - }; - - template - class SymEdgeMap : public Parent::EdgeMap { - public: - typedef SymEdge KeyType; - - SymEdgeMap(const SymSmartGraph& g) - : SymSmartGraph::Parent::EdgeMap(g) {} - SymEdgeMap(const SymSmartGraph& g, Value v) - : SymSmartGraph::Parent::EdgeMap(g, v) {} - template - SymEdgeMap(const SymEdgeMap& copy) - : SymSmartGraph::Parent::EdgeMap(copy) { } - - }; - - // Create edge map registry. - CREATE_EDGE_MAP_REGISTRY; - // Create edge maps. - CREATE_EDGE_MAP(ArrayMap); - - class Edge { - friend class SymSmartGraph; - friend class SymSmartGraph::EdgeIt; - friend class SymSmartGraph::OutEdgeIt; - friend class SymSmartGraph::InEdgeIt; - - protected: - int id; - - Edge(int pid) { id = pid; } - - public: - /// An Edge with id \c n. - - Edge() { } - Edge (Invalid) { id = -1; } - - operator SymEdge(){ return SymEdge(id >> 1);} - - bool operator==(const Edge i) const {return id == i.id;} - bool operator!=(const Edge i) const {return id != i.id;} - bool operator<(const Edge i) const {return id < i.id;} - // ///Validity check - // operator bool() { return n!=-1; } - }; - - class SymEdge : public SmartGraph::Edge { - friend class SymSmartGraph; - friend class SymSmartGraph::Edge; - typedef SmartGraph::Edge Parent; - - protected: - SymEdge(int pid) : Parent(pid) {} - public: - - SymEdge() { } - SymEdge(const SmartGraph::Edge& i) : Parent(i) {} - SymEdge (Invalid) : Parent(INVALID) {} - - }; - - class OutEdgeIt { - Parent::OutEdgeIt out; - Parent::InEdgeIt in; - public: - OutEdgeIt() {} - OutEdgeIt(const SymSmartGraph& g, Edge e) { - if ((e.id & 1) == 0) { - out = Parent::OutEdgeIt(g, SymEdge(e)); - in = Parent::InEdgeIt(g, g.tail(e)); - } else { - out = Parent::OutEdgeIt(INVALID); - in = Parent::InEdgeIt(g, SymEdge(e)); - } - } - OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } - - OutEdgeIt(const SymSmartGraph& g, const Node v) - : out(g, v), in(g, v) {} - OutEdgeIt &operator++() { - if (out != INVALID) { - ++out; - } else { - ++in; - } - return *this; - } - - operator Edge() const { - if (out == INVALID && in == INVALID) return INVALID; - return out != INVALID ? forward(out) : backward(in); - } - - bool operator==(const Edge i) const {return Edge(*this) == i;} - bool operator!=(const Edge i) const {return Edge(*this) != i;} - bool operator<(const Edge i) const {return Edge(*this) < i;} - }; - - class InEdgeIt { - Parent::OutEdgeIt out; - Parent::InEdgeIt in; - public: - InEdgeIt() {} - InEdgeIt(const SymSmartGraph& g, Edge e) { - if ((e.id & 1) == 0) { - out = Parent::OutEdgeIt(g, SymEdge(e)); - in = Parent::InEdgeIt(g, g.tail(e)); - } else { - out = Parent::OutEdgeIt(INVALID); - in = Parent::InEdgeIt(g, SymEdge(e)); - } - } - InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } - - InEdgeIt(const SymSmartGraph& g, const Node v) - : out(g, v), in(g, v) {} - - InEdgeIt &operator++() { - if (out != INVALID) { - ++out; - } else { - ++in; - } - return *this; - } - - operator Edge() const { - if (out == INVALID && in == INVALID) return INVALID; - return out != INVALID ? backward(out) : forward(in); - } - - bool operator==(const Edge i) const {return Edge(*this) == i;} - bool operator!=(const Edge i) const {return Edge(*this) != i;} - bool operator<(const Edge i) const {return Edge(*this) < i;} - }; - - class SymEdgeIt : public Parent::EdgeIt { - - public: - SymEdgeIt() {} - - SymEdgeIt(const SymSmartGraph& g) - : SymSmartGraph::Parent::EdgeIt(g) {} - - SymEdgeIt(const SymSmartGraph& g, SymEdge e) - : SymSmartGraph::Parent::EdgeIt(g, e) {} - - SymEdgeIt(Invalid i) - : SymSmartGraph::Parent::EdgeIt(INVALID) {} - - SymEdgeIt& operator++() { - SymSmartGraph::Parent::EdgeIt::operator++(); - return *this; - } - - operator SymEdge() const { - return SymEdge - (static_cast(*this)); - } - bool operator==(const SymEdge i) const {return SymEdge(*this) == i;} - bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;} - bool operator<(const SymEdge i) const {return SymEdge(*this) < i;} - }; - - class EdgeIt { - SymEdgeIt it; - bool fw; - public: - EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {} - EdgeIt (Invalid i) : it(i) { } - EdgeIt(const SymSmartGraph& g, Edge e) - : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { } - EdgeIt() { } - EdgeIt& operator++() { - fw = !fw; - if (fw) ++it; - return *this; - } - operator Edge() const { - if (it == INVALID) return INVALID; - return fw ? forward(it) : backward(it); - } - bool operator==(const Edge i) const {return Edge(*this) == i;} - bool operator!=(const Edge i) const {return Edge(*this) != i;} - bool operator<(const Edge i) const {return Edge(*this) < i;} - - }; - - ///Number of nodes. - int nodeNum() const { return Parent::nodeNum(); } - ///Number of edges. - int edgeNum() const { return 2*Parent::edgeNum(); } - ///Number of symmetric edges. - int symEdgeNum() const { return Parent::edgeNum(); } - - /// Maximum node ID. - - /// Maximum node ID. - ///\sa id(Node) - int maxNodeId() const { return Parent::maxNodeId(); } - /// Maximum edge ID. - - /// Maximum edge ID. - ///\sa id(Edge) - int maxEdgeId() const { return 2*Parent::maxEdgeId(); } - /// Maximum symmetric edge ID. - - /// Maximum symmetric edge ID. - ///\sa id(SymEdge) - int maxSymEdgeId() const { return Parent::maxEdgeId(); } - - - Node tail(Edge e) const { - return (e.id & 1) == 0 ? - Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e)); - } - - Node head(Edge e) const { - return (e.id & 1) == 0 ? - Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e)); - } - - Node tail(SymEdge e) const { - return Parent::tail(e); - } - - Node head(SymEdge e) const { - return Parent::head(e); - } - - NodeIt& first(NodeIt& v) const { - v=NodeIt(*this); return v; } - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); return e; } - SymEdgeIt& first(SymEdgeIt& e) const { - e=SymEdgeIt(*this); return e; } - OutEdgeIt& first(OutEdgeIt& e, const Node v) const { - e=OutEdgeIt(*this,v); return e; } - InEdgeIt& first(InEdgeIt& e, const Node v) const { - e=InEdgeIt(*this,v); return e; } - - /// Node ID. - - /// The ID of a valid Node is a nonnegative integer not greater than - /// \ref maxNodeId(). The range of the ID's is not surely continuous - /// and the greatest node ID can be actually less then \ref maxNodeId(). - /// - /// The ID of the \ref INVALID node is -1. - ///\return The ID of the node \c v. - static int id(Node v) { return Parent::id(v); } - /// Edge ID. - - /// The ID of a valid Edge is a nonnegative integer not greater than - /// \ref maxEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxEdgeId(). - /// - /// The ID of the \ref INVALID edge is -1. - ///\return The ID of the edge \c e. - static int id(Edge e) { return e.id; } - - /// The ID of a valid SymEdge is a nonnegative integer not greater than - /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxSymEdgeId(). - /// - /// The ID of the \ref INVALID symmetric edge is -1. - ///\return The ID of the edge \c e. - static int id(SymEdge e) { return Parent::id(e); } - - /// Adds a new node to the graph. - - /// \warning It adds the new node to the front of the list. - /// (i.e. the lastly added node becomes the first.) - Node addNode() { - return Parent::addNode(); - } - - SymEdge addEdge(Node u, Node v) { - SymEdge se = Parent::addEdge(u, v); - edge_maps.add(forward(se)); - edge_maps.add(backward(se)); - return se; - } - - /// Finds an edge between two nodes. - - /// Finds an edge from node \c u to node \c v. - /// - /// If \c prev is \ref INVALID (this is the default value), then - /// It finds the first edge from \c u to \c v. Otherwise it looks for - /// the next edge from \c u to \c v after \c prev. - /// \return The found edge or INVALID if there is no such an edge. - Edge findEdge(Node u, Node v, Edge prev = INVALID) - { - if (prev == INVALID || id(prev) & 1 == 0) { - SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); - if (se != INVALID) return forward(se); - } else { - SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); - if (se != INVALID) return backward(se); - } - return INVALID; - } - -// /// Finds an symmetric edge between two nodes. - -// /// Finds an symmetric edge from node \c u to node \c v. -// /// -// /// If \c prev is \ref INVALID (this is the default value), then -// /// It finds the first edge from \c u to \c v. Otherwise it looks for -// /// the next edge from \c u to \c v after \c prev. -// /// \return The found edge or INVALID if there is no such an edge. - -// SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID) -// { -// if (prev == INVALID || id(prev) & 1 == 0) { -// SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); -// if (se != INVALID) return se; -// } else { -// SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); -// if (se != INVALID) return se; -// } -// return INVALID; -// } - - public: - - void clear() { - edge_maps.clear(); - Parent::clear(); - } - - static Edge opposite(Edge e) { - return Edge(id(e) ^ 1); - } - - static Edge forward(SymEdge e) { - return Edge(id(e) << 1); - } - - static Edge backward(SymEdge e) { - return Edge((id(e) << 1) | 1); - } - - }; - ///Graph for bidirectional edges. - - ///The purpose of this graph structure is to handle graphs - ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair - ///of oppositely directed edges. - ///There is a new edge map type called - ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap" - ///that complements this - ///feature by - ///storing shared values for the edge pairs. The usual - ///\ref Graph::EdgeMap "EdgeMap" - ///can be used - ///as well. - /// - ///The oppositely directed edge can also be obtained easily - ///using \ref opposite. - ///\warning It shares the similarity with \ref SmartGraph that - ///it is not possible to delete edges or nodes from the graph. - //\sa SmartGraph. - - /* class SymSmartGraph : public SmartGraph - { - public: - typedef SymSmartGraph Graph; - - // Create symmetric map registry. - CREATE_SYM_EDGE_MAP_REGISTRY; - // Create symmetric edge map. - CREATE_SYM_EDGE_MAP(ArrayMap); - - - SymSmartGraph() : SmartGraph() { } - SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { } - ///Adds a pair of oppositely directed edges to the graph. - Edge addEdge(Node u, Node v) - { - Edge e = SmartGraph::addEdge(u,v); - Edge f = SmartGraph::addEdge(v,u); - sym_edge_maps.add(e); - sym_edge_maps.add(f); - return e; - } - - ///The oppositely directed edge. - - ///Returns the oppositely directed - ///pair of the edge \c e. - static Edge opposite(Edge e) - { - Edge f; - f.n = e.n - 2*(e.n%2) + 1; - return f; - } - - - };*/ - /// @} } //namespace lemon diff -r f2ea4aac9ada -r c94ef40a22ce src/lemon/suurballe.h --- a/src/lemon/suurballe.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/lemon/suurballe.h Wed Oct 27 22:38:50 2004 +0000 @@ -125,12 +125,10 @@ paths.resize(k); for (int j=0; j +#include -#include -#include +#include ///\ingroup graphmaps ///\file @@ -31,34 +31,41 @@ /// \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 MapRegistry The MapRegistry that the maps will belong to. - * \param Value The value type of the map. - * - * \author Balazs Dezso - */ - - template - class VectorMap : public MapRegistry::MapBase { - template friend class VectorMap; + /// 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 AlterationObserverRegistry 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 + class VectorMap : public AlterationObserverRegistry<_Item>::ObserverBase { public: - /// The graph type of the maps. - typedef typename MapRegistry::Graph Graph; - /// The key type of the maps. - typedef typename MapRegistry::KeyType KeyType; - /// The iterator to iterate on the keys. - typedef typename MapRegistry::KeyIt KeyIt; + /// The graph type of the map. + typedef _Graph Graph; + /// The key type of the map. + typedef _Item KeyType; + /// The id map type of the map. + typedef _IdMap IdMap; + /// The registry type of the map. + typedef AlterationObserverRegistry<_Item> Registry; + /// The value type of the map. + typedef _Value Value; /// The map type. typedef VectorMap Map; - /// The MapBase of the Map which implements the core regisitry function. - typedef typename MapRegistry::MapBase MapBase; + /// The base class of the map. + typedef typename Registry::ObserverBase Parent; private: @@ -67,7 +74,6 @@ public: - /// The value type of the map. typedef Value ValueType; /// The reference type of the map; @@ -82,95 +88,98 @@ /// The pointer type of the map; typedef typename Container::const_pointer ConstPointerType; - /// Constructor to attach the new map into a registry. + /// Constructor to attach the new map into the registry. - /** Constructor to attach the new map into a registry. - * It adds all the nodes or edges of the graph to the map. - */ - VectorMap(const Graph& g, MapRegistry& r) - : MapBase(g, r), container(KeyInfo::maxId(g)+1) {} + /// 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, Registry& _r) : graph(&_g) { + attach(_r); + build(); + } /// Constructor uses given value to initialize the map. - /** Constructor uses given value to initialize the map. - * It adds all the nodes or edges of the graph to the map. - */ - VectorMap(const Graph& g, MapRegistry& r, const Value& v) - : MapBase(g, r), container(KeyInfo::maxId(g)+1, v) {} + /// 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, Registry& r, const Value& v) : graph(&g) { + attach(r); + container.resize(IdMap(*graph).maxId() + 1, v); + } - /// Assign operator to copy a map of an other map type. - - /** Assign operator to copy a map of an other map type. - * This map's value type must be assignable by the other - * map type's value type. - */ - template - VectorMap(const VectorMap& c) - : MapBase(c), container(c.container.size()) { - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); - container[id] = c.container[id]; + VectorMap(const VectorMap& copy) : graph(copy.getGraph()) { + if (copy.attached()) { + attach(*copy.getRegistry()); + container = copy.container; } } - /// Assign operator to copy a map of an other map type. - /** Assign operator to copy a map of an other map type. - * This map's value type must be assignable by the other - * map type's value type. + /** Assign operator to copy a map of the same map type. */ - template - VectorMap& operator=(const VectorMap& c) { - if (MapBase::getGraph() != c.getGraph()) { - MapBase::operator=(c); - container.resize(c.container.size()); + VectorMap& operator=(const VectorMap& copy) { + if (© == this) return *this; + + if (graph != copy.graph) { + if (attached()) { + detach(); + } + if (copy.attached()) { + attach(*copy.getRegistry()); + } } - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { - int id = KeyInfo::id(*MapBase::getGraph(), it); - container[id] = c.container[id]; + container = copy.container; + + return *this; + } + + + virtual ~VectorMap() { + if (attached()) { + detach(); } - return *this; + } + + const Graph* getGraph() const { + return graph; } /// The subcript operator. - /** - * The subscript operator. The map can be subscripted by the - * actual keys of the graph. - */ + /// The subscript operator. The map can be subscripted by the + /// actual items of the graph. + ReferenceType operator[](const KeyType& key) { - int id = KeyInfo::id(*MapBase::getGraph(), key); - return container[id]; + return container[IdMap(*graph)[key]]; } /// The const subcript operator. - /** - * The const subscript operator. The map can be subscripted by the - * actual keys of the graph. - */ + /// The const subscript operator. The map can be subscripted by the + /// actual items of the graph. + ConstReferenceType operator[](const KeyType& key) const { - int id = KeyInfo::id(*MapBase::getGraph(), key); - return container[id]; + return container[IdMap(*graph)[key]]; } - ///Setter function of the map. - /** Setter function of the map. Equivalent with map[key] = val. - * This is a compatibility feature with the not dereferable maps. - */ - void set(const KeyType& key, const ValueType& val) { - int id = KeyInfo::id(*MapBase::getGraph(), key); - container[id] = val; + /// The setter function of the map. + + /// It the same as operator[](key) = value expression. + /// + + void set(const KeyType& key, const ValueType& value) { + (*this)[key] = value; } + /// Adds a new key to the map. - /** Adds a new key to the map. It called by the map registry - * and it overrides the \ref MapRegistry::MapBase MapBase's - * add() member function. - */ + /// 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 KeyType& key) { - int id = KeyInfo::id(*MapBase::getGraph(), key); + int id = IdMap(*graph)[key]; if (id >= (int)container.size()) { container.resize(id + 1); } @@ -178,93 +187,94 @@ /// Erases a key from the map. - /** Erase a key from the map. It called by the map registry - * and it overrides the \ref MapRegistry::MapBase MapBase's - * erase() member function. - */ + /// 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 KeyType& key) {} - /// Makes empty the map. + /// Buildes the map. + + /// It buildes the map. It called by the observer registry + /// and it overrides the build() member function of the observer base. - /** Makes empty the map. It called by the map registry - * and it overrides the \ref MapRegistry::MapBase MapBase's - * clear() member function. - */ + void build() { + container.resize(IdMap(*graph).maxId() + 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(); } - /// 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: Container container; + const Graph *graph; + }; + + + template + class VectorMappableGraphExtender : public _Base { public: - // STL compatibility typedefs. - typedef Iterator iterator; - typedef ConstIterator const_iterator; - typedef typename Iterator::PairValueType value_type; - typedef typename Iterator::KeyType key_type; - typedef typename Iterator::ValueType data_type; - typedef typename Iterator::PairReferenceType reference; - typedef typename Iterator::PairPointerType pointer; - typedef typename ConstIterator::PairReferenceType const_reference; - typedef typename ConstIterator::PairPointerType const_pointer; - typedef int difference_type; + + 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::NodeObserverRegistry NodeObserverRegistry; + + typedef typename Parent::Edge Edge; + typedef typename Parent::EdgeIt EdgeIt; + typedef typename Parent::EdgeIdMap EdgeIdMap; + typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry; + + + + template + class NodeMap : public VectorMap { + public: + typedef VectorMappableGraphExtender<_Base> Graph; + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIdMap NodeIdMap; + + typedef VectorMap Parent; + + typedef typename Parent::Graph Graph; + typedef typename Parent::Value Value; + + NodeMap(const Graph& g) + : Parent(g, g.getNodeObserverRegistry()) {} + NodeMap(const Graph& g, const Value& v) + : Parent(g, g.getNodeObserverRegistry(), v) {} + + }; + + template + class EdgeMap : public VectorMap { + public: + typedef VectorMappableGraphExtender<_Base> Graph; + + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIdMap EdgeIdMap; + + typedef VectorMap Parent; + + typedef typename Parent::Graph Graph; + typedef typename Parent::Value Value; + + EdgeMap(const Graph& g) + : Parent(g, g.getEdgeObserverRegistry()) {} + EdgeMap(const Graph& g, const Value& v) + : Parent(g, g.getEdgeObserverRegistry(), v) {} + + }; + }; /// @} diff -r f2ea4aac9ada -r c94ef40a22ce src/test/Makefile.am --- a/src/test/Makefile.am Mon Oct 25 13:29:46 2004 +0000 +++ b/src/test/Makefile.am Wed Oct 27 22:38:50 2004 +0000 @@ -2,17 +2,22 @@ EXTRA_DIST = preflow_graph.dim #input file for preflow_test.cc -noinst_HEADERS = test_tools.h graph_test.h sym_graph_test.h +noinst_HEADERS = \ + test_tools.h \ + graph_test.h \ + sym_graph_test.h \ + map_test.h \ + graph_utils_test.h check_PROGRAMS = \ bfs_test \ dfs_test \ dijkstra_test \ graph_test \ - sym_graph_test \ - graph_wrapper_test \ + graph_utils_test \ kruskal_test \ min_cost_flow_test \ + new_graph_test \ suurballe_test \ path_test \ preflow_test \ @@ -20,6 +25,7 @@ test_tools_pass \ time_measure_test \ unionfind_test \ + graph_wrapper_test \ xy_test TESTS = $(check_PROGRAMS) @@ -29,10 +35,11 @@ dfs_test_SOURCES = dfs_test.cc dijkstra_test_SOURCES = dijkstra_test.cc graph_test_SOURCES = graph_test.cc -sym_graph_test_SOURCES = sym_graph_test.cc +graph_utils_test_SOURCES = graph_utils_test.cc graph_wrapper_test_SOURCES = graph_wrapper_test.cc kruskal_test_SOURCES = kruskal_test.cc min_cost_flow_test_SOURCES = min_cost_flow_test.cc +new_graph_test_SOURCES = new_graph_test.cc suurballe_test_SOURCES = suurballe_test.cc path_test_SOURCES = path_test.cc preflow_test_SOURCES = preflow_test.cc diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_factory_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/graph_factory_test.cc Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,154 @@ +/* -*- C++ -*- + * src/test/graph_test.cc - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 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. + * + */ + +#include +#include +#include +#include +#include +#include + +#include"test_tools.h" +#include"graph_test.h" + +/** +\file +This test makes consistency checks of list graph structures. + +G.addNode(), G.addEdge(), G.tail(), G.head() + +\todo Checks for empty graphs and isolated points. +conversion. +*/ + +using namespace lemon; + +template void bidirPetersen(Graph &G) +{ + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + + checkGraphEdgeList(G,15); + + std::vector ee; + + for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e); + + for(typename std::vector::iterator p=ee.begin();p!=ee.end();p++) + G.addEdge(G.head(*p),G.tail(*p)); +} + +template void checkPetersen(Graph &G) +{ + typedef typename Graph::Node Node; + + typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::NodeIt NodeIt; + + checkGraphNodeList(G,10); + checkGraphEdgeList(G,30); + + for(NodeIt n(G);n!=INVALID;++n) { + checkGraphInEdgeList(G,n,3); + checkGraphOutEdgeList(G,n,3); + } +} + +//Compile Graph +template void lemon::skeleton::checkCompileStaticGraph +(skeleton::StaticGraph &); + +template +void lemon::skeleton::checkCompileExtendableGraph +(skeleton::ExtendableGraph &); + +template +void lemon::skeleton::checkCompileErasableGraph +(skeleton::ErasableGraph &); + +//Compile SmartGraph +template +void lemon::skeleton::checkCompileExtendableGraph(SmartGraph &); +template +void lemon::skeleton::checkCompileGraphFindEdge(SmartGraph &); + +//Compile SymSmartGraph +//template void hugo::checkCompileGraph(SymSmartGraph &); +//template void hugo::checkCompileGraphFindEdge(SymSmartGraph &); + +//Compile ListGraph +template +void lemon::skeleton::checkCompileExtendableGraph(ListGraph &); +template +void lemon::skeleton::checkCompileErasableGraph(ListGraph &); +template +void lemon::skeleton::checkCompileGraphFindEdge(ListGraph &); + + +//Compile SymListGraph +//template void hugo::checkCompileGraph(SymListGraph &); +//template void hugo::checkCompileErasableGraph(SymListGraph &); +//template void hugo::checkCompileGraphFindEdge(SymListGraph &); + +//Compile FullGraph +template void lemon::skeleton::checkCompileStaticGraph(FullGraph &); +template +void lemon::skeleton::checkCompileGraphFindEdge(FullGraph &); + + +int main() +{ + { + SmartGraph G; + addPetersen(G); + bidirPetersen(G); + checkPetersen(G); + } + { + ListGraph G; + addPetersen(G); + bidirPetersen(G); + checkPetersen(G); + } + { + // SymSmartGraph G; + // addPetersen(G); + // checkPetersen(G); + } + { + // SymListGraph G; + // addPetersen(G); + // checkPetersen(G); + } + + ///\file + ///\todo map tests. + ///\todo copy constr tests. + + + // Some map tests. + // FIXME: These shouldn't be here. + using namespace skeleton; + function_requires< ReadMapConcept< ReadMap > >(); + function_requires< WriteMapConcept< WriteMap > >(); + function_requires< ReadWriteMapConcept< ReadWriteMap > >(); + function_requires< ReferenceMapConcept< ReferenceMap > >(); + + + std::cout << __FILE__ ": All tests passed.\n"; + + return 0; +} diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_test.cc --- a/src/test/graph_test.cc Mon Oct 25 13:29:46 2004 +0000 +++ b/src/test/graph_test.cc Wed Oct 27 22:38:50 2004 +0000 @@ -1,157 +1,67 @@ -/* -*- C++ -*- - * src/test/graph_test.cc - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2004 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. - * - */ +// -*- c++ -*- -#include -#include -#include -#include -#include +#include +#include -#include"test_tools.h" -#include"graph_test.h" +#include +#include +#include +#include -/** -\file -This test makes consistency checks of list graph structures. +#include "test_tools.h" +#include "graph_test.h" +#include "map_test.h" -G.addNode(), G.addEdge(), G.tail(), G.head() - -\todo Checks for empty graphs and isolated points. -conversion. -*/ using namespace lemon; +using namespace lemon::skeleton; -template void bidirPetersen(Graph &G) -{ - typedef typename Graph::Edge Edge; - typedef typename Graph::EdgeIt EdgeIt; - - checkGraphEdgeList(G,15); - - std::vector ee; - - for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e); - for(typename std::vector::iterator p=ee.begin();p!=ee.end();p++) - G.addEdge(G.head(*p),G.tail(*p)); -} +int main() { + ///\file + { // checking graph components + function_requires >(); -template void checkPetersen(Graph &G) -{ - typedef typename Graph::Node Node; + function_requires >(); - typedef typename Graph::EdgeIt EdgeIt; - typedef typename Graph::NodeIt NodeIt; + function_requires >(); + function_requires >(); - checkGraphNodeList(G,10); - checkGraphEdgeList(G,30); + function_requires >(); + function_requires >(); + function_requires >(); - for(NodeIt n(G);n!=INVALID;++n) { - checkGraphInEdgeList(G,n,3); - checkGraphOutEdgeList(G,n,3); - } -} + function_requires >(); -//Compile Graph -template void lemon::skeleton::checkCompileStaticGraph -(skeleton::StaticGraph &); + function_requires >(); + function_requires >(); -template -void lemon::skeleton::checkCompileExtendableGraph -(skeleton::ExtendableGraph &); + function_requires >(); + function_requires >(); + function_requires >(); + } + { // checking skeleton graphs + function_requires >(); + function_requires >(); + function_requires >(); + } + { // checking list graph + function_requires >(); -template -void lemon::skeleton::checkCompileErasableGraph -(skeleton::ErasableGraph &); + checkGraph(); + checkGraphNodeMap(); + checkGraphEdgeMap(); + } + { // checking smart graph + function_requires >(); -//Compile SmartGraph -template -void lemon::skeleton::checkCompileExtendableGraph(SmartGraph &); -template -void lemon::skeleton::checkCompileGraphFindEdge(SmartGraph &); - -//Compile SymSmartGraph -//template void hugo::checkCompileGraph(SymSmartGraph &); -//template void hugo::checkCompileGraphFindEdge(SymSmartGraph &); - -//Compile ListGraph -template -void lemon::skeleton::checkCompileExtendableGraph(ListGraph &); -template -void lemon::skeleton::checkCompileErasableGraph(ListGraph &); -template -void lemon::skeleton::checkCompileGraphFindEdge(ListGraph &); - - -//Compile SymListGraph -//template void hugo::checkCompileGraph(SymListGraph &); -//template void hugo::checkCompileErasableGraph(SymListGraph &); -//template void hugo::checkCompileGraphFindEdge(SymListGraph &); - -//Compile FullGraph -template void lemon::skeleton::checkCompileStaticGraph(FullGraph &); -template -void lemon::skeleton::checkCompileGraphFindEdge(FullGraph &); - -//Compile EdgeSet -template void lemon::skeleton::checkCompileExtendableGraph > -(EdgeSet &); -template void lemon::skeleton::checkCompileGraphEraseEdge > -(EdgeSet &); -template void lemon::skeleton::checkCompileGraphFindEdge > -(EdgeSet &); - -//Compile EdgeSet -template void lemon::skeleton::checkCompileExtendableGraph > -(EdgeSet &); -template void lemon::skeleton::checkCompileGraphEraseEdge > -(EdgeSet &); -template void lemon::skeleton::checkCompileGraphFindEdge > -(EdgeSet &); - - -int main() -{ - { - SmartGraph G; - addPetersen(G); - bidirPetersen(G); - checkPetersen(G); + checkGraph(); + checkGraphNodeMap(); + checkGraphEdgeMap(); } - { - ListGraph G; - addPetersen(G); - bidirPetersen(G); - checkPetersen(G); + { // checking full graph + function_requires >(); } - { - // SymSmartGraph G; - // addPetersen(G); - // checkPetersen(G); - } - { - // SymListGraph G; - // addPetersen(G); - // checkPetersen(G); - } - - ///\file - ///\todo map tests. - ///\todo copy constr tests. std::cout << __FILE__ ": All tests passed.\n"; diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_test.h --- a/src/test/graph_test.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/test/graph_test.h Wed Oct 27 22:38:50 2004 +0000 @@ -21,56 +21,64 @@ //! \ingroup misc //! \file -//! \brief Some utility to test graph classes. +//! \brief Some utility and test cases to test graph classes. namespace lemon { template void checkGraphNodeList(Graph &G, int nn) - { - typename Graph::NodeIt n(G); - for(int i=0;i void checkGraphEdgeList(Graph &G, int nn) - { - typedef typename Graph::EdgeIt EdgeIt; + template + void checkGraphEdgeList(Graph &G, int nn) + { + typedef typename Graph::EdgeIt EdgeIt; - EdgeIt e(G); - for(int i=0;i void checkGraphOutEdgeList(Graph &G, - typename Graph::Node n, - int nn) - { - typename Graph::OutEdgeIt e(G,n); - for(int i=0;i + void checkGraphOutEdgeList(Graph &G, typename Graph::Node n, int nn) + { + typename Graph::OutEdgeIt e(G,n); + for(int i=0;i void checkGraphInEdgeList(Graph &G, - typename Graph::Node n, - int nn) - { - typename Graph::InEdgeIt e(G,n); - for(int i=0;i void + checkGraphInEdgeList(Graph &G, typename Graph::Node n, int nn) + { + typename Graph::InEdgeIt e(G,n); + for(int i=0;i + void checkGraph() { + const int num = 5; + Graph G; + addPetersen(G, num); + bidirGraph(G); + checkBidirPetersen(G, num); + } ///\file ///\todo Check head(), tail() as well; diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_utils_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/graph_utils_test.cc Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,29 @@ +// -*- c++ -*- + +#include +#include + +#include +#include +#include + +#include "test_tools.h" +#include "graph_utils_test.h" + + +using namespace lemon; + + +int main() { + ///\file + { // checking list graph + checkGraphCounters(); + } + { // checking smart graph + checkGraphCounters(); + } + + std::cout << __FILE__ ": All tests passed.\n"; + + return 0; +} diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_utils_test.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/graph_utils_test.h Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,44 @@ +/* -*- C++ -*- + * src/test/graph_utils_test.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 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_TEST_GRAPH_UTILS_TEST_H +#define LEMON_TEST_GRAPH_UTILS_TEST_H + + +#include "test_tools.h" + +//! \ingroup misc +//! \file +//! \brief Test cases for graph utils. +namespace lemon { + + template + void checkGraphCounters() { + const int num = 5; + Graph graph; + addPetersen(graph, num); + bidirGraph(graph); + check(countNodes(graph) == 2*num, "Wrong node counter."); + check(countEdges(graph) == 6*num, "Wrong edge counter."); + for (typename Graph::NodeIt it(graph); it != INVALID; ++it) { + check(countOutEdges(graph, it) == 3, "Wrong out degree counter."); + check(countInEdges(graph, it) == 3, "Wrong in degree counter."); + } + } + +} //namespace lemon + + +#endif diff -r f2ea4aac9ada -r c94ef40a22ce src/test/graph_wrapper_test.cc --- a/src/test/graph_wrapper_test.cc Mon Oct 25 13:29:46 2004 +0000 +++ b/src/test/graph_wrapper_test.cc Wed Oct 27 22:38:50 2004 +0000 @@ -15,8 +15,11 @@ */ #include +#include + #include #include + #include #include #include @@ -32,66 +35,31 @@ */ using namespace lemon; +using namespace lemon::skeleton; typedef SmartGraph Graph; -//Compile GraphWrapper -typedef GraphWrapper GW; -template void lemon::skeleton::checkCompileStaticGraph(GW &); - -//Compile RevGraphWrapper -typedef RevGraphWrapper RevGW; -template void lemon::skeleton::checkCompileStaticGraph(RevGW &); - -//Compile SubGraphWrapper -typedef SubGraphWrapper, - Graph::EdgeMap > SubGW; -template void lemon::skeleton::checkCompileStaticGraph(SubGW &); - -//Compile NodeSubGraphWrapper -typedef NodeSubGraphWrapper > NodeSubGW; -template void lemon::skeleton::checkCompileStaticGraph(NodeSubGW &); - -//Compile EdgeSubGraphWrapper -typedef EdgeSubGraphWrapper > EdgeSubGW; -template void lemon::skeleton::checkCompileStaticGraph(EdgeSubGW &); - -//Compile UndirGraphWrapper -/// \bug UndirGraphWrapper cannot pass the StaticGraph test -//typedef UndirGraphWrapper UndirGW; -//template void checkCompileStaticGraph(UndirGW &); - -//Compile UndirGraph -//typedef UndirGraph UndirG; -//template void checkCompileStaticGraph(UndirG &); - -//Compile SubBidirGraphWrapper -typedef SubBidirGraphWrapper, - Graph::EdgeMap > SubBDGW; -template void lemon::skeleton::checkCompileStaticGraph(SubBDGW &); - -//Compile BidirGraphWrapper -typedef BidirGraphWrapper BidirGW; -template void lemon::skeleton::checkCompileStaticGraph(BidirGW &); - -//Compile BidirGraph -typedef BidirGraph BidirG; -template void lemon::skeleton::checkCompileStaticGraph(BidirG &); - -//Compile ResGraphWrapper -typedef ResGraphWrapper, - Graph::EdgeMap > ResGW; -template void lemon::skeleton::checkCompileStaticGraph(ResGW &); - -//Compile ErasingFirstGraphWrapper -typedef ErasingFirstGraphWrapper > ErasingFirstGW; -template -void lemon::skeleton::checkCompileStaticGraph(ErasingFirstGW &); - int main() { + { + function_requires > >(); + + function_requires > >(); + + function_requires , Graph::EdgeMap > > >(); + function_requires > > >(); + function_requires > > >(); + + function_requires, Graph::EdgeMap > > > (); + + function_requires > >(); + + function_requires, Graph::EdgeMap > > >(); + + function_requires > > >(); + } std::cout << __FILE__ ": All tests passed.\n"; return 0; diff -r f2ea4aac9ada -r c94ef40a22ce src/test/map_test.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/map_test.h Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,95 @@ +/* -*- C++ -*- + * src/test/map_test.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 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_TEST_MAP_TEST_H +#define LEMON_TEST_MAP_TEST_H + + +#include + +#include "test_tools.h" + + +//! \ingroup misc +//! \file +//! \brief Some utility to test map classes. + +namespace lemon { + + + template + void checkGraphNodeMap() { + Graph graph; + const int num = 16; + + typedef typename Graph::Node Node; + + std::vector nodes; + for (int i = 0; i < num; ++i) { + nodes.push_back(graph.addNode()); + } + typedef typename Graph::template NodeMap IntNodeMap; + IntNodeMap map(graph, 42); + for (int i = 0; i < (int)nodes.size(); ++i) { + check(map[nodes[i]] == 42, "Wrong map constructor."); + } + for (int i = 0; i < num; ++i) { + nodes.push_back(graph.addNode()); + map[nodes.back()] = 23; + } + graph.clear(); + nodes.clear(); + } + + template + void checkGraphEdgeMap() { + Graph graph; + const int num = 16; + + typedef typename Graph::Node Node; + typedef typename Graph::Edge Edge; + + std::vector nodes; + for (int i = 0; i < num; ++i) { + nodes.push_back(graph.addNode()); + } + + std::vector edges; + for (int i = 0; i < num; ++i) { + for (int j = 0; j < i; ++j) { + edges.push_back(graph.addEdge(nodes[i], nodes[j])); + } + } + + typedef typename Graph::template EdgeMap IntEdgeMap; + IntEdgeMap map(graph, 42); + + for (int i = 0; i < (int)edges.size(); ++i) { + check(map[edges[i]] == 42, "Wrong map constructor."); + } + + for (int i = 0; i < num; ++i) { + for (int j = i + 1; j < num; ++j) { + edges.push_back(graph.addEdge(nodes[i], nodes[j])); + map[edges.back()] = 23; + } + } + graph.clear(); + edges.clear(); + } + +} + +#endif diff -r f2ea4aac9ada -r c94ef40a22ce src/test/new_graph_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/new_graph_test.cc Wed Oct 27 22:38:50 2004 +0000 @@ -0,0 +1,39 @@ +/* -*- C++ -*- + * src/test/new_graph_test.cc - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 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. + * + */ + +#include +// #include + +using namespace lemon::skeleton; + +// Borrowed from boost: +template inline void ignore_unused_variable_warning(const T&) { } + +int main() +{ + // This is the "right" way to check a concept: + // boost::function_requires< BaseGraphItemConcept >(); + + // which is equivalent (considering compile-time checks) to + // BaseGraphItemConcept bgic; + // bgic.constraints(); + // but not actually call or intatiates anything... + // It's doing aproximately this: + typedef BaseGraphItemConcept CC; + void (CC::*x)() = &CC::constraints; + ignore_unused_variable_warning(x); + // But even more hackish... +} diff -r f2ea4aac9ada -r c94ef40a22ce src/test/test_tools.h --- a/src/test/test_tools.h Mon Oct 25 13:29:46 2004 +0000 +++ b/src/test/test_tools.h Wed Oct 27 22:38:50 2004 +0000 @@ -70,7 +70,7 @@ ///\return The nodes and edges of the generated graph. template -PetStruct addPetersen(Graph &G,int num=5) +PetStruct addPetersen(Graph &G,int num = 5) { PetStruct n; @@ -81,12 +81,50 @@ for(int i=0;i void bidirGraph(Graph &G) +{ + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + + std::vector ee; + + for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e); + + for(typename std::vector::iterator p=ee.begin();p!=ee.end();p++) + G.addEdge(G.head(*p),G.tail(*p)); +} + + +/// \brief Checks the bidirectioned Petersen graph. +/// +/// Checks the bidirectioned Petersen graph. +/// +template void checkBidirPetersen(Graph &G, int num = 5) +{ + typedef typename Graph::Node Node; + + typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::NodeIt NodeIt; + + checkGraphNodeList(G, 2 * num); + checkGraphEdgeList(G, 6 * num); + + for(NodeIt n(G);n!=INVALID;++n) { + checkGraphInEdgeList(G, n, 3); + checkGraphOutEdgeList(G, n, 3); + } +} + ///Structure returned by \ref addSymPetersen(). ///Structure returned by \ref addSymPetersen(). diff -r f2ea4aac9ada -r c94ef40a22ce src/work/klao/TODO --- a/src/work/klao/TODO Mon Oct 25 13:29:46 2004 +0000 +++ b/src/work/klao/TODO Wed Oct 27 22:38:50 2004 +0000 @@ -1,1 +1,3 @@ +full_graph.h -t atnez(et)ni! + megcsinalni, hogy mukodjon a kereses a doksiban