LEMON/LEMON-main Changeset - r107:31a2e6d28f61

Repositories » LEMON » LEMON-main

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; }

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:

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);

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
 		    ///

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)

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;

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);
+		    }

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.

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

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.

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);
 		//   }

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