LEMON/LEMON-official Changeset - r107:31a2e6d28f61

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r107:31a2e6d28f61

« 106:9ba2d2

108:889d0c »

r107:31a2e6d28f61

Fri, 21 Mar 2008 23:25:40

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Happy New Year! (Update Copyright dates)

0 16 0

default

16 files changed with 16 insertions and 16 deletions:

LICENSE

lemon/bits/alteration_notifier.h

lemon/bits/array_map.h

lemon/bits/base_extender.h

lemon/bits/default_map.h

lemon/bits/graph_extender.h

lemon/bits/map_extender.h

lemon/bits/traits.h

lemon/bits/vector_map.h

lemon/concepts/digraph.h

lemon/concepts/graph.h

lemon/concepts/graph_components.h

test/digraph_test.cc

test/digraph_test.h

test/graph_test.cc

test/map_test.h

↑ Collapse diff ↑

LICENSE

Show inline comments

 		LEMON code without an explicit copyright is covered by the following
 		copyright/license.
-		Copyright (C) 2003-2007 Egervary Jeno Kombinatorikus Optimalizalasi
+		Copyright (C) 2003-2008 Egervary Jeno Kombinatorikus Optimalizalasi
 		Kutatocsoport (Egervary Combinatorial Optimization Research Group,
 		EGRES).
 		Permission is hereby granted, free of charge, to any person or organization
 		obtaining a copy of the software and accompanying documentation covered by
 		this license (the "Software") to use, reproduce, display, distribute,
 		execute, and transmit the Software, and to prepare derivative works of the
 		Software, and to permit third-parties to whom the Software is furnished to
 		do so, all subject to the following:
 		The copyright notices in the Software and this entire statement, including
 		the above license grant, this restriction and the following disclaimer,
 		must be included in all copies of the Software, in whole or in part, and
 		all derivative works of the Software, unless such copies or derivative
 		works are solely in the form of machine-executable object code generated by
 		a source language processor.
 		THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 		IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 		FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
 		SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
 		FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
 		ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 		DEALINGS IN THE SOFTWARE.
 		===========================================================================
 		This license is a verbatim copy of the Boost Software License, Version 1.0.

lemon/bits/alteration_notifier.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <vector>
 		#include <list>
 		#include <lemon/bits/utility.h>
 		///\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 <typename _Container, typename _Item>
 		  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*>(_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<ObserverBase*>::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<Item>& 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<Item>& 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<ObserverBase*> 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<Item>& 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<Item>& 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

lemon/bits/array_map.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <memory>
 		#include <lemon/bits/traits.h>
 		#include <lemon/bits/alteration_notifier.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		/// \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 <typename _Graph, typename _Item, typename _Value>
 		  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<Value> 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=<ArrayMap>(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 <typename CMap>
 		    ArrayMap& operator=(const CMap& cmap) {
 		      checkConcept<concepts::ReadMap<Key, _Value>, 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<Key>& 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<Key>& 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

lemon/bits/base_extender.h

Show inline comments

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * Copyright (C) 2003-2008
 * 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 <lemon/bits/invalid.h>
#include <lemon/error.h>

#include <lemon/bits/map_extender.h>
#include <lemon/bits/default_map.h>

#include <lemon/concept_check.h>
#include <lemon/concepts/maps.h>

///\ingroup digraphbits
///\file
///\brief Extenders for the digraph types
namespace lemon {

  /// \ingroup digraphbits
  ///
  /// \brief BaseDigraph to BaseGraph extender
  template <typename Base>
  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<that.forward ||
	  (!(that.forward<forward) && Edge(*this)<Edge(that));
      }
    };



    using Parent::source;

    /// Source of the given Arc.
    Node source(const Arc &e) const {
      return e.forward ? Parent::source(e) : Parent::target(e);
    }

    using Parent::target;

    /// Target of the given Arc.
    Node target(const Arc &e) const {
      return e.forward ? Parent::target(e) : Parent::source(e);
    }

    /// \brief Directed arc from an edge.
    ///
    /// Returns a directed arc corresponding to the specified Edge.
    /// If the given bool is true the given edge and the
    /// returned arc have the same source node.
    static Arc direct(const Edge &ue, bool d) {
      return Arc(ue, d);
    }

    /// Returns whether the given directed arc is same orientation as the
    /// corresponding edge.
    ///
    /// \todo reference to the corresponding point of the undirected digraph
    /// concept. "What does the direction of an edge mean?"
    static bool direction(const Arc &e) { return e.forward; }


    using Parent::first;
    using Parent::next;

    void first(Arc &e) const {
      Parent::first(e);
      e.forward=true;
    }

    void next(Arc &e) const {
      if( e.forward ) {
	e.forward = false;
      }
      else {
	Parent::next(e);
	e.forward = true;
      }
    }

    void firstOut(Arc &e, const Node &n) const {
      Parent::firstIn(e,n);
      if( Edge(e) != INVALID ) {
	e.forward = false;
      }
      else {
	Parent::firstOut(e,n);
	e.forward = true;
      }
    }
    void nextOut(Arc &e) const {
      if( ! e.forward ) {
	Node n = Parent::target(e);
	Parent::nextIn(e);
	if( Edge(e) == INVALID ) {
	  Parent::firstOut(e, n);
	  e.forward = true;
	}
      }
      else {
	Parent::nextOut(e);
      }
    }

    void firstIn(Arc &e, const Node &n) const {
      Parent::firstOut(e,n);
      if( Edge(e) != INVALID ) {
	e.forward = false;
      }
      else {
	Parent::firstIn(e,n);
	e.forward = true;
      }
    }
    void nextIn(Arc &e) const {
      if( ! e.forward ) {
	Node n = Parent::source(e);
	Parent::nextOut(e);
	if( Edge(e) == INVALID ) {
	  Parent::firstIn(e, n);
	  e.forward = true;
	}
      }
      else {
	Parent::nextIn(e);
      }
    }

    void firstInc(Edge &e, bool &d, const Node &n) const {
      d = true;
      Parent::firstOut(e, n);
      if (e != INVALID) return;
      d = false;
      Parent::firstIn(e, n);
    }

    void nextInc(Edge &e, bool &d) const {
      if (d) {
	Node s = Parent::source(e);
	Parent::nextOut(e);
	if (e != INVALID) return;
	d = false;
	Parent::firstIn(e, s);
      } else {
	Parent::nextIn(e);
      }
    }

    Node nodeFromId(int ix) const {
      return Parent::nodeFromId(ix);
    }

    Arc arcFromId(int ix) const {
      return direct(Parent::arcFromId(ix >> 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 <typename Base>
  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&>(node));
    }
    void next(Red& node) const {
      Parent::nextRed(static_cast<Node&>(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&>(node));
    }
    void next(Blue& node) const {
      Parent::nextBlue(static_cast<Node&>(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<Edge&>(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<forward) && Edge(*this)<Edge(i));
      }
    };

    void first(Arc& arc) const {
      Parent::first(static_cast<Edge&>(arc));
      arc.forward = true;
    }

    void next(Arc& arc) const {
      if (!arc.forward) {
	Parent::next(static_cast<Edge&>(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<Edge&>(arc) == INVALID;
      }
    }
    void nextOut(Arc& arc) const {
      if (arc.forward) {
	Parent::nextFromRed(arc);
      } else {
	Parent::nextFromBlue(arc);
        arc.forward = static_cast<Edge&>(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<Edge&>(arc) == INVALID;
      }
    }
    void nextIn(Arc& arc) const {
      if (arc.forward) {
	Parent::nextFromBlue(arc);
      } else {
	Parent::nextFromRed(arc);
	arc.forward = static_cast<Edge&>(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<const Edge&>(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

lemon/bits/default_map.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <lemon/bits/array_map.h>
 		#include <lemon/bits/vector_map.h>
 		//#include <lemon/bits/debug_map.h>
 		///\ingroup graphbits
 		///\file
 		///\brief Graph maps that construct and destruct their elements dynamically.
 		namespace lemon {
 		  //#ifndef LEMON_USE_DEBUG_MAP
 		  template <typename _Graph, typename _Item, typename _Value>
 		  struct DefaultMapSelector {
 		    typedef ArrayMap<_Graph, _Item, _Value> Map;
 		  };
 		  // bool
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, bool> {
 		    typedef VectorMap<_Graph, _Item, bool> Map;
 		  };
 		  // char
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, char> {
 		    typedef VectorMap<_Graph, _Item, char> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, signed char> {
 		    typedef VectorMap<_Graph, _Item, signed char> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, unsigned char> {
 		    typedef VectorMap<_Graph, _Item, unsigned char> Map;
 		  };
 		  // int
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, signed int> {
 		    typedef VectorMap<_Graph, _Item, signed int> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, unsigned int> {
 		    typedef VectorMap<_Graph, _Item, unsigned int> Map;
 		  };
 		  // short
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, signed short> {
 		    typedef VectorMap<_Graph, _Item, signed short> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, unsigned short> {
 		    typedef VectorMap<_Graph, _Item, unsigned short> Map;
 		  };
 		  // long
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, signed long> {
 		    typedef VectorMap<_Graph, _Item, signed long> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, unsigned long> {
 		    typedef VectorMap<_Graph, _Item, unsigned long> Map;
 		  };
 		#if defined __GNUC__ && !defined __STRICT_ANSI__
 		  // long long
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, signed long long> {
 		    typedef VectorMap<_Graph, _Item, signed long long> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, unsigned long long> {
 		    typedef VectorMap<_Graph, _Item, unsigned long long> Map;
 		  };
 		#endif
 		  // float
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, float> {
 		    typedef VectorMap<_Graph, _Item, float> Map;
 		  };
 		  // double
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, double> {
 		    typedef VectorMap<_Graph, _Item,  double> Map;
 		  };
 		  // long double
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, long double> {
 		    typedef VectorMap<_Graph, _Item, long double> Map;
 		  };
 		  // pointer
 		  template <typename _Graph, typename _Item, typename _Ptr>
 		  struct DefaultMapSelector<_Graph, _Item, _Ptr*> {
 		    typedef VectorMap<_Graph, _Item, _Ptr*> Map;
 		  };
 		// #else
 		//   template <typename _Graph, typename _Item, typename _Value>
 		//   struct DefaultMapSelector {
 		//     typedef DebugMap<_Graph, _Item, _Value> Map;
 		//   };
 		// #endif
 		  /// \e
 		  template <typename _Graph, typename _Item, typename _Value>
 		  class DefaultMap
 		    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
 		  public:
 		    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
 		    typedef DefaultMap<_Graph, _Item, _Value> Map;
 		    typedef typename Parent::Graph Graph;
 		    typedef typename Parent::Value Value;
 		    explicit DefaultMap(const Graph& graph) : Parent(graph) {}
 		    DefaultMap(const Graph& graph, const Value& value)
 		      : Parent(graph, value) {}
 		    DefaultMap& operator=(const DefaultMap& cmap) {
 		      return operator=<DefaultMap>(cmap);
+		    }
 		    template <typename CMap>
 		    DefaultMap& operator=(const CMap& cmap) {
 		      Parent::operator=(cmap);
 		      return *this;
+		    }
 		  };
+		}
 		#endif

lemon/bits/graph_extender.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <lemon/bits/invalid.h>
 		#include <lemon/bits/utility.h>
 		#include <lemon/bits/map_extender.h>
 		#include <lemon/bits/default_map.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		///\ingroup graphbits
 		///\file
 		///\brief Extenders for the digraph types
 		namespace lemon {
 		  /// \ingroup graphbits
 		  ///
 		  /// \brief Extender for the Digraphs
 		  template <typename Base>
 		  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 &node, const Arc &arc) const {
 		      if (node == Parent::source(arc))
 			return Parent::target(arc);
 		      else if(node == Parent::target(arc))
 			return Parent::source(arc);
 		      else
 			return INVALID;
+		    }
 		    // Alterable extension
 		    typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
 		    typedef AlterationNotifier<DigraphExtender, Arc> 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<Node&>(*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<Arc&>(*this));
+		      }
 		      ArcIt(const Digraph& digraph, const Arc& arc) :
 			Arc(arc), _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 &arc) const {
 		      return Parent::source(arc);
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (i.e. the target in this case) of the
 		    /// iterator
 		    Node runningNode(const OutArcIt &arc) const {
 		      return Parent::target(arc);
+		    }
 		    /// \brief Base node of the iterator
 		    ///
 		    /// Returns the base node (i.e. the target in this case) of the iterator
 		    Node baseNode(const InArcIt &arc) const {
 		      return Parent::target(arc);
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (i.e. the source in this case) of the
 		    /// iterator
 		    Node runningNode(const InArcIt &arc) const {
 		      return Parent::source(arc);
+		    }
 		    template <typename _Value>
 		    class NodeMap
 		      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
 		    public:
 		      typedef DigraphExtender Digraph;
 		      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > 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=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
 		    public:
 		      typedef DigraphExtender Digraph;
 		      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > 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=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      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 <typename Digraph, typename NodeRefMap, typename ArcRefMap>
 		    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 <typename Base>
 		  class GraphExtender : public Base {
 		  public:
 		    typedef Base Parent;
 		    typedef GraphExtender Graph;
 		    typedef True UndirectedTag;
 		    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 &arc) const {
 		      return Parent::direct(arc, !Parent::direction(arc));
+		    }
 		    using Parent::direct;
 		    Arc direct(const Edge &edge, const Node &node) const {
 		      return Parent::direct(edge, Parent::source(edge) == node);
+		    }
 		    // Alterable extension
 		    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
 		    typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
 		    typedef AlterationNotifier<GraphExtender, Edge> 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 Graph* _graph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Graph& graph) : _graph(&graph) {
 			_graph->first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Graph& graph, const Node& node)
 			: Node(node), _graph(&graph) {}
 		      NodeIt& operator++() {
 			_graph->next(*this);
 			return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Graph* _graph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Graph& graph) : _graph(&graph) {
 			_graph->first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Graph& graph, const Arc& arc) :
 			Arc(arc), _graph(&graph) { }
 		      ArcIt& operator++() {
 			_graph->next(*this);
 			return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Graph* _graph;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Graph& graph, const Node& node)
 			: _graph(&graph) {
 			_graph->firstOut(*this, node);
+		      }
 		      OutArcIt(const Graph& graph, const Arc& arc)
 			: Arc(arc), _graph(&graph) {}
 		      OutArcIt& operator++() {
 			_graph->nextOut(*this);
 			return *this;
+		      }
 		    };
 		    class InArcIt : public Arc {
 		      const Graph* _graph;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Graph& graph, const Node& node)
 			: _graph(&graph) {
 			_graph->firstIn(*this, node);
+		      }
 		      InArcIt(const Graph& graph, const Arc& arc) :
 			Arc(arc), _graph(&graph) {}
 		      InArcIt& operator++() {
 			_graph->nextIn(*this);
 			return *this;
+		      }
 		    };
 		    class EdgeIt : public Parent::Edge {
 		      const Graph* _graph;
 		    public:
 		      EdgeIt() { }
 		      EdgeIt(Invalid i) : Edge(i) { }
 		      explicit EdgeIt(const Graph& graph) : _graph(&graph) {
 			_graph->first(static_cast<Edge&>(*this));
+		      }
 		      EdgeIt(const Graph& graph, const Edge& edge) :
 			Edge(edge), _graph(&graph) { }
 		      EdgeIt& operator++() {
 			_graph->next(*this);
 			return *this;
+		      }
 		    };
 		    class IncEdgeIt : public Parent::Edge {
 		      friend class GraphExtender;
 		      const Graph* _graph;
 		      bool _direction;
 		    public:
 		      IncEdgeIt() { }
 		      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
 		      IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
 			_graph->firstInc(*this, _direction, node);
+		      }
 		      IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
 			: _graph(&graph), Edge(edge) {
 			_direction = (_graph->source(edge) == node);
+		      }
 		      IncEdgeIt& operator++() {
 			_graph->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 &arc) const {
 		      return Parent::source(static_cast<const Arc&>(arc));
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the target in this case) of the
 		    /// iterator
 		    Node runningNode(const OutArcIt &arc) const {
 		      return Parent::target(static_cast<const Arc&>(arc));
+		    }
 		    /// \brief Base node of the iterator
 		    ///
 		    /// Returns the base node (ie. the target in this case) of the iterator
 		    Node baseNode(const InArcIt &arc) const {
 		      return Parent::target(static_cast<const Arc&>(arc));
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the source in this case) of the
 		    /// iterator
 		    Node runningNode(const InArcIt &arc) const {
 		      return Parent::source(static_cast<const Arc&>(arc));
+		    }
 		    /// Base node of the iterator
 		    ///
 		    /// Returns the base node of the iterator
 		    Node baseNode(const IncEdgeIt &edge) const {
 		      return edge._direction ? source(edge) : target(edge);
+		    }
 		    /// Running node of the iterator
 		    ///
 		    /// Returns the running node of the iterator
 		    Node runningNode(const IncEdgeIt &edge) const {
 		      return edge._direction ? target(edge) : source(edge);
+		    }
 		    // Mappable extension
 		    template <typename _Value>
 		    class NodeMap
 		      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
 		    public:
 		      typedef GraphExtender Graph;
 		      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
 		      NodeMap(const Graph& graph)
 			: Parent(graph) {}
 		      NodeMap(const Graph& graph, const _Value& value)
 			: Parent(graph, value) {}
 		      NodeMap& operator=(const NodeMap& cmap) {
 			return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
 		    public:
 		      typedef GraphExtender Graph;
 		      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
 		      ArcMap(const Graph& graph)
 			: Parent(graph) {}
 		      ArcMap(const Graph& graph, const _Value& value)
 			: Parent(graph, value) {}
 		      ArcMap& operator=(const ArcMap& cmap) {
 			return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap
 		      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
 		    public:
 		      typedef GraphExtender Graph;
 		      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
 		      EdgeMap(const Graph& graph)
 			: Parent(graph) {}
 		      EdgeMap(const Graph& graph, const _Value& value)
 			: Parent(graph, value) {}
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 			return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      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<Arc> 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 <typename Graph, typename NodeRefMap, typename EdgeRefMap>
 		    void build(const Graph& graph, NodeRefMap& nodeRef,
 		               EdgeRefMap& edgeRef) {
 		      Parent::build(graph, 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<Arc> av;
 		      av.push_back(Parent::direct(edge, true));
 		      av.push_back(Parent::direct(edge, false));
 		      notifier(Arc()).erase(av);
 		      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

lemon/bits/map_extender.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <iterator>
 		#include <lemon/bits/traits.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		///\file
 		///\brief Extenders for iterable maps.
 		namespace lemon {
 		  /// \ingroup graphbits
 		  ///
 		  /// \brief Extender for maps
 		  template <typename _Map>
 		  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=<MapExtender>(cmap);
+		    }
 		    template <typename CMap>
 		    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<Map>::ConstReturnValue operator*() const {
 			return map[*this];
+		      }
 		      typename MapTraits<Map>::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<Map>::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 <typename _Graph, typename _Map>
 		  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=<MapExtender>(cmap);
+		    }
 		    template <typename CMap>
 		    SubMapExtender& operator=(const CMap& cmap) {
 		      checkConcept<concepts::ReadMap<Key, Value>, 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<Map>::ConstReturnValue operator*() const {
 			return map[*this];
+		      }
 		      typename MapTraits<Map>::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<Map>::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

lemon/bits/traits.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <lemon/bits/utility.h>
 		///\file
 		///\brief Traits for graphs and maps
 		///
 		namespace lemon {
 		  template <typename _Graph, typename _Item>
 		  class ItemSetTraits {};
 		  template <typename Graph, typename Enable = void>
 		  struct NodeNotifierIndicator {
 		    typedef InvalidType Type;
 		  };
 		  template <typename Graph>
 		  struct NodeNotifierIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type
 		  > {
 		    typedef typename Graph::NodeNotifier Type;
 		  };
 		  template <typename _Graph>
 		  class ItemSetTraits<_Graph, typename _Graph::Node> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Node Item;
 		    typedef typename Graph::NodeIt ItemIt;
 		    typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;
 		    template <typename _Value>
 		    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 <typename Graph, typename Enable = void>
 		  struct ArcNotifierIndicator {
 		    typedef InvalidType Type;
 		  };
 		  template <typename Graph>
 		  struct ArcNotifierIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type
 		  > {
 		    typedef typename Graph::ArcNotifier Type;
 		  };
 		  template <typename _Graph>
 		  class ItemSetTraits<_Graph, typename _Graph::Arc> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Arc Item;
 		    typedef typename Graph::ArcIt ItemIt;
 		    typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;
 		    template <typename _Value>
 		    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 <typename Graph, typename Enable = void>
 		  struct EdgeNotifierIndicator {
 		    typedef InvalidType Type;
 		  };
 		  template <typename Graph>
 		  struct EdgeNotifierIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type
 		  > {
 		    typedef typename Graph::EdgeNotifier Type;
 		  };
 		  template <typename _Graph>
 		  class ItemSetTraits<_Graph, typename _Graph::Edge> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Edge Item;
 		    typedef typename Graph::EdgeIt ItemIt;
 		    typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;
 		    template <typename _Value>
 		    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 <typename Map, typename Enable = void>
 		  struct MapTraits {
 		    typedef False ReferenceMapTag;
 		    typedef typename Map::Key Key;
 		    typedef typename Map::Value Value;
 		    typedef const Value ConstReturnValue;
 		    typedef const Value ReturnValue;
 		  };
 		  template <typename Map>
 		  struct MapTraits<
 		    Map, typename enable_if<typename Map::ReferenceMapTag, void>::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 <typename MatrixMap, typename Enable = void>
 		  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 <typename MatrixMap>
 		  struct MatrixMapTraits<
 		    MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag,
 		                                  void>::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 <typename Graph, typename Enable = void>
 		  struct NodeNumTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct NodeNumTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::NodeNumTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct ArcNumTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct ArcNumTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::ArcNumTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct FindArcTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct FindArcTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::FindArcTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct UndirectedTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct UndirectedTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::UndirectedTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct BuildTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct BuildTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::BuildTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
+		}
 		#endif

lemon/bits/vector_map.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <vector>
 		#include <algorithm>
 		#include <lemon/bits/traits.h>
 		#include <lemon/bits/utility.h>
 		#include <lemon/bits/alteration_notifier.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		///\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 <typename _Graph, typename _Item, typename _Value>
 		  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=<VectorMap>(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 <typename CMap>
 		    VectorMap& operator=(const CMap& cmap) {
 		      checkConcept<concepts::ReadMap<Key, _Value>, 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<Key>& 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<Key>& 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

lemon/concepts/digraph.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <lemon/bits/invalid.h>
 		#include <lemon/bits/utility.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/graph_components.h>
 		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; }
 		      /// \brief Returns the ID of the node.
 		      int id(Node) const { return -1; }
 		      /// \brief Returns the ID of the arc.
 		      int id(Arc) const { return -1; }
 		      /// \brief Returns the node with the given ID.
 		      ///
 		      /// \pre The argument should be a valid node ID in the graph.
 		      Node nodeFromId(int) const { return INVALID; }
 		      /// \brief Returns the arc with the given ID.
 		      ///
 		      /// \pre The argument should be a valid arc ID in the graph.
 		      Arc arcFromId(int) const { return INVALID; }
 		      /// \brief Returns an upper bound on the node IDs.
 		      int maxNodeId() const { return -1; }
 		      /// \brief Returns an upper bound on the arc IDs.
 		      int maxArcId() const { return -1; }
 		      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 {}
 		      // The second parameter is dummy.
 		      Node fromId(int, Node) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Arc fromId(int, Arc) const { return INVALID; }
 		      // Dummy parameter.
 		      int maxId(Node) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Arc) const { return -1; }
 		      /// \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 T>
 		      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 <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, 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 T>
 		      class ArcMap : public ReadWriteMap<Arc,T> {
 		      public:
 		        ///\e
 		        ArcMap(const Digraph&) { }
 		        ///\e
 		        ArcMap(const Digraph&, T) { }
 		        ///Copy constructor
 		        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      template <typename RDigraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<IterableDigraphComponent<>, Digraph>();
 			  checkConcept<IDableDigraphComponent<>, Digraph>();
 		          checkConcept<MappableDigraphComponent<>, Digraph>();
+		        }
 		      };
 		    };
 		  } //namespace concepts
 		} //namespace lemon
 		#endif // LEMON_CONCEPT_DIGRAPH_H

lemon/concepts/graph.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <lemon/concepts/graph_components.h>
 		#include <lemon/concepts/graph.h>
 		#include <lemon/bits/utility.h>
 		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 IncEdgeIt 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::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class IncEdgeIt : public Edge {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        IncEdgeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        IncEdgeIt(Invalid) { }
 		        /// This constructor sets the iterator to first incident arc.
 		        /// This constructor set the iterator to the first incident arc of
 		        /// the node.
 		        IncEdgeIt(const Graph&, const Node&) { }
 		        /// Edge -> IncEdgeIt 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.
 		        IncEdgeIt(const Graph&, const Edge&) { }
 		        /// Next incident arc
 		        /// Assign the iterator to the next incident arc
 			/// of the corresponding node.
 		        IncEdgeIt& 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 T>
 		      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 <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, 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 T>
 		      class ArcMap : public ReadWriteMap<Arc,T>
+		      {
 		      public:
 		        ///\e
 		        ArcMap(const Graph&) { }
 		        ///\e
 		        ArcMap(const Graph&, T) { }
 		        ///Copy constructor
 		        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, T>, 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 T>
 		      class EdgeMap : public ReadWriteMap<Edge,T>
+		      {
 		      public:
 		        ///\e
 		        EdgeMap(const Graph&) { }
 		        ///\e
 		        EdgeMap(const Graph&, T) { }
 		        ///Copy constructor
 		        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
 		        ///Assignment operator
 		        template <typename CMap>
 		        EdgeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Edge, T>, 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; }
 		      /// \brief Returns the id of the node.
 		      int id(Node) const { return -1; }
 		      /// \brief Returns the id of the edge.
 		      int id(Edge) const { return -1; }
 		      /// \brief Returns the id of the arc.
 		      int id(Arc) const { return -1; }
 		      /// \brief Returns the node with the given id.
 		      ///
 		      /// \pre The argument should be a valid node id in the graph.
 		      Node nodeFromId(int) const { return INVALID; }
 		      /// \brief Returns the edge with the given id.
 		      ///
 		      /// \pre The argument should be a valid edge id in the graph.
 		      Edge edgeFromId(int) const { return INVALID; }
 		      /// \brief Returns the arc with the given id.
 		      ///
 		      /// \pre The argument should be a valid arc id in the graph.
 		      Arc arcFromId(int) const { return INVALID; }
 		      /// \brief Returns an upper bound on the node IDs.
 		      int maxNodeId() const { return -1; }
 		      /// \brief Returns an upper bound on the edge IDs.
 		      int maxEdgeId() const { return -1; }
 		      /// \brief Returns an upper bound on the arc IDs.
 		      int maxArcId() const { return -1; }
 		      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 {}
 		      // The second parameter is dummy.
 		      Node fromId(int, Node) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Edge fromId(int, Edge) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Arc fromId(int, Arc) const { return INVALID; }
 		      // Dummy parameter.
 		      int maxId(Node) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Edge) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Arc) const { return -1; }
 		      /// \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(IncEdgeIt) const {
 			return INVALID;
+		      }
 		      /// \brief Running node of the iterator
 		      ///
 		      /// Returns the running node of the iterator
 		      Node runningNode(IncEdgeIt) const {
 			return INVALID;
+		      }
 		      template <typename Graph>
 		      struct Constraints {
 			void constraints() {
 			  checkConcept<IterableGraphComponent<>, Graph>();
 			  checkConcept<IDableGraphComponent<>, Graph>();
 			  checkConcept<MappableGraphComponent<>, Graph>();
+			}
 		      };
 		    };
+		  }
+		}
 		#endif

lemon/concepts/graph_components.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <lemon/bits/invalid.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/bits/alteration_notifier.h>
 		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 <char _selector = '0'>
 		#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<typename _GraphItem>
 		      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 <typename _Digraph>
 		      struct Constraints {
 			typedef typename _Digraph::Node Node;
 			typedef typename _Digraph::Arc Arc;
 			void constraints() {
 			  checkConcept<GraphItem<'n'>, Node>();
 			  checkConcept<GraphItem<'a'>, 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 <typename _Graph>
 		      struct Constraints {
 			typedef typename _Graph::Node Node;
 			typedef typename _Graph::Arc Arc;
 			typedef typename _Graph::Edge Edge;
 			void constraints() {
 		          checkConcept<BaseDigraphComponent, _Graph>();
 			  checkConcept<GraphItem<'u'>, 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 <typename _Base = BaseDigraphComponent>
 		    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 <typename _Digraph>
 		      struct Constraints {
 			void constraints() {
 			  checkConcept<Base, _Digraph >();
 			  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 <typename _Base = BaseGraphComponent>
 		    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 <typename _Graph>
 		      struct Constraints {
 			void constraints() {
 			  checkConcept<Base, _Graph >();
 			  checkConcept<IDableDigraphComponent<Base>, _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 <typename _Graph, typename _Item>
 		    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<typename _GraphItemIt>
 		      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 <typename _Graph,
 			      typename _Item = typename _Graph::Arc,
 		              typename _Base = typename _Graph::Node,
 			      char _selector = '0'>
 		    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 <typename _GraphIncIt>
 		      struct Constraints {
 			void constraints() {
 			  checkConcept<GraphItem<_selector>, _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 <typename _Base = BaseDigraphComponent>
 		    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<Digraph, Node> NodeIt;
 		      /// \brief This iterator goes through each node.
 		      ///
 		      /// This iterator goes through each node.
 		      ///
 		      typedef GraphItemIt<Digraph, Arc> 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<Digraph, Arc, Node, 'i'> 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<Digraph, Arc, Node, 'o'> 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 <typename _Digraph>
 		      struct Constraints {
 			void constraints() {
 			  checkConcept<Base, _Digraph>();
+		          {
 		            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<GraphItemIt<_Digraph, typename _Digraph::Arc>,
 		              typename _Digraph::ArcIt >();
 		            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
 		              typename _Digraph::NodeIt >();
 		            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
 		              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
 		            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
 		              typename _Digraph::Node, 'o'>, 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 <typename _Base = BaseGraphComponent>
 		    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

test/digraph_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <iostream>
 		#include <vector>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/list_graph.h>
 		//#include <lemon/smart_graph.h>
 		//#include <lemon/full_graph.h>
 		//#include <lemon/hypercube_graph.h>
 		#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<BaseDigraphComponent, BaseDigraphComponent >();
 		    checkConcept<IDableDigraphComponent<>,
 		      IDableDigraphComponent<> >();
 		    checkConcept<IterableDigraphComponent<>,
 		      IterableDigraphComponent<> >();
 		    checkConcept<MappableDigraphComponent<>,
 		      MappableDigraphComponent<> >();
+		  }
 		  { // checking skeleton digraphs
 		    checkConcept<Digraph, Digraph>();
+		  }
 		  { // checking list digraph
 		    checkConcept<Digraph, ListDigraph >();
 		    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
 		    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
 		    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
 		    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
 		    checkDigraph<ListDigraph>();
 		    checkGraphNodeMap<ListDigraph>();
 		    checkGraphArcMap<ListDigraph>();
+		  }
 		//   { // checking smart digraph
 		//     checkConcept<Digraph, SmartDigraph >();
 		//     checkDigraph<SmartDigraph>();
 		//     checkDigraphNodeMap<SmartDigraph>();
 		//     checkDigraphArcMap<SmartDigraph>();
 		//   }
 		//   { // checking full digraph
 		//     checkConcept<Digraph, FullDigraph >();
 		//   }
 		//   { // checking full digraph
 		//     checkConcept<Digraph, HyperCubeDigraph >();
 		//   }
 		  std::cout << __FILE__ ": All tests passed.\n";
 		  return 0;
+		}

test/digraph_test.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <lemon/graph_utils.h>
 		#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<class Digraph>
 		  struct PetStruct
+		  {
 		    ///Vector containing the outer nodes.
 		    std::vector<typename Digraph::Node> outer;
 		    ///Vector containing the inner nodes.
 		    std::vector<typename Digraph::Node> inner;
 		    ///Vector containing the edges of the inner circle.
 		    std::vector<typename Digraph::Arc> incir;
 		    ///Vector containing the edges of the outer circle.
 		    std::vector<typename Digraph::Arc> outcir;
 		    ///Vector containing the chord edges.
 		    std::vector<typename Digraph::Arc> 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<typename Digraph>
 		  PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
+		  {
 		    PetStruct<Digraph> n;
 		    for(int i=0;i<num;i++) {
 		      n.outer.push_back(G.addNode());
 		      n.inner.push_back(G.addNode());
+		    }
 		    for(int i=0;i<num;i++) {
 		      n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
 		      n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
 		      n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
+		    }
 		    return n;
+		  }
 		  /// \brief Adds to the digraph the reverse pair of all edges.
 		  ///
 		  /// Adds to the digraph the reverse pair of all edges.
 		  ///
 		  template<class Digraph>
 		  void bidirDigraph(Digraph &G)
+		  {
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    std::vector<Arc> ee;
 		    for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
 		    for(typename std::vector<Arc>::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<class Digraph>
 		  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<class Digraph> void checkDigraphNodeList(Digraph &G, int nn)
+		  {
 		    typename Digraph::NodeIt n(G);
 		    for(int i=0;i<nn;i++) {
 		      check(n!=INVALID,"Wrong Node list linking.");
 		      ++n;
+		    }
 		    check(n==INVALID,"Wrong Node list linking.");
+		  }
 		  template<class Digraph>
 		  void checkDigraphArcList(Digraph &G, int nn)
+		  {
 		    typedef typename Digraph::ArcIt ArcIt;
 		    ArcIt e(G);
 		    for(int i=0;i<nn;i++) {
 		      check(e!=INVALID,"Wrong Arc list linking.");
 		      ++e;
+		    }
 		    check(e==INVALID,"Wrong Arc list linking.");
+		  }
 		  template<class Digraph>
 		  void checkDigraphOutArcList(Digraph &G, typename Digraph::Node n, int nn)
+		  {
 		    typename Digraph::OutArcIt e(G,n);
 		    for(int i=0;i<nn;i++) {
 		      check(e!=INVALID,"Wrong OutArc list linking.");
 		      check(n==G.source(e), "Wrong OutArc list linking.");
 		      ++e;
+		    }
 		    check(e==INVALID,"Wrong OutArc list linking.");
+		  }
 		  template<class Digraph> void
 		  checkDigraphInArcList(Digraph &G, typename Digraph::Node n, int nn)
+		  {
 		    typename Digraph::InArcIt e(G,n);
 		    for(int i=0;i<nn;i++) {
 		      check(e!=INVALID,"Wrong InArc list linking.");
 		      check(n==G.target(e), "Wrong InArc list linking.");
 		      ++e;
+		    }
 		    check(e==INVALID,"Wrong InArc list linking.");
+		  }
 		  template <class Digraph>
 		  void checkDigraph() {
 		    const int num = 5;
 		    Digraph G;
 		    addPetersen(G, num);
 		    bidirDigraph(G);
 		    checkBidirPetersen(G, num);
+		  }
 		  template <class Digraph>
 		  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<Digraph> ConArcIt;
+		  }
 		  ///\file
 		  ///\todo Check target(), source() as well;
 		} //namespace lemon
 		#endif

test/graph_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * 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 <lemon/concepts/graph.h>
 		#include <lemon/list_graph.h>
 		// #include <lemon/smart_graph.h>
 		// #include <lemon/full_graph.h>
 		// #include <lemon/grid_graph.h>
 		//#include <lemon/graph_utils.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		void check_concepts() {
 		  { // checking digraph components
 		    checkConcept<BaseGraphComponent, BaseGraphComponent >();
 		    checkConcept<IDableGraphComponent<>,
 		      IDableGraphComponent<> >();
 		    checkConcept<IterableGraphComponent<>,
 		      IterableGraphComponent<> >();
 		    checkConcept<MappableGraphComponent<>,
 		      MappableGraphComponent<> >();
+		  }
+		  {
 		    checkConcept<Graph, ListGraph>();
 		//     checkConcept<Graph, SmartGraph>();
 		//     checkConcept<Graph, FullGraph>();
 		//     checkConcept<Graph, Graph>();
 		//     checkConcept<Graph, GridGraph>();
+		  }
+		}
 		template <typename Graph>
 		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 <typename Graph>
 		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 <typename Graph>
 		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<ListGraph>();
 		//  check_graph<SmartGraph>();
 		//   {
 		//     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;
+		}

test/map_test.h

Show inline comments

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * Copyright (C) 2003-2008
 * 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 <vector>
#include <lemon/maps.h>

#include "test_tools.h"


//! \ingroup misc
//! \file
//! \brief Some utilities to test map classes.

namespace lemon {



  template <typename Graph>
  void checkGraphNodeMap() {
    Graph graph;
    const int num = 16;
    
    typedef typename Graph::Node Node;

    std::vector<Node> nodes;
    for (int i = 0; i < num; ++i) {
      nodes.push_back(graph.addNode());      
    }
    typedef typename Graph::template NodeMap<int> 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<Node>(12);
    for (int i = 0; i < int(nodes.size()); ++i) {
      check(map[nodes[i]] == 12, "Wrong map constructor.");      
    }    
    graph.clear();
    nodes.clear();
  }

  template <typename Graph>
  void checkGraphArcMap() {
    Graph graph;
    const int num = 16;
    
    typedef typename Graph::Node Node;
    typedef typename Graph::Arc Arc;
    
    std::vector<Node> nodes;
    for (int i = 0; i < num; ++i) {
      nodes.push_back(graph.addNode());
    }
    
    std::vector<Arc> 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<int> 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<Arc>(12);
    for (int i = 0; i < int(edges.size()); ++i) {
      check(map[edges[i]] == 12, "Wrong map constructor.");      
    }    
    graph.clear();
    edges.clear();    
  }

  template <typename Graph>
  void checkGraphEdgeMap() {
    Graph graph;
    const int num = 16;
    
    typedef typename Graph::Node Node;
    typedef typename Graph::Edge Edge;
    
    std::vector<Node> nodes;
    for (int i = 0; i < num; ++i) {
      nodes.push_back(graph.addNode());
    }
    
    std::vector<Edge> 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<int> 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<Edge>(12);
    for (int i = 0; i < int(edges.size()); ++i) {
      check(map[edges[i]] == 12, "Wrong map constructor.");      
    }    
    graph.clear();
    edges.clear();    
  }

}

#endif

0 comments (0 inline)

1	1	/* -- C++ --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library
4	4	*
5		* Copyright (C) 2003-~~2007~~
	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#ifndef LEMON_TEST_MAP_TEST_H
20	20	#define LEMON_TEST_MAP_TEST_H
21	21
22	22
23	23	#include <vector>
24	24	#include <lemon/maps.h>
25	25
26	26	#include "test_tools.h"
27	27
28	28
29	29	//! \ingroup misc
30	30	//! \file
31	31	//! \brief Some utilities to test map classes.
32	32
33	33	namespace lemon {
34	34
35	35
36	36
37	37	template <typename Graph>
38	38	void checkGraphNodeMap() {
39	39	Graph graph;
40	40	const int num = 16;
41	41
42	42	typedef typename Graph::Node Node;
43	43
44	44	std::vector<Node> nodes;
45	45	for (int i = 0; i < num; ++i) {
46	46	nodes.push_back(graph.addNode());
47	47	}
48	48	typedef typename Graph::template NodeMap<int> IntNodeMap;
49	49	IntNodeMap map(graph, 42);
50	50	for (int i = 0; i < int(nodes.size()); ++i) {
51	51	check(map[nodes[i]] == 42, "Wrong map constructor.");
52	52	}
53	53	for (int i = 0; i < num; ++i) {
54	54	nodes.push_back(graph.addNode());
55	55	map[nodes.back()] = 23;
56	56	}
57	57	map = constMap<Node>(12);
58	58	for (int i = 0; i < int(nodes.size()); ++i) {
59	59	check(map[nodes[i]] == 12, "Wrong map constructor.");
60	60	}
61	61	graph.clear();
62	62	nodes.clear();
63	63	}
64	64
65	65	template <typename Graph>
66	66	void checkGraphArcMap() {
67	67	Graph graph;
68	68	const int num = 16;
69	69
70	70	typedef typename Graph::Node Node;
71	71	typedef typename Graph::Arc Arc;
72	72
73	73	std::vector<Node> nodes;
74	74	for (int i = 0; i < num; ++i) {
75	75	nodes.push_back(graph.addNode());
76	76	}
77	77
78	78	std::vector<Arc> edges;
79	79	for (int i = 0; i < num; ++i) {
80	80	for (int j = 0; j < i; ++j) {
81	81	edges.push_back(graph.addArc(nodes[i], nodes[j]));
82	82	}
83	83	}
84	84
85	85	typedef typename Graph::template ArcMap<int> IntArcMap;
86	86	IntArcMap map(graph, 42);
87	87
88	88	for (int i = 0; i < int(edges.size()); ++i) {
89	89	check(map[edges[i]] == 42, "Wrong map constructor.");
90	90	}
91	91
92	92	for (int i = 0; i < num; ++i) {
93	93	for (int j = i + 1; j < num; ++j) {
94	94	edges.push_back(graph.addArc(nodes[i], nodes[j]));
95	95	map[edges.back()] = 23;
96	96	}
97	97	}
98	98	map = constMap<Arc>(12);
99	99	for (int i = 0; i < int(edges.size()); ++i) {
100	100	check(map[edges[i]] == 12, "Wrong map constructor.");
101	101	}
102	102	graph.clear();
103	103	edges.clear();
104	104	}
105	105
106	106	template <typename Graph>
107	107	void checkGraphEdgeMap() {
108	108	Graph graph;
109	109	const int num = 16;
110	110
111	111	typedef typename Graph::Node Node;
112	112	typedef typename Graph::Edge Edge;
113	113
114	114	std::vector<Node> nodes;
115	115	for (int i = 0; i < num; ++i) {
116	116	nodes.push_back(graph.addNode());
117	117	}
118	118
119	119	std::vector<Edge> edges;
120	120	for (int i = 0; i < num; ++i) {
121	121	for (int j = 0; j < i; ++j) {
122	122	edges.push_back(graph.addEdge(nodes[i], nodes[j]));
123	123	}
124	124	}
125	125
126	126	typedef typename Graph::template EdgeMap<int> IntEdgeMap;
127	127	IntEdgeMap map(graph, 42);
128	128
129	129	for (int i = 0; i < int(edges.size()); ++i) {
130	130	check(map[edges[i]] == 42, "Wrong map constructor.");
131	131	}
132	132
133	133	for (int i = 0; i < num; ++i) {
134	134	for (int j = i + 1; j < num; ++j) {
135	135	edges.push_back(graph.addEdge(nodes[i], nodes[j]));
136	136	map[edges.back()] = 23;
137	137	}
138	138	}
139	139	map = constMap<Edge>(12);
140	140	for (int i = 0; i < int(edges.size()); ++i) {
141	141	check(map[edges[i]] == 12, "Wrong map constructor.");
142	142	}
143	143	graph.clear();
144	144	edges.clear();
145	145	}
146	146
147	147	}
148	148
149	149	#endif

RhodeCode

Login to your account