LEMON/LEMON-official Changeset - r1081:f1398882a928

doc/groups.dox

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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -270,17 +270,17 @@
 		/**
 		@defgroup shortest_path Shortest Path Algorithms
 		@ingroup algs
 		\brief Algorithms for finding shortest paths.
 		This group contains the algorithms for finding shortest paths in digraphs.
-		 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
 		 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
 		   source node when all arc lengths are non-negative.
 		 - \ref Suurballe A successive shortest path algorithm for finding
 		   arc-disjoint paths between two nodes having minimum total length.
 		*/
 		/**
 		@defgroup max_flow Maximum Flow Algorithms
 		@ingroup algs
@@ -301,17 +301,17 @@
 		    \quad \forall u\in V\setminus\{s,t\} \f]
 		\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 		\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
 		Tarjan for solving this problem. It also provides functions to query the
 		minimum cut, which is the dual problem of maximum flow.
-		\ref Circulation is a preflow push-relabel algorithm implemented directly
 		\ref Circulation is a preflow push-relabel algorithm implemented directly
 		for finding feasible circulations, which is a somewhat different problem,
 		but it is strongly related to maximum flow.
 		For more information, see \ref Circulation.
 		*/
 		/**
 		@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
 		@ingroup algs

doc/lgf.dox

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
 * Copyright (C) 2003-2011
 * 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,

doc/min_cost_flow.dox

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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -76,17 +76,17 @@
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
 		   - \f$\pi(u)<=0\f$;
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
 		\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
 		\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
 		All algorithms provide dual solution (node potentials), as well,
 		if an optimal flow is found.
@@ -114,17 +114,17 @@
 		when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
 		instead of the <em>"greater or equal"</em> (GEQ) constraints.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
-		It means that the total demand must be less or equal to the
 		It means that the total demand must be less or equal to the
 		total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
 		positive) and all the demands have to be satisfied, but there
 		could be supplies that are not carried out from the supply
 		nodes.
 		The equality form is also a special case of this form, of course.
 		You could easily transform this case to the \ref mcf_def "GEQ form"
 		of the problem by reversing the direction of the arcs and taking the

lemon/adaptors.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -413,17 +413,17 @@
 		    NF* _node_filter;
 		    AF* _arc_filter;
 		    SubDigraphBase()
 		      : Parent(), _node_filter(0), _arc_filter(0) { }
 		    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
 		      Parent::initialize(digraph);
 		      _node_filter = &node_filter;
-		      _arc_filter = &arc_filter;
 		      _arc_filter = &arc_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void first(Node& i) const {
@@ -500,21 +500,21 @@
 		        arc = Parent::findArc(source, target, arc);
+		      }
 		      return arc;
+		    }
 		  public:
 		    template <typename V>
 		    class NodeMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
-			      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
+		    class NodeMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
 		              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
-			LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
+		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
@@ -527,19 +527,19 @@
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class ArcMap
 		    class ArcMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
-			      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
+		              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
 		        : Parent(adaptor) {}
@@ -574,17 +574,17 @@
 		    NF* _node_filter;
 		    AF* _arc_filter;
 		    SubDigraphBase()
 		      : Parent(), _node_filter(0), _arc_filter(0) { }
 		    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
 		      Parent::initialize(digraph);
 		      _node_filter = &node_filter;
-		      _arc_filter = &arc_filter;
 		      _arc_filter = &arc_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void first(Node& i) const {
@@ -643,20 +643,20 @@
 		      Arc arc = Parent::findArc(source, target, prev);
 		      while (arc != INVALID && !(*_arc_filter)[arc]) {
 		        arc = Parent::findArc(source, target, arc);
+		      }
 		      return arc;
+		    }
 		    template <typename V>
-		    class NodeMap
 		    class NodeMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
-		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
@@ -670,17 +670,17 @@
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class ArcMap
 		    class ArcMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
@@ -1011,20 +1011,20 @@
 		      Edge edge = Parent::findEdge(u, v, prev);
 		      while (edge != INVALID && !(*_edge_filter)[edge]) {
 		        edge = Parent::findEdge(u, v, edge);
+		      }
 		      return edge;
+		    }
 		    template <typename V>
-		    class NodeMap
 		    class NodeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
-		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
@@ -1038,20 +1038,20 @@
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class ArcMap
 		    class ArcMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
-		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
@@ -1065,20 +1065,20 @@
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class EdgeMap
 		    class EdgeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
-		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
 		        : Parent(adaptor) {}
@@ -1107,18 +1107,18 @@
 		    typedef GR Graph;
 		    typedef NF NodeFilterMap;
 		    typedef EF EdgeFilterMap;
 		    typedef SubGraphBase Adaptor;
 		  protected:
 		    NF* _node_filter;
 		    EF* _edge_filter;
 		    SubGraphBase()
 			  : Parent(), _node_filter(0), _edge_filter(0) { }
 		    SubGraphBase()
 		          : Parent(), _node_filter(0), _edge_filter(0) { }
 		    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
 		      Parent::initialize(graph);
 		      _node_filter = &node_filter;
 		      _edge_filter = &edge_filter;
+		    }
 		  public:
@@ -1209,20 +1209,20 @@
 		      Edge edge = Parent::findEdge(u, v, prev);
 		      while (edge != INVALID && !(*_edge_filter)[edge]) {
 		        edge = Parent::findEdge(u, v, edge);
+		      }
 		      return edge;
+		    }
 		    template <typename V>
-		    class NodeMap
 		    class NodeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
-		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
@@ -1236,20 +1236,20 @@
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class ArcMap
 		    class ArcMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
-		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
@@ -1263,21 +1263,21 @@
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class EdgeMap
 		    class EdgeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 			LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
@@ -1490,17 +1490,17 @@
 		           typename NF = typename GR::template NodeMap<bool>,
 		           typename Enable = void>
 		  class FilterNodes :
 		    public DigraphAdaptorExtender<
 		      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
 		                     true> > {
 		#endif
 		    typedef DigraphAdaptorExtender<
-		      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
 		      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
 		                     true> > Parent;
 		  public:
 		    typedef GR Digraph;
 		    typedef NF NodeFilterMap;
 		    typedef typename Parent::Node Node;
@@ -1511,17 +1511,17 @@
 		    FilterNodes() : const_true_map() {}
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subgraph for the given digraph or graph with the
 		    /// given node filter map.
-		    FilterNodes(GR& graph, NF& node_filter)
 		    FilterNodes(GR& graph, NF& node_filter)
 		      : Parent(), const_true_map()
+		    {
 		      Parent::initialize(graph, node_filter, const_true_map);
+		    }
 		    /// \brief Sets the status of the given node
 		    ///
 		    /// This function sets the status of the given node.
@@ -1549,21 +1549,21 @@
 		    void enable(const Node& n) const { Parent::status(n, true); }
 		  };
 		  template<typename GR, typename NF>
 		  class FilterNodes<GR, NF,
 		                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
 		    public GraphAdaptorExtender<
-		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		                   true> > {
 		    typedef GraphAdaptorExtender<
-		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		                   true> > Parent;
 		  public:
 		    typedef GR Graph;
 		    typedef NF NodeFilterMap;
 		    typedef typename Parent::Node Node;
@@ -1637,17 +1637,17 @@
 		  template<typename DGR,
 		           typename AF = typename DGR::template ArcMap<bool> >
 		  class FilterArcs :
 		    public DigraphAdaptorExtender<
 		      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
 		                     AF, false> > {
 		#endif
 		    typedef DigraphAdaptorExtender<
-		      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
 		      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
 		                     AF, false> > Parent;
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		    /// The type of the arc filter map.
 		    typedef AF ArcFilterMap;
@@ -1743,21 +1743,21 @@
 		  template<typename GR,
 		           typename EF>
 		  class FilterEdges {
 		#else
 		  template<typename GR,
 		           typename EF = typename GR::template EdgeMap<bool> >
 		  class FilterEdges :
 		    public GraphAdaptorExtender<
-		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
 		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
 		                   EF, false> > {
 		#endif
 		    typedef GraphAdaptorExtender<
-		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
 		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
 		                   EF, false> > Parent;
 		  public:
 		    /// The type of the adapted graph.
 		    typedef GR Graph;
 		    /// The type of the edge filter map.
 		    typedef EF EdgeFilterMap;
@@ -1772,17 +1772,17 @@
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subgraph for the given graph with the given edge
 		    /// filter map.
-		    FilterEdges(GR& graph, EF& edge_filter)
 		    FilterEdges(GR& graph, EF& edge_filter)
 		      : Parent(), const_true_map() {
 		      Parent::initialize(graph, const_true_map, edge_filter);
+		    }
 		    /// \brief Sets the status of the given edge
 		    ///
 		    /// This function sets the status of the given edge.
 		    /// It is done by simply setting the assigned value of \c e
@@ -1840,17 +1840,17 @@
 		    typedef typename Digraph::Node Node;
 		    class Arc {
 		      friend class UndirectorBase;
 		    protected:
 		      Edge _edge;
 		      bool _forward;
-		      Arc(const Edge& edge, bool forward)
 		      Arc(const Edge& edge, bool forward)
 		        : _edge(edge), _forward(forward) {}
 		    public:
 		      Arc() {}
 		      Arc(Invalid) : _edge(INVALID), _forward(true) {}
 		      operator const Edge&() const { return _edge; }
@@ -2080,17 +2080,17 @@
 		      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
 		      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
 		      ArcMapBase(const UndirectorBase<DGR>& adaptor) :
 		        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
 		      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
-		        : _forward(*adaptor._digraph, value),
 		        : _forward(*adaptor._digraph, value),
 		          _backward(*adaptor._digraph, value) {}
 		      void set(const Arc& a, const V& value) {
 		        if (direction(a)) {
 		          _forward.set(a, value);
 		        } else {
 		          _backward.set(a, value);
+		        }
@@ -2198,17 +2198,17 @@
 		    };
 		    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
 		    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
 		    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
 		    typedef EdgeNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
 		  protected:
 		    UndirectorBase() : _digraph(0) {}
 		    DGR* _digraph;
@@ -2702,17 +2702,17 @@
 		#ifdef DOXYGEN
 		  template<typename DGR, typename CM, typename FM, typename TL>
 		  class ResidualDigraph
 		#else
 		  template<typename DGR,
 		           typename CM = typename DGR::template ArcMap<int>,
 		           typename FM = CM,
 		           typename TL = Tolerance<typename CM::Value> >
-		  class ResidualDigraph
 		  class ResidualDigraph
 		    : public SubDigraph<
 		        Undirector<const DGR>,
 		        ConstMap<typename DGR::Node, Const<bool, true> >,
 		        typename Undirector<const DGR>::template CombinedArcMap<
 		          _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
 		          _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
 		#endif
+		  {
@@ -2759,17 +2759,17 @@
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the residual digraph adaptor. The parameters are the
 		    /// digraph, the capacity map, the flow map, and a tolerance object.
 		    ResidualDigraph(const DGR& digraph, const CM& capacity,
 		                    FM& flow, const TL& tolerance = Tolerance())
-		      : Parent(), _capacity(&capacity), _flow(&flow),
 		      : Parent(), _capacity(&capacity), _flow(&flow),
 		        _graph(digraph), _node_filter(),
 		        _forward_filter(capacity, flow, tolerance),
 		        _backward_filter(capacity, flow, tolerance),
 		        _arc_filter(_forward_filter, _backward_filter)
+		    {
 		      Parent::initialize(_graph, _node_filter, _arc_filter);
+		    }
@@ -2841,17 +2841,17 @@
 		      const Adaptor* _adaptor;
 		    public:
 		      /// The key type of the map
 		      typedef Arc Key;
 		      /// The value type of the map
 		      typedef typename CapacityMap::Value Value;
 		      /// Constructor
-		      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
 		      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
 		        : _adaptor(&adaptor) {}
 		      /// Returns the value associated with the given residual arc
 		      Value operator[](const Arc& a) const {
 		        return _adaptor->residualCapacity(a);
+		      }
 		    };
@@ -3418,17 +3418,17 @@
 		      return Parent::arc(a);
+		    }
 		    /// \brief Node map combined from two original node maps
 		    ///
 		    /// This map adaptor class adapts two node maps of the original digraph
 		    /// to get a node map of the split digraph.
 		    /// Its value type is inherited from the first node map type (\c IN).
-		    /// \tparam IN The type of the node map for the in-nodes.
 		    /// \tparam IN The type of the node map for the in-nodes.
 		    /// \tparam OUT The type of the node map for the out-nodes.
 		    template <typename IN, typename OUT>
 		    class CombinedNodeMap {
 		    public:
 		      /// The key type of the map
 		      typedef Node Key;
 		      /// The value type of the map

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
 * Copyright (C) 2003-2011
 * 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,

lemon/bits/array_map.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -65,17 +65,17 @@
 		    // The map type.
 		    typedef ArrayMap Map;
 		    // The notifier type.
 		    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
 		  private:
 		    // The MapBase of the Map which imlements the core regisitry function.
 		    typedef typename Notifier::ObserverBase Parent;
 		    typedef std::allocator<Value> Allocator;
 		  public:
 		    // \brief Graph initialized map constructor.

lemon/bits/default_map.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -152,17 +152,17 @@
 		  // DefaultMap class
 		  template <typename _Graph, typename _Item, typename _Value>
 		  class DefaultMap
 		    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
 		    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
 		  public:
 		    typedef DefaultMap<_Graph, _Item, _Value> Map;
 		    typedef typename Parent::GraphType GraphType;
 		    typedef typename Parent::Value Value;
 		    explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
 		    DefaultMap(const GraphType& graph, const Value& value)
 		      : Parent(graph, value) {}
 		    DefaultMap& operator=(const DefaultMap& cmap) {

lemon/bits/edge_set_extender.h

Show inline comments

 		/* -*- C++ -*-
+		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -58,21 +58,21 @@
+		    }
 		    Arc fromId(int id, Arc) const {
 		      return Parent::arcFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Arc &e) const {
 		      if (n == Parent::source(e))
-			return Parent::target(e);
+		        return Parent::target(e);
 		      else if(n==Parent::target(e))
-			return Parent::source(e);
+		        return Parent::source(e);
 		      else
-			return INVALID;
+		        return INVALID;
+		    }
 		    // Alteration notifier extensions
 		    // The arc observer registry.
 		    typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
@@ -86,105 +86,105 @@
 		    // Gives back the arc alteration notifier.
 		    ArcNotifier& notifier(Arc) const {
 		      return arc_notifier;
+		    }
 		    // Iterable extensions
-		    class NodeIt : public Node {
 		    class NodeIt : public Node {
 		      const Digraph* digraph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
-			_graph.first(static_cast<Node&>(*this));
+		        _graph.first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Digraph& _graph, const Node& node)
 			: Node(node), digraph(&_graph) {}
 		      NodeIt(const Digraph& _graph, const Node& node)
 		        : Node(node), digraph(&_graph) {}
 		      NodeIt& operator++() {
 			digraph->next(*this);
-			return *this;
+		      NodeIt& operator++() {
 		        digraph->next(*this);
 		        return *this;
+		      }
 		    };
-		    class ArcIt : public Arc {
 		    class ArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
-			_graph.first(static_cast<Arc&>(*this));
+		        _graph.first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Digraph& _graph, const Arc& e) :
 			Arc(e), digraph(&_graph) { }
 		      ArcIt(const Digraph& _graph, const Arc& e) :
 		        Arc(e), digraph(&_graph) { }
 		      ArcIt& operator++() {
 			digraph->next(*this);
-			return *this;
+		      ArcIt& operator++() {
 		        digraph->next(*this);
 		        return *this;
+		      }
 		    };
-		    class OutArcIt : public Arc {
 		    class OutArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Digraph& _graph, const Node& node)
 			: digraph(&_graph) {
-			_graph.firstOut(*this, node);
+		      OutArcIt(const Digraph& _graph, const Node& node)
 		        : digraph(&_graph) {
 		        _graph.firstOut(*this, node);
+		      }
 		      OutArcIt(const Digraph& _graph, const Arc& arc)
 			: Arc(arc), digraph(&_graph) {}
 		      OutArcIt(const Digraph& _graph, const Arc& arc)
 		        : Arc(arc), digraph(&_graph) {}
 		      OutArcIt& operator++() {
 			digraph->nextOut(*this);
-			return *this;
+		      OutArcIt& operator++() {
 		        digraph->nextOut(*this);
 		        return *this;
+		      }
 		    };
-		    class InArcIt : public Arc {
 		    class InArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Digraph& _graph, const Node& node)
 			: digraph(&_graph) {
-			_graph.firstIn(*this, node);
+		      InArcIt(const Digraph& _graph, const Node& node)
 		        : digraph(&_graph) {
 		        _graph.firstIn(*this, node);
+		      }
 		      InArcIt(const Digraph& _graph, const Arc& arc) :
 			Arc(arc), digraph(&_graph) {}
 		      InArcIt(const Digraph& _graph, const Arc& arc) :
 		        Arc(arc), digraph(&_graph) {}
 		      InArcIt& operator++() {
 			digraph->nextIn(*this);
-			return *this;
+		      InArcIt& operator++() {
 		        digraph->nextIn(*this);
 		        return *this;
+		      }
 		    };
 		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (ie. the source in this case) of the iterator
 		    Node baseNode(const OutArcIt &e) const {
@@ -210,49 +210,49 @@
 		    // iterator
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    using Parent::first;
 		    // Mappable extension
 		    template <typename _Value>
-		    class ArcMap
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
 		      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
 		    public:
 		      explicit ArcMap(const Digraph& _g)
 			: Parent(_g) {}
 		      ArcMap(const Digraph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      explicit ArcMap(const Digraph& _g)
 		        : Parent(_g) {}
 		      ArcMap(const Digraph& _g, const _Value& _v)
 		        : Parent(_g, _v) {}
 		      ArcMap& operator=(const ArcMap& cmap) {
-			return operator=<ArcMap>(cmap);
+		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
-			return *this;
+		        return *this;
+		      }
 		    };
 		    // Alteration extension
 		    Arc addArc(const Node& from, const Node& to) {
 		      Arc arc = Parent::addArc(from, to);
 		      notifier(Arc()).add(arc);
 		      return arc;
+		    }
 		    void clear() {
 		      notifier(Arc()).clear();
 		      Parent::clear();
+		    }
 		    void erase(const Arc& arc) {
 		      notifier(Arc()).erase(arc);
 		      Parent::erase(arc);
@@ -307,21 +307,21 @@
+		    }
 		    Edge fromId(int id, Edge) const {
 		      return Parent::edgeFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Edge &e) const {
 		      if( n == Parent::u(e))
-			return Parent::v(e);
+		        return Parent::v(e);
 		      else if( n == Parent::v(e))
-			return Parent::u(e);
+		        return Parent::u(e);
 		      else
-			return INVALID;
+		        return INVALID;
+		    }
 		    Arc oppositeArc(const Arc &e) const {
 		      return Parent::direct(e, !Parent::direction(e));
+		    }
 		    using Parent::direct;
 		    Arc direct(const Edge &e, const Node &s) const {
@@ -335,164 +335,164 @@
 		  protected:
 		    mutable ArcNotifier arc_notifier;
 		    mutable EdgeNotifier edge_notifier;
 		  public:
 		    using Parent::notifier;
 		    ArcNotifier& notifier(Arc) const {
 		      return arc_notifier;
+		    }
 		    EdgeNotifier& notifier(Edge) const {
 		      return edge_notifier;
+		    }
-		    class NodeIt : public Node {
 		    class NodeIt : public Node {
 		      const Graph* graph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
-			_graph.first(static_cast<Node&>(*this));
+		        _graph.first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Graph& _graph, const Node& node)
 			: Node(node), graph(&_graph) {}
 		      NodeIt(const Graph& _graph, const Node& node)
 		        : Node(node), graph(&_graph) {}
 		      NodeIt& operator++() {
 			graph->next(*this);
-			return *this;
+		      NodeIt& operator++() {
 		        graph->next(*this);
 		        return *this;
+		      }
 		    };
-		    class ArcIt : public Arc {
 		    class ArcIt : public Arc {
 		      const Graph* graph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
-			_graph.first(static_cast<Arc&>(*this));
+		        _graph.first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Graph& _graph, const Arc& e) :
 			Arc(e), graph(&_graph) { }
 		      ArcIt(const Graph& _graph, const Arc& e) :
 		        Arc(e), graph(&_graph) { }
 		      ArcIt& operator++() {
 			graph->next(*this);
-			return *this;
+		      ArcIt& operator++() {
 		        graph->next(*this);
 		        return *this;
+		      }
 		    };
-		    class OutArcIt : public Arc {
 		    class OutArcIt : public Arc {
 		      const Graph* graph;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Graph& _graph, const Node& node)
 			: graph(&_graph) {
-			_graph.firstOut(*this, node);
+		      OutArcIt(const Graph& _graph, const Node& node)
 		        : graph(&_graph) {
 		        _graph.firstOut(*this, node);
+		      }
 		      OutArcIt(const Graph& _graph, const Arc& arc)
 			: Arc(arc), graph(&_graph) {}
 		      OutArcIt(const Graph& _graph, const Arc& arc)
 		        : Arc(arc), graph(&_graph) {}
 		      OutArcIt& operator++() {
 			graph->nextOut(*this);
-			return *this;
+		      OutArcIt& operator++() {
 		        graph->nextOut(*this);
 		        return *this;
+		      }
 		    };
-		    class InArcIt : public Arc {
 		    class InArcIt : public Arc {
 		      const Graph* graph;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Graph& _graph, const Node& node)
 			: graph(&_graph) {
-			_graph.firstIn(*this, node);
+		      InArcIt(const Graph& _graph, const Node& node)
 		        : graph(&_graph) {
 		        _graph.firstIn(*this, node);
+		      }
 		      InArcIt(const Graph& _graph, const Arc& arc) :
 			Arc(arc), graph(&_graph) {}
 		      InArcIt(const Graph& _graph, const Arc& arc) :
 		        Arc(arc), graph(&_graph) {}
 		      InArcIt& operator++() {
 			graph->nextIn(*this);
-			return *this;
+		      InArcIt& operator++() {
 		        graph->nextIn(*this);
 		        return *this;
+		      }
 		    };
-		    class EdgeIt : public Parent::Edge {
 		    class EdgeIt : public Parent::Edge {
 		      const Graph* graph;
 		    public:
 		      EdgeIt() { }
 		      EdgeIt(Invalid i) : Edge(i) { }
 		      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
-			_graph.first(static_cast<Edge&>(*this));
+		        _graph.first(static_cast<Edge&>(*this));
+		      }
 		      EdgeIt(const Graph& _graph, const Edge& e) :
 			Edge(e), graph(&_graph) { }
 		      EdgeIt(const Graph& _graph, const Edge& e) :
 		        Edge(e), graph(&_graph) { }
 		      EdgeIt& operator++() {
 			graph->next(*this);
-			return *this;
+		      EdgeIt& operator++() {
 		        graph->next(*this);
 		        return *this;
+		      }
 		    };
 		    class IncEdgeIt : public Parent::Edge {
 		      friend class EdgeSetExtender;
 		      const Graph* graph;
 		      bool direction;
 		    public:
 		      IncEdgeIt() { }
 		      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
 		      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
-			_graph.firstInc(*this, direction, n);
+		        _graph.firstInc(*this, direction, n);
+		      }
 		      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
 			: graph(&_graph), Edge(ue) {
 			direction = (_graph.source(ue) == n);
 		        : graph(&_graph), Edge(ue) {
 		        direction = (_graph.source(ue) == n);
+		      }
 		      IncEdgeIt& operator++() {
 			graph->nextInc(*this, direction);
 			return *this;
 		        graph->nextInc(*this, direction);
 		        return *this;
+		      }
 		    };
 		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (ie. the source in this case) of the iterator
 		    Node baseNode(const OutArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
@@ -529,76 +529,76 @@
 		    //
 		    // Returns the running node of the iterator
 		    Node runningNode(const IncEdgeIt &e) const {
 		      return e.direction ? v(e) : u(e);
+		    }
 		    template <typename _Value>
-		    class ArcMap
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
 		      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
 		    public:
 		      explicit ArcMap(const Graph& _g)
 			: Parent(_g) {}
 		      ArcMap(const Graph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      explicit ArcMap(const Graph& _g)
 		        : Parent(_g) {}
 		      ArcMap(const Graph& _g, const _Value& _v)
 		        : Parent(_g, _v) {}
 		      ArcMap& operator=(const ArcMap& cmap) {
-			return operator=<ArcMap>(cmap);
+		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
-			return *this;
+		        return *this;
+		      }
 		    };
 		    template <typename _Value>
-		    class EdgeMap
 		    class EdgeMap
 		      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
 		      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
 		    public:
 		      explicit EdgeMap(const Graph& _g)
 			: Parent(_g) {}
 		      explicit EdgeMap(const Graph& _g)
 		        : Parent(_g) {}
 		      EdgeMap(const Graph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      EdgeMap(const Graph& _g, const _Value& _v)
 		        : Parent(_g, _v) {}
 		      EdgeMap& operator=(const EdgeMap& cmap) {
-			return operator=<EdgeMap>(cmap);
+		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
-			return *this;
+		        return *this;
+		      }
 		    };
 		    // Alteration extension
 		    Edge addEdge(const Node& from, const Node& to) {
 		      Edge edge = Parent::addEdge(from, to);
 		      notifier(Edge()).add(edge);
 		      std::vector<Arc> arcs;
 		      arcs.push_back(Parent::direct(edge, true));
 		      arcs.push_back(Parent::direct(edge, false));
 		      notifier(Arc()).add(arcs);
 		      return edge;
+		    }
 		    void clear() {
 		      notifier(Arc()).clear();
 		      notifier(Edge()).clear();
 		      Parent::clear();
+		    }
 		    void erase(const Edge& edge) {
 		      std::vector<Arc> arcs;
@@ -614,14 +614,14 @@
 		      arc_notifier.setContainer(*this);
 		      edge_notifier.setContainer(*this);
+		    }
 		    ~EdgeSetExtender() {
 		      edge_notifier.clear();
 		      arc_notifier.clear();
+		    }
 		  };
+		}
 		#endif

lemon/bits/graph_adaptor_extender.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
 * Copyright (C) 2003-2011
 * 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,

lemon/bits/map_extender.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
 * Copyright (C) 2003-2011
 * 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,

lemon/bits/path_dump.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
 * Copyright (C) 2003-2011
 * 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,

lemon/bits/solver_bits.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
 * Copyright (C) 2003-2011
 * 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,

lemon/bits/windows.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -93,17 +93,17 @@
 		    std::string getWinFormattedDate()
+		    {
 		      std::ostringstream os;
 		#ifdef WIN32
 		      SYSTEMTIME time;
 		      GetSystemTime(&time);
 		      char buf1[11], buf2[9], buf3[5];
-			  if (GetDateFormat(MY_LOCALE, 0, &time,
+		          if (GetDateFormat(MY_LOCALE, 0, &time,
 		                        ("ddd MMM dd"), buf1, 11) &&
 		          GetTimeFormat(MY_LOCALE, 0, &time,
 		                        ("HH':'mm':'ss"), buf2, 9) &&
 		          GetDateFormat(MY_LOCALE, 0, &time,
 		                        ("yyyy"), buf3, 5)) {
 		        os << buf1 << ' ' << buf2 << ' ' << buf3;
+		      }
 		      else os << "unknown";

lemon/cbc.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
 * Copyright (C) 2003-2011
 * 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,
@@ -115,15 +115,15 @@

    virtual void _clear();

    virtual void _messageLevel(MessageLevel level);
    void _applyMessageLevel();

    int _message_level;

    


  };

}

#endif

lemon/circulation.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -54,18 +54,18 @@
 		    ///
 		    /// The type of the map that stores the upper bounds (capacities)
 		    /// on the arcs.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef UM UpperMap;
 		    /// \brief The type of supply map.
 		    ///
 		    /// The type of the map that stores the signed supply values of the
 		    /// nodes.
 		    /// The type of the map that stores the signed supply values of the
 		    /// nodes.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef SM SupplyMap;
 		    /// \brief The type of the flow and supply values.
 		    typedef typename SupplyMap::Value Value;
 		    /// \brief The type of the map that stores the flow values.
 		    ///
@@ -129,27 +129,27 @@
 		     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		     \f$-sup(u)\f$ demand.
 		     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
 		     solution of the following problem.
 		     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
 		     \geq sup(u) \quad \forall u\in V, \f]
 		     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
 		     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		     zero or negative in order to have a feasible solution (since the sum
 		     of the expressions on the left-hand side of the inequalities is zero).
 		     It means that the total demand must be greater or equal to the total
 		     supply and all the supplies have to be carried out from the supply nodes,
 		     but there could be demands that are not satisfied.
 		     If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		     constraints have to be satisfied with equality, i.e. all demands
 		     have to be satisfied and all supplies have to be used.
 		     If you need the opposite inequalities in the supply/demand constraints
 		     (i.e. the total demand is less than the total supply and all the demands
 		     have to be satisfied while there could be supplies that are not used),
 		     then you could easily transform the problem to the above form by reversing
 		     the direction of the arcs and taking the negative of the supply values
 		     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
 		     This algorithm either calculates a feasible circulation, or provides
@@ -320,17 +320,17 @@
 		  public:
 		    /// Constructor.
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    /// \param lower The lower bounds for the flow values on the arcs.
-		    /// \param upper The upper bounds (capacities) for the flow values
 		    /// \param upper The upper bounds (capacities) for the flow values
 		    /// on the arcs.
 		    /// \param supply The signed supply values of the nodes.
 		    Circulation(const Digraph &graph, const LowerMap &lower,
 		                const UpperMap &upper, const SupplyMap &supply)
 		      : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
 		        _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
 		        _excess(NULL) {}

lemon/clp.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-2008
 * Copyright (C) 2003-2011
 * 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,

lemon/clp.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -132,17 +132,17 @@
 		    virtual VarStatus _getRowStatus(int i) const;
 		    virtual ProblemType _getPrimalType() const;
 		    virtual ProblemType _getDualType() const;
 		    virtual void _clear();
 		    virtual void _messageLevel(MessageLevel);
 		  public:
 		    ///Solves LP with primal simplex method.
 		    SolveExitStatus solvePrimal();
 		    ///Solves LP with dual simplex method.
 		    SolveExitStatus solveDual();

lemon/concepts/digraph.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -430,17 +430,17 @@
 		        ///\e
 		        NodeMap(const Digraph&) { }
 		        ///\e
 		        NodeMap(const Digraph&, T) { }
 		      private:
 		        ///Copy constructor
-		        NodeMap(const NodeMap& nm) :
 		        NodeMap(const NodeMap& nm) :
 		          ReferenceMap<Node, T, T&, const T&>(nm) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, CMap>();
 		          return *this;
+		        }
 		      };

lemon/concepts/graph_components.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -33,17 +33,17 @@
 		    /// \brief Concept class for \c Node, \c Arc and \c Edge types.
 		    ///
 		    /// This class describes the concept of \c Node, \c Arc and \c Edge
 		    /// subtypes of digraph and graph types.
 		    ///
 		    /// \note This class is a template class so that we can use it to
 		    /// create graph skeleton classes. The reason for this is that \c Node
-		    /// and \c Arc (or \c Edge) types should \e not derive from the same
 		    /// and \c Arc (or \c Edge) types should \e not derive from the same
 		    /// base class. For \c Node you should instantiate it with character
 		    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
 		#ifndef DOXYGEN
 		    template <char sel = '0'>
 		#endif
 		    class GraphItem {
 		    public:
 		      /// \brief Default constructor.
@@ -84,17 +84,17 @@
 		      /// \brief Inequality operator.
 		      ///
 		      /// Inequality operator.
 		      bool operator!=(const GraphItem&) const { return false; }
 		      /// \brief Ordering operator.
 		      ///
 		      /// This operator defines an ordering of the items.
-		      /// It makes possible to use graph item types as key types in
 		      /// It makes possible to use graph item types as key types in
 		      /// associative containers (e.g. \c std::map).
 		      ///
 		      /// \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<(const GraphItem&) const { return false; }
 		      template<typename _GraphItem>
@@ -117,17 +117,17 @@
 		        const _GraphItem &ib;
 		      };
 		    };
 		    /// \brief Base skeleton class for directed graphs.
 		    ///
 		    /// This class describes the base interface of directed graph types.
 		    /// All digraph %concepts have to conform to this class.
-		    /// It just provides types for nodes and arcs and functions
 		    /// It just provides types for nodes and arcs and functions
 		    /// to get the source and the target nodes of arcs.
 		    class BaseDigraphComponent {
 		    public:
 		      typedef BaseDigraphComponent Digraph;
 		      /// \brief Node class of the digraph.
 		      ///
@@ -421,17 +421,17 @@
+		        }
 		        const _Graph& graph;
 		      };
 		    };
 		    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
 		    ///
-		    /// This class describes the concept of \c NodeIt, \c ArcIt and
 		    /// This class describes the concept of \c NodeIt, \c ArcIt and
 		    /// \c EdgeIt subtypes of digraph and graph types.
 		    template <typename GR, typename Item>
 		    class GraphItemIt : public Item {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor.
 		      /// \warning The default constructor is not required to set
@@ -461,17 +461,17 @@
 		      /// Assignment operator for the iterator.
 		      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
 		      /// \brief Increment the iterator.
 		      ///
 		      /// This operator increments the iterator, i.e. assigns it to the
 		      /// next item.
 		      GraphItemIt& 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 GraphItemIt&) const { return true;}
 		      /// \brief Inequality operator
@@ -496,25 +496,25 @@
 		          Item bi = it1;
 		          bi = it2;
+		        }
 		        const GR& g;
 		      };
 		    };
-		    /// \brief Concept class for \c InArcIt, \c OutArcIt and
 		    /// \brief Concept class for \c InArcIt, \c OutArcIt and
 		    /// \c IncEdgeIt types.
 		    ///
-		    /// This class describes the concept of \c InArcIt, \c OutArcIt
 		    /// This class describes the concept of \c InArcIt, \c OutArcIt
 		    /// and \c IncEdgeIt subtypes of digraph and graph types.
 		    ///
 		    /// \note Since these iterator classes do not inherit from the same
 		    /// base class, there is an additional template parameter (selector)
-		    /// \c sel. For \c InArcIt you should instantiate it with character
 		    /// \c sel. For \c InArcIt you should instantiate it with character
 		    /// \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.
@@ -525,20 +525,20 @@
 		      /// as uninitialized.
 		      GraphIncIt() {}
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy constructor.
 		      GraphIncIt(const GraphIncIt& it) : Item(it) {}
-		      /// \brief Constructor that sets the iterator to the first
 		      /// \brief Constructor that sets the iterator to the first
 		      /// incoming or outgoing arc.
 		      ///
-		      /// Constructor that sets the iterator to the first 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.
@@ -799,26 +799,26 @@
 		      /// \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
 		      /// 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
 		      /// 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
 		      /// 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;
 		      /// @}
@@ -985,17 +985,17 @@
 		        const _Graph& graph;
 		      };
 		    };
 		    /// \brief Concept class for standard graph maps.
 		    ///
 		    /// This class describes the concept of standard graph maps, i.e.
-		    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
 		    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
 		    /// graph types, which can be used for associating data to graph items.
 		    /// The standard graph maps must conform to the ReferenceMap concept.
 		    template <typename GR, typename K, typename V>
 		    class GraphMap : public ReferenceMap<K, V, V&, const V&> {
 		      typedef ReferenceMap<K, V, V&, const V&> Parent;
 		    public:
@@ -1040,17 +1040,17 @@
 		    public:
 		      template<typename _Map>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept
 		            <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
 		          _Map m1(g);
 		          _Map m2(g,t);
 		          // Copy constructor
 		          // _Map m3(m);
 		          // Assignment operator
 		          // ReadMap<Key, Value> cmap;
 		          // m3 = cmap;
 		          ignore_unused_variable_warning(m1);
@@ -1063,17 +1063,17 @@
 		        const typename GraphMap::Value &t;
 		      };
 		    };
 		    /// \brief Skeleton class for mappable directed graphs.
 		    ///
 		    /// This class describes the interface of mappable directed graphs.
-		    /// It extends \ref BaseDigraphComponent with the standard digraph
 		    /// It extends \ref BaseDigraphComponent with the standard digraph
 		    /// map classes, namely \c NodeMap and \c ArcMap.
 		    /// This concept is part of the Digraph concept.
 		    template <typename BAS = BaseDigraphComponent>
 		    class MappableDigraphComponent : public BAS  {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
@@ -1200,17 +1200,17 @@
 		        const _Digraph& digraph;
 		      };
 		    };
 		    /// \brief Skeleton class for mappable undirected graphs.
 		    ///
 		    /// This class describes the interface of mappable undirected graphs.
-		    /// It extends \ref MappableDigraphComponent with the standard graph
 		    /// It extends \ref MappableDigraphComponent with the standard graph
 		    /// map class for edges (\c EdgeMap).
 		    /// This concept is part of the Graph concept.
 		    template <typename BAS = BaseGraphComponent>
 		    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Edge Edge;
@@ -1285,17 +1285,17 @@
 		        const _Graph& graph;
 		      };
 		    };
 		    /// \brief Skeleton class for extendable directed graphs.
 		    ///
 		    /// This class describes the interface of extendable directed graphs.
-		    /// It extends \ref BaseDigraphComponent with functions for adding
 		    /// It extends \ref BaseDigraphComponent with functions for adding
 		    /// nodes and arcs to the digraph.
 		    /// This concept requires \ref AlterableDigraphComponent.
 		    template <typename BAS = BaseDigraphComponent>
 		    class ExtendableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
@@ -1329,17 +1329,17 @@
 		        _Digraph& digraph;
 		      };
 		    };
 		    /// \brief Skeleton class for extendable undirected graphs.
 		    ///
 		    /// This class describes the interface of extendable undirected graphs.
-		    /// It extends \ref BaseGraphComponent with functions for adding
 		    /// It extends \ref BaseGraphComponent with functions for adding
 		    /// nodes and edges to the graph.
 		    /// This concept requires \ref AlterableGraphComponent.
 		    template <typename BAS = BaseGraphComponent>
 		    class ExtendableGraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
@@ -1373,30 +1373,30 @@
 		        _Graph& graph;
 		      };
 		    };
 		    /// \brief Skeleton class for erasable directed graphs.
 		    ///
 		    /// This class describes the interface of erasable directed graphs.
-		    /// It extends \ref BaseDigraphComponent with functions for removing
 		    /// It extends \ref BaseDigraphComponent with functions for removing
 		    /// nodes and arcs from the digraph.
 		    /// This concept requires \ref AlterableDigraphComponent.
 		    template <typename BAS = BaseDigraphComponent>
 		    class ErasableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// \brief Erase a node from the digraph.
 		      ///
-		      /// This function erases the given node from the digraph and all arcs
 		      /// This function erases the given node from the digraph and all arcs
 		      /// connected to the node.
 		      void erase(const Node&) {}
 		      /// \brief Erase an arc from the digraph.
 		      ///
 		      /// This function erases the given arc from the digraph.
 		      void erase(const Arc&) {}
@@ -1412,17 +1412,17 @@
 		        _Digraph& digraph;
 		      };
 		    };
 		    /// \brief Skeleton class for erasable undirected graphs.
 		    ///
 		    /// This class describes the interface of erasable undirected graphs.
-		    /// It extends \ref BaseGraphComponent with functions for removing
 		    /// It extends \ref BaseGraphComponent with functions for removing
 		    /// nodes and edges from the graph.
 		    /// This concept requires \ref AlterableGraphComponent.
 		    template <typename BAS = BaseGraphComponent>
 		    class ErasableGraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;

lemon/concepts/maps.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
 * Copyright (C) 2003-2011
 * 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,

lemon/connectivity.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -253,17 +253,17 @@
 		  /// \brief Check whether a directed graph is strongly connected.
 		  ///
 		  /// This function checks whether the given directed graph is strongly
 		  /// connected, i.e. any two nodes of the digraph are
 		  /// connected with directed paths in both direction.
 		  ///
 		  /// \return \c true if the digraph is strongly connected.
 		  /// \note By definition, the empty digraph is strongly connected.
-		  ///
 		  ///
 		  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
 		  /// \see connected()
 		  template <typename Digraph>
 		  bool stronglyConnected(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
@@ -305,17 +305,17 @@
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Count the number of strongly connected components of a
 		  /// \brief Count the number of strongly connected components of a
 		  /// directed graph
 		  ///
 		  /// This function counts the number of strongly connected components of
 		  /// the given directed graph.
 		  ///
 		  /// The strongly connected components are the classes of an
 		  /// equivalence relation on the nodes of a digraph. Two nodes are in
 		  /// the same class if they are connected with directed paths in both
@@ -739,31 +739,31 @@
 		  template <typename Graph>
 		  int countBiNodeConnectedComponents(const Graph& graph);
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Check whether an undirected graph is bi-node-connected.
 		  ///
-		  /// This function checks whether the given undirected graph is
 		  /// This function checks whether the given undirected graph is
 		  /// bi-node-connected, i.e. any two edges are on same circle.
 		  ///
 		  /// \return \c true if the graph bi-node-connected.
 		  /// \note By definition, the empty graph is bi-node-connected.
 		  ///
 		  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
 		  template <typename Graph>
 		  bool biNodeConnected(const Graph& graph) {
 		    return countBiNodeConnectedComponents(graph) <= 1;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Count the number of bi-node-connected components of an
 		  /// \brief Count the number of bi-node-connected components of an
 		  /// undirected graph.
 		  ///
 		  /// This function counts the number of bi-node-connected components of
 		  /// the given undirected graph.
 		  ///
 		  /// The bi-node-connected components are the classes of an equivalence
 		  /// relation on the edges of a undirected graph. Two edges are in the
 		  /// same class if they are on same circle.
@@ -807,17 +807,17 @@
 		  /// same class if they are on same circle.
 		  ///
 		  /// \image html node_biconnected_components.png
 		  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \retval compMap A writable edge map. The values will be set from 0
 		  /// to the number of the bi-node-connected components minus one. Each
-		  /// value of the map will be set exactly once, and the values of a
 		  /// value of the map will be set exactly once, and the values of a
 		  /// certain component will be set continuously.
 		  /// \return The number of bi-node-connected components.
 		  ///
 		  /// \see biNodeConnected(), countBiNodeConnectedComponents()
 		  template <typename Graph, typename EdgeMap>
 		  int biNodeConnectedComponents(const Graph& graph,
 		                                EdgeMap& compMap) {
 		    checkConcept<concepts::Graph, Graph>();
@@ -853,17 +853,17 @@
 		  ///
 		  /// The bi-node-connected components are the classes of an equivalence
 		  /// relation on the edges of a undirected graph. Two edges are in the
 		  /// same class if they are on same circle.
 		  /// The bi-node-connected components are separted by the cut nodes of
 		  /// the components.
 		  ///
 		  /// \param graph The undirected graph.
-		  /// \retval cutMap A writable node map. The values will be set to
 		  /// \retval cutMap A writable node map. The values will be set to
 		  /// \c true for the nodes that separate two or more components
 		  /// (exactly once for each cut node), and will not be changed for
 		  /// other nodes.
 		  /// \return The number of the cut nodes.
 		  ///
 		  /// \see biNodeConnected(), biNodeConnectedComponents()
 		  template <typename Graph, typename NodeMap>
 		  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
@@ -1080,17 +1080,17 @@
 		  template <typename Graph>
 		  int countBiEdgeConnectedComponents(const Graph& graph);
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Check whether an undirected graph is bi-edge-connected.
 		  ///
-		  /// This function checks whether the given undirected graph is
 		  /// This function checks whether the given undirected graph is
 		  /// bi-edge-connected, i.e. any two nodes are connected with at least
 		  /// two edge-disjoint paths.
 		  ///
 		  /// \return \c true if the graph is bi-edge-connected.
 		  /// \note By definition, the empty graph is bi-edge-connected.
 		  ///
 		  /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
 		  template <typename Graph>
@@ -1187,17 +1187,17 @@
 		    return compNum;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Find the bi-edge-connected cut edges in an undirected graph.
 		  ///
 		  /// This function finds the bi-edge-connected cut edges in the given
-		  /// undirected graph.
 		  /// undirected graph.
 		  ///
 		  /// The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes of an undirected graph. Two nodes are in the
 		  /// same class if they are connected with at least two edge-disjoint
 		  /// paths.
 		  /// The bi-edge-connected components are separted by the cut edges of
 		  /// the components.
 		  ///
@@ -1344,17 +1344,17 @@
 		  /// \brief Sort the nodes of a DAG into topolgical order.
 		  ///
 		  /// This function sorts the nodes of the given acyclic digraph (DAG)
 		  /// into topolgical order and also checks whether the given digraph
 		  /// is DAG.
 		  ///
 		  /// \param digraph The digraph.
 		  /// \retval order A readable and writable node map. The values will be
-		  /// set from 0 to the number of the nodes in the digraph minus one.
 		  /// set from 0 to the number of the nodes in the digraph minus one.
 		  /// Each value of the map will be set exactly once, and the values will
 		  /// be set descending order.
 		  /// \return \c false if the digraph is not DAG.
 		  ///
 		  /// \see dag(), topologicalSort()
 		  template <typename Digraph, typename NodeMap>
 		  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
 		    using namespace _connectivity_bits;

lemon/core.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -1236,17 +1236,18 @@
 		  public:
 		    /// The Digraph type
 		    typedef GR Digraph;
 		  protected:
-		    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
 		    class AutoNodeMap :
 		      public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
 		      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
 		    public:
 		      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
 		      virtual void add(const Node& node) {
 		        Parent::add(node);
@@ -1275,17 +1276,17 @@
 		    public:
 		      ArcLess(const Digraph &_g) : g(_g) {}
 		      bool operator()(Arc a,Arc b) const
+		      {
 		        return g.target(a)<g.target(b);
+		      }
 		    };
-		  protected:
 		  protected:
 		    const Digraph &_g;
 		    AutoNodeMap _head;
 		    typename Digraph::template ArcMap<Arc> _parent;
 		    typename Digraph::template ArcMap<Arc> _left;
 		    typename Digraph::template ArcMap<Arc> _right;
 		  public:

lemon/cplex.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
 * Copyright (C) 2003-2011
 * 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,
@@ -451,17 +451,17 @@
    case MESSAGE_NORMAL:
    case MESSAGE_VERBOSE:
      _message_enabled = true;
      break;
    }
  }

  void CplexBase::_applyMessageLevel() {
    CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, 
    CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
                   _message_enabled ? CPX_ON : CPX_OFF);
  }

  // CplexLp members

  CplexLp::CplexLp()
    : LpBase(), LpSolver(), CplexBase() {}


lemon/dfs.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
 * Copyright (C) 2003-2011
 * 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,

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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -56,17 +56,17 @@
 		    int lineShift;
 		    ///Constructor. It sets the type to \c NONE.
 		    DimacsDescriptor() : type(NONE) {}
 		  };
 		  ///Discover the type of a DIMACS file
 		  ///This function starts seeking the beginning of the given file for the
-		  ///problem type and size info.
 		  ///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;
@@ -207,17 +207,17 @@
 		      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;
@@ -232,17 +232,17 @@
+		        }
 		        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);
@@ -357,21 +357,21 @@
+		  }
 		  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);
+		  }
 		  /// \brief DIMACS plain (di)graph reader function.
 		  ///
 		  /// This function reads a plain (di)graph without any designated nodes
-		  /// and maps (e.g. a matching instance) from DIMACS format, i.e. from
 		  /// 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.
@@ -387,17 +387,17 @@
 		    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

lemon/edge_set.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
 * Copyright (C) 2003-2011
 * 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,

lemon/euler.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -21,32 +21,32 @@
 		#include<lemon/core.h>
 		#include<lemon/adaptors.h>
 		#include<lemon/connectivity.h>
 		#include <list>
 		/// \ingroup graph_properties
 		/// \file
-		/// \brief Euler tour iterators and a function for checking the \e Eulerian
 		/// \brief Euler tour iterators and a function for checking the \e Eulerian
 		/// property.
 		///
 		///This file provides Euler tour iterators and a function to check
 		///if a (di)graph is \e Eulerian.
 		namespace lemon {
 		  ///Euler tour iterator for digraphs.
 		  /// \ingroup graph_prop
 		  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
 		  ///graph (if there exists) and it converts to the \c Arc type of the digraph.
 		  ///
 		  ///For example, if the given digraph has an Euler tour (i.e it has only one
-		  ///non-trivial component and the in-degree is equal to the out-degree
 		  ///non-trivial component and the in-degree is equal to the out-degree
 		  ///for all nodes), then the following code will put the arcs of \c g
 		  ///to the vector \c et according to an Euler tour of \c g.
 		  ///\code
 		  ///  std::vector<ListDigraph::Arc> et;
 		  ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
 		  ///    et.push_back(e);
 		  ///\endcode
 		  ///If \c g has no Euler tour, then the resulted walk will not be closed
@@ -133,26 +133,26 @@
 		  ///Euler tour iterator for graphs.
 		  /// \ingroup graph_properties
 		  ///This iterator provides an Euler tour (Eulerian circuit) of an
 		  ///\e undirected graph (if there exists) and it converts to the \c Arc
 		  ///and \c Edge types of the graph.
 		  ///
-		  ///For example, if the given graph has an Euler tour (i.e it has only one
 		  ///For example, if the given graph has an Euler tour (i.e it has only one
 		  ///non-trivial component and the degree of each node is even),
 		  ///the following code will print the arc IDs according to an
 		  ///Euler tour of \c g.
 		  ///\code
 		  ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
 		  ///    std::cout << g.id(Edge(e)) << std::eol;
 		  ///  }
 		  ///\endcode
-		  ///Although this iterator is for undirected graphs, it still returns
 		  ///Although this iterator is for undirected graphs, it still returns
 		  ///arcs in order to indicate the direction of the tour.
 		  ///(But arcs convert to edges, of course.)
 		  ///
 		  ///If \c g has no Euler tour, then the resulted walk will not be closed
 		  ///or not contain all edges.
 		  template<typename GR>
 		  class EulerIt
+		  {
@@ -228,17 +228,17 @@
+		      }
 		      return *this;
+		    }
 		    ///Postfix incrementation
 		    /// Postfix incrementation.
 		    ///
-		    ///\warning This incrementation returns an \c Arc (which converts to
 		    ///\warning This incrementation returns an \c Arc (which converts to
 		    ///an \c Edge), not an \ref EulerIt, as one may expect.
 		    Arc operator++(int)
+		    {
 		      Arc e=*this;
 		      ++(*this);
 		      return e;
+		    }
 		  };

lemon/glpk.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -25,26 +25,26 @@
 		#include <lemon/lp_base.h>
 		namespace lemon {
 		  namespace _solver_bits {
 		    class VoidPtr {
 		    private:
-		      void *_ptr;
 		      void *_ptr;
 		    public:
 		      VoidPtr() : _ptr(0) {}
 		      template <typename T>
 		      VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}
 		      template <typename T>
 		      VoidPtr& operator=(T* ptr) {
 		        _ptr = reinterpret_cast<void*>(ptr);
 		      VoidPtr& operator=(T* ptr) {
 		        _ptr = reinterpret_cast<void*>(ptr);
 		        return *this;
+		      }
 		      template <typename T>
 		      operator T*() const { return reinterpret_cast<T*>(_ptr); }
 		    };
+		  }
@@ -118,23 +118,23 @@
 		    static void freeEnv();
 		    struct FreeEnvHelper {
 		      ~FreeEnvHelper() {
 		        freeEnv();
+		      }
 		    };
 		    static FreeEnvHelper freeEnvHelper;
 		  protected:
 		    int _message_level;
 		  public:
 		    ///Pointer to the underlying GLPK data structure.
 		    _solver_bits::VoidPtr lpx() {return lp;}
 		    ///Const pointer to the underlying GLPK data structure.
 		    _solver_bits::VoidPtr lpx() const {return lp;}
 		    ///Returns the constraint identifier understood by GLPK.

lemon/gomory_hu.h

Show inline comments

 		/* -*- C++ -*-
+		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -22,197 +22,197 @@
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/preflow.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		/// \ingroup min_cut
-		/// \file
 		/// \file
 		/// \brief Gomory-Hu cut tree in graphs.
 		namespace lemon {
 		  /// \ingroup min_cut
 		  ///
 		  /// \brief Gomory-Hu cut tree algorithm
 		  ///
 		  /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
 		  /// may contain edges which are not in the original graph. It has the
-		  /// property that the minimum capacity edge of the path between two nodes
 		  /// property that the minimum capacity edge of the path between two nodes
 		  /// in this tree has the same weight as the minimum cut in the graph
 		  /// between these nodes. Moreover the components obtained by removing
 		  /// this edge from the tree determine the corresponding minimum cut.
 		  /// Therefore once this tree is computed, the minimum cut between any pair
 		  /// of nodes can easily be obtained.
-		  ///
 		  ///
 		  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
 		  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
 		  /// time complexity. It calculates a rooted Gomory-Hu tree.
 		  /// The structure of the tree and the edge weights can be
 		  /// obtained using \c predNode(), \c predValue() and \c rootDist().
 		  /// The functions \c minCutMap() and \c minCutValue() calculate
 		  /// the minimum cut and the minimum cut value between any two nodes
 		  /// in the graph. You can also list (iterate on) the nodes and the
 		  /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
 		  ///
 		  /// \tparam GR The type of the undirected graph the algorithm runs on.
 		  /// \tparam CAP The type of the edge map containing the capacities.
 		  /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR,
-			    typename CAP>
+		            typename CAP>
 		#else
 		  template <typename GR,
-			    typename CAP = typename GR::template EdgeMap<int> >
+		            typename CAP = typename GR::template EdgeMap<int> >
 		#endif
 		  class GomoryHu {
 		  public:
 		    /// The graph type of the algorithm
 		    typedef GR Graph;
 		    /// The capacity map type of the algorithm
 		    typedef CAP Capacity;
 		    /// The value type of capacities
 		    typedef typename Capacity::Value Value;
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    const Graph& _graph;
 		    const Capacity& _capacity;
 		    Node _root;
 		    typename Graph::template NodeMap<Node>* _pred;
 		    typename Graph::template NodeMap<Value>* _weight;
 		    typename Graph::template NodeMap<int>* _order;
 		    void createStructures() {
 		      if (!_pred) {
-			_pred = new typename Graph::template NodeMap<Node>(_graph);
+		        _pred = new typename Graph::template NodeMap<Node>(_graph);
+		      }
 		      if (!_weight) {
-			_weight = new typename Graph::template NodeMap<Value>(_graph);
+		        _weight = new typename Graph::template NodeMap<Value>(_graph);
+		      }
 		      if (!_order) {
-			_order = new typename Graph::template NodeMap<int>(_graph);
+		        _order = new typename Graph::template NodeMap<int>(_graph);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_pred) {
-			delete _pred;
+		        delete _pred;
+		      }
 		      if (_weight) {
-			delete _weight;
+		        delete _weight;
+		      }
 		      if (_order) {
-			delete _order;
+		        delete _order;
+		      }
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor.
 		    /// \param graph The undirected graph the algorithm runs on.
 		    /// \param capacity The edge capacity map.
-		    GomoryHu(const Graph& graph, const Capacity& capacity)
 		    GomoryHu(const Graph& graph, const Capacity& capacity)
 		      : _graph(graph), _capacity(capacity),
-			_pred(0), _weight(0), _order(0)
+		        _pred(0), _weight(0), _order(0)
+		    {
 		      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
+		    }
 		    /// \brief Destructor
 		    ///
 		    /// Destructor.
 		    ~GomoryHu() {
 		      destroyStructures();
+		    }
 		  private:
 		    // Initialize the internal data structures
 		    void init() {
 		      createStructures();
 		      _root = NodeIt(_graph);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_pred)[n] = _root;
 		        (*_order)[n] = -1;
+		      }
 		      (*_pred)[_root] = INVALID;
-		      (*_weight)[_root] = std::numeric_limits<Value>::max();
 		      (*_weight)[_root] = std::numeric_limits<Value>::max();
+		    }
 		    // Start the algorithm
 		    void start() {
 		      Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
-			if (n == _root) continue;
+		        if (n == _root) continue;
 			Node pn = (*_pred)[n];
 			fa.source(n);
-			fa.target(pn);
+		        Node pn = (*_pred)[n];
 		        fa.source(n);
 		        fa.target(pn);
-			fa.runMinCut();
+		        fa.runMinCut();
-			(*_weight)[n] = fa.flowValue();
+		        (*_weight)[n] = fa.flowValue();
 			for (NodeIt nn(_graph); nn != INVALID; ++nn) {
 			  if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
 			    (*_pred)[nn] = n;
+			  }
+			}
 			if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
 			  (*_pred)[n] = (*_pred)[pn];
 			  (*_pred)[pn] = n;
 			  (*_weight)[n] = (*_weight)[pn];
 			  (*_weight)[pn] = fa.flowValue();
+			}
+		        for (NodeIt nn(_graph); nn != INVALID; ++nn) {
 		          if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
 		            (*_pred)[nn] = n;
+		          }
+		        }
 		        if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
 		          (*_pred)[n] = (*_pred)[pn];
 		          (*_pred)[pn] = n;
 		          (*_weight)[n] = (*_weight)[pn];
 		          (*_weight)[pn] = fa.flowValue();
+		        }
+		      }
 		      (*_order)[_root] = 0;
 		      int index = 1;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 			std::vector<Node> st;
 			Node nn = n;
 			while ((*_order)[nn] == -1) {
 			  st.push_back(nn);
 			  nn = (*_pred)[nn];
+			}
 			while (!st.empty()) {
 			  (*_order)[st.back()] = index++;
 			  st.pop_back();
+			}
 		        std::vector<Node> st;
 		        Node nn = n;
 		        while ((*_order)[nn] == -1) {
 		          st.push_back(nn);
 		          nn = (*_pred)[nn];
+		        }
 		        while (!st.empty()) {
 		          (*_order)[st.back()] = index++;
 		          st.pop_back();
+		        }
+		      }
+		    }
 		  public:
 		    ///\name Execution Control
 		    ///@{
 		    /// \brief Run the Gomory-Hu algorithm.
 		    ///
 		    /// This function runs the Gomory-Hu algorithm.
 		    void run() {
 		      init();
 		      start();
+		    }
 		    /// @}
 		    ///\name Query Functions
 		    ///The results of the algorithm can be obtained using these
 		    ///functions.\n
 		    ///\ref run() should be called before using them.\n
 		    ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
@@ -227,17 +227,17 @@
 		    /// \pre \ref run() must be called before using this function.
 		    Node predNode(const Node& node) const {
 		      return (*_pred)[node];
+		    }
 		    /// \brief Return the weight of the predecessor edge in the
 		    /// Gomory-Hu tree.
 		    ///
-		    /// This function returns the weight of the predecessor edge of the
 		    /// This function returns the weight of the predecessor edge of the
 		    /// given node in the Gomory-Hu tree.
 		    /// If \c node is the root of the tree, the result is undefined.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Value predValue(const Node& node) const {
 		      return (*_weight)[node];
+		    }
@@ -249,34 +249,34 @@
 		    /// \pre \ref run() must be called before using this function.
 		    int rootDist(const Node& node) const {
 		      return (*_order)[node];
+		    }
 		    /// \brief Return the minimum cut value between two nodes
 		    ///
 		    /// This function returns the minimum cut value between the nodes
-		    /// \c s and \c t.
 		    /// \c s and \c t.
 		    /// It finds the nearest common ancestor of the given nodes in the
 		    /// Gomory-Hu tree and calculates the minimum weight edge on the
 		    /// paths to the ancestor.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Value minCutValue(const Node& s, const Node& t) const {
 		      Node sn = s, tn = t;
 		      Value value = std::numeric_limits<Value>::max();
 		      while (sn != tn) {
 			if ((*_order)[sn] < (*_order)[tn]) {
 			  if ((*_weight)[tn] <= value) value = (*_weight)[tn];
 			  tn = (*_pred)[tn];
 			} else {
 			  if ((*_weight)[sn] <= value) value = (*_weight)[sn];
 			  sn = (*_pred)[sn];
+			}
+		        if ((*_order)[sn] < (*_order)[tn]) {
 		          if ((*_weight)[tn] <= value) value = (*_weight)[tn];
 		          tn = (*_pred)[tn];
 		        } else {
 		          if ((*_weight)[sn] <= value) value = (*_weight)[sn];
 		          sn = (*_pred)[sn];
+		        }
+		      }
 		      return value;
+		    }
 		    /// \brief Return the minimum cut between two nodes
 		    ///
 		    /// This function returns the minimum cut between the nodes \c s and \c t
 		    /// in the \c cutMap parameter by setting the nodes in the component of
@@ -289,74 +289,74 @@
 		    /// \param cutMap The cut will be returned in this map.
 		    /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap
 		    /// "ReadWriteMap" on the graph nodes.
 		    ///
 		    /// \return The value of the minimum cut between \c s and \c t.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename CutMap>
-		    Value minCutMap(const Node& s, ///<
 		    Value minCutMap(const Node& s, ///<
 		                    const Node& t,
-		                    ///<
 		                    ///<
 		                    CutMap& cutMap
-		                    ///<
 		                    ///<
 		                    ) const {
 		      Node sn = s, tn = t;
 		      bool s_root=false;
 		      Node rn = INVALID;
 		      Value value = std::numeric_limits<Value>::max();
 		      while (sn != tn) {
 			if ((*_order)[sn] < (*_order)[tn]) {
 			  if ((*_weight)[tn] <= value) {
-			    rn = tn;
+		        if ((*_order)[sn] < (*_order)[tn]) {
 		          if ((*_weight)[tn] <= value) {
 		            rn = tn;
 		            s_root = false;
 			    value = (*_weight)[tn];
+			  }
 			  tn = (*_pred)[tn];
 			} else {
 			  if ((*_weight)[sn] <= value) {
 			    rn = sn;
 		            value = (*_weight)[tn];
+		          }
 		          tn = (*_pred)[tn];
 		        } else {
 		          if ((*_weight)[sn] <= value) {
 		            rn = sn;
 		            s_root = true;
 			    value = (*_weight)[sn];
+			  }
 			  sn = (*_pred)[sn];
+			}
 		            value = (*_weight)[sn];
+		          }
 		          sn = (*_pred)[sn];
+		        }
+		      }
 		      typename Graph::template NodeMap<bool> reached(_graph, false);
 		      reached[_root] = true;
 		      cutMap.set(_root, !s_root);
 		      reached[rn] = true;
 		      cutMap.set(rn, s_root);
 		      std::vector<Node> st;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
-			st.clear();
+		        st.clear();
 		        Node nn = n;
 			while (!reached[nn]) {
 			  st.push_back(nn);
 			  nn = (*_pred)[nn];
+			}
 			while (!st.empty()) {
 			  cutMap.set(st.back(), cutMap[nn]);
 			  st.pop_back();
+			}
 		        while (!reached[nn]) {
 		          st.push_back(nn);
 		          nn = (*_pred)[nn];
+		        }
 		        while (!st.empty()) {
 		          cutMap.set(st.back(), cutMap[nn]);
 		          st.pop_back();
+		        }
+		      }
 		      return value;
+		    }
 		    ///@}
 		    friend class MinCutNodeIt;
 		    /// Iterate on the nodes of a minimum cut
 		    /// This iterator class lists the nodes of a minimum cut found by
 		    /// GomoryHu. Before using it, you must allocate a GomoryHu class
 		    /// and call its \ref GomoryHu::run() "run()" method.
 		    ///
 		    /// This example counts the nodes in the minimum cut separating \c s from
 		    /// \c t.
 		    /// \code
 		    /// GomoruHu<Graph> gom(g, capacities);
@@ -439,21 +439,21 @@
 		      /// expect.
 		      typename Graph::Node operator++(int)
+		      {
 		        typename Graph::Node n=*this;
 		        ++(*this);
 		        return n;
+		      }
 		    };
 		    friend class MinCutEdgeIt;
 		    /// Iterate on the edges of a minimum cut
 		    /// This iterator class lists the edges of a minimum cut found by
 		    /// GomoryHu. Before using it, you must allocate a GomoryHu class
 		    /// and call its \ref GomoryHu::run() "run()" method.
 		    ///
 		    /// This example computes the value of the minimum cut separating \c s from
 		    /// \c t.
 		    /// \code
 		    /// GomoruHu<Graph> gom(g, capacities);
@@ -476,17 +476,17 @@
 		        ++_arc_it;
 		        while(_node_it!=INVALID && _arc_it==INVALID)
+		          {
 		            for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
 		            if(_node_it!=INVALID)
 		              _arc_it=typename Graph::OutArcIt(_graph,_node_it);
+		          }
+		      }
 		    public:
 		      /// Constructor
 		      /// Constructor.
 		      ///
 		      MinCutEdgeIt(GomoryHu const &gomory,
 		                   ///< The GomoryHu class. You must call its
 		                   ///  run() method
@@ -545,17 +545,17 @@
 		      ///
 		      MinCutEdgeIt &operator++()
+		      {
 		        step();
 		        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
 		        return *this;
+		      }
 		      /// Postfix incrementation
 		      /// Postfix incrementation.
 		      ///
 		      /// \warning This incrementation
 		      /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
 		      typename Graph::Arc operator++(int)
+		      {
 		        typename Graph::Arc e=*this;
 		        ++(*this);

lemon/graph_to_eps.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
 * Copyright (C) 2003-2011
 * 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,

lemon/hao_orlin.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -26,44 +26,44 @@
 		#include <lemon/maps.h>
 		#include <lemon/core.h>
 		#include <lemon/tolerance.h>
 		/// \file
 		/// \ingroup min_cut
 		/// \brief Implementation of the Hao-Orlin algorithm.
 		///
-		/// Implementation of the Hao-Orlin algorithm for finding a minimum cut
 		/// Implementation of the Hao-Orlin algorithm for finding a minimum cut
 		/// in a digraph.
 		namespace lemon {
 		  /// \ingroup min_cut
 		  ///
 		  /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.
 		  ///
 		  /// This class implements the Hao-Orlin algorithm for finding a minimum
-		  /// value cut in a directed graph \f$D=(V,A)\f$.
 		  /// value cut in a directed graph \f$D=(V,A)\f$.
 		  /// It takes a fixed node \f$ source \in V \f$ and
 		  /// consists of two phases: in the first phase it determines a
 		  /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
 		  /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing
 		  /// capacity) and in the second phase it determines a minimum cut
 		  /// with \f$ source \f$ on the sink-side (i.e. a set
 		  /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing
 		  /// capacity). Obviously, the smaller of these two cuts will be a
 		  /// minimum cut of \f$ D \f$. The algorithm is a modified
 		  /// preflow push-relabel algorithm. Our implementation calculates
 		  /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
 		  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
 		  /// purpose of such algorithm is e.g. testing network reliability.
 		  ///
 		  /// For an undirected graph you can run just the first phase of the
 		  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
-		  /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$
 		  /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$
 		  /// time. It is implemented in the NagamochiIbaraki algorithm class.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam CAP The type of the arc map containing the capacities,
 		  /// which can be any numreric type. The default map type is
 		  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TOL Tolerance class for handling inexact computations. The
 		  /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".
@@ -71,17 +71,17 @@
 		  template <typename GR, typename CAP, typename TOL>
 		#else
 		  template <typename GR,
 		            typename CAP = typename GR::template ArcMap<int>,
 		            typename TOL = Tolerance<typename CAP::Value> >
 		#endif
 		  class HaoOrlin {
 		  public:
 		    /// The digraph type of the algorithm
 		    typedef GR Digraph;
 		    /// The capacity map type of the algorithm
 		    typedef CAP CapacityMap;
 		    /// The tolerance type of the algorithm
 		    typedef TOL Tolerance;
 		  private:
@@ -842,17 +842,17 @@
 		    /// algorithm.
 		    void init() {
 		      init(NodeIt(_graph));
+		    }
 		    /// \brief Initialize the internal data structures.
 		    ///
 		    /// This function initializes the internal data structures. It creates
-		    /// the maps and some bucket structures for the algorithm.
 		    /// the maps and some bucket structures for the algorithm.
 		    /// The given node is used as the source node for the push-relabel
 		    /// algorithm.
 		    void init(const Node& source) {
 		      _source = source;
 		      _node_num = countNodes(_graph);
 		      _first.resize(_node_num);
@@ -922,40 +922,40 @@
 		    void run() {
 		      init();
 		      calculateOut();
 		      calculateIn();
+		    }
 		    /// \brief Run the algorithm.
 		    ///
-		    /// This function runs the algorithm. It uses the given \c source node,
 		    /// This function runs the algorithm. It uses the given \c source node,
 		    /// finds a proper \c target node and then calls the \ref init(),
 		    /// \ref calculateOut() and \ref calculateIn().
 		    void run(const Node& s) {
 		      init(s);
 		      calculateOut();
 		      calculateIn();
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The result of the %HaoOrlin algorithm
 		    /// can be obtained using these functions.\n
-		    /// \ref run(), \ref calculateOut() or \ref calculateIn()
 		    /// \ref run(), \ref calculateOut() or \ref calculateIn()
 		    /// should be called before using them.
 		    /// @{
 		    /// \brief Return the value of the minimum cut.
 		    ///
 		    /// This function returns the value of the minimum cut.
 		    ///
-		    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
 		    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
 		    /// must be called before using this function.
 		    Value minCutValue() const {
 		      return _min_cut;
+		    }
 		    /// \brief Return a minimum cut.
 		    ///
@@ -964,17 +964,17 @@
 		    /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
 		    /// for the nodes of \f$ X \f$).
 		    ///
 		    /// \param cutMap A \ref concepts::WriteMap "writable" node map with
 		    /// \c bool (or convertible) value type.
 		    ///
 		    /// \return The value of the minimum cut.
 		    ///
-		    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
 		    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
 		    /// must be called before using this function.
 		    template <typename CutMap>
 		    Value minCutMap(CutMap& cutMap) const {
 		      for (NodeIt it(_graph); it != INVALID; ++it) {
 		        cutMap.set(it, (*_min_cut_map)[it]);
+		      }
 		      return _min_cut;
+		    }

lemon/lgf_reader.h

Show inline comments

@@ -557,17 +557,17 @@
+		    }
 		  private:
 		    template <typename TDGR>
 		    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is);
 		    template <typename TDGR>
-		    friend DigraphReader<TDGR> digraphReader(TDGR& digraph,
 		    friend DigraphReader<TDGR> digraphReader(TDGR& digraph,
 		                                             const std::string& fn);
 		    template <typename TDGR>
 		    friend DigraphReader<TDGR> digraphReader(TDGR& 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) {
@@ -1189,24 +1189,24 @@
 		        throw FormatError("Section @attributes not found");
+		      }
+		    }
 		    /// @}
 		  };
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief Return a \ref DigraphReader class
 		  ///
 		  /// This function just returns a \ref DigraphReader class.
 		  ///
-		  /// With this function a digraph can be read from an
 		  /// With this function a digraph can be read from an
 		  /// \ref lgf-format "LGF" file or input stream with several maps and
 		  /// attributes. For example, there is network flow problem on a
 		  /// digraph, i.e. a digraph with a \e capacity map on the arcs and
 		  /// \e source and \e target nodes. This digraph can be read with the
 		  /// following code:
 		  ///
 		  ///\code
 		  ///ListDigraph digraph;
@@ -1251,17 +1251,17 @@
 		  template <typename TDGR>
 		  DigraphReader<TDGR> digraphReader(TDGR& digraph, const char* fn) {
 		    DigraphReader<TDGR> tmp(digraph, fn);
 		    return tmp;
+		  }
 		  template <typename GR>
 		  class GraphReader;
 		  template <typename TGR>
 		  GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin);
 		  template <typename TGR>
 		  GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
 		  template <typename TGR>
 		  GraphReader<TGR> graphReader(TGR& graph, const char *fn);
 		  /// \ingroup lemon_io
@@ -1388,17 +1388,17 @@
+		      }
+		    }
 		  private:
 		    template <typename TGR>
 		    friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is);
 		    template <typename TGR>
-		    friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
 		    friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
 		    template <typename TGR>
 		    friend GraphReader<TGR> graphReader(TGR& 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) {
@@ -2072,19 +2072,19 @@
 		    /// @}
 		  };
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief Return a \ref GraphReader class
 		  ///
-		  /// This function just returns a \ref GraphReader class.
 		  /// This function just returns a \ref GraphReader class.
 		  ///
-		  /// With this function a graph can be read from an
 		  /// With this function a graph can be read from an
 		  /// \ref lgf-format "LGF" file or input stream with several maps and
 		  /// attributes. For example, there is weighted matching problem on a
 		  /// graph, i.e. a graph with a \e weight map on the edges. This
 		  /// graph can be read with the following code:
 		  ///
 		  ///\code
 		  ///ListGraph graph;
 		  ///ListGraph::EdgeMap<int> weight(graph);

lemon/lgf_writer.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -346,17 +346,17 @@
 		    };
+		  }
 		  template <typename DGR>
 		  class DigraphWriter;
 		  template <typename TDGR>
-		  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
 		  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
 		                                   std::ostream& os = std::cout);
 		  template <typename TDGR>
 		  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const std::string& fn);
 		  template <typename TDGR>
 		  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const char* fn);
@@ -499,17 +499,17 @@
 		      if (local_os) {
 		        delete _os;
+		      }
+		    }
 		  private:
 		    template <typename TDGR>
-		    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
 		    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
 		                                             std::ostream& os);
 		    template <typename TDGR>
 		    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
 		                                             const std::string& fn);
 		    template <typename TDGR>
 		    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
 		                                             const char *fn);
@@ -912,17 +912,17 @@
 		    /// @}
 		  };
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief Return a \ref DigraphWriter class
 		  ///
-		  /// This function just returns a \ref DigraphWriter class.
 		  /// This function just returns a \ref DigraphWriter class.
 		  ///
 		  /// With this function a digraph can be write to a file or output
 		  /// stream in \ref lgf-format "LGF" format with several maps and
 		  /// attributes. For example, with the following code a network flow
 		  /// problem can be written to the standard output, i.e. a digraph
 		  /// with a \e capacity map on the arcs and \e source and \e target
 		  /// nodes:
 		  ///
@@ -952,17 +952,17 @@
+		  }
 		  /// \brief Return a \ref DigraphWriter class
 		  ///
 		  /// This function just returns a \ref DigraphWriter class.
 		  /// \relates DigraphWriter
 		  /// \sa digraphWriter(const TDGR& digraph, std::ostream& os)
 		  template <typename TDGR>
-		  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
 		  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
 		                                    const std::string& fn) {
 		    DigraphWriter<TDGR> tmp(digraph, fn);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref DigraphWriter class
 		  ///
 		  /// This function just returns a \ref DigraphWriter class.
@@ -1096,21 +1096,21 @@
+		      }
+		    }
 		  private:
 		    template <typename TGR>
 		    friend GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os);
 		    template <typename TGR>
-		    friend GraphWriter<TGR> graphWriter(const TGR& graph,
 		    friend GraphWriter<TGR> graphWriter(const TGR& graph,
 		                                        const std::string& fn);
 		    template <typename TGR>
 		    friend GraphWriter<TGR> graphWriter(const TGR& 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);
@@ -1551,17 +1551,17 @@
 		    /// @}
 		  };
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief Return a \ref GraphWriter class
 		  ///
-		  /// This function just returns a \ref GraphWriter class.
 		  /// This function just returns a \ref GraphWriter class.
 		  ///
 		  /// With this function a graph can be write to a file or output
 		  /// stream in \ref lgf-format "LGF" format with several maps and
 		  /// attributes. For example, with the following code a weighted
 		  /// matching problem can be written to the standard output, i.e. a
 		  /// graph with a \e weight map on the edges:
 		  ///
 		  ///\code

lemon/lp.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -79,15 +79,15 @@
 		  typedef CplexLp Lp;
 		# define LEMON_DEFAULT_MIP CPLEX
 		  typedef CplexMip Mip;
 		#elif LEMON_HAVE_SOPLEX
 		# define DEFAULT_LP SOPLEX
 		  typedef SoplexLp Lp;
 		#elif LEMON_HAVE_CLP
 		# define DEFAULT_LP CLP
-		  typedef ClpLp Lp;
 		  typedef ClpLp Lp;
 		#endif
 		#endif
 		} //namespace lemon
 		#endif //LEMON_LP_H

lemon/lp_base.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-2008
 * Copyright (C) 2003-2011
 * 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,

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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -77,17 +77,17 @@
 		      MESSAGE_ERROR,
 		      /// Warnings.
 		      MESSAGE_WARNING,
 		      /// Normal output.
 		      MESSAGE_NORMAL,
 		      /// 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;
@@ -109,24 +109,24 @@
 		      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.
 		      /// \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
@@ -151,35 +151,35 @@
 		    ///\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.
 		      ///
 		      ColIt &operator++()
+		      {
 		        _solver->cols.nextItem(_id);
 		        return *this;
+		      }
 		    };
@@ -204,32 +204,32 @@
 		      friend class LpBase;
 		    protected:
 		      int _id;
 		      explicit Row(int id) : _id(id) {}
 		    public:
 		      typedef Value ExprValue;
 		      typedef True LpRow;
 		      /// Default constructor
 		      /// \warning The default constructor sets the Row to an
 		      /// undefined value.
 		      Row() {}
 		      /// Invalid constructor \& conversion.
 		      /// This constructor initializes the Row to be invalid.
-		      /// \sa Invalid for more details.
 		      /// \sa Invalid for more details.
 		      Row(const Invalid&) : _id(-1) {}
 		      /// Equality operator
 		      /// Two \ref Row "Row"s are equal if and only if they point to
 		      /// the same LP row or both are invalid.
 		      bool operator==(Row r) const  {return _id == r._id;}
 		      /// Inequality operator
 		      /// \sa operator==(Row r)
 		      ///
 		      bool operator!=(Row r) const  {return _id != r._id;}
 		      /// Artificial ordering operator.
 		      /// To allow the use of this object in std::map or similar
 		      /// associative container we require this.
 		      ///
@@ -246,35 +246,35 @@
 		    ///\code
 		    /// int count=0;
 		    /// for (LpBase::RowIt c(lp); c!=INVALID; ++c) ++count;
 		    ///\endcode
 		    class RowIt : public Row {
 		      const LpBase *_solver;
 		    public:
 		      /// Default constructor
 		      /// \warning The default constructor sets the iterator
 		      /// to an undefined value.
 		      RowIt() {}
 		      /// Sets the iterator to the first Row
 		      /// Sets the iterator to the first Row.
 		      ///
 		      RowIt(const LpBase &solver) : _solver(&solver)
+		      {
 		        _solver->rows.firstItem(_id);
+		      }
 		      /// Invalid constructor \& conversion
 		      /// Initialize the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      RowIt(const Invalid&) : Row(INVALID) {}
 		      /// Next row
 		      /// Assign the iterator to the next row.
 		      ///
 		      RowIt &operator++()
+		      {
 		        _solver->rows.nextItem(_id);
 		        return *this;
+		      }
 		    };
@@ -342,17 +342,17 @@
 		    protected:
 		      Value const_comp;
 		      std::map<int, Value> comps;
 		    public:
 		      typedef True SolverExpr;
 		      /// Default constructor
 		      /// Construct an empty expression, the coefficients and
 		      /// the constant component are initialized to zero.
 		      Expr() : const_comp(0) {}
 		      /// Construct an expression from a column
 		      /// Construct an expression, which has a term with \c c variable
 		      /// and 1.0 coefficient.
 		      Expr(const Col &c) : const_comp(0) {
@@ -443,93 +443,93 @@
 		        for (std::map<int, Value>::iterator it=comps.begin();
 		             it!=comps.end(); ++it)
 		          it->second/=c;
 		        const_comp/=c;
 		        return *this;
+		      }
 		      ///Iterator over the expression
 		      ///The iterator iterates over the terms of the expression.
-		      ///
 		      ///The iterator iterates over the terms of the expression.
 		      ///
 		      ///\code
 		      ///double s=0;
 		      ///for(LpBase::Expr::CoeffIt i(e);i!=INVALID;++i)
 		      ///  s+= *i * primal(i);
 		      ///\endcode
 		      class CoeffIt {
 		      private:
 		        std::map<int, Value>::iterator _it, _end;
 		      public:
 		        /// Sets the iterator to the first term
 		        /// Sets the iterator to the first term of the expression.
 		        ///
 		        CoeffIt(Expr& e)
 		          : _it(e.comps.begin()), _end(e.comps.end()){}
 		        /// Convert the iterator to the column of the term
 		        operator Col() const {
 		          return colFromId(_it->first);
+		        }
 		        /// Returns the coefficient of the term
 		        Value& operator*() { return _it->second; }
 		        /// Returns the coefficient of the term
 		        const Value& operator*() const { return _it->second; }
 		        /// Next term
 		        /// Assign the iterator to the next term.
 		        ///
 		        CoeffIt& operator++() { ++_it; return *this; }
 		        /// Equality operator
 		        bool operator==(Invalid) const { return _it == _end; }
 		        /// Inequality operator
 		        bool operator!=(Invalid) const { return _it != _end; }
 		      };
 		      /// Const iterator over the expression
 		      ///The iterator iterates over the terms of the expression.
-		      ///
 		      ///The iterator iterates over the terms of the expression.
 		      ///
 		      ///\code
 		      ///double s=0;
 		      ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i)
 		      ///  s+=*i * primal(i);
 		      ///\endcode
 		      class ConstCoeffIt {
 		      private:
 		        std::map<int, Value>::const_iterator _it, _end;
 		      public:
 		        /// Sets the iterator to the first term
 		        /// Sets the iterator to the first term of the expression.
 		        ///
 		        ConstCoeffIt(const Expr& e)
 		          : _it(e.comps.begin()), _end(e.comps.end()){}
 		        /// Convert the iterator to the column of the term
 		        operator Col() const {
 		          return colFromId(_it->first);
+		        }
 		        /// Returns the coefficient of the term
 		        const Value& operator*() const { return _it->second; }
 		        /// Next term
 		        /// Assign the iterator to the next term.
 		        ///
 		        ConstCoeffIt& operator++() { ++_it; return *this; }
 		        /// Equality operator
 		        bool operator==(Invalid) const { return _it == _end; }
 		        /// Inequality operator
 		        bool operator!=(Invalid) const { return _it != _end; }
@@ -668,17 +668,17 @@
 		      typedef LpBase::Value Value;
 		    protected:
 		      std::map<int, Value> comps;
 		    public:
 		      typedef True SolverExpr;
 		      /// Default constructor
 		      /// Construct an empty expression, the coefficients are
 		      /// initialized to zero.
 		      DualExpr() {}
 		      /// Construct an expression from a row
 		      /// Construct an expression, which has a term with \c r dual
 		      /// variable and 1.0 coefficient.
 		      DualExpr(const Row &r) {
@@ -703,17 +703,17 @@
 		        if (v != 0.0) {
 		          typedef std::map<int, Value>::value_type pair_type;
 		          comps.insert(pair_type(id(r), v));
 		        } else {
 		          comps.erase(id(r));
+		        }
+		      }
 		      /// \brief Removes the coefficients which's absolute value does
-		      /// not exceed \c epsilon.
 		      /// not exceed \c epsilon.
 		      void simplify(Value epsilon = 0.0) {
 		        std::map<int, Value>::iterator it=comps.begin();
 		        while (it != comps.end()) {
 		          std::map<int, Value>::iterator jt=it;
 		          ++jt;
 		          if (std::fabs((*it).second) <= epsilon) comps.erase(it);
 		          it=jt;
+		        }
@@ -752,33 +752,33 @@
 		      DualExpr &operator/=(const Value &v) {
 		        for (std::map<int, Value>::iterator it=comps.begin();
 		             it!=comps.end(); ++it)
 		          it->second/=v;
 		        return *this;
+		      }
 		      ///Iterator over the expression
 		      ///The iterator iterates over the terms of the expression.
-		      ///
 		      ///The iterator iterates over the terms of the expression.
 		      ///
 		      ///\code
 		      ///double s=0;
 		      ///for(LpBase::DualExpr::CoeffIt i(e);i!=INVALID;++i)
 		      ///  s+= *i * dual(i);
 		      ///\endcode
 		      class CoeffIt {
 		      private:
 		        std::map<int, Value>::iterator _it, _end;
 		      public:
 		        /// Sets the iterator to the first term
 		        /// Sets the iterator to the first term of the expression.
 		        ///
 		        CoeffIt(DualExpr& e)
 		          : _it(e.comps.begin()), _end(e.comps.end()){}
 		        /// Convert the iterator to the row of the term
 		        operator Row() const {
 		          return rowFromId(_it->first);
@@ -786,60 +786,60 @@
 		        /// Returns the coefficient of the term
 		        Value& operator*() { return _it->second; }
 		        /// Returns the coefficient of the term
 		        const Value& operator*() const { return _it->second; }
 		        /// Next term
 		        /// Assign the iterator to the next term.
 		        ///
 		        CoeffIt& operator++() { ++_it; return *this; }
 		        /// Equality operator
 		        bool operator==(Invalid) const { return _it == _end; }
 		        /// Inequality operator
 		        bool operator!=(Invalid) const { return _it != _end; }
 		      };
 		      ///Iterator over the expression
 		      ///The iterator iterates over the terms of the expression.
-		      ///
 		      ///The iterator iterates over the terms of the expression.
 		      ///
 		      ///\code
 		      ///double s=0;
 		      ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i)
 		      ///  s+= *i * dual(i);
 		      ///\endcode
 		      class ConstCoeffIt {
 		      private:
 		        std::map<int, Value>::const_iterator _it, _end;
 		      public:
 		        /// Sets the iterator to the first term
 		        /// Sets the iterator to the first term of the expression.
 		        ///
 		        ConstCoeffIt(const DualExpr& e)
 		          : _it(e.comps.begin()), _end(e.comps.end()){}
 		        /// Convert the iterator to the row of the term
 		        operator Row() const {
 		          return rowFromId(_it->first);
+		        }
 		        /// Returns the coefficient of the term
 		        const Value& operator*() const { return _it->second; }
 		        /// Next term
 		        /// Assign the iterator to the next term.
 		        ///
 		        ConstCoeffIt& operator++() { ++_it; return *this; }
 		        /// Equality operator
 		        bool operator==(Invalid) const { return _it == _end; }
 		        /// Inequality operator
 		        bool operator!=(Invalid) const { return _it != _end; }
@@ -1798,20 +1798,20 @@
 		      OPTIMAL = 3,
 		      /// = 4. The cost function is unbounded.
 		      UNBOUNDED = 4
 		    };
 		    ///The basis status of variables
 		    enum VarStatus {
 		      /// The variable is in the basis
-		      BASIC,
 		      BASIC,
 		      /// The variable is free, but not basic
 		      FREE,
-		      /// The variable has active lower bound
 		      /// The variable has active lower bound
 		      LOWER,
 		      /// The variable has active upper bound
 		      UPPER,
 		      /// The variable is non-basic and fixed
 		      FIXED
 		    };
 		  protected:
@@ -1880,17 +1880,17 @@
 		    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.
 		    ///
@@ -1914,17 +1914,17 @@
 		      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.
 		    ///
@@ -2056,17 +2056,17 @@
 		    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;}
 		    ///@}

lemon/lp_skeleton.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-2008
 * Copyright (C) 2003-2011
 * 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,

lemon/lp_skeleton.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -18,23 +18,23 @@
 		#ifndef LEMON_LP_SKELETON_H
 		#define LEMON_LP_SKELETON_H
 		#include <lemon/lp_base.h>
 		///\file
 		///\brief Skeleton file to implement LP/MIP solver interfaces
-		///
 		///
 		///The classes in this file do nothing, but they can serve as skeletons when
 		///implementing an interface to new solvers.
 		namespace lemon {
 		  ///A skeleton class to implement LP/MIP solver base interface
 		  ///This class does nothing, but it can serve as a skeleton when
 		  ///implementing an interface to new solvers.
 		  class SkeletonSolverBase : public virtual LpBase {
 		    int col_num,row_num;
 		  protected:
 		    SkeletonSolverBase()

lemon/maps.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -1813,17 +1813,17 @@
 		  /// @}
 		  /// \addtogroup graph_maps
 		  /// @{
 		  /// \brief Provides an immutable and unique id for each item in a graph.
 		  ///
 		  /// IdMap provides a unique and immutable id for each item of the
-		  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
 		  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
 		  ///  - \b unique: different items get different ids,
 		  ///  - \b immutable: the id of an item does not change (even if you
 		  ///    delete other nodes).
 		  ///
 		  /// Using this map you get access (i.e. can read) the inner id values of
 		  /// the items stored in the graph, which is returned by the \c id()
 		  /// function of the graph. This map can be inverted with its member
 		  /// class \c InverseMap or with the \c operator() member.
@@ -2268,17 +2268,17 @@
 		    /// \brief Gives back the \e RangeId of the item
 		    ///
 		    /// Gives back the \e RangeId of the item.
 		    int operator[](const Item& item) const {
 		      return Map::operator[](item);
+		    }
 		    /// \brief Gives back the item belonging to a \e RangeId
-		    ///
 		    ///
 		    /// Gives back the item belonging to a \e RangeId.
 		    Item operator()(int id) const {
 		      return _inv_map[id];
+		    }
 		  private:
 		    typedef std::vector<Item> Container;
@@ -2494,33 +2494,33 @@
 		  /// \brief Map of the in-degrees of nodes in a digraph.
 		  ///
 		  /// This map returns the in-degree of a node. Once it is constructed,
 		  /// the degrees are stored in a standard \c NodeMap, so each query is done
 		  /// in constant time. On the other hand, the values are updated automatically
 		  /// whenever the digraph changes.
 		  ///
-		  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
 		  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
 		  /// may provide alternative ways to modify the digraph.
 		  /// The correct behavior of InDegMap is not guarantied if these additional
 		  /// features are used. For example the functions
 		  /// \ref ListDigraph::changeSource() "changeSource()",
 		  /// \ref ListDigraph::changeTarget() "changeTarget()" and
 		  /// \ref ListDigraph::reverseArc() "reverseArc()"
 		  /// of \ref ListDigraph will \e not update the degree values correctly.
 		  ///
 		  /// \sa OutDegMap
 		  template <typename GR>
 		  class InDegMap
 		    : protected ItemSetTraits<GR, typename GR::Arc>
 		      ::ItemNotifier::ObserverBase {
 		  public:
 		    /// The graph type of InDegMap
 		    typedef GR Graph;
 		    typedef GR Digraph;
 		    /// The key type
 		    typedef typename Digraph::Node Key;
 		    /// The value type
 		    typedef int Value;
@@ -2624,17 +2624,17 @@
 		  /// \brief Map of the out-degrees of nodes in a digraph.
 		  ///
 		  /// This map returns the out-degree of a node. Once it is constructed,
 		  /// the degrees are stored in a standard \c NodeMap, so each query is done
 		  /// in constant time. On the other hand, the values are updated automatically
 		  /// whenever the digraph changes.
 		  ///
-		  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
 		  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
 		  /// may provide alternative ways to modify the digraph.
 		  /// The correct behavior of OutDegMap is not guarantied if these additional
 		  /// features are used. For example the functions
 		  /// \ref ListDigraph::changeSource() "changeSource()",
 		  /// \ref ListDigraph::changeTarget() "changeTarget()" and
 		  /// \ref ListDigraph::reverseArc() "reverseArc()"
 		  /// of \ref ListDigraph will \e not update the degree values correctly.
 		  ///

lemon/matching.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -36,17 +36,17 @@
 		namespace lemon {
 		  /// \ingroup matching
 		  ///
 		  /// \brief Maximum cardinality matching in general graphs
 		  ///
 		  /// This class implements Edmonds' alternating forest matching algorithm
 		  /// for finding a maximum cardinality matching in a general undirected graph.
-		  /// It can be started from an arbitrary initial matching
 		  /// It can be started from an arbitrary initial matching
 		  /// (the default is the empty one).
 		  ///
 		  /// The dual solution of the problem is a map of the nodes to
 		  /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D),
 		  /// \c ODD (or \c A) and \c MATCHED (or \c C) defining the Gallai-Edmonds
 		  /// decomposition of the graph. The nodes in \c EVEN/D induce a subgraph
 		  /// with factor-critical components, the nodes in \c ODD/A form the
 		  /// canonical barrier, and the nodes in \c MATCHED/C induce a graph having
@@ -64,21 +64,21 @@
 		    /// The graph type of the algorithm
 		    typedef GR Graph;
 		    /// The type of the matching map
 		    typedef typename Graph::template NodeMap<typename Graph::Arc>
 		    MatchingMap;
 		    ///\brief Status constants for Gallai-Edmonds decomposition.
 		    ///
-		    ///These constants are used for indicating the Gallai-Edmonds
 		    ///These constants are used for indicating the Gallai-Edmonds
 		    ///decomposition of a graph. The nodes with status \c EVEN (or \c D)
 		    ///induce a subgraph with factor-critical components, the nodes with
 		    ///status \c ODD (or \c A) form the canonical barrier, and the nodes
-		    ///with status \c MATCHED (or \c C) induce a subgraph having a
 		    ///with status \c MATCHED (or \c C) induce a subgraph having a
 		    ///perfect matching.
 		    enum Status {
 		      EVEN = 1,       ///< = 1. (\c D is an alias for \c EVEN.)
 		      D = 1,
 		      MATCHED = 0,    ///< = 0. (\c C is an alias for \c MATCHED.)
 		      C = 0,
 		      ODD = -1,       ///< = -1. (\c A is an alias for \c ODD.)
 		      A = -1,
@@ -507,17 +507,17 @@
 		          (*_blossom_rep)[_blossom_set->insert(n)] = n;
 		          _tree_set->insert(n);
 		          (*_status)[n] = EVEN;
 		          processSparse(n);
+		        }
+		      }
+		    }
-		    /// \brief Start Edmonds' algorithm with a heuristic improvement
 		    /// \brief Start Edmonds' algorithm with a heuristic improvement
 		    /// for dense graphs
 		    ///
 		    /// This function runs Edmonds' algorithm with a heuristic of postponing
 		    /// shrinks, therefore resulting in a faster algorithm for dense graphs.
 		    ///
 		    /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
 		    /// called before using this function.
 		    void startDense() {
@@ -529,18 +529,18 @@
 		          processDense(n);
+		        }
+		      }
+		    }
 		    /// \brief Run Edmonds' algorithm
 		    ///
 		    /// This function runs Edmonds' algorithm. An additional heuristic of
 		    /// postponing shrinks is used for relatively dense graphs
 		    /// This function runs Edmonds' algorithm. An additional heuristic of
 		    /// postponing shrinks is used for relatively dense graphs
 		    /// (for which <tt>m>=2*n</tt> holds).
 		    void run() {
 		      if (countEdges(_graph) < 2 * countNodes(_graph)) {
 		        greedyInit();
 		        startSparse();
 		      } else {
 		        init();
 		        startDense();
@@ -551,66 +551,66 @@
 		    /// \name Primal Solution
 		    /// Functions to get the primal solution, i.e. the maximum matching.
 		    /// @{
 		    /// \brief Return the size (cardinality) of the matching.
 		    ///
-		    /// This function returns the size (cardinality) of the current matching.
 		    /// This function returns the size (cardinality) of the current matching.
 		    /// After run() it returns the size of the maximum matching in the graph.
 		    int matchingSize() const {
 		      int size = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if ((*_matching)[n] != INVALID) {
 		          ++size;
+		        }
+		      }
 		      return size / 2;
+		    }
 		    /// \brief Return \c true if the given edge is in the matching.
 		    ///
-		    /// This function returns \c true if the given edge is in the current
 		    /// This function returns \c true if the given edge is in the current
 		    /// matching.
 		    bool matching(const Edge& edge) const {
 		      return edge == (*_matching)[_graph.u(edge)];
+		    }
 		    /// \brief Return the matching arc (or edge) incident to the given node.
 		    ///
 		    /// This function returns the matching arc (or edge) incident to the
-		    /// given node in the current matching or \c INVALID if the node is
 		    /// given node in the current matching or \c INVALID if the node is
 		    /// not covered by the matching.
 		    Arc matching(const Node& n) const {
 		      return (*_matching)[n];
+		    }
 		    /// \brief Return a const reference to the matching map.
 		    ///
 		    /// This function returns a const reference to a node map that stores
 		    /// the matching arc (or edge) incident to each node.
 		    const MatchingMap& matchingMap() const {
 		      return *_matching;
+		    }
 		    /// \brief Return the mate of the given node.
 		    ///
-		    /// This function returns the mate of the given node in the current
 		    /// This function returns the mate of the given node in the current
 		    /// matching or \c INVALID if the node is not covered by the matching.
 		    Node mate(const Node& n) const {
 		      return (*_matching)[n] != INVALID ?
 		        _graph.target((*_matching)[n]) : INVALID;
+		    }
 		    /// @}
 		    /// \name Dual Solution
-		    /// Functions to get the dual solution, i.e. the Gallai-Edmonds
 		    /// Functions to get the dual solution, i.e. the Gallai-Edmonds
 		    /// decomposition.
 		    /// @{
 		    /// \brief Return the status of the given node in the Edmonds-Gallai
 		    /// decomposition.
 		    ///
 		    /// This function returns the \ref Status "status" of the given node
@@ -643,18 +643,18 @@
 		  ///
 		  /// \brief Weighted matching in general graphs
 		  ///
 		  /// This class provides an efficient implementation of Edmond's
 		  /// maximum weighted matching algorithm. The implementation is based
 		  /// on extensive use of priority queues and provides
 		  /// \f$O(nm\log n)\f$ time complexity.
 		  ///
 		  /// The maximum weighted matching problem is to find a subset of the
 		  /// edges in an undirected graph with maximum overall weight for which
 		  /// The maximum weighted matching problem is to find a subset of the
 		  /// edges in an undirected graph with maximum overall weight for which
 		  /// each node has at most one incident edge.
 		  /// It can be formulated with the following linear program.
 		  /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f]
 		  /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
 		      \quad \forall B\in\mathcal{O}\f] */
 		  /// \f[x_e \ge 0\quad \forall e\in E\f]
 		  /// \f[\max \sum_{e\in E}x_ew_e\f]
 		  /// where \f$\delta(X)\f$ is the set of edges incident to a node in
@@ -668,26 +668,26 @@
 		  /// following.
 		  /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}
 		      z_B \ge w_{uv} \quad \forall uv\in E\f] */
 		  /// \f[y_u \ge 0 \quad \forall u \in V\f]
 		  /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f]
 		  /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
 		      \frac{\vert B \vert - 1}{2}z_B\f] */
 		  ///
-		  /// The algorithm can be executed with the run() function.
 		  /// The algorithm can be executed with the run() function.
 		  /// After it the matching (the primal solution) and the dual solution
 		  /// can be obtained using the query functions and the
 		  /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class,
-		  /// which is able to iterate on the nodes of a blossom.
+		  /// can be obtained using the query functions and the
 		  /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class,
 		  /// which is able to iterate on the nodes of a blossom.
 		  /// If the value type is integer, then the dual solution is multiplied
 		  /// by \ref MaxWeightedMatching::dualScale "4".
 		  ///
 		  /// \tparam GR The undirected graph type the algorithm runs on.
-		  /// \tparam WM The type edge weight map. The default type is
 		  /// \tparam WM The type edge weight map. The default type is
 		  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename WM>
 		#else
 		  template <typename GR,
 		            typename WM = typename GR::template EdgeMap<int> >
 		#endif
 		  class MaxWeightedMatching {
@@ -1715,17 +1715,17 @@
+		      }
 		      for (EdgeIt e(_graph); e != INVALID; ++e) {
 		        (*_delta3_index)[e] = _delta3->PRE_HEAP;
+		      }
 		      for (int i = 0; i < _blossom_num; ++i) {
 		        (*_delta2_index)[i] = _delta2->PRE_HEAP;
 		        (*_delta4_index)[i] = _delta4->PRE_HEAP;
+		      }
 		      _delta1->clear();
 		      _delta2->clear();
 		      _delta3->clear();
 		      _delta4->clear();
 		      _blossom_set->clear();
 		      _tree_set->clear();
 		      int index = 0;
@@ -1863,17 +1863,17 @@
 		    void run() {
 		      init();
 		      start();
+		    }
 		    /// @}
 		    /// \name Primal Solution
-		    /// Functions to get the primal solution, i.e. the maximum weighted
 		    /// Functions to get the primal solution, i.e. the maximum weighted
 		    /// matching.\n
 		    /// Either \ref run() or \ref start() function should be called before
 		    /// using them.
 		    /// @{
 		    /// \brief Return the weight of the matching.
 		    ///
@@ -1902,28 +1902,28 @@
 		          ++num;
+		        }
+		      }
 		      return num /= 2;
+		    }
 		    /// \brief Return \c true if the given edge is in the matching.
 		    ///
-		    /// This function returns \c true if the given edge is in the found
 		    /// This function returns \c true if the given edge is in the found
 		    /// matching.
 		    ///
 		    /// \pre Either run() or start() must be called before using this function.
 		    bool matching(const Edge& edge) const {
 		      return edge == (*_matching)[_graph.u(edge)];
+		    }
 		    /// \brief Return the matching arc (or edge) incident to the given node.
 		    ///
 		    /// This function returns the matching arc (or edge) incident to the
-		    /// given node in the found matching or \c INVALID if the node is
 		    /// given node in the found matching or \c INVALID if the node is
 		    /// not covered by the matching.
 		    ///
 		    /// \pre Either run() or start() must be called before using this function.
 		    Arc matching(const Node& node) const {
 		      return (*_matching)[node];
+		    }
 		    /// \brief Return a const reference to the matching map.
@@ -1931,17 +1931,17 @@
 		    /// This function returns a const reference to a node map that stores
 		    /// the matching arc (or edge) incident to each node.
 		    const MatchingMap& matchingMap() const {
 		      return *_matching;
+		    }
 		    /// \brief Return the mate of the given node.
 		    ///
-		    /// This function returns the mate of the given node in the found
 		    /// This function returns the mate of the given node in the found
 		    /// matching or \c INVALID if the node is not covered by the matching.
 		    ///
 		    /// \pre Either run() or start() must be called before using this function.
 		    Node mate(const Node& node) const {
 		      return (*_matching)[node] != INVALID ?
 		        _graph.target((*_matching)[node]) : INVALID;
+		    }
@@ -1951,18 +1951,18 @@
 		    /// Functions to get the dual solution.\n
 		    /// Either \ref run() or \ref start() function should be called before
 		    /// using them.
 		    /// @{
 		    /// \brief Return the value of the dual solution.
 		    ///
 		    /// This function returns the value of the dual solution.
 		    /// It should be equal to the primal value scaled by \ref dualScale
 		    /// This function returns the value of the dual solution.
 		    /// It should be equal to the primal value scaled by \ref dualScale
 		    /// "dual scale".
 		    ///
 		    /// \pre Either run() or start() must be called before using this function.
 		    Value dualValue() const {
 		      Value sum = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        sum += nodeValue(n);
+		      }
@@ -2007,29 +2007,29 @@
 		    ///
 		    /// \pre Either run() or start() must be called before using this function.
 		    Value blossomValue(int k) const {
 		      return _blossom_potential[k].value;
+		    }
 		    /// \brief Iterator for obtaining the nodes of a blossom.
 		    ///
-		    /// This class provides an iterator for obtaining the nodes of the
 		    /// This class provides an iterator for obtaining the nodes of the
 		    /// given blossom. It lists a subset of the nodes.
-		    /// Before using this iterator, you must allocate a
 		    /// Before using this iterator, you must allocate a
 		    /// MaxWeightedMatching class and execute it.
 		    class BlossomIt {
 		    public:
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor to get the nodes of the given variable.
 		      ///
 		      /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or
 		      /// \ref MaxWeightedMatching::start() "algorithm.start()" must be
 		      /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or
 		      /// \ref MaxWeightedMatching::start() "algorithm.start()" must be
 		      /// called before initializing this iterator.
 		      BlossomIt(const MaxWeightedMatching& algorithm, int variable)
 		        : _algorithm(&algorithm)
+		      {
 		        _index = _algorithm->_blossom_potential[variable].begin;
 		        _last = _algorithm->_blossom_potential[variable].end;
+		      }
@@ -2072,18 +2072,18 @@
 		  ///
 		  /// \brief Weighted perfect matching in general graphs
 		  ///
 		  /// This class provides an efficient implementation of Edmond's
 		  /// maximum weighted perfect matching algorithm. The implementation
 		  /// is based on extensive use of priority queues and provides
 		  /// \f$O(nm\log n)\f$ time complexity.
 		  ///
 		  /// The maximum weighted perfect matching problem is to find a subset of
 		  /// the edges in an undirected graph with maximum overall weight for which
 		  /// The maximum weighted perfect matching problem is to find a subset of
 		  /// the edges in an undirected graph with maximum overall weight for which
 		  /// each node has exactly one incident edge.
 		  /// It can be formulated with the following linear program.
 		  /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f]
 		  /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
 		      \quad \forall B\in\mathcal{O}\f] */
 		  /// \f[x_e \ge 0\quad \forall e\in E\f]
 		  /// \f[\max \sum_{e\in E}x_ew_e\f]
 		  /// where \f$\delta(X)\f$ is the set of edges incident to a node in
@@ -2096,26 +2096,26 @@
 		  /// the result of the algorithm. The dual linear problem is the
 		  /// following.
 		  /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}z_B \ge
 		      w_{uv} \quad \forall uv\in E\f] */
 		  /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f]
 		  /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
 		      \frac{\vert B \vert - 1}{2}z_B\f] */
 		  ///
-		  /// The algorithm can be executed with the run() function.
 		  /// The algorithm can be executed with the run() function.
 		  /// After it the matching (the primal solution) and the dual solution
 		  /// can be obtained using the query functions and the
 		  /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class,
-		  /// which is able to iterate on the nodes of a blossom.
+		  /// can be obtained using the query functions and the
 		  /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class,
 		  /// which is able to iterate on the nodes of a blossom.
 		  /// If the value type is integer, then the dual solution is multiplied
 		  /// by \ref MaxWeightedMatching::dualScale "4".
 		  ///
 		  /// \tparam GR The undirected graph type the algorithm runs on.
-		  /// \tparam WM The type edge weight map. The default type is
 		  /// \tparam WM The type edge weight map. The default type is
 		  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename WM>
 		#else
 		  template <typename GR,
 		            typename WM = typename GR::template EdgeMap<int> >
 		#endif
 		  class MaxWeightedPerfectMatching {
@@ -3110,17 +3110,17 @@
 		    bool run() {
 		      init();
 		      return start();
+		    }
 		    /// @}
 		    /// \name Primal Solution
-		    /// Functions to get the primal solution, i.e. the maximum weighted
 		    /// Functions to get the primal solution, i.e. the maximum weighted
 		    /// perfect matching.\n
 		    /// Either \ref run() or \ref start() function should be called before
 		    /// using them.
 		    /// @{
 		    /// \brief Return the weight of the matching.
 		    ///
@@ -3134,28 +3134,28 @@
 		          sum += _weight[(*_matching)[n]];
+		        }
+		      }
 		      return sum /= 2;
+		    }
 		    /// \brief Return \c true if the given edge is in the matching.
 		    ///
-		    /// This function returns \c true if the given edge is in the found
 		    /// This function returns \c true if the given edge is in the found
 		    /// matching.
 		    ///
 		    /// \pre Either run() or start() must be called before using this function.
 		    bool matching(const Edge& edge) const {
 		      return static_cast<const Edge&>((*_matching)[_graph.u(edge)]) == edge;
+		    }
 		    /// \brief Return the matching arc (or edge) incident to the given node.
 		    ///
 		    /// This function returns the matching arc (or edge) incident to the
-		    /// given node in the found matching or \c INVALID if the node is
 		    /// given node in the found matching or \c INVALID if the node is
 		    /// not covered by the matching.
 		    ///
 		    /// \pre Either run() or start() must be called before using this function.
 		    Arc matching(const Node& node) const {
 		      return (*_matching)[node];
+		    }
 		    /// \brief Return a const reference to the matching map.
@@ -3163,17 +3163,17 @@
 		    /// This function returns a const reference to a node map that stores
 		    /// the matching arc (or edge) incident to each node.
 		    const MatchingMap& matchingMap() const {
 		      return *_matching;
+		    }
 		    /// \brief Return the mate of the given node.
 		    ///
-		    /// This function returns the mate of the given node in the found
 		    /// This function returns the mate of the given node in the found
 		    /// matching or \c INVALID if the node is not covered by the matching.
 		    ///
 		    /// \pre Either run() or start() must be called before using this function.
 		    Node mate(const Node& node) const {
 		      return _graph.target((*_matching)[node]);
+		    }
 		    /// @}
@@ -3182,18 +3182,18 @@
 		    /// Functions to get the dual solution.\n
 		    /// Either \ref run() or \ref start() function should be called before
 		    /// using them.
 		    /// @{
 		    /// \brief Return the value of the dual solution.
 		    ///
 		    /// This function returns the value of the dual solution.
 		    /// It should be equal to the primal value scaled by \ref dualScale
 		    /// This function returns the value of the dual solution.
 		    /// It should be equal to the primal value scaled by \ref dualScale
 		    /// "dual scale".
 		    ///
 		    /// \pre Either run() or start() must be called before using this function.
 		    Value dualValue() const {
 		      Value sum = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        sum += nodeValue(n);
+		      }
@@ -3238,29 +3238,29 @@
 		    ///
 		    /// \pre Either run() or start() must be called before using this function.
 		    Value blossomValue(int k) const {
 		      return _blossom_potential[k].value;
+		    }
 		    /// \brief Iterator for obtaining the nodes of a blossom.
 		    ///
-		    /// This class provides an iterator for obtaining the nodes of the
 		    /// This class provides an iterator for obtaining the nodes of the
 		    /// given blossom. It lists a subset of the nodes.
-		    /// Before using this iterator, you must allocate a
 		    /// Before using this iterator, you must allocate a
 		    /// MaxWeightedPerfectMatching class and execute it.
 		    class BlossomIt {
 		    public:
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor to get the nodes of the given variable.
 		      ///
 		      /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()"
 		      /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()"
 		      /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()"
 		      /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()"
 		      /// must be called before initializing this iterator.
 		      BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
 		        : _algorithm(&algorithm)
+		      {
 		        _index = _algorithm->_blossom_potential[variable].begin;
 		        _last = _algorithm->_blossom_potential[variable].end;
+		      }

lemon/math.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
 * Copyright (C) 2003-2011
 * 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,
@@ -51,17 +51,17 @@
  /// pi/4
  const long double PI_4    = 0.7853981633974483096156608458198757L;
  /// sqrt(2)
  const long double SQRT2   = 1.4142135623730950488016887242096981L;
  /// 1/sqrt(2)
  const long double SQRT1_2 = 0.7071067811865475244008443621048490L;

  ///Check whether the parameter is NaN or not
  

  ///This function checks whether the parameter is NaN or not.
  ///Is should be equivalent with std::isnan(), but it is not
  ///provided by all compilers.
  inline bool isNaN(double v)
    {
      return v!=v;
    }


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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -122,18 +122,18 @@
 		            typename TR =
 		              MinCostArborescenceDefaultTraits<GR, CM> >
 		#else
 		  template <typename GR, typename CM, typedef TR>
 		#endif
 		  class MinCostArborescence {
 		  public:
 		    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class"
 		    /// of the algorithm.
 		    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class"
 		    /// of the algorithm.
 		    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.
@@ -430,17 +430,17 @@
+		      }
 		    };
 		    /// \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,
 		    /// It must meet the \ref concepts::WriteMap "WriteMap" concept,
 		    /// and its value type must be the \c Arc type of the digraph.
 		    template <class T>
 		    struct SetPredMap
 		      : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
 		    };
 		    /// @}

lemon/network_simplex.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -90,17 +90,17 @@
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The objective function of the problem is unbounded, i.e.
 		      /// there is a directed cycle having negative total cost and
 		      /// infinite upper bound.
 		      UNBOUNDED
 		    };
 		    /// \brief Constants for selecting the type of the supply constraints.
 		    ///
 		    /// Enum type containing constants for selecting the supply type,
 		    /// i.e. the direction of the inequalities in the supply/demand
 		    /// constraints of the \ref min_cost_flow "minimum cost flow problem".
 		    ///
 		    /// The default supply type is \c GEQ, the \c LEQ type can be
 		    /// selected using \ref supplyType().
@@ -108,17 +108,17 @@
 		    enum SupplyType {
 		      /// This option means that there are <em>"greater or equal"</em>
 		      /// supply/demand constraints in the definition of the problem.
 		      GEQ,
 		      /// This option means that there are <em>"less or equal"</em>
 		      /// supply/demand constraints in the definition of the problem.
 		      LEQ
 		    };
 		    /// \brief Constants for selecting the pivot rule.
 		    ///
 		    /// Enum type containing constants for selecting the pivot rule for
 		    /// the \ref run() function.
 		    ///
 		    /// \ref NetworkSimplex provides five different pivot rule
 		    /// implementations that significantly affect the running time
 		    /// of the algorithm.
@@ -151,17 +151,17 @@
 		      CANDIDATE_LIST,
 		      /// The Altering Candidate List pivot rule.
 		      /// It is a modified version of the Candidate List method.
 		      /// It keeps only the several best eligible arcs from the former
 		      /// candidate list and extends this list in every iteration.
 		      ALTERING_LIST
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<Arc> ArcVector;
 		    typedef std::vector<Node> NodeVector;
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<bool> BoolVector;
@@ -218,17 +218,17 @@
 		    // Temporary data used in the current pivot iteration
 		    int in_arc, join, u_in, v_in, u_out, v_out;
 		    int first, second, right, last;
 		    int stem, par_stem, new_stem;
 		    Value delta;
 		  public:
 		    /// \brief Constant for infinite upper bounds (capacities).
 		    ///
 		    /// Constant for infinite upper bounds (capacities).
 		    /// It is \c std::numeric_limits<Value>::infinity() if available,
 		    /// \c std::numeric_limits<Value>::max() otherwise.
 		    const Value INF;
 		  private:
@@ -639,17 +639,17 @@
 		          std::numeric_limits<Value>::infinity() :
 		          std::numeric_limits<Value>::max())
+		    {
 		      // Check the value types
 		      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
 		        "The flow type of NetworkSimplex must be signed");
 		      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
 		        "The cost type of NetworkSimplex must be signed");
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      int all_node_num = _node_num + 1;
 		      int max_arc_num = _arc_num + 2 * _node_num;
 		      _source.resize(max_arc_num);
 		      _target.resize(max_arc_num);
@@ -679,17 +679,17 @@
 		      int k = std::max(int(std::sqrt(double(_arc_num))), 10);
 		      i = 0;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _arc_id[a] = i;
 		        _source[i] = _node_id[_graph.source(a)];
 		        _target[i] = _node_id[_graph.target(a)];
 		        if ((i += k) >= _arc_num) i = (i % k) + 1;
+		      }
 		      // Initialize maps
 		      for (int i = 0; i != _node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      for (int i = 0; i != _arc_num; ++i) {
 		        _lower[i] = 0;
 		        _upper[i] = INF;
 		        _cost[i] = 1;
@@ -804,17 +804,17 @@
 		    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      _supply[_node_id[s]] =  k;
 		      _supply[_node_id[t]] = -k;
 		      return *this;
+		    }
 		    /// \brief Set the type of the supply constraints.
 		    ///
 		    /// This function sets the type of the supply/demand constraints.
 		    /// If it is not used before calling \ref run(), the \ref GEQ supply
 		    /// type will be used.
 		    ///
 		    /// For more information see \ref SupplyType.
 		    ///
@@ -830,17 +830,17 @@
 		    /// The algorithm can be executed using \ref run().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// The paramters can be specified using functions \ref lowerMap(),
-		    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
 		    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
 		    /// \ref supplyType().
 		    /// For example,
 		    /// \code
 		    ///   NetworkSimplex<ListDigraph> ns(graph);
 		    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
@@ -1049,17 +1049,17 @@
 		        ART_COST = (ART_COST + 1) * _node_num;
+		      }
 		      // Initialize arc maps
 		      for (int i = 0; i != _arc_num; ++i) {
 		        _flow[i] = 0;
 		        _state[i] = STATE_LOWER;
+		      }
 		      // Set data for the artificial root node
 		      _root = _node_num;
 		      _parent[_root] = -1;
 		      _pred[_root] = -1;
 		      _thread[_root] = 0;
 		      _rev_thread[0] = _root;
 		      _succ_num[_root] = _node_num + 1;
 		      _last_succ[_root] = _root - 1;
@@ -1223,17 +1223,17 @@
 		          delta = d;
 		          u_out = u;
 		          result = 1;
+		        }
+		      }
 		      // Search the cycle along the path form the second node to the root
 		      for (int u = second; u != join; u = _parent[u]) {
 		        e = _pred[u];
-		        d = _forward[u] ?
 		        d = _forward[u] ?
 		          (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
 		        if (d <= delta) {
 		          delta = d;
 		          u_out = u;
 		          result = 2;
+		        }
+		      }
@@ -1430,34 +1430,34 @@
 		        bool change = findLeavingArc();
 		        if (delta >= INF) return UNBOUNDED;
 		        changeFlow(change);
 		        if (change) {
 		          updateTreeStructure();
 		          updatePotential();
+		        }
+		      }
 		      // Check feasibility
 		      for (int e = _search_arc_num; e != _all_arc_num; ++e) {
 		        if (_flow[e] != 0) return INFEASIBLE;
+		      }
 		      // Transform the solution and the supply map to the original form
 		      if (_have_lower) {
 		        for (int i = 0; i != _arc_num; ++i) {
 		          Value c = _lower[i];
 		          if (c != 0) {
 		            _flow[i] += c;
 		            _supply[_source[i]] += c;
 		            _supply[_target[i]] -= c;
+		          }
+		        }
+		      }
 		      // Shift potentials to meet the requirements of the GEQ/LEQ type
 		      // optimality conditions
 		      if (_sum_supply == 0) {
 		        if (_stype == GEQ) {
 		          Cost max_pot = -std::numeric_limits<Cost>::max();
 		          for (int i = 0; i != _node_num; ++i) {
 		            if (_pi[i] > max_pot) max_pot = _pi[i];
+		          }

lemon/path.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -961,30 +961,30 @@
 		    template <typename From, typename To>
 		    struct PathCopySelectorBackward<From, To, true> {
 		      static void copy(const From& from, To& to) {
 		        to.clear();
 		        to.buildRev(from);
+		      }
 		    };
 		    template <typename From, typename To,
 		              bool revEnable = RevPathTagIndicator<From>::value>
 		    struct PathCopySelector {
 		      static void copy(const From& from, To& to) {
 		        PathCopySelectorForward<From, To>::copy(from, to);
+		      }
+		      }
 		    };
 		    template <typename From, typename To>
 		    struct PathCopySelector<From, To, true> {
 		      static void copy(const From& from, To& to) {
 		        PathCopySelectorBackward<From, To>::copy(from, to);
+		      }
+		      }
 		    };
+		  }
 		  /// \brief Make a copy of a path.
 		  ///
 		  /// This function makes a copy of a path.

lemon/preflow.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -531,20 +531,20 @@
 		        Value rem = (*_flow)[e];
 		        if (_tolerance.positive(rem)) {
 		          Node v = _graph.source(e);
 		          if ((*_level)[v] == _level->maxLevel()) continue;
 		          _flow->set(e, 0);
 		          (*_excess)[v] += rem;
+		        }
+		      }
-		      for (NodeIt n(_graph); n != INVALID; ++n)
 		      for (NodeIt n(_graph); n != INVALID; ++n)
 		        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
 		          _level->activate(n);
 		      return true;
+		    }
 		    /// \brief Starts the first phase of the preflow algorithm.
 		    ///
 		    /// The preflow algorithm consists of two phases, this method runs
 		    /// the first phase. After the first phase the maximum flow value
 		    /// and a minimum value cut can already be computed, although a
@@ -562,17 +562,17 @@
 		        Node n = INVALID;
 		        int level = -1;
 		        while (num > 0) {
 		          n = _level->highestActive();
 		          if (n == INVALID) goto first_phase_done;
 		          level = _level->highestActiveLevel();
 		          --num;
 		          Value excess = (*_excess)[n];
 		          int new_level = _level->maxLevel();
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		            Value rem = (*_capacity)[e] - (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.target(e);
 		            if ((*_level)[v] < level) {

lemon/soplex.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-2008
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -269,17 +269,17 @@
 		  SoplexLp::Value SoplexLp::_getObjCoeff(int i) const {
 		    return soplex->obj(i);
+		  }
 		  SoplexLp::SolveExitStatus SoplexLp::_solve() {
 		    _clear_temporals();
 		    _applyMessageLevel();
 		    soplex::SPxSolver::Status status = soplex->solve();
 		    switch (status) {
 		    case soplex::SPxSolver::OPTIMAL:
 		    case soplex::SPxSolver::INFEASIBLE:
 		    case soplex::SPxSolver::UNBOUNDED:

lemon/soplex.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
 * Copyright (C) 2003-2011
 * 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,

lemon/suurballe.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
 * Copyright (C) 2003-2011
 * 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,

lemon/unionfind.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
 * Copyright (C) 2003-2011
 * 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,

test/bfs_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -78,17 +78,17 @@
 		    bfs_test.init();
 		    bfs_test.addSource(s);
 		    n = bfs_test.processNextNode();
 		    n = bfs_test.processNextNode(t, b);
 		    n = bfs_test.processNextNode(nm, n);
 		    n = const_bfs_test.nextNode();
 		    b = const_bfs_test.emptyQueue();
 		    i = const_bfs_test.queueSize();
 		    bfs_test.start();
 		    bfs_test.start(t);
 		    bfs_test.start(nm);
 		    l  = const_bfs_test.dist(t);
 		    e  = const_bfs_test.predArc(t);
 		    s  = const_bfs_test.predNode(t);
 		    b  = const_bfs_test.reached(t);
@@ -99,41 +99,41 @@
+		  {
 		    BType
 		      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
 		      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
 		      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
 		      ::SetStandardProcessedMap
 		      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
 		      ::Create bfs_test(G);
 		    concepts::ReadWriteMap<Node,Arc> pred_map;
 		    concepts::ReadWriteMap<Node,int> dist_map;
 		    concepts::ReadWriteMap<Node,bool> reached_map;
 		    concepts::WriteMap<Node,bool> processed_map;
 		    bfs_test
 		      .predMap(pred_map)
 		      .distMap(dist_map)
 		      .reachedMap(reached_map)
 		      .processedMap(processed_map);
 		    bfs_test.run(s);
 		    bfs_test.run(s,t);
 		    bfs_test.run();
 		    bfs_test.init();
 		    bfs_test.addSource(s);
 		    n = bfs_test.processNextNode();
 		    n = bfs_test.processNextNode(t, b);
 		    n = bfs_test.processNextNode(nm, n);
 		    n = bfs_test.nextNode();
 		    b = bfs_test.emptyQueue();
 		    i = bfs_test.queueSize();
 		    bfs_test.start();
 		    bfs_test.start(t);
 		    bfs_test.start(nm);
 		    l  = bfs_test.dist(t);
 		    e  = bfs_test.predArc(t);
 		    s  = bfs_test.predNode(t);
 		    b  = bfs_test.reached(t);

test/circulation_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -76,33 +76,33 @@
 		  typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>
 		            ::SetFlowMap<FlowMap>
 		            ::SetElevator<Elev>
 		            ::SetStandardElevator<LinkedElev>
 		            ::Create CirculationType;
 		  CirculationType circ_test(g, lcap, ucap, supply);
 		  const CirculationType& const_circ_test = circ_test;
 		  circ_test
 		    .lowerMap(lcap)
 		    .upperMap(ucap)
 		    .supplyMap(supply)
 		    .flowMap(flow);
 		  circ_test.init();
 		  circ_test.greedyInit();
 		  circ_test.start();
 		  circ_test.run();
 		  v = const_circ_test.flow(a);
 		  const FlowMap& fm = const_circ_test.flowMap();
 		  b = const_circ_test.barrier(n);
 		  const_circ_test.barrierMap(bar);
 		  ignore_unused_variable_warning(fm);
+		}
 		template <class G, class LM, class UM, class DM>
 		void checkCirculation(const G& g, const LM& lm, const UM& um,
 		                      const DM& dm, bool find)
+		{
 		  Circulation<G, LM, UM, DM> circ(g, lm, um, dm);

test/connectivity_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -24,36 +24,36 @@
 		using namespace lemon;
 		int main()
+		{
 		  typedef ListDigraph Digraph;
 		  typedef Undirector<Digraph> Graph;
+		  {
 		    Digraph d;
 		    Digraph::NodeMap<int> order(d);
 		    Graph g(d);
 		    check(stronglyConnected(d), "The empty digraph is strongly connected");
 		    check(countStronglyConnectedComponents(d) == 0,
 		          "The empty digraph has 0 strongly connected component");
 		    check(connected(g), "The empty graph is connected");
 		    check(countConnectedComponents(g) == 0,
 		          "The empty graph has 0 connected component");
 		    check(biNodeConnected(g), "The empty graph is bi-node-connected");
 		    check(countBiNodeConnectedComponents(g) == 0,
 		          "The empty graph has 0 bi-node-connected component");
 		    check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
 		    check(countBiEdgeConnectedComponents(g) == 0,
 		          "The empty graph has 0 bi-edge-connected component");
 		    check(dag(d), "The empty digraph is DAG.");
 		    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
 		    check(loopFree(d), "The empty digraph is loop-free.");
 		    check(parallelFree(d), "The empty digraph is parallel-free.");
 		    check(simpleGraph(d), "The empty digraph is simple.");
 		    check(acyclic(g), "The empty graph is acyclic.");
 		    check(tree(g), "The empty graph is tree.");
@@ -77,17 +77,17 @@
 		          "This graph has 1 connected component");
 		    check(biNodeConnected(g), "This graph is bi-node-connected");
 		    check(countBiNodeConnectedComponents(g) == 0,
 		          "This graph has 0 bi-node-connected component");
 		    check(biEdgeConnected(g), "This graph is bi-edge-connected");
 		    check(countBiEdgeConnectedComponents(g) == 1,
 		          "This graph has 1 bi-edge-connected component");
 		    check(dag(d), "This digraph is DAG.");
 		    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
 		    check(loopFree(d), "This digraph is loop-free.");
 		    check(parallelFree(d), "This digraph is parallel-free.");
 		    check(simpleGraph(d), "This digraph is simple.");
 		    check(acyclic(g), "This graph is acyclic.");
 		    check(tree(g), "This graph is tree.");
@@ -96,24 +96,24 @@
 		    check(parallelFree(g), "This graph is parallel-free.");
 		    check(simpleGraph(g), "This graph is simple.");
+		  }
+		  {
 		    Digraph d;
 		    Digraph::NodeMap<int> order(d);
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    Digraph::Node n4 = d.addNode();
 		    Digraph::Node n5 = d.addNode();
 		    Digraph::Node n6 = d.addNode();
 		    d.addArc(n1, n3);
 		    d.addArc(n3, n2);
 		    d.addArc(n2, n1);
 		    d.addArc(n4, n2);
 		    d.addArc(n4, n3);
 		    d.addArc(n5, n6);
 		    d.addArc(n6, n5);
@@ -131,33 +131,33 @@
 		    check(simpleGraph(d), "This digraph is simple.");
 		    check(!acyclic(g), "This graph is not acyclic.");
 		    check(!tree(g), "This graph is not tree.");
 		    check(!bipartite(g), "This graph is not bipartite.");
 		    check(loopFree(g), "This graph is loop-free.");
 		    check(!parallelFree(g), "This graph is not parallel-free.");
 		    check(!simpleGraph(g), "This graph is not simple.");
 		    d.addArc(n3, n3);
 		    check(!loopFree(d), "This digraph is not loop-free.");
 		    check(!loopFree(g), "This graph is not loop-free.");
 		    check(!simpleGraph(d), "This digraph is not simple.");
 		    d.addArc(n3, n2);
 		    check(!parallelFree(d), "This digraph is not parallel-free.");
+		  }
+		  {
 		    Digraph d;
 		    Digraph::ArcMap<bool> cutarcs(d, false);
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    Digraph::Node n4 = d.addNode();
 		    Digraph::Node n5 = d.addNode();
 		    Digraph::Node n6 = d.addNode();
 		    Digraph::Node n7 = d.addNode();
 		    Digraph::Node n8 = d.addNode();
@@ -167,17 +167,17 @@
 		    d.addArc(n2, n8);
 		    d.addArc(n8, n5);
 		    d.addArc(n6, n4);
 		    d.addArc(n4, n6);
 		    d.addArc(n2, n5);
 		    d.addArc(n1, n8);
 		    d.addArc(n6, n7);
 		    d.addArc(n7, n6);
 		    check(!stronglyConnected(d), "This digraph is not strongly connected");
 		    check(countStronglyConnectedComponents(d) == 3,
 		          "This digraph has 3 strongly connected components");
 		    Digraph::NodeMap<int> scomp1(d);
 		    check(stronglyConnectedComponents(d, scomp1) == 3,
 		          "This digraph has 3 strongly connected components");
 		    check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
 		          scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
@@ -230,17 +230,17 @@
+		    }
+		  }
+		  {
 		    // DAG example for topological sort from the book New Algorithms
 		    // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
 		    Digraph d;
 		    Digraph::NodeMap<int> order(d);
 		    Digraph::Node belt = d.addNode();
 		    Digraph::Node trousers = d.addNode();
 		    Digraph::Node necktie = d.addNode();
 		    Digraph::Node coat = d.addNode();
 		    Digraph::Node socks = d.addNode();
 		    Digraph::Node shirt = d.addNode();
 		    Digraph::Node shoe = d.addNode();
 		    Digraph::Node watch = d.addNode();
@@ -250,48 +250,48 @@
 		    d.addArc(pants, shoe);
 		    d.addArc(pants, trousers);
 		    d.addArc(trousers, shoe);
 		    d.addArc(trousers, belt);
 		    d.addArc(belt, coat);
 		    d.addArc(shirt, belt);
 		    d.addArc(shirt, necktie);
 		    d.addArc(necktie, coat);
 		    check(dag(d), "This digraph is DAG.");
 		    topologicalSort(d, order);
 		    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
 		      check(order[d.source(a)] < order[d.target(a)],
 		            "Wrong topologicalSort()");
+		    }
+		  }
+		  {
 		    ListGraph g;
 		    ListGraph::NodeMap<bool> map(g);
 		    ListGraph::Node n1 = g.addNode();
 		    ListGraph::Node n2 = g.addNode();
 		    ListGraph::Node n3 = g.addNode();
 		    ListGraph::Node n4 = g.addNode();
 		    ListGraph::Node n5 = g.addNode();
 		    ListGraph::Node n6 = g.addNode();
 		    ListGraph::Node n7 = g.addNode();
 		    g.addEdge(n1, n3);
 		    g.addEdge(n1, n4);
 		    g.addEdge(n2, n5);
 		    g.addEdge(n3, n6);
 		    g.addEdge(n4, n6);
 		    g.addEdge(n4, n7);
 		    g.addEdge(n5, n7);
 		    check(bipartite(g), "This graph is bipartite");
 		    check(bipartitePartitions(g, map), "This graph is bipartite");
 		    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
 		          "Wrong bipartitePartitions()");
 		    check(map[n3] == map[n4] && map[n3] == map[n5],
 		          "Wrong bipartitePartitions()");
+		  }
 		  return 0;
+		}

test/dfs_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -81,17 +81,17 @@
 		    dfs_test.run();
 		    dfs_test.init();
 		    dfs_test.addSource(s);
 		    e = dfs_test.processNextArc();
 		    e = const_dfs_test.nextArc();
 		    b = const_dfs_test.emptyQueue();
 		    i = const_dfs_test.queueSize();
 		    dfs_test.start();
 		    dfs_test.start(t);
 		    dfs_test.start(am);
 		    l  = const_dfs_test.dist(t);
 		    e  = const_dfs_test.predArc(t);
 		    s  = const_dfs_test.predNode(t);
 		    b  = const_dfs_test.reached(t);
@@ -107,34 +107,34 @@
 		      ::SetStandardProcessedMap
 		      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
 		      ::Create dfs_test(G);
 		    concepts::ReadWriteMap<Node,Arc> pred_map;
 		    concepts::ReadWriteMap<Node,int> dist_map;
 		    concepts::ReadWriteMap<Node,bool> reached_map;
 		    concepts::WriteMap<Node,bool> processed_map;
 		    dfs_test
 		      .predMap(pred_map)
 		      .distMap(dist_map)
 		      .reachedMap(reached_map)
 		      .processedMap(processed_map);
 		    dfs_test.run(s);
 		    dfs_test.run(s,t);
 		    dfs_test.run();
 		    dfs_test.init();
 		    dfs_test.addSource(s);
 		    e = dfs_test.processNextArc();
 		    e = dfs_test.nextArc();
 		    b = dfs_test.emptyQueue();
 		    i = dfs_test.queueSize();
 		    dfs_test.start();
 		    dfs_test.start(t);
 		    dfs_test.start(am);
 		    l  = dfs_test.dist(t);
 		    e  = dfs_test.predArc(t);
 		    s  = dfs_test.predNode(t);
 		    b  = dfs_test.reached(t);
@@ -214,17 +214,17 @@
+		      }
+		    }
+		  }
+		  {
 		  Dfs<Digraph> dfs(G);
 		  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
+		  }
+		  {
 		    NullMap<Node,Arc> myPredMap;
 		    dfs(G).predMap(myPredMap).run(s);
+		  }
+		}
 		int main()
+		{

test/dijkstra_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -80,17 +80,17 @@
 		    dijkstra_test.init();
 		    dijkstra_test.addSource(s);
 		    dijkstra_test.addSource(s, 1);
 		    n = dijkstra_test.processNextNode();
 		    n = const_dijkstra_test.nextNode();
 		    b = const_dijkstra_test.emptyQueue();
 		    i = const_dijkstra_test.queueSize();
 		    dijkstra_test.start();
 		    dijkstra_test.start(t);
 		    dijkstra_test.start(nm);
 		    l  = const_dijkstra_test.dist(t);
 		    e  = const_dijkstra_test.predArc(t);
 		    s  = const_dijkstra_test.predNode(t);
 		    b  = const_dijkstra_test.reached(t);
@@ -104,44 +104,44 @@
 		    DType
 		      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
 		      ::SetDistMap<concepts::ReadWriteMap<Node,VType> >
 		      ::SetStandardProcessedMap
 		      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
 		      ::SetOperationTraits<DijkstraDefaultOperationTraits<VType> >
 		      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
 		      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
-		      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
 		      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
 		                concepts::ReadWriteMap<Node,int> >
 		      ::Create dijkstra_test(G,length);
 		    LengthMap length_map;
 		    concepts::ReadWriteMap<Node,Arc> pred_map;
 		    concepts::ReadWriteMap<Node,VType> dist_map;
 		    concepts::WriteMap<Node,bool> processed_map;
 		    concepts::ReadWriteMap<Node,int> heap_cross_ref;
 		    BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref);
 		    dijkstra_test
 		      .lengthMap(length_map)
 		      .predMap(pred_map)
 		      .distMap(dist_map)
 		      .processedMap(processed_map)
 		      .heap(heap, heap_cross_ref);
 		    dijkstra_test.run(s);
 		    dijkstra_test.run(s,t);
 		    dijkstra_test.addSource(s);
 		    dijkstra_test.addSource(s, 1);
 		    n = dijkstra_test.processNextNode();
 		    n = dijkstra_test.nextNode();
 		    b = dijkstra_test.emptyQueue();
 		    i = dijkstra_test.queueSize();
 		    dijkstra_test.start();
 		    dijkstra_test.start(t);
 		    dijkstra_test.start(nm);
 		    l  = dijkstra_test.dist(t);
 		    e  = dijkstra_test.predArc(t);
 		    s  = dijkstra_test.predNode(t);
 		    b  = dijkstra_test.reached(t);

test/edge_set_test.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-2008
 * Copyright (C) 2003-2011
 * 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,

test/euler_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -80,21 +80,21 @@
 		        "checkEulerIt: Not visited or multiple times visited edge found");
+		  }
+		}
 		int main()
+		{
 		  typedef ListDigraph Digraph;
 		  typedef Undirector<Digraph> Graph;
+		  {
 		    Digraph d;
 		    Graph g(d);
 		    checkDiEulerIt(d);
 		    checkDiEulerIt(g);
 		    checkEulerIt(g);
 		    check(eulerian(d), "This graph is Eulerian");
 		    check(eulerian(g), "This graph is Eulerian");
+		  }
+		  {
@@ -123,17 +123,17 @@
 		    check(eulerian(g), "This graph is Eulerian");
+		  }
+		  {
 		    Digraph d;
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    d.addArc(n1, n2);
 		    d.addArc(n2, n1);
 		    d.addArc(n2, n3);
 		    d.addArc(n3, n2);
 		    checkDiEulerIt(d);
 		    checkDiEulerIt(d, n2);
 		    checkDiEulerIt(g);
@@ -148,17 +148,17 @@
 		    Digraph d;
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    Digraph::Node n4 = d.addNode();
 		    Digraph::Node n5 = d.addNode();
 		    Digraph::Node n6 = d.addNode();
 		    d.addArc(n1, n2);
 		    d.addArc(n2, n4);
 		    d.addArc(n1, n3);
 		    d.addArc(n3, n4);
 		    d.addArc(n4, n1);
 		    d.addArc(n3, n5);
 		    d.addArc(n5, n2);
 		    d.addArc(n4, n6);
@@ -184,17 +184,17 @@
 		    Digraph d;
 		    Graph g(d);
 		    Digraph::Node n0 = d.addNode();
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    Digraph::Node n4 = d.addNode();
 		    Digraph::Node n5 = d.addNode();
 		    d.addArc(n1, n2);
 		    d.addArc(n2, n3);
 		    d.addArc(n3, n1);
 		    checkDiEulerIt(d);
 		    checkDiEulerIt(d, n2);
 		    checkDiEulerIt(g);
@@ -206,17 +206,17 @@
 		    check(!eulerian(g), "This graph is not Eulerian");
+		  }
+		  {
 		    Digraph d;
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    d.addArc(n1, n2);
 		    d.addArc(n2, n3);
 		    check(!eulerian(d), "This graph is not Eulerian");
 		    check(!eulerian(g), "This graph is not Eulerian");
+		  }
 		  return 0;

test/gomory_hu_test.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-2011
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <iostream>
 		#include "test_tools.h"
 		#include <lemon/smart_graph.h>
 		#include <lemon/concepts/graph.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/gomory_hu.h>
@@ -28,17 +46,17 @@
 		  "2 3  2     1\n"
 		  "0 3  4     5\n"
 		  "0 3  5     10\n"
 		  "0 3  6     7\n"
 		  "4 2  7     1\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "target 3\n";
 		void checkGomoryHuCompile()
+		{
 		  typedef int Value;
 		  typedef concepts::Graph Graph;
 		  typedef Graph::Node Node;
 		  typedef Graph::Edge Edge;
 		  typedef concepts::ReadMap<Edge, Value> CapMap;
@@ -64,17 +82,17 @@
 		  v = const_gh_test.minCutMap(n, n, cut);
+		}
 		GRAPH_TYPEDEFS(Graph);
 		typedef Graph::EdgeMap<int> IntEdgeMap;
 		typedef Graph::NodeMap<bool> BoolNodeMap;
 		int cutValue(const Graph& graph, const BoolNodeMap& cut,
-			     const IntEdgeMap& capacity) {
+		             const IntEdgeMap& capacity) {
 		  int sum = 0;
 		  for (EdgeIt e(graph); e != INVALID; ++e) {
 		    Node s = graph.u(e);
 		    Node t = graph.v(e);
 		    if (cut[s] != cut[t]) {
 		      sum += capacity[e];
@@ -102,22 +120,22 @@
 		      BoolNodeMap cm(graph);
 		      ght.minCutMap(u, v, cm);
 		      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
 		      check(cm[u] != cm[v], "Wrong cut 2");
 		      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
 		      int sum=0;
 		      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
-		        sum+=capacity[a];
 		        sum+=capacity[a];
 		      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
 		      sum=0;
 		      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
 		        sum++;
 		      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
 		        sum++;
 		      check(sum == countNodes(graph), "Problem with MinCutNodeIt");
+		    }
+		  }
 		  return 0;
+		}

test/graph_copy_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -65,17 +65,17 @@
 		  ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);
 		  ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);
 		  digraphCopy(from, to).
 		    nodeMap(fnm, tnm).arcMap(fam, tam).
 		    nodeRef(nr).arcRef(er).
 		    nodeCrossRef(ncr).arcCrossRef(ecr).
 		    node(fn, tn).arc(fa, ta).run();
 		  check(countNodes(from) == countNodes(to), "Wrong copy.");
 		  check(countArcs(from) == countArcs(to), "Wrong copy.");
 		  for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
 		    check(ncr[nr[it]] == it, "Wrong copy.");
 		    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
+		  }
@@ -93,17 +93,17 @@
 		  for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {
 		    check(er[ecr[it]] == it, "Wrong copy.");
+		  }
 		  check(tn == nr[fn], "Wrong copy.");
 		  check(ta == er[fa], "Wrong copy.");
 		  // Test repeated copy
 		  digraphCopy(from, to).run();
 		  check(countNodes(from) == countNodes(to), "Wrong copy.");
 		  check(countArcs(from) == countArcs(to), "Wrong copy.");
+		}
 		void graph_copy_test() {
 		  const int nn = 10;
 		  // Build a graph
@@ -195,17 +195,17 @@
 		    check(er[ecr[it]] == it, "Wrong copy.");
+		  }
 		  check(tn == nr[fn], "Wrong copy.");
 		  check(ta == ar[fa], "Wrong copy.");
 		  check(te == er[fe], "Wrong copy.");
 		  // Test repeated copy
 		  graphCopy(from, to).run();
 		  check(countNodes(from) == countNodes(to), "Wrong copy.");
 		  check(countEdges(from) == countEdges(to), "Wrong copy.");
 		  check(countArcs(from) == countArcs(to), "Wrong copy.");
+		}
 		int main() {
 		  digraph_copy_test();

test/hao_orlin_test.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
 * Copyright (C) 2003-2011
 * 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,
@@ -78,17 +78,17 @@
  ho_test.run();
  ho_test.run(n);

  v = const_ho_test.minCutValue();
  v = const_ho_test.minCutMap(cut);
}

template <typename Graph, typename CapMap, typename CutMap>
typename CapMap::Value 
typename CapMap::Value
  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
{
  typename CapMap::Value sum = 0;
  for (typename Graph::ArcIt a(graph); a != INVALID; ++a) {
    if (cut[graph.source(a)] && !cut[graph.target(a)])
      sum += cap[a];
  }
  return sum;
@@ -105,59 +105,59 @@
    .arcMap("cap2", cap2)
    .arcMap("cap3", cap3)
    .run();

  {
    HaoOrlin<SmartDigraph> ho(graph, cap1);
    ho.run();
    ho.minCutMap(cut);
    

    check(ho.minCutValue() == 1, "Wrong cut value");
    check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
  }
  {
    HaoOrlin<SmartDigraph> ho(graph, cap2);
    ho.run();
    ho.minCutMap(cut);

    check(ho.minCutValue() == 1, "Wrong cut value");
    check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
  }
  {
    HaoOrlin<SmartDigraph> ho(graph, cap3);
    ho.run();
    ho.minCutMap(cut);
    

    check(ho.minCutValue() == 1, "Wrong cut value");
    check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
  }
  

  typedef Undirector<SmartDigraph> UGraph;
  UGraph ugraph(graph);
  

  {
    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
    ho.run();
    ho.minCutMap(cut);
    

    check(ho.minCutValue() == 2, "Wrong cut value");
    check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
  }
  {
    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2);
    ho.run();
    ho.minCutMap(cut);
    

    check(ho.minCutValue() == 5, "Wrong cut value");
    check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
  }
  {
    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3);
    ho.run();
    ho.minCutMap(cut);
    

    check(ho.minCutValue() == 5, "Wrong cut value");
    check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
  }

  return 0;
}

test/heap_test.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
 * Copyright (C) 2003-2011
 * 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,

test/lgf_test.cc

Show inline comments

@@ -58,20 +58,20 @@
  "label\n"
  "0\n"
  "1\n"
  "@arcs\n"
  "     label -\n"
  "0 1\n";


int main() 
int main()
{
  {
    ListDigraph d; 
    ListDigraph d;
    ListDigraph::Node s,t;
    ListDigraph::ArcMap<int> label(d);
    std::istringstream input(test_lgf);
    digraphReader(d, input).
      node("source", s).
      node("target", t).
      arcMap("label", label).
      run();
@@ -88,41 +88,41 @@
      node("target", t).
      edgeMap("label", label).
      run();
    check(countNodes(g) == 2,"There should be 2 nodes");
    check(countEdges(g) == 2,"There should be 2 arcs");
  }

  {
    ListDigraph d; 
    ListDigraph d;
    std::istringstream input(test_lgf_nomap);
    digraphReader(d, input).
      run();
    check(countNodes(d) == 2,"There should be 2 nodes");
    check(countArcs(d) == 1,"There should be 1 arc");
  }
  {
    ListGraph g;
    std::istringstream input(test_lgf_nomap);
    graphReader(g, input).
      run();
    check(countNodes(g) == 2,"There should be 2 nodes");
    check(countEdges(g) == 1,"There should be 1 edge");
  }

  {
    ListDigraph d; 
    ListDigraph d;
    std::istringstream input(test_lgf_bad1);
    bool ok=false;
    try {
      digraphReader(d, input).
        run();
    }
    catch (FormatError& error) 
    catch (FormatError& error)
      {
        ok = true;
      }
    check(ok,"FormatError exception should have occured");
  }
  {
    ListGraph g;
    std::istringstream input(test_lgf_bad1);
@@ -134,17 +134,17 @@
    catch (FormatError& error)
      {
        ok = true;
      }
    check(ok,"FormatError exception should have occured");
  }

  {
    ListDigraph d; 
    ListDigraph d;
    std::istringstream input(test_lgf_bad2);
    bool ok=false;
    try {
      digraphReader(d, input).
        run();
    }
    catch (FormatError& error)
      {

test/maps_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -65,18 +65,20 @@
+		{
 		  // Map concepts
 		  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
 		  checkConcept<ReadMap<A,C>, ReadMap<A,C> >();
 		  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
 		  checkConcept<WriteMap<A,C>, WriteMap<A,C> >();
 		  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
 		  checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();
 		  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
 		  checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >();
 		  checkConcept<ReferenceMap<A,B,B&,const B&>,
 		               ReferenceMap<A,B,B&,const B&> >();
 		  checkConcept<ReferenceMap<A,C,C&,const C&>,
 		               ReferenceMap<A,C,C&,const C&> >();
 		  // NullMap
+		  {
 		    checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >();
 		    NullMap<A,B> map1;
 		    NullMap<A,B> map2 = map1;
 		    map1 = nullMap<A,B>();
+		  }
@@ -195,17 +197,18 @@
+		  {
 		    checkConcept<ReadMap<A,B>, FunctorToMap<F,A,B> >();
 		    checkConcept<ReadMap<A,B>, FunctorToMap<F> >();
 		    FunctorToMap<F> map1;
 		    FunctorToMap<F> map2 = FunctorToMap<F>(F());
 		    B b = functorToMap(F())[A()];
 		    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
-		    MapToFunctor<ReadMap<A,B> > map = MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
 		    MapToFunctor<ReadMap<A,B> > map =
 		      MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
 		    check(functorToMap(&func)[A()] == 3,
 		          "Something is wrong with FunctorToMap");
 		    check(mapToFunctor(constMap<A,int>(2))(A()) == 2,
 		          "Something is wrong with MapToFunctor");
 		    check(mapToFunctor(functorToMap(&func))(A()) == 3 &&
 		          mapToFunctor(functorToMap(&func))[A()] == 3,
 		          "Something is wrong with FunctorToMap or MapToFunctor");
@@ -344,34 +347,34 @@
 		          v2[0]==20 && v2[1]==50 && v2[2]==60,
 		          "Something is wrong with LoggerBoolMap");
 		    int i = 0;
 		    for ( LoggerBoolMap<vec::iterator>::Iterator it = map2.begin();
 		          it != map2.end(); ++it )
 		      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
+		  }
 		  // CrossRefMap
+		  {
 		    typedef ListDigraph Graph;
 		    DIGRAPH_TYPEDEFS(Graph);
 		    checkConcept<ReadWriteMap<Node, int>,
 		                 CrossRefMap<Graph, Node, int> >();
 		    Graph gr;
 		    typedef CrossRefMap<Graph, Node, char> CRMap;
 		    typedef CRMap::ValueIterator ValueIt;
 		    CRMap map(gr);
 		    Node n0 = gr.addNode();
 		    Node n1 = gr.addNode();
 		    Node n2 = gr.addNode();
 		    map.set(n0, 'A');
 		    map.set(n1, 'B');
 		    map.set(n2, 'C');
 		    map.set(n2, 'A');
 		    map.set(n0, 'C');
 		    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
 		          "Wrong CrossRefMap");

test/matching_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -129,26 +129,26 @@
 		    const_mat_test = mat_test;
 		  mat_test.init();
 		  mat_test.greedyInit();
 		  mat_test.matchingInit(mat);
 		  mat_test.startSparse();
 		  mat_test.startDense();
 		  mat_test.run();
 		  const_mat_test.matchingSize();
 		  const_mat_test.matching(e);
 		  const_mat_test.matching(n);
 		  const MaxMatching<Graph>::MatchingMap& mmap =
 		    const_mat_test.matchingMap();
 		  e = mmap[n];
 		  const_mat_test.mate(n);
-		  MaxMatching<Graph>::Status stat =
 		  MaxMatching<Graph>::Status stat =
 		    const_mat_test.status(n);
 		  const MaxMatching<Graph>::StatusMap& smap =
 		    const_mat_test.statusMap();
 		  stat = smap[n];
 		  const_mat_test.barrier(n);
+		}
 		void checkMaxWeightedMatchingCompile()
@@ -165,26 +165,26 @@
 		  MaxWeightedMatching<Graph> mat_test(g, w);
 		  const MaxWeightedMatching<Graph>&
 		    const_mat_test = mat_test;
 		  mat_test.init();
 		  mat_test.start();
 		  mat_test.run();
 		  const_mat_test.matchingWeight();
 		  const_mat_test.matchingSize();
 		  const_mat_test.matching(e);
 		  const_mat_test.matching(n);
 		  const MaxWeightedMatching<Graph>::MatchingMap& mmap =
 		    const_mat_test.matchingMap();
 		  e = mmap[n];
 		  const_mat_test.mate(n);
 		  int k = 0;
 		  const_mat_test.dualValue();
 		  const_mat_test.nodeValue(n);
 		  const_mat_test.blossomNum();
 		  const_mat_test.blossomSize(k);
 		  const_mat_test.blossomValue(k);
+		}
@@ -202,25 +202,25 @@
 		  MaxWeightedPerfectMatching<Graph> mat_test(g, w);
 		  const MaxWeightedPerfectMatching<Graph>&
 		    const_mat_test = mat_test;
 		  mat_test.init();
 		  mat_test.start();
 		  mat_test.run();
 		  const_mat_test.matchingWeight();
 		  const_mat_test.matching(e);
 		  const_mat_test.matching(n);
 		  const MaxWeightedPerfectMatching<Graph>::MatchingMap& mmap =
 		    const_mat_test.matchingMap();
 		  e = mmap[n];
 		  const_mat_test.mate(n);
 		  int k = 0;
 		  const_mat_test.dualValue();
 		  const_mat_test.nodeValue(n);
 		  const_mat_test.blossomNum();
 		  const_mat_test.blossomSize(k);
 		  const_mat_test.blossomValue(k);
+		}

test/min_cost_arborescence_test.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-2008
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -105,32 +105,32 @@
 		    .run(s);
 		  mcarb_test.init();
 		  mcarb_test.addSource(s);
 		  mcarb_test.start();
 		  n = mcarb_test.processNextNode();
 		  b = const_mcarb_test.emptyQueue();
 		  i = const_mcarb_test.queueSize();
 		  c = const_mcarb_test.arborescenceCost();
 		  b = const_mcarb_test.arborescence(e);
 		  e = const_mcarb_test.pred(n);
 		  const MinCostArbType::ArborescenceMap &am =
 		    const_mcarb_test.arborescenceMap();
 		  const MinCostArbType::PredMap &pm =
 		    const_mcarb_test.predMap();
 		  b = const_mcarb_test.reached(n);
 		  b = const_mcarb_test.processed(n);
 		  i = const_mcarb_test.dualNum();
 		  c = const_mcarb_test.dualValue();
 		  i = const_mcarb_test.dualSize(i);
 		  c = const_mcarb_test.dualValue(i);
 		  ignore_unused_variable_warning(am);
 		  ignore_unused_variable_warning(pm);
+		}
 		int main() {
 		  typedef SmartDigraph Digraph;
 		  DIGRAPH_TYPEDEFS(Digraph);

test/min_cost_flow_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -42,17 +42,17 @@
 		  "    5     9    0    0    0    6   11\n"
 		  "    6    -6    0    0    0   -5   -6\n"
 		  "    7     0    0    0    0    0    0\n"
 		  "    8     0    0    0    0    0    3\n"
 		  "    9     3    0    0    0    0    0\n"
 		  "   10    -2    0    0    0   -7   -2\n"
 		  "   11     0    0    0    0  -10    0\n"
 		  "   12   -20  -27    0  -30  -30  -20\n"
-		  "\n"
 		  "\n"
 		  "@arcs\n"
 		  "       cost  cap low1 low2 low3\n"
 		  " 1  2    70   11    0    8    8\n"
 		  " 1  3   150    3    0    1    0\n"
 		  " 1  4    80   15    0    2    2\n"
 		  " 2  8    80   12    0    0    0\n"
 		  " 3  5   140    5    0    3    1\n"
 		  " 4  6    60   10    0    1    0\n"
@@ -88,17 +88,17 @@
 		class McfClassConcept
+		{
 		public:
 		  template <typename MCF>
 		  struct Constraints {
 		    void constraints() {
 		      checkConcept<concepts::Digraph, GR>();
 		      const Constraints& me = *this;
 		      MCF mcf(me.g);
 		      const MCF& const_mcf = mcf;
 		      b = mcf.reset()
 		             .lowerMap(me.lower)
 		             .upperMap(me.upper)
@@ -117,17 +117,17 @@
 		    typedef typename GR::Node Node;
 		    typedef typename GR::Arc Arc;
 		    typedef concepts::ReadMap<Node, Value> NM;
 		    typedef concepts::ReadMap<Arc, Value> VAM;
 		    typedef concepts::ReadMap<Arc, Cost> CAM;
 		    typedef concepts::WriteMap<Arc, Value> FlowMap;
 		    typedef concepts::WriteMap<Node, Cost> PotMap;
 		    GR g;
 		    VAM lower;
 		    VAM upper;
 		    CAM cost;
 		    NM sup;
 		    Node n;
 		    Arc a;
 		    Value k;
@@ -171,43 +171,43 @@
 		  return true;
+		}
 		// Check the feasibility of the given potentials (dual soluiton)
 		// using the "Complementary Slackness" optimality condition
 		template < typename GR, typename LM, typename UM,
 		           typename CM, typename SM, typename FM, typename PM >
 		bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
-		                     const CM& cost, const SM& supply, const FM& flow,
 		                     const CM& cost, const SM& supply, const FM& flow,
 		                     const PM& pi, SupplyType type )
+		{
 		  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		  bool opt = true;
 		  for (ArcIt e(gr); opt && e != INVALID; ++e) {
 		    typename CM::Value red_cost =
 		      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
 		    opt = red_cost == 0 ||
 		          (red_cost > 0 && flow[e] == lower[e]) ||
 		          (red_cost < 0 && flow[e] == upper[e]);
+		  }
 		  for (NodeIt n(gr); opt && n != INVALID; ++n) {
 		    typename SM::Value sum = 0;
 		    for (OutArcIt e(gr, n); e != INVALID; ++e)
 		      sum += flow[e];
 		    for (InArcIt e(gr, n); e != INVALID; ++e)
 		      sum -= flow[e];
 		    if (type != LEQ) {
 		      opt = (pi[n] <= 0) && (sum == supply[n] || pi[n] == 0);
 		    } else {
 		      opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0);
+		    }
+		  }
 		  return opt;
+		}
 		// Check whether the dual cost is equal to the primal cost
 		template < typename GR, typename LM, typename UM,
 		           typename CM, typename SM, typename PM >
 		bool checkDualCost( const GR& gr, const LM& lower, const UM& upper,
 		                    const CM& cost, const SM& supply, const PM& pi,
@@ -222,26 +222,26 @@
+		  }
 		  for (ArcIt a(gr); a != INVALID; ++a) {
 		    if (lower[a] != 0) {
 		      dual_cost += lower[a] * cost[a];
 		      red_supply[gr.source(a)] -= lower[a];
 		      red_supply[gr.target(a)] += lower[a];
+		    }
+		  }
 		  for (NodeIt n(gr); n != INVALID; ++n) {
 		    dual_cost -= red_supply[n] * pi[n];
+		  }
 		  for (ArcIt a(gr); a != INVALID; ++a) {
 		    typename CM::Value red_cost =
 		      cost[a] + pi[gr.source(a)] - pi[gr.target(a)];
 		    dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0);
+		  }
 		  return dual_cost == total;
+		}
 		// Run a minimum cost flow algorithm and check the results
 		template < typename MCF, typename GR,
 		           typename LM, typename UM,
 		           typename CM, typename SM,
 		           typename PT >
@@ -303,47 +303,47 @@
 		    .nodeMap("sup2", s2)
 		    .nodeMap("sup3", s3)
 		    .nodeMap("sup4", s4)
 		    .nodeMap("sup5", s5)
 		    .nodeMap("sup6", s6)
 		    .node("source", v)
 		    .node("target", w)
 		    .run();
 		  // Build test digraphs with negative costs
 		  Digraph neg_gr;
 		  Node n1 = neg_gr.addNode();
 		  Node n2 = neg_gr.addNode();
 		  Node n3 = neg_gr.addNode();
 		  Node n4 = neg_gr.addNode();
 		  Node n5 = neg_gr.addNode();
 		  Node n6 = neg_gr.addNode();
 		  Node n7 = neg_gr.addNode();
 		  Arc a1 = neg_gr.addArc(n1, n2);
 		  Arc a2 = neg_gr.addArc(n1, n3);
 		  Arc a3 = neg_gr.addArc(n2, n4);
 		  Arc a4 = neg_gr.addArc(n3, n4);
 		  Arc a5 = neg_gr.addArc(n3, n2);
 		  Arc a6 = neg_gr.addArc(n5, n3);
 		  Arc a7 = neg_gr.addArc(n5, n6);
 		  Arc a8 = neg_gr.addArc(n6, n7);
 		  Arc a9 = neg_gr.addArc(n7, n5);
 		  Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
 		  ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
 		  Digraph::NodeMap<int> neg_s(neg_gr, 0);
 		  neg_l2[a7] =  1000;
 		  neg_l2[a8] = -1000;
 		  neg_s[n1] =  100;
 		  neg_s[n4] = -100;
 		  neg_c[a1] =  100;
 		  neg_c[a2] =   30;
 		  neg_c[a3] =   20;
 		  neg_c[a4] =   80;
 		  neg_c[a5] =   50;
 		  neg_c[a6] =   10;
 		  neg_c[a7] =   80;
 		  neg_c[a8] =   30;
@@ -417,17 +417,17 @@
 		    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1,
 		      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A16");
 		    neg_mcf.upperMap(neg_u2);
 		    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2,
 		      neg_c, neg_s, neg_mcf.OPTIMAL, true,  -40000, "#A17");
 		    neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);
 		    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
 		      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A18");
 		    NetworkSimplex<Digraph> negs_mcf(negs_gr);
 		    negs_mcf.costMap(negs_c).supplyMap(negs_s);
 		    checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,
 		      negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ);
+		  }
 		  // B. Test NetworkSimplex with each pivot rule
+		  {

test/preflow_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -108,17 +108,17 @@
 		  preflow_test.run();
 		  preflow_test.runMinCut();
 		  v = const_preflow_test.flowValue();
 		  v = const_preflow_test.flow(e);
 		  const FlowMap& fm = const_preflow_test.flowMap();
 		  b = const_preflow_test.minCut(n);
 		  const_preflow_test.minCutMap(cut);
 		  ignore_unused_variable_warning(fm);
+		}
 		int cutValue (const SmartDigraph& g,
 		              const SmartDigraph::NodeMap<bool>& cut,
 		              const SmartDigraph::ArcMap<int>& cap) {
 		  int c=0;
@@ -149,17 +149,17 @@
 		    if (sum != 0) return false;
+		  }
 		  return true;
+		}
 		void initFlowTest()
+		{
 		  DIGRAPH_TYPEDEFS(SmartDigraph);
 		  SmartDigraph g;
 		  SmartDigraph::ArcMap<int> cap(g),iflow(g);
 		  Node s=g.addNode(); Node t=g.addNode();
 		  Node n1=g.addNode(); Node n2=g.addNode();
 		  Arc a;
 		  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
 		  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
 		  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
@@ -261,11 +261,11 @@
 		  preflow_test.minCutMap(min_cut3);
 		  min_cut_value=cutValue(g,min_cut3,cap);
 		  check(preflow_test.flowValue() == min_cut_value,
 		        "The max flow value or the three min cut values are incorrect.");
 		  initFlowTest();
 		  return 0;
+		}

test/suurballe_test.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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -75,17 +75,17 @@
 		void checkSuurballeCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::Arc Arc;
 		  typedef concepts::ReadMap<Arc, VType> LengthMap;
 		  typedef Suurballe<Digraph, LengthMap> SuurballeType;
 		  Digraph g;
 		  Node n;
 		  Arc e;
 		  LengthMap len;
 		  SuurballeType::FlowMap flow(g);
 		  SuurballeType::PotentialMap pi(g);
@@ -99,29 +99,29 @@
 		  int k;
 		  k = suurb_test.run(n, n);
 		  k = suurb_test.run(n, n, k);
 		  suurb_test.init(n);
 		  k = suurb_test.findFlow(n);
 		  k = suurb_test.findFlow(n, k);
 		  suurb_test.findPaths();
 		  int f;
 		  VType c;
 		  c = const_suurb_test.totalLength();
 		  f = const_suurb_test.flow(e);
 		  const SuurballeType::FlowMap& fm =
 		    const_suurb_test.flowMap();
 		  c = const_suurb_test.potential(n);
 		  const SuurballeType::PotentialMap& pm =
 		    const_suurb_test.potentialMap();
 		  k = const_suurb_test.pathNum();
 		  Path<Digraph> p = const_suurb_test.path(k);
 		  ignore_unused_variable_warning(fm);
 		  ignore_unused_variable_warning(pm);
+		}
 		// Check the feasibility of the flow
 		template <typename Digraph, typename FlowMap>
 		bool checkFlow( const Digraph& gr, const FlowMap& flow,
 		                typename Digraph::Node s, typename Digraph::Node t,

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
+		 * Copyright (C) 2003-2011
 		 * 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,
@@ -83,17 +83,17 @@
 		  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';
 		  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
+		}
 		template<class Value>
 		void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
 		               Value infty, DimacsDescriptor &desc)
+		{
 		  bool report = !ap.given("q");
 		  Digraph g;
@@ -142,17 +142,17 @@
 		  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';
 		                       << 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"]));
@@ -160,17 +160,17 @@
 		  iss >> infty;
 		  if(iss.fail())
+		    {
 		      std::cerr << "Cannot interpret '"
 		                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
 		                << std::endl;
 		      exit(1);
+		    }
 		  switch(desc.type)
+		    {
 		    case DimacsDescriptor::MIN:
 		      solve_min<Value>(ap,is,os,infty,desc);
 		      break;
 		    case DimacsDescriptor::MAX:
 		      solve_max<Value>(ap,is,os,infty,desc);
 		      break;
@@ -232,17 +232,17 @@
 		    default:
 		      std::cerr << ap.commandName() << ": too many arguments\n";
 		      return 1;
+		    }
 		  std::istream& is = (ap.files().size()<1 ? std::cin : input);
 		  std::ostream& os = (ap.files().size()<2 ? std::cout : output);
 		  DimacsDescriptor desc = dimacsType(is);
 		  if(!ap.given("q"))
+		    {
 		      std::cout << "Problem type: ";
 		      switch(desc.type)
+		        {
 		        case DimacsDescriptor::MIN:
 		          std::cout << "min";
 		          break;
@@ -257,17 +257,17 @@
 		        default:
 		          exit(1);
 		          break;
+		        }
 		      std::cout << "\nNum of nodes: " << desc.nodeNum;
 		      std::cout << "\nNum of arcs:  " << desc.edgeNum;
 		      std::cout << "\n\n";
+		    }
 		  if(ap.given("double"))
 		    solve<double>(ap,is,os,desc);
 		  else if(ap.given("ldouble"))
 		    solve<long double>(ap,is,os,desc);
 		#ifdef LEMON_HAVE_LONG_LONG
 		  else if(ap.given("long"))
 		    solve<long long>(ap,is,os,desc);
 		#endif

RhodeCode

Login to your account

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-~~2009~~
	5	* Copyright (C) 2003-2011
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-~~2008~~
	5	* Copyright (C) 2003-2011
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,

...	...	@@ -58,20 +58,20 @@
58	58	"label\n"
59	59	"0\n"
60	60	"1\n"
61	61	"@arcs\n"
62	62	" label -\n"
63	63	"0 1\n";
64	64
65	65
66		int main()
	66	int main()
67	67	{
68	68	{
69		ListDigraph d;
	69	ListDigraph d;
70	70	ListDigraph::Node s,t;
71	71	ListDigraph::ArcMap<int> label(d);
72	72	std::istringstream input(test_lgf);
73	73	digraphReader(d, input).
74	74	node("source", s).
75	75	node("target", t).
76	76	arcMap("label", label).
77	77	run();
...	...	@@ -88,41 +88,41 @@
88	88	node("target", t).
89	89	edgeMap("label", label).
90	90	run();
91	91	check(countNodes(g) == 2,"There should be 2 nodes");
92	92	check(countEdges(g) == 2,"There should be 2 arcs");
93	93	}
94	94
95	95	{
96		ListDigraph d;
	96	ListDigraph d;
97	97	std::istringstream input(test_lgf_nomap);
98	98	digraphReader(d, input).
99	99	run();
100	100	check(countNodes(d) == 2,"There should be 2 nodes");
101	101	check(countArcs(d) == 1,"There should be 1 arc");
102	102	}
103	103	{
104	104	ListGraph g;
105	105	std::istringstream input(test_lgf_nomap);
106	106	graphReader(g, input).
107	107	run();
108	108	check(countNodes(g) == 2,"There should be 2 nodes");
109	109	check(countEdges(g) == 1,"There should be 1 edge");
110	110	}
111	111
112	112	{
113		ListDigraph d;
	113	ListDigraph d;
114	114	std::istringstream input(test_lgf_bad1);
115	115	bool ok=false;
116	116	try {
117	117	digraphReader(d, input).
118	118	run();
119	119	}
120		catch (FormatError& error)
	120	catch (FormatError& error)
121	121	{
122	122	ok = true;
123	123	}
124	124	check(ok,"FormatError exception should have occured");
125	125	}
126	126	{
127	127	ListGraph g;
128	128	std::istringstream input(test_lgf_bad1);
...	...	@@ -134,17 +134,17 @@
134	134	catch (FormatError& error)
135	135	{
136	136	ok = true;
137	137	}
138	138	check(ok,"FormatError exception should have occured");
139	139	}
140	140
141	141	{
142		ListDigraph d;
	142	ListDigraph d;
143	143	std::istringstream input(test_lgf_bad2);
144	144	bool ok=false;
145	145	try {
146	146	digraphReader(d, input).
147	147	run();
148	148	}
149	149	catch (FormatError& error)
150	150	{