diff --git a/lemon/Makefile.am b/lemon/Makefile.am --- a/lemon/Makefile.am +++ b/lemon/Makefile.am @@ -21,7 +21,17 @@ lemon/tolerance.h bits_HEADERS += \ + lemon/bits/alteration_notifier.h \ + lemon/bits/array_map.h \ + lemon/bits/base_extender.h \ + lemon/bits/default_map.h \ lemon/bits/invalid.h \ - lemon/bits/utility.h + lemon/bits/map_extender.h \ + lemon/bits/utility.h \ + lemon/bits/vector_map.h concept_HEADERS += + lemon/concept_check.h \ + lemon/concepts/digraph.h \ + lemon/concepts/graph.h \ + lemon/concepts/graph_components.h diff --git a/lemon/bits/alteration_notifier.h b/lemon/bits/alteration_notifier.h new file mode 100644 --- /dev/null +++ b/lemon/bits/alteration_notifier.h @@ -0,0 +1,485 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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_BITS_ALTERATION_NOTIFIER_H +#define LEMON_BITS_ALTERATION_NOTIFIER_H + +#include +#include + +#include + +///\ingroup graphbits +///\file +///\brief Observer notifier for graph alteration observers. + +namespace lemon { + + /// \ingroup graphbits + /// + /// \brief Notifier class to notify observes about alterations in + /// a container. + /// + /// The simple graph's can be refered as two containers, one node container + /// and one edge container. But they are not standard containers they + /// does not store values directly they are just key continars for more + /// value containers which are the node and edge maps. + /// + /// The graph's node and edge sets can be changed as we add or erase + /// nodes and edges in the graph. Lemon would like to handle easily + /// that the node and edge maps should contain values for all nodes or + /// edges. If we want to check on every indicing if the map contains + /// the current indicing key that cause a drawback in the performance + /// in the library. We use another solution we notify all maps about + /// an alteration in the graph, which cause only drawback on the + /// alteration of the graph. + /// + /// This class provides an interface to the container. The \e first() and \e + /// next() member functions make possible to iterate on the keys of the + /// container. The \e id() function returns an integer id for each key. + /// The \e maxId() function gives back an upper bound of the ids. + /// + /// For the proper functonality of this class, we should notify it + /// about each alteration in the container. The alterations have four type + /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and + /// \e erase() signals that only one or few items added or erased to or + /// from the graph. If all items are erased from the graph or from an empty + /// graph a new graph is builded then it can be signaled with the + /// clear() and build() members. Important rule that if we erase items + /// from graph we should first signal the alteration and after that erase + /// them from the container, on the other way on item addition we should + /// first extend the container and just after that signal the alteration. + /// + /// The alteration can be observed with a class inherited from the + /// \e ObserverBase nested class. The signals can be handled with + /// overriding the virtual functions defined in the base class. The + /// observer base can be attached to the notifier with the + /// \e attach() member and can be detached with detach() function. The + /// alteration handlers should not call any function which signals + /// an other alteration in the same notifier and should not + /// detach any observer from the notifier. + /// + /// Alteration observers try to be exception safe. If an \e add() or + /// a \e clear() function throws an exception then the remaining + /// observeres will not be notified and the fulfilled additions will + /// be rolled back by calling the \e erase() or \e clear() + /// functions. Thence the \e erase() and \e clear() should not throw + /// exception. Actullay, it can be throw only + /// \ref AlterationObserver::ImmediateDetach ImmediateDetach + /// exception which detach the observer from the notifier. + /// + /// There are some place when the alteration observing is not completly + /// reliable. If we want to carry out the node degree in the graph + /// as in the \ref InDegMap and we use the reverseEdge that cause + /// unreliable functionality. Because the alteration observing signals + /// only erasing and adding but not the reversing it will stores bad + /// degrees. The sub graph adaptors cannot signal the alterations because + /// just a setting in the filter map can modify the graph and this cannot + /// be watched in any way. + /// + /// \param _Container The container which is observed. + /// \param _Item The item type which is obserbved. + /// + /// \author Balazs Dezso + + template + class AlterationNotifier { + public: + + typedef True Notifier; + + typedef _Container Container; + typedef _Item Item; + + /// \brief Exception which can be called from \e clear() and + /// \e erase(). + /// + /// From the \e clear() and \e erase() function only this + /// exception is allowed to throw. The exception immediatly + /// detaches the current observer from the notifier. Because the + /// \e clear() and \e erase() should not throw other exceptions + /// it can be used to invalidate the observer. + struct ImmediateDetach {}; + + /// \brief ObserverBase is the base class for the observers. + /// + /// ObserverBase is the abstract base class for the observers. + /// It will be notified about an item was inserted into or + /// erased from the graph. + /// + /// The observer interface contains some pure virtual functions + /// to override. The add() and erase() functions are + /// to notify the oberver when one item is added or + /// erased. + /// + /// The build() and clear() members are to notify the observer + /// about the container is built from an empty container or + /// is cleared to an empty container. + /// + /// \author Balazs Dezso + + class ObserverBase { + protected: + typedef AlterationNotifier Notifier; + + friend class AlterationNotifier; + + /// \brief Default constructor. + /// + /// Default constructor for ObserverBase. + /// + ObserverBase() : _notifier(0) {} + + /// \brief Constructor which attach the observer into notifier. + /// + /// Constructor which attach the observer into notifier. + ObserverBase(AlterationNotifier& nf) { + attach(nf); + } + + /// \brief Constructor which attach the obserever to the same notifier. + /// + /// Constructor which attach the obserever to the same notifier as + /// the other observer is attached to. + ObserverBase(const ObserverBase& copy) { + if (copy.attached()) { + attach(*copy.notifier()); + } + } + + /// \brief Destructor + virtual ~ObserverBase() { + if (attached()) { + detach(); + } + } + + /// \brief Attaches the observer into an AlterationNotifier. + /// + /// This member attaches the observer into an AlterationNotifier. + /// + void attach(AlterationNotifier& nf) { + nf.attach(*this); + } + + /// \brief Detaches the observer into an AlterationNotifier. + /// + /// This member detaches the observer from an AlterationNotifier. + /// + void detach() { + _notifier->detach(*this); + } + + /// \brief Gives back a pointer to the notifier which the map + /// attached into. + /// + /// This function gives back a pointer to the notifier which the map + /// attached into. + /// + Notifier* notifier() const { return const_cast(_notifier); } + + /// Gives back true when the observer is attached into a notifier. + bool attached() const { return _notifier != 0; } + + private: + + ObserverBase& operator=(const ObserverBase& copy); + + protected: + + Notifier* _notifier; + typename std::list::iterator _index; + + /// \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 + /// more item is added to the container. + /// + /// The add() member function notificates the observer about more item + /// is added to the container. It have to be overrided in the + /// subclasses. + virtual void add(const std::vector& items) = 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 + /// more item is erased from the container. + /// + /// The erase() member function notificates the observer about more item + /// is erased from the container. It have to be overrided in the + /// subclasses. + virtual void erase(const std::vector& items) = 0; + + /// \brief The member function to notificate the observer about the + /// container is built. + /// + /// The build() member function notificates the observer about the + /// container is built from an empty container. It have to be + /// overrided in the subclasses. + + virtual void build() = 0; + + /// \brief The member function to notificate the observer about all + /// items are erased from the container. + /// + /// The clear() member function notificates the observer about all + /// items are erased from the container. It have to be overrided in + /// the subclasses. + virtual void clear() = 0; + + }; + + protected: + + const Container* container; + + typedef std::list Observers; + Observers _observers; + + + public: + + /// \brief Default constructor. + /// + /// The default constructor of the AlterationNotifier. + /// It creates an empty notifier. + AlterationNotifier() + : container(0) {} + + /// \brief Constructor. + /// + /// Constructor with the observed container parameter. + AlterationNotifier(const Container& _container) + : container(&_container) {} + + /// \brief Copy Constructor of the AlterationNotifier. + /// + /// Copy constructor of the AlterationNotifier. + /// It creates only an empty notifier because the copiable + /// notifier's observers have to be registered still into that notifier. + AlterationNotifier(const AlterationNotifier& _notifier) + : container(_notifier.container) {} + + /// \brief Destructor. + /// + /// Destructor of the AlterationNotifier. + /// + ~AlterationNotifier() { + typename Observers::iterator it; + for (it = _observers.begin(); it != _observers.end(); ++it) { + (*it)->_notifier = 0; + } + } + + /// \brief Sets the container. + /// + /// Sets the container. + void setContainer(const Container& _container) { + container = &_container; + } + + protected: + + AlterationNotifier& operator=(const AlterationNotifier&); + + public: + + + + /// \brief First item in the container. + /// + /// Returns the first item in the container. It is + /// for start the iteration on the container. + void first(Item& item) const { + container->first(item); + } + + /// \brief Next item in the container. + /// + /// Returns the next item in the container. It is + /// for iterate on the container. + void next(Item& item) const { + container->next(item); + } + + /// \brief Returns the id of the item. + /// + /// Returns the id of the item provided by the container. + int id(const Item& item) const { + return container->id(item); + } + + /// \brief Returns the maximum id of the container. + /// + /// Returns the maximum id of the container. + int maxId() const { + return container->maxId(Item()); + } + + protected: + + void attach(ObserverBase& observer) { + observer._index = _observers.insert(_observers.begin(), &observer); + observer._notifier = this; + } + + void detach(ObserverBase& observer) { + _observers.erase(observer._index); + observer._index = _observers.end(); + observer._notifier = 0; + } + + public: + + /// \brief Notifies all the registed observers about an item added to + /// the container. + /// + /// It notifies all the registed observers about an item added to + /// the container. + /// + void add(const Item& item) { + typename Observers::reverse_iterator it; + try { + for (it = _observers.rbegin(); it != _observers.rend(); ++it) { + (*it)->add(item); + } + } catch (...) { + typename Observers::iterator jt; + for (jt = it.base(); jt != _observers.end(); ++jt) { + (*jt)->erase(item); + } + throw; + } + } + + /// \brief Notifies all the registed observers about more item added to + /// the container. + /// + /// It notifies all the registed observers about more item added to + /// the container. + /// + void add(const std::vector& items) { + typename Observers::reverse_iterator it; + try { + for (it = _observers.rbegin(); it != _observers.rend(); ++it) { + (*it)->add(items); + } + } catch (...) { + typename Observers::iterator jt; + for (jt = it.base(); jt != _observers.end(); ++jt) { + (*jt)->erase(items); + } + throw; + } + } + + /// \brief Notifies all the registed observers about an item erased from + /// the container. + /// + /// It notifies all the registed observers about an item erased from + /// the container. + /// + void erase(const Item& item) throw() { + typename Observers::iterator it = _observers.begin(); + while (it != _observers.end()) { + try { + (*it)->erase(item); + ++it; + } catch (const ImmediateDetach&) { + it = _observers.erase(it); + (*it)->_index = _observers.end(); + (*it)->_notifier = 0; + } + } + } + + /// \brief Notifies all the registed observers about more item erased + /// from the container. + /// + /// It notifies all the registed observers about more item erased from + /// the container. + /// + void erase(const std::vector& items) { + typename Observers::iterator it = _observers.begin(); + while (it != _observers.end()) { + try { + (*it)->erase(items); + ++it; + } catch (const ImmediateDetach&) { + it = _observers.erase(it); + (*it)->_index = _observers.end(); + (*it)->_notifier = 0; + } + } + } + + /// \brief Notifies all the registed observers about the container is + /// built. + /// + /// Notifies all the registed observers about the container is built + /// from an empty container. + void build() { + typename Observers::reverse_iterator it; + try { + for (it = _observers.rbegin(); it != _observers.rend(); ++it) { + (*it)->build(); + } + } catch (...) { + typename Observers::iterator jt; + for (jt = it.base(); jt != _observers.end(); ++jt) { + (*jt)->clear(); + } + throw; + } + } + + /// \brief Notifies all the registed observers about all items are + /// erased. + /// + /// Notifies all the registed observers about all items are erased + /// from the container. + void clear() { + typename Observers::iterator it = _observers.begin(); + while (it != _observers.end()) { + try { + (*it)->clear(); + ++it; + } catch (const ImmediateDetach&) { + it = _observers.erase(it); + (*it)->_index = _observers.end(); + (*it)->_notifier = 0; + } + } + } + }; + +} + +#endif diff --git a/lemon/bits/array_map.h b/lemon/bits/array_map.h new file mode 100644 --- /dev/null +++ b/lemon/bits/array_map.h @@ -0,0 +1,346 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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_BITS_ARRAY_MAP_H +#define LEMON_BITS_ARRAY_MAP_H + +#include + +#include +#include +#include +#include + +/// \ingroup graphbits +/// \file +/// \brief Graph map based on the array storage. + +namespace lemon { + + /// \ingroup graphbits + /// + /// \brief Graph map based on the array storage. + /// + /// The ArrayMap template class is graph map structure what + /// automatically updates the map when a key is added to or erased from + /// the map. This map uses the allocators to implement + /// the container functionality. + /// + /// The template parameters are the Graph the current Item type and + /// the Value type of the map. + template + class ArrayMap + : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { + public: + /// The graph type of the maps. + typedef _Graph Graph; + /// The item type of the map. + typedef _Item Item; + /// The reference map tag. + typedef True ReferenceMapTag; + + /// The key type of the maps. + typedef _Item Key; + /// The value type of the map. + typedef _Value Value; + + /// The const reference type of the map. + typedef const _Value& ConstReference; + /// The reference type of the map. + typedef _Value& Reference; + + /// The notifier type. + typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; + + /// The MapBase of the Map which imlements the core regisitry function. + typedef typename Notifier::ObserverBase Parent; + + private: + typedef std::allocator Allocator; + + public: + + /// \brief Graph initialized map constructor. + /// + /// Graph initialized map constructor. + explicit ArrayMap(const Graph& graph) { + Parent::attach(graph.notifier(Item())); + allocate_memory(); + Notifier* nf = Parent::notifier(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it);; + allocator.construct(&(values[id]), Value()); + } + } + + /// \brief Constructor to use default value to initialize the map. + /// + /// It constructs a map and initialize all of the the map. + ArrayMap(const Graph& graph, const Value& value) { + Parent::attach(graph.notifier(Item())); + allocate_memory(); + Notifier* nf = Parent::notifier(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it);; + allocator.construct(&(values[id]), value); + } + } + + /// \brief Constructor to copy a map of the same map type. + /// + /// Constructor to copy a map of the same map type. + ArrayMap(const ArrayMap& copy) : Parent() { + if (copy.attached()) { + attach(*copy.notifier()); + } + capacity = copy.capacity; + if (capacity == 0) return; + values = allocator.allocate(capacity); + Notifier* nf = Parent::notifier(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it);; + allocator.construct(&(values[id]), copy.values[id]); + } + } + + /// \brief Assign operator. + /// + /// This operator assigns for each item in the map the + /// value mapped to the same item in the copied map. + /// The parameter map should be indiced with the same + /// itemset because this assign operator does not change + /// the container of the map. + ArrayMap& operator=(const ArrayMap& cmap) { + return operator=(cmap); + } + + + /// \brief Template assign operator. + /// + /// The given parameter should be conform to the ReadMap + /// concecpt and could be indiced by the current item set of + /// the NodeMap. In this case the value for each item + /// is assigned by the value of the given ReadMap. + template + ArrayMap& operator=(const CMap& cmap) { + checkConcept, CMap>(); + const typename Parent::Notifier* nf = Parent::notifier(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + set(it, cmap[it]); + } + return *this; + } + + /// \brief The destructor of the map. + /// + /// The destructor of the map. + virtual ~ArrayMap() { + if (attached()) { + clear(); + detach(); + } + } + + protected: + + using Parent::attach; + using Parent::detach; + using Parent::attached; + + public: + + /// \brief The subscript operator. + /// + /// The subscript operator. The map can be subscripted by the + /// actual keys of the graph. + Value& operator[](const Key& key) { + int id = Parent::notifier()->id(key); + return values[id]; + } + + /// \brief The const subscript operator. + /// + /// The const subscript operator. The map can be subscripted by the + /// actual keys of the graph. + const Value& operator[](const Key& key) const { + int id = Parent::notifier()->id(key); + return values[id]; + } + + /// \brief 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 Key& key, const Value& val) { + (*this)[key] = val; + } + + protected: + + /// \brief Adds a new key to the map. + /// + /// It adds a new key to the map. It called by the observer notifier + /// and it overrides the add() member function of the observer base. + virtual void add(const Key& key) { + Notifier* nf = Parent::notifier(); + int id = nf->id(key); + if (id >= capacity) { + int new_capacity = (capacity == 0 ? 1 : capacity); + while (new_capacity <= id) { + new_capacity <<= 1; + } + Value* new_values = allocator.allocate(new_capacity); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int jd = nf->id(it);; + if (id != jd) { + allocator.construct(&(new_values[jd]), values[jd]); + allocator.destroy(&(values[jd])); + } + } + if (capacity != 0) allocator.deallocate(values, capacity); + values = new_values; + capacity = new_capacity; + } + allocator.construct(&(values[id]), Value()); + } + + /// \brief Adds more new keys to the map. + /// + /// It adds more new keys to the map. It called by the observer notifier + /// and it overrides the add() member function of the observer base. + virtual void add(const std::vector& keys) { + Notifier* nf = Parent::notifier(); + int max_id = -1; + for (int i = 0; i < int(keys.size()); ++i) { + int id = nf->id(keys[i]); + if (id > max_id) { + max_id = id; + } + } + if (max_id >= capacity) { + int new_capacity = (capacity == 0 ? 1 : capacity); + while (new_capacity <= max_id) { + new_capacity <<= 1; + } + Value* new_values = allocator.allocate(new_capacity); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it); + bool found = false; + for (int i = 0; i < int(keys.size()); ++i) { + int jd = nf->id(keys[i]); + if (id == jd) { + found = true; + break; + } + } + if (found) continue; + allocator.construct(&(new_values[id]), values[id]); + allocator.destroy(&(values[id])); + } + if (capacity != 0) allocator.deallocate(values, capacity); + values = new_values; + capacity = new_capacity; + } + for (int i = 0; i < int(keys.size()); ++i) { + int id = nf->id(keys[i]); + allocator.construct(&(values[id]), Value()); + } + } + + /// \brief Erase a key from the map. + /// + /// Erase a key from the map. It called by the observer notifier + /// and it overrides the erase() member function of the observer base. + virtual void erase(const Key& key) { + int id = Parent::notifier()->id(key); + allocator.destroy(&(values[id])); + } + + /// \brief Erase more keys from the map. + /// + /// Erase more keys from the map. It called by the observer notifier + /// and it overrides the erase() member function of the observer base. + virtual void erase(const std::vector& keys) { + for (int i = 0; i < int(keys.size()); ++i) { + int id = Parent::notifier()->id(keys[i]); + allocator.destroy(&(values[id])); + } + } + + /// \brief Buildes the map. + /// + /// It buildes the map. It called by the observer notifier + /// and it overrides the build() member function of the observer base. + virtual void build() { + Notifier* nf = Parent::notifier(); + allocate_memory(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it);; + allocator.construct(&(values[id]), Value()); + } + } + + /// \brief Clear the map. + /// + /// It erase all items from the map. It called by the observer notifier + /// and it overrides the clear() member function of the observer base. + virtual void clear() { + Notifier* nf = Parent::notifier(); + if (capacity != 0) { + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it); + allocator.destroy(&(values[id])); + } + allocator.deallocate(values, capacity); + capacity = 0; + } + } + + private: + + void allocate_memory() { + int max_id = Parent::notifier()->maxId(); + if (max_id == -1) { + capacity = 0; + values = 0; + return; + } + capacity = 1; + while (capacity <= max_id) { + capacity <<= 1; + } + values = allocator.allocate(capacity); + } + + int capacity; + Value* values; + Allocator allocator; + + }; + +} + +#endif diff --git a/lemon/bits/base_extender.h b/lemon/bits/base_extender.h new file mode 100644 --- /dev/null +++ b/lemon/bits/base_extender.h @@ -0,0 +1,495 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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_BITS_BASE_EXTENDER_H +#define LEMON_BITS_BASE_EXTENDER_H + +#include +#include + +#include +#include + +#include +#include + +///\ingroup digraphbits +///\file +///\brief Extenders for the digraph types +namespace lemon { + + /// \ingroup digraphbits + /// + /// \brief BaseDigraph to BaseGraph extender + template + class UndirDigraphExtender : public Base { + + public: + + typedef Base Parent; + typedef typename Parent::Arc Edge; + typedef typename Parent::Node Node; + + typedef True UndirectedTag; + + class Arc : public Edge { + friend class UndirDigraphExtender; + + protected: + bool forward; + + Arc(const Edge &ue, bool _forward) : + Edge(ue), forward(_forward) {} + + public: + Arc() {} + + /// Invalid arc constructor + Arc(Invalid i) : Edge(i), forward(true) {} + + bool operator==(const Arc &that) const { + return forward==that.forward && Edge(*this)==Edge(that); + } + bool operator!=(const Arc &that) const { + return forward!=that.forward || Edge(*this)!=Edge(that); + } + bool operator<(const Arc &that) const { + return forward> 1), bool(ix & 1)); + } + + Edge edgeFromId(int ix) const { + return Parent::arcFromId(ix); + } + + int id(const Node &n) const { + return Parent::id(n); + } + + int id(const Edge &e) const { + return Parent::id(e); + } + + int id(const Arc &e) const { + return 2 * Parent::id(e) + int(e.forward); + } + + int maxNodeId() const { + return Parent::maxNodeId(); + } + + int maxArcId() const { + return 2 * Parent::maxArcId() + 1; + } + + int maxEdgeId() const { + return Parent::maxArcId(); + } + + + int arcNum() const { + return 2 * Parent::arcNum(); + } + + int edgeNum() const { + return Parent::arcNum(); + } + + Arc findArc(Node s, Node t, Arc p = INVALID) const { + if (p == INVALID) { + Edge arc = Parent::findArc(s, t); + if (arc != INVALID) return direct(arc, true); + arc = Parent::findArc(t, s); + if (arc != INVALID) return direct(arc, false); + } else if (direction(p)) { + Edge arc = Parent::findArc(s, t, p); + if (arc != INVALID) return direct(arc, true); + arc = Parent::findArc(t, s); + if (arc != INVALID) return direct(arc, false); + } else { + Edge arc = Parent::findArc(t, s, p); + if (arc != INVALID) return direct(arc, false); + } + return INVALID; + } + + Edge findEdge(Node s, Node t, Edge p = INVALID) const { + if (s != t) { + if (p == INVALID) { + Edge arc = Parent::findArc(s, t); + if (arc != INVALID) return arc; + arc = Parent::findArc(t, s); + if (arc != INVALID) return arc; + } else if (Parent::s(p) == s) { + Edge arc = Parent::findArc(s, t, p); + if (arc != INVALID) return arc; + arc = Parent::findArc(t, s); + if (arc != INVALID) return arc; + } else { + Edge arc = Parent::findArc(t, s, p); + if (arc != INVALID) return arc; + } + } else { + return Parent::findArc(s, t, p); + } + return INVALID; + } + }; + + template + class BidirBpGraphExtender : public Base { + public: + typedef Base Parent; + typedef BidirBpGraphExtender Digraph; + + typedef typename Parent::Node Node; + typedef typename Parent::Edge Edge; + + + using Parent::first; + using Parent::next; + + using Parent::id; + + class Red : public Node { + friend class BidirBpGraphExtender; + public: + Red() {} + Red(const Node& node) : Node(node) { + LEMON_ASSERT(Parent::red(node) || node == INVALID, + typename Parent::NodeSetError()); + } + Red& operator=(const Node& node) { + LEMON_ASSERT(Parent::red(node) || node == INVALID, + typename Parent::NodeSetError()); + Node::operator=(node); + return *this; + } + Red(Invalid) : Node(INVALID) {} + Red& operator=(Invalid) { + Node::operator=(INVALID); + return *this; + } + }; + + void first(Red& node) const { + Parent::firstRed(static_cast(node)); + } + void next(Red& node) const { + Parent::nextRed(static_cast(node)); + } + + int id(const Red& node) const { + return Parent::redId(node); + } + + class Blue : public Node { + friend class BidirBpGraphExtender; + public: + Blue() {} + Blue(const Node& node) : Node(node) { + LEMON_ASSERT(Parent::blue(node) || node == INVALID, + typename Parent::NodeSetError()); + } + Blue& operator=(const Node& node) { + LEMON_ASSERT(Parent::blue(node) || node == INVALID, + typename Parent::NodeSetError()); + Node::operator=(node); + return *this; + } + Blue(Invalid) : Node(INVALID) {} + Blue& operator=(Invalid) { + Node::operator=(INVALID); + return *this; + } + }; + + void first(Blue& node) const { + Parent::firstBlue(static_cast(node)); + } + void next(Blue& node) const { + Parent::nextBlue(static_cast(node)); + } + + int id(const Blue& node) const { + return Parent::redId(node); + } + + Node source(const Edge& arc) const { + return red(arc); + } + Node target(const Edge& arc) const { + return blue(arc); + } + + void firstInc(Edge& arc, bool& dir, const Node& node) const { + if (Parent::red(node)) { + Parent::firstFromRed(arc, node); + dir = true; + } else { + Parent::firstFromBlue(arc, node); + dir = static_cast(arc) == INVALID; + } + } + void nextInc(Edge& arc, bool& dir) const { + if (dir) { + Parent::nextFromRed(arc); + } else { + Parent::nextFromBlue(arc); + if (arc == INVALID) dir = true; + } + } + + class Arc : public Edge { + friend class BidirBpGraphExtender; + protected: + bool forward; + + Arc(const Edge& arc, bool _forward) + : Edge(arc), forward(_forward) {} + + public: + Arc() {} + Arc (Invalid) : Edge(INVALID), forward(true) {} + bool operator==(const Arc& i) const { + return Edge::operator==(i) && forward == i.forward; + } + bool operator!=(const Arc& i) const { + return Edge::operator!=(i) || forward != i.forward; + } + bool operator<(const Arc& i) const { + return Edge::operator<(i) || + (!(i.forward(arc)); + arc.forward = true; + } + + void next(Arc& arc) const { + if (!arc.forward) { + Parent::next(static_cast(arc)); + } + arc.forward = !arc.forward; + } + + void firstOut(Arc& arc, const Node& node) const { + if (Parent::red(node)) { + Parent::firstFromRed(arc, node); + arc.forward = true; + } else { + Parent::firstFromBlue(arc, node); + arc.forward = static_cast(arc) == INVALID; + } + } + void nextOut(Arc& arc) const { + if (arc.forward) { + Parent::nextFromRed(arc); + } else { + Parent::nextFromBlue(arc); + arc.forward = static_cast(arc) == INVALID; + } + } + + void firstIn(Arc& arc, const Node& node) const { + if (Parent::blue(node)) { + Parent::firstFromBlue(arc, node); + arc.forward = true; + } else { + Parent::firstFromRed(arc, node); + arc.forward = static_cast(arc) == INVALID; + } + } + void nextIn(Arc& arc) const { + if (arc.forward) { + Parent::nextFromBlue(arc); + } else { + Parent::nextFromRed(arc); + arc.forward = static_cast(arc) == INVALID; + } + } + + Node source(const Arc& arc) const { + return arc.forward ? Parent::red(arc) : Parent::blue(arc); + } + Node target(const Arc& arc) const { + return arc.forward ? Parent::blue(arc) : Parent::red(arc); + } + + int id(const Arc& arc) const { + return (Parent::id(static_cast(arc)) << 1) + + (arc.forward ? 0 : 1); + } + Arc arcFromId(int ix) const { + return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0); + } + int maxArcId() const { + return (Parent::maxEdgeId() << 1) + 1; + } + + bool direction(const Arc& arc) const { + return arc.forward; + } + + Arc direct(const Edge& arc, bool dir) const { + return Arc(arc, dir); + } + + int arcNum() const { + return 2 * Parent::edgeNum(); + } + + int edgeNum() const { + return Parent::edgeNum(); + } + + + }; +} + +#endif diff --git a/lemon/bits/default_map.h b/lemon/bits/default_map.h new file mode 100644 --- /dev/null +++ b/lemon/bits/default_map.h @@ -0,0 +1,181 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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_BITS_DEFAULT_MAP_H +#define LEMON_BITS_DEFAULT_MAP_H + + +#include +#include +//#include + +///\ingroup graphbits +///\file +///\brief Graph maps that construct and destruct their elements dynamically. + +namespace lemon { + + + //#ifndef LEMON_USE_DEBUG_MAP + + template + struct DefaultMapSelector { + typedef ArrayMap<_Graph, _Item, _Value> Map; + }; + + // bool + template + struct DefaultMapSelector<_Graph, _Item, bool> { + typedef VectorMap<_Graph, _Item, bool> Map; + }; + + // char + template + struct DefaultMapSelector<_Graph, _Item, char> { + typedef VectorMap<_Graph, _Item, char> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, signed char> { + typedef VectorMap<_Graph, _Item, signed char> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, unsigned char> { + typedef VectorMap<_Graph, _Item, unsigned char> Map; + }; + + + // int + template + struct DefaultMapSelector<_Graph, _Item, signed int> { + typedef VectorMap<_Graph, _Item, signed int> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, unsigned int> { + typedef VectorMap<_Graph, _Item, unsigned int> Map; + }; + + + // short + template + struct DefaultMapSelector<_Graph, _Item, signed short> { + typedef VectorMap<_Graph, _Item, signed short> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, unsigned short> { + typedef VectorMap<_Graph, _Item, unsigned short> Map; + }; + + + // long + template + struct DefaultMapSelector<_Graph, _Item, signed long> { + typedef VectorMap<_Graph, _Item, signed long> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, unsigned long> { + typedef VectorMap<_Graph, _Item, unsigned long> Map; + }; + + +#if defined __GNUC__ && !defined __STRICT_ANSI__ + + // long long + template + struct DefaultMapSelector<_Graph, _Item, signed long long> { + typedef VectorMap<_Graph, _Item, signed long long> Map; + }; + + template + struct DefaultMapSelector<_Graph, _Item, unsigned long long> { + typedef VectorMap<_Graph, _Item, unsigned long long> Map; + }; + +#endif + + + // float + template + struct DefaultMapSelector<_Graph, _Item, float> { + typedef VectorMap<_Graph, _Item, float> Map; + }; + + + // double + template + struct DefaultMapSelector<_Graph, _Item, double> { + typedef VectorMap<_Graph, _Item, double> Map; + }; + + + // long double + template + struct DefaultMapSelector<_Graph, _Item, long double> { + typedef VectorMap<_Graph, _Item, long double> Map; + }; + + + // pointer + template + struct DefaultMapSelector<_Graph, _Item, _Ptr*> { + typedef VectorMap<_Graph, _Item, _Ptr*> Map; + }; + +// #else + +// template +// struct DefaultMapSelector { +// typedef DebugMap<_Graph, _Item, _Value> Map; +// }; + +// #endif + + /// \e + template + class DefaultMap + : public DefaultMapSelector<_Graph, _Item, _Value>::Map { + public: + typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent; + typedef DefaultMap<_Graph, _Item, _Value> Map; + + typedef typename Parent::Graph Graph; + typedef typename Parent::Value Value; + + explicit DefaultMap(const Graph& graph) : Parent(graph) {} + DefaultMap(const Graph& graph, const Value& value) + : Parent(graph, value) {} + + DefaultMap& operator=(const DefaultMap& cmap) { + return operator=(cmap); + } + + template + DefaultMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + +} + +#endif diff --git a/lemon/bits/graph_extender.h b/lemon/bits/graph_extender.h new file mode 100644 --- /dev/null +++ b/lemon/bits/graph_extender.h @@ -0,0 +1,747 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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_BITS_GRAPH_EXTENDER_H +#define LEMON_BITS_GRAPH_EXTENDER_H + +#include + +#include +#include + +#include +#include + +///\ingroup graphbits +///\file +///\brief Extenders for the digraph types +namespace lemon { + + /// \ingroup graphbits + /// + /// \brief Extender for the Digraphs + template + class DigraphExtender : public Base { + public: + + typedef Base Parent; + typedef DigraphExtender Digraph; + + // Base extensions + + typedef typename Parent::Node Node; + typedef typename Parent::Arc Arc; + + int maxId(Node) const { + return Parent::maxNodeId(); + } + + int maxId(Arc) const { + return Parent::maxArcId(); + } + + Node fromId(int id, Node) const { + return Parent::nodeFromId(id); + } + + Arc fromId(int id, Arc) const { + return Parent::arcFromId(id); + } + + Node oppositeNode(const Node &n, const Arc &e) const { + if (n == Parent::source(e)) + return Parent::target(e); + else if(n==Parent::target(e)) + return Parent::source(e); + else + return INVALID; + } + + // Alterable extension + + typedef AlterationNotifier NodeNotifier; + typedef AlterationNotifier ArcNotifier; + + + protected: + + mutable NodeNotifier node_notifier; + mutable ArcNotifier arc_notifier; + + public: + + NodeNotifier& notifier(Node) const { + return node_notifier; + } + + ArcNotifier& notifier(Arc) const { + return arc_notifier; + } + + class NodeIt : public Node { + const Digraph* digraph; + public: + + NodeIt() {} + + NodeIt(Invalid i) : Node(i) { } + + explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) { + _digraph.first(static_cast(*this)); + } + + NodeIt(const Digraph& _digraph, const Node& node) + : Node(node), digraph(&_digraph) {} + + NodeIt& operator++() { + digraph->next(*this); + return *this; + } + + }; + + + class ArcIt : public Arc { + const Digraph* digraph; + public: + + ArcIt() { } + + ArcIt(Invalid i) : Arc(i) { } + + explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) { + _digraph.first(static_cast(*this)); + } + + ArcIt(const Digraph& _digraph, const Arc& e) : + Arc(e), digraph(&_digraph) { } + + ArcIt& operator++() { + digraph->next(*this); + return *this; + } + + }; + + + class OutArcIt : public Arc { + const Digraph* digraph; + public: + + OutArcIt() { } + + OutArcIt(Invalid i) : Arc(i) { } + + OutArcIt(const Digraph& _digraph, const Node& node) + : digraph(&_digraph) { + _digraph.firstOut(*this, node); + } + + OutArcIt(const Digraph& _digraph, const Arc& arc) + : Arc(arc), digraph(&_digraph) {} + + OutArcIt& operator++() { + digraph->nextOut(*this); + return *this; + } + + }; + + + class InArcIt : public Arc { + const Digraph* digraph; + public: + + InArcIt() { } + + InArcIt(Invalid i) : Arc(i) { } + + InArcIt(const Digraph& _digraph, const Node& node) + : digraph(&_digraph) { + _digraph.firstIn(*this, node); + } + + InArcIt(const Digraph& _digraph, const Arc& arc) : + Arc(arc), digraph(&_digraph) {} + + InArcIt& operator++() { + digraph->nextIn(*this); + return *this; + } + + }; + + /// \brief Base node of the iterator + /// + /// Returns the base node (i.e. the source in this case) of the iterator + Node baseNode(const OutArcIt &e) const { + return Parent::source(e); + } + /// \brief Running node of the iterator + /// + /// Returns the running node (i.e. the target in this case) of the + /// iterator + Node runningNode(const OutArcIt &e) const { + return Parent::target(e); + } + + /// \brief Base node of the iterator + /// + /// Returns the base node (i.e. the target in this case) of the iterator + Node baseNode(const InArcIt &e) const { + return Parent::target(e); + } + /// \brief Running node of the iterator + /// + /// Returns the running node (i.e. the source in this case) of the + /// iterator + Node runningNode(const InArcIt &e) const { + return Parent::source(e); + } + + + template + class NodeMap + : public MapExtender > { + public: + typedef DigraphExtender Digraph; + typedef MapExtender > Parent; + + explicit NodeMap(const Digraph& digraph) + : Parent(digraph) {} + NodeMap(const Digraph& digraph, const _Value& value) + : Parent(digraph, value) {} + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + template + class ArcMap + : public MapExtender > { + public: + typedef DigraphExtender Digraph; + typedef MapExtender > Parent; + + explicit ArcMap(const Digraph& digraph) + : Parent(digraph) {} + ArcMap(const Digraph& digraph, const _Value& value) + : Parent(digraph, value) {} + + ArcMap& operator=(const ArcMap& cmap) { + return operator=(cmap); + } + + template + ArcMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + + Node addNode() { + Node node = Parent::addNode(); + notifier(Node()).add(node); + return node; + } + + Arc addArc(const Node& from, const Node& to) { + Arc arc = Parent::addArc(from, to); + notifier(Arc()).add(arc); + return arc; + } + + void clear() { + notifier(Arc()).clear(); + notifier(Node()).clear(); + Parent::clear(); + } + + template + void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) { + Parent::build(digraph, nodeRef, arcRef); + notifier(Node()).build(); + notifier(Arc()).build(); + } + + void erase(const Node& node) { + Arc arc; + Parent::firstOut(arc, node); + while (arc != INVALID ) { + erase(arc); + Parent::firstOut(arc, node); + } + + Parent::firstIn(arc, node); + while (arc != INVALID ) { + erase(arc); + Parent::firstIn(arc, node); + } + + notifier(Node()).erase(node); + Parent::erase(node); + } + + void erase(const Arc& arc) { + notifier(Arc()).erase(arc); + Parent::erase(arc); + } + + DigraphExtender() { + node_notifier.setContainer(*this); + arc_notifier.setContainer(*this); + } + + + ~DigraphExtender() { + arc_notifier.clear(); + node_notifier.clear(); + } + }; + + /// \ingroup graphbits + /// + /// \brief Extender for the Graphs + template + class GraphExtender : public Base { + public: + + typedef Base Parent; + typedef GraphExtender Digraph; + + typedef typename Parent::Node Node; + typedef typename Parent::Arc Arc; + typedef typename Parent::Edge Edge; + + // Graph extension + + int maxId(Node) const { + return Parent::maxNodeId(); + } + + int maxId(Arc) const { + return Parent::maxArcId(); + } + + int maxId(Edge) const { + return Parent::maxEdgeId(); + } + + Node fromId(int id, Node) const { + return Parent::nodeFromId(id); + } + + Arc fromId(int id, Arc) const { + return Parent::arcFromId(id); + } + + Edge fromId(int id, Edge) const { + return Parent::edgeFromId(id); + } + + Node oppositeNode(const Node &n, const Edge &e) const { + if( n == Parent::source(e)) + return Parent::target(e); + else if( n == Parent::target(e)) + return Parent::source(e); + else + return INVALID; + } + + Arc oppositeArc(const Arc &e) const { + return Parent::direct(e, !Parent::direction(e)); + } + + using Parent::direct; + Arc direct(const Edge &ue, const Node &s) const { + return Parent::direct(ue, Parent::source(ue) == s); + } + + // Alterable extension + + typedef AlterationNotifier NodeNotifier; + typedef AlterationNotifier ArcNotifier; + typedef AlterationNotifier EdgeNotifier; + + + protected: + + mutable NodeNotifier node_notifier; + mutable ArcNotifier arc_notifier; + mutable EdgeNotifier edge_notifier; + + public: + + NodeNotifier& notifier(Node) const { + return node_notifier; + } + + ArcNotifier& notifier(Arc) const { + return arc_notifier; + } + + EdgeNotifier& notifier(Edge) const { + return edge_notifier; + } + + + + class NodeIt : public Node { + const Digraph* digraph; + public: + + NodeIt() {} + + NodeIt(Invalid i) : Node(i) { } + + explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) { + _digraph.first(static_cast(*this)); + } + + NodeIt(const Digraph& _digraph, const Node& node) + : Node(node), digraph(&_digraph) {} + + NodeIt& operator++() { + digraph->next(*this); + return *this; + } + + }; + + + class ArcIt : public Arc { + const Digraph* digraph; + public: + + ArcIt() { } + + ArcIt(Invalid i) : Arc(i) { } + + explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) { + _digraph.first(static_cast(*this)); + } + + ArcIt(const Digraph& _digraph, const Arc& e) : + Arc(e), digraph(&_digraph) { } + + ArcIt& operator++() { + digraph->next(*this); + return *this; + } + + }; + + + class OutArcIt : public Arc { + const Digraph* digraph; + public: + + OutArcIt() { } + + OutArcIt(Invalid i) : Arc(i) { } + + OutArcIt(const Digraph& _digraph, const Node& node) + : digraph(&_digraph) { + _digraph.firstOut(*this, node); + } + + OutArcIt(const Digraph& _digraph, const Arc& arc) + : Arc(arc), digraph(&_digraph) {} + + OutArcIt& operator++() { + digraph->nextOut(*this); + return *this; + } + + }; + + + class InArcIt : public Arc { + const Digraph* digraph; + public: + + InArcIt() { } + + InArcIt(Invalid i) : Arc(i) { } + + InArcIt(const Digraph& _digraph, const Node& node) + : digraph(&_digraph) { + _digraph.firstIn(*this, node); + } + + InArcIt(const Digraph& _digraph, const Arc& arc) : + Arc(arc), digraph(&_digraph) {} + + InArcIt& operator++() { + digraph->nextIn(*this); + return *this; + } + + }; + + + class EdgeIt : public Parent::Edge { + const Digraph* digraph; + public: + + EdgeIt() { } + + EdgeIt(Invalid i) : Edge(i) { } + + explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) { + _digraph.first(static_cast(*this)); + } + + EdgeIt(const Digraph& _digraph, const Edge& e) : + Edge(e), digraph(&_digraph) { } + + EdgeIt& operator++() { + digraph->next(*this); + return *this; + } + + }; + + class IncArcIt : public Parent::Edge { + friend class GraphExtender; + const Digraph* digraph; + bool direction; + public: + + IncArcIt() { } + + IncArcIt(Invalid i) : Edge(i), direction(false) { } + + IncArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) { + _digraph.firstInc(*this, direction, n); + } + + IncArcIt(const Digraph& _digraph, const Edge &ue, const Node &n) + : digraph(&_digraph), Edge(ue) { + direction = (_digraph.source(ue) == n); + } + + IncArcIt& operator++() { + digraph->nextInc(*this, direction); + return *this; + } + }; + + /// \brief Base node of the iterator + /// + /// Returns the base node (ie. the source in this case) of the iterator + Node baseNode(const OutArcIt &e) const { + return Parent::source(static_cast(e)); + } + /// \brief Running node of the iterator + /// + /// Returns the running node (ie. the target in this case) of the + /// iterator + Node runningNode(const OutArcIt &e) const { + return Parent::target(static_cast(e)); + } + + /// \brief Base node of the iterator + /// + /// Returns the base node (ie. the target in this case) of the iterator + Node baseNode(const InArcIt &e) const { + return Parent::target(static_cast(e)); + } + /// \brief Running node of the iterator + /// + /// Returns the running node (ie. the source in this case) of the + /// iterator + Node runningNode(const InArcIt &e) const { + return Parent::source(static_cast(e)); + } + + /// Base node of the iterator + /// + /// Returns the base node of the iterator + Node baseNode(const IncArcIt &e) const { + return e.direction ? source(e) : target(e); + } + /// Running node of the iterator + /// + /// Returns the running node of the iterator + Node runningNode(const IncArcIt &e) const { + return e.direction ? target(e) : source(e); + } + + // Mappable extension + + template + class NodeMap + : public MapExtender > { + public: + typedef GraphExtender Digraph; + typedef MapExtender > Parent; + + NodeMap(const Digraph& digraph) + : Parent(digraph) {} + NodeMap(const Digraph& digraph, const _Value& value) + : Parent(digraph, value) {} + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + template + class ArcMap + : public MapExtender > { + public: + typedef GraphExtender Digraph; + typedef MapExtender > Parent; + + ArcMap(const Digraph& digraph) + : Parent(digraph) {} + ArcMap(const Digraph& digraph, const _Value& value) + : Parent(digraph, value) {} + + ArcMap& operator=(const ArcMap& cmap) { + return operator=(cmap); + } + + template + ArcMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + + template + class EdgeMap + : public MapExtender > { + public: + typedef GraphExtender Digraph; + typedef MapExtender > Parent; + + EdgeMap(const Digraph& digraph) + : Parent(digraph) {} + + EdgeMap(const Digraph& digraph, const _Value& value) + : Parent(digraph, value) {} + + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=(cmap); + } + + template + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + // Alteration extension + + Node addNode() { + Node node = Parent::addNode(); + notifier(Node()).add(node); + return node; + } + + Edge addEdge(const Node& from, const Node& to) { + Edge edge = Parent::addEdge(from, to); + notifier(Edge()).add(edge); + std::vector ev; + ev.push_back(Parent::direct(edge, true)); + ev.push_back(Parent::direct(edge, false)); + notifier(Arc()).add(ev); + return edge; + } + + void clear() { + notifier(Arc()).clear(); + notifier(Edge()).clear(); + notifier(Node()).clear(); + Parent::clear(); + } + + template + void build(const Digraph& digraph, NodeRefMap& nodeRef, + EdgeRefMap& edgeRef) { + Parent::build(digraph, nodeRef, edgeRef); + notifier(Node()).build(); + notifier(Edge()).build(); + notifier(Arc()).build(); + } + + void erase(const Node& node) { + Arc arc; + Parent::firstOut(arc, node); + while (arc != INVALID ) { + erase(arc); + Parent::firstOut(arc, node); + } + + Parent::firstIn(arc, node); + while (arc != INVALID ) { + erase(arc); + Parent::firstIn(arc, node); + } + + notifier(Node()).erase(node); + Parent::erase(node); + } + + void erase(const Edge& edge) { + std::vector ev; + ev.push_back(Parent::direct(edge, true)); + ev.push_back(Parent::direct(edge, false)); + notifier(Arc()).erase(ev); + notifier(Edge()).erase(edge); + Parent::erase(edge); + } + + GraphExtender() { + node_notifier.setContainer(*this); + arc_notifier.setContainer(*this); + edge_notifier.setContainer(*this); + } + + ~GraphExtender() { + edge_notifier.clear(); + arc_notifier.clear(); + node_notifier.clear(); + } + + }; + +} + +#endif diff --git a/lemon/bits/map_extender.h b/lemon/bits/map_extender.h new file mode 100644 --- /dev/null +++ b/lemon/bits/map_extender.h @@ -0,0 +1,321 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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_BITS_MAP_EXTENDER_H +#define LEMON_BITS_MAP_EXTENDER_H + +#include + +#include + +#include +#include + +///\file +///\brief Extenders for iterable maps. + +namespace lemon { + + /// \ingroup graphbits + /// + /// \brief Extender for maps + template + class MapExtender : public _Map { + public: + + typedef _Map Parent; + typedef MapExtender Map; + + + typedef typename Parent::Graph Graph; + typedef typename Parent::Key Item; + + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + + class MapIt; + class ConstMapIt; + + friend class MapIt; + friend class ConstMapIt; + + public: + + MapExtender(const Graph& graph) + : Parent(graph) {} + + MapExtender(const Graph& graph, const Value& value) + : Parent(graph, value) {} + + MapExtender& operator=(const MapExtender& cmap) { + return operator=(cmap); + } + + template + MapExtender& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + class MapIt : public Item { + public: + + typedef Item Parent; + typedef typename Map::Value Value; + + MapIt() {} + + MapIt(Invalid i) : Parent(i) { } + + explicit MapIt(Map& _map) : map(_map) { + map.notifier()->first(*this); + } + + MapIt(const Map& _map, const Item& item) + : Parent(item), map(_map) {} + + MapIt& operator++() { + map.notifier()->next(*this); + return *this; + } + + typename MapTraits::ConstReturnValue operator*() const { + return map[*this]; + } + + typename MapTraits::ReturnValue operator*() { + return map[*this]; + } + + void set(const Value& value) { + map.set(*this, value); + } + + protected: + Map& map; + + }; + + class ConstMapIt : public Item { + public: + + typedef Item Parent; + + typedef typename Map::Value Value; + + ConstMapIt() {} + + ConstMapIt(Invalid i) : Parent(i) { } + + explicit ConstMapIt(Map& _map) : map(_map) { + map.notifier()->first(*this); + } + + ConstMapIt(const Map& _map, const Item& item) + : Parent(item), map(_map) {} + + ConstMapIt& operator++() { + map.notifier()->next(*this); + return *this; + } + + typename MapTraits::ConstReturnValue operator*() const { + return map[*this]; + } + + protected: + const Map& map; + }; + + class ItemIt : public Item { + public: + + typedef Item Parent; + + ItemIt() {} + + ItemIt(Invalid i) : Parent(i) { } + + explicit ItemIt(Map& _map) : map(_map) { + map.notifier()->first(*this); + } + + ItemIt(const Map& _map, const Item& item) + : Parent(item), map(_map) {} + + ItemIt& operator++() { + map.notifier()->next(*this); + return *this; + } + + protected: + const Map& map; + + }; + }; + + /// \ingroup graphbits + /// + /// \brief Extender for maps which use a subset of the items. + template + class SubMapExtender : public _Map { + public: + + typedef _Map Parent; + typedef SubMapExtender Map; + + typedef _Graph Graph; + + typedef typename Parent::Key Item; + + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + + class MapIt; + class ConstMapIt; + + friend class MapIt; + friend class ConstMapIt; + + public: + + SubMapExtender(const Graph& _graph) + : Parent(_graph), graph(_graph) {} + + SubMapExtender(const Graph& _graph, const Value& _value) + : Parent(_graph, _value), graph(_graph) {} + + SubMapExtender& operator=(const SubMapExtender& cmap) { + return operator=(cmap); + } + + template + SubMapExtender& operator=(const CMap& cmap) { + checkConcept, CMap>(); + Item it; + for (graph.first(it); it != INVALID; graph.next(it)) { + Parent::set(it, cmap[it]); + } + return *this; + } + + class MapIt : public Item { + public: + + typedef Item Parent; + typedef typename Map::Value Value; + + MapIt() {} + + MapIt(Invalid i) : Parent(i) { } + + explicit MapIt(Map& _map) : map(_map) { + map.graph.first(*this); + } + + MapIt(const Map& _map, const Item& item) + : Parent(item), map(_map) {} + + MapIt& operator++() { + map.graph.next(*this); + return *this; + } + + typename MapTraits::ConstReturnValue operator*() const { + return map[*this]; + } + + typename MapTraits::ReturnValue operator*() { + return map[*this]; + } + + void set(const Value& value) { + map.set(*this, value); + } + + protected: + Map& map; + + }; + + class ConstMapIt : public Item { + public: + + typedef Item Parent; + + typedef typename Map::Value Value; + + ConstMapIt() {} + + ConstMapIt(Invalid i) : Parent(i) { } + + explicit ConstMapIt(Map& _map) : map(_map) { + map.graph.first(*this); + } + + ConstMapIt(const Map& _map, const Item& item) + : Parent(item), map(_map) {} + + ConstMapIt& operator++() { + map.graph.next(*this); + return *this; + } + + typename MapTraits::ConstReturnValue operator*() const { + return map[*this]; + } + + protected: + const Map& map; + }; + + class ItemIt : public Item { + public: + + typedef Item Parent; + + ItemIt() {} + + ItemIt(Invalid i) : Parent(i) { } + + explicit ItemIt(Map& _map) : map(_map) { + map.graph.first(*this); + } + + ItemIt(const Map& _map, const Item& item) + : Parent(item), map(_map) {} + + ItemIt& operator++() { + map.graph.next(*this); + return *this; + } + + protected: + const Map& map; + + }; + + private: + + const Graph& graph; + + }; + +} + +#endif diff --git a/lemon/bits/traits.h b/lemon/bits/traits.h new file mode 100644 --- /dev/null +++ b/lemon/bits/traits.h @@ -0,0 +1,272 @@ + +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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_BITS_TRAITS_H +#define LEMON_BITS_TRAITS_H + +#include + +///\file +///\brief Traits for graphs and maps +/// + +namespace lemon { + template + class ItemSetTraits {}; + + + template + struct NodeNotifierIndicator { + typedef InvalidType Type; + }; + template + struct NodeNotifierIndicator< + Graph, + typename enable_if::type + > { + typedef typename Graph::NodeNotifier Type; + }; + + template + class ItemSetTraits<_Graph, typename _Graph::Node> { + public: + + typedef _Graph Graph; + + typedef typename Graph::Node Item; + typedef typename Graph::NodeIt ItemIt; + + typedef typename NodeNotifierIndicator::Type ItemNotifier; + + template + class Map : public Graph::template NodeMap<_Value> { + public: + typedef typename Graph::template NodeMap<_Value> Parent; + typedef typename Graph::template NodeMap<_Value> Type; + typedef typename Parent::Value Value; + + Map(const Graph& _digraph) : Parent(_digraph) {} + Map(const Graph& _digraph, const Value& _value) + : Parent(_digraph, _value) {} + + }; + + }; + + template + struct ArcNotifierIndicator { + typedef InvalidType Type; + }; + template + struct ArcNotifierIndicator< + Graph, + typename enable_if::type + > { + typedef typename Graph::ArcNotifier Type; + }; + + template + class ItemSetTraits<_Graph, typename _Graph::Arc> { + public: + + typedef _Graph Graph; + + typedef typename Graph::Arc Item; + typedef typename Graph::ArcIt ItemIt; + + typedef typename ArcNotifierIndicator::Type ItemNotifier; + + template + class Map : public Graph::template ArcMap<_Value> { + public: + typedef typename Graph::template ArcMap<_Value> Parent; + typedef typename Graph::template ArcMap<_Value> Type; + typedef typename Parent::Value Value; + + Map(const Graph& _digraph) : Parent(_digraph) {} + Map(const Graph& _digraph, const Value& _value) + : Parent(_digraph, _value) {} + }; + + }; + + template + struct EdgeNotifierIndicator { + typedef InvalidType Type; + }; + template + struct EdgeNotifierIndicator< + Graph, + typename enable_if::type + > { + typedef typename Graph::EdgeNotifier Type; + }; + + template + class ItemSetTraits<_Graph, typename _Graph::Edge> { + public: + + typedef _Graph Graph; + + typedef typename Graph::Edge Item; + typedef typename Graph::EdgeIt ItemIt; + + typedef typename EdgeNotifierIndicator::Type ItemNotifier; + + template + class Map : public Graph::template EdgeMap<_Value> { + public: + typedef typename Graph::template EdgeMap<_Value> Parent; + typedef typename Graph::template EdgeMap<_Value> Type; + typedef typename Parent::Value Value; + + Map(const Graph& _digraph) : Parent(_digraph) {} + Map(const Graph& _digraph, const Value& _value) + : Parent(_digraph, _value) {} + }; + + }; + + template + struct MapTraits { + typedef False ReferenceMapTag; + + typedef typename Map::Key Key; + typedef typename Map::Value Value; + + typedef const Value ConstReturnValue; + typedef const Value ReturnValue; + }; + + template + struct MapTraits< + Map, typename enable_if::type > + { + typedef True ReferenceMapTag; + + typedef typename Map::Key Key; + typedef typename Map::Value Value; + + typedef typename Map::ConstReference ConstReturnValue; + typedef typename Map::Reference ReturnValue; + + typedef typename Map::ConstReference ConstReference; + typedef typename Map::Reference Reference; + }; + + template + struct MatrixMapTraits { + typedef False ReferenceMapTag; + + typedef typename MatrixMap::FirstKey FirstKey; + typedef typename MatrixMap::SecondKey SecondKey; + typedef typename MatrixMap::Value Value; + + typedef const Value ConstReturnValue; + typedef const Value ReturnValue; + }; + + template + struct MatrixMapTraits< + MatrixMap, typename enable_if::type > + { + typedef True ReferenceMapTag; + + typedef typename MatrixMap::FirstKey FirstKey; + typedef typename MatrixMap::SecondKey SecondKey; + typedef typename MatrixMap::Value Value; + + typedef typename MatrixMap::ConstReference ConstReturnValue; + typedef typename MatrixMap::Reference ReturnValue; + + typedef typename MatrixMap::ConstReference ConstReference; + typedef typename MatrixMap::Reference Reference; + }; + + // Indicators for the tags + + template + struct NodeNumTagIndicator { + static const bool value = false; + }; + + template + struct NodeNumTagIndicator< + Graph, + typename enable_if::type + > { + static const bool value = true; + }; + + template + struct ArcNumTagIndicator { + static const bool value = false; + }; + + template + struct ArcNumTagIndicator< + Graph, + typename enable_if::type + > { + static const bool value = true; + }; + + template + struct FindArcTagIndicator { + static const bool value = false; + }; + + template + struct FindArcTagIndicator< + Graph, + typename enable_if::type + > { + static const bool value = true; + }; + + template + struct UndirectedTagIndicator { + static const bool value = false; + }; + + template + struct UndirectedTagIndicator< + Graph, + typename enable_if::type + > { + static const bool value = true; + }; + + template + struct BuildTagIndicator { + static const bool value = false; + }; + + template + struct BuildTagIndicator< + Graph, + typename enable_if::type + > { + static const bool value = true; + }; + +} + +#endif diff --git a/lemon/bits/vector_map.h b/lemon/bits/vector_map.h new file mode 100644 --- /dev/null +++ b/lemon/bits/vector_map.h @@ -0,0 +1,243 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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_BITS_VECTOR_MAP_H +#define LEMON_BITS_VECTOR_MAP_H + +#include +#include + +#include +#include + +#include + +#include +#include + +///\ingroup graphbits +/// +///\file +///\brief Vector based graph maps. +namespace lemon { + + /// \ingroup graphbits + /// + /// \brief Graph map based on the std::vector storage. + /// + /// 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 type uses the std::vector to store the values. + /// + /// \param Notifier The AlterationNotifier that will notify this map. + /// \param Item The item type of the graph items. + /// \param Value The value type of the map. + /// + /// \author Balazs Dezso + template + class VectorMap + : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { + private: + + /// The container type of the map. + typedef std::vector<_Value> Container; + + public: + + /// The graph type of the map. + typedef _Graph Graph; + /// The item type of the map. + typedef _Item Item; + /// The reference map tag. + typedef True ReferenceMapTag; + + /// The key type of the map. + typedef _Item Key; + /// The value type of the map. + typedef _Value Value; + + /// The notifier type. + typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; + + /// The map type. + typedef VectorMap Map; + /// The base class of the map. + typedef typename Notifier::ObserverBase Parent; + + /// The reference type of the map; + typedef typename Container::reference Reference; + /// The const reference type of the map; + typedef typename Container::const_reference ConstReference; + + + /// \brief Constructor to attach the new map into the notifier. + /// + /// It constructs a map and attachs it into the notifier. + /// It adds all the items of the graph to the map. + VectorMap(const Graph& graph) { + Parent::attach(graph.notifier(Item())); + container.resize(Parent::notifier()->maxId() + 1); + } + + /// \brief Constructor uses given value to initialize the map. + /// + /// It constructs a map uses a given value to initialize the map. + /// It adds all the items of the graph to the map. + VectorMap(const Graph& graph, const Value& value) { + Parent::attach(graph.notifier(Item())); + container.resize(Parent::notifier()->maxId() + 1, value); + } + + /// \brief Copy constructor + /// + /// Copy constructor. + VectorMap(const VectorMap& _copy) : Parent() { + if (_copy.attached()) { + Parent::attach(*_copy.notifier()); + container = _copy.container; + } + } + + /// \brief Assign operator. + /// + /// This operator assigns for each item in the map the + /// value mapped to the same item in the copied map. + /// The parameter map should be indiced with the same + /// itemset because this assign operator does not change + /// the container of the map. + VectorMap& operator=(const VectorMap& cmap) { + return operator=(cmap); + } + + + /// \brief Template assign operator. + /// + /// The given parameter should be conform to the ReadMap + /// concecpt and could be indiced by the current item set of + /// the NodeMap. In this case the value for each item + /// is assigned by the value of the given ReadMap. + template + VectorMap& operator=(const CMap& cmap) { + checkConcept, CMap>(); + const typename Parent::Notifier* nf = Parent::notifier(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + set(it, cmap[it]); + } + return *this; + } + + public: + + /// \brief The subcript operator. + /// + /// The subscript operator. The map can be subscripted by the + /// actual items of the graph. + Reference operator[](const Key& key) { + return container[Parent::notifier()->id(key)]; + } + + /// \brief The const subcript operator. + /// + /// The const subscript operator. The map can be subscripted by the + /// actual items of the graph. + ConstReference operator[](const Key& key) const { + return container[Parent::notifier()->id(key)]; + } + + + /// \brief The setter function of the map. + /// + /// It the same as operator[](key) = value expression. + void set(const Key& key, const Value& value) { + (*this)[key] = value; + } + + protected: + + /// \brief Adds a new key to the map. + /// + /// It adds a new key to the map. It called by the observer notifier + /// and it overrides the add() member function of the observer base. + virtual void add(const Key& key) { + int id = Parent::notifier()->id(key); + if (id >= int(container.size())) { + container.resize(id + 1); + } + } + + /// \brief Adds more new keys to the map. + /// + /// It adds more new keys to the map. It called by the observer notifier + /// and it overrides the add() member function of the observer base. + virtual void add(const std::vector& keys) { + int max = container.size() - 1; + for (int i = 0; i < int(keys.size()); ++i) { + int id = Parent::notifier()->id(keys[i]); + if (id >= max) { + max = id; + } + } + container.resize(max + 1); + } + + /// \brief Erase a key from the map. + /// + /// Erase a key from the map. It called by the observer notifier + /// and it overrides the erase() member function of the observer base. + virtual void erase(const Key& key) { + container[Parent::notifier()->id(key)] = Value(); + } + + /// \brief Erase more keys from the map. + /// + /// Erase more keys from the map. It called by the observer notifier + /// and it overrides the erase() member function of the observer base. + virtual void erase(const std::vector& keys) { + for (int i = 0; i < int(keys.size()); ++i) { + container[Parent::notifier()->id(keys[i])] = Value(); + } + } + + /// \brief Buildes the map. + /// + /// It buildes the map. It called by the observer notifier + /// and it overrides the build() member function of the observer base. + virtual void build() { + int size = Parent::notifier()->maxId() + 1; + container.reserve(size); + container.resize(size); + } + + /// \brief Clear the map. + /// + /// It erase all items from the map. It called by the observer notifier + /// and it overrides the clear() member function of the observer base. + virtual void clear() { + container.clear(); + } + + private: + + Container container; + + }; + +} + +#endif diff --git a/lemon/concepts/digraph.h b/lemon/concepts/digraph.h new file mode 100644 --- /dev/null +++ b/lemon/concepts/digraph.h @@ -0,0 +1,453 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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_CONCEPT_DIGRAPH_H +#define LEMON_CONCEPT_DIGRAPH_H + +///\ingroup graph_concepts +///\file +///\brief The concept of directed graphs. + +#include +#include +#include +#include +#include + +namespace lemon { + namespace concepts { + + /// \ingroup graph_concepts + /// + /// \brief Class describing the concept of directed graphs. + /// + /// This class describes the \ref concept "concept" of the + /// immutable directed digraphs. + /// + /// Note that actual digraph implementation like @ref ListDigraph or + /// @ref SmartDigraph may have several additional functionality. + /// + /// \sa concept + class Digraph { + private: + ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. + + ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. + /// + Digraph(const Digraph &) {}; + ///\brief Assignment of \ref Digraph "Digraph"s to another ones are + ///\e not allowed. Use DigraphCopy() instead. + + ///Assignment of \ref Digraph "Digraph"s to another ones are + ///\e not allowed. Use DigraphCopy() instead. + + void operator=(const Digraph &) {} + public: + ///\e + + /// Defalult constructor. + + /// Defalult constructor. + /// + Digraph() { } + /// Class for identifying a node of the digraph + + /// This class identifies a node of the digraph. It also serves + /// as a base class of the node iterators, + /// thus they will convert to this type. + 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; } + + /// Artificial ordering operator. + + /// To allow the use of digraph descriptors as key type in std::map or + /// similar associative container we require this. + /// + /// \note This operator only have to define some strict ordering of + /// the items; this order has nothing to do with the iteration + /// ordering of the items. + bool operator<(Node) const { return false; } + + }; + + /// 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 digraph \c g of type \c Digraph like this: + ///\code + /// int count=0; + /// for (Digraph::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& n) : Node(n) { } + /// 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 Digraph&) { } + /// Node -> NodeIt conversion. + + /// Sets the iterator to the node of \c the digraph pointed by + /// the trivial iterator. + /// This feature necessitates that each time we + /// iterate the arc-set, the iteration order is the same. + NodeIt(const Digraph&, const Node&) { } + /// Next node. + + /// Assign the iterator to the next node. + /// + NodeIt& operator++() { return *this; } + }; + + + /// Class for identifying an arc of the digraph + + /// This class identifies an arc of the digraph. It also serves + /// as a base class of the arc iterators, + /// thus they will convert to this type. + class Arc { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + Arc() { } + /// Copy constructor. + + /// Copy constructor. + /// + Arc(const Arc&) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + Arc(Invalid) { } + /// Equality operator + + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. + bool operator==(Arc) const { return true; } + /// Inequality operator + + /// \sa operator==(Arc n) + /// + bool operator!=(Arc) const { return true; } + + /// Artificial ordering operator. + + /// To allow the use of digraph descriptors as key type in std::map or + /// similar associative container we require this. + /// + /// \note This operator only have to define some strict ordering of + /// the items; this order has nothing to do with the iteration + /// ordering of the items. + bool operator<(Arc) const { return false; } + }; + + /// This iterator goes trough the outgoing arcs of a node. + + /// This iterator goes trough the \e outgoing arcs of a certain node + /// of a digraph. + /// Its usage is quite simple, for example you can count the number + /// of outgoing arcs of a node \c n + /// in digraph \c g of type \c Digraph as follows. + ///\code + /// int count=0; + /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; + ///\endcode + + class OutArcIt : public Arc { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + OutArcIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + OutArcIt(const OutArcIt& e) : Arc(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + OutArcIt(Invalid) { } + /// This constructor sets the iterator to the first outgoing arc. + + /// This constructor sets the iterator to the first outgoing arc of + /// the node. + OutArcIt(const Digraph&, const Node&) { } + /// Arc -> OutArcIt conversion + + /// Sets the iterator to the value of the trivial iterator. + /// This feature necessitates that each time we + /// iterate the arc-set, the iteration order is the same. + OutArcIt(const Digraph&, const Arc&) { } + ///Next outgoing arc + + /// Assign the iterator to the next + /// outgoing arc of the corresponding node. + OutArcIt& operator++() { return *this; } + }; + + /// This iterator goes trough the incoming arcs of a node. + + /// This iterator goes trough the \e incoming arcs of a certain node + /// of a digraph. + /// Its usage is quite simple, for example you can count the number + /// of outgoing arcs of a node \c n + /// in digraph \c g of type \c Digraph as follows. + ///\code + /// int count=0; + /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count; + ///\endcode + + class InArcIt : public Arc { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + InArcIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + InArcIt(const InArcIt& e) : Arc(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + InArcIt(Invalid) { } + /// This constructor sets the iterator to first incoming arc. + + /// This constructor set the iterator to the first incoming arc of + /// the node. + InArcIt(const Digraph&, const Node&) { } + /// Arc -> InArcIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the arc-set, the iteration order is the same. + InArcIt(const Digraph&, const Arc&) { } + /// Next incoming arc + + /// Assign the iterator to the next inarc of the corresponding node. + /// + InArcIt& operator++() { return *this; } + }; + /// This iterator goes through each arc. + + /// This iterator goes through each arc of a digraph. + /// Its usage is quite simple, for example you can count the number + /// of arcs in a digraph \c g of type \c Digraph as follows: + ///\code + /// int count=0; + /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count; + ///\endcode + class ArcIt : public Arc { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + ArcIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + ArcIt(const ArcIt& e) : Arc(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + ArcIt(Invalid) { } + /// This constructor sets the iterator to the first arc. + + /// This constructor sets the iterator to the first arc of \c g. + ///@param g the digraph + ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } + /// Arc -> ArcIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the arc-set, the iteration order is the same. + ArcIt(const Digraph&, const Arc&) { } + ///Next arc + + /// Assign the iterator to the next arc. + ArcIt& operator++() { return *this; } + }; + ///Gives back the target node of an arc. + + ///Gives back the target node of an arc. + /// + Node target(Arc) const { return INVALID; } + ///Gives back the source node of an arc. + + ///Gives back the source node of an arc. + /// + Node source(Arc) const { return INVALID; } + + void first(Node&) const {} + void next(Node&) const {} + + void first(Arc&) const {} + void next(Arc&) const {} + + + void firstIn(Arc&, const Node&) const {} + void nextIn(Arc&) const {} + + void firstOut(Arc&, const Node&) const {} + void nextOut(Arc&) const {} + + /// \brief The base node of the iterator. + /// + /// Gives back the base node of the iterator. + /// It is always the target of the pointed arc. + Node baseNode(const InArcIt&) const { return INVALID; } + + /// \brief The running node of the iterator. + /// + /// Gives back the running node of the iterator. + /// It is always the source of the pointed arc. + Node runningNode(const InArcIt&) const { return INVALID; } + + /// \brief The base node of the iterator. + /// + /// Gives back the base node of the iterator. + /// It is always the source of the pointed arc. + Node baseNode(const OutArcIt&) const { return INVALID; } + + /// \brief The running node of the iterator. + /// + /// Gives back the running node of the iterator. + /// It is always the target of the pointed arc. + Node runningNode(const OutArcIt&) const { return INVALID; } + + /// \brief The opposite node on the given arc. + /// + /// Gives back the opposite node on the given arc. + Node oppositeNode(const Node&, const Arc&) const { return INVALID; } + + /// \brief Read write map of the nodes to type \c T. + /// + /// ReadWrite map of the nodes to type \c T. + /// \sa Reference + template + class NodeMap : public ReadWriteMap< Node, T > { + public: + + ///\e + NodeMap(const Digraph&) { } + ///\e + NodeMap(const Digraph&, T) { } + + ///Copy constructor + NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } + ///Assignment operator + template + NodeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + }; + + /// \brief Read write map of the arcs to type \c T. + /// + /// Reference map of the arcs to type \c T. + /// \sa Reference + template + class ArcMap : public ReadWriteMap { + public: + + ///\e + ArcMap(const Digraph&) { } + ///\e + ArcMap(const Digraph&, T) { } + ///Copy constructor + ArcMap(const ArcMap& em) : ReadWriteMap(em) { } + ///Assignment operator + template + ArcMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + }; + + template + struct Constraints { + void constraints() { + checkConcept, Digraph>(); + checkConcept, Digraph>(); + } + }; + + }; + + } //namespace concepts +} //namespace lemon + + + +#endif // LEMON_CONCEPT_DIGRAPH_H diff --git a/lemon/concepts/graph.h b/lemon/concepts/graph.h new file mode 100644 --- /dev/null +++ b/lemon/concepts/graph.h @@ -0,0 +1,702 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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 graph_concepts +///\file +///\brief The concept of Undirected Graphs. + +#ifndef LEMON_CONCEPT_GRAPH_H +#define LEMON_CONCEPT_GRAPH_H + +#include +#include +#include + +namespace lemon { + namespace concepts { + + /// \ingroup graph_concepts + /// + /// \brief Class describing the concept of Undirected Graphs. + /// + /// This class describes the common interface of all Undirected + /// Graphs. + /// + /// As all concept describing classes it provides only interface + /// without any sensible implementation. So any algorithm for + /// undirected graph should compile with this class, but it will not + /// run properly, of course. + /// + /// The LEMON undirected graphs also fulfill the concept of + /// directed graphs (\ref lemon::concepts::Digraph "Digraph + /// Concept"). Each edges can be seen as two opposite + /// directed arc and consequently the undirected graph can be + /// seen as the direceted graph of these directed arcs. The + /// Graph has the Edge inner class for the edges and + /// the Arc type for the directed arcs. The Arc type is + /// convertible to Edge or inherited from it so from a directed + /// arc we can get the represented edge. + /// + /// In the sense of the LEMON each edge has a default + /// direction (it should be in every computer implementation, + /// because the order of edge's nodes defines an + /// orientation). With the default orientation we can define that + /// the directed arc is forward or backward directed. With the \c + /// direction() and \c direct() function we can get the direction + /// of the directed arc and we can direct an edge. + /// + /// The EdgeIt is an iterator for the edges. We can use + /// the EdgeMap to map values for the edges. The InArcIt and + /// OutArcIt iterates on the same edges but with opposite + /// direction. The IncArcIt iterates also on the same edges + /// as the OutArcIt and InArcIt but it is not convertible to Arc just + /// to Edge. + class Graph { + public: + /// \brief The undirected graph should be tagged by the + /// UndirectedTag. + /// + /// The undirected graph should be tagged by the UndirectedTag. This + /// tag helps the enable_if technics to make compile time + /// specializations for undirected graphs. + typedef True UndirectedTag; + + /// \brief 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; } + + /// Artificial ordering operator. + + /// To allow the use of graph descriptors as key type in std::map or + /// similar associative container we require this. + /// + /// \note This operator only have to define some strict ordering of + /// the items; this order has nothing to do with the iteration + /// ordering of the items. + bool operator<(Node) const { return false; } + + }; + + /// 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& n) : Node(n) { } + /// 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 Graph&) { } + /// Node -> NodeIt conversion. + + /// Sets the iterator to the node of \c the graph pointed by + /// the trivial iterator. + /// This feature necessitates that each time we + /// iterate the arc-set, the iteration order is the same. + NodeIt(const Graph&, const Node&) { } + /// 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==(Edge n) + /// + bool operator!=(Edge) const { return true; } + + /// Artificial ordering operator. + + /// To allow the use of graph descriptors as key type in std::map or + /// similar associative container we require this. + /// + /// \note This operator only have to define some strict ordering of + /// the items; this order has nothing to do with the iteration + /// ordering of the items. + bool operator<(Edge) const { return false; } + }; + + /// 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& e) : Edge(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + EdgeIt(Invalid) { } + /// This constructor sets the iterator to the first edge. + + /// This constructor sets the iterator to the first edge. + EdgeIt(const Graph&) { } + /// Edge -> EdgeIt conversion + + /// Sets the iterator to the value of the trivial iterator. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the + /// same. + EdgeIt(const Graph&, const Edge&) { } + /// Next edge + + /// Assign the iterator to the next edge. + EdgeIt& operator++() { return *this; } + }; + + /// \brief This iterator goes trough the incident undirected + /// arcs of a node. + /// + /// This iterator goes trough the incident edges + /// of a certain node of a graph. You should assume that the + /// loop arcs will be iterated twice. + /// + /// Its usage is quite simple, for example you can compute the + /// degree (i.e. count the number of incident arcs of a node \c n + /// in graph \c g of type \c Graph as follows. + /// + ///\code + /// int count=0; + /// for(Graph::IncArcIt e(g, n); e!=INVALID; ++e) ++count; + ///\endcode + class IncArcIt : public Edge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + IncArcIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + IncArcIt(const IncArcIt& e) : Edge(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + IncArcIt(Invalid) { } + /// This constructor sets the iterator to first incident arc. + + /// This constructor set the iterator to the first incident arc of + /// the node. + IncArcIt(const Graph&, const Node&) { } + /// Edge -> IncArcIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the arc-set, the iteration order is the same. + IncArcIt(const Graph&, const Edge&) { } + /// Next incident arc + + /// Assign the iterator to the next incident arc + /// of the corresponding node. + IncArcIt& operator++() { return *this; } + }; + + /// The directed arc type. + + /// The directed arc type. It can be converted to the + /// edge or it should be inherited from the undirected + /// arc. + class Arc : public Edge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + Arc() { } + /// Copy constructor. + + /// Copy constructor. + /// + Arc(const Arc& e) : Edge(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + Arc(Invalid) { } + /// Equality operator + + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. + bool operator==(Arc) const { return true; } + /// Inequality operator + + /// \sa operator==(Arc n) + /// + bool operator!=(Arc) const { return true; } + + /// Artificial ordering operator. + + /// To allow the use of graph descriptors as key type in std::map or + /// similar associative container we require this. + /// + /// \note This operator only have to define some strict ordering of + /// the items; this order has nothing to do with the iteration + /// ordering of the items. + bool operator<(Arc) const { return false; } + + }; + /// This iterator goes through each directed arc. + + /// This iterator goes through each arc of a graph. + /// Its usage is quite simple, for example you can count the number + /// of arcs in a graph \c g of type \c Graph as follows: + ///\code + /// int count=0; + /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count; + ///\endcode + class ArcIt : public Arc { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + ArcIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + ArcIt(const ArcIt& e) : Arc(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + ArcIt(Invalid) { } + /// This constructor sets the iterator to the first arc. + + /// This constructor sets the iterator to the first arc of \c g. + ///@param g the graph + ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } + /// Arc -> ArcIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the arc-set, the iteration order is the same. + ArcIt(const Graph&, const Arc&) { } + ///Next arc + + /// Assign the iterator to the next arc. + ArcIt& operator++() { return *this; } + }; + + /// This iterator goes trough the outgoing directed arcs of a node. + + /// This iterator goes trough the \e outgoing arcs of a certain node + /// of a graph. + /// Its usage is quite simple, for example you can count the number + /// of outgoing arcs of a node \c n + /// in graph \c g of type \c Graph as follows. + ///\code + /// int count=0; + /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; + ///\endcode + + class OutArcIt : public Arc { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + OutArcIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + OutArcIt(const OutArcIt& e) : Arc(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + OutArcIt(Invalid) { } + /// This constructor sets the iterator to the first outgoing arc. + + /// This constructor sets the iterator to the first outgoing arc of + /// the node. + ///@param n the node + ///@param g the graph + OutArcIt(const Graph& n, const Node& g) { + ignore_unused_variable_warning(n); + ignore_unused_variable_warning(g); + } + /// Arc -> OutArcIt conversion + + /// Sets the iterator to the value of the trivial iterator. + /// This feature necessitates that each time we + /// iterate the arc-set, the iteration order is the same. + OutArcIt(const Graph&, const Arc&) { } + ///Next outgoing arc + + /// Assign the iterator to the next + /// outgoing arc of the corresponding node. + OutArcIt& operator++() { return *this; } + }; + + /// This iterator goes trough the incoming directed arcs of a node. + + /// This iterator goes trough the \e incoming arcs of a certain node + /// of a graph. + /// Its usage is quite simple, for example you can count the number + /// of outgoing arcs of a node \c n + /// in graph \c g of type \c Graph as follows. + ///\code + /// int count=0; + /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count; + ///\endcode + + class InArcIt : public Arc { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + InArcIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + InArcIt(const InArcIt& e) : Arc(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + InArcIt(Invalid) { } + /// This constructor sets the iterator to first incoming arc. + + /// This constructor set the iterator to the first incoming arc of + /// the node. + ///@param n the node + ///@param g the graph + InArcIt(const Graph& g, const Node& n) { + ignore_unused_variable_warning(n); + ignore_unused_variable_warning(g); + } + /// Arc -> InArcIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the arc-set, the iteration order is the same. + InArcIt(const Graph&, const Arc&) { } + /// Next incoming arc + + /// Assign the iterator to the next inarc of the corresponding node. + /// + InArcIt& operator++() { return *this; } + }; + + /// \brief Read write map of the nodes to type \c T. + /// + /// ReadWrite map of the nodes to type \c T. + /// \sa Reference + template + class NodeMap : public ReadWriteMap< Node, T > + { + public: + + ///\e + NodeMap(const Graph&) { } + ///\e + NodeMap(const Graph&, T) { } + + ///Copy constructor + NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } + ///Assignment operator + template + NodeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + }; + + /// \brief Read write map of the directed arcs to type \c T. + /// + /// Reference map of the directed arcs to type \c T. + /// \sa Reference + template + class ArcMap : public ReadWriteMap + { + public: + + ///\e + ArcMap(const Graph&) { } + ///\e + ArcMap(const Graph&, T) { } + ///Copy constructor + ArcMap(const ArcMap& em) : ReadWriteMap(em) { } + ///Assignment operator + template + ArcMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + }; + + /// Read write map of the edges to type \c T. + + /// Reference map of the arcs to type \c T. + /// \sa Reference + template + class EdgeMap : public ReadWriteMap + { + public: + + ///\e + EdgeMap(const Graph&) { } + ///\e + EdgeMap(const Graph&, T) { } + ///Copy constructor + EdgeMap(const EdgeMap& em) : ReadWriteMap(em) {} + ///Assignment operator + template + EdgeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + }; + + /// \brief Direct the given edge. + /// + /// Direct the given edge. The returned arc source + /// will be the given node. + Arc direct(const Edge&, const Node&) const { + return INVALID; + } + + /// \brief Direct the given edge. + /// + /// Direct the given edge. The returned arc + /// represents the given edge and the direction comes + /// from the bool parameter. The source of the edge and + /// the directed arc is the same when the given bool is true. + Arc direct(const Edge&, bool) const { + return INVALID; + } + + /// \brief Returns true if the arc has default orientation. + /// + /// Returns whether the given directed arc is same orientation as + /// the corresponding edge's default orientation. + bool direction(Arc) const { return true; } + + /// \brief Returns the opposite directed arc. + /// + /// Returns the opposite directed arc. + Arc oppositeArc(Arc) const { return INVALID; } + + /// \brief Opposite node on an arc + /// + /// \return the opposite of the given Node on the given Edge + Node oppositeNode(Node, Edge) const { return INVALID; } + + /// \brief First node of the edge. + /// + /// \return the first node of the given Edge. + /// + /// Naturally edges don't have direction and thus + /// don't have source and target node. But we use these two methods + /// to query the two nodes of the arc. The direction of the arc + /// which arises this way is called the inherent direction of the + /// edge, and is used to define the "default" direction + /// of the directed versions of the arcs. + /// \sa direction + Node u(Edge) const { return INVALID; } + + /// \brief Second node of the edge. + Node v(Edge) const { return INVALID; } + + /// \brief Source node of the directed arc. + Node source(Arc) const { return INVALID; } + + /// \brief Target node of the directed arc. + Node target(Arc) const { return INVALID; } + + void first(Node&) const {} + void next(Node&) const {} + + void first(Edge&) const {} + void next(Edge&) const {} + + void first(Arc&) const {} + void next(Arc&) const {} + + void firstOut(Arc&, Node) const {} + void nextOut(Arc&) const {} + + void firstIn(Arc&, Node) const {} + void nextIn(Arc&) const {} + + + void firstInc(Edge &, bool &, const Node &) const {} + void nextInc(Edge &, bool &) const {} + + /// \brief Base node of the iterator + /// + /// Returns the base node (the source in this case) of the iterator + Node baseNode(OutArcIt e) const { + return source(e); + } + /// \brief Running node of the iterator + /// + /// Returns the running node (the target in this case) of the + /// iterator + Node runningNode(OutArcIt e) const { + return target(e); + } + + /// \brief Base node of the iterator + /// + /// Returns the base node (the target in this case) of the iterator + Node baseNode(InArcIt e) const { + return target(e); + } + /// \brief Running node of the iterator + /// + /// Returns the running node (the source in this case) of the + /// iterator + Node runningNode(InArcIt e) const { + return source(e); + } + + /// \brief Base node of the iterator + /// + /// Returns the base node of the iterator + Node baseNode(IncArcIt) const { + return INVALID; + } + + /// \brief Running node of the iterator + /// + /// Returns the running node of the iterator + Node runningNode(IncArcIt) const { + return INVALID; + } + + template + struct Constraints { + void constraints() { + checkConcept, Graph>(); + checkConcept, Graph>(); + } + }; + + }; + + } + +} + +#endif diff --git a/lemon/concepts/graph_components.h b/lemon/concepts/graph_components.h new file mode 100644 --- /dev/null +++ b/lemon/concepts/graph_components.h @@ -0,0 +1,1490 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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 graph_concepts +///\file +///\brief The concept of graph components. + + +#ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H +#define LEMON_CONCEPT_GRAPH_COMPONENTS_H + +#include +#include + +#include + +namespace lemon { + namespace concepts { + + /// \brief Skeleton class for graph Node and Arc types + /// + /// This class describes the interface of Node and Arc (and Edge + /// in undirected graphs) subtypes of graph types. + /// + /// \note This class is a template class so that we can use it to + /// create graph skeleton classes. The reason for this is than Node + /// and Arc types should \em not derive from the same base class. + /// For Node you should instantiate it with character 'n' and for Arc + /// with 'a'. + +#ifndef DOXYGEN + template +#endif + class GraphItem { + public: + /// \brief Default constructor. + /// + /// \warning The default constructor is not required to set + /// the item to some well-defined value. So you should consider it + /// as uninitialized. + GraphItem() {} + /// \brief Copy constructor. + /// + /// Copy constructor. + /// + GraphItem(const GraphItem &) {} + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the item to be invalid. + /// \sa Invalid for more details. + GraphItem(Invalid) {} + /// \brief Assign operator for nodes. + /// + /// The nodes are assignable. + /// + GraphItem& operator=(GraphItem const&) { return *this; } + /// \brief Equality operator. + /// + /// Two iterators are equal if and only if they represents the + /// same node in the graph or both are invalid. + bool operator==(GraphItem) const { return false; } + /// \brief Inequality operator. + /// + /// \sa operator==(const Node& n) + /// + bool operator!=(GraphItem) const { return false; } + + /// \brief Artificial ordering operator. + /// + /// To allow the use of graph descriptors as key type in std::map or + /// similar associative container we require this. + /// + /// \note This operator only have to define some strict ordering of + /// the items; this order has nothing to do with the iteration + /// ordering of the items. + bool operator<(GraphItem) const { return false; } + + template + struct Constraints { + void constraints() { + _GraphItem i1; + _GraphItem i2 = i1; + _GraphItem i3 = INVALID; + + i1 = i2 = i3; + + bool b; + // b = (ia == ib) && (ia != ib) && (ia < ib); + b = (ia == ib) && (ia != ib); + b = (ia == INVALID) && (ib != INVALID); + b = (ia < ib); + } + + const _GraphItem &ia; + const _GraphItem &ib; + }; + }; + + /// \brief An empty base directed graph class. + /// + /// This class provides the minimal set of features needed for a + /// directed graph structure. All digraph concepts have to be + /// conform to this base directed graph. It just provides types + /// for nodes and arcs and functions to get the source and the + /// target of the arcs. + class BaseDigraphComponent { + public: + + typedef BaseDigraphComponent Digraph; + + /// \brief Node class of the digraph. + /// + /// This class represents the Nodes of the digraph. + /// + typedef GraphItem<'n'> Node; + + /// \brief Arc class of the digraph. + /// + /// This class represents the Arcs of the digraph. + /// + typedef GraphItem<'e'> Arc; + + /// \brief Gives back the target node of an arc. + /// + /// Gives back the target node of an arc. + /// + Node target(const Arc&) const { return INVALID;} + + /// \brief Gives back the source node of an arc. + /// + /// Gives back the source node of an arc. + /// + Node source(const Arc&) const { return INVALID;} + + /// \brief Gives back the opposite node on the given arc. + /// + /// Gives back the opposite node on the given arc. + Node oppositeNode(const Node&, const Arc&) const { + return INVALID; + } + + template + struct Constraints { + typedef typename _Digraph::Node Node; + typedef typename _Digraph::Arc Arc; + + void constraints() { + checkConcept, Node>(); + checkConcept, Arc>(); + { + Node n; + Arc e(INVALID); + n = digraph.source(e); + n = digraph.target(e); + n = digraph.oppositeNode(n, e); + } + } + + const _Digraph& digraph; + }; + }; + + /// \brief An empty base undirected graph class. + /// + /// This class provides the minimal set of features needed for an + /// undirected graph structure. All undirected graph concepts have + /// to be conform to this base graph. It just provides types for + /// nodes, arcs and edges and functions to get the + /// source and the target of the arcs and edges, + /// conversion from arcs to edges and function to get + /// both direction of the edges. + class BaseGraphComponent : public BaseDigraphComponent { + public: + typedef BaseDigraphComponent::Node Node; + typedef BaseDigraphComponent::Arc Arc; + /// \brief Undirected arc class of the graph. + /// + /// This class represents the edges of the graph. + /// The undirected graphs can be used as a directed graph which + /// for each arc contains the opposite arc too so the graph is + /// bidirected. The edge represents two opposite + /// directed arcs. + class Edge : public GraphItem<'u'> { + public: + typedef GraphItem<'u'> Parent; + /// \brief Default constructor. + /// + /// \warning The default constructor is not required to set + /// the item to some well-defined value. So you should consider it + /// as uninitialized. + Edge() {} + /// \brief Copy constructor. + /// + /// Copy constructor. + /// + Edge(const Edge &) : Parent() {} + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the item to be invalid. + /// \sa Invalid for more details. + Edge(Invalid) {} + /// \brief Converter from arc to edge. + /// + /// Besides the core graph item functionality each arc should + /// be convertible to the represented edge. + Edge(const Arc&) {} + /// \brief Assign arc to edge. + /// + /// Besides the core graph item functionality each arc should + /// be convertible to the represented edge. + Edge& operator=(const Arc&) { return *this; } + }; + + /// \brief Returns the direction of the arc. + /// + /// Returns the direction of the arc. Each arc represents an + /// edge with a direction. It gives back the + /// direction. + bool direction(const Arc&) const { return true; } + + /// \brief Returns the directed arc. + /// + /// Returns the directed arc from its direction and the + /// represented edge. + Arc direct(const Edge&, bool) const { return INVALID;} + + /// \brief Returns the directed arc. + /// + /// Returns the directed arc from its source and the + /// represented edge. + Arc direct(const Edge&, const Node&) const { return INVALID;} + + /// \brief Returns the opposite arc. + /// + /// Returns the opposite arc. It is the arc representing the + /// same edge and has opposite direction. + Arc oppositeArc(const Arc&) const { return INVALID;} + + /// \brief Gives back one ending of an edge. + /// + /// Gives back one ending of an edge. + Node u(const Edge&) const { return INVALID;} + + /// \brief Gives back the other ending of an edge. + /// + /// Gives back the other ending of an edge. + Node v(const Edge&) const { return INVALID;} + + template + struct Constraints { + typedef typename _Graph::Node Node; + typedef typename _Graph::Arc Arc; + typedef typename _Graph::Edge Edge; + + void constraints() { + checkConcept(); + checkConcept, Edge>(); + { + Node n; + Edge ue(INVALID); + Arc e; + n = graph.u(ue); + n = graph.v(ue); + e = graph.direct(ue, true); + e = graph.direct(ue, n); + e = graph.oppositeArc(e); + ue = e; + bool d = graph.direction(e); + ignore_unused_variable_warning(d); + } + } + + const _Graph& graph; + }; + + }; + + /// \brief An empty idable base digraph class. + /// + /// This class provides beside the core digraph features + /// core id functions for the digraph structure. + /// The most of the base digraphs should be conform to this concept. + /// The id's are unique and immutable. + template + class IDableDigraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Arc Arc; + + /// \brief 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;} + + /// \brief Gives back the node by the unique id. + /// + /// Gives back the node by the unique id. + /// If the digraph does not contain node with the given id + /// then the result of the function is undetermined. + Node nodeFromId(int) const { return INVALID;} + + /// \brief Gives back an unique integer id for the Arc. + /// + /// Gives back an unique integer id for the Arc. + /// + int id(const Arc&) const { return -1;} + + /// \brief Gives back the arc by the unique id. + /// + /// Gives back the arc by the unique id. + /// If the digraph does not contain arc with the given id + /// then the result of the function is undetermined. + Arc arcFromId(int) const { return INVALID;} + + /// \brief 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 maxNodeId() const { return -1;} + + /// \brief Gives back an integer greater or equal to the maximum + /// Arc id. + /// + /// Gives back an integer greater or equal to the maximum Arc + /// id. + int maxArcId() const { return -1;} + + template + struct Constraints { + + void constraints() { + checkConcept(); + typename _Digraph::Node node; + int nid = digraph.id(node); + nid = digraph.id(node); + node = digraph.nodeFromId(nid); + typename _Digraph::Arc arc; + int eid = digraph.id(arc); + eid = digraph.id(arc); + arc = digraph.arcFromId(eid); + + nid = digraph.maxNodeId(); + ignore_unused_variable_warning(nid); + eid = digraph.maxArcId(); + ignore_unused_variable_warning(eid); + } + + const _Digraph& digraph; + }; + }; + + /// \brief An empty idable base undirected graph class. + /// + /// This class provides beside the core undirected graph features + /// core id functions for the undirected graph structure. The + /// most of the base undirected graphs should be conform to this + /// concept. The id's are unique and immutable. + template + class IDableGraphComponent : public IDableDigraphComponent<_Base> { + public: + + typedef _Base Base; + typedef typename Base::Edge Edge; + + using IDableDigraphComponent<_Base>::id; + + /// \brief 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;} + + /// \brief Gives back the edge by the unique id. + /// + /// Gives back the edge by the unique id. If the + /// graph does not contain arc with the given id then the + /// result of the function is undetermined. + Edge edgeFromId(int) const { return INVALID;} + + /// \brief 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 maxEdgeId() const { return -1;} + + template + struct Constraints { + + void constraints() { + checkConcept(); + checkConcept, _Graph >(); + typename _Graph::Edge edge; + int ueid = graph.id(edge); + ueid = graph.id(edge); + edge = graph.edgeFromId(ueid); + ueid = graph.maxEdgeId(); + ignore_unused_variable_warning(ueid); + } + + const _Graph& graph; + }; + }; + + /// \brief Skeleton class for graph NodeIt and ArcIt + /// + /// Skeleton class for graph NodeIt and ArcIt. + /// + template + class GraphItemIt : public _Item { + public: + /// \brief Default constructor. + /// + /// @warning The default constructor sets the iterator + /// to an undefined value. + GraphItemIt() {} + /// \brief Copy constructor. + /// + /// Copy constructor. + /// + GraphItemIt(const GraphItemIt& ) {} + /// \brief Sets the iterator to the first item. + /// + /// Sets the iterator to the first item of \c the graph. + /// + explicit GraphItemIt(const _Graph&) {} + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the item to be invalid. + /// \sa Invalid for more details. + GraphItemIt(Invalid) {} + /// \brief Assign operator for items. + /// + /// The items are assignable. + /// + GraphItemIt& operator=(const GraphItemIt&) { return *this; } + /// \brief Next item. + /// + /// Assign the iterator to the next item. + /// + GraphItemIt& operator++() { return *this; } + /// \brief Equality operator + /// + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. + bool operator==(const GraphItemIt&) const { return true;} + /// \brief Inequality operator + /// + /// \sa operator==(Node n) + /// + bool operator!=(const GraphItemIt&) const { return true;} + + template + struct Constraints { + void constraints() { + _GraphItemIt it1(g); + _GraphItemIt it2; + + it2 = ++it1; + ++it2 = it1; + ++(++it1); + + _Item bi = it1; + bi = it2; + } + _Graph& g; + }; + }; + + /// \brief Skeleton class for graph InArcIt and OutArcIt + /// + /// \note Because InArcIt and OutArcIt may not inherit from the same + /// base class, the _selector is a additional template parameter. For + /// InArcIt you should instantiate it with character 'i' and for + /// OutArcIt with 'o'. + template + class GraphIncIt : public _Item { + public: + /// \brief Default constructor. + /// + /// @warning The default constructor sets the iterator + /// to an undefined value. + GraphIncIt() {} + /// \brief Copy constructor. + /// + /// Copy constructor. + /// + GraphIncIt(GraphIncIt const& gi) : _Item(gi) {} + /// \brief Sets the iterator to the first arc incoming into or outgoing + /// from the node. + /// + /// Sets the iterator to the first arc incoming into or outgoing + /// from the node. + /// + explicit GraphIncIt(const _Graph&, const _Base&) {} + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the item to be invalid. + /// \sa Invalid for more details. + GraphIncIt(Invalid) {} + /// \brief Assign operator for iterators. + /// + /// The iterators are assignable. + /// + GraphIncIt& operator=(GraphIncIt const&) { return *this; } + /// \brief Next item. + /// + /// Assign the iterator to the next item. + /// + GraphIncIt& operator++() { return *this; } + + /// \brief Equality operator + /// + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. + bool operator==(const GraphIncIt&) const { return true;} + + /// \brief Inequality operator + /// + /// \sa operator==(Node n) + /// + bool operator!=(const GraphIncIt&) const { return true;} + + template + struct Constraints { + void constraints() { + checkConcept, _GraphIncIt>(); + _GraphIncIt it1(graph, node); + _GraphIncIt it2; + + it2 = ++it1; + ++it2 = it1; + ++(++it1); + _Item e = it1; + e = it2; + + } + + _Item arc; + _Base node; + _Graph graph; + _GraphIncIt it; + }; + }; + + + /// \brief An empty iterable digraph class. + /// + /// This class provides beside the core digraph features + /// iterator based iterable interface for the digraph structure. + /// This concept is part of the Digraph concept. + template + class IterableDigraphComponent : public _Base { + + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Arc Arc; + + typedef IterableDigraphComponent Digraph; + + /// \name Base iteration + /// + /// This interface provides functions for iteration on digraph items + /// + /// @{ + + /// \brief Gives back the first node in the iterating order. + /// + /// Gives back the first node in the iterating order. + /// + void first(Node&) const {} + + /// \brief Gives back the next node in the iterating order. + /// + /// Gives back the next node in the iterating order. + /// + void next(Node&) const {} + + /// \brief Gives back the first arc in the iterating order. + /// + /// Gives back the first arc in the iterating order. + /// + void first(Arc&) const {} + + /// \brief Gives back the next arc in the iterating order. + /// + /// Gives back the next arc in the iterating order. + /// + void next(Arc&) const {} + + + /// \brief Gives back the first of the arcs point to the given + /// node. + /// + /// Gives back the first of the arcs point to the given node. + /// + void firstIn(Arc&, const Node&) const {} + + /// \brief Gives back the next of the arcs points to the given + /// node. + /// + /// Gives back the next of the arcs points to the given node. + /// + void nextIn(Arc&) const {} + + /// \brief Gives back the first of the arcs start from the + /// given node. + /// + /// Gives back the first of the arcs start from the given node. + /// + void firstOut(Arc&, const Node&) const {} + + /// \brief Gives back the next of the arcs start from the given + /// node. + /// + /// Gives back the next of the arcs start from the given node. + /// + void nextOut(Arc&) const {} + + /// @} + + /// \name Class based iteration + /// + /// This interface provides functions for iteration on digraph items + /// + /// @{ + + /// \brief This iterator goes through each node. + /// + /// This iterator goes through each node. + /// + typedef GraphItemIt NodeIt; + + /// \brief This iterator goes through each node. + /// + /// This iterator goes through each node. + /// + typedef GraphItemIt ArcIt; + + /// \brief This iterator goes trough the incoming arcs of a node. + /// + /// This iterator goes trough the \e inccoming arcs of a certain node + /// of a digraph. + typedef GraphIncIt InArcIt; + + /// \brief This iterator goes trough the outgoing arcs of a node. + /// + /// This iterator goes trough the \e outgoing arcs of a certain node + /// of a digraph. + typedef GraphIncIt OutArcIt; + + /// \brief The base node of the iterator. + /// + /// Gives back the base node of the iterator. + /// It is always the target of the pointed arc. + Node baseNode(const InArcIt&) const { return INVALID; } + + /// \brief The running node of the iterator. + /// + /// Gives back the running node of the iterator. + /// It is always the source of the pointed arc. + Node runningNode(const InArcIt&) const { return INVALID; } + + /// \brief The base node of the iterator. + /// + /// Gives back the base node of the iterator. + /// It is always the source of the pointed arc. + Node baseNode(const OutArcIt&) const { return INVALID; } + + /// \brief The running node of the iterator. + /// + /// Gives back the running node of the iterator. + /// It is always the target of the pointed arc. + Node runningNode(const OutArcIt&) const { return INVALID; } + + /// @} + + template + struct Constraints { + void constraints() { + checkConcept(); + + { + typename _Digraph::Node node(INVALID); + typename _Digraph::Arc arc(INVALID); + { + digraph.first(node); + digraph.next(node); + } + { + digraph.first(arc); + digraph.next(arc); + } + { + digraph.firstIn(arc, node); + digraph.nextIn(arc); + } + { + digraph.firstOut(arc, node); + digraph.nextOut(arc); + } + } + + { + checkConcept, + typename _Digraph::ArcIt >(); + checkConcept, + typename _Digraph::NodeIt >(); + checkConcept, typename _Digraph::InArcIt>(); + checkConcept, typename _Digraph::OutArcIt>(); + + typename _Digraph::Node n; + typename _Digraph::InArcIt ieit(INVALID); + typename _Digraph::OutArcIt oeit(INVALID); + n = digraph.baseNode(ieit); + n = digraph.runningNode(ieit); + n = digraph.baseNode(oeit); + n = digraph.runningNode(oeit); + ignore_unused_variable_warning(n); + } + } + + const _Digraph& digraph; + + }; + }; + + /// \brief An empty iterable undirected graph class. + /// + /// This class provides beside the core graph features iterator + /// based iterable interface for the undirected graph structure. + /// This concept is part of the Graph concept. + template + class IterableGraphComponent : public IterableDigraphComponent<_Base> { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Arc Arc; + typedef typename Base::Edge Edge; + + + typedef IterableGraphComponent Graph; + + /// \name Base iteration + /// + /// This interface provides functions for iteration on graph items + /// @{ + + using IterableDigraphComponent<_Base>::first; + using IterableDigraphComponent<_Base>::next; + + /// \brief Gives back the first edge in the iterating + /// order. + /// + /// Gives back the first edge in the iterating order. + /// + void first(Edge&) const {} + + /// \brief Gives back the next edge in the iterating + /// order. + /// + /// Gives back the next edge in the iterating order. + /// + void next(Edge&) const {} + + + /// \brief Gives back the first of the edges from the + /// given node. + /// + /// Gives back the first of the edges from the given + /// node. The bool parameter gives back that direction which + /// gives a good direction of the edge so the source of the + /// directed arc is the given node. + void firstInc(Edge&, bool&, const Node&) const {} + + /// \brief Gives back the next of the edges from the + /// given node. + /// + /// Gives back the next of the edges from the given + /// node. The bool parameter should be used as the \c firstInc() + /// use it. + void nextInc(Edge&, bool&) const {} + + using IterableDigraphComponent<_Base>::baseNode; + using IterableDigraphComponent<_Base>::runningNode; + + /// @} + + /// \name Class based iteration + /// + /// This interface provides functions for iteration on graph items + /// + /// @{ + + /// \brief This iterator goes through each node. + /// + /// This iterator goes through each node. + typedef GraphItemIt EdgeIt; + /// \brief This iterator goes trough the incident arcs of a + /// node. + /// + /// This iterator goes trough the incident arcs of a certain + /// node of a graph. + typedef GraphIncIt IncArcIt; + /// \brief The base node of the iterator. + /// + /// Gives back the base node of the iterator. + Node baseNode(const IncArcIt&) const { return INVALID; } + + /// \brief The running node of the iterator. + /// + /// Gives back the running node of the iterator. + Node runningNode(const IncArcIt&) const { return INVALID; } + + /// @} + + template + struct Constraints { + void constraints() { + checkConcept, _Graph>(); + + { + typename _Graph::Node node(INVALID); + typename _Graph::Edge edge(INVALID); + bool dir; + { + graph.first(edge); + graph.next(edge); + } + { + graph.firstInc(edge, dir, node); + graph.nextInc(edge, dir); + } + + } + + { + checkConcept, + typename _Graph::EdgeIt >(); + checkConcept, typename _Graph::IncArcIt>(); + + typename _Graph::Node n; + typename _Graph::IncArcIt ueit(INVALID); + n = graph.baseNode(ueit); + n = graph.runningNode(ueit); + } + } + + const _Graph& graph; + + }; + }; + + /// \brief An empty alteration notifier digraph class. + /// + /// This class provides beside the core digraph features alteration + /// notifier interface for the digraph structure. This implements + /// an observer-notifier pattern for each digraph item. More + /// obsevers can be registered into the notifier and whenever an + /// alteration occured in the digraph all the observers will + /// notified about it. + template + class AlterableDigraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Arc Arc; + + + /// The node observer registry. + typedef AlterationNotifier + NodeNotifier; + /// The arc observer registry. + typedef AlterationNotifier + ArcNotifier; + + /// \brief Gives back the node alteration notifier. + /// + /// Gives back the node alteration notifier. + NodeNotifier& notifier(Node) const { + return NodeNotifier(); + } + + /// \brief Gives back the arc alteration notifier. + /// + /// Gives back the arc alteration notifier. + ArcNotifier& notifier(Arc) const { + return ArcNotifier(); + } + + template + struct Constraints { + void constraints() { + checkConcept(); + typename _Digraph::NodeNotifier& nn + = digraph.notifier(typename _Digraph::Node()); + + typename _Digraph::ArcNotifier& en + = digraph.notifier(typename _Digraph::Arc()); + + ignore_unused_variable_warning(nn); + ignore_unused_variable_warning(en); + } + + const _Digraph& digraph; + + }; + + }; + + /// \brief An empty alteration notifier undirected graph class. + /// + /// This class provides beside the core graph features alteration + /// notifier interface for the graph structure. This implements + /// an observer-notifier pattern for each graph item. More + /// obsevers can be registered into the notifier and whenever an + /// alteration occured in the graph all the observers will + /// notified about it. + template + class AlterableGraphComponent : public AlterableDigraphComponent<_Base> { + public: + + typedef _Base Base; + typedef typename Base::Edge Edge; + + + /// The arc observer registry. + typedef AlterationNotifier + EdgeNotifier; + + /// \brief Gives back the arc alteration notifier. + /// + /// Gives back the arc alteration notifier. + EdgeNotifier& notifier(Edge) const { + return EdgeNotifier(); + } + + template + struct Constraints { + void constraints() { + checkConcept, _Graph>(); + typename _Graph::EdgeNotifier& uen + = graph.notifier(typename _Graph::Edge()); + ignore_unused_variable_warning(uen); + } + + const _Graph& graph; + + }; + + }; + + /// \brief Class describing the concept of graph maps + /// + /// This class describes the common interface of the graph maps + /// (NodeMap, ArcMap), that is \ref maps-page "maps" which can be used to + /// associate data to graph descriptors (nodes or arcs). + template + class GraphMap : public ReadWriteMap<_Item, _Value> { + public: + + typedef ReadWriteMap<_Item, _Value> Parent; + + /// The graph type of the map. + typedef _Graph Graph; + /// The key type of the map. + typedef _Item Key; + /// The value type of the map. + typedef _Value Value; + + /// \brief Construct a new map. + /// + /// Construct a new map for the graph. + explicit GraphMap(const Graph&) {} + /// \brief Construct a new map with default value. + /// + /// Construct a new map for the graph and initalise the values. + GraphMap(const Graph&, const Value&) {} + /// \brief Copy constructor. + /// + /// Copy Constructor. + GraphMap(const GraphMap&) : Parent() {} + + /// \brief Assign operator. + /// + /// Assign operator. It does not mofify the underlying graph, + /// it just iterates on the current item set and set the map + /// with the value returned by the assigned map. + template + GraphMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + + template + struct Constraints { + void constraints() { + checkConcept, _Map >(); + // Construction with a graph parameter + _Map a(g); + // Constructor with a graph and a default value parameter + _Map a2(g,t); + // Copy constructor. + _Map b(c); + + ReadMap cmap; + b = cmap; + + ignore_unused_variable_warning(a2); + ignore_unused_variable_warning(b); + } + + const _Map &c; + const Graph &g; + const typename GraphMap::Value &t; + }; + + }; + + /// \brief An empty mappable digraph class. + /// + /// This class provides beside the core digraph features + /// map interface for the digraph structure. + /// This concept is part of the Digraph concept. + template + class MappableDigraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Arc Arc; + + typedef MappableDigraphComponent Digraph; + + /// \brief ReadWrite map of the nodes. + /// + /// ReadWrite map of the nodes. + /// + template + class NodeMap : public GraphMap { + public: + typedef GraphMap Parent; + + /// \brief Construct a new map. + /// + /// Construct a new map for the digraph. + explicit NodeMap(const MappableDigraphComponent& digraph) + : Parent(digraph) {} + + /// \brief Construct a new map with default value. + /// + /// Construct a new map for the digraph and initalise the values. + NodeMap(const MappableDigraphComponent& digraph, const _Value& value) + : Parent(digraph, value) {} + + /// \brief Copy constructor. + /// + /// Copy Constructor. + NodeMap(const NodeMap& nm) : Parent(nm) {} + + /// \brief Assign operator. + /// + /// Assign operator. + template + NodeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + + }; + + /// \brief ReadWrite map of the arcs. + /// + /// ReadWrite map of the arcs. + /// + template + class ArcMap : public GraphMap { + public: + typedef GraphMap Parent; + + /// \brief Construct a new map. + /// + /// Construct a new map for the digraph. + explicit ArcMap(const MappableDigraphComponent& digraph) + : Parent(digraph) {} + + /// \brief Construct a new map with default value. + /// + /// Construct a new map for the digraph and initalise the values. + ArcMap(const MappableDigraphComponent& digraph, const _Value& value) + : Parent(digraph, value) {} + + /// \brief Copy constructor. + /// + /// Copy Constructor. + ArcMap(const ArcMap& nm) : Parent(nm) {} + + /// \brief Assign operator. + /// + /// Assign operator. + template + ArcMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + + }; + + + template + struct Constraints { + + struct Dummy { + int value; + Dummy() : value(0) {} + Dummy(int _v) : value(_v) {} + }; + + void constraints() { + checkConcept(); + { // int map test + typedef typename _Digraph::template NodeMap IntNodeMap; + checkConcept, + IntNodeMap >(); + } { // bool map test + typedef typename _Digraph::template NodeMap BoolNodeMap; + checkConcept, + BoolNodeMap >(); + } { // Dummy map test + typedef typename _Digraph::template NodeMap DummyNodeMap; + checkConcept, + DummyNodeMap >(); + } + + { // int map test + typedef typename _Digraph::template ArcMap IntArcMap; + checkConcept, + IntArcMap >(); + } { // bool map test + typedef typename _Digraph::template ArcMap BoolArcMap; + checkConcept, + BoolArcMap >(); + } { // Dummy map test + typedef typename _Digraph::template ArcMap DummyArcMap; + checkConcept, + DummyArcMap >(); + } + } + + _Digraph& digraph; + }; + }; + + /// \brief An empty mappable base bipartite graph class. + /// + /// This class provides beside the core graph features + /// map interface for the graph structure. + /// This concept is part of the Graph concept. + template + class MappableGraphComponent : public MappableDigraphComponent<_Base> { + public: + + typedef _Base Base; + typedef typename Base::Edge Edge; + + typedef MappableGraphComponent Graph; + + /// \brief ReadWrite map of the edges. + /// + /// ReadWrite map of the edges. + /// + template + class EdgeMap : public GraphMap { + public: + typedef GraphMap Parent; + + /// \brief Construct a new map. + /// + /// Construct a new map for the graph. + explicit EdgeMap(const MappableGraphComponent& graph) + : Parent(graph) {} + + /// \brief Construct a new map with default value. + /// + /// Construct a new map for the graph and initalise the values. + EdgeMap(const MappableGraphComponent& graph, const _Value& value) + : Parent(graph, value) {} + + /// \brief Copy constructor. + /// + /// Copy Constructor. + EdgeMap(const EdgeMap& nm) : Parent(nm) {} + + /// \brief Assign operator. + /// + /// Assign operator. + template + EdgeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + + }; + + + template + struct Constraints { + + struct Dummy { + int value; + Dummy() : value(0) {} + Dummy(int _v) : value(_v) {} + }; + + void constraints() { + checkConcept, _Graph>(); + + { // int map test + typedef typename _Graph::template EdgeMap IntEdgeMap; + checkConcept, + IntEdgeMap >(); + } { // bool map test + typedef typename _Graph::template EdgeMap BoolEdgeMap; + checkConcept, + BoolEdgeMap >(); + } { // Dummy map test + typedef typename _Graph::template EdgeMap DummyEdgeMap; + checkConcept, + DummyEdgeMap >(); + } + } + + _Graph& graph; + }; + }; + + /// \brief An empty extendable digraph class. + /// + /// This class provides beside the core digraph features digraph + /// extendable interface for the digraph structure. The main + /// difference between the base and this interface is that the + /// digraph alterations should handled already on this level. + template + class ExtendableDigraphComponent : public _Base { + public: + typedef _Base Base; + + typedef typename _Base::Node Node; + typedef typename _Base::Arc Arc; + + /// \brief Adds a new node to the digraph. + /// + /// Adds a new node to the digraph. + /// + Node addNode() { + return INVALID; + } + + /// \brief Adds a new arc connects the given two nodes. + /// + /// Adds a new arc connects the the given two nodes. + Arc addArc(const Node&, const Node&) { + return INVALID; + } + + template + struct Constraints { + void constraints() { + checkConcept(); + typename _Digraph::Node node_a, node_b; + node_a = digraph.addNode(); + node_b = digraph.addNode(); + typename _Digraph::Arc arc; + arc = digraph.addArc(node_a, node_b); + } + + _Digraph& digraph; + }; + }; + + /// \brief An empty extendable base undirected graph class. + /// + /// This class provides beside the core undirected graph features + /// core undircted graph extend interface for the graph structure. + /// The main difference between the base and this interface is + /// that the graph alterations should handled already on this + /// level. + template + class ExtendableGraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename _Base::Node Node; + typedef typename _Base::Edge Edge; + + /// \brief Adds a new node to the graph. + /// + /// Adds a new node to the graph. + /// + Node addNode() { + return INVALID; + } + + /// \brief Adds a new arc connects the given two nodes. + /// + /// Adds a new arc connects the the given two nodes. + Edge addArc(const Node&, const Node&) { + return INVALID; + } + + template + struct Constraints { + void constraints() { + checkConcept(); + typename _Graph::Node node_a, node_b; + node_a = graph.addNode(); + node_b = graph.addNode(); + typename _Graph::Edge edge; + edge = graph.addEdge(node_a, node_b); + } + + _Graph& graph; + }; + }; + + /// \brief An empty erasable digraph class. + /// + /// This class provides beside the core digraph features core erase + /// functions for the digraph structure. The main difference between + /// the base and this interface is that the digraph alterations + /// should handled already on this level. + template + class ErasableDigraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Arc Arc; + + /// \brief Erase a node from the digraph. + /// + /// Erase a node from the digraph. This function should + /// erase all arcs connecting to the node. + void erase(const Node&) {} + + /// \brief Erase an arc from the digraph. + /// + /// Erase an arc from the digraph. + /// + void erase(const Arc&) {} + + template + struct Constraints { + void constraints() { + checkConcept(); + typename _Digraph::Node node; + digraph.erase(node); + typename _Digraph::Arc arc; + digraph.erase(arc); + } + + _Digraph& digraph; + }; + }; + + /// \brief An empty erasable base undirected graph class. + /// + /// This class provides beside the core undirected graph features + /// core erase functions for the undirceted graph structure. The + /// main difference between the base and this interface is that + /// the graph alterations should handled already on this level. + template + class ErasableGraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; + + /// \brief Erase a node from the graph. + /// + /// Erase a node from the graph. This function should erase + /// arcs connecting to the node. + void erase(const Node&) {} + + /// \brief Erase an arc from the graph. + /// + /// Erase an arc from the graph. + /// + void erase(const Edge&) {} + + template + struct Constraints { + void constraints() { + checkConcept(); + typename _Graph::Node node; + graph.erase(node); + typename _Graph::Arc arc; + graph.erase(arc); + } + + _Graph& graph; + }; + }; + + /// \brief An empty clearable base digraph class. + /// + /// This class provides beside the core digraph features core clear + /// functions for the digraph structure. The main difference between + /// the base and this interface is that the digraph alterations + /// should handled already on this level. + template + class ClearableDigraphComponent : public _Base { + public: + + typedef _Base Base; + + /// \brief Erase all nodes and arcs from the digraph. + /// + /// Erase all nodes and arcs from the digraph. + /// + void clear() {} + + template + struct Constraints { + void constraints() { + checkConcept(); + digraph.clear(); + } + + _Digraph digraph; + }; + }; + + /// \brief An empty clearable base undirected graph class. + /// + /// This class provides beside the core undirected graph features + /// core clear functions for the undirected graph structure. The + /// main difference between the base and this interface is that + /// the graph alterations should handled already on this level. + template + class ClearableGraphComponent : public ClearableDigraphComponent<_Base> { + public: + + typedef _Base Base; + + template + struct Constraints { + void constraints() { + checkConcept, _Graph>(); + } + + _Graph graph; + }; + }; + + } + +} + +#endif diff --git a/lemon/list_graph.h b/lemon/list_graph.h --- a/lemon/list_graph.h +++ b/lemon/list_graph.h @@ -16,3 +16,1452 @@ * */ +#ifndef LEMON_LIST_GRAPH_H +#define LEMON_LIST_GRAPH_H + +///\ingroup graphs +///\file +///\brief ListDigraph, ListGraph classes. + +#include + +#include +#include + +namespace lemon { + + class ListDigraphBase { + + protected: + struct NodeT { + int first_in, first_out; + int prev, next; + }; + + struct ArcT { + int target, source; + int prev_in, prev_out; + int next_in, next_out; + }; + + std::vector nodes; + + int first_node; + + int first_free_node; + + std::vector arcs; + + int first_free_arc; + + public: + + typedef ListDigraphBase Digraph; + + class Node { + friend class ListDigraphBase; + protected: + + int id; + explicit Node(int pid) { id = pid;} + + 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;} + }; + + class Arc { + friend class ListDigraphBase; + protected: + + int id; + explicit Arc(int pid) { id = pid;} + + public: + Arc() {} + Arc (Invalid) { id = -1; } + bool operator==(const Arc& arc) const {return id == arc.id;} + bool operator!=(const Arc& arc) const {return id != arc.id;} + bool operator<(const Arc& arc) const {return id < arc.id;} + }; + + + + ListDigraphBase() + : nodes(), first_node(-1), + first_free_node(-1), arcs(), first_free_arc(-1) {} + + + int maxNodeId() const { return nodes.size()-1; } + int maxArcId() const { return arcs.size()-1; } + + Node source(Arc e) const { return Node(arcs[e.id].source); } + Node target(Arc e) const { return Node(arcs[e.id].target); } + + + void first(Node& node) const { + node.id = first_node; + } + + void next(Node& node) const { + node.id = nodes[node.id].next; + } + + + void first(Arc& 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(Arc& arc) const { + if (arcs[arc.id].next_in != -1) { + arc.id = arcs[arc.id].next_in; + } else { + int n; + for(n = nodes[arcs[arc.id].target].next; + n!=-1 && nodes[n].first_in == -1; + n = nodes[n].next); + arc.id = (n == -1) ? -1 : nodes[n].first_in; + } + } + + void firstOut(Arc &e, const Node& v) const { + e.id = nodes[v.id].first_out; + } + void nextOut(Arc &e) const { + e.id=arcs[e.id].next_out; + } + + void firstIn(Arc &e, const Node& v) const { + e.id = nodes[v.id].first_in; + } + void nextIn(Arc &e) const { + e.id=arcs[e.id].next_in; + } + + + static int id(Node v) { return v.id; } + static int id(Arc e) { return e.id; } + + static Node nodeFromId(int id) { return Node(id);} + static Arc arcFromId(int id) { return Arc(id);} + + 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; + + return Node(n); + } + + Arc addArc(Node u, Node v) { + int n; + + if (first_free_arc == -1) { + n = arcs.size(); + arcs.push_back(ArcT()); + } else { + n = first_free_arc; + first_free_arc = arcs[n].next_in; + } + + arcs[n].source = u.id; + arcs[n].target = v.id; + + arcs[n].next_out = nodes[u.id].first_out; + if(nodes[u.id].first_out != -1) { + arcs[nodes[u.id].first_out].prev_out = n; + } + + arcs[n].next_in = nodes[v.id].first_in; + if(nodes[v.id].first_in != -1) { + arcs[nodes[v.id].first_in].prev_in = n; + } + + arcs[n].prev_in = arcs[n].prev_out = -1; + + nodes[u.id].first_out = nodes[v.id].first_in = n; + + return Arc(n); + } + + 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; + + } + + void erase(const Arc& arc) { + int n = arc.id; + + if(arcs[n].next_in!=-1) { + arcs[arcs[n].next_in].prev_in = arcs[n].prev_in; + } + + if(arcs[n].prev_in!=-1) { + arcs[arcs[n].prev_in].next_in = arcs[n].next_in; + } else { + nodes[arcs[n].target].first_in = arcs[n].next_in; + } + + + if(arcs[n].next_out!=-1) { + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; + } + + if(arcs[n].prev_out!=-1) { + arcs[arcs[n].prev_out].next_out = arcs[n].next_out; + } else { + nodes[arcs[n].source].first_out = arcs[n].next_out; + } + + arcs[n].next_in = first_free_arc; + first_free_arc = n; + + } + + void clear() { + arcs.clear(); + nodes.clear(); + first_node = first_free_node = first_free_arc = -1; + } + + protected: + void changeTarget(Arc e, Node n) + { + if(arcs[e.id].next_in != -1) + arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in; + if(arcs[e.id].prev_in != -1) + arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in; + else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in; + if (nodes[n.id].first_in != -1) { + arcs[nodes[n.id].first_in].prev_in = e.id; + } + arcs[e.id].target = n.id; + arcs[e.id].prev_in = -1; + arcs[e.id].next_in = nodes[n.id].first_in; + nodes[n.id].first_in = e.id; + } + void changeSource(Arc e, Node n) + { + if(arcs[e.id].next_out != -1) + arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out; + if(arcs[e.id].prev_out != -1) + arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out; + else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out; + if (nodes[n.id].first_out != -1) { + arcs[nodes[n.id].first_out].prev_out = e.id; + } + arcs[e.id].source = n.id; + arcs[e.id].prev_out = -1; + arcs[e.id].next_out = nodes[n.id].first_out; + nodes[n.id].first_out = e.id; + } + + }; + + typedef DigraphExtender ExtendedListDigraphBase; + + /// \addtogroup digraphs + /// @{ + + ///A list digraph class. + + ///This is a simple and fast digraph implementation. + /// + ///It conforms to the \ref concepts::Digraph "Digraph concept" and it + ///also provides several additional useful extra functionalities. + ///The most of the member functions and nested classes are + ///documented only in the concept class. + /// + ///An important extra feature of this digraph implementation is that + ///its maps are real \ref concepts::ReferenceMap "reference map"s. + /// + ///\sa concepts::Digraph. + + class ListDigraph : public ExtendedListDigraphBase { + private: + ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead. + + ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead. + /// + ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; + ///\brief Assignment of ListDigraph to another one is \e not allowed. + ///Use DigraphCopy() instead. + + ///Assignment of ListDigraph to another one is \e not allowed. + ///Use DigraphCopy() instead. + void operator=(const ListDigraph &) {} + public: + + typedef ExtendedListDigraphBase Parent; + + /// Constructor + + /// Constructor. + /// + ListDigraph() {} + + ///Add a new node to the digraph. + + /// \return the new node. + /// + Node addNode() { return Parent::addNode(); } + + ///Add a new arc to the digraph. + + ///Add a new arc to the digraph with source node \c s + ///and target node \c t. + ///\return the new arc. + Arc addArc(const Node& s, const Node& t) { + return Parent::addArc(s, t); + } + + /// Changes the target of \c e to \c n + + /// Changes the target of \c e to \c n + /// + ///\note The ArcIts and OutArcIts referencing + ///the changed arc remain valid. However InArcIts are + ///invalidated. + ///\warning This functionality cannot be used together with the Snapshot + ///feature. + void changeTarget(Arc e, Node n) { + Parent::changeTarget(e,n); + } + /// Changes the source of \c e to \c n + + /// Changes the source of \c e to \c n + /// + ///\note The ArcIts and InArcIts referencing + ///the changed arc remain valid. However OutArcIts are + ///invalidated. + ///\warning This functionality cannot be used together with the Snapshot + ///feature. + void changeSource(Arc e, Node n) { + Parent::changeSource(e,n); + } + + /// Invert the direction of an arc. + + ///\note The ArcIts referencing the changed arc remain + ///valid. However OutArcIts and InArcIts are + ///invalidated. + ///\warning This functionality cannot be used together with the Snapshot + ///feature. + void reverseArc(Arc e) { + Node t=target(e); + changeTarget(e,source(e)); + changeSource(e,t); + } + + /// Using this it is possible to avoid the superfluous memory + /// allocation: if you know that the digraph you want to build will + /// be very large (e.g. it will contain millions of nodes and/or arcs) + /// then it is worth reserving space for this amount before starting + /// to build the digraph. + /// \sa reserveArc + void reserveNode(int n) { nodes.reserve(n); }; + + /// \brief Using this it is possible to avoid the superfluous memory + /// allocation. + + /// Using this it is possible to avoid the superfluous memory + /// allocation: if you know that the digraph you want to build will + /// be very large (e.g. it will contain millions of nodes and/or arcs) + /// then it is worth reserving space for this amount before starting + /// to build the digraph. + /// \sa reserveNode + void reserveArc(int m) { arcs.reserve(m); }; + + ///Contract two nodes. + + ///This function contracts two nodes. + /// + ///Node \p b will be removed but instead of deleting + ///incident arcs, they will be joined to \p a. + ///The last parameter \p r controls whether to remove loops. \c true + ///means that loops will be removed. + /// + ///\note The ArcIts + ///referencing a moved arc remain + ///valid. However InArcIts and OutArcIts + ///may be invalidated. + ///\warning This functionality cannot be used together with the Snapshot + ///feature. + void contract(Node a, Node b, bool r = true) + { + for(OutArcIt e(*this,b);e!=INVALID;) { + OutArcIt f=e; + ++f; + if(r && target(e)==a) erase(e); + else changeSource(e,a); + e=f; + } + for(InArcIt e(*this,b);e!=INVALID;) { + InArcIt f=e; + ++f; + if(r && source(e)==a) erase(e); + else changeTarget(e,a); + e=f; + } + erase(b); + } + + ///Split a node. + + ///This function splits a node. First a new node is added to the digraph, + ///then the source of each outgoing arc of \c n is moved to this new node. + ///If \c connect is \c true (this is the default value), then a new arc + ///from \c n to the newly created node is also added. + ///\return The newly created node. + /// + ///\note The ArcIts referencing a moved arc remain + ///valid. However InArcIts and OutArcIts may + ///be invalidated. + /// + ///\warning This functionality cannot be used together with the + ///Snapshot feature. \todo It could be implemented in a bit + ///faster way. + Node split(Node n, bool connect = true) { + Node b = addNode(); + for(OutArcIt e(*this,n);e!=INVALID;) { + OutArcIt f=e; + ++f; + changeSource(e,b); + e=f; + } + if (connect) addArc(n,b); + return b; + } + + ///Split an arc. + + ///This function splits an arc. First a new node \c b is added to + ///the digraph, then the original arc is re-targeted to \c + ///b. Finally an arc from \c b to the original target is added. + ///\return The newly created node. + ///\warning This functionality + ///cannot be used together with the Snapshot feature. + Node split(Arc e) { + Node b = addNode(); + addArc(b,target(e)); + changeTarget(e,b); + return b; + } + + /// \brief Class to make a snapshot of the digraph and restore + /// to it later. + /// + /// Class to make a snapshot of the digraph and to restore it + /// later. + /// + /// The newly added nodes and arcs can be removed using the + /// restore() function. + /// + /// \warning Arc and node deletions cannot be restored. This + /// events invalidate the snapshot. + class Snapshot { + protected: + + typedef Parent::NodeNotifier NodeNotifier; + + class NodeObserverProxy : public NodeNotifier::ObserverBase { + public: + + NodeObserverProxy(Snapshot& _snapshot) + : snapshot(_snapshot) {} + + using NodeNotifier::ObserverBase::attach; + using NodeNotifier::ObserverBase::detach; + using NodeNotifier::ObserverBase::attached; + + protected: + + virtual void add(const Node& node) { + snapshot.addNode(node); + } + virtual void add(const std::vector& nodes) { + for (int i = nodes.size() - 1; i >= 0; ++i) { + snapshot.addNode(nodes[i]); + } + } + virtual void erase(const Node& node) { + snapshot.eraseNode(node); + } + virtual void erase(const std::vector& nodes) { + for (int i = 0; i < int(nodes.size()); ++i) { + snapshot.eraseNode(nodes[i]); + } + } + virtual void build() { + Node node; + std::vector nodes; + for (notifier()->first(node); node != INVALID; + notifier()->next(node)) { + nodes.push_back(node); + } + for (int i = nodes.size() - 1; i >= 0; --i) { + snapshot.addNode(nodes[i]); + } + } + virtual void clear() { + Node node; + for (notifier()->first(node); node != INVALID; + notifier()->next(node)) { + snapshot.eraseNode(node); + } + } + + Snapshot& snapshot; + }; + + class ArcObserverProxy : public ArcNotifier::ObserverBase { + public: + + ArcObserverProxy(Snapshot& _snapshot) + : snapshot(_snapshot) {} + + using ArcNotifier::ObserverBase::attach; + using ArcNotifier::ObserverBase::detach; + using ArcNotifier::ObserverBase::attached; + + protected: + + virtual void add(const Arc& arc) { + snapshot.addArc(arc); + } + virtual void add(const std::vector& arcs) { + for (int i = arcs.size() - 1; i >= 0; ++i) { + snapshot.addArc(arcs[i]); + } + } + virtual void erase(const Arc& arc) { + snapshot.eraseArc(arc); + } + virtual void erase(const std::vector& arcs) { + for (int i = 0; i < int(arcs.size()); ++i) { + snapshot.eraseArc(arcs[i]); + } + } + virtual void build() { + Arc arc; + std::vector arcs; + for (notifier()->first(arc); arc != INVALID; + notifier()->next(arc)) { + arcs.push_back(arc); + } + for (int i = arcs.size() - 1; i >= 0; --i) { + snapshot.addArc(arcs[i]); + } + } + virtual void clear() { + Arc arc; + for (notifier()->first(arc); arc != INVALID; + notifier()->next(arc)) { + snapshot.eraseArc(arc); + } + } + + Snapshot& snapshot; + }; + + ListDigraph *digraph; + + NodeObserverProxy node_observer_proxy; + ArcObserverProxy arc_observer_proxy; + + std::list added_nodes; + std::list added_arcs; + + + void addNode(const Node& node) { + added_nodes.push_front(node); + } + void eraseNode(const Node& node) { + std::list::iterator it = + std::find(added_nodes.begin(), added_nodes.end(), node); + if (it == added_nodes.end()) { + clear(); + arc_observer_proxy.detach(); + throw NodeNotifier::ImmediateDetach(); + } else { + added_nodes.erase(it); + } + } + + void addArc(const Arc& arc) { + added_arcs.push_front(arc); + } + void eraseArc(const Arc& arc) { + std::list::iterator it = + std::find(added_arcs.begin(), added_arcs.end(), arc); + if (it == added_arcs.end()) { + clear(); + node_observer_proxy.detach(); + throw ArcNotifier::ImmediateDetach(); + } else { + added_arcs.erase(it); + } + } + + void attach(ListDigraph &_digraph) { + digraph = &_digraph; + node_observer_proxy.attach(digraph->notifier(Node())); + arc_observer_proxy.attach(digraph->notifier(Arc())); + } + + void detach() { + node_observer_proxy.detach(); + arc_observer_proxy.detach(); + } + + bool attached() const { + return node_observer_proxy.attached(); + } + + void clear() { + added_nodes.clear(); + added_arcs.clear(); + } + + public: + + /// \brief Default constructor. + /// + /// Default constructor. + /// To actually make a snapshot you must call save(). + Snapshot() + : digraph(0), node_observer_proxy(*this), + arc_observer_proxy(*this) {} + + /// \brief Constructor that immediately makes a snapshot. + /// + /// This constructor immediately makes a snapshot of the digraph. + /// \param _digraph The digraph we make a snapshot of. + Snapshot(ListDigraph &_digraph) + : node_observer_proxy(*this), + arc_observer_proxy(*this) { + attach(_digraph); + } + + /// \brief Make a snapshot. + /// + /// Make a snapshot of the digraph. + /// + /// This function can be called more than once. In case of a repeated + /// call, the previous snapshot gets lost. + /// \param _digraph The digraph we make the snapshot of. + void save(ListDigraph &_digraph) { + if (attached()) { + detach(); + clear(); + } + attach(_digraph); + } + + /// \brief Undo the changes until the last snapshot. + // + /// Undo the changes until the last snapshot created by save(). + void restore() { + detach(); + for(std::list::iterator it = added_arcs.begin(); + it != added_arcs.end(); ++it) { + digraph->erase(*it); + } + for(std::list::iterator it = added_nodes.begin(); + it != added_nodes.end(); ++it) { + digraph->erase(*it); + } + clear(); + } + + /// \brief Gives back true when the snapshot is valid. + /// + /// Gives back true when the snapshot is valid. + bool valid() const { + return attached(); + } + }; + + }; + + ///@} + + class ListGraphBase { + + protected: + + struct NodeT { + int first_out; + int prev, next; + }; + + struct ArcT { + int target; + int prev_out, next_out; + }; + + std::vector nodes; + + int first_node; + + int first_free_node; + + std::vector arcs; + + int first_free_arc; + + public: + + typedef ListGraphBase Digraph; + + class Node; + class Arc; + class Edge; + + class Node { + friend class ListGraphBase; + protected: + + int id; + explicit Node(int pid) { id = pid;} + + 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;} + }; + + class Edge { + friend class ListGraphBase; + protected: + + int id; + explicit Edge(int pid) { id = pid;} + + public: + Edge() {} + Edge (Invalid) { id = -1; } + bool operator==(const Edge& arc) const {return id == arc.id;} + bool operator!=(const Edge& arc) const {return id != arc.id;} + bool operator<(const Edge& arc) const {return id < arc.id;} + }; + + class Arc { + friend class ListGraphBase; + protected: + + int id; + explicit Arc(int pid) { id = pid;} + + public: + operator Edge() const { return edgeFromId(id / 2); } + + Arc() {} + Arc (Invalid) { id = -1; } + bool operator==(const Arc& arc) const {return id == arc.id;} + bool operator!=(const Arc& arc) const {return id != arc.id;} + bool operator<(const Arc& arc) const {return id < arc.id;} + }; + + + + ListGraphBase() + : nodes(), first_node(-1), + first_free_node(-1), arcs(), first_free_arc(-1) {} + + + int maxNodeId() const { return nodes.size()-1; } + int maxEdgeId() const { return arcs.size() / 2 - 1; } + int maxArcId() const { return arcs.size()-1; } + + Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); } + Node target(Arc e) const { return Node(arcs[e.id].target); } + + Node u(Edge e) const { return Node(arcs[2 * e.id].target); } + Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); } + + static bool direction(Arc e) { + return (e.id & 1) == 1; + } + + static Arc direct(Edge e, bool d) { + return Arc(e.id * 2 + (d ? 1 : 0)); + } + + void first(Node& node) const { + node.id = first_node; + } + + void next(Node& node) const { + node.id = nodes[node.id].next; + } + + void first(Arc& e) const { + int n = first_node; + while (n != -1 && nodes[n].first_out == -1) { + n = nodes[n].next; + } + e.id = (n == -1) ? -1 : nodes[n].first_out; + } + + void next(Arc& e) const { + if (arcs[e.id].next_out != -1) { + e.id = arcs[e.id].next_out; + } else { + int n = nodes[arcs[e.id ^ 1].target].next; + while(n != -1 && nodes[n].first_out == -1) { + n = nodes[n].next; + } + e.id = (n == -1) ? -1 : nodes[n].first_out; + } + } + + void first(Edge& e) const { + int n = first_node; + while (n != -1) { + e.id = nodes[n].first_out; + while ((e.id & 1) != 1) { + e.id = arcs[e.id].next_out; + } + if (e.id != -1) { + e.id /= 2; + return; + } + n = nodes[n].next; + } + e.id = -1; + } + + void next(Edge& e) const { + int n = arcs[e.id * 2].target; + e.id = arcs[(e.id * 2) | 1].next_out; + while ((e.id & 1) != 1) { + e.id = arcs[e.id].next_out; + } + if (e.id != -1) { + e.id /= 2; + return; + } + n = nodes[n].next; + while (n != -1) { + e.id = nodes[n].first_out; + while ((e.id & 1) != 1) { + e.id = arcs[e.id].next_out; + } + if (e.id != -1) { + e.id /= 2; + return; + } + n = nodes[n].next; + } + e.id = -1; + } + + void firstOut(Arc &e, const Node& v) const { + e.id = nodes[v.id].first_out; + } + void nextOut(Arc &e) const { + e.id = arcs[e.id].next_out; + } + + void firstIn(Arc &e, const Node& v) const { + e.id = ((nodes[v.id].first_out) ^ 1); + if (e.id == -2) e.id = -1; + } + void nextIn(Arc &e) const { + e.id = ((arcs[e.id ^ 1].next_out) ^ 1); + if (e.id == -2) e.id = -1; + } + + void firstInc(Edge &e, bool& d, const Node& v) const { + int de = nodes[v.id].first_out; + if (de != -1 ) { + e.id = de / 2; + d = ((de & 1) == 1); + } else { + e.id = -1; + d = true; + } + } + void nextInc(Edge &e, bool& d) const { + int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); + if (de != -1 ) { + e.id = de / 2; + d = ((de & 1) == 1); + } else { + e.id = -1; + d = true; + } + } + + static int id(Node v) { return v.id; } + static int id(Arc e) { return e.id; } + static int id(Edge e) { return e.id; } + + static Node nodeFromId(int id) { return Node(id);} + static Arc arcFromId(int id) { return Arc(id);} + static Edge edgeFromId(int id) { return Edge(id);} + + 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_out = -1; + + return Node(n); + } + + Edge addEdge(Node u, Node v) { + int n; + + if (first_free_arc == -1) { + n = arcs.size(); + arcs.push_back(ArcT()); + arcs.push_back(ArcT()); + } else { + n = first_free_arc; + first_free_arc = arcs[n].next_out; + } + + arcs[n].target = u.id; + arcs[n | 1].target = v.id; + + arcs[n].next_out = nodes[v.id].first_out; + if (nodes[v.id].first_out != -1) { + arcs[nodes[v.id].first_out].prev_out = n; + } + arcs[n].prev_out = -1; + nodes[v.id].first_out = n; + + arcs[n | 1].next_out = nodes[u.id].first_out; + if (nodes[u.id].first_out != -1) { + arcs[nodes[u.id].first_out].prev_out = (n | 1); + } + arcs[n | 1].prev_out = -1; + nodes[u.id].first_out = (n | 1); + + return Edge(n / 2); + } + + 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; + + } + + void erase(const Edge& arc) { + int n = arc.id * 2; + + if (arcs[n].next_out != -1) { + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; + } + + if (arcs[n].prev_out != -1) { + arcs[arcs[n].prev_out].next_out = arcs[n].next_out; + } else { + nodes[arcs[n | 1].target].first_out = arcs[n].next_out; + } + + if (arcs[n | 1].next_out != -1) { + arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out; + } + + if (arcs[n | 1].prev_out != -1) { + arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out; + } else { + nodes[arcs[n].target].first_out = arcs[n | 1].next_out; + } + + arcs[n].next_out = first_free_arc; + first_free_arc = n; + + } + + void clear() { + arcs.clear(); + nodes.clear(); + first_node = first_free_node = first_free_arc = -1; + } + + protected: + + void changeTarget(Edge e, Node n) { + if(arcs[2 * e.id].next_out != -1) { + arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out; + } + if(arcs[2 * e.id].prev_out != -1) { + arcs[arcs[2 * e.id].prev_out].next_out = + arcs[2 * e.id].next_out; + } else { + nodes[arcs[(2 * e.id) | 1].target].first_out = + arcs[2 * e.id].next_out; + } + + if (nodes[n.id].first_out != -1) { + arcs[nodes[n.id].first_out].prev_out = 2 * e.id; + } + arcs[(2 * e.id) | 1].target = n.id; + arcs[2 * e.id].prev_out = -1; + arcs[2 * e.id].next_out = nodes[n.id].first_out; + nodes[n.id].first_out = 2 * e.id; + } + + void changeSource(Edge e, Node n) { + if(arcs[(2 * e.id) | 1].next_out != -1) { + arcs[arcs[(2 * e.id) | 1].next_out].prev_out = + arcs[(2 * e.id) | 1].prev_out; + } + if(arcs[(2 * e.id) | 1].prev_out != -1) { + arcs[arcs[(2 * e.id) | 1].prev_out].next_out = + arcs[(2 * e.id) | 1].next_out; + } else { + nodes[arcs[2 * e.id].target].first_out = + arcs[(2 * e.id) | 1].next_out; + } + + if (nodes[n.id].first_out != -1) { + arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); + } + arcs[2 * e.id].target = n.id; + arcs[(2 * e.id) | 1].prev_out = -1; + arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out; + nodes[n.id].first_out = ((2 * e.id) | 1); + } + + }; + +// typedef GraphExtender > +// ExtendedListGraphBase; + + typedef GraphExtender ExtendedListGraphBase; + + + + /// \addtogroup digraphs + /// @{ + + ///An undirected list digraph class. + + ///This is a simple and fast undirected digraph implementation. + /// + ///An important extra feature of this digraph implementation is that + ///its maps are real \ref concepts::ReferenceMap "reference map"s. + /// + ///It conforms to the + ///\ref concepts::Graph "Graph concept". + /// + ///\sa concepts::Graph. + /// + class ListGraph : public ExtendedListGraphBase { + private: + ///ListGraph is \e not copy constructible. Use GraphCopy() instead. + + ///ListGraph is \e not copy constructible. Use GraphCopy() instead. + /// + ListGraph(const ListGraph &) :ExtendedListGraphBase() {}; + ///\brief Assignment of ListGraph to another one is \e not allowed. + ///Use GraphCopy() instead. + + ///Assignment of ListGraph to another one is \e not allowed. + ///Use GraphCopy() instead. + void operator=(const ListGraph &) {} + public: + /// Constructor + + /// Constructor. + /// + ListGraph() {} + + typedef ExtendedListGraphBase Parent; + + typedef Parent::OutArcIt IncArcIt; + + /// \brief Add a new node to the digraph. + /// + /// \return the new node. + /// + Node addNode() { return Parent::addNode(); } + + /// \brief Add a new edge to the digraph. + /// + /// Add a new arc to the digraph with source node \c s + /// and target node \c t. + /// \return the new edge. + Edge addEdge(const Node& s, const Node& t) { + return Parent::addEdge(s, t); + } + /// \brief Changes the source of \c e to \c n + /// + /// Changes the source of \c e to \c n + /// + ///\note The ArcIts and InArcIts + ///referencing the changed arc remain + ///valid. However OutArcIts are invalidated. + void changeSource(Edge e, Node n) { + Parent::changeSource(e,n); + } + /// \brief Changes the target of \c e to \c n + /// + /// Changes the target of \c e to \c n + /// + /// \note The ArcIts referencing the changed arc remain + /// valid. However the other iterators may be invalidated. + void changeTarget(Edge e, Node n) { + Parent::changeTarget(e,n); + } + /// \brief Changes the source of \c e to \c n + /// + /// Changes the source of \c e to \c n. It changes the proper + /// node of the represented edge. + /// + ///\note The ArcIts and InArcIts + ///referencing the changed arc remain + ///valid. However OutArcIts are invalidated. + void changeSource(Arc e, Node n) { + if (Parent::direction(e)) { + Parent::changeSource(e,n); + } else { + Parent::changeTarget(e,n); + } + } + /// \brief Changes the target of \c e to \c n + /// + /// Changes the target of \c e to \c n. It changes the proper + /// node of the represented edge. + /// + ///\note The ArcIts and OutArcIts + ///referencing the changed arc remain + ///valid. However InArcIts are invalidated. + void changeTarget(Arc e, Node n) { + if (Parent::direction(e)) { + Parent::changeTarget(e,n); + } else { + Parent::changeSource(e,n); + } + } + /// \brief Contract two nodes. + /// + /// This function contracts two nodes. + /// + /// Node \p b will be removed but instead of deleting + /// its neighboring arcs, they will be joined to \p a. + /// The last parameter \p r controls whether to remove loops. \c true + /// means that loops will be removed. + /// + /// \note The ArcIts referencing a moved arc remain + /// valid. + void contract(Node a, Node b, bool r = true) { + for(IncArcIt e(*this, b); e!=INVALID;) { + IncArcIt f = e; ++f; + if (r && runningNode(e) == a) { + erase(e); + } else if (source(e) == b) { + changeSource(e, a); + } else { + changeTarget(e, a); + } + e = f; + } + erase(b); + } + + + /// \brief Class to make a snapshot of the digraph and restore + /// to it later. + /// + /// Class to make a snapshot of the digraph and to restore it + /// later. + /// + /// The newly added nodes and edges can be removed + /// using the restore() function. + /// + /// \warning Arc and node deletions cannot be restored. This + /// events invalidate the snapshot. + class Snapshot { + protected: + + typedef Parent::NodeNotifier NodeNotifier; + + class NodeObserverProxy : public NodeNotifier::ObserverBase { + public: + + NodeObserverProxy(Snapshot& _snapshot) + : snapshot(_snapshot) {} + + using NodeNotifier::ObserverBase::attach; + using NodeNotifier::ObserverBase::detach; + using NodeNotifier::ObserverBase::attached; + + protected: + + virtual void add(const Node& node) { + snapshot.addNode(node); + } + virtual void add(const std::vector& nodes) { + for (int i = nodes.size() - 1; i >= 0; ++i) { + snapshot.addNode(nodes[i]); + } + } + virtual void erase(const Node& node) { + snapshot.eraseNode(node); + } + virtual void erase(const std::vector& nodes) { + for (int i = 0; i < int(nodes.size()); ++i) { + snapshot.eraseNode(nodes[i]); + } + } + virtual void build() { + Node node; + std::vector nodes; + for (notifier()->first(node); node != INVALID; + notifier()->next(node)) { + nodes.push_back(node); + } + for (int i = nodes.size() - 1; i >= 0; --i) { + snapshot.addNode(nodes[i]); + } + } + virtual void clear() { + Node node; + for (notifier()->first(node); node != INVALID; + notifier()->next(node)) { + snapshot.eraseNode(node); + } + } + + Snapshot& snapshot; + }; + + class EdgeObserverProxy : public EdgeNotifier::ObserverBase { + public: + + EdgeObserverProxy(Snapshot& _snapshot) + : snapshot(_snapshot) {} + + using EdgeNotifier::ObserverBase::attach; + using EdgeNotifier::ObserverBase::detach; + using EdgeNotifier::ObserverBase::attached; + + protected: + + virtual void add(const Edge& arc) { + snapshot.addEdge(arc); + } + virtual void add(const std::vector& arcs) { + for (int i = arcs.size() - 1; i >= 0; ++i) { + snapshot.addEdge(arcs[i]); + } + } + virtual void erase(const Edge& arc) { + snapshot.eraseEdge(arc); + } + virtual void erase(const std::vector& arcs) { + for (int i = 0; i < int(arcs.size()); ++i) { + snapshot.eraseEdge(arcs[i]); + } + } + virtual void build() { + Edge arc; + std::vector arcs; + for (notifier()->first(arc); arc != INVALID; + notifier()->next(arc)) { + arcs.push_back(arc); + } + for (int i = arcs.size() - 1; i >= 0; --i) { + snapshot.addEdge(arcs[i]); + } + } + virtual void clear() { + Edge arc; + for (notifier()->first(arc); arc != INVALID; + notifier()->next(arc)) { + snapshot.eraseEdge(arc); + } + } + + Snapshot& snapshot; + }; + + ListGraph *digraph; + + NodeObserverProxy node_observer_proxy; + EdgeObserverProxy arc_observer_proxy; + + std::list added_nodes; + std::list added_arcs; + + + void addNode(const Node& node) { + added_nodes.push_front(node); + } + void eraseNode(const Node& node) { + std::list::iterator it = + std::find(added_nodes.begin(), added_nodes.end(), node); + if (it == added_nodes.end()) { + clear(); + arc_observer_proxy.detach(); + throw NodeNotifier::ImmediateDetach(); + } else { + added_nodes.erase(it); + } + } + + void addEdge(const Edge& arc) { + added_arcs.push_front(arc); + } + void eraseEdge(const Edge& arc) { + std::list::iterator it = + std::find(added_arcs.begin(), added_arcs.end(), arc); + if (it == added_arcs.end()) { + clear(); + node_observer_proxy.detach(); + throw EdgeNotifier::ImmediateDetach(); + } else { + added_arcs.erase(it); + } + } + + void attach(ListGraph &_digraph) { + digraph = &_digraph; + node_observer_proxy.attach(digraph->notifier(Node())); + arc_observer_proxy.attach(digraph->notifier(Edge())); + } + + void detach() { + node_observer_proxy.detach(); + arc_observer_proxy.detach(); + } + + bool attached() const { + return node_observer_proxy.attached(); + } + + void clear() { + added_nodes.clear(); + added_arcs.clear(); + } + + public: + + /// \brief Default constructor. + /// + /// Default constructor. + /// To actually make a snapshot you must call save(). + Snapshot() + : digraph(0), node_observer_proxy(*this), + arc_observer_proxy(*this) {} + + /// \brief Constructor that immediately makes a snapshot. + /// + /// This constructor immediately makes a snapshot of the digraph. + /// \param _digraph The digraph we make a snapshot of. + Snapshot(ListGraph &_digraph) + : node_observer_proxy(*this), + arc_observer_proxy(*this) { + attach(_digraph); + } + + /// \brief Make a snapshot. + /// + /// Make a snapshot of the digraph. + /// + /// This function can be called more than once. In case of a repeated + /// call, the previous snapshot gets lost. + /// \param _digraph The digraph we make the snapshot of. + void save(ListGraph &_digraph) { + if (attached()) { + detach(); + clear(); + } + attach(_digraph); + } + + /// \brief Undo the changes until the last snapshot. + // + /// Undo the changes until the last snapshot created by save(). + void restore() { + detach(); + for(std::list::iterator it = added_arcs.begin(); + it != added_arcs.end(); ++it) { + digraph->erase(*it); + } + for(std::list::iterator it = added_nodes.begin(); + it != added_nodes.end(); ++it) { + digraph->erase(*it); + } + clear(); + } + + /// \brief Gives back true when the snapshot is valid. + /// + /// Gives back true when the snapshot is valid. + bool valid() const { + return attached(); + } + }; + }; + + /// @} +} //namespace lemon + + +#endif diff --git a/test/Makefile.am b/test/Makefile.am --- a/test/Makefile.am +++ b/test/Makefile.am @@ -5,7 +5,9 @@ test/test_tools.h check_PROGRAMS += \ + test/digraph_test \ test/dim_test \ + test/graph_test \ test/random_test \ test/test_tools_fail \ test/test_tools_pass @@ -13,7 +15,9 @@ TESTS += $(check_PROGRAMS) XFAIL_TESTS += test/test_tools_fail$(EXEEXT) +test_digraph_test_SOURCES = test/digraph_test.cc test_dim_test_SOURCES = test/dim_test.cc +test_graph_test_SOURCES = test/graph_test.cc test_random_test_SOURCES = test/random_test.cc test_test_tools_fail_SOURCES = test/test_tools_fail.cc test_test_tools_pass_SOURCES = test/test_tools_pass.cc diff --git a/test/digraph_test.cc b/test/digraph_test.cc new file mode 100644 --- /dev/null +++ b/test/digraph_test.cc @@ -0,0 +1,82 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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 + +#include "test_tools.h" +#include "digraph_test.h" +#include "map_test.h" + + +using namespace lemon; +using namespace lemon::concepts; + + +int main() { + { // checking digraph components + checkConcept(); + + checkConcept, + IDableDigraphComponent<> >(); + + checkConcept, + IterableDigraphComponent<> >(); + + checkConcept, + MappableDigraphComponent<> >(); + + } + { // checking skeleton digraphs + checkConcept(); + } + { // checking list digraph + checkConcept(); + checkConcept, ListDigraph>(); + checkConcept, ListDigraph>(); + checkConcept, ListDigraph>(); + checkConcept, ListDigraph>(); + + checkDigraph(); + checkGraphNodeMap(); + checkGraphArcMap(); + } +// { // checking smart digraph +// checkConcept(); + +// checkDigraph(); +// checkDigraphNodeMap(); +// checkDigraphArcMap(); +// } +// { // checking full digraph +// checkConcept(); +// } +// { // checking full digraph +// checkConcept(); +// } + + std::cout << __FILE__ ": All tests passed.\n"; + + return 0; +} diff --git a/test/digraph_test.h b/test/digraph_test.h new file mode 100644 --- /dev/null +++ b/test/digraph_test.h @@ -0,0 +1,188 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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_TEST_H +#define LEMON_TEST_GRAPH_TEST_H + +//#include +#include "test_tools.h" + +//! \ingroup misc +//! \file +//! \brief Some utility and test cases to test digraph classes. +namespace lemon { + + ///Structure returned by \ref addPetersen(). + + ///Structure returned by \ref addPetersen(). + /// + template + struct PetStruct + { + ///Vector containing the outer nodes. + std::vector outer; + ///Vector containing the inner nodes. + std::vector inner; + ///Vector containing the edges of the inner circle. + std::vector incir; + ///Vector containing the edges of the outer circle. + std::vector outcir; + ///Vector containing the chord edges. + std::vector chords; + }; + + + + ///Adds a Petersen graph to \c G. + + ///Adds a Petersen graph to \c G. + ///\return The nodes and edges of the generated graph. + + template + PetStruct addPetersen(Digraph &G,int num = 5) + { + PetStruct n; + + for(int i=0;i + void bidirDigraph(Digraph &G) + { + typedef typename Digraph::Arc Arc; + typedef typename Digraph::ArcIt ArcIt; + + std::vector ee; + + for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e); + + for(typename std::vector::iterator p=ee.begin();p!=ee.end();p++) + G.addArc(G.target(*p),G.source(*p)); + } + + + /// \brief Checks the bidirectioned Petersen graph. + /// + /// Checks the bidirectioned Petersen graph. + /// + template + void checkBidirPetersen(Digraph &G, int num = 5) + { + typedef typename Digraph::Node Node; + + typedef typename Digraph::ArcIt ArcIt; + typedef typename Digraph::NodeIt NodeIt; + + checkDigraphNodeList(G, 2 * num); + checkDigraphArcList(G, 6 * num); + + for(NodeIt n(G);n!=INVALID;++n) { + checkDigraphInArcList(G, n, 3); + checkDigraphOutArcList(G, n, 3); + } + } + + template void checkDigraphNodeList(Digraph &G, int nn) + { + typename Digraph::NodeIt n(G); + for(int i=0;i + void checkDigraphArcList(Digraph &G, int nn) + { + typedef typename Digraph::ArcIt ArcIt; + + ArcIt e(G); + for(int i=0;i + void checkDigraphOutArcList(Digraph &G, typename Digraph::Node n, int nn) + { + typename Digraph::OutArcIt e(G,n); + for(int i=0;i void + checkDigraphInArcList(Digraph &G, typename Digraph::Node n, int nn) + { + typename Digraph::InArcIt e(G,n); + for(int i=0;i + void checkDigraph() { + const int num = 5; + Digraph G; + addPetersen(G, num); + bidirDigraph(G); + checkBidirPetersen(G, num); + } + + template + void checkDigraphIterators(const Digraph& digraph) { + typedef typename Digraph::Node Node; + typedef typename Digraph::NodeIt NodeIt; + typedef typename Digraph::Arc Arc; + typedef typename Digraph::ArcIt ArcIt; + typedef typename Digraph::InArcIt InArcIt; + typedef typename Digraph::OutArcIt OutArcIt; + // typedef ConArcIt ConArcIt; + } + + ///\file + ///\todo Check target(), source() as well; + + +} //namespace lemon + + +#endif diff --git a/test/graph_test.cc b/test/graph_test.cc new file mode 100644 --- /dev/null +++ b/test/graph_test.cc @@ -0,0 +1,207 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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" + + +using namespace lemon; +using namespace lemon::concepts; + +void check_concepts() { + + { // checking digraph components + checkConcept(); + + checkConcept, + IDableGraphComponent<> >(); + + checkConcept, + IterableGraphComponent<> >(); + + checkConcept, + MappableGraphComponent<> >(); + + } + { + checkConcept(); +// checkConcept(); +// checkConcept(); +// checkConcept(); +// checkConcept(); + } +} + +template +void check_item_counts(Graph &g, int n, int e) { + int nn = 0; + for (typename Graph::NodeIt it(g); it != INVALID; ++it) { + ++nn; + } + + check(nn == n, "Wrong node number."); + // check(countNodes(g) == n, "Wrong node number."); + + int ee = 0; + for (typename Graph::ArcIt it(g); it != INVALID; ++it) { + ++ee; + } + + check(ee == 2*e, "Wrong arc number."); + // check(countArcs(g) == 2*e, "Wrong arc number."); + + int uee = 0; + for (typename Graph::EdgeIt it(g); it != INVALID; ++it) { + ++uee; + } + + check(uee == e, "Wrong edge number."); + // check(countEdges(g) == e, "Wrong edge number."); +} + +template +void print_items(Graph &g) { + + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::ArcIt ArcIt; + + std::cout << "Nodes" << std::endl; + int i=0; + for(NodeIt it(g); it!=INVALID; ++it, ++i) { + std::cout << " " << i << ": " << g.id(it) << std::endl; + } + + std::cout << "Edge" << std::endl; + i=0; + for(EdgeIt it(g); it!=INVALID; ++it, ++i) { + std::cout << " " << i << ": " << g.id(it) + << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) + << ")" << std::endl; + } + + std::cout << "Arc" << std::endl; + i=0; + for(ArcIt it(g); it!=INVALID; ++it, ++i) { + std::cout << " " << i << ": " << g.id(it) + << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) + << ")" << std::endl; + } + +} + +template +void check_graph() { + + typedef typename Graph::Node Node; + typedef typename Graph::Edge Edge; + typedef typename Graph::Arc Arc; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::ArcIt ArcIt; + + Graph g; + + check_item_counts(g,0,0); + + Node + n1 = g.addNode(), + n2 = g.addNode(), + n3 = g.addNode(); + + Edge + e1 = g.addEdge(n1, n2), + e2 = g.addEdge(n2, n3); + + // print_items(g); + + check_item_counts(g,3,2); +} + +// void checkGridGraph(const GridGraph& g, int w, int h) { +// check(g.width() == w, "Wrong width"); +// check(g.height() == h, "Wrong height"); + +// for (int i = 0; i < w; ++i) { +// for (int j = 0; j < h; ++j) { +// check(g.col(g(i, j)) == i, "Wrong col"); +// check(g.row(g(i, j)) == j, "Wrong row"); +// } +// } + +// for (int i = 0; i < w; ++i) { +// for (int j = 0; j < h - 1; ++j) { +// check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); +// check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); +// } +// check(g.down(g(i, h - 1)) == INVALID, "Wrong down"); +// } + +// for (int i = 0; i < w; ++i) { +// for (int j = 1; j < h; ++j) { +// check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); +// check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up"); +// } +// check(g.up(g(i, 0)) == INVALID, "Wrong up"); +// } + +// for (int j = 0; j < h; ++j) { +// for (int i = 0; i < w - 1; ++i) { +// check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); +// check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); +// } +// check(g.right(g(w - 1, j)) == INVALID, "Wrong right"); +// } + +// for (int j = 0; j < h; ++j) { +// for (int i = 1; i < w; ++i) { +// check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); +// check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); +// } +// check(g.left(g(0, j)) == INVALID, "Wrong left"); +// } +// } + +int main() { + check_concepts(); + + check_graph(); +// check_graph(); + +// { +// FullGraph g(5); +// check_item_counts(g, 5, 10); +// } + +// { +// GridGraph g(5, 6); +// check_item_counts(g, 30, 49); +// checkGridGraph(g, 5, 6); +// } + + std::cout << __FILE__ ": All tests passed.\n"; + + return 0; +} diff --git a/test/map_test.h b/test/map_test.h new file mode 100644 --- /dev/null +++ b/test/map_test.h @@ -0,0 +1,149 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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 + +#include "test_tools.h" + + +//! \ingroup misc +//! \file +//! \brief Some utilities 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; + } + map = constMap(12); + for (int i = 0; i < int(nodes.size()); ++i) { + check(map[nodes[i]] == 12, "Wrong map constructor."); + } + graph.clear(); + nodes.clear(); + } + + template + void checkGraphArcMap() { + Graph graph; + const int num = 16; + + typedef typename Graph::Node Node; + typedef typename Graph::Arc Arc; + + 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.addArc(nodes[i], nodes[j])); + } + } + + typedef typename Graph::template ArcMap IntArcMap; + IntArcMap 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.addArc(nodes[i], nodes[j])); + map[edges.back()] = 23; + } + } + map = constMap(12); + for (int i = 0; i < int(edges.size()); ++i) { + check(map[edges[i]] == 12, "Wrong map constructor."); + } + graph.clear(); + edges.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; + } + } + map = constMap(12); + for (int i = 0; i < int(edges.size()); ++i) { + check(map[edges[i]] == 12, "Wrong map constructor."); + } + graph.clear(); + edges.clear(); + } + +} + +#endif