LEMON/LEMON-main Changeset - r588:58f70400e139

Repositories » LEMON » LEMON-main

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

Changeset - r588:58f70400e139

« 584:33c6b6
« 587:114920

589:630c48 »

r588:58f70400e139

Wed, 15 Apr 2009 08:07:25

[Not Reviewed]

0 comments (0 inline)

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

Merge

0 19 0

merge default

0 files changed with 118 insertions and 125 deletions:

lemon/bin_heap.h

lemon/concepts/graph_components.h

lemon/concepts/heap.h

lemon/dfs.h

lemon/dijkstra.h

lemon/dimacs.h

lemon/graph_to_eps.h

lemon/kruskal.h

lemon/lgf_reader.h

lemon/lgf_writer.h

lemon/lp_base.h

lemon/maps.h

lemon/min_cost_arborescence.h

lemon/random.h

lemon/suurballe.h

lemon/time_measure.h

tools/dimacs-solver.cc

tools/dimacs-to-lgf.cc

tools/lgf-gen.cc

↑ Collapse diff ↑

lemon/bin_heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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_BIN_HEAP_H
 		#define LEMON_BIN_HEAP_H
 		///\ingroup auxdat
 		///\file
 		///\brief Binary Heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		namespace lemon {
 		  ///\ingroup auxdat
 		  ///
 		  ///\brief A Binary Heap implementation.
 		  ///
 		  ///This class implements the \e binary \e heap data structure.
 		  ///
 		  ///A \e heap is a data structure for storing items with specified values
 		  ///called \e priorities in such a way that finding the item with minimum
 		  ///priority is efficient. \c Comp specifies the ordering of the priorities.
 		  ///In a heap one can change the priority of an item, add or erase an
 		  ///item, etc.
 		  ///
 		  ///\tparam PR Type of the priority of the items.
 		  ///\tparam IM A read and writable item map with int values, used internally
 		  ///to handle the cross references.
 		  ///\tparam Comp A functor class for the ordering of the priorities.
 		  ///The default is \c std::less<PR>.
 		  ///
 		  ///\sa FibHeap
 		  ///\sa Dijkstra
 		  template <typename PR, typename IM, typename Comp = std::less<PR> >
 		  class BinHeap {
 		  public:
 		    ///\e
 		    typedef IM ItemIntMap;
 		    ///\e
 		    typedef PR Prio;
 		    ///\e
 		    typedef typename ItemIntMap::Key Item;
 		    ///\e
 		    typedef std::pair<Item,Prio> Pair;
 		    ///\e
 		    typedef Comp Compare;
 		    /// \brief Type to represent the items states.
 		    ///
 		    /// Each Item element have a state associated to it. It may be "in heap",
 		    /// "pre heap" or "post heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// The item-int map must be initialized in such way that it assigns
 		    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		    enum State {
 		      IN_HEAP = 0,    ///< \e
 		      PRE_HEAP = -1,  ///< \e
-		      POST_HEAP = -2  ///< \e
+		      IN_HEAP = 0,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		  private:
 		    std::vector<Pair> _data;
 		    Compare _comp;
 		    ItemIntMap &_iim;
 		  public:
 		    /// \brief The constructor.
 		    ///
 		    /// The constructor.
 		    /// \param map should be given to the constructor, since it is used
 		    /// internally to handle the cross references. The value of the map
 		    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
 		    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
 		    /// \brief The constructor.
 		    ///
 		    /// The constructor.
 		    /// \param map should be given to the constructor, since it is used
 		    /// internally to handle the cross references. The value of the map
 		    /// should be PRE_HEAP (-1) for each element.
 		    ///
 		    /// \param comp The comparator function object.
 		    BinHeap(ItemIntMap &map, const Compare &comp)
 		      : _iim(map), _comp(comp) {}
 		    /// The number of items stored in the heap.
 		    ///
 		    /// \brief Returns the number of items stored in the heap.
 		    int size() const { return _data.size(); }
 		    /// \brief Checks if the heap stores no items.
 		    ///
 		    /// Returns \c true if and only if the heap stores no items.
 		    bool empty() const { return _data.empty(); }
 		    /// \brief Make empty this heap.
 		    ///
 		    /// Make empty this heap. It does not change the cross reference map.
 		    /// If you want to reuse what is not surely empty you should first clear
 		    /// the heap and after that you should set the cross reference map for
 		    /// each item to \c PRE_HEAP.
 		    void clear() {
 		      _data.clear();
+		    }
 		  private:
 		    static int parent(int i) { return (i-1)/2; }
 		    static int second_child(int i) { return 2*i+2; }
 		    bool less(const Pair &p1, const Pair &p2) const {
 		      return _comp(p1.second, p2.second);
+		    }
 		    int bubble_up(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,_data[par]) ) {
 		        move(_data[par],hole);
 		        hole = par;
 		        par = parent(hole);
+		      }
 		      move(p, hole);
 		      return hole;
+		    }
 		    int bubble_down(int hole, Pair p, int length) {
 		      int child = second_child(hole);
 		      while(child < length) {
 		        if( less(_data[child-1], _data[child]) ) {
 		          --child;
+		        }
 		        if( !less(_data[child], p) )
 		          goto ok;
 		        move(_data[child], hole);
 		        hole = child;
 		        child = second_child(hole);
+		      }
 		      child--;
 		      if( child<length && less(_data[child], p) ) {
 		        move(_data[child], hole);
 		        hole=child;
+		      }
 		    ok:
 		      move(p, hole);
 		      return hole;
+		    }
 		    void move(const Pair &p, int i) {
 		      _data[i] = p;
 		      _iim.set(p.first, i);
+		    }
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.

lemon/concepts/graph_components.h

Show inline comments

@@ -509,409 +509,409 @@
 		    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
 		    template <typename GR,
 		              typename Item = typename GR::Arc,
 		              typename Base = typename GR::Node,
 		              char sel = '0'>
 		    class GraphIncIt : public Item {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor.
 		      /// \warning The default constructor is not required to set
 		      /// the iterator to some well-defined value. So you should consider it
 		      /// as uninitialized.
 		      GraphIncIt() {}
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy constructor.
 		      GraphIncIt(const GraphIncIt& it) : Item(it) {}
 		      /// \brief Constructor that sets the iterator to the first
 		      /// incoming or outgoing arc.
 		      ///
 		      /// Constructor that sets the iterator to the first arc
 		      /// incoming to or outgoing from the given node.
 		      explicit GraphIncIt(const GR&, const Base&) {}
 		      /// \brief Constructor for conversion from \c INVALID.
 		      ///
 		      /// Constructor for conversion from \c INVALID.
 		      /// It initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      GraphIncIt(Invalid) {}
 		      /// \brief Assignment operator.
 		      ///
 		      /// Assignment operator for the iterator.
 		      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
 		      /// \brief Increment the iterator.
 		      ///
 		      /// This operator increments the iterator, i.e. assigns it to the
 		      /// next arc incoming to or outgoing from the given node.
 		      GraphIncIt& operator++() { return *this; }
 		      /// \brief Equality operator
 		      ///
 		      /// 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
 		      ///
 		      /// Inequality 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;}
 		      template <typename _GraphIncIt>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<GraphItem<sel>, _GraphIncIt>();
 		          _GraphIncIt it1(graph, node);
 		          _GraphIncIt it2;
 		          _GraphIncIt it3 = it1;
 		          _GraphIncIt it4 = INVALID;
 		          it2 = ++it1;
 		          ++it2 = it1;
 		          ++(++it1);
 		          Item e = it1;
 		          e = it2;
+		        }
 		        const Base& node;
 		        const GR& graph;
 		      };
 		    };
 		    /// \brief Skeleton class for iterable directed graphs.
 		    ///
 		    /// This class describes the interface of iterable directed
 		    /// graphs. It extends \ref BaseDigraphComponent with the core
 		    /// iterable interface.
 		    /// This concept is part of the Digraph concept.
 		    template <typename BAS = BaseDigraphComponent>
 		    class IterableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      typedef IterableDigraphComponent Digraph;
-		      /// \name Base iteration
+		      /// \name Base Iteration
 		      ///
 		      /// This interface provides functions for iteration on digraph items.
 		      ///
 		      /// @{
 		      /// \brief Return the first node.
 		      ///
 		      /// This function gives back the first node in the iteration order.
 		      void first(Node&) const {}
 		      /// \brief Return the next node.
 		      ///
 		      /// This function gives back the next node in the iteration order.
 		      void next(Node&) const {}
 		      /// \brief Return the first arc.
 		      ///
 		      /// This function gives back the first arc in the iteration order.
 		      void first(Arc&) const {}
 		      /// \brief Return the next arc.
 		      ///
 		      /// This function gives back the next arc in the iteration order.
 		      void next(Arc&) const {}
 		      /// \brief Return the first arc incomming to the given node.
 		      ///
 		      /// This function gives back the first arc incomming to the
 		      /// given node.
 		      void firstIn(Arc&, const Node&) const {}
 		      /// \brief Return the next arc incomming to the given node.
 		      ///
 		      /// This function gives back the next arc incomming to the
 		      /// given node.
 		      void nextIn(Arc&) const {}
 		      /// \brief Return the first arc outgoing form the given node.
 		      ///
 		      /// This function gives back the first arc outgoing form the
 		      /// given node.
 		      void firstOut(Arc&, const Node&) const {}
 		      /// \brief Return the next arc outgoing form the given node.
 		      ///
 		      /// This function gives back the next arc outgoing form the
 		      /// given node.
 		      void nextOut(Arc&) const {}
 		      /// @}
-		      /// \name Class based iteration
+		      /// \name Class Based Iteration
 		      ///
 		      /// This interface provides iterator classes for 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 arc.
 		      ///
 		      /// This iterator goes through each arc.
 		      ///
 		      typedef GraphItemIt<Digraph, Arc> ArcIt;
 		      /// \brief 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.
 		      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.
 		      ///
 		      /// This function gives back the base node of the iterator.
 		      /// It is always the target node of the pointed arc.
 		      Node baseNode(const InArcIt&) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// This function gives back the running node of the iterator.
 		      /// It is always the source node of the pointed arc.
 		      Node runningNode(const InArcIt&) const { return INVALID; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// This function gives back the base node of the iterator.
 		      /// It is always the source node of the pointed arc.
 		      Node baseNode(const OutArcIt&) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// This function gives back the running node of the iterator.
 		      /// It is always the target node 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;
 		            const typename _Digraph::InArcIt iait(INVALID);
 		            const typename _Digraph::OutArcIt oait(INVALID);
 		            n = digraph.baseNode(iait);
 		            n = digraph.runningNode(iait);
 		            n = digraph.baseNode(oait);
 		            n = digraph.runningNode(oait);
 		            ignore_unused_variable_warning(n);
+		          }
+		        }
 		        const _Digraph& digraph;
 		      };
 		    };
 		    /// \brief Skeleton class for iterable undirected graphs.
 		    ///
 		    /// This class describes the interface of iterable undirected
 		    /// graphs. It extends \ref IterableDigraphComponent with the core
 		    /// iterable interface of undirected graphs.
 		    /// This concept is part of the Graph concept.
 		    template <typename BAS = BaseGraphComponent>
 		    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      typedef typename Base::Edge Edge;
 		      typedef IterableGraphComponent Graph;
-		      /// \name Base iteration
+		      /// \name Base Iteration
 		      ///
 		      /// This interface provides functions for iteration on edges.
 		      ///
 		      /// @{
 		      using IterableDigraphComponent<Base>::first;
 		      using IterableDigraphComponent<Base>::next;
 		      /// \brief Return the first edge.
 		      ///
 		      /// This function gives back the first edge in the iteration order.
 		      void first(Edge&) const {}
 		      /// \brief Return the next edge.
 		      ///
 		      /// This function gives back the next edge in the iteration order.
 		      void next(Edge&) const {}
 		      /// \brief Return the first edge incident to the given node.
 		      ///
 		      /// This function gives back the first edge incident to the given
 		      /// node. The bool parameter gives back the direction for which the
 		      /// source node of the directed arc representing the edge is the
 		      /// given node.
 		      void firstInc(Edge&, bool&, const Node&) const {}
 		      /// \brief Gives back the next of the edges from the
 		      /// given node.
 		      ///
 		      /// This function gives back the next edge incident to the given
 		      /// node. The bool parameter should be used as \c firstInc() use it.
 		      void nextInc(Edge&, bool&) const {}
 		      using IterableDigraphComponent<Base>::baseNode;
 		      using IterableDigraphComponent<Base>::runningNode;
 		      /// @}
-		      /// \name Class based iteration
+		      /// \name Class Based Iteration
 		      ///
 		      /// This interface provides iterator classes for edges.
 		      ///
 		      /// @{
 		      /// \brief This iterator goes through each edge.
 		      ///
 		      /// This iterator goes through each edge.
 		      typedef GraphItemIt<Graph, Edge> EdgeIt;
 		      /// \brief This iterator goes trough the incident edges of a
 		      /// node.
 		      ///
 		      /// This iterator goes trough the incident edges of a certain
 		      /// node of a graph.
 		      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// This function gives back the base node of the iterator.
 		      Node baseNode(const IncEdgeIt&) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// This function gives back the running node of the iterator.
 		      Node runningNode(const IncEdgeIt&) const { return INVALID; }
 		      /// @}
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<IterableDigraphComponent<Base>, _Graph>();
+		          {
 		            typename _Graph::Node node(INVALID);
 		            typename _Graph::Edge edge(INVALID);
 		            bool dir;
+		            {
 		              graph.first(edge);
 		              graph.next(edge);
+		            }
+		            {
 		              graph.firstInc(edge, dir, node);
 		              graph.nextInc(edge, dir);
+		            }
+		          }
+		          {
 		            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
 		              typename _Graph::EdgeIt >();
 		            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
 		              typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
 		            typename _Graph::Node n;
 		            const typename _Graph::IncEdgeIt ieit(INVALID);
 		            n = graph.baseNode(ieit);
 		            n = graph.runningNode(ieit);
+		          }
+		        }
 		        const _Graph& graph;
 		      };
 		    };
 		    /// \brief Skeleton class for alterable directed graphs.
 		    ///
 		    /// This class describes the interface of alterable directed
 		    /// graphs. It extends \ref BaseDigraphComponent with the alteration
 		    /// notifier interface. It implements
 		    /// an observer-notifier pattern for each digraph item. More
 		    /// obsevers can be registered into the notifier and whenever an
 		    /// alteration occured in the digraph all the observers will be
 		    /// notified about it.
 		    template <typename BAS = BaseDigraphComponent>
 		    class AlterableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// Node alteration notifier class.
 		      typedef AlterationNotifier<AlterableDigraphComponent, Node>
 		      NodeNotifier;
 		      /// Arc alteration notifier class.
 		      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
 		      ArcNotifier;
 		      /// \brief Return the node alteration notifier.
 		      ///
 		      /// This function gives back the node alteration notifier.
 		      NodeNotifier& notifier(Node) const {
 		         return NodeNotifier();

lemon/concepts/heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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 concept
 		///\file
 		///\brief The concept of heaps.
 		#ifndef LEMON_CONCEPTS_HEAP_H
 		#define LEMON_CONCEPTS_HEAP_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief The heap concept.
 		    ///
 		    /// Concept class describing the main interface of heaps. A \e heap
 		    /// is a data structure for storing items with specified values called
 		    /// \e priorities in such a way that finding the item with minimum
 		    /// priority is efficient. In a heap one can change the priority of an
 		    /// item, add or erase an item, etc.
 		    ///
 		    /// \tparam PR Type of the priority of the items.
 		    /// \tparam IM A read and writable item map with int values, used
 		    /// internally to handle the cross references.
 		    /// \tparam Comp A functor class for the ordering of the priorities.
 		    /// The default is \c std::less<PR>.
 		#ifdef DOXYGEN
 		    template <typename PR, typename IM, typename Comp = std::less<PR> >
 		#else
 		    template <typename PR, typename IM>
 		#endif
 		    class Heap {
 		    public:
 		      /// Type of the item-int map.
 		      typedef IM ItemIntMap;
 		      /// Type of the priorities.
 		      typedef PR Prio;
 		      /// Type of the items stored in the heap.
 		      typedef typename ItemIntMap::Key Item;
 		      /// \brief Type to represent the states of the items.
 		      ///
 		      /// Each item has a state associated to it. It can be "in heap",
 		      /// "pre heap" or "post heap". The later two are indifferent
 		      /// from the point of view of the heap, but may be useful for
 		      /// the user.
 		      ///
 		      /// The item-int map must be initialized in such way that it assigns
 		      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		      enum State {
 		        IN_HEAP = 0,    ///< The "in heap" state constant.
 		        PRE_HEAP = -1,  ///< The "pre heap" state constant.
-		        POST_HEAP = -2  ///< The "post heap" state constant.
+		        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
 		        PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant.
 		        POST_HEAP = -2  ///< = -2. The "post heap" state constant.
 		      };
 		      /// \brief The constructor.
 		      ///
 		      /// The constructor.
 		      /// \param map A map that assigns \c int values to keys of type
 		      /// \c Item. It is used internally by the heap implementations to
 		      /// handle the cross references. The assigned value must be
 		      /// \c PRE_HEAP (<tt>-1</tt>) for every item.
 		      explicit Heap(ItemIntMap &map) {}
 		      /// \brief The number of items stored in the heap.
 		      ///
 		      /// Returns the number of items stored in the heap.
 		      int size() const { return 0; }
 		      /// \brief Checks if the heap is empty.
 		      ///
 		      /// Returns \c true if the heap is empty.
 		      bool empty() const { return false; }
 		      /// \brief Makes the heap empty.
 		      ///
 		      /// Makes the heap empty.
 		      void clear();
 		      /// \brief Inserts an item into the heap with the given priority.
 		      ///
 		      /// Inserts the given item into the heap with the given priority.
 		      /// \param i The item to insert.
 		      /// \param p The priority of the item.
 		      void push(const Item &i, const Prio &p) {}
 		      /// \brief Returns the item having minimum priority.
 		      ///
 		      /// Returns the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Item top() const {}
 		      /// \brief The minimum priority.
 		      ///
 		      /// Returns the minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Prio prio() const {}
 		      /// \brief Removes the item having minimum priority.
 		      ///
 		      /// Removes the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      void pop() {}
 		      /// \brief Removes an item from the heap.
 		      ///
 		      /// Removes the given item from the heap if it is already stored.
 		      /// \param i The item to delete.
 		      void erase(const Item &i) {}
 		      /// \brief The priority of an item.
 		      ///
 		      /// Returns the priority of the given item.
 		      /// \param i The item.
 		      /// \pre \c i must be in the heap.
 		      Prio operator[](const Item &i) const {}
 		      /// \brief Sets the priority of an item or inserts it, if it is
 		      /// not stored in the heap.
 		      ///
 		      /// This method sets the priority of the given item if it is
 		      /// already stored in the heap.
 		      /// Otherwise it inserts the given item with the given priority.
 		      ///
 		      /// \param i The item.
 		      /// \param p The priority.
 		      void set(const Item &i, const Prio &p) {}
 		      /// \brief Decreases the priority of an item to the given value.
 		      ///
 		      /// Decreases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      /// \pre \c i must be stored in the heap with priority at least \c p.
 		      void decrease(const Item &i, const Prio &p) {}
 		      /// \brief Increases the priority of an item to the given value.
 		      ///
 		      /// Increases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      /// \pre \c i must be stored in the heap with priority at most \c p.
 		      void increase(const Item &i, const Prio &p) {}
 		      /// \brief Returns if an item is in, has already been in, or has
 		      /// never been in the heap.
 		      ///
 		      /// This method returns \c PRE_HEAP if the given item has never
 		      /// been in the heap, \c IN_HEAP if it is in the heap at the moment,

lemon/dfs.h

Show inline comments

@@ -113,193 +113,193 @@
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %DFS algorithm.
 		  ///
 		  ///There is also a \ref dfs() "function-type interface" for the DFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default type is \ref ListDigraph.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=DfsDefaultTraits<GR> >
 		#endif
 		  class Dfs {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///DFS paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::OutArcIt> _stack;
 		    int _stack_head;
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Dfs() {}
 		  public:
 		    typedef Dfs Create;
-		    ///\name Named template parameters
+		    ///\name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
 		      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "DistMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
 		    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ProcessedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.

lemon/dijkstra.h

Show inline comments

@@ -193,193 +193,193 @@
 		#else
 		  template <typename GR=ListDigraph,
 		            typename LEN=typename GR::template ArcMap<int>,
 		            typename TR=DijkstraDefaultTraits<GR,LEN> >
 		#endif
 		  class Dijkstra {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///The type of the length of the arcs.
 		    typedef typename TR::LengthMap::Value Value;
 		    ///The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The cross reference type used for the current heap.
 		    typedef typename TR::HeapCrossRef HeapCrossRef;
 		    ///The heap type used by the algorithm.
 		    typedef typename TR::Heap Heap;
 		    ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
 		    ///of the algorithm.
 		    typedef typename TR::OperationTraits OperationTraits;
 		    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the length map.
 		    const LengthMap *_length;
 		    //Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    //Pointer to the heap cross references.
 		    HeapCrossRef *_heap_cross_ref;
 		    //Indicates if _heap_cross_ref is locally allocated (true) or not.
 		    bool local_heap_cross_ref;
 		    //Pointer to the heap.
 		    Heap *_heap;
 		    //Indicates if _heap is locally allocated (true) or not.
 		    bool local_heap;
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
 		      if (!_heap_cross_ref) {
 		        local_heap_cross_ref = true;
 		        _heap_cross_ref = Traits::createHeapCrossRef(*G);
+		      }
 		      if (!_heap) {
 		        local_heap = true;
 		        _heap = Traits::createHeap(*_heap_cross_ref);
+		      }
+		    }
 		  public:
 		    typedef Dijkstra Create;
-		    ///\name Named template parameters
+		    ///\name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap
 		      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "DistMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap
 		      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ProcessedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap
 		      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap
 		      : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
 		      typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
 		      Create;
 		    };
 		    template <class H, class CR>
 		    struct SetHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
 		        LEMON_ASSERT(false, "HeapCrossRef is not initialized");
 		        return 0; // ignore warnings
+		      }
 		      static Heap *createHeap(HeapCrossRef &)
+		      {
 		        LEMON_ASSERT(false, "Heap is not initialized");

lemon/dimacs.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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_DIMACS_H
 		#define LEMON_DIMACS_H
 		#include <iostream>
 		#include <string>
 		#include <vector>
 		#include <limits>
 		#include <lemon/maps.h>
 		#include <lemon/error.h>
 		/// \ingroup dimacs_group
 		/// \file
 		/// \brief DIMACS file format reader.
 		namespace lemon {
 		  /// \addtogroup dimacs_group
 		  /// @{
 		  /// DIMACS file type descriptor.
 		  struct DimacsDescriptor
+		  {
 		    ///File type enum
 		    enum Type
+		      {
 		        NONE, MIN, MAX, SP, MAT
-		      };
+		    ///\brief DIMACS file type enum
 		    ///
 		    ///DIMACS file type enum.
 		    enum Type {
 		      NONE,  ///< Undefined type.
 		      MIN,   ///< DIMACS file type for minimum cost flow problems.
 		      MAX,   ///< DIMACS file type for maximum flow problems.
 		      SP,    ///< DIMACS file type for shostest path problems.
 		      MAT    ///< DIMACS file type for plain graphs and matching problems.
 		    };
 		    ///The file type
 		    Type type;
 		    ///The number of nodes in the graph
 		    int nodeNum;
 		    ///The number of edges in the graph
 		    int edgeNum;
 		    int lineShift;
-		    /// Constructor. Sets the type to NONE.
+		    ///Constructor. It sets the type to \c NONE.
 		    DimacsDescriptor() : type(NONE) {}
 		  };
 		  ///Discover the type of a DIMACS file
 		  ///It starts seeking the beginning of the file for the problem type
 		  ///and size info. The found data is returned in a special struct
 		  ///that can be evaluated and passed to the appropriate reader
 		  ///function.
 		  ///This function starts seeking the beginning of the given file for the
 		  ///problem type and size info.
 		  ///The found data is returned in a special struct that can be evaluated
 		  ///and passed to the appropriate reader function.
 		  DimacsDescriptor dimacsType(std::istream& is)
+		  {
 		    DimacsDescriptor r;
 		    std::string problem,str;
 		    char c;
 		    r.lineShift=0;
 		    while (is >> c)
 		      switch(c)
+		        {
 		        case 'p':
 		          if(is >> problem >> r.nodeNum >> r.edgeNum)
+		            {
 		              getline(is, str);
 		              r.lineShift++;
 		              if(problem=="min") r.type=DimacsDescriptor::MIN;
 		              else if(problem=="max") r.type=DimacsDescriptor::MAX;
 		              else if(problem=="sp") r.type=DimacsDescriptor::SP;
 		              else if(problem=="mat") r.type=DimacsDescriptor::MAT;
 		              else throw FormatError("Unknown problem type");
 		              return r;
+		            }
 		          else
+		            {
 		              throw FormatError("Missing or wrong problem type declaration.");
+		            }
 		          break;
 		        case 'c':
 		          getline(is, str);
 		          r.lineShift++;
 		          break;
 		        default:
 		          throw FormatError("Unknown DIMACS declaration.");
+		        }
 		    throw FormatError("Missing problem type declaration.");
+		  }
 		  /// DIMACS minimum cost flow reader function.
 		  /// \brief DIMACS minimum cost flow reader function.
 		  ///
 		  /// This function reads a minimum cost flow instance from DIMACS format,
 		  /// i.e. from a DIMACS file having a line starting with
 		  /// \code
 		  ///   p min
 		  /// \endcode
 		  /// At the beginning, \c g is cleared by \c g.clear(). The supply
 		  /// amount of the nodes are written to the \c supply node map
 		  /// (they are signed values). The lower bounds, capacities and costs
 		  /// of the arcs are written to the \c lower, \c capacity and \c cost
 		  /// arc maps.
 		  ///
 		  /// If the capacity of an arc is less than the lower bound, it will
 		  /// be set to "infinite" instead. The actual value of "infinite" is
 		  /// contolled by the \c infty parameter. If it is 0 (the default value),
 		  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
 		  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
 		  /// a non-zero value, that value will be used as "infinite".
 		  ///
 		  /// If the file type was previously evaluated by dimacsType(), then
 		  /// the descriptor struct should be given by the \c dest parameter.
 		  template <typename Digraph, typename LowerMap,
 		            typename CapacityMap, typename CostMap,
 		            typename SupplyMap>
 		  void readDimacsMin(std::istream& is,
 		                     Digraph &g,
 		                     LowerMap& lower,
 		                     CapacityMap& capacity,
 		                     CostMap& cost,
 		                     SupplyMap& supply,
 		                     typename CapacityMap::Value infty = 0,
 		                     DimacsDescriptor desc=DimacsDescriptor())
+		  {
 		    g.clear();
 		    std::vector<typename Digraph::Node> nodes;
 		    typename Digraph::Arc e;
 		    std::string problem, str;
 		    char c;
 		    int i, j;
 		    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
 		    if(desc.type!=DimacsDescriptor::MIN)
 		      throw FormatError("Problem type mismatch");
 		    nodes.resize(desc.nodeNum + 1);
 		    for (int k = 1; k <= desc.nodeNum; ++k) {
 		      nodes[k] = g.addNode();
 		      supply.set(nodes[k], 0);
+		    }
 		    typename SupplyMap::Value sup;
 		    typename CapacityMap::Value low;
 		    typename CapacityMap::Value cap;
 		    typename CostMap::Value co;
 		    typedef typename CapacityMap::Value Capacity;
 		    if(infty==0)
 		      infty = std::numeric_limits<Capacity>::has_infinity ?
 		        std::numeric_limits<Capacity>::infinity() :
 		        std::numeric_limits<Capacity>::max();
 		    while (is >> c) {
 		      switch (c) {
 		      case 'c': // comment line
 		        getline(is, str);
 		        break;
 		      case 'n': // node definition line
 		        is >> i >> sup;
 		        getline(is, str);
 		        supply.set(nodes[i], sup);
 		        break;
 		      case 'a': // arc definition line
 		        is >> i >> j >> low >> cap >> co;
 		        getline(is, str);
 		        e = g.addArc(nodes[i], nodes[j]);
 		        lower.set(e, low);
 		        if (cap >= low)
 		          capacity.set(e, cap);
 		        else
 		          capacity.set(e, infty);
 		        cost.set(e, co);
 		        break;
+		      }
+		    }
+		  }
 		  template<typename Digraph, typename CapacityMap>
 		  void _readDimacs(std::istream& is,
 		                   Digraph &g,
 		                   CapacityMap& capacity,
 		                   typename Digraph::Node &s,
 		                   typename Digraph::Node &t,
 		                   typename CapacityMap::Value infty = 0,
 		                   DimacsDescriptor desc=DimacsDescriptor()) {
 		    g.clear();
 		    s=t=INVALID;
 		    std::vector<typename Digraph::Node> nodes;
 		    typename Digraph::Arc e;
 		    char c, d;
 		    int i, j;
 		    typename CapacityMap::Value _cap;
 		    std::string str;
 		    nodes.resize(desc.nodeNum + 1);
 		    for (int k = 1; k <= desc.nodeNum; ++k) {
 		      nodes[k] = g.addNode();
+		    }
 		    typedef typename CapacityMap::Value Capacity;
 		    if(infty==0)
 		      infty = std::numeric_limits<Capacity>::has_infinity ?
 		        std::numeric_limits<Capacity>::infinity() :
 		        std::numeric_limits<Capacity>::max();
 		    while (is >> c) {
 		      switch (c) {
 		      case 'c': // comment line
 		        getline(is, str);
 		        break;
 		      case 'n': // node definition line
 		        if (desc.type==DimacsDescriptor::SP) { // shortest path problem
 		          is >> i;
 		          getline(is, str);
 		          s = nodes[i];
+		        }
 		        if (desc.type==DimacsDescriptor::MAX) { // max flow problem
 		          is >> i >> d;
 		          getline(is, str);
 		          if (d == 's') s = nodes[i];
 		          if (d == 't') t = nodes[i];
+		        }
 		        break;
 		      case 'a': // arc definition line
 		        if (desc.type==DimacsDescriptor::SP) {
 		          is >> i >> j >> _cap;
 		          getline(is, str);
 		          e = g.addArc(nodes[i], nodes[j]);
 		          capacity.set(e, _cap);
+		        }
 		        else if (desc.type==DimacsDescriptor::MAX) {
 		          is >> i >> j >> _cap;
 		          getline(is, str);
 		          e = g.addArc(nodes[i], nodes[j]);
 		          if (_cap >= 0)
 		            capacity.set(e, _cap);
 		          else
 		            capacity.set(e, infty);
+		        }
 		        else {
 		          is >> i >> j;
 		          getline(is, str);
 		          g.addArc(nodes[i], nodes[j]);
+		        }
 		        break;
+		      }
+		    }
+		  }
 		  /// DIMACS maximum flow reader function.
+		  /// \brief DIMACS maximum flow reader function.
 		  ///
 		  /// This function reads a maximum flow instance from DIMACS format,
 		  /// i.e. from a DIMACS file having a line starting with
 		  /// \code
 		  ///   p max
 		  /// \endcode
 		  /// At the beginning, \c g is cleared by \c g.clear(). The arc
 		  /// capacities are written to the \c capacity arc map and \c s and
 		  /// \c t are set to the source and the target nodes.
 		  ///
 		  /// If the capacity of an arc is negative, it will
 		  /// be set to "infinite" instead. The actual value of "infinite" is
 		  /// contolled by the \c infty parameter. If it is 0 (the default value),
 		  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
 		  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
 		  /// a non-zero value, that value will be used as "infinite".
 		  ///
 		  /// If the file type was previously evaluated by dimacsType(), then
 		  /// the descriptor struct should be given by the \c dest parameter.
 		  template<typename Digraph, typename CapacityMap>
 		  void readDimacsMax(std::istream& is,
 		                     Digraph &g,
 		                     CapacityMap& capacity,
 		                     typename Digraph::Node &s,
 		                     typename Digraph::Node &t,
 		                     typename CapacityMap::Value infty = 0,
 		                     DimacsDescriptor desc=DimacsDescriptor()) {
 		    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
 		    if(desc.type!=DimacsDescriptor::MAX)
 		      throw FormatError("Problem type mismatch");
 		    _readDimacs(is,g,capacity,s,t,infty,desc);
+		  }
 		  /// DIMACS shortest path reader function.
+		  /// \brief DIMACS shortest path reader function.
 		  ///
 		  /// This function reads a shortest path instance from DIMACS format,
 		  /// i.e. from a DIMACS file having a line starting with
 		  /// \code
 		  ///   p sp
 		  /// \endcode
 		  /// At the beginning, \c g is cleared by \c g.clear(). The arc
 		  /// lengths are written to the \c length arc map and \c s is set to the
 		  /// source node.
 		  ///
 		  /// If the file type was previously evaluated by dimacsType(), then
 		  /// the descriptor struct should be given by the \c dest parameter.
 		  template<typename Digraph, typename LengthMap>
 		  void readDimacsSp(std::istream& is,
 		                    Digraph &g,
 		                    LengthMap& length,
 		                    typename Digraph::Node &s,
 		                    DimacsDescriptor desc=DimacsDescriptor()) {
 		    typename Digraph::Node t;
 		    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
 		    if(desc.type!=DimacsDescriptor::SP)
 		      throw FormatError("Problem type mismatch");
 		    _readDimacs(is, g, length, s, t, 0, desc);
+		  }
 		  /// DIMACS capacitated digraph reader function.
+		  /// \brief DIMACS capacitated digraph reader function.
 		  ///
 		  /// This function reads an arc capacitated digraph instance from
 		  /// DIMACS 'max' or 'sp' format.
 		  /// At the beginning, \c g is cleared by \c g.clear()
 		  /// and the arc capacities/lengths are written to the \c capacity
 		  /// arc map.
 		  ///
 		  /// In case of the 'max' format, if the capacity of an arc is negative,
 		  /// it will
 		  /// be set to "infinite" instead. The actual value of "infinite" is
 		  /// contolled by the \c infty parameter. If it is 0 (the default value),
 		  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
 		  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
 		  /// a non-zero value, that value will be used as "infinite".
 		  ///
 		  /// If the file type was previously evaluated by dimacsType(), then
 		  /// the descriptor struct should be given by the \c dest parameter.
 		  template<typename Digraph, typename CapacityMap>
 		  void readDimacsCap(std::istream& is,
 		                     Digraph &g,
 		                     CapacityMap& capacity,
 		                     typename CapacityMap::Value infty = 0,
 		                     DimacsDescriptor desc=DimacsDescriptor()) {
 		    typename Digraph::Node u,v;
 		    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
 		    if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
 		      throw FormatError("Problem type mismatch");
 		    _readDimacs(is, g, capacity, u, v, infty, desc);
+		  }
 		  template<typename Graph>
 		  typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
 		  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
 		              dummy<0> = 0)
+		  {
 		    g.addEdge(s,t);
+		  }
 		  template<typename Graph>
 		  typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
 		  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
 		              dummy<1> = 1)
+		  {
 		    g.addArc(s,t);
+		  }
 		  /// DIMACS plain (di)graph reader function.
+		  /// \brief DIMACS plain (di)graph reader function.
 		  ///
 		  /// This function reads a (di)graph without any designated nodes and
 		  /// maps from DIMACS format, i.e. from DIMACS files having a line
-		  /// starting with
+		  /// This function reads a plain (di)graph without any designated nodes
 		  /// and maps (e.g. a matching instance) from DIMACS format, i.e. from
 		  /// DIMACS files having a line starting with
 		  /// \code
 		  ///   p mat
 		  /// \endcode
 		  /// At the beginning, \c g is cleared by \c g.clear().
 		  ///
 		  /// If the file type was previously evaluated by dimacsType(), then
 		  /// the descriptor struct should be given by the \c dest parameter.
 		  template<typename Graph>
 		  void readDimacsMat(std::istream& is, Graph &g,
 		                     DimacsDescriptor desc=DimacsDescriptor())
+		  {
 		    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
 		    if(desc.type!=DimacsDescriptor::MAT)
 		      throw FormatError("Problem type mismatch");
 		    g.clear();
 		    std::vector<typename Graph::Node> nodes;
 		    char c;
 		    int i, j;
 		    std::string str;
 		    nodes.resize(desc.nodeNum + 1);
 		    for (int k = 1; k <= desc.nodeNum; ++k) {
 		      nodes[k] = g.addNode();
+		    }
 		    while (is >> c) {
 		      switch (c) {
 		      case 'c': // comment line
 		        getline(is, str);
 		        break;
 		      case 'n': // node definition line
 		        break;
 		      case 'a': // arc definition line
 		        is >> i >> j;
 		        getline(is, str);
 		        _addArcEdge(g,nodes[i], nodes[j]);
 		        break;
+		      }
+		    }
+		  }
 		  /// DIMACS plain digraph writer function.
 		  ///
 		  /// This function writes a digraph without any designated nodes and
 		  /// maps into DIMACS format, i.e. into DIMACS file having a line
 		  /// starting with
 		  /// \code
 		  ///   p mat
 		  /// \endcode
 		  /// If \c comment is not empty, then it will be printed in the first line
 		  /// prefixed by 'c'.
 		  template<typename Digraph>
 		  void writeDimacsMat(std::ostream& os, const Digraph &g,
 		                      std::string comment="") {
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    if(!comment.empty())
 		      os << "c " << comment << std::endl;
 		    os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
 		    typename Digraph::template NodeMap<int> nodes(g);
 		    int i = 1;
 		    for(NodeIt v(g); v != INVALID; ++v) {
 		      nodes.set(v, i);
 		      ++i;
+		    }
 		    for(ArcIt e(g); e != INVALID; ++e) {
 		      os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
 		         << std::endl;
+		    }
+		  }
 		  /// @}
 		} //namespace lemon
 		#endif //LEMON_DIMACS_H

lemon/graph_to_eps.h

Show inline comments

@@ -175,208 +175,204 @@
 		///
 		///For detailed examples see the \ref graph_to_eps_demo.cc demo file.
 		template<class T> class GraphToEps : public T
+		{
 		  // Can't believe it is required by the C++ standard
 		  using T::g;
 		  using T::os;
 		  using T::_coords;
 		  using T::_nodeSizes;
 		  using T::_nodeShapes;
 		  using T::_nodeColors;
 		  using T::_arcColors;
 		  using T::_arcWidths;
 		  using T::_arcWidthScale;
 		  using T::_nodeScale;
 		  using T::_xBorder;
 		  using T::_yBorder;
 		  using T::_scale;
 		  using T::_nodeBorderQuotient;
 		  using T::_drawArrows;
 		  using T::_arrowLength;
 		  using T::_arrowWidth;
 		  using T::_showNodes;
 		  using T::_showArcs;
 		  using T::_enableParallel;
 		  using T::_parArcDist;
 		  using T::_showNodeText;
 		  using T::_nodeTexts;
 		  using T::_nodeTextSize;
 		  using T::_showNodePsText;
 		  using T::_nodePsTexts;
 		  using T::_nodePsTextsPreamble;
 		  using T::_undirected;
 		  using T::_pleaseRemoveOsStream;
 		  using T::_scaleToA4;
 		  using T::_title;
 		  using T::_copyright;
 		  using T::NodeTextColorType;
 		  using T::CUST_COL;
 		  using T::DIST_COL;
 		  using T::DIST_BW;
 		  using T::_nodeTextColorType;
 		  using T::_nodeTextColors;
 		  using T::_autoNodeScale;
 		  using T::_autoArcWidthScale;
 		  using T::_absoluteNodeSizes;
 		  using T::_absoluteArcWidths;
 		  using T::_negY;
 		  using T::_preScale;
 		  // dradnats ++C eht yb deriuqer si ti eveileb t'naC
 		  typedef typename T::Graph Graph;
 		  typedef typename Graph::Node Node;
 		  typedef typename Graph::NodeIt NodeIt;
 		  typedef typename Graph::Arc Arc;
 		  typedef typename Graph::ArcIt ArcIt;
 		  typedef typename Graph::InArcIt InArcIt;
 		  typedef typename Graph::OutArcIt OutArcIt;
 		  static const int INTERPOL_PREC;
 		  static const double A4HEIGHT;
 		  static const double A4WIDTH;
 		  static const double A4BORDER;
 		  bool dontPrint;
 		public:
 		  ///Node shapes
 		  ///Node shapes.
 		  ///
 		  enum NodeShapes {
 		    /// = 0
 		    ///\image html nodeshape_0.png
 		    ///\image latex nodeshape_0.eps "CIRCLE shape (0)" width=2cm
 		    CIRCLE=0,
 		    /// = 1
 		    ///\image html nodeshape_1.png
 		    ///\image latex nodeshape_1.eps "SQUARE shape (1)" width=2cm
 		    ///
 		    SQUARE=1,
 		    /// = 2
 		    ///\image html nodeshape_2.png
 		    ///\image latex nodeshape_2.eps "DIAMOND shape (2)" width=2cm
 		    ///
 		    DIAMOND=2,
 		    /// = 3
 		    ///\image html nodeshape_3.png
 		    ///\image latex nodeshape_2.eps "MALE shape (4)" width=2cm
 		    ///
 		    ///\image latex nodeshape_3.eps "MALE shape (3)" width=2cm
 		    MALE=3,
 		    /// = 4
 		    ///\image html nodeshape_4.png
 		    ///\image latex nodeshape_2.eps "FEMALE shape (4)" width=2cm
 		    ///
 		    ///\image latex nodeshape_4.eps "FEMALE shape (4)" width=2cm
 		    FEMALE=4
 		  };
 		private:
 		  class arcLess {
 		    const Graph &g;
 		  public:
 		    arcLess(const Graph &_g) : g(_g) {}
 		    bool operator()(Arc a,Arc b) const
+		    {
 		      Node ai=std::min(g.source(a),g.target(a));
 		      Node aa=std::max(g.source(a),g.target(a));
 		      Node bi=std::min(g.source(b),g.target(b));
 		      Node ba=std::max(g.source(b),g.target(b));
 		      return ai<bi ||
 		        (ai==bi && (aa < ba ||
 		                    (aa==ba && ai==g.source(a) && bi==g.target(b))));
+		    }
 		  };
 		  bool isParallel(Arc e,Arc f) const
+		  {
 		    return (g.source(e)==g.source(f)&&
 		            g.target(e)==g.target(f)) ||
 		      (g.source(e)==g.target(f)&&
 		       g.target(e)==g.source(f));
+		  }
 		  template<class TT>
 		  static std::string psOut(const dim2::Point<TT> &p)
+		    {
 		      std::ostringstream os;
 		      os << p.x << ' ' << p.y;
 		      return os.str();
+		    }
 		  static std::string psOut(const Color &c)
+		    {
 		      std::ostringstream os;
 		      os << c.red() << ' ' << c.green() << ' ' << c.blue();
 		      return os.str();
+		    }
 		public:
 		  GraphToEps(const T &t) : T(t), dontPrint(false) {};
 		  template<class X> struct CoordsTraits : public T {
 		  typedef X CoordsMapType;
 		    const X &_coords;
 		    CoordsTraits(const T &t,const X &x) : T(t), _coords(x) {}
 		  };
 		  ///Sets the map of the node coordinates
 		  ///Sets the map of the node coordinates.
 		  ///\param x must be a node map with \ref dim2::Point "dim2::Point<double>" or
 		  ///\ref dim2::Point "dim2::Point<int>" values.
 		  template<class X> GraphToEps<CoordsTraits<X> > coords(const X &x) {
 		    dontPrint=true;
 		    return GraphToEps<CoordsTraits<X> >(CoordsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeSizesTraits : public T {
 		    const X &_nodeSizes;
 		    NodeSizesTraits(const T &t,const X &x) : T(t), _nodeSizes(x) {}
 		  };
 		  ///Sets the map of the node sizes
 		  ///Sets the map of the node sizes.
 		  ///\param x must be a node map with \c double (or convertible) values.
 		  template<class X> GraphToEps<NodeSizesTraits<X> > nodeSizes(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<NodeSizesTraits<X> >(NodeSizesTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeShapesTraits : public T {
 		    const X &_nodeShapes;
 		    NodeShapesTraits(const T &t,const X &x) : T(t), _nodeShapes(x) {}
 		  };
 		  ///Sets the map of the node shapes
 		  ///Sets the map of the node shapes.
 		  ///The available shape values
 		  ///can be found in \ref NodeShapes "enum NodeShapes".
 		  ///\param x must be a node map with \c int (or convertible) values.
 		  ///\sa NodeShapes
 		  template<class X> GraphToEps<NodeShapesTraits<X> > nodeShapes(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<NodeShapesTraits<X> >(NodeShapesTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeTextsTraits : public T {
 		    const X &_nodeTexts;
 		    NodeTextsTraits(const T &t,const X &x) : T(t), _nodeTexts(x) {}
 		  };
 		  ///Sets the text printed on the nodes
 		  ///Sets the text printed on the nodes.
 		  ///\param x must be a node map with type that can be pushed to a standard
 		  ///\c ostream.
 		  template<class X> GraphToEps<NodeTextsTraits<X> > nodeTexts(const X &x)

lemon/kruskal.h

Show inline comments

@@ -155,175 +155,173 @@
 		    template <typename In>
 		    struct KruskalValueSelector<In,
 		      typename enable_if<SequenceInputIndicator<In>, void>::type>
+		    {
 		      typedef typename In::value_type::second_type Value;
 		    };
 		    template <typename In>
 		    struct KruskalValueSelector<In,
 		      typename enable_if<MapInputIndicator<In>, void>::type>
+		    {
 		      typedef typename In::Value Value;
 		    };
 		    template <typename Graph, typename In, typename Out,
 		              typename InEnable = void>
 		    struct KruskalInputSelector {};
 		    template <typename Graph, typename In, typename Out,
 		              typename InEnable = void>
 		    struct KruskalOutputSelector {};
 		    template <typename Graph, typename In, typename Out>
 		    struct KruskalInputSelector<Graph, In, Out,
 		      typename enable_if<SequenceInputIndicator<In>, void>::type >
+		    {
 		      typedef typename In::value_type::second_type Value;
 		      static Value kruskal(const Graph& graph, const In& in, Out& out) {
 		        return KruskalOutputSelector<Graph, In, Out>::
 		          kruskal(graph, in, out);
+		      }
 		    };
 		    template <typename Graph, typename In, typename Out>
 		    struct KruskalInputSelector<Graph, In, Out,
 		      typename enable_if<MapInputIndicator<In>, void>::type >
+		    {
 		      typedef typename In::Value Value;
 		      static Value kruskal(const Graph& graph, const In& in, Out& out) {
 		        typedef typename In::Key MapArc;
 		        typedef typename In::Value Value;
 		        typedef typename ItemSetTraits<Graph, MapArc>::ItemIt MapArcIt;
 		        typedef std::vector<std::pair<MapArc, Value> > Sequence;
 		        Sequence seq;
 		        for (MapArcIt it(graph); it != INVALID; ++it) {
 		          seq.push_back(std::make_pair(it, in[it]));
+		        }
 		        std::sort(seq.begin(), seq.end(), PairComp<Sequence>());
 		        return KruskalOutputSelector<Graph, Sequence, Out>::
 		          kruskal(graph, seq, out);
+		      }
 		    };
 		    template <typename T>
 		    struct RemoveConst {
 		      typedef T type;
 		    };
 		    template <typename T>
 		    struct RemoveConst<const T> {
 		      typedef T type;
 		    };
 		    template <typename Graph, typename In, typename Out>
 		    struct KruskalOutputSelector<Graph, In, Out,
 		      typename enable_if<SequenceOutputIndicator<Out>, void>::type >
+		    {
 		      typedef typename In::value_type::second_type Value;
 		      static Value kruskal(const Graph& graph, const In& in, Out& out) {
 		        typedef LoggerBoolMap<typename RemoveConst<Out>::type> Map;
 		        Map map(out);
 		        return _kruskal_bits::kruskal(graph, in, map);
+		      }
 		    };
 		    template <typename Graph, typename In, typename Out>
 		    struct KruskalOutputSelector<Graph, In, Out,
 		      typename enable_if<MapOutputIndicator<Out>, void>::type >
+		    {
 		      typedef typename In::value_type::second_type Value;
 		      static Value kruskal(const Graph& graph, const In& in, Out& out) {
 		        return _kruskal_bits::kruskal(graph, in, out);
+		      }
 		    };
+		  }
 		  /// \ingroup spantree
 		  ///
-		  /// \brief Kruskal algorithm to find a minimum cost spanning tree of
+		  /// \brief Kruskal's algorithm for finding a minimum cost spanning tree of
 		  /// a graph.
 		  ///
 		  /// This function runs Kruskal's algorithm to find a minimum cost
 		  /// spanning tree.
+		  /// spanning tree of a graph.
 		  /// Due to some C++ hacking, it accepts various input and output types.
 		  ///
 		  /// \param g The graph the algorithm runs on.
 		  /// It can be either \ref concepts::Digraph "directed" or
 		  /// \ref concepts::Graph "undirected".
 		  /// If the graph is directed, the algorithm consider it to be
 		  /// undirected by disregarding the direction of the arcs.
 		  ///
 		  /// \param in This object is used to describe the arc/edge costs.
 		  /// It can be one of the following choices.
 		  /// - An STL compatible 'Forward Container' with
 		  /// <tt>std::pair<GR::Arc,X></tt> or
 		  /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where
-		  /// \c X is the type of the costs. The pairs indicates the arcs/edges
+		  /// <tt>std::pair<GR::Arc,C></tt> or
 		  /// <tt>std::pair<GR::Edge,C></tt> as its <tt>value_type</tt>, where
 		  /// \c C is the type of the costs. The pairs indicates the arcs/edges
 		  /// along with the assigned cost. <em>They must be in a
 		  /// cost-ascending order.</em>
 		  /// - Any readable arc/edge map. The values of the map indicate the
 		  /// arc/edge costs.
 		  ///
 		  /// \retval out Here we also have a choice.
 		  /// - It can be a writable \c bool arc/edge map. After running the
 		  /// algorithm it will contain the found minimum cost spanning
 		  /// - It can be a writable arc/edge map with \c bool value type. After
 		  /// running the algorithm it will contain the found minimum cost spanning
 		  /// tree: the value of an arc/edge will be set to \c true if it belongs
 		  /// to the tree, otherwise it will be set to \c false. The value of
 		  /// each arc/edge will be set exactly once.
 		  /// - It can also be an iteraror of an STL Container with
 		  /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its
 		  /// <tt>value_type</tt>.  The algorithm copies the elements of the
 		  /// found tree into this sequence.  For example, if we know that the
 		  /// spanning tree of the graph \c g has say 53 arcs, then we can
 		  /// put its arcs into an STL vector \c tree with a code like this.
 		  ///\code
 		  /// std::vector<Arc> tree(53);
 		  /// kruskal(g,cost,tree.begin());
 		  ///\endcode
 		  /// Or if we don't know in advance the size of the tree, we can
 		  /// write this.
 		  ///\code
 		  /// std::vector<Arc> tree;
 		  /// kruskal(g,cost,std::back_inserter(tree));
 		  ///\endcode
 		  ///
 		  /// \return The total cost of the found spanning tree.
 		  ///
 		  /// \note If the input graph is not (weakly) connected, a spanning
 		  /// forest is calculated instead of a spanning tree.
 		#ifdef DOXYGEN
 		  template <class Graph, class In, class Out>
 		  Value kruskal(GR const& g, const In& in, Out& out)
 		  template <typename Graph, typename In, typename Out>
 		  Value kruskal(const Graph& g, const In& in, Out& out)
 		#else
 		  template <class Graph, class In, class Out>
 		  inline typename _kruskal_bits::KruskalValueSelector<In>::Value
 		  kruskal(const Graph& graph, const In& in, Out& out)
 		#endif
+		  {
 		    return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
 		      kruskal(graph, in, out);
+		  }
 		  template <class Graph, class In, class Out>
 		  inline typename _kruskal_bits::KruskalValueSelector<In>::Value
 		  kruskal(const Graph& graph, const In& in, const Out& out)
+		  {
 		    return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
 		      kruskal(graph, in, out);
+		  }
 		} //namespace lemon
 		#endif //LEMON_KRUSKAL_H

lemon/lgf_reader.h

Show inline comments

@@ -500,327 +500,327 @@
 		    ///
 		    /// Construct a directed graph reader, which reads from the given
 		    /// input stream.
 		    DigraphReader(Digraph& digraph, std::istream& is = std::cin)
 		      : _is(&is), local_is(false), _digraph(digraph),
 		        _use_nodes(false), _use_arcs(false),
 		        _skip_nodes(false), _skip_arcs(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph reader, which reads from the given
 		    /// file.
 		    DigraphReader(Digraph& digraph, const std::string& fn)
 		      : _is(new std::ifstream(fn.c_str())), local_is(true),
 		        _filename(fn), _digraph(digraph),
 		        _use_nodes(false), _use_arcs(false),
 		        _skip_nodes(false), _skip_arcs(false) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph reader, which reads from the given
 		    /// file.
 		    DigraphReader(Digraph& digraph, const char* fn)
 		      : _is(new std::ifstream(fn)), local_is(true),
 		        _filename(fn), _digraph(digraph),
 		        _use_nodes(false), _use_arcs(false),
 		        _skip_nodes(false), _skip_arcs(false) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Destructor
 		    ~DigraphReader() {
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename ArcMaps::iterator it = _arc_maps.begin();
 		           it != _arc_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        delete it->second;
+		      }
 		      if (local_is) {
 		        delete _is;
+		      }
+		    }
 		  private:
 		    template <typename DGR>
 		    friend DigraphReader<DGR> digraphReader(DGR& digraph, std::istream& is);
 		    template <typename DGR>
 		    friend DigraphReader<DGR> digraphReader(DGR& digraph,
 		                                            const std::string& fn);
 		    template <typename DGR>
 		    friend DigraphReader<DGR> digraphReader(DGR& digraph, const char *fn);
 		    DigraphReader(DigraphReader& other)
 		      : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
 		        _use_nodes(other._use_nodes), _use_arcs(other._use_arcs),
 		        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
 		      other._is = 0;
 		      other.local_is = false;
 		      _node_index.swap(other._node_index);
 		      _arc_index.swap(other._arc_index);
 		      _node_maps.swap(other._node_maps);
 		      _arc_maps.swap(other._arc_maps);
 		      _attributes.swap(other._attributes);
 		      _nodes_caption = other._nodes_caption;
 		      _arcs_caption = other._arcs_caption;
 		      _attributes_caption = other._attributes_caption;
+		    }
 		    DigraphReader& operator=(const DigraphReader&);
 		  public:
-		    /// \name Reading rules
+		    /// \name Reading Rules
 		    /// @{
 		    /// \brief Node map reading rule
 		    ///
 		    /// Add a node map reading rule to the reader.
 		    template <typename Map>
 		    DigraphReader& nodeMap(const std::string& caption, Map& map) {
 		      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Node>* storage =
 		        new _reader_bits::MapStorage<Node, Map>(map);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node map reading rule
 		    ///
 		    /// Add a node map reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Map, typename Converter>
 		    DigraphReader& nodeMap(const std::string& caption, Map& map,
 		                           const Converter& converter = Converter()) {
 		      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Node>* storage =
 		        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map reading rule
 		    ///
 		    /// Add an arc map reading rule to the reader.
 		    template <typename Map>
 		    DigraphReader& arcMap(const std::string& caption, Map& map) {
 		      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Arc>* storage =
 		        new _reader_bits::MapStorage<Arc, Map>(map);
 		      _arc_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map reading rule
 		    ///
 		    /// Add an arc map reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Map, typename Converter>
 		    DigraphReader& arcMap(const std::string& caption, Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Arc>* storage =
 		        new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
 		      _arc_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute reading rule
 		    ///
 		    /// Add an attribute reading rule to the reader.
 		    template <typename Value>
 		    DigraphReader& attribute(const std::string& caption, Value& value) {
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Value>(value);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute reading rule
 		    ///
 		    /// Add an attribute reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Value, typename Converter>
 		    DigraphReader& attribute(const std::string& caption, Value& value,
 		                             const Converter& converter = Converter()) {
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node reading rule
 		    ///
 		    /// Add a node reading rule to reader.
 		    DigraphReader& node(const std::string& caption, Node& node) {
 		      typedef _reader_bits::MapLookUpConverter<Node> Converter;
 		      Converter converter(_node_index);
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc reading rule
 		    ///
 		    /// Add an arc reading rule to reader.
 		    DigraphReader& arc(const std::string& caption, Arc& arc) {
 		      typedef _reader_bits::MapLookUpConverter<Arc> Converter;
 		      Converter converter(_arc_index);
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// @}
-		    /// \name Select section by name
+		    /// \name Select Section by Name
 		    /// @{
 		    /// \brief Set \c \@nodes section to be read
 		    ///
 		    /// Set \c \@nodes section to be read
 		    DigraphReader& nodes(const std::string& caption) {
 		      _nodes_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Set \c \@arcs section to be read
 		    ///
 		    /// Set \c \@arcs section to be read
 		    DigraphReader& arcs(const std::string& caption) {
 		      _arcs_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Set \c \@attributes section to be read
 		    ///
 		    /// Set \c \@attributes section to be read
 		    DigraphReader& attributes(const std::string& caption) {
 		      _attributes_caption = caption;
 		      return *this;
+		    }
 		    /// @}
-		    /// \name Using previously constructed node or arc set
+		    /// \name Using Previously Constructed Node or Arc Set
 		    /// @{
 		    /// \brief Use previously constructed node set
 		    ///
 		    /// Use previously constructed node set, and specify the node
 		    /// label map.
 		    template <typename Map>
 		    DigraphReader& useNodes(const Map& map) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
 		      _use_nodes = true;
 		      _writer_bits::DefaultConverter<typename Map::Value> converter;
 		      for (NodeIt n(_digraph); n != INVALID; ++n) {
 		        _node_index.insert(std::make_pair(converter(map[n]), n));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed node set
 		    ///
 		    /// Use previously constructed node set, and specify the node
 		    /// label map and a functor which converts the label map values to
 		    /// \c std::string.
 		    template <typename Map, typename Converter>
 		    DigraphReader& useNodes(const Map& map,
 		                            const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
 		      _use_nodes = true;
 		      for (NodeIt n(_digraph); n != INVALID; ++n) {
 		        _node_index.insert(std::make_pair(converter(map[n]), n));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed arc set
 		    ///
 		    /// Use previously constructed arc set, and specify the arc
 		    /// label map.
 		    template <typename Map>
 		    DigraphReader& useArcs(const Map& map) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
 		      _use_arcs = true;
 		      _writer_bits::DefaultConverter<typename Map::Value> converter;
 		      for (ArcIt a(_digraph); a != INVALID; ++a) {
 		        _arc_index.insert(std::make_pair(converter(map[a]), a));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed arc set
 		    ///
 		    /// Use previously constructed arc set, and specify the arc
 		    /// label map and a functor which converts the label map values to
 		    /// \c std::string.
 		    template <typename Map, typename Converter>
 		    DigraphReader& useArcs(const Map& map,
 		                           const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
 		      _use_arcs = true;
 		      for (ArcIt a(_digraph); a != INVALID; ++a) {
 		        _arc_index.insert(std::make_pair(converter(map[a]), a));
+		      }
 		      return *this;
+		    }
 		    /// \brief Skips the reading of node section
 		    ///
 		    /// Omit the reading of the node section. This implies that each node
 		    /// map reading rule will be abandoned, and the nodes of the graph
 		    /// will not be constructed, which usually cause that the arc set
 		    /// could not be read due to lack of node name resolving.
 		    /// Therefore \c skipArcs() function should also be used, or
 		    /// \c useNodes() should be used to specify the label of the nodes.
 		    DigraphReader& skipNodes() {
 		      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
 		      _skip_nodes = true;
 		      return *this;
+		    }
 		    /// \brief Skips the reading of arc section
 		    ///
 		    /// Omit the reading of the arc section. This implies that each arc
 		    /// map reading rule will be abandoned, and the arcs of the graph
 		    /// will not be constructed.
 		    DigraphReader& skipArcs() {
 		      LEMON_ASSERT(!_skip_arcs, "Skip arcs already set");
 		      _skip_arcs = true;
 		      return *this;
+		    }
 		    /// @}
 		  private:
@@ -1023,193 +1023,193 @@
 		        if (!_use_arcs) {
 		          typename NodeIndex::iterator it;
 		          it = _node_index.find(source_token);
 		          if (it == _node_index.end()) {
 		            std::ostringstream msg;
 		            msg << "Item not found: " << source_token;
 		            throw FormatError(msg.str());
+		          }
 		          Node source = it->second;
 		          it = _node_index.find(target_token);
 		          if (it == _node_index.end()) {
 		            std::ostringstream msg;
 		            msg << "Item not found: " << target_token;
 		            throw FormatError(msg.str());
+		          }
 		          Node target = it->second;
 		          a = _digraph.addArc(source, target);
 		          if (label_index != -1)
 		            _arc_index.insert(std::make_pair(tokens[label_index], a));
 		        } else {
 		          if (label_index == -1)
 		            throw FormatError("Label map not found");
 		          typename std::map<std::string, Arc>::iterator it =
 		            _arc_index.find(tokens[label_index]);
 		          if (it == _arc_index.end()) {
 		            std::ostringstream msg;
 		            msg << "Arc with label not found: " << tokens[label_index];
 		            throw FormatError(msg.str());
+		          }
 		          a = it->second;
+		        }
 		        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
 		          _arc_maps[i].second->set(a, tokens[map_index[i]]);
+		        }
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
+		    }
 		    void readAttributes() {
 		      std::set<std::string> read_attr;
 		      char c;
 		      while (readLine() && line >> c && c != '@') {
 		        line.putback(c);
 		        std::string attr, token;
 		        if (!_reader_bits::readToken(line, attr))
 		          throw FormatError("Attribute name not found");
 		        if (!_reader_bits::readToken(line, token))
 		          throw FormatError("Attribute value not found");
 		        if (line >> c)
 		          throw FormatError("Extra character at the end of line");
+		        {
 		          std::set<std::string>::iterator it = read_attr.find(attr);
 		          if (it != read_attr.end()) {
 		            std::ostringstream msg;
 		            msg << "Multiple occurence of attribute: " << attr;
 		            throw FormatError(msg.str());
+		          }
 		          read_attr.insert(attr);
+		        }
+		        {
 		          typename Attributes::iterator it = _attributes.lower_bound(attr);
 		          while (it != _attributes.end() && it->first == attr) {
 		            it->second->set(token);
 		            ++it;
+		          }
+		        }
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        if (read_attr.find(it->first) == read_attr.end()) {
 		          std::ostringstream msg;
 		          msg << "Attribute not found: " << it->first;
 		          throw FormatError(msg.str());
+		        }
+		      }
+		    }
 		  public:
-		    /// \name Execution of the reader
+		    /// \name Execution of the Reader
 		    /// @{
 		    /// \brief Start the batch processing
 		    ///
 		    /// This function starts the batch processing
 		    void run() {
 		      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
 		      bool nodes_done = _skip_nodes;
 		      bool arcs_done = _skip_arcs;
 		      bool attributes_done = false;
 		      line_num = 0;
 		      readLine();
 		      skipSection();
 		      while (readSuccess()) {
 		        try {
 		          char c;
 		          std::string section, caption;
 		          line >> c;
 		          _reader_bits::readToken(line, section);
 		          _reader_bits::readToken(line, caption);
 		          if (line >> c)
 		            throw FormatError("Extra character at the end of line");
 		          if (section == "nodes" && !nodes_done) {
 		            if (_nodes_caption.empty() || _nodes_caption == caption) {
 		              readNodes();
 		              nodes_done = true;
+		            }
 		          } else if ((section == "arcs" || section == "edges") &&
 		                     !arcs_done) {
 		            if (_arcs_caption.empty() || _arcs_caption == caption) {
 		              readArcs();
 		              arcs_done = true;
+		            }
 		          } else if (section == "attributes" && !attributes_done) {
 		            if (_attributes_caption.empty() || _attributes_caption == caption) {
 		              readAttributes();
 		              attributes_done = true;
+		            }
 		          } else {
 		            readLine();
 		            skipSection();
+		          }
 		        } catch (FormatError& error) {
 		          error.line(line_num);
 		          error.file(_filename);
 		          throw;
+		        }
+		      }
 		      if (!nodes_done) {
 		        throw FormatError("Section @nodes not found");
+		      }
 		      if (!arcs_done) {
 		        throw FormatError("Section @arcs not found");
+		      }
 		      if (!attributes_done && !_attributes.empty()) {
 		        throw FormatError("Section @attributes not found");
+		      }
+		    }
 		    /// @}
 		  };
 		  /// \brief Return a \ref DigraphReader class
 		  ///
 		  /// This function just returns a \ref DigraphReader class.
 		  /// \relates DigraphReader
 		  template <typename Digraph>
 		  DigraphReader<Digraph> digraphReader(Digraph& digraph, std::istream& is) {
 		    DigraphReader<Digraph> tmp(digraph, is);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref DigraphReader class
 		  ///
 		  /// This function just returns a \ref DigraphReader class.
 		  /// \relates DigraphReader
 		  template <typename Digraph>
 		  DigraphReader<Digraph> digraphReader(Digraph& digraph,
 		                                       const std::string& fn) {
 		    DigraphReader<Digraph> tmp(digraph, fn);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref DigraphReader class
 		  ///
 		  /// This function just returns a \ref DigraphReader class.
@@ -1296,373 +1296,373 @@
 		    /// \brief Constructor
 		    ///
 		    /// Construct an undirected graph reader, which reads from the given
 		    /// input stream.
 		    GraphReader(Graph& graph, std::istream& is = std::cin)
 		      : _is(&is), local_is(false), _graph(graph),
 		        _use_nodes(false), _use_edges(false),
 		        _skip_nodes(false), _skip_edges(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct an undirected graph reader, which reads from the given
 		    /// file.
 		    GraphReader(Graph& graph, const std::string& fn)
 		      : _is(new std::ifstream(fn.c_str())), local_is(true),
 		        _filename(fn), _graph(graph),
 		        _use_nodes(false), _use_edges(false),
 		        _skip_nodes(false), _skip_edges(false) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Construct an undirected graph reader, which reads from the given
 		    /// file.
 		    GraphReader(Graph& graph, const char* fn)
 		      : _is(new std::ifstream(fn)), local_is(true),
 		        _filename(fn), _graph(graph),
 		        _use_nodes(false), _use_edges(false),
 		        _skip_nodes(false), _skip_edges(false) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Destructor
 		    ~GraphReader() {
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename EdgeMaps::iterator it = _edge_maps.begin();
 		           it != _edge_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        delete it->second;
+		      }
 		      if (local_is) {
 		        delete _is;
+		      }
+		    }
 		  private:
 		    template <typename Graph>
 		    friend GraphReader<Graph> graphReader(Graph& graph, std::istream& is);
 		    template <typename Graph>
 		    friend GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);
 		    template <typename Graph>
 		    friend GraphReader<Graph> graphReader(Graph& graph, const char *fn);
 		    GraphReader(GraphReader& other)
 		      : _is(other._is), local_is(other.local_is), _graph(other._graph),
 		        _use_nodes(other._use_nodes), _use_edges(other._use_edges),
 		        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
 		      other._is = 0;
 		      other.local_is = false;
 		      _node_index.swap(other._node_index);
 		      _edge_index.swap(other._edge_index);
 		      _node_maps.swap(other._node_maps);
 		      _edge_maps.swap(other._edge_maps);
 		      _attributes.swap(other._attributes);
 		      _nodes_caption = other._nodes_caption;
 		      _edges_caption = other._edges_caption;
 		      _attributes_caption = other._attributes_caption;
+		    }
 		    GraphReader& operator=(const GraphReader&);
 		  public:
-		    /// \name Reading rules
+		    /// \name Reading Rules
 		    /// @{
 		    /// \brief Node map reading rule
 		    ///
 		    /// Add a node map reading rule to the reader.
 		    template <typename Map>
 		    GraphReader& nodeMap(const std::string& caption, Map& map) {
 		      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Node>* storage =
 		        new _reader_bits::MapStorage<Node, Map>(map);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node map reading rule
 		    ///
 		    /// Add a node map reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Map, typename Converter>
 		    GraphReader& nodeMap(const std::string& caption, Map& map,
 		                           const Converter& converter = Converter()) {
 		      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Node>* storage =
 		        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge map reading rule
 		    ///
 		    /// Add an edge map reading rule to the reader.
 		    template <typename Map>
 		    GraphReader& edgeMap(const std::string& caption, Map& map) {
 		      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Edge>* storage =
 		        new _reader_bits::MapStorage<Edge, Map>(map);
 		      _edge_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge map reading rule
 		    ///
 		    /// Add an edge map reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Map, typename Converter>
 		    GraphReader& edgeMap(const std::string& caption, Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Edge>* storage =
 		        new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
 		      _edge_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map reading rule
 		    ///
 		    /// Add an arc map reading rule to the reader.
 		    template <typename Map>
 		    GraphReader& arcMap(const std::string& caption, Map& map) {
 		      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Edge>* forward_storage =
 		        new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
 		      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
 		      _reader_bits::MapStorageBase<Edge>* backward_storage =
 		        new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
 		      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
 		      return *this;
+		    }
 		    /// \brief Arc map reading rule
 		    ///
 		    /// Add an arc map reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Map, typename Converter>
 		    GraphReader& arcMap(const std::string& caption, Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Edge>* forward_storage =
 		        new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
 		        (_graph, map, converter);
 		      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
 		      _reader_bits::MapStorageBase<Edge>* backward_storage =
 		        new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
 		        (_graph, map, converter);
 		      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
 		      return *this;
+		    }
 		    /// \brief Attribute reading rule
 		    ///
 		    /// Add an attribute reading rule to the reader.
 		    template <typename Value>
 		    GraphReader& attribute(const std::string& caption, Value& value) {
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Value>(value);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute reading rule
 		    ///
 		    /// Add an attribute reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Value, typename Converter>
 		    GraphReader& attribute(const std::string& caption, Value& value,
 		                             const Converter& converter = Converter()) {
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node reading rule
 		    ///
 		    /// Add a node reading rule to reader.
 		    GraphReader& node(const std::string& caption, Node& node) {
 		      typedef _reader_bits::MapLookUpConverter<Node> Converter;
 		      Converter converter(_node_index);
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge reading rule
 		    ///
 		    /// Add an edge reading rule to reader.
 		    GraphReader& edge(const std::string& caption, Edge& edge) {
 		      typedef _reader_bits::MapLookUpConverter<Edge> Converter;
 		      Converter converter(_edge_index);
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc reading rule
 		    ///
 		    /// Add an arc reading rule to reader.
 		    GraphReader& arc(const std::string& caption, Arc& arc) {
 		      typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
 		      Converter converter(_graph, _edge_index);
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// @}
-		    /// \name Select section by name
+		    /// \name Select Section by Name
 		    /// @{
 		    /// \brief Set \c \@nodes section to be read
 		    ///
 		    /// Set \c \@nodes section to be read.
 		    GraphReader& nodes(const std::string& caption) {
 		      _nodes_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Set \c \@edges section to be read
 		    ///
 		    /// Set \c \@edges section to be read.
 		    GraphReader& edges(const std::string& caption) {
 		      _edges_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Set \c \@attributes section to be read
 		    ///
 		    /// Set \c \@attributes section to be read.
 		    GraphReader& attributes(const std::string& caption) {
 		      _attributes_caption = caption;
 		      return *this;
+		    }
 		    /// @}
-		    /// \name Using previously constructed node or edge set
+		    /// \name Using Previously Constructed Node or Edge Set
 		    /// @{
 		    /// \brief Use previously constructed node set
 		    ///
 		    /// Use previously constructed node set, and specify the node
 		    /// label map.
 		    template <typename Map>
 		    GraphReader& useNodes(const Map& map) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
 		      _use_nodes = true;
 		      _writer_bits::DefaultConverter<typename Map::Value> converter;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _node_index.insert(std::make_pair(converter(map[n]), n));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed node set
 		    ///
 		    /// Use previously constructed node set, and specify the node
 		    /// label map and a functor which converts the label map values to
 		    /// \c std::string.
 		    template <typename Map, typename Converter>
 		    GraphReader& useNodes(const Map& map,
 		                            const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
 		      _use_nodes = true;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _node_index.insert(std::make_pair(converter(map[n]), n));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed edge set
 		    ///
 		    /// Use previously constructed edge set, and specify the edge
 		    /// label map.
 		    template <typename Map>
 		    GraphReader& useEdges(const Map& map) {
 		      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
 		      _use_edges = true;
 		      _writer_bits::DefaultConverter<typename Map::Value> converter;
 		      for (EdgeIt a(_graph); a != INVALID; ++a) {
 		        _edge_index.insert(std::make_pair(converter(map[a]), a));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed edge set
 		    ///
 		    /// Use previously constructed edge set, and specify the edge
 		    /// label map and a functor which converts the label map values to
 		    /// \c std::string.
 		    template <typename Map, typename Converter>
 		    GraphReader& useEdges(const Map& map,
 		                            const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
 		      _use_edges = true;
 		      for (EdgeIt a(_graph); a != INVALID; ++a) {
 		        _edge_index.insert(std::make_pair(converter(map[a]), a));
+		      }
 		      return *this;
+		    }
 		    /// \brief Skip the reading of node section
 		    ///
 		    /// Omit the reading of the node section. This implies that each node
 		    /// map reading rule will be abandoned, and the nodes of the graph
 		    /// will not be constructed, which usually cause that the edge set
 		    /// could not be read due to lack of node name
 		    /// could not be read due to lack of node name resolving.
 		    /// Therefore \c skipEdges() function should also be used, or
 		    /// \c useNodes() should be used to specify the label of the nodes.
 		    GraphReader& skipNodes() {
 		      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
 		      _skip_nodes = true;
 		      return *this;
+		    }
 		    /// \brief Skip the reading of edge section
 		    ///
 		    /// Omit the reading of the edge section. This implies that each edge
 		    /// map reading rule will be abandoned, and the edges of the graph
 		    /// will not be constructed.
 		    GraphReader& skipEdges() {
 		      LEMON_ASSERT(!_skip_edges, "Skip edges already set");
 		      _skip_edges = true;
 		      return *this;
+		    }
 		    /// @}
@@ -1866,193 +1866,193 @@
 		        if (!_use_edges) {
 		          typename NodeIndex::iterator it;
 		          it = _node_index.find(source_token);
 		          if (it == _node_index.end()) {
 		            std::ostringstream msg;
 		            msg << "Item not found: " << source_token;
 		            throw FormatError(msg.str());
+		          }
 		          Node source = it->second;
 		          it = _node_index.find(target_token);
 		          if (it == _node_index.end()) {
 		            std::ostringstream msg;
 		            msg << "Item not found: " << target_token;
 		            throw FormatError(msg.str());
+		          }
 		          Node target = it->second;
 		          e = _graph.addEdge(source, target);
 		          if (label_index != -1)
 		            _edge_index.insert(std::make_pair(tokens[label_index], e));
 		        } else {
 		          if (label_index == -1)
 		            throw FormatError("Label map not found");
 		          typename std::map<std::string, Edge>::iterator it =
 		            _edge_index.find(tokens[label_index]);
 		          if (it == _edge_index.end()) {
 		            std::ostringstream msg;
 		            msg << "Edge with label not found: " << tokens[label_index];
 		            throw FormatError(msg.str());
+		          }
 		          e = it->second;
+		        }
 		        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
 		          _edge_maps[i].second->set(e, tokens[map_index[i]]);
+		        }
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
+		    }
 		    void readAttributes() {
 		      std::set<std::string> read_attr;
 		      char c;
 		      while (readLine() && line >> c && c != '@') {
 		        line.putback(c);
 		        std::string attr, token;
 		        if (!_reader_bits::readToken(line, attr))
 		          throw FormatError("Attribute name not found");
 		        if (!_reader_bits::readToken(line, token))
 		          throw FormatError("Attribute value not found");
 		        if (line >> c)
 		          throw FormatError("Extra character at the end of line");
+		        {
 		          std::set<std::string>::iterator it = read_attr.find(attr);
 		          if (it != read_attr.end()) {
 		            std::ostringstream msg;
 		            msg << "Multiple occurence of attribute: " << attr;
 		            throw FormatError(msg.str());
+		          }
 		          read_attr.insert(attr);
+		        }
+		        {
 		          typename Attributes::iterator it = _attributes.lower_bound(attr);
 		          while (it != _attributes.end() && it->first == attr) {
 		            it->second->set(token);
 		            ++it;
+		          }
+		        }
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        if (read_attr.find(it->first) == read_attr.end()) {
 		          std::ostringstream msg;
 		          msg << "Attribute not found: " << it->first;
 		          throw FormatError(msg.str());
+		        }
+		      }
+		    }
 		  public:
-		    /// \name Execution of the reader
+		    /// \name Execution of the Reader
 		    /// @{
 		    /// \brief Start the batch processing
 		    ///
 		    /// This function starts the batch processing
 		    void run() {
 		      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
 		      bool nodes_done = _skip_nodes;
 		      bool edges_done = _skip_edges;
 		      bool attributes_done = false;
 		      line_num = 0;
 		      readLine();
 		      skipSection();
 		      while (readSuccess()) {
 		        try {
 		          char c;
 		          std::string section, caption;
 		          line >> c;
 		          _reader_bits::readToken(line, section);
 		          _reader_bits::readToken(line, caption);
 		          if (line >> c)
 		            throw FormatError("Extra character at the end of line");
 		          if (section == "nodes" && !nodes_done) {
 		            if (_nodes_caption.empty() || _nodes_caption == caption) {
 		              readNodes();
 		              nodes_done = true;
+		            }
 		          } else if ((section == "edges" || section == "arcs") &&
 		                     !edges_done) {
 		            if (_edges_caption.empty() || _edges_caption == caption) {
 		              readEdges();
 		              edges_done = true;
+		            }
 		          } else if (section == "attributes" && !attributes_done) {
 		            if (_attributes_caption.empty() || _attributes_caption == caption) {
 		              readAttributes();
 		              attributes_done = true;
+		            }
 		          } else {
 		            readLine();
 		            skipSection();
+		          }
 		        } catch (FormatError& error) {
 		          error.line(line_num);
 		          error.file(_filename);
 		          throw;
+		        }
+		      }
 		      if (!nodes_done) {
 		        throw FormatError("Section @nodes not found");
+		      }
 		      if (!edges_done) {
 		        throw FormatError("Section @edges not found");
+		      }
 		      if (!attributes_done && !_attributes.empty()) {
 		        throw FormatError("Section @attributes not found");
+		      }
+		    }
 		    /// @}
 		  };
 		  /// \brief Return a \ref GraphReader class
 		  ///
 		  /// This function just returns a \ref GraphReader class.
 		  /// \relates GraphReader
 		  template <typename Graph>
 		  GraphReader<Graph> graphReader(Graph& graph, std::istream& is) {
 		    GraphReader<Graph> tmp(graph, is);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref GraphReader class
 		  ///
 		  /// This function just returns a \ref GraphReader class.
 		  /// \relates GraphReader
 		  template <typename Graph>
 		  GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) {
 		    GraphReader<Graph> tmp(graph, fn);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref GraphReader class
 		  ///
 		  /// This function just returns a \ref GraphReader class.
@@ -2065,611 +2065,611 @@
 		  class SectionReader;
 		  SectionReader sectionReader(std::istream& is);
 		  SectionReader sectionReader(const std::string& fn);
 		  SectionReader sectionReader(const char* fn);
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief Section reader class
 		  ///
 		  /// In the \ref lgf-format "LGF" file extra sections can be placed,
 		  /// which contain any data in arbitrary format. Such sections can be
 		  /// read with this class. A reading rule can be added to the class
 		  /// with two different functions. With the \c sectionLines() function a
 		  /// functor can process the section line-by-line, while with the \c
 		  /// sectionStream() member the section can be read from an input
 		  /// stream.
 		  class SectionReader {
 		  private:
 		    std::istream* _is;
 		    bool local_is;
 		    std::string _filename;
 		    typedef std::map<std::string, _reader_bits::Section*> Sections;
 		    Sections _sections;
 		    int line_num;
 		    std::istringstream line;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct a section reader, which reads from the given input
 		    /// stream.
 		    SectionReader(std::istream& is)
 		      : _is(&is), local_is(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct a section reader, which reads from the given file.
 		    SectionReader(const std::string& fn)
 		      : _is(new std::ifstream(fn.c_str())), local_is(true),
 		        _filename(fn) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Construct a section reader, which reads from the given file.
 		    SectionReader(const char* fn)
 		      : _is(new std::ifstream(fn)), local_is(true),
 		        _filename(fn) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Destructor
 		    ~SectionReader() {
 		      for (Sections::iterator it = _sections.begin();
 		           it != _sections.end(); ++it) {
 		        delete it->second;
+		      }
 		      if (local_is) {
 		        delete _is;
+		      }
+		    }
 		  private:
 		    friend SectionReader sectionReader(std::istream& is);
 		    friend SectionReader sectionReader(const std::string& fn);
 		    friend SectionReader sectionReader(const char* fn);
 		    SectionReader(SectionReader& other)
 		      : _is(other._is), local_is(other.local_is) {
 		      other._is = 0;
 		      other.local_is = false;
 		      _sections.swap(other._sections);
+		    }
 		    SectionReader& operator=(const SectionReader&);
 		  public:
-		    /// \name Section readers
+		    /// \name Section Readers
 		    /// @{
 		    /// \brief Add a section processor with line oriented reading
 		    ///
 		    /// The first parameter is the type descriptor of the section, the
 		    /// second is a functor, which takes just one \c std::string
 		    /// parameter. At the reading process, each line of the section
 		    /// will be given to the functor object. However, the empty lines
 		    /// and the comment lines are filtered out, and the leading
 		    /// whitespaces are trimmed from each processed string.
 		    ///
 		    /// For example let's see a section, which contain several
 		    /// integers, which should be inserted into a vector.
 		    ///\code
 		    ///  @numbers
 		    ///  12 45 23
 		    ///  4
 		    ///  23 6
 		    ///\endcode
 		    ///
 		    /// The functor is implemented as a struct:
 		    ///\code
 		    ///  struct NumberSection {
 		    ///    std::vector<int>& _data;
 		    ///    NumberSection(std::vector<int>& data) : _data(data) {}
 		    ///    void operator()(const std::string& line) {
 		    ///      std::istringstream ls(line);
 		    ///      int value;
 		    ///      while (ls >> value) _data.push_back(value);
 		    ///    }
 		    ///  };
 		    ///
 		    ///  // ...
 		    ///
 		    ///  reader.sectionLines("numbers", NumberSection(vec));
 		    ///\endcode
 		    template <typename Functor>
 		    SectionReader& sectionLines(const std::string& type, Functor functor) {
 		      LEMON_ASSERT(!type.empty(), "Type is empty.");
 		      LEMON_ASSERT(_sections.find(type) == _sections.end(),
 		                   "Multiple reading of section.");
 		      _sections.insert(std::make_pair(type,
 		        new _reader_bits::LineSection<Functor>(functor)));
 		      return *this;
+		    }
 		    /// \brief Add a section processor with stream oriented reading
 		    ///
 		    /// The first parameter is the type of the section, the second is
 		    /// a functor, which takes an \c std::istream& and an \c int&
 		    /// parameter, the latter regard to the line number of stream. The
 		    /// functor can read the input while the section go on, and the
 		    /// line number should be modified accordingly.
 		    template <typename Functor>
 		    SectionReader& sectionStream(const std::string& type, Functor functor) {
 		      LEMON_ASSERT(!type.empty(), "Type is empty.");
 		      LEMON_ASSERT(_sections.find(type) == _sections.end(),
 		                   "Multiple reading of section.");
 		      _sections.insert(std::make_pair(type,
 		         new _reader_bits::StreamSection<Functor>(functor)));
 		      return *this;
+		    }
 		    /// @}
 		  private:
 		    bool readLine() {
 		      std::string str;
 		      while(++line_num, std::getline(*_is, str)) {
 		        line.clear(); line.str(str);
 		        char c;
 		        if (line >> std::ws >> c && c != '#') {
 		          line.putback(c);
 		          return true;
+		        }
+		      }
 		      return false;
+		    }
 		    bool readSuccess() {
 		      return static_cast<bool>(*_is);
+		    }
 		    void skipSection() {
 		      char c;
 		      while (readSuccess() && line >> c && c != '@') {
 		        readLine();
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
+		    }
 		  public:
-		    /// \name Execution of the reader
+		    /// \name Execution of the Reader
 		    /// @{
 		    /// \brief Start the batch processing
 		    ///
 		    /// This function starts the batch processing.
 		    void run() {
 		      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
 		      std::set<std::string> extra_sections;
 		      line_num = 0;
 		      readLine();
 		      skipSection();
 		      while (readSuccess()) {
 		        try {
 		          char c;
 		          std::string section, caption;
 		          line >> c;
 		          _reader_bits::readToken(line, section);
 		          _reader_bits::readToken(line, caption);
 		          if (line >> c)
 		            throw FormatError("Extra character at the end of line");
 		          if (extra_sections.find(section) != extra_sections.end()) {
 		            std::ostringstream msg;
 		            msg << "Multiple occurence of section: " << section;
 		            throw FormatError(msg.str());
+		          }
 		          Sections::iterator it = _sections.find(section);
 		          if (it != _sections.end()) {
 		            extra_sections.insert(section);
 		            it->second->process(*_is, line_num);
+		          }
 		          readLine();
 		          skipSection();
 		        } catch (FormatError& error) {
 		          error.line(line_num);
 		          error.file(_filename);
 		          throw;
+		        }
+		      }
 		      for (Sections::iterator it = _sections.begin();
 		           it != _sections.end(); ++it) {
 		        if (extra_sections.find(it->first) == extra_sections.end()) {
 		          std::ostringstream os;
 		          os << "Cannot find section: " << it->first;
 		          throw FormatError(os.str());
+		        }
+		      }
+		    }
 		    /// @}
 		  };
 		  /// \brief Return a \ref SectionReader class
 		  ///
 		  /// This function just returns a \ref SectionReader class.
 		  /// \relates SectionReader
 		  inline SectionReader sectionReader(std::istream& is) {
 		    SectionReader tmp(is);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref SectionReader class
 		  ///
 		  /// This function just returns a \ref SectionReader class.
 		  /// \relates SectionReader
 		  inline SectionReader sectionReader(const std::string& fn) {
 		    SectionReader tmp(fn);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref SectionReader class
 		  ///
 		  /// This function just returns a \ref SectionReader class.
 		  /// \relates SectionReader
 		  inline SectionReader sectionReader(const char* fn) {
 		    SectionReader tmp(fn);
 		    return tmp;
+		  }
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief Reader for the contents of the \ref lgf-format "LGF" file
 		  ///
 		  /// This class can be used to read the sections, the map names and
 		  /// the attributes from a file. Usually, the LEMON programs know
 		  /// that, which type of graph, which maps and which attributes
 		  /// should be read from a file, but in general tools (like glemon)
 		  /// the contents of an LGF file should be guessed somehow. This class
 		  /// reads the graph and stores the appropriate information for
 		  /// reading the graph.
 		  ///
 		  ///\code
 		  /// LgfContents contents("graph.lgf");
 		  /// contents.run();
 		  ///
 		  /// // Does it contain any node section and arc section?
 		  /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
 		  ///   std::cerr << "Failure, cannot find graph." << std::endl;
 		  ///   return -1;
 		  /// }
 		  /// std::cout << "The name of the default node section: "
 		  ///           << contents.nodeSection(0) << std::endl;
 		  /// std::cout << "The number of the arc maps: "
 		  ///           << contents.arcMaps(0).size() << std::endl;
 		  /// std::cout << "The name of second arc map: "
 		  ///           << contents.arcMaps(0)[1] << std::endl;
 		  ///\endcode
 		  class LgfContents {
 		  private:
 		    std::istream* _is;
 		    bool local_is;
 		    std::vector<std::string> _node_sections;
 		    std::vector<std::string> _edge_sections;
 		    std::vector<std::string> _attribute_sections;
 		    std::vector<std::string> _extra_sections;
 		    std::vector<bool> _arc_sections;
 		    std::vector<std::vector<std::string> > _node_maps;
 		    std::vector<std::vector<std::string> > _edge_maps;
 		    std::vector<std::vector<std::string> > _attributes;
 		    int line_num;
 		    std::istringstream line;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct an \e LGF contents reader, which reads from the given
 		    /// input stream.
 		    LgfContents(std::istream& is)
 		      : _is(&is), local_is(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct an \e LGF contents reader, which reads from the given
 		    /// file.
 		    LgfContents(const std::string& fn)
 		      : _is(new std::ifstream(fn.c_str())), local_is(true) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Construct an \e LGF contents reader, which reads from the given
 		    /// file.
 		    LgfContents(const char* fn)
 		      : _is(new std::ifstream(fn)), local_is(true) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Destructor
 		    ~LgfContents() {
 		      if (local_is) delete _is;
+		    }
 		  private:
 		    LgfContents(const LgfContents&);
 		    LgfContents& operator=(const LgfContents&);
 		  public:
-		    /// \name Node sections
+		    /// \name Node Sections
 		    /// @{
 		    /// \brief Gives back the number of node sections in the file.
 		    ///
 		    /// Gives back the number of node sections in the file.
 		    int nodeSectionNum() const {
 		      return _node_sections.size();
+		    }
 		    /// \brief Returns the node section name at the given position.
 		    ///
 		    /// Returns the node section name at the given position.
 		    const std::string& nodeSection(int i) const {
 		      return _node_sections[i];
+		    }
 		    /// \brief Gives back the node maps for the given section.
 		    ///
 		    /// Gives back the node maps for the given section.
 		    const std::vector<std::string>& nodeMapNames(int i) const {
 		      return _node_maps[i];
+		    }
 		    /// @}
-		    /// \name Arc/Edge sections
+		    /// \name Arc/Edge Sections
 		    /// @{
 		    /// \brief Gives back the number of arc/edge sections in the file.
 		    ///
 		    /// Gives back the number of arc/edge sections in the file.
 		    /// \note It is synonym of \c edgeSectionNum().
 		    int arcSectionNum() const {
 		      return _edge_sections.size();
+		    }
 		    /// \brief Returns the arc/edge section name at the given position.
 		    ///
 		    /// Returns the arc/edge section name at the given position.
 		    /// \note It is synonym of \c edgeSection().
 		    const std::string& arcSection(int i) const {
 		      return _edge_sections[i];
+		    }
 		    /// \brief Gives back the arc/edge maps for the given section.
 		    ///
 		    /// Gives back the arc/edge maps for the given section.
 		    /// \note It is synonym of \c edgeMapNames().
 		    const std::vector<std::string>& arcMapNames(int i) const {
 		      return _edge_maps[i];
+		    }
 		    /// @}
 		    /// \name Synonyms
 		    /// @{
 		    /// \brief Gives back the number of arc/edge sections in the file.
 		    ///
 		    /// Gives back the number of arc/edge sections in the file.
 		    /// \note It is synonym of \c arcSectionNum().
 		    int edgeSectionNum() const {
 		      return _edge_sections.size();
+		    }
 		    /// \brief Returns the section name at the given position.
 		    ///
 		    /// Returns the section name at the given position.
 		    /// \note It is synonym of \c arcSection().
 		    const std::string& edgeSection(int i) const {
 		      return _edge_sections[i];
+		    }
 		    /// \brief Gives back the edge maps for the given section.
 		    ///
 		    /// Gives back the edge maps for the given section.
 		    /// \note It is synonym of \c arcMapNames().
 		    const std::vector<std::string>& edgeMapNames(int i) const {
 		      return _edge_maps[i];
+		    }
 		    /// @}
-		    /// \name Attribute sections
+		    /// \name Attribute Sections
 		    /// @{
 		    /// \brief Gives back the number of attribute sections in the file.
 		    ///
 		    /// Gives back the number of attribute sections in the file.
 		    int attributeSectionNum() const {
 		      return _attribute_sections.size();
+		    }
 		    /// \brief Returns the attribute section name at the given position.
 		    ///
 		    /// Returns the attribute section name at the given position.
 		    const std::string& attributeSectionNames(int i) const {
 		      return _attribute_sections[i];
+		    }
 		    /// \brief Gives back the attributes for the given section.
 		    ///
 		    /// Gives back the attributes for the given section.
 		    const std::vector<std::string>& attributes(int i) const {
 		      return _attributes[i];
+		    }
 		    /// @}
-		    /// \name Extra sections
+		    /// \name Extra Sections
 		    /// @{
 		    /// \brief Gives back the number of extra sections in the file.
 		    ///
 		    /// Gives back the number of extra sections in the file.
 		    int extraSectionNum() const {
 		      return _extra_sections.size();
+		    }
 		    /// \brief Returns the extra section type at the given position.
 		    ///
 		    /// Returns the section type at the given position.
 		    const std::string& extraSection(int i) const {
 		      return _extra_sections[i];
+		    }
 		    /// @}
 		  private:
 		    bool readLine() {
 		      std::string str;
 		      while(++line_num, std::getline(*_is, str)) {
 		        line.clear(); line.str(str);
 		        char c;
 		        if (line >> std::ws >> c && c != '#') {
 		          line.putback(c);
 		          return true;
+		        }
+		      }
 		      return false;
+		    }
 		    bool readSuccess() {
 		      return static_cast<bool>(*_is);
+		    }
 		    void skipSection() {
 		      char c;
 		      while (readSuccess() && line >> c && c != '@') {
 		        readLine();
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
+		    }
 		    void readMaps(std::vector<std::string>& maps) {
 		      char c;
 		      if (!readLine() || !(line >> c) || c == '@') {
 		        if (readSuccess() && line) line.putback(c);
 		        return;
+		      }
 		      line.putback(c);
 		      std::string map;
 		      while (_reader_bits::readToken(line, map)) {
 		        maps.push_back(map);
+		      }
+		    }
 		    void readAttributes(std::vector<std::string>& attrs) {
 		      readLine();
 		      char c;
 		      while (readSuccess() && line >> c && c != '@') {
 		        line.putback(c);
 		        std::string attr;
 		        _reader_bits::readToken(line, attr);
 		        attrs.push_back(attr);
 		        readLine();
+		      }
 		      line.putback(c);
+		    }
 		  public:
-		    /// \name Execution of the contents reader
+		    /// \name Execution of the Contents Reader
 		    /// @{
 		    /// \brief Starts the reading
 		    ///
 		    /// This function starts the reading.
 		    void run() {
 		      readLine();
 		      skipSection();
 		      while (readSuccess()) {
 		        char c;
 		        line >> c;
 		        std::string section, caption;
 		        _reader_bits::readToken(line, section);
 		        _reader_bits::readToken(line, caption);
 		        if (section == "nodes") {
 		          _node_sections.push_back(caption);
 		          _node_maps.push_back(std::vector<std::string>());
 		          readMaps(_node_maps.back());
 		          readLine(); skipSection();
 		        } else if (section == "arcs" || section == "edges") {
 		          _edge_sections.push_back(caption);
 		          _arc_sections.push_back(section == "arcs");
 		          _edge_maps.push_back(std::vector<std::string>());
 		          readMaps(_edge_maps.back());
 		          readLine(); skipSection();
 		        } else if (section == "attributes") {
 		          _attribute_sections.push_back(caption);
 		          _attributes.push_back(std::vector<std::string>());
 		          readAttributes(_attributes.back());
 		        } else {
 		          _extra_sections.push_back(section);
 		          readLine(); skipSection();
+		        }
+		      }
+		    }
 		    /// @}
 		  };
+		}
 		#endif

lemon/lgf_writer.h

Show inline comments

@@ -445,323 +445,323 @@
 		    bool _skip_nodes;
 		    bool _skip_arcs;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output stream.
 		    DigraphWriter(const Digraph& digraph, std::ostream& os = std::cout)
 		      : _os(&os), local_os(false), _digraph(digraph),
 		        _skip_nodes(false), _skip_arcs(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output file.
 		    DigraphWriter(const Digraph& digraph, const std::string& fn)
 		      : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
 		        _skip_nodes(false), _skip_arcs(false) {
 		      if (!(*_os)) {
 		        delete _os;
 		        throw IoError("Cannot write file", fn);
+		      }
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output file.
 		    DigraphWriter(const Digraph& digraph, const char* fn)
 		      : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
 		        _skip_nodes(false), _skip_arcs(false) {
 		      if (!(*_os)) {
 		        delete _os;
 		        throw IoError("Cannot write file", fn);
+		      }
+		    }
 		    /// \brief Destructor
 		    ~DigraphWriter() {
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename ArcMaps::iterator it = _arc_maps.begin();
 		           it != _arc_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        delete it->second;
+		      }
 		      if (local_os) {
 		        delete _os;
+		      }
+		    }
 		  private:
 		    template <typename DGR>
 		    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
 		                                            std::ostream& os);
 		    template <typename DGR>
 		    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
 		                                            const std::string& fn);
 		    template <typename DGR>
 		    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
 		                                            const char *fn);
 		    DigraphWriter(DigraphWriter& other)
 		      : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
 		        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
 		      other._os = 0;
 		      other.local_os = false;
 		      _node_index.swap(other._node_index);
 		      _arc_index.swap(other._arc_index);
 		      _node_maps.swap(other._node_maps);
 		      _arc_maps.swap(other._arc_maps);
 		      _attributes.swap(other._attributes);
 		      _nodes_caption = other._nodes_caption;
 		      _arcs_caption = other._arcs_caption;
 		      _attributes_caption = other._attributes_caption;
+		    }
 		    DigraphWriter& operator=(const DigraphWriter&);
 		  public:
-		    /// \name Writing rules
+		    /// \name Writing Rules
 		    /// @{
 		    /// \brief Node map writing rule
 		    ///
 		    /// Add a node map writing rule to the writer.
 		    template <typename Map>
 		    DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Node>* storage =
 		        new _writer_bits::MapStorage<Node, Map>(map);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node map writing rule
 		    ///
 		    /// Add a node map writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Map, typename Converter>
 		    DigraphWriter& nodeMap(const std::string& caption, const Map& map,
 		                           const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Node>* storage =
 		        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map writing rule
 		    ///
 		    /// Add an arc map writing rule to the writer.
 		    template <typename Map>
 		    DigraphWriter& arcMap(const std::string& caption, const Map& map) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Arc>* storage =
 		        new _writer_bits::MapStorage<Arc, Map>(map);
 		      _arc_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map writing rule
 		    ///
 		    /// Add an arc map writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Map, typename Converter>
 		    DigraphWriter& arcMap(const std::string& caption, const Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Arc>* storage =
 		        new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
 		      _arc_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute writing rule
 		    ///
 		    /// Add an attribute writing rule to the writer.
 		    template <typename Value>
 		    DigraphWriter& attribute(const std::string& caption, const Value& value) {
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Value>(value);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute writing rule
 		    ///
 		    /// Add an attribute writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Value, typename Converter>
 		    DigraphWriter& attribute(const std::string& caption, const Value& value,
 		                             const Converter& converter = Converter()) {
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node writing rule
 		    ///
 		    /// Add a node writing rule to the writer.
 		    DigraphWriter& node(const std::string& caption, const Node& node) {
 		      typedef _writer_bits::MapLookUpConverter<Node> Converter;
 		      Converter converter(_node_index);
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc writing rule
 		    ///
 		    /// Add an arc writing rule to writer.
 		    DigraphWriter& arc(const std::string& caption, const Arc& arc) {
 		      typedef _writer_bits::MapLookUpConverter<Arc> Converter;
 		      Converter converter(_arc_index);
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
-		    /// \name Section captions
+		    /// \name Section Captions
 		    /// @{
 		    /// \brief Add an additional caption to the \c \@nodes section
 		    ///
 		    /// Add an additional caption to the \c \@nodes section.
 		    DigraphWriter& nodes(const std::string& caption) {
 		      _nodes_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Add an additional caption to the \c \@arcs section
 		    ///
 		    /// Add an additional caption to the \c \@arcs section.
 		    DigraphWriter& arcs(const std::string& caption) {
 		      _arcs_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Add an additional caption to the \c \@attributes section
 		    ///
 		    /// Add an additional caption to the \c \@attributes section.
 		    DigraphWriter& attributes(const std::string& caption) {
 		      _attributes_caption = caption;
 		      return *this;
+		    }
-		    /// \name Skipping section
+		    /// \name Skipping Section
 		    /// @{
 		    /// \brief Skip writing the node set
 		    ///
 		    /// The \c \@nodes section will not be written to the stream.
 		    DigraphWriter& skipNodes() {
 		      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
 		      _skip_nodes = true;
 		      return *this;
+		    }
 		    /// \brief Skip writing arc set
 		    ///
 		    /// The \c \@arcs section will not be written to the stream.
 		    DigraphWriter& skipArcs() {
 		      LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
 		      _skip_arcs = true;
 		      return *this;
+		    }
 		    /// @}
 		  private:
 		    void writeNodes() {
 		      _writer_bits::MapStorageBase<Node>* label = 0;
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      *_os << "@nodes";
 		      if (!_nodes_caption.empty()) {
 		        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
+		      }
 		      *_os << std::endl;
 		      if (label == 0) {
 		        *_os << "label" << '\t';
+		      }
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << '\t';
+		      }
 		      *_os << std::endl;
 		      std::vector<Node> nodes;
 		      for (NodeIt n(_digraph); n != INVALID; ++n) {
 		        nodes.push_back(n);
+		      }
 		      if (label == 0) {
 		        IdMap<Digraph, Node> id_map(_digraph);
 		        _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
 		        std::sort(nodes.begin(), nodes.end(), id_less);
 		      } else {
 		        label->sort(nodes);
+		      }
 		      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
 		        Node n = nodes[i];
 		        if (label == 0) {
 		          std::ostringstream os;
 		          os << _digraph.id(n);
 		          _writer_bits::writeToken(*_os, os.str());
 		          *_os << '\t';
 		          _node_index.insert(std::make_pair(n, os.str()));
+		        }
 		        for (typename NodeMaps::iterator it = _node_maps.begin();
 		             it != _node_maps.end(); ++it) {
 		          std::string value = it->second->get(n);
 		          _writer_bits::writeToken(*_os, value);
 		          if (it->first == "label") {
 		            _node_index.insert(std::make_pair(n, value));
+		          }
 		          *_os << '\t';
+		        }
 		        *_os << std::endl;
+		      }
+		    }
 		    void createNodeIndex() {
 		      _writer_bits::MapStorageBase<Node>* label = 0;
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      if (label == 0) {
 		        for (NodeIt n(_digraph); n != INVALID; ++n) {
@@ -792,193 +792,193 @@
 		        _writer_bits::writeToken(*_os << ' ', _arcs_caption);
+		      }
 		      *_os << std::endl;
 		      *_os << '\t' << '\t';
 		      if (label == 0) {
 		        *_os << "label" << '\t';
+		      }
 		      for (typename ArcMaps::iterator it = _arc_maps.begin();
 		           it != _arc_maps.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << '\t';
+		      }
 		      *_os << std::endl;
 		      std::vector<Arc> arcs;
 		      for (ArcIt n(_digraph); n != INVALID; ++n) {
 		        arcs.push_back(n);
+		      }
 		      if (label == 0) {
 		        IdMap<Digraph, Arc> id_map(_digraph);
 		        _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
 		        std::sort(arcs.begin(), arcs.end(), id_less);
 		      } else {
 		        label->sort(arcs);
+		      }
 		      for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
 		        Arc a = arcs[i];
 		        _writer_bits::writeToken(*_os, _node_index.
 		                                 find(_digraph.source(a))->second);
 		        *_os << '\t';
 		        _writer_bits::writeToken(*_os, _node_index.
 		                                 find(_digraph.target(a))->second);
 		        *_os << '\t';
 		        if (label == 0) {
 		          std::ostringstream os;
 		          os << _digraph.id(a);
 		          _writer_bits::writeToken(*_os, os.str());
 		          *_os << '\t';
 		          _arc_index.insert(std::make_pair(a, os.str()));
+		        }
 		        for (typename ArcMaps::iterator it = _arc_maps.begin();
 		             it != _arc_maps.end(); ++it) {
 		          std::string value = it->second->get(a);
 		          _writer_bits::writeToken(*_os, value);
 		          if (it->first == "label") {
 		            _arc_index.insert(std::make_pair(a, value));
+		          }
 		          *_os << '\t';
+		        }
 		        *_os << std::endl;
+		      }
+		    }
 		    void createArcIndex() {
 		      _writer_bits::MapStorageBase<Arc>* label = 0;
 		      for (typename ArcMaps::iterator it = _arc_maps.begin();
 		           it != _arc_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      if (label == 0) {
 		        for (ArcIt a(_digraph); a != INVALID; ++a) {
 		          std::ostringstream os;
 		          os << _digraph.id(a);
 		          _arc_index.insert(std::make_pair(a, os.str()));
+		        }
 		      } else {
 		        for (ArcIt a(_digraph); a != INVALID; ++a) {
 		          std::string value = label->get(a);
 		          _arc_index.insert(std::make_pair(a, value));
+		        }
+		      }
+		    }
 		    void writeAttributes() {
 		      if (_attributes.empty()) return;
 		      *_os << "@attributes";
 		      if (!_attributes_caption.empty()) {
 		        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
+		      }
 		      *_os << std::endl;
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << ' ';
 		        _writer_bits::writeToken(*_os, it->second->get());
 		        *_os << std::endl;
+		      }
+		    }
 		  public:
-		    /// \name Execution of the writer
+		    /// \name Execution of the Writer
 		    /// @{
 		    /// \brief Start the batch processing
 		    ///
 		    /// This function starts the batch processing.
 		    void run() {
 		      if (!_skip_nodes) {
 		        writeNodes();
 		      } else {
 		        createNodeIndex();
+		      }
 		      if (!_skip_arcs) {
 		        writeArcs();
 		      } else {
 		        createArcIndex();
+		      }
 		      writeAttributes();
+		    }
 		    /// \brief Give back the stream of the writer
 		    ///
 		    /// Give back the stream of the writer.
 		    std::ostream& ostream() {
 		      return *_os;
+		    }
 		    /// @}
 		  };
 		  /// \brief Return a \ref DigraphWriter class
 		  ///
 		  /// This function just returns a \ref DigraphWriter class.
 		  /// \relates DigraphWriter
 		  template <typename Digraph>
 		  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
 		                                       std::ostream& os) {
 		    DigraphWriter<Digraph> tmp(digraph, os);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref DigraphWriter class
 		  ///
 		  /// This function just returns a \ref DigraphWriter class.
 		  /// \relates DigraphWriter
 		  template <typename Digraph>
 		  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
 		                                       const std::string& fn) {
 		    DigraphWriter<Digraph> tmp(digraph, fn);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref DigraphWriter class
 		  ///
 		  /// This function just returns a \ref DigraphWriter class.
 		  /// \relates DigraphWriter
 		  template <typename Digraph>
 		  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
 		                                       const char* fn) {
 		    DigraphWriter<Digraph> tmp(digraph, fn);
 		    return tmp;
+		  }
 		  template <typename Graph>
 		  class GraphWriter;
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph,
 		                                 std::ostream& os = std::cout);
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn);
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn);
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief \ref lgf-format "LGF" writer for directed graphs
 		  ///
 		  /// This utility writes an \ref lgf-format "LGF" file.
 		  ///
 		  /// It can be used almost the same way as \c DigraphWriter.
 		  /// The only difference is that this class can handle edges and
 		  /// edge maps as well as arcs and arc maps.
 		  ///
 		  /// The arc maps are written into the file as two columns, the
 		  /// caption of the columns are the name of the map prefixed with \c
 		  /// '+' and \c '-'. The arcs are written into the \c \@attributes
 		  /// section as a \c '+' or a \c '-' prefix (depends on the direction
 		  /// of the arc) and the label of corresponding edge.
 		  template <typename GR>
 		  class GraphWriter {
 		  public:
 		    typedef GR Graph;
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  private:
@@ -1013,369 +1013,369 @@
 		    bool _skip_nodes;
 		    bool _skip_edges;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output stream.
 		    GraphWriter(const Graph& graph, std::ostream& os = std::cout)
 		      : _os(&os), local_os(false), _graph(graph),
 		        _skip_nodes(false), _skip_edges(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output file.
 		    GraphWriter(const Graph& graph, const std::string& fn)
 		      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
 		        _skip_nodes(false), _skip_edges(false) {
 		      if (!(*_os)) {
 		        delete _os;
 		        throw IoError("Cannot write file", fn);
+		      }
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output file.
 		    GraphWriter(const Graph& graph, const char* fn)
 		      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
 		        _skip_nodes(false), _skip_edges(false) {
 		      if (!(*_os)) {
 		        delete _os;
 		        throw IoError("Cannot write file", fn);
+		      }
+		    }
 		    /// \brief Destructor
 		    ~GraphWriter() {
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename EdgeMaps::iterator it = _edge_maps.begin();
 		           it != _edge_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        delete it->second;
+		      }
 		      if (local_os) {
 		        delete _os;
+		      }
+		    }
 		  private:
 		    template <typename Graph>
 		    friend GraphWriter<Graph> graphWriter(const Graph& graph,
 		                                          std::ostream& os);
 		    template <typename Graph>
 		    friend GraphWriter<Graph> graphWriter(const Graph& graph,
 		                                          const std::string& fn);
 		    template <typename Graph>
 		    friend GraphWriter<Graph> graphWriter(const Graph& graph,
 		                                          const char *fn);
 		    GraphWriter(GraphWriter& other)
 		      : _os(other._os), local_os(other.local_os), _graph(other._graph),
 		        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
 		      other._os = 0;
 		      other.local_os = false;
 		      _node_index.swap(other._node_index);
 		      _edge_index.swap(other._edge_index);
 		      _node_maps.swap(other._node_maps);
 		      _edge_maps.swap(other._edge_maps);
 		      _attributes.swap(other._attributes);
 		      _nodes_caption = other._nodes_caption;
 		      _edges_caption = other._edges_caption;
 		      _attributes_caption = other._attributes_caption;
+		    }
 		    GraphWriter& operator=(const GraphWriter&);
 		  public:
-		    /// \name Writing rules
+		    /// \name Writing Rules
 		    /// @{
 		    /// \brief Node map writing rule
 		    ///
 		    /// Add a node map writing rule to the writer.
 		    template <typename Map>
 		    GraphWriter& nodeMap(const std::string& caption, const Map& map) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Node>* storage =
 		        new _writer_bits::MapStorage<Node, Map>(map);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node map writing rule
 		    ///
 		    /// Add a node map writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Map, typename Converter>
 		    GraphWriter& nodeMap(const std::string& caption, const Map& map,
 		                           const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Node>* storage =
 		        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge map writing rule
 		    ///
 		    /// Add an edge map writing rule to the writer.
 		    template <typename Map>
 		    GraphWriter& edgeMap(const std::string& caption, const Map& map) {
 		      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Edge>* storage =
 		        new _writer_bits::MapStorage<Edge, Map>(map);
 		      _edge_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge map writing rule
 		    ///
 		    /// Add an edge map writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Map, typename Converter>
 		    GraphWriter& edgeMap(const std::string& caption, const Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Edge>* storage =
 		        new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
 		      _edge_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map writing rule
 		    ///
 		    /// Add an arc map writing rule to the writer.
 		    template <typename Map>
 		    GraphWriter& arcMap(const std::string& caption, const Map& map) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Edge>* forward_storage =
 		        new _writer_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
 		      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
 		      _writer_bits::MapStorageBase<Edge>* backward_storage =
 		        new _writer_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
 		      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
 		      return *this;
+		    }
 		    /// \brief Arc map writing rule
 		    ///
 		    /// Add an arc map writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Map, typename Converter>
 		    GraphWriter& arcMap(const std::string& caption, const Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Edge>* forward_storage =
 		        new _writer_bits::GraphArcMapStorage<Graph, true, Map, Converter>
 		        (_graph, map, converter);
 		      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
 		      _writer_bits::MapStorageBase<Edge>* backward_storage =
 		        new _writer_bits::GraphArcMapStorage<Graph, false, Map, Converter>
 		        (_graph, map, converter);
 		      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
 		      return *this;
+		    }
 		    /// \brief Attribute writing rule
 		    ///
 		    /// Add an attribute writing rule to the writer.
 		    template <typename Value>
 		    GraphWriter& attribute(const std::string& caption, const Value& value) {
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Value>(value);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute writing rule
 		    ///
 		    /// Add an attribute writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Value, typename Converter>
 		    GraphWriter& attribute(const std::string& caption, const Value& value,
 		                             const Converter& converter = Converter()) {
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node writing rule
 		    ///
 		    /// Add a node writing rule to the writer.
 		    GraphWriter& node(const std::string& caption, const Node& node) {
 		      typedef _writer_bits::MapLookUpConverter<Node> Converter;
 		      Converter converter(_node_index);
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge writing rule
 		    ///
 		    /// Add an edge writing rule to writer.
 		    GraphWriter& edge(const std::string& caption, const Edge& edge) {
 		      typedef _writer_bits::MapLookUpConverter<Edge> Converter;
 		      Converter converter(_edge_index);
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc writing rule
 		    ///
 		    /// Add an arc writing rule to writer.
 		    GraphWriter& arc(const std::string& caption, const Arc& arc) {
 		      typedef _writer_bits::GraphArcLookUpConverter<Graph> Converter;
 		      Converter converter(_graph, _edge_index);
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
-		    /// \name Section captions
+		    /// \name Section Captions
 		    /// @{
 		    /// \brief Add an additional caption to the \c \@nodes section
 		    ///
 		    /// Add an additional caption to the \c \@nodes section.
 		    GraphWriter& nodes(const std::string& caption) {
 		      _nodes_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Add an additional caption to the \c \@arcs section
 		    ///
 		    /// Add an additional caption to the \c \@arcs section.
 		    GraphWriter& edges(const std::string& caption) {
 		      _edges_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Add an additional caption to the \c \@attributes section
 		    ///
 		    /// Add an additional caption to the \c \@attributes section.
 		    GraphWriter& attributes(const std::string& caption) {
 		      _attributes_caption = caption;
 		      return *this;
+		    }
-		    /// \name Skipping section
+		    /// \name Skipping Section
 		    /// @{
 		    /// \brief Skip writing the node set
 		    ///
 		    /// The \c \@nodes section will not be written to the stream.
 		    GraphWriter& skipNodes() {
 		      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
 		      _skip_nodes = true;
 		      return *this;
+		    }
 		    /// \brief Skip writing edge set
 		    ///
 		    /// The \c \@edges section will not be written to the stream.
 		    GraphWriter& skipEdges() {
 		      LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
 		      _skip_edges = true;
 		      return *this;
+		    }
 		    /// @}
 		  private:
 		    void writeNodes() {
 		      _writer_bits::MapStorageBase<Node>* label = 0;
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      *_os << "@nodes";
 		      if (!_nodes_caption.empty()) {
 		        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
+		      }
 		      *_os << std::endl;
 		      if (label == 0) {
 		        *_os << "label" << '\t';
+		      }
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << '\t';
+		      }
 		      *_os << std::endl;
 		      std::vector<Node> nodes;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        nodes.push_back(n);
+		      }
 		      if (label == 0) {
 		        IdMap<Graph, Node> id_map(_graph);
 		        _writer_bits::MapLess<IdMap<Graph, Node> > id_less(id_map);
 		        std::sort(nodes.begin(), nodes.end(), id_less);
 		      } else {
 		        label->sort(nodes);
+		      }
 		      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
 		        Node n = nodes[i];
 		        if (label == 0) {
 		          std::ostringstream os;
 		          os << _graph.id(n);
 		          _writer_bits::writeToken(*_os, os.str());
 		          *_os << '\t';
 		          _node_index.insert(std::make_pair(n, os.str()));
+		        }
 		        for (typename NodeMaps::iterator it = _node_maps.begin();
 		             it != _node_maps.end(); ++it) {
 		          std::string value = it->second->get(n);
 		          _writer_bits::writeToken(*_os, value);
 		          if (it->first == "label") {
 		            _node_index.insert(std::make_pair(n, value));
+		          }
 		          *_os << '\t';
+		        }
 		        *_os << std::endl;
+		      }
+		    }
 		    void createNodeIndex() {
 		      _writer_bits::MapStorageBase<Node>* label = 0;
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      if (label == 0) {
 		        for (NodeIt n(_graph); n != INVALID; ++n) {
@@ -1406,372 +1406,372 @@
 		        _writer_bits::writeToken(*_os << ' ', _edges_caption);
+		      }
 		      *_os << std::endl;
 		      *_os << '\t' << '\t';
 		      if (label == 0) {
 		        *_os << "label" << '\t';
+		      }
 		      for (typename EdgeMaps::iterator it = _edge_maps.begin();
 		           it != _edge_maps.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << '\t';
+		      }
 		      *_os << std::endl;
 		      std::vector<Edge> edges;
 		      for (EdgeIt n(_graph); n != INVALID; ++n) {
 		        edges.push_back(n);
+		      }
 		      if (label == 0) {
 		        IdMap<Graph, Edge> id_map(_graph);
 		        _writer_bits::MapLess<IdMap<Graph, Edge> > id_less(id_map);
 		        std::sort(edges.begin(), edges.end(), id_less);
 		      } else {
 		        label->sort(edges);
+		      }
 		      for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
 		        Edge e = edges[i];
 		        _writer_bits::writeToken(*_os, _node_index.
 		                                 find(_graph.u(e))->second);
 		        *_os << '\t';
 		        _writer_bits::writeToken(*_os, _node_index.
 		                                 find(_graph.v(e))->second);
 		        *_os << '\t';
 		        if (label == 0) {
 		          std::ostringstream os;
 		          os << _graph.id(e);
 		          _writer_bits::writeToken(*_os, os.str());
 		          *_os << '\t';
 		          _edge_index.insert(std::make_pair(e, os.str()));
+		        }
 		        for (typename EdgeMaps::iterator it = _edge_maps.begin();
 		             it != _edge_maps.end(); ++it) {
 		          std::string value = it->second->get(e);
 		          _writer_bits::writeToken(*_os, value);
 		          if (it->first == "label") {
 		            _edge_index.insert(std::make_pair(e, value));
+		          }
 		          *_os << '\t';
+		        }
 		        *_os << std::endl;
+		      }
+		    }
 		    void createEdgeIndex() {
 		      _writer_bits::MapStorageBase<Edge>* label = 0;
 		      for (typename EdgeMaps::iterator it = _edge_maps.begin();
 		           it != _edge_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      if (label == 0) {
 		        for (EdgeIt e(_graph); e != INVALID; ++e) {
 		          std::ostringstream os;
 		          os << _graph.id(e);
 		          _edge_index.insert(std::make_pair(e, os.str()));
+		        }
 		      } else {
 		        for (EdgeIt e(_graph); e != INVALID; ++e) {
 		          std::string value = label->get(e);
 		          _edge_index.insert(std::make_pair(e, value));
+		        }
+		      }
+		    }
 		    void writeAttributes() {
 		      if (_attributes.empty()) return;
 		      *_os << "@attributes";
 		      if (!_attributes_caption.empty()) {
 		        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
+		      }
 		      *_os << std::endl;
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << ' ';
 		        _writer_bits::writeToken(*_os, it->second->get());
 		        *_os << std::endl;
+		      }
+		    }
 		  public:
-		    /// \name Execution of the writer
+		    /// \name Execution of the Writer
 		    /// @{
 		    /// \brief Start the batch processing
 		    ///
 		    /// This function starts the batch processing.
 		    void run() {
 		      if (!_skip_nodes) {
 		        writeNodes();
 		      } else {
 		        createNodeIndex();
+		      }
 		      if (!_skip_edges) {
 		        writeEdges();
 		      } else {
 		        createEdgeIndex();
+		      }
 		      writeAttributes();
+		    }
 		    /// \brief Give back the stream of the writer
 		    ///
 		    /// Give back the stream of the writer
 		    std::ostream& ostream() {
 		      return *_os;
+		    }
 		    /// @}
 		  };
 		  /// \brief Return a \ref GraphWriter class
 		  ///
 		  /// This function just returns a \ref GraphWriter class.
 		  /// \relates GraphWriter
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph,
 		                                 std::ostream& os) {
 		    GraphWriter<Graph> tmp(graph, os);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref GraphWriter class
 		  ///
 		  /// This function just returns a \ref GraphWriter class.
 		  /// \relates GraphWriter
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn) {
 		    GraphWriter<Graph> tmp(graph, fn);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref GraphWriter class
 		  ///
 		  /// This function just returns a \ref GraphWriter class.
 		  /// \relates GraphWriter
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn) {
 		    GraphWriter<Graph> tmp(graph, fn);
 		    return tmp;
+		  }
 		  class SectionWriter;
 		  SectionWriter sectionWriter(std::istream& is);
 		  SectionWriter sectionWriter(const std::string& fn);
 		  SectionWriter sectionWriter(const char* fn);
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief Section writer class
 		  ///
 		  /// In the \ref lgf-format "LGF" file extra sections can be placed,
 		  /// which contain any data in arbitrary format. Such sections can be
 		  /// written with this class. A writing rule can be added to the
 		  /// class with two different functions. With the \c sectionLines()
 		  /// function a generator can write the section line-by-line, while
 		  /// with the \c sectionStream() member the section can be written to
 		  /// an output stream.
 		  class SectionWriter {
 		  private:
 		    std::ostream* _os;
 		    bool local_os;
 		    typedef std::vector<std::pair<std::string, _writer_bits::Section*> >
 		    Sections;
 		    Sections _sections;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct a section writer, which writes to the given output
 		    /// stream.
 		    SectionWriter(std::ostream& os)
 		      : _os(&os), local_os(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct a section writer, which writes into the given file.
 		    SectionWriter(const std::string& fn)
 		      : _os(new std::ofstream(fn.c_str())), local_os(true) {
 		      if (!(*_os)) {
 		        delete _os;
 		        throw IoError("Cannot write file", fn);
+		      }
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Construct a section writer, which writes into the given file.
 		    SectionWriter(const char* fn)
 		      : _os(new std::ofstream(fn)), local_os(true) {
 		      if (!(*_os)) {
 		        delete _os;
 		        throw IoError("Cannot write file", fn);
+		      }
+		    }
 		    /// \brief Destructor
 		    ~SectionWriter() {
 		      for (Sections::iterator it = _sections.begin();
 		           it != _sections.end(); ++it) {
 		        delete it->second;
+		      }
 		      if (local_os) {
 		        delete _os;
+		      }
+		    }
 		  private:
 		    friend SectionWriter sectionWriter(std::ostream& os);
 		    friend SectionWriter sectionWriter(const std::string& fn);
 		    friend SectionWriter sectionWriter(const char* fn);
 		    SectionWriter(SectionWriter& other)
 		      : _os(other._os), local_os(other.local_os) {
 		      other._os = 0;
 		      other.local_os = false;
 		      _sections.swap(other._sections);
+		    }
 		    SectionWriter& operator=(const SectionWriter&);
 		  public:
-		    /// \name Section writers
+		    /// \name Section Writers
 		    /// @{
 		    /// \brief Add a section writer with line oriented writing
 		    ///
 		    /// The first parameter is the type descriptor of the section, the
 		    /// second is a generator with std::string values. At the writing
 		    /// process, the returned \c std::string will be written into the
 		    /// output file until it is an empty string.
 		    ///
 		    /// For example, an integer vector is written into a section.
 		    ///\code
 		    ///  @numbers
 		    ///  12 45 23 78
 		    ///  4 28 38 28
 		    ///  23 6 16
 		    ///\endcode
 		    ///
 		    /// The generator is implemented as a struct.
 		    ///\code
 		    ///  struct NumberSection {
 		    ///    std::vector<int>::const_iterator _it, _end;
 		    ///    NumberSection(const std::vector<int>& data)
 		    ///      : _it(data.begin()), _end(data.end()) {}
 		    ///    std::string operator()() {
 		    ///      int rem_in_line = 4;
 		    ///      std::ostringstream ls;
 		    ///      while (rem_in_line > 0 && _it != _end) {
 		    ///        ls << *(_it++) << ' ';
 		    ///        --rem_in_line;
 		    ///      }
 		    ///      return ls.str();
 		    ///    }
 		    ///  };
 		    ///
 		    ///  // ...
 		    ///
 		    ///  writer.sectionLines("numbers", NumberSection(vec));
 		    ///\endcode
 		    template <typename Functor>
 		    SectionWriter& sectionLines(const std::string& type, Functor functor) {
 		      LEMON_ASSERT(!type.empty(), "Type is empty.");
 		      _sections.push_back(std::make_pair(type,
 		        new _writer_bits::LineSection<Functor>(functor)));
 		      return *this;
+		    }
 		    /// \brief Add a section writer with stream oriented writing
 		    ///
 		    /// The first parameter is the type of the section, the second is
 		    /// a functor, which takes a \c std::ostream& parameter. The
 		    /// functor writes the section to the output stream.
 		    /// \warning The last line must be closed with end-line character.
 		    template <typename Functor>
 		    SectionWriter& sectionStream(const std::string& type, Functor functor) {
 		      LEMON_ASSERT(!type.empty(), "Type is empty.");
 		      _sections.push_back(std::make_pair(type,
 		         new _writer_bits::StreamSection<Functor>(functor)));
 		      return *this;
+		    }
 		    /// @}
 		  public:
-		    /// \name Execution of the writer
+		    /// \name Execution of the Writer
 		    /// @{
 		    /// \brief Start the batch processing
 		    ///
 		    /// This function starts the batch processing.
 		    void run() {
 		      LEMON_ASSERT(_os != 0, "This writer is assigned to an other writer");
 		      for (Sections::iterator it = _sections.begin();
 		           it != _sections.end(); ++it) {
 		        (*_os) << '@' << it->first << std::endl;
 		        it->second->process(*_os);
+		      }
+		    }
 		    /// \brief Give back the stream of the writer
 		    ///
 		    /// Returns the stream of the writer
 		    std::ostream& ostream() {
 		      return *_os;
+		    }
 		    /// @}
 		  };
 		  /// \brief Return a \ref SectionWriter class
 		  ///
 		  /// This function just returns a \ref SectionWriter class.
 		  /// \relates SectionWriter
 		  inline SectionWriter sectionWriter(std::ostream& os) {
 		    SectionWriter tmp(os);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref SectionWriter class
 		  ///
 		  /// This function just returns a \ref SectionWriter class.
 		  /// \relates SectionWriter
 		  inline SectionWriter sectionWriter(const std::string& fn) {
 		    SectionWriter tmp(fn);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref SectionWriter class
 		  ///
 		  /// This function just returns a \ref SectionWriter class.
 		  /// \relates SectionWriter
 		  inline SectionWriter sectionWriter(const char* fn) {
 		    SectionWriter tmp(fn);
 		    return tmp;
+		  }
+		}
 		#endif

lemon/lp_base.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * 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_LP_BASE_H
 		#define LEMON_LP_BASE_H
 		#include<iostream>
 		#include<vector>
 		#include<map>
 		#include<limits>
 		#include<lemon/math.h>
 		#include<lemon/error.h>
 		#include<lemon/assert.h>
 		#include<lemon/core.h>
 		#include<lemon/bits/solver_bits.h>
 		///\file
 		///\brief The interface of the LP solver interface.
 		///\ingroup lp_group
 		namespace lemon {
 		  ///Common base class for LP and MIP solvers
 		  ///Usually this class is not used directly, please use one of the concrete
 		  ///implementations of the solver interface.
 		  ///\ingroup lp_group
 		  class LpBase {
 		  protected:
 		    _solver_bits::VarIndex rows;
 		    _solver_bits::VarIndex cols;
 		  public:
 		    ///Possible outcomes of an LP solving procedure
 		    enum SolveExitStatus {
-		      ///This means that the problem has been successfully solved: either
+		      /// = 0. It means that the problem has been successfully solved: either
 		      ///an optimal solution has been found or infeasibility/unboundedness
 		      ///has been proved.
 		      SOLVED = 0,
 		      ///Any other case (including the case when some user specified
 		      ///limit has been exceeded)
 		      /// = 1. Any other case (including the case when some user specified
 		      ///limit has been exceeded).
 		      UNSOLVED = 1
 		    };
 		    ///Direction of the optimization
 		    enum Sense {
 		      /// Minimization
 		      MIN,
 		      /// Maximization
 		      MAX
 		    };
 		    ///Enum for \c messageLevel() parameter
 		    enum MessageLevel {
-		      /// no output (default value)
+		      /// No output (default value).
 		      MESSAGE_NOTHING,
-		      /// error messages only
+		      /// Error messages only.
 		      MESSAGE_ERROR,
-		      /// warnings
+		      /// Warnings.
 		      MESSAGE_WARNING,
-		      /// normal output
+		      /// Normal output.
 		      MESSAGE_NORMAL,
-		      /// verbose output
+		      /// Verbose output.
 		      MESSAGE_VERBOSE
 		    };
 		    ///The floating point type used by the solver
 		    typedef double Value;
 		    ///The infinity constant
 		    static const Value INF;
 		    ///The not a number constant
 		    static const Value NaN;
 		    friend class Col;
 		    friend class ColIt;
 		    friend class Row;
 		    friend class RowIt;
 		    ///Refer to a column of the LP.
 		    ///This type is used to refer to a column of the LP.
 		    ///
 		    ///Its value remains valid and correct even after the addition or erase of
 		    ///other columns.
 		    ///
 		    ///\note This class is similar to other Item types in LEMON, like
 		    ///Node and Arc types in digraph.
 		    class Col {
 		      friend class LpBase;
 		    protected:
 		      int _id;
 		      explicit Col(int id) : _id(id) {}
 		    public:
 		      typedef Value ExprValue;
 		      typedef True LpCol;
 		      /// Default constructor
 		      /// \warning The default constructor sets the Col to an
 		      /// undefined value.
 		      Col() {}
 		      /// Invalid constructor \& conversion.
 		      /// This constructor initializes the Col to be invalid.
 		      /// \sa Invalid for more details.
 		      Col(const Invalid&) : _id(-1) {}
 		      /// Equality operator
 		      /// Two \ref Col "Col"s are equal if and only if they point to
 		      /// the same LP column or both are invalid.
 		      bool operator==(Col c) const  {return _id == c._id;}
 		      /// Inequality operator
 		      /// \sa operator==(Col c)
 		      ///
 		      bool operator!=(Col c) const  {return _id != c._id;}
 		      /// Artificial ordering operator.
 		      /// To allow the use of this object 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<(Col c) const  {return _id < c._id;}
 		    };
 		    ///Iterator for iterate over the columns of an LP problem
 		    /// Its usage is quite simple, for example you can count the number
 		    /// of columns in an LP \c lp:
 		    ///\code
 		    /// int count=0;
 		    /// for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count;
 		    ///\endcode
 		    class ColIt : public Col {
 		      const LpBase *_solver;
 		    public:
 		      /// Default constructor
 		      /// \warning The default constructor sets the iterator
 		      /// to an undefined value.
 		      ColIt() {}
 		      /// Sets the iterator to the first Col
 		      /// Sets the iterator to the first Col.
 		      ///
 		      ColIt(const LpBase &solver) : _solver(&solver)
+		      {
 		        _solver->cols.firstItem(_id);
+		      }
 		      /// Invalid constructor \& conversion
 		      /// Initialize the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      ColIt(const Invalid&) : Col(INVALID) {}
 		      /// Next column
 		      /// Assign the iterator to the next column.
@@ -912,193 +912,193 @@
 		      ExprIterator& operator++() { ++_host_it; return *this; }
 		      ExprIterator operator++(int) {
 		        ExprIterator tmp(*this); ++_host_it; return tmp;
+		      }
 		      ExprIterator& operator--() { --_host_it; return *this; }
 		      ExprIterator operator--(int) {
 		        ExprIterator tmp(*this); --_host_it; return tmp;
+		      }
 		      bool operator==(const ExprIterator& it) const {
 		        return _host_it == it._host_it;
+		      }
 		      bool operator!=(const ExprIterator& it) const {
 		        return _host_it != it._host_it;
+		      }
 		    };
 		  protected:
 		    //Abstract virtual functions
 		    virtual int _addColId(int col) { return cols.addIndex(col); }
 		    virtual int _addRowId(int row) { return rows.addIndex(row); }
 		    virtual void _eraseColId(int col) { cols.eraseIndex(col); }
 		    virtual void _eraseRowId(int row) { rows.eraseIndex(row); }
 		    virtual int _addCol() = 0;
 		    virtual int _addRow() = 0;
 		    virtual void _eraseCol(int col) = 0;
 		    virtual void _eraseRow(int row) = 0;
 		    virtual void _getColName(int col, std::string& name) const = 0;
 		    virtual void _setColName(int col, const std::string& name) = 0;
 		    virtual int _colByName(const std::string& name) const = 0;
 		    virtual void _getRowName(int row, std::string& name) const = 0;
 		    virtual void _setRowName(int row, const std::string& name) = 0;
 		    virtual int _rowByName(const std::string& name) const = 0;
 		    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e) = 0;
 		    virtual void _getRowCoeffs(int i, InsertIterator b) const = 0;
 		    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e) = 0;
 		    virtual void _getColCoeffs(int i, InsertIterator b) const = 0;
 		    virtual void _setCoeff(int row, int col, Value value) = 0;
 		    virtual Value _getCoeff(int row, int col) const = 0;
 		    virtual void _setColLowerBound(int i, Value value) = 0;
 		    virtual Value _getColLowerBound(int i) const = 0;
 		    virtual void _setColUpperBound(int i, Value value) = 0;
 		    virtual Value _getColUpperBound(int i) const = 0;
 		    virtual void _setRowLowerBound(int i, Value value) = 0;
 		    virtual Value _getRowLowerBound(int i) const = 0;
 		    virtual void _setRowUpperBound(int i, Value value) = 0;
 		    virtual Value _getRowUpperBound(int i) const = 0;
 		    virtual void _setObjCoeffs(ExprIterator b, ExprIterator e) = 0;
 		    virtual void _getObjCoeffs(InsertIterator b) const = 0;
 		    virtual void _setObjCoeff(int i, Value obj_coef) = 0;
 		    virtual Value _getObjCoeff(int i) const = 0;
 		    virtual void _setSense(Sense) = 0;
 		    virtual Sense _getSense() const = 0;
 		    virtual void _clear() = 0;
 		    virtual const char* _solverName() const = 0;
 		    virtual void _messageLevel(MessageLevel level) = 0;
 		    //Own protected stuff
 		    //Constant component of the objective function
 		    Value obj_const_comp;
 		    LpBase() : rows(), cols(), obj_const_comp(0) {}
 		  public:
 		    /// Virtual destructor
 		    virtual ~LpBase() {}
 		    ///Gives back the name of the solver.
 		    const char* solverName() const {return _solverName();}
-		    ///\name Build up and modify the LP
+		    ///\name Build Up and Modify the LP
 		    ///@{
 		    ///Add a new empty column (i.e a new variable) to the LP
 		    Col addCol() { Col c; c._id = _addColId(_addCol()); return c;}
 		    ///\brief Adds several new columns (i.e variables) at once
 		    ///
 		    ///This magic function takes a container as its argument and fills
 		    ///its elements with new columns (i.e. variables)
 		    ///\param t can be
 		    ///- a standard STL compatible iterable container with
 		    ///\ref Col as its \c values_type like
 		    ///\code
 		    ///std::vector<LpBase::Col>
 		    ///std::list<LpBase::Col>
 		    ///\endcode
 		    ///- a standard STL compatible iterable container with
 		    ///\ref Col as its \c mapped_type like
 		    ///\code
 		    ///std::map<AnyType,LpBase::Col>
 		    ///\endcode
 		    ///- an iterable lemon \ref concepts::WriteMap "write map" like
 		    ///\code
 		    ///ListGraph::NodeMap<LpBase::Col>
 		    ///ListGraph::ArcMap<LpBase::Col>
 		    ///\endcode
 		    ///\return The number of the created column.
 		#ifdef DOXYGEN
 		    template<class T>
 		    int addColSet(T &t) { return 0;}
 		#else
 		    template<class T>
 		    typename enable_if<typename T::value_type::LpCol,int>::type
 		    addColSet(T &t,dummy<0> = 0) {
 		      int s=0;
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
 		      return s;
+		    }
 		    template<class T>
 		    typename enable_if<typename T::value_type::second_type::LpCol,
 		                       int>::type
 		    addColSet(T &t,dummy<1> = 1) {
 		      int s=0;
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {
 		        i->second=addCol();
 		        s++;
+		      }
 		      return s;
+		    }
 		    template<class T>
 		    typename enable_if<typename T::MapIt::Value::LpCol,
 		                       int>::type
 		    addColSet(T &t,dummy<2> = 2) {
 		      int s=0;
 		      for(typename T::MapIt i(t); i!=INVALID; ++i)
+		        {
 		          i.set(addCol());
 		          s++;
+		        }
 		      return s;
+		    }
 		#endif
 		    ///Set a column (i.e a dual constraint) of the LP
 		    ///\param c is the column to be modified
 		    ///\param e is a dual linear expression (see \ref DualExpr)
 		    ///a better one.
 		    void col(Col c, const DualExpr &e) {
 		      e.simplify();
 		      _setColCoeffs(cols(id(c)), ExprIterator(e.comps.begin(), rows),
 		                    ExprIterator(e.comps.end(), rows));
+		    }
 		    ///Get a column (i.e a dual constraint) of the LP
 		    ///\param c is the column to get
 		    ///\return the dual expression associated to the column
 		    DualExpr col(Col c) const {
 		      DualExpr e;
 		      _getColCoeffs(cols(id(c)), InsertIterator(e.comps, rows));
 		      return e;
+		    }
 		    ///Add a new column to the LP
 		    ///\param e is a dual linear expression (see \ref DualExpr)
 		    ///\param o is the corresponding component of the objective
 		    ///function. It is 0 by default.
 		    ///\return The created column.
 		    Col addCol(const DualExpr &e, Value o = 0) {
 		      Col c=addCol();
 		      col(c,e);
 		      objCoeff(c,o);
 		      return c;
@@ -1695,395 +1695,394 @@
 		    tmp.upperBound()=n;
 		    return tmp;
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Value &n,
 		                                   const LpBase::Constr &c) {
 		    LpBase::Constr tmp(c);
 		    LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint");
 		    tmp.upperBound()=n;
 		    return tmp;
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Constr &c,
 		                                   const LpBase::Value &n)
+		  {
 		    LpBase::Constr tmp(c);
 		    LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint");
 		    tmp.lowerBound()=n;
 		    return tmp;
+		  }
 		  ///Addition
 		  ///\relates LpBase::DualExpr
 		  ///
 		  inline LpBase::DualExpr operator+(const LpBase::DualExpr &a,
 		                                    const LpBase::DualExpr &b) {
 		    LpBase::DualExpr tmp(a);
 		    tmp+=b;
 		    return tmp;
+		  }
 		  ///Substraction
 		  ///\relates LpBase::DualExpr
 		  ///
 		  inline LpBase::DualExpr operator-(const LpBase::DualExpr &a,
 		                                    const LpBase::DualExpr &b) {
 		    LpBase::DualExpr tmp(a);
 		    tmp-=b;
 		    return tmp;
+		  }
 		  ///Multiply with constant
 		  ///\relates LpBase::DualExpr
 		  ///
 		  inline LpBase::DualExpr operator*(const LpBase::DualExpr &a,
 		                                    const LpBase::Value &b) {
 		    LpBase::DualExpr tmp(a);
 		    tmp*=b;
 		    return tmp;
+		  }
 		  ///Multiply with constant
 		  ///\relates LpBase::DualExpr
 		  ///
 		  inline LpBase::DualExpr operator*(const LpBase::Value &a,
 		                                    const LpBase::DualExpr &b) {
 		    LpBase::DualExpr tmp(b);
 		    tmp*=a;
 		    return tmp;
+		  }
 		  ///Divide with constant
 		  ///\relates LpBase::DualExpr
 		  ///
 		  inline LpBase::DualExpr operator/(const LpBase::DualExpr &a,
 		                                    const LpBase::Value &b) {
 		    LpBase::DualExpr tmp(a);
 		    tmp/=b;
 		    return tmp;
+		  }
 		  /// \ingroup lp_group
 		  ///
 		  /// \brief Common base class for LP solvers
 		  ///
 		  /// This class is an abstract base class for LP solvers. This class
 		  /// provides a full interface for set and modify an LP problem,
 		  /// solve it and retrieve the solution. You can use one of the
 		  /// descendants as a concrete implementation, or the \c Lp
 		  /// default LP solver. However, if you would like to handle LP
 		  /// solvers as reference or pointer in a generic way, you can use
 		  /// this class directly.
 		  class LpSolver : virtual public LpBase {
 		  public:
 		    /// The problem types for primal and dual problems
 		    enum ProblemType {
 		      ///Feasible solution hasn't been found (but may exist).
+		      /// = 0. Feasible solution hasn't been found (but may exist).
 		      UNDEFINED = 0,
 		      ///The problem has no feasible solution
+		      /// = 1. The problem has no feasible solution.
 		      INFEASIBLE = 1,
 		      ///Feasible solution found
+		      /// = 2. Feasible solution found.
 		      FEASIBLE = 2,
 		      ///Optimal solution exists and found
+		      /// = 3. Optimal solution exists and found.
 		      OPTIMAL = 3,
 		      ///The cost function is unbounded
+		      /// = 4. The cost function is unbounded.
 		      UNBOUNDED = 4
 		    };
 		    ///The basis status of variables
 		    enum VarStatus {
 		      /// The variable is in the basis
 		      BASIC,
 		      /// The variable is free, but not basic
 		      FREE,
 		      /// The variable has active lower bound
 		      LOWER,
 		      /// The variable has active upper bound
 		      UPPER,
 		      /// The variable is non-basic and fixed
 		      FIXED
 		    };
 		  protected:
 		    virtual SolveExitStatus _solve() = 0;
 		    virtual Value _getPrimal(int i) const = 0;
 		    virtual Value _getDual(int i) const = 0;
 		    virtual Value _getPrimalRay(int i) const = 0;
 		    virtual Value _getDualRay(int i) const = 0;
 		    virtual Value _getPrimalValue() const = 0;
 		    virtual VarStatus _getColStatus(int i) const = 0;
 		    virtual VarStatus _getRowStatus(int i) const = 0;
 		    virtual ProblemType _getPrimalType() const = 0;
 		    virtual ProblemType _getDualType() const = 0;
 		  public:
 		    ///Allocate a new LP problem instance
 		    virtual LpSolver* newSolver() const = 0;
 		    ///Make a copy of the LP problem
 		    virtual LpSolver* cloneSolver() const = 0;
 		    ///\name Solve the LP
 		    ///@{
 		    ///\e Solve the LP problem at hand
 		    ///
 		    ///\return The result of the optimization procedure. Possible
 		    ///values and their meanings can be found in the documentation of
 		    ///\ref SolveExitStatus.
 		    SolveExitStatus solve() { return _solve(); }
 		    ///@}
-		    ///\name Obtain the solution
+		    ///\name Obtain the Solution
 		    ///@{
 		    /// The type of the primal problem
 		    ProblemType primalType() const {
 		      return _getPrimalType();
+		    }
 		    /// The type of the dual problem
 		    ProblemType dualType() const {
 		      return _getDualType();
+		    }
 		    /// Return the primal value of the column
 		    /// Return the primal value of the column.
 		    /// \pre The problem is solved.
 		    Value primal(Col c) const { return _getPrimal(cols(id(c))); }
 		    /// Return the primal value of the expression
 		    /// Return the primal value of the expression, i.e. the dot
 		    /// product of the primal solution and the expression.
 		    /// \pre The problem is solved.
 		    Value primal(const Expr& e) const {
 		      double res = *e;
 		      for (Expr::ConstCoeffIt c(e); c != INVALID; ++c) {
 		        res += *c * primal(c);
+		      }
 		      return res;
+		    }
 		    /// Returns a component of the primal ray
 		    /// The primal ray is solution of the modified primal problem,
 		    /// where we change each finite bound to 0, and we looking for a
 		    /// negative objective value in case of minimization, and positive
 		    /// objective value for maximization. If there is such solution,
 		    /// that proofs the unsolvability of the dual problem, and if a
 		    /// feasible primal solution exists, then the unboundness of
 		    /// primal problem.
 		    ///
 		    /// \pre The problem is solved and the dual problem is infeasible.
 		    /// \note Some solvers does not provide primal ray calculation
 		    /// functions.
 		    Value primalRay(Col c) const { return _getPrimalRay(cols(id(c))); }
 		    /// Return the dual value of the row
 		    /// Return the dual value of the row.
 		    /// \pre The problem is solved.
 		    Value dual(Row r) const { return _getDual(rows(id(r))); }
 		    /// Return the dual value of the dual expression
 		    /// Return the dual value of the dual expression, i.e. the dot
 		    /// product of the dual solution and the dual expression.
 		    /// \pre The problem is solved.
 		    Value dual(const DualExpr& e) const {
 		      double res = 0.0;
 		      for (DualExpr::ConstCoeffIt r(e); r != INVALID; ++r) {
 		        res += *r * dual(r);
+		      }
 		      return res;
+		    }
 		    /// Returns a component of the dual ray
 		    /// The dual ray is solution of the modified primal problem, where
 		    /// we change each finite bound to 0 (i.e. the objective function
 		    /// coefficients in the primal problem), and we looking for a
 		    /// ositive objective value. If there is such solution, that
 		    /// proofs the unsolvability of the primal problem, and if a
 		    /// feasible dual solution exists, then the unboundness of
 		    /// dual problem.
 		    ///
 		    /// \pre The problem is solved and the primal problem is infeasible.
 		    /// \note Some solvers does not provide dual ray calculation
 		    /// functions.
 		    Value dualRay(Row r) const { return _getDualRay(rows(id(r))); }
 		    /// Return the basis status of the column
 		    /// \see VarStatus
 		    VarStatus colStatus(Col c) const { return _getColStatus(cols(id(c))); }
 		    /// Return the basis status of the row
 		    /// \see VarStatus
 		    VarStatus rowStatus(Row r) const { return _getRowStatus(rows(id(r))); }
 		    ///The value of the objective function
 		    ///\return
 		    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
 		    /// of the primal problem, depending on whether we minimize or maximize.
 		    ///- \ref NaN if no primal solution is found.
 		    ///- The (finite) objective value if an optimal solution is found.
 		    Value primal() const { return _getPrimalValue()+obj_const_comp;}
 		    ///@}
 		  protected:
 		  };
 		  /// \ingroup lp_group
 		  ///
 		  /// \brief Common base class for MIP solvers
 		  ///
 		  /// This class is an abstract base class for MIP solvers. This class
 		  /// provides a full interface for set and modify an MIP problem,
 		  /// solve it and retrieve the solution. You can use one of the
 		  /// descendants as a concrete implementation, or the \c Lp
 		  /// default MIP solver. However, if you would like to handle MIP
 		  /// solvers as reference or pointer in a generic way, you can use
 		  /// this class directly.
 		  class MipSolver : virtual public LpBase {
 		  public:
 		    /// The problem types for MIP problems
 		    enum ProblemType {
 		      ///Feasible solution hasn't been found (but may exist).
+		      /// = 0. Feasible solution hasn't been found (but may exist).
 		      UNDEFINED = 0,
 		      ///The problem has no feasible solution
+		      /// = 1. The problem has no feasible solution.
 		      INFEASIBLE = 1,
 		      ///Feasible solution found
+		      /// = 2. Feasible solution found.
 		      FEASIBLE = 2,
 		      ///Optimal solution exists and found
+		      /// = 3. Optimal solution exists and found.
 		      OPTIMAL = 3,
 		      ///The cost function is unbounded
 		      ///
-		      ///The Mip or at least the relaxed problem is unbounded
+		      /// = 4. The cost function is unbounded.
 		      ///The Mip or at least the relaxed problem is unbounded.
 		      UNBOUNDED = 4
 		    };
 		    ///Allocate a new MIP problem instance
 		    virtual MipSolver* newSolver() const = 0;
 		    ///Make a copy of the MIP problem
 		    virtual MipSolver* cloneSolver() const = 0;
 		    ///\name Solve the MIP
 		    ///@{
 		    /// Solve the MIP problem at hand
 		    ///
 		    ///\return The result of the optimization procedure. Possible
 		    ///values and their meanings can be found in the documentation of
 		    ///\ref SolveExitStatus.
 		    SolveExitStatus solve() { return _solve(); }
 		    ///@}
-		    ///\name Setting column type
+		    ///\name Set Column Type
 		    ///@{
 		    ///Possible variable (column) types (e.g. real, integer, binary etc.)
 		    enum ColTypes {
 		      ///Continuous variable (default)
+		      /// = 0. Continuous variable (default).
 		      REAL = 0,
 		      ///Integer variable
+		      /// = 1. Integer variable.
 		      INTEGER = 1
 		    };
 		    ///Sets the type of the given column to the given type
 		    ///Sets the type of the given column to the given type.
 		    ///
 		    void colType(Col c, ColTypes col_type) {
 		      _setColType(cols(id(c)),col_type);
+		    }
 		    ///Gives back the type of the column.
 		    ///Gives back the type of the column.
 		    ///
 		    ColTypes colType(Col c) const {
 		      return _getColType(cols(id(c)));
+		    }
 		    ///@}
-		    ///\name Obtain the solution
+		    ///\name Obtain the Solution
 		    ///@{
 		    /// The type of the MIP problem
 		    ProblemType type() const {
 		      return _getType();
+		    }
 		    /// Return the value of the row in the solution
 		    ///  Return the value of the row in the solution.
 		    /// \pre The problem is solved.
 		    Value sol(Col c) const { return _getSol(cols(id(c))); }
 		    /// Return the value of the expression in the solution
 		    /// Return the value of the expression in the solution, i.e. the
 		    /// dot product of the solution and the expression.
 		    /// \pre The problem is solved.
 		    Value sol(const Expr& e) const {
 		      double res = *e;
 		      for (Expr::ConstCoeffIt c(e); c != INVALID; ++c) {
 		        res += *c * sol(c);
+		      }
 		      return res;
+		    }
 		    ///The value of the objective function
 		    ///\return
 		    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
 		    /// of the problem, depending on whether we minimize or maximize.
 		    ///- \ref NaN if no primal solution is found.
 		    ///- The (finite) objective value if an optimal solution is found.
 		    Value solValue() const { return _getSolValue()+obj_const_comp;}
 		    ///@}
 		  protected:
 		    virtual SolveExitStatus _solve() = 0;
 		    virtual ColTypes _getColType(int col) const = 0;
 		    virtual void _setColType(int col, ColTypes col_type) = 0;
 		    virtual ProblemType _getType() const = 0;
 		    virtual Value _getSol(int i) const = 0;
 		    virtual Value _getSolValue() const = 0;
 		  };
 		} //namespace lemon
 		#endif //LEMON_LP_BASE_H

lemon/maps.h

Show inline comments

@@ -2635,148 +2635,148 @@
 		  private:
 		    class AutoNodeMap
 		      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
 		    public:
 		      typedef typename ItemSetTraits<Digraph, Key>::
 		      template Map<int>::Type Parent;
 		      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
 		      virtual void add(const Key& key) {
 		        Parent::add(key);
 		        Parent::set(key, 0);
+		      }
 		      virtual void add(const std::vector<Key>& keys) {
 		        Parent::add(keys);
 		        for (int i = 0; i < int(keys.size()); ++i) {
 		          Parent::set(keys[i], 0);
+		        }
+		      }
 		      virtual void build() {
 		        Parent::build();
 		        Key it;
 		        typename Parent::Notifier* nf = Parent::notifier();
 		        for (nf->first(it); it != INVALID; nf->next(it)) {
 		          Parent::set(it, 0);
+		        }
+		      }
 		    };
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor for creating an out-degree map.
 		    explicit OutDegMap(const Digraph& graph)
 		      : _digraph(graph), _deg(graph) {
 		      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = countOutArcs(_digraph, it);
+		      }
+		    }
 		    /// \brief Gives back the out-degree of a Node.
 		    ///
 		    /// Gives back the out-degree of a Node.
 		    int operator[](const Key& key) const {
 		      return _deg[key];
+		    }
 		  protected:
 		    typedef typename Digraph::Arc Arc;
 		    virtual void add(const Arc& arc) {
 		      ++_deg[_digraph.source(arc)];
+		    }
 		    virtual void add(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        ++_deg[_digraph.source(arcs[i])];
+		      }
+		    }
 		    virtual void erase(const Arc& arc) {
 		      --_deg[_digraph.source(arc)];
+		    }
 		    virtual void erase(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        --_deg[_digraph.source(arcs[i])];
+		      }
+		    }
 		    virtual void build() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = countOutArcs(_digraph, it);
+		      }
+		    }
 		    virtual void clear() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = 0;
+		      }
+		    }
 		  private:
 		    const Digraph& _digraph;
 		    AutoNodeMap _deg;
 		  };
 		  /// \brief Potential difference map
 		  ///
 		  /// PotentialMap returns the difference between the potentials of the
 		  /// source and target nodes of each arc in a digraph, i.e. it returns
 		  /// PotentialDifferenceMap returns the difference between the potentials of
 		  /// the source and target nodes of each arc in a digraph, i.e. it returns
 		  /// \code
 		  ///   potential[gr.target(arc)] - potential[gr.source(arc)].
 		  /// \endcode
 		  /// \tparam GR The digraph type.
 		  /// \tparam POT A node map storing the potentials.
 		  template <typename GR, typename POT>
 		  class PotentialDifferenceMap {
 		  public:
 		    /// Key type
 		    typedef typename GR::Arc Key;
 		    /// Value type
 		    typedef typename POT::Value Value;
 		    /// \brief Constructor
 		    ///
 		    /// Contructor of the map.
 		    explicit PotentialDifferenceMap(const GR& gr,
 		                                    const POT& potential)
 		      : _digraph(gr), _potential(potential) {}
 		    /// \brief Returns the potential difference for the given arc.
 		    ///
 		    /// Returns the potential difference for the given arc, i.e.
 		    /// \code
 		    ///   potential[gr.target(arc)] - potential[gr.source(arc)].
 		    /// \endcode
 		    Value operator[](const Key& arc) const {
 		      return _potential[_digraph.target(arc)] -
 		        _potential[_digraph.source(arc)];
+		    }
 		  private:
 		    const GR& _digraph;
 		    const POT& _potential;
 		  };
 		  /// \brief Returns a PotentialDifferenceMap.
 		  ///
 		  /// This function just returns a PotentialDifferenceMap.
 		  /// \relates PotentialDifferenceMap
 		  template <typename GR, typename POT>
 		  PotentialDifferenceMap<GR, POT>
 		  potentialDifferenceMap(const GR& gr, const POT& potential) {
 		    return PotentialDifferenceMap<GR, POT>(gr, potential);
+		  }
 		  /// @}
+		}
 		#endif // LEMON_MAPS_H

lemon/min_cost_arborescence.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * 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_MIN_COST_ARBORESCENCE_H
 		#define LEMON_MIN_COST_ARBORESCENCE_H
 		///\ingroup spantree
 		///\file
 		///\brief Minimum Cost Arborescence algorithm.
 		#include <vector>
 		#include <lemon/list_graph.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/assert.h>
 		namespace lemon {
 		  /// \brief Default traits class for MinCostArborescence class.
 		  ///
 		  /// Default traits class for MinCostArborescence class.
 		  /// \param GR Digraph type.
 		  /// \param CM Type of cost map.
 		  template <class GR, class CM>
 		  struct MinCostArborescenceDefaultTraits{
 		    /// \brief The digraph type the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc costs.
 		    ///
 		    /// The type of the map that stores the arc costs.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef CM CostMap;
 		    /// \brief The value type of the costs.
 		    ///
 		    /// The value type of the costs.
 		    typedef typename CostMap::Value Value;
 		    /// \brief The type of the map that stores which arcs are in the
 		    /// arborescence.
 		    ///
 		    /// The type of the map that stores which arcs are in the
 		    /// arborescence.  It must meet the \ref concepts::WriteMap
 		    /// "WriteMap" concept.  Initially it will be set to false on each
 		    /// arc. After it will set all arborescence arcs once.
 		    typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
 		    /// \brief Instantiates a \c ArborescenceMap.
 		    ///
 		    /// This function instantiates a \c ArborescenceMap.
 		    /// \param digraph is the graph, to which we would like to
 		    /// calculate the \c ArborescenceMap.
 		    static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
 		      return new ArborescenceMap(digraph);
+		    }
 		    /// \brief The type of the \c PredMap
 		    ///
 		    /// The type of the \c PredMap. It is a node map with an arc value type.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    /// \brief Instantiates a \c PredMap.
 		    ///
 		    /// This function instantiates a \c PredMap.
 		    /// \param digraph The digraph to which we would like to define the
 		    /// \c PredMap.
 		    static PredMap *createPredMap(const Digraph &digraph){
 		      return new PredMap(digraph);
+		    }
 		  };
 		  /// \ingroup spantree
 		  ///
-		  /// \brief %MinCostArborescence algorithm class.
+		  /// \brief Minimum Cost Arborescence algorithm class.
 		  ///
 		  /// This class provides an efficient implementation of
-		  /// %MinCostArborescence algorithm. The arborescence is a tree
+		  /// Minimum Cost Arborescence algorithm. The arborescence is a tree
 		  /// which is directed from a given source node of the digraph. One or
 		  /// more sources should be given for the algorithm and it will calculate
 		  /// the minimum cost subgraph which are union of arborescences with the
 		  /// given sources and spans all the nodes which are reachable from the
 		  /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
 		  ///
 		  /// The algorithm provides also an optimal dual solution, therefore
 		  /// the optimality of the solution can be checked.
 		  ///
 		  /// \param GR The digraph type the algorithm runs on. The default value
 		  /// is \ref ListDigraph.
 		  /// \param CM This read-only ArcMap determines the costs of the
 		  /// arcs. It is read once for each arc, so the map may involve in
 		  /// relatively time consuming process to compute the arc cost if
 		  /// it is necessary. The default map type is \ref
 		  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
 		  /// \param TR Traits class to set various data types used
 		  /// by the algorithm. The default traits class is
 		  /// \ref MinCostArborescenceDefaultTraits
 		  /// "MinCostArborescenceDefaultTraits<GR, CM>".  See \ref
 		  /// MinCostArborescenceDefaultTraits for the documentation of a
 		  /// MinCostArborescence traits class.
 		#ifndef DOXYGEN
 		  template <typename GR = ListDigraph,
 		            typename CM = typename GR::template ArcMap<int>,
 		            typename TR =
 		              MinCostArborescenceDefaultTraits<GR, CM> >
 		#else
 		  template <typename GR, typename CM, typedef TR>
 		#endif
 		  class MinCostArborescence {
 		  public:
 		    /// The traits.
 		    typedef TR Traits;
 		    /// The type of the underlying digraph.
 		    typedef typename Traits::Digraph Digraph;
 		    /// The type of the map that stores the arc costs.
 		    typedef typename Traits::CostMap CostMap;
 		    ///The type of the costs of the arcs.
 		    typedef typename Traits::Value Value;
 		    ///The type of the predecessor map.
 		    typedef typename Traits::PredMap PredMap;
 		    ///The type of the map that stores which arcs are in the arborescence.
 		    typedef typename Traits::ArborescenceMap ArborescenceMap;
 		    typedef MinCostArborescence Create;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    struct CostArc {
 		      Arc arc;
 		      Value value;
 		      CostArc() {}
 		      CostArc(Arc _arc, Value _value) : arc(_arc), value(_value) {}
 		    };
 		    const Digraph *_digraph;
 		    const CostMap *_cost;
 		    PredMap *_pred;
 		    bool local_pred;
 		    ArborescenceMap *_arborescence;
 		    bool local_arborescence;
 		    typedef typename Digraph::template ArcMap<int> ArcOrder;
 		    ArcOrder *_arc_order;
 		    typedef typename Digraph::template NodeMap<int> NodeOrder;
 		    NodeOrder *_node_order;
 		    typedef typename Digraph::template NodeMap<CostArc> CostArcMap;
 		    CostArcMap *_cost_arcs;
 		    struct StackLevel {
 		      std::vector<CostArc> arcs;
 		      int node_level;
 		    };
 		    std::vector<StackLevel> level_stack;
 		    std::vector<Node> queue;
 		    typedef std::vector<typename Digraph::Node> DualNodeList;
 		    DualNodeList _dual_node_list;
 		    struct DualVariable {
 		      int begin, end;
@@ -297,193 +297,193 @@
 		      DualVariable var(_dual_node_list.size() - 1,
 		                       _dual_node_list.size(), minimum.value);
 		      _dual_variables.push_back(var);
 		      for (int i = 0; i < int(nodes.size()); ++i) {
 		        (*_cost_arcs)[nodes[i]].value -= minimum.value;
 		        level.arcs.push_back((*_cost_arcs)[nodes[i]]);
 		        (*_cost_arcs)[nodes[i]].arc = INVALID;
+		      }
 		      level_stack.push_back(level);
 		      return minimum.arc;
+		    }
 		    Arc contract(Node node) {
 		      int node_bottom = bottom(node);
 		      std::vector<Node> nodes;
 		      while (!level_stack.empty() &&
 		             level_stack.back().node_level >= node_bottom) {
 		        for (int i = 0; i < int(level_stack.back().arcs.size()); ++i) {
 		          Arc arc = level_stack.back().arcs[i].arc;
 		          Node source = _digraph->source(arc);
 		          Value value = level_stack.back().arcs[i].value;
 		          if ((*_node_order)[source] >= node_bottom) continue;
 		          if ((*_cost_arcs)[source].arc == INVALID) {
 		            (*_cost_arcs)[source].arc = arc;
 		            (*_cost_arcs)[source].value = value;
 		            nodes.push_back(source);
 		          } else {
 		            if ((*_cost_arcs)[source].value > value) {
 		              (*_cost_arcs)[source].arc = arc;
 		              (*_cost_arcs)[source].value = value;
+		            }
+		          }
+		        }
 		        level_stack.pop_back();
+		      }
 		      CostArc minimum = (*_cost_arcs)[nodes[0]];
 		      for (int i = 1; i < int(nodes.size()); ++i) {
 		        if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
 		          minimum = (*_cost_arcs)[nodes[i]];
+		        }
+		      }
 		      (*_arc_order)[minimum.arc] = _dual_variables.size();
 		      DualVariable var(node_bottom, _dual_node_list.size(), minimum.value);
 		      _dual_variables.push_back(var);
 		      StackLevel level;
 		      level.node_level = node_bottom;
 		      for (int i = 0; i < int(nodes.size()); ++i) {
 		        (*_cost_arcs)[nodes[i]].value -= minimum.value;
 		        level.arcs.push_back((*_cost_arcs)[nodes[i]]);
 		        (*_cost_arcs)[nodes[i]].arc = INVALID;
+		      }
 		      level_stack.push_back(level);
 		      return minimum.arc;
+		    }
 		    int bottom(Node node) {
 		      int k = level_stack.size() - 1;
 		      while (level_stack[k].node_level > (*_node_order)[node]) {
 		        --k;
+		      }
 		      return level_stack[k].node_level;
+		    }
 		    void finalize(Arc arc) {
 		      Node node = _digraph->target(arc);
 		      _heap->push(node, (*_arc_order)[arc]);
 		      _pred->set(node, arc);
 		      while (!_heap->empty()) {
 		        Node source = _heap->top();
 		        _heap->pop();
 		        (*_node_order)[source] = -1;
 		        for (OutArcIt it(*_digraph, source); it != INVALID; ++it) {
 		          if ((*_arc_order)[it] < 0) continue;
 		          Node target = _digraph->target(it);
 		          switch(_heap->state(target)) {
 		          case Heap::PRE_HEAP:
 		            _heap->push(target, (*_arc_order)[it]);
 		            _pred->set(target, it);
 		            break;
 		          case Heap::IN_HEAP:
 		            if ((*_arc_order)[it] < (*_heap)[target]) {
 		              _heap->decrease(target, (*_arc_order)[it]);
 		              _pred->set(target, it);
+		            }
 		            break;
 		          case Heap::POST_HEAP:
 		            break;
+		          }
+		        }
 		        _arborescence->set((*_pred)[source], true);
+		      }
+		    }
 		  public:
-		    /// \name Named template parameters
+		    /// \name Named Template Parameters
 		    /// @{
 		    template <class T>
 		    struct DefArborescenceMapTraits : public Traits {
 		      typedef T ArborescenceMap;
 		      static ArborescenceMap *createArborescenceMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ArborescenceMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for
 		    /// setting ArborescenceMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// ArborescenceMap type
 		    template <class T>
 		    struct DefArborescenceMap
 		      : public MinCostArborescence<Digraph, CostMap,
 		                                   DefArborescenceMapTraits<T> > {
 		    };
 		    template <class T>
 		    struct DefPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for
 		    /// setting PredMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// PredMap type
 		    template <class T>
 		    struct DefPredMap
 		      : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
 		    };
 		    /// @}
 		    /// \brief Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm will run on.
 		    /// \param cost The cost map used by the algorithm.
 		    MinCostArborescence(const Digraph& digraph, const CostMap& cost)
 		      : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
 		        _arborescence(0), local_arborescence(false),
 		        _arc_order(0), _node_order(0), _cost_arcs(0),
 		        _heap_cross_ref(0), _heap(0) {}
 		    /// \brief Destructor.
 		    ~MinCostArborescence() {
 		      destroyStructures();
+		    }
 		    /// \brief Sets the arborescence map.
 		    ///
 		    /// Sets the arborescence map.
 		    /// \return <tt>(*this)</tt>
 		    MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
 		      if (local_arborescence) {
 		        delete _arborescence;
+		      }
 		      local_arborescence = false;
 		      _arborescence = &m;
 		      return *this;
+		    }
 		    /// \brief Sets the arborescence map.
 		    ///
 		    /// Sets the arborescence map.
 		    /// \return <tt>(*this)</tt>
 		    MinCostArborescence& predMap(PredMap& m) {
 		      if (local_pred) {
 		        delete _pred;
+		      }
 		      local_pred = false;
 		      _pred = &m;
 		      return *this;
+		    }
 		    /// \name Query Functions
 		    /// The result of the %MinCostArborescence algorithm can be obtained
 		    /// using these functions.\n
 		    /// Before the use of these functions,
 		    /// either run() or start() must be called.
 		    /// @{
 		    /// \brief Returns a reference to the arborescence map.
 		    ///
@@ -537,193 +537,193 @@
 		    /// \brief Indicates that a node is processed.
 		    ///
 		    /// Indicates that a node is processed. The arborescence path exists
 		    /// from the source to the given node.
 		    bool processed(Node node) const {
 		      return (*_node_order)[node] == -1;
+		    }
 		    /// \brief Returns the number of the dual variables in basis.
 		    ///
 		    /// Returns the number of the dual variables in basis.
 		    int dualNum() const {
 		      return _dual_variables.size();
+		    }
 		    /// \brief Returns the value of the dual solution.
 		    ///
 		    /// Returns the value of the dual solution. It should be
 		    /// equal to the arborescence value.
 		    Value dualValue() const {
 		      Value sum = 0;
 		      for (int i = 0; i < int(_dual_variables.size()); ++i) {
 		        sum += _dual_variables[i].value;
+		      }
 		      return sum;
+		    }
 		    /// \brief Returns the number of the nodes in the dual variable.
 		    ///
 		    /// Returns the number of the nodes in the dual variable.
 		    int dualSize(int k) const {
 		      return _dual_variables[k].end - _dual_variables[k].begin;
+		    }
 		    /// \brief Returns the value of the dual variable.
 		    ///
 		    /// Returns the the value of the dual variable.
 		    const Value& dualValue(int k) const {
 		      return _dual_variables[k].value;
+		    }
 		    /// \brief Lemon iterator for get a dual variable.
 		    ///
 		    /// Lemon iterator for get a dual variable. This class provides
 		    /// a common style lemon iterator which gives back a subset of
 		    /// the nodes.
 		    class DualIt {
 		    public:
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor for get the nodeset of the variable.
 		      DualIt(const MinCostArborescence& algorithm, int variable)
 		        : _algorithm(&algorithm)
+		      {
 		        _index = _algorithm->_dual_variables[variable].begin;
 		        _last = _algorithm->_dual_variables[variable].end;
+		      }
 		      /// \brief Conversion to node.
 		      ///
 		      /// Conversion to node.
 		      operator Node() const {
 		        return _algorithm->_dual_node_list[_index];
+		      }
 		      /// \brief Increment operator.
 		      ///
 		      /// Increment operator.
 		      DualIt& operator++() {
 		        ++_index;
 		        return *this;
+		      }
 		      /// \brief Validity checking
 		      ///
 		      /// Checks whether the iterator is invalid.
 		      bool operator==(Invalid) const {
 		        return _index == _last;
+		      }
 		      /// \brief Validity checking
 		      ///
 		      /// Checks whether the iterator is valid.
 		      bool operator!=(Invalid) const {
 		        return _index != _last;
+		      }
 		    private:
 		      const MinCostArborescence* _algorithm;
 		      int _index, _last;
 		    };
 		    /// @}
-		    /// \name Execution control
+		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to use
 		    /// one of the member functions called \c run(...). \n
 		    /// If you need more control on the execution,
 		    /// first you must call \ref init(), then you can add several
 		    /// source nodes with \ref addSource().
 		    /// Finally \ref start() will perform the arborescence
 		    /// computation.
 		    ///@{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    ///
 		    void init() {
 		      createStructures();
 		      _heap->clear();
 		      for (NodeIt it(*_digraph); it != INVALID; ++it) {
 		        (*_cost_arcs)[it].arc = INVALID;
 		        (*_node_order)[it] = -3;
 		        (*_heap_cross_ref)[it] = Heap::PRE_HEAP;
 		        _pred->set(it, INVALID);
+		      }
 		      for (ArcIt it(*_digraph); it != INVALID; ++it) {
 		        _arborescence->set(it, false);
 		        (*_arc_order)[it] = -1;
+		      }
 		      _dual_node_list.clear();
 		      _dual_variables.clear();
+		    }
 		    /// \brief Adds a new source node.
 		    ///
 		    /// Adds a new source node to the algorithm.
 		    void addSource(Node source) {
 		      std::vector<Node> nodes;
 		      nodes.push_back(source);
 		      while (!nodes.empty()) {
 		        Node node = nodes.back();
 		        nodes.pop_back();
 		        for (OutArcIt it(*_digraph, node); it != INVALID; ++it) {
 		          Node target = _digraph->target(it);
 		          if ((*_node_order)[target] == -3) {
 		            (*_node_order)[target] = -2;
 		            nodes.push_back(target);
 		            queue.push_back(target);
+		          }
+		        }
+		      }
 		      (*_node_order)[source] = -1;
+		    }
 		    /// \brief Processes the next node in the priority queue.
 		    ///
 		    /// Processes the next node in the priority queue.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \warning The queue must not be empty!
 		    Node processNextNode() {
 		      Node node = queue.back();
 		      queue.pop_back();
 		      if ((*_node_order)[node] == -2) {
 		        Arc arc = prepare(node);
 		        Node source = _digraph->source(arc);
 		        while ((*_node_order)[source] != -1) {
 		          if ((*_node_order)[source] >= 0) {
 		            arc = contract(source);
 		          } else {
 		            arc = prepare(source);
+		          }
 		          source = _digraph->source(arc);
+		        }
 		        finalize(arc);
 		        level_stack.clear();
+		      }
 		      return node;
+		    }
 		    /// \brief Returns the number of the nodes to be processed.
 		    ///
 		    /// Returns the number of the nodes to be processed.
 		    int queueSize() const {
 		      return queue.size();
+		    }
 		    /// \brief Returns \c false if there are nodes to be processed.
 		    ///
 		    /// Returns \c false if there are nodes to be processed.
 		    bool emptyQueue() const {
 		      return queue.empty();
+		    }
 		    /// \brief Executes the algorithm.
 		    ///
 		    /// Executes the algorithm.

lemon/random.h

Show inline comments

@@ -566,440 +566,440 @@
+		    }
 		    /// \brief Assign operator
 		    ///
 		    /// Assign operator. The generated sequence will be identical to
 		    /// the other sequence. It can be used to save the current state
 		    /// of the generator and later use it to generate the same
 		    /// sequence.
 		    Random& operator=(const Random& other) {
 		      if (&other != this) {
 		        core.copyState(other.core);
+		      }
 		      return *this;
+		    }
 		    /// \brief Seeding random sequence
 		    ///
 		    /// Seeding the random sequence. The current number type will be
 		    /// converted to the architecture word type.
 		    template <typename Number>
 		    void seed(Number seed) {
 		      _random_bits::Initializer<Number, Word>::init(core, seed);
+		    }
 		    /// \brief Seeding random sequence
 		    ///
 		    /// Seeding the random sequence. The given range should contain
 		    /// any number type and the numbers will be converted to the
 		    /// architecture word type.
 		    template <typename Iterator>
 		    void seed(Iterator begin, Iterator end) {
 		      typedef typename std::iterator_traits<Iterator>::value_type Number;
 		      _random_bits::Initializer<Number, Word>::init(core, begin, end);
+		    }
 		    /// \brief Seeding from file or from process id and time
 		    ///
 		    /// By default, this function calls the \c seedFromFile() member
 		    /// function with the <tt>/dev/urandom</tt> file. If it does not success,
 		    /// it uses the \c seedFromTime().
 		    /// \return Currently always \c true.
 		    bool seed() {
 		#ifndef WIN32
 		      if (seedFromFile("/dev/urandom", 0)) return true;
 		#endif
 		      if (seedFromTime()) return true;
 		      return false;
+		    }
 		    /// \brief Seeding from file
 		    ///
 		    /// Seeding the random sequence from file. The linux kernel has two
 		    /// devices, <tt>/dev/random</tt> and <tt>/dev/urandom</tt> which
 		    /// could give good seed values for pseudo random generators (The
 		    /// difference between two devices is that the <tt>random</tt> may
 		    /// block the reading operation while the kernel can give good
 		    /// source of randomness, while the <tt>urandom</tt> does not
 		    /// block the input, but it could give back bytes with worse
 		    /// entropy).
 		    /// \param file The source file
 		    /// \param offset The offset, from the file read.
 		    /// \return \c true when the seeding successes.
 		#ifndef WIN32
 		    bool seedFromFile(const std::string& file = "/dev/urandom", int offset = 0)
 		#else
 		    bool seedFromFile(const std::string& file = "", int offset = 0)
 		#endif
+		    {
 		      std::ifstream rs(file.c_str());
 		      const int size = 4;
 		      Word buf[size];
 		      if (offset != 0 && !rs.seekg(offset)) return false;
 		      if (!rs.read(reinterpret_cast<char*>(buf), sizeof(buf))) return false;
 		      seed(buf, buf + size);
 		      return true;
+		    }
 		    /// \brief Seding from process id and time
 		    ///
 		    /// Seding from process id and time. This function uses the
 		    /// current process id and the current time for initialize the
 		    /// random sequence.
 		    /// \return Currently always \c true.
 		    bool seedFromTime() {
 		#ifndef WIN32
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      seed(getpid() + tv.tv_sec + tv.tv_usec);
 		#else
 		      seed(bits::getWinRndSeed());
 		#endif
 		      return true;
+		    }
 		    /// @}
-		    ///\name Uniform distributions
+		    ///\name Uniform Distributions
 		    ///
 		    /// @{
 		    /// \brief Returns a random real number from the range [0, 1)
 		    ///
 		    /// It returns a random real number from the range [0, 1). The
 		    /// default Number type is \c double.
 		    template <typename Number>
 		    Number real() {
 		      return _random_bits::RealConversion<Number, Word>::convert(core);
+		    }
 		    double real() {
 		      return real<double>();
+		    }
 		    /// \brief Returns a random real number from the range [0, 1)
 		    ///
 		    /// It returns a random double from the range [0, 1).
 		    double operator()() {
 		      return real<double>();
+		    }
 		    /// \brief Returns a random real number from the range [0, b)
 		    ///
 		    /// It returns a random real number from the range [0, b).
 		    double operator()(double b) {
 		      return real<double>() * b;
+		    }
 		    /// \brief Returns a random real number from the range [a, b)
 		    ///
 		    /// It returns a random real number from the range [a, b).
 		    double operator()(double a, double b) {
 		      return real<double>() * (b - a) + a;
+		    }
 		    /// \brief Returns a random integer from a range
 		    ///
 		    /// It returns a random integer from the range {0, 1, ..., b - 1}.
 		    template <typename Number>
 		    Number integer(Number b) {
 		      return _random_bits::Mapping<Number, Word>::map(core, b);
+		    }
 		    /// \brief Returns a random integer from a range
 		    ///
 		    /// It returns a random integer from the range {a, a + 1, ..., b - 1}.
 		    template <typename Number>
 		    Number integer(Number a, Number b) {
 		      return _random_bits::Mapping<Number, Word>::map(core, b - a) + a;
+		    }
 		    /// \brief Returns a random integer from a range
 		    ///
 		    /// It returns a random integer from the range {0, 1, ..., b - 1}.
 		    template <typename Number>
 		    Number operator[](Number b) {
 		      return _random_bits::Mapping<Number, Word>::map(core, b);
+		    }
 		    /// \brief Returns a random non-negative integer
 		    ///
 		    /// It returns a random non-negative integer uniformly from the
 		    /// whole range of the current \c Number type. The default result
 		    /// type of this function is <tt>unsigned int</tt>.
 		    template <typename Number>
 		    Number uinteger() {
 		      return _random_bits::IntConversion<Number, Word>::convert(core);
+		    }
 		    unsigned int uinteger() {
 		      return uinteger<unsigned int>();
+		    }
 		    /// \brief Returns a random integer
 		    ///
 		    /// It returns a random integer uniformly from the whole range of
 		    /// the current \c Number type. The default result type of this
 		    /// function is \c int.
 		    template <typename Number>
 		    Number integer() {
 		      static const int nb = std::numeric_limits<Number>::digits +
 		        (std::numeric_limits<Number>::is_signed ? 1 : 0);
 		      return _random_bits::IntConversion<Number, Word, nb>::convert(core);
+		    }
 		    int integer() {
 		      return integer<int>();
+		    }
 		    /// \brief Returns a random bool
 		    ///
 		    /// It returns a random bool. The generator holds a buffer for
 		    /// random bits. Every time when it become empty the generator makes
 		    /// a new random word and fill the buffer up.
 		    bool boolean() {
 		      return bool_producer.convert(core);
+		    }
 		    /// @}
-		    ///\name Non-uniform distributions
+		    ///\name Non-uniform Distributions
 		    ///
 		    ///@{
 		    /// \brief Returns a random bool with given probability of true result.
 		    ///
 		    /// It returns a random bool with given probability of true result.
 		    bool boolean(double p) {
 		      return operator()() < p;
+		    }
 		    /// Standard normal (Gauss) distribution
 		    /// Standard normal (Gauss) distribution.
 		    /// \note The Cartesian form of the Box-Muller
 		    /// transformation is used to generate a random normal distribution.
 		    double gauss()
+		    {
 		      double V1,V2,S;
 		      do {
 		        V1=2*real<double>()-1;
 		        V2=2*real<double>()-1;
 		        S=V1*V1+V2*V2;
 		      } while(S>=1);
 		      return std::sqrt(-2*std::log(S)/S)*V1;
+		    }
 		    /// Normal (Gauss) distribution with given mean and standard deviation
 		    /// Normal (Gauss) distribution with given mean and standard deviation.
 		    /// \sa gauss()
 		    double gauss(double mean,double std_dev)
+		    {
 		      return gauss()*std_dev+mean;
+		    }
 		    /// Lognormal distribution
 		    /// Lognormal distribution. The parameters are the mean and the standard
 		    /// deviation of <tt>exp(X)</tt>.
 		    ///
 		    double lognormal(double n_mean,double n_std_dev)
+		    {
 		      return std::exp(gauss(n_mean,n_std_dev));
+		    }
 		    /// Lognormal distribution
 		    /// Lognormal distribution. The parameter is an <tt>std::pair</tt> of
 		    /// the mean and the standard deviation of <tt>exp(X)</tt>.
 		    ///
 		    double lognormal(const std::pair<double,double> &params)
+		    {
 		      return std::exp(gauss(params.first,params.second));
+		    }
 		    /// Compute the lognormal parameters from mean and standard deviation
 		    /// This function computes the lognormal parameters from mean and
 		    /// standard deviation. The return value can direcly be passed to
 		    /// lognormal().
 		    std::pair<double,double> lognormalParamsFromMD(double mean,
 		                                                   double std_dev)
+		    {
 		      double fr=std_dev/mean;
 		      fr*=fr;
 		      double lg=std::log(1+fr);
 		      return std::pair<double,double>(std::log(mean)-lg/2.0,std::sqrt(lg));
+		    }
 		    /// Lognormal distribution with given mean and standard deviation
 		    /// Lognormal distribution with given mean and standard deviation.
 		    ///
 		    double lognormalMD(double mean,double std_dev)
+		    {
 		      return lognormal(lognormalParamsFromMD(mean,std_dev));
+		    }
 		    /// Exponential distribution with given mean
 		    /// This function generates an exponential distribution random number
 		    /// with mean <tt>1/lambda</tt>.
 		    ///
 		    double exponential(double lambda=1.0)
+		    {
 		      return -std::log(1.0-real<double>())/lambda;
+		    }
 		    /// Gamma distribution with given integer shape
 		    /// This function generates a gamma distribution random number.
 		    ///
 		    ///\param k shape parameter (<tt>k>0</tt> integer)
 		    double gamma(int k)
+		    {
 		      double s = 0;
 		      for(int i=0;i<k;i++) s-=std::log(1.0-real<double>());
 		      return s;
+		    }
 		    /// Gamma distribution with given shape and scale parameter
 		    /// This function generates a gamma distribution random number.
 		    ///
 		    ///\param k shape parameter (<tt>k>0</tt>)
 		    ///\param theta scale parameter
 		    ///
 		    double gamma(double k,double theta=1.0)
+		    {
 		      double xi,nu;
 		      const double delta = k-std::floor(k);
 		      const double v0=E/(E-delta);
 		      do {
 		        double V0=1.0-real<double>();
 		        double V1=1.0-real<double>();
 		        double V2=1.0-real<double>();
 		        if(V2<=v0)
+		          {
 		            xi=std::pow(V1,1.0/delta);
 		            nu=V0*std::pow(xi,delta-1.0);
+		          }
 		        else
+		          {
 		            xi=1.0-std::log(V1);
 		            nu=V0*std::exp(-xi);
+		          }
 		      } while(nu>std::pow(xi,delta-1.0)*std::exp(-xi));
 		      return theta*(xi+gamma(int(std::floor(k))));
+		    }
 		    /// Weibull distribution
 		    /// This function generates a Weibull distribution random number.
 		    ///
 		    ///\param k shape parameter (<tt>k>0</tt>)
 		    ///\param lambda scale parameter (<tt>lambda>0</tt>)
 		    ///
 		    double weibull(double k,double lambda)
+		    {
 		      return lambda*pow(-std::log(1.0-real<double>()),1.0/k);
+		    }
 		    /// Pareto distribution
 		    /// This function generates a Pareto distribution random number.
 		    ///
 		    ///\param k shape parameter (<tt>k>0</tt>)
 		    ///\param x_min location parameter (<tt>x_min>0</tt>)
 		    ///
 		    double pareto(double k,double x_min)
+		    {
 		      return exponential(gamma(k,1.0/x_min))+x_min;
+		    }
 		    /// Poisson distribution
 		    /// This function generates a Poisson distribution random number with
 		    /// parameter \c lambda.
 		    ///
 		    /// The probability mass function of this distribusion is
 		    /// \f[ \frac{e^{-\lambda}\lambda^k}{k!} \f]
 		    /// \note The algorithm is taken from the book of Donald E. Knuth titled
 		    /// ''Seminumerical Algorithms'' (1969). Its running time is linear in the
 		    /// return value.
 		    int poisson(double lambda)
+		    {
 		      const double l = std::exp(-lambda);
 		      int k=0;
 		      double p = 1.0;
 		      do {
 		        k++;
 		        p*=real<double>();
 		      } while (p>=l);
 		      return k-1;
+		    }
 		    ///@}
-		    ///\name Two dimensional distributions
+		    ///\name Two Dimensional Distributions
 		    ///
 		    ///@{
 		    /// Uniform distribution on the full unit circle
 		    /// Uniform distribution on the full unit circle.
 		    ///
 		    dim2::Point<double> disc()
+		    {
 		      double V1,V2;
 		      do {
 		        V1=2*real<double>()-1;
 		        V2=2*real<double>()-1;
 		      } while(V1*V1+V2*V2>=1);
 		      return dim2::Point<double>(V1,V2);
+		    }
 		    /// A kind of two dimensional normal (Gauss) distribution
 		    /// This function provides a turning symmetric two-dimensional distribution.
 		    /// Both coordinates are of standard normal distribution, but they are not
 		    /// independent.
 		    ///
 		    /// \note The coordinates are the two random variables provided by
 		    /// the Box-Muller method.
 		    dim2::Point<double> gauss2()
+		    {
 		      double V1,V2,S;
 		      do {
 		        V1=2*real<double>()-1;
 		        V2=2*real<double>()-1;
 		        S=V1*V1+V2*V2;
 		      } while(S>=1);
 		      double W=std::sqrt(-2*std::log(S)/S);
 		      return dim2::Point<double>(W*V1,W*V2);
+		    }
 		    /// A kind of two dimensional exponential distribution
 		    /// This function provides a turning symmetric two-dimensional distribution.
 		    /// The x-coordinate is of conditionally exponential distribution
 		    /// with the condition that x is positive and y=0. If x is negative and
 		    /// y=0 then, -x is of exponential distribution. The same is true for the
 		    /// y-coordinate.
 		    dim2::Point<double> exponential2()
+		    {
 		      double V1,V2,S;
 		      do {
 		        V1=2*real<double>()-1;
 		        V2=2*real<double>()-1;
 		        S=V1*V1+V2*V2;
 		      } while(S>=1);
 		      double W=-std::log(S)/S;
 		      return dim2::Point<double>(W*V1,W*V2);
+		    }
 		    ///@}
 		  };
 		  extern Random rnd;
+		}
 		#endif

lemon/suurballe.h

Show inline comments

@@ -195,193 +195,193 @@
 		        // Update potentials of processed nodes
 		        Length t_dist = heap.prio();
 		        for (int i = 0; i < int(_proc_nodes.size()); ++i)
 		          _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
 		        return true;
+		      }
 		    }; //class ResidualDijkstra
 		  private:
 		    // The digraph the algorithm runs on
 		    const Digraph &_graph;
 		    // The length map
 		    const LengthMap &_length;
 		    // Arc map of the current flow
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    // Node map of the current potentials
 		    PotentialMap *_potential;
 		    bool _local_potential;
 		    // The source node
 		    Node _source;
 		    // The target node
 		    Node _target;
 		    // Container to store the found paths
 		    std::vector< SimplePath<Digraph> > paths;
 		    int _path_num;
 		    // The pred arc map
 		    PredMap _pred;
 		    // Implementation of the Dijkstra algorithm for finding augmenting
 		    // shortest paths in the residual network
 		    ResidualDijkstra *_dijkstra;
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param length The length (cost) values of the arcs.
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    Suurballe( const Digraph &digraph,
 		               const LengthMap &length,
 		               Node s, Node t ) :
 		      _graph(digraph), _length(length), _flow(0), _local_flow(false),
 		      _potential(0), _local_potential(false), _source(s), _target(t),
 		      _pred(digraph) {}
 		    /// Destructor.
 		    ~Suurballe() {
 		      if (_local_flow) delete _flow;
 		      if (_local_potential) delete _potential;
 		      delete _dijkstra;
+		    }
 		    /// \brief Set the flow map.
 		    ///
 		    /// This function sets the flow map.
 		    ///
 		    /// The found flow contains only 0 and 1 values. It is the union of
 		    /// the found arc-disjoint paths.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    Suurballe& flowMap(FlowMap &map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \brief Set the potential map.
 		    ///
 		    /// This function sets the potential map.
 		    ///
 		    /// The potentials provide the dual solution of the underlying
 		    /// minimum cost flow problem.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    Suurballe& potentialMap(PotentialMap &map) {
 		      if (_local_potential) {
 		        delete _potential;
 		        _local_potential = false;
+		      }
 		      _potential = &map;
 		      return *this;
+		    }
-		    /// \name Execution control
+		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to call the run()
 		    /// function.
 		    /// \n
 		    /// If you only need the flow that is the union of the found
 		    /// arc-disjoint paths, you may call init() and findFlow().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    ///
 		    /// \param k The number of paths to be found.
 		    ///
 		    /// \return \c k if there are at least \c k arc-disjoint paths from
 		    /// \c s to \c t in the digraph. Otherwise it returns the number of
 		    /// arc-disjoint paths found.
 		    ///
 		    /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
 		    /// shortcut of the following code.
 		    /// \code
 		    ///   s.init();
 		    ///   s.findFlow(k);
 		    ///   s.findPaths();
 		    /// \endcode
 		    int run(int k = 2) {
 		      init();
 		      findFlow(k);
 		      findPaths();
 		      return _path_num;
+		    }
 		    /// \brief Initialize the algorithm.
 		    ///
 		    /// This function initializes the algorithm.
 		    void init() {
 		      // Initialize maps
 		      if (!_flow) {
 		        _flow = new FlowMap(_graph);
 		        _local_flow = true;
+		      }
 		      if (!_potential) {
 		        _potential = new PotentialMap(_graph);
 		        _local_potential = true;
+		      }
 		      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
 		      _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
 		                                        *_potential, _pred,
 		                                        _source, _target );
+		    }
 		    /// \brief Execute the successive shortest path algorithm to find
 		    /// an optimal flow.
 		    ///
 		    /// This function executes the successive shortest path algorithm to
 		    /// find a minimum cost flow, which is the union of \c k or less
 		    /// arc-disjoint paths.
 		    ///
 		    /// \return \c k if there are at least \c k arc-disjoint paths from
 		    /// \c s to \c t in the digraph. Otherwise it returns the number of
 		    /// arc-disjoint paths found.
 		    ///
 		    /// \pre \ref init() must be called before using this function.
 		    int findFlow(int k = 2) {
 		      // Find shortest paths
 		      _path_num = 0;
 		      while (_path_num < k) {
 		        // Run Dijkstra
 		        if (!_dijkstra->run()) break;
 		        ++_path_num;
 		        // Set the flow along the found shortest path
 		        Node u = _target;
 		        Arc e;
 		        while ((e = _pred[u]) != INVALID) {
 		          if (u == _graph.target(e)) {
 		            (*_flow)[e] = 1;
 		            u = _graph.source(e);
 		          } else {
 		            (*_flow)[e] = 0;
 		            u = _graph.target(e);
+		          }
+		        }
+		      }
 		      return _path_num;
+		    }
 		    /// \brief Compute the paths from the flow.
 		    ///
 		    /// This function computes the paths from the flow.
 		    ///
 		    /// \pre \ref init() and \ref findFlow() must be called before using
 		    /// this function.
 		    void findPaths() {

lemon/time_measure.h

Show inline comments

@@ -194,301 +194,301 @@
 		    ///\note On <tt>WIN32</tt> platform this value is not calculated.
 		    ///
 		    double cSystemTime() const
+		    {
 		      return cstime;
+		    }
 		    ///Gives back the real time
 		    double realTime() const {return rtime;}
 		  };
 		  inline TimeStamp operator*(double b,const TimeStamp &t)
+		  {
 		    return t*b;
+		  }
 		  ///Prints the time counters
 		  ///Prints the time counters in the following form:
 		  ///
 		  /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
 		  ///
 		  /// where the values are the
 		  /// \li \c u: user cpu time,
 		  /// \li \c s: system cpu time,
 		  /// \li \c cu: user cpu time of children,
 		  /// \li \c cs: system cpu time of children,
 		  /// \li \c real: real time.
 		  /// \relates TimeStamp
 		  /// \note On <tt>WIN32</tt> platform the cummulative values are not
 		  /// calculated.
 		  inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
+		  {
 		    os << "u: " << t.userTime() <<
 		      "s, s: " << t.systemTime() <<
 		      "s, cu: " << t.cUserTime() <<
 		      "s, cs: " << t.cSystemTime() <<
 		      "s, real: " << t.realTime() << "s";
 		    return os;
+		  }
 		  ///Class for measuring the cpu time and real time usage of the process
 		  ///Class for measuring the cpu time and real time usage of the process.
 		  ///It is quite easy-to-use, here is a short example.
 		  ///\code
 		  /// #include<lemon/time_measure.h>
 		  /// #include<iostream>
 		  ///
 		  /// int main()
 		  /// {
 		  ///
 		  ///   ...
 		  ///
 		  ///   Timer t;
 		  ///   doSomething();
 		  ///   std::cout << t << '\n';
 		  ///   t.restart();
 		  ///   doSomethingElse();
 		  ///   std::cout << t << '\n';
 		  ///
 		  ///   ...
 		  ///
 		  /// }
 		  ///\endcode
 		  ///
 		  ///The \ref Timer can also be \ref stop() "stopped" and
 		  ///\ref start() "started" again, so it is possible to compute collected
 		  ///running times.
 		  ///
 		  ///\warning Depending on the operation system and its actual configuration
 		  ///the time counters have a certain (10ms on a typical Linux system)
 		  ///granularity.
 		  ///Therefore this tool is not appropriate to measure very short times.
 		  ///Also, if you start and stop the timer very frequently, it could lead to
 		  ///distorted results.
 		  ///
 		  ///\note If you want to measure the running time of the execution of a certain
 		  ///function, consider the usage of \ref TimeReport instead.
 		  ///
 		  ///\sa TimeReport
 		  class Timer
+		  {
 		    int _running; //Timer is running iff _running>0; (_running>=0 always holds)
 		    TimeStamp start_time; //This is the relativ start-time if the timer
 		                          //is _running, the collected _running time otherwise.
 		    void _reset() {if(_running) start_time.stamp(); else start_time.reset();}
 		  public:
 		    ///Constructor.
 		    ///\param run indicates whether or not the timer starts immediately.
 		    ///
 		    Timer(bool run=true) :_running(run) {_reset();}
-		    ///\name Control the state of the timer
+		    ///\name Control the State of the Timer
 		    ///Basically a Timer can be either running or stopped,
 		    ///but it provides a bit finer control on the execution.
 		    ///The \ref lemon::Timer "Timer" also counts the number of
 		    ///\ref lemon::Timer::start() "start()" executions, and it stops
 		    ///only after the same amount (or more) \ref lemon::Timer::stop()
 		    ///"stop()"s. This can be useful e.g. to compute the running time
 		    ///of recursive functions.
 		    ///@{
 		    ///Reset and stop the time counters
 		    ///This function resets and stops the time counters
 		    ///\sa restart()
 		    void reset()
+		    {
 		      _running=0;
 		      _reset();
+		    }
 		    ///Start the time counters
 		    ///This function starts the time counters.
 		    ///
 		    ///If the timer is started more than ones, it will remain running
 		    ///until the same amount of \ref stop() is called.
 		    ///\sa stop()
 		    void start()
+		    {
 		      if(_running) _running++;
 		      else {
 		        _running=1;
 		        TimeStamp t;
 		        t.stamp();
 		        start_time=t-start_time;
+		      }
+		    }
 		    ///Stop the time counters
 		    ///This function stops the time counters. If start() was executed more than
 		    ///once, then the same number of stop() execution is necessary the really
 		    ///stop the timer.
 		    ///
 		    ///\sa halt()
 		    ///\sa start()
 		    ///\sa restart()
 		    ///\sa reset()
 		    void stop()
+		    {
 		      if(_running && !--_running) {
 		        TimeStamp t;
 		        t.stamp();
 		        start_time=t-start_time;
+		      }
+		    }
 		    ///Halt (i.e stop immediately) the time counters
 		    ///This function stops immediately the time counters, i.e. <tt>t.halt()</tt>
 		    ///is a faster
 		    ///equivalent of the following.
 		    ///\code
 		    ///  while(t.running()) t.stop()
 		    ///\endcode
 		    ///
 		    ///
 		    ///\sa stop()
 		    ///\sa restart()
 		    ///\sa reset()
 		    void halt()
+		    {
 		      if(_running) {
 		        _running=0;
 		        TimeStamp t;
 		        t.stamp();
 		        start_time=t-start_time;
+		      }
+		    }
 		    ///Returns the running state of the timer
 		    ///This function returns the number of stop() exections that is
 		    ///necessary to really stop the timer.
 		    ///For example the timer
 		    ///is running if and only if the return value is \c true
 		    ///(i.e. greater than
 		    ///zero).
 		    int running()  { return _running; }
 		    ///Restart the time counters
 		    ///This function is a shorthand for
 		    ///a reset() and a start() calls.
 		    ///
 		    void restart()
+		    {
 		      reset();
 		      start();
+		    }
 		    ///@}
-		    ///\name Query Functions for the ellapsed time
+		    ///\name Query Functions for the Ellapsed Time
 		    ///@{
 		    ///Gives back the ellapsed user time of the process
 		    double userTime() const
+		    {
 		      return operator TimeStamp().userTime();
+		    }
 		    ///Gives back the ellapsed system time of the process
 		    double systemTime() const
+		    {
 		      return operator TimeStamp().systemTime();
+		    }
 		    ///Gives back the ellapsed user time of the process' children
 		    ///\note On <tt>WIN32</tt> platform this value is not calculated.
 		    ///
 		    double cUserTime() const
+		    {
 		      return operator TimeStamp().cUserTime();
+		    }
 		    ///Gives back the ellapsed user time of the process' children
 		    ///\note On <tt>WIN32</tt> platform this value is not calculated.
 		    ///
 		    double cSystemTime() const
+		    {
 		      return operator TimeStamp().cSystemTime();
+		    }
 		    ///Gives back the ellapsed real time
 		    double realTime() const
+		    {
 		      return operator TimeStamp().realTime();
+		    }
 		    ///Computes the ellapsed time
 		    ///This conversion computes the ellapsed time, therefore you can print
 		    ///the ellapsed time like this.
 		    ///\code
 		    ///  Timer t;
 		    ///  doSomething();
 		    ///  std::cout << t << '\n';
 		    ///\endcode
 		    operator TimeStamp () const
+		    {
 		      TimeStamp t;
 		      t.stamp();
 		      return _running?t-start_time:start_time;
+		    }
 		    ///@}
 		  };
 		  ///Same as Timer but prints a report on destruction.
 		  ///Same as \ref Timer but prints a report on destruction.
 		  ///This example shows its usage.
 		  ///\code
 		  ///  void myAlg(ListGraph &g,int n)
 		  ///  {
 		  ///    TimeReport tr("Running time of myAlg: ");
 		  ///    ... //Here comes the algorithm
 		  ///  }
 		  ///\endcode
 		  ///
 		  ///\sa Timer
 		  ///\sa NoTimeReport
 		  class TimeReport : public Timer
+		  {
 		    std::string _title;
 		    std::ostream &_os;
 		  public:
 		    ///Constructor
 		    ///Constructor.
 		    ///\param title This text will be printed before the ellapsed time.
 		    ///\param os The stream to print the report to.
 		    ///\param run Sets whether the timer should start immediately.
 		    TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true)
 		      : Timer(run), _title(title), _os(os){}
 		    ///Destructor that prints the ellapsed time
 		    ~TimeReport()
+		    {
 		      _os << _title << *this << std::endl;
+		    }
 		  };
 		  ///'Do nothing' version of TimeReport
 		  ///\sa TimeReport
 		  ///
 		  class NoTimeReport
+		  {
 		  public:
 		    ///\e

tools/dimacs-solver.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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 tools
 		///\file
 		///\brief DIMACS problem solver.
 		///
 		/// This program solves various problems given in DIMACS format.
 		///
 		/// See
 		/// \verbatim
 		///  dimacs-solver --help
-		/// \endverbatim
+		/// \code
 		///   dimacs-solver --help
 		/// \endcode
 		/// for more info on usage.
 		///
 		#include <iostream>
 		#include <fstream>
 		#include <cstring>
 		#include <lemon/smart_graph.h>
 		#include <lemon/dimacs.h>
 		#include <lemon/lgf_writer.h>
 		#include <lemon/time_measure.h>
 		#include <lemon/arg_parser.h>
 		#include <lemon/error.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/preflow.h>
 		#include <lemon/max_matching.h>
 		using namespace lemon;
 		typedef SmartDigraph Digraph;
 		DIGRAPH_TYPEDEFS(Digraph);
 		typedef SmartGraph Graph;
 		template<class Value>
 		void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
 		              DimacsDescriptor &desc)
+		{
 		  bool report = !ap.given("q");
 		  Digraph g;
 		  Node s;
 		  Digraph::ArcMap<Value> len(g);
 		  Timer t;
 		  t.restart();
 		  readDimacsSp(is, g, len, s, desc);
 		  if(report) std::cerr << "Read the file: " << t << '\n';
 		  t.restart();
 		  Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
 		  if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
 		  t.restart();
 		  dij.run(s);
 		  if(report) std::cerr << "Run Dijkstra: " << t << '\n';
+		}
 		template<class Value>
 		void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
 		               Value infty, DimacsDescriptor &desc)
+		{
 		  bool report = !ap.given("q");
 		  Digraph g;
 		  Node s,t;
 		  Digraph::ArcMap<Value> cap(g);
 		  Timer ti;
 		  ti.restart();
 		  readDimacsMax(is, g, cap, s, t, infty, desc);
 		  if(report) std::cerr << "Read the file: " << ti << '\n';
 		  ti.restart();
 		  Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
 		  if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
 		  ti.restart();
 		  pre.run();
 		  if(report) std::cerr << "Run Preflow: " << ti << '\n';
 		  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
+		}
 		void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
 		              DimacsDescriptor &desc)
+		{
 		  bool report = !ap.given("q");
 		  Graph g;
 		  Timer ti;
 		  ti.restart();
 		  readDimacsMat(is, g, desc);
 		  if(report) std::cerr << "Read the file: " << ti << '\n';
 		  ti.restart();
 		  MaxMatching<Graph> mat(g);
 		  if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
 		  ti.restart();
 		  mat.run();
 		  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
 		  if(report) std::cerr << "\nCardinality of max matching: "
 		                       << mat.matchingSize() << '\n';
+		}
 		template<class Value>
 		void solve(ArgParser &ap, std::istream &is, std::ostream &os,
 		           DimacsDescriptor &desc)
+		{
 		  std::stringstream iss(static_cast<std::string>(ap["infcap"]));
 		  Value infty;
 		  iss >> infty;
 		  if(iss.fail())
+		    {
 		      std::cerr << "Cannot interpret '"
 		                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
 		                << std::endl;
 		      exit(1);

tools/dimacs-to-lgf.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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 tools
 		///\file
 		///\brief DIMACS to LGF converter.
 		///
 		/// This program converts various DIMACS formats to the LEMON Digraph Format
 		/// (LGF).
 		///
 		/// See
 		/// \verbatim
 		///  dimacs-to-lgf --help
 		/// \endverbatim
 		/// for more info on usage.
 		///
+		/// \code
 		///   dimacs-to-lgf --help
 		/// \endcode
 		/// for more info on the usage.
 		#include <iostream>
 		#include <fstream>
 		#include <cstring>
 		#include <lemon/smart_graph.h>
 		#include <lemon/dimacs.h>
 		#include <lemon/lgf_writer.h>
 		#include <lemon/arg_parser.h>
 		#include <lemon/error.h>
 		using namespace std;
 		using namespace lemon;
 		int main(int argc, const char *argv[]) {
 		  typedef SmartDigraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::ArcIt ArcIt;
 		  typedef Digraph::NodeIt NodeIt;
 		  typedef Digraph::ArcMap<double> DoubleArcMap;
 		  typedef Digraph::NodeMap<double> DoubleNodeMap;
 		  std::string inputName;
 		  std::string outputName;
 		  ArgParser ap(argc, argv);
 		  ap.other("[INFILE [OUTFILE]]",
 		           "If either the INFILE or OUTFILE file is missing the standard\n"
 		           "     input/output will be used instead.")
 		    .run();
 		  ifstream input;
 		  ofstream output;
 		  switch(ap.files().size())
+		    {
 		    case 2:
 		      output.open(ap.files()[1].c_str());
 		      if (!output) {
 		        throw IoError("Cannot open the file for writing", ap.files()[1]);
+		      }
 		    case 1:
 		      input.open(ap.files()[0].c_str());
 		      if (!input) {
 		        throw IoError("File cannot be found", ap.files()[0]);
+		      }
 		    case 0:
 		      break;
 		    default:
 		      cerr << ap.commandName() << ": too many arguments\n";
 		      return 1;
+		  }
 		  istream& is = (ap.files().size()<1 ? cin : input);
 		  ostream& os = (ap.files().size()<2 ? cout : output);
 		  DimacsDescriptor desc = dimacsType(is);
 		  switch(desc.type)
+		    {
 		    case DimacsDescriptor::MIN:
+		      {
 		        Digraph digraph;
 		        DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
 		        DoubleNodeMap supply(digraph);
 		        readDimacsMin(is, digraph, lower, capacity, cost, supply, 0, desc);
 		        DigraphWriter<Digraph>(digraph, os).
 		          nodeMap("supply", supply).
 		          arcMap("lower", lower).
 		          arcMap("capacity", capacity).
 		          arcMap("cost", cost).
 		          attribute("problem","min").
 		          run();
+		      }
 		      break;
 		    case DimacsDescriptor::MAX:
+		      {
 		        Digraph digraph;
 		        Node s, t;
 		        DoubleArcMap capacity(digraph);
 		        readDimacsMax(is, digraph, capacity, s, t, 0, desc);
 		        DigraphWriter<Digraph>(digraph, os).
 		          arcMap("capacity", capacity).
 		          node("source", s).
 		          node("target", t).
 		          attribute("problem","max").
 		          run();
+		      }
 		      break;
 		    case DimacsDescriptor::SP:
+		      {
 		        Digraph digraph;
 		        Node s;
 		        DoubleArcMap capacity(digraph);

tools/lgf-gen.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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 tools
 		/// \file
 		/// \brief Special plane digraph generator.
 		///
 		/// Graph generator application for various types of plane graphs.
 		///
 		/// See
 		/// \verbatim
 		///  lgf-gen --help
-		/// \endverbatim
+		/// \code
 		///   lgf-gen --help
 		/// \endcode
 		/// for more info on the usage.
 		///
 		#include <algorithm>
 		#include <set>
 		#include <ctime>
 		#include <lemon/list_graph.h>
 		#include <lemon/random.h>
 		#include <lemon/dim2.h>
 		#include <lemon/bfs.h>
 		#include <lemon/counter.h>
 		#include <lemon/suurballe.h>
 		#include <lemon/graph_to_eps.h>
 		#include <lemon/lgf_writer.h>
 		#include <lemon/arg_parser.h>
 		#include <lemon/euler.h>
 		#include <lemon/math.h>
 		#include <lemon/kruskal.h>
 		#include <lemon/time_measure.h>
 		using namespace lemon;
 		typedef dim2::Point<double> Point;
 		GRAPH_TYPEDEFS(ListGraph);
 		bool progress=true;
 		int N;
 		// int girth;
 		ListGraph g;
 		std::vector<Node> nodes;
 		ListGraph::NodeMap<Point> coords(g);
 		double totalLen(){
 		  double tlen=0;
 		  for(EdgeIt e(g);e!=INVALID;++e)
 		    tlen+=sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare());
 		  return tlen;
+		}
 		int tsp_impr_num=0;
 		const double EPSILON=1e-8;
 		bool tsp_improve(Node u, Node v)
+		{
 		  double luv=std::sqrt((coords[v]-coords[u]).normSquare());
 		  Node u2=u;
 		  Node v2=v;
 		  do {
 		    Node n;
 		    for(IncEdgeIt e(g,v2);(n=g.runningNode(e))==u2;++e) { }
 		    u2=v2;
 		    v2=n;
 		    if(luv+std::sqrt((coords[v2]-coords[u2]).normSquare())-EPSILON>
 		       std::sqrt((coords[u]-coords[u2]).normSquare())+
 		       std::sqrt((coords[v]-coords[v2]).normSquare()))
+		      {
 		         g.erase(findEdge(g,u,v));
 		         g.erase(findEdge(g,u2,v2));
 		        g.addEdge(u2,u);
 		        g.addEdge(v,v2);
 		        tsp_impr_num++;
 		        return true;
+		      }
 		  } while(v2!=u);
 		  return false;
+		}
 		bool tsp_improve(Node u)
+		{
 		  for(IncEdgeIt e(g,u);e!=INVALID;++e)
 		    if(tsp_improve(u,g.runningNode(e))) return true;
 		  return false;
+		}
 		void tsp_improve()
+		{
 		  bool b;
 		  do {
 		    b=false;
 		    for(NodeIt n(g);n!=INVALID;++n)
 		      if(tsp_improve(n)) b=true;
 		  } while(b);
+		}
 		void tsp()
+		{
 		  for(int i=0;i<N;i++) g.addEdge(nodes[i],nodes[(i+1)%N]);
 		  tsp_improve();
+		}
 		class Line
+		{
 		public:

0 comments (0 inline)

RhodeCode

Login to your account