LEMON/LEMON-official Changeset - r566:c786cd201266

Repositories » LEMON » LEMON-official

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

Changeset - r566:c786cd201266

« 565:8668e1

567:42d4b8 »

r566:c786cd201266

Mon, 23 Feb 2009 11:58:39

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Fix several missing includes (#232)

0 7 0

default

7 files changed with 12 insertions and 0 deletions:

lemon/adaptors.h

lemon/bits/edge_set_extender.h

lemon/bits/path_dump.h

lemon/bits/solver_bits.h

lemon/concepts/heap.h

lemon/elevator.h

lemon/suurballe.h

↑ Collapse diff ↑

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
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_ADAPTORS_H
 		#define LEMON_ADAPTORS_H
 		/// \ingroup graph_adaptors
 		/// \file
 		/// \brief Adaptor classes for digraphs and graphs
 		///
 		/// This file contains several useful adaptors for digraphs and graphs.
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/bits/variant.h>
 		#include <lemon/bits/graph_adaptor_extender.h>
 		#include <lemon/bits/map_extender.h>
 		#include <lemon/tolerance.h>
 		#include <algorithm>
 		namespace lemon {
 		#ifdef _MSC_VER
 		#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED
 		#else
 		#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED
 		#endif
 		  template<typename DGR>
 		  class DigraphAdaptorBase {
 		  public:
 		    typedef DGR Digraph;
 		    typedef DigraphAdaptorBase Adaptor;
 		  protected:
 		    DGR* _digraph;
 		    DigraphAdaptorBase() : _digraph(0) { }
 		    void initialize(DGR& digraph) { _digraph = &digraph; }
 		  public:
 		    DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }
 		    typedef typename DGR::Node Node;
 		    typedef typename DGR::Arc Arc;
 		    void first(Node& i) const { _digraph->first(i); }
 		    void first(Arc& i) const { _digraph->first(i); }
 		    void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
 		    void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
 		    void next(Node& i) const { _digraph->next(i); }
 		    void next(Arc& i) const { _digraph->next(i); }
 		    void nextIn(Arc& i) const { _digraph->nextIn(i); }
 		    void nextOut(Arc& i) const { _digraph->nextOut(i); }
 		    Node source(const Arc& a) const { return _digraph->source(a); }
 		    Node target(const Arc& a) const { return _digraph->target(a); }
 		    typedef NodeNumTagIndicator<DGR> NodeNumTag;
 		    int nodeNum() const { return _digraph->nodeNum(); }
 		    typedef ArcNumTagIndicator<DGR> ArcNumTag;
 		    int arcNum() const { return _digraph->arcNum(); }
 		    typedef FindArcTagIndicator<DGR> FindArcTag;
 		    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
 		      return _digraph->findArc(u, v, prev);
+		    }
 		    Node addNode() { return _digraph->addNode(); }
 		    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
 		    void erase(const Node& n) { _digraph->erase(n); }
 		    void erase(const Arc& a) { _digraph->erase(a); }
 		    void clear() { _digraph->clear(); }
 		    int id(const Node& n) const { return _digraph->id(n); }
 		    int id(const Arc& a) const { return _digraph->id(a); }
 		    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
 		    int maxNodeId() const { return _digraph->maxNodeId(); }
 		    int maxArcId() const { return _digraph->maxArcId(); }
 		    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
 		    typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
 		    template <typename V>
 		    class NodeMap : public DGR::template NodeMap<V> {
 		    public:
 		      typedef typename DGR::template NodeMap<V> Parent;
 		      explicit NodeMap(const Adaptor& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      NodeMap(const Adaptor& adaptor, const V& value)
 		        : Parent(*adaptor._digraph, value) { }
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap : public DGR::template ArcMap<V> {
 		    public:
 		      typedef typename DGR::template ArcMap<V> Parent;
 		      explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
 		        : Parent(*adaptor._digraph, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template<typename GR>
 		  class GraphAdaptorBase {
 		  public:
 		    typedef GR Graph;
 		  protected:
 		    GR* _graph;
 		    GraphAdaptorBase() : _graph(0) {}
 		    void initialize(GR& graph) { _graph = &graph; }
 		  public:
 		    GraphAdaptorBase(GR& graph) : _graph(&graph) {}
 		    typedef typename GR::Node Node;
 		    typedef typename GR::Arc Arc;
 		    typedef typename GR::Edge Edge;
 		    void first(Node& i) const { _graph->first(i); }
 		    void first(Arc& i) const { _graph->first(i); }
 		    void first(Edge& i) const { _graph->first(i); }
 		    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
 		    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
 		    void firstInc(Edge &i, bool &d, const Node &n) const {
 		      _graph->firstInc(i, d, n);
+		    }
 		    void next(Node& i) const { _graph->next(i); }
 		    void next(Arc& i) const { _graph->next(i); }
 		    void next(Edge& i) const { _graph->next(i); }
 		    void nextIn(Arc& i) const { _graph->nextIn(i); }
 		    void nextOut(Arc& i) const { _graph->nextOut(i); }
 		    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
 		    Node u(const Edge& e) const { return _graph->u(e); }
 		    Node v(const Edge& e) const { return _graph->v(e); }
 		    Node source(const Arc& a) const { return _graph->source(a); }
 		    Node target(const Arc& a) const { return _graph->target(a); }
 		    typedef NodeNumTagIndicator<Graph> NodeNumTag;
 		    int nodeNum() const { return _graph->nodeNum(); }
 		    typedef ArcNumTagIndicator<Graph> ArcNumTag;
 		    int arcNum() const { return _graph->arcNum(); }
 		    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
 		    int edgeNum() const { return _graph->edgeNum(); }
 		    typedef FindArcTagIndicator<Graph> FindArcTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) const {
 		      return _graph->findArc(u, v, prev);
+		    }
 		    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
 		    Edge findEdge(const Node& u, const Node& v,
 		                  const Edge& prev = INVALID) const {
 		      return _graph->findEdge(u, v, prev);
+		    }
 		    Node addNode() { return _graph->addNode(); }
 		    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
 		    void erase(const Node& i) { _graph->erase(i); }
 		    void erase(const Edge& i) { _graph->erase(i); }
 		    void clear() { _graph->clear(); }
 		    bool direction(const Arc& a) const { return _graph->direction(a); }
 		    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
 		    int id(const Node& v) const { return _graph->id(v); }
 		    int id(const Arc& a) const { return _graph->id(a); }
 		    int id(const Edge& e) const { return _graph->id(e); }
 		    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
 		    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
 		    int maxNodeId() const { return _graph->maxNodeId(); }
 		    int maxArcId() const { return _graph->maxArcId(); }
 		    int maxEdgeId() const { return _graph->maxEdgeId(); }
 		    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 		    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 		    typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
 		    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
 		    template <typename V>
 		    class NodeMap : public GR::template NodeMap<V> {
 		    public:
 		      typedef typename GR::template NodeMap<V> Parent;
 		      explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
 		        : Parent(*adapter._graph) {}
 		      NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap : public GR::template ArcMap<V> {
 		    public:
 		      typedef typename GR::template ArcMap<V> Parent;
 		      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
 		        : Parent(*adapter._graph) {}
 		      ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class EdgeMap : public GR::template EdgeMap<V> {
 		    public:
 		      typedef typename GR::template EdgeMap<V> Parent;
 		      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
 		        : Parent(*adapter._graph) {}
 		      EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename DGR>
 		  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
 		  public:
 		    typedef DGR Digraph;
 		    typedef DigraphAdaptorBase<DGR> Parent;
 		  protected:
 		    ReverseDigraphBase() : Parent() { }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
 		    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
 		    void nextIn(Arc& a) const { Parent::nextOut(a); }
 		    void nextOut(Arc& a) const { Parent::nextIn(a); }
 		    Node source(const Arc& a) const { return Parent::target(a); }
 		    Node target(const Arc& a) const { return Parent::source(a); }
 		    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
 		    typedef FindArcTagIndicator<DGR> FindArcTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) const {
 		      return Parent::findArc(v, u, prev);
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for reversing the orientation of the arcs in
 		  /// a digraph.
 		  ///
 		  /// ReverseDigraph can be used for reversing the arcs in a digraph.
 		  /// It conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// The adapted digraph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  ///
 		  /// \note The \c Node and \c Arc types of this adaptor and the adapted
 		  /// digraph are convertible to each other.
 		  template<typename DGR>
 		#ifdef DOXYGEN
 		  class ReverseDigraph {
 		#else
 		  class ReverseDigraph :
 		    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
 		#endif
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
 		  protected:
 		    ReverseDigraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a reverse digraph adaptor for the given digraph.
 		    explicit ReverseDigraph(DGR& digraph) {
 		      Parent::initialize(digraph);
+		    }
 		  };
 		  /// \brief Returns a read-only ReverseDigraph adaptor
 		  ///
 		  /// This function just returns a read-only \ref ReverseDigraph adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates ReverseDigraph
 		  template<typename DGR>
 		  ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
 		    return ReverseDigraph<const DGR>(digraph);
+		  }
 		  template <typename DGR, typename NF, typename AF, bool ch = true>
 		  class SubDigraphBase : public DigraphAdaptorBase<DGR> {
 		  public:
 		    typedef DGR Digraph;
 		    typedef NF NodeFilterMap;
 		    typedef AF ArcFilterMap;
 		    typedef SubDigraphBase Adaptor;
 		    typedef DigraphAdaptorBase<DGR> Parent;
 		  protected:
 		    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;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
 		    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
 		    bool status(const Node& n) const { return (*_node_filter)[n]; }
 		    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
 		    typedef False NodeNumTag;
 		    typedef False ArcNumTag;
 		    typedef FindArcTagIndicator<DGR> FindArcTag;
 		    Arc findArc(const Node& source, const Node& target,
 		                const Arc& prev = INVALID) const {
 		      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(source, target, prev);
 		      while (arc != INVALID && !(*_arc_filter)[arc]) {
 		        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>)> {
 		    public:
 		      typedef V Value;
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
 			    LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
 			      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
 		    public:
 		      typedef V Value;
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename DGR, typename NF, typename AF>
 		  class SubDigraphBase<DGR, NF, AF, false>
 		    : public DigraphAdaptorBase<DGR> {
 		  public:
 		    typedef DGR Digraph;
 		    typedef NF NodeFilterMap;
 		    typedef AF ArcFilterMap;
 		    typedef SubDigraphBase Adaptor;
 		    typedef DigraphAdaptorBase<Digraph> Parent;
 		  protected:
 		    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;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
+		    }
 		    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
 		    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
 		    bool status(const Node& n) const { return (*_node_filter)[n]; }
 		    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
 		    typedef False NodeNumTag;
 		    typedef False ArcNumTag;
 		    typedef FindArcTagIndicator<DGR> FindArcTag;
 		    Arc findArc(const Node& source, const Node& target,
 		                const Arc& prev = INVALID) const {
 		      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
 		        return INVALID;
+		      }
 		      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
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
 		    public:
 		      typedef V Value;
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
 		    public:
 		      typedef V Value;
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for hiding nodes and arcs in a digraph
 		  ///
 		  /// SubDigraph can be used for hiding nodes and arcs in a digraph.
 		  /// A \c bool node map and a \c bool arc map must be specified, which
 		  /// define the filters for nodes and arcs.
 		  /// Only the nodes and arcs with \c true filter value are
 		  /// shown in the subdigraph. The arcs that are incident to hidden
 		  /// nodes are also filtered out.
 		  /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// The adapted digraph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam NF The type of the node filter map.
 		  /// It must be a \c bool (or convertible) node map of the
 		  /// adapted digraph. The default type is
 		  /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".
 		  /// \tparam AF The type of the arc filter map.
 		  /// It must be \c bool (or convertible) arc map of the
 		  /// adapted digraph. The default type is
 		  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
 		  ///
 		  /// \note The \c Node and \c Arc types of this adaptor and the adapted
 		  /// digraph are convertible to each other.
 		  ///
 		  /// \see FilterNodes
 		  /// \see FilterArcs
 		#ifdef DOXYGEN
 		  template<typename DGR, typename NF, typename AF>
 		  class SubDigraph {
 		#else
 		  template<typename DGR,
 		           typename NF = typename DGR::template NodeMap<bool>,
 		           typename AF = typename DGR::template ArcMap<bool> >
 		  class SubDigraph :
 		    public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > {
 		#endif
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		    /// The type of the node filter map.
 		    typedef NF NodeFilterMap;
 		    /// The type of the arc filter map.
 		    typedef AF ArcFilterMap;
 		    typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> >
 		      Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    SubDigraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subdigraph for the given digraph with the
 		    /// given node and arc filter maps.
 		    SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {
 		      Parent::initialize(digraph, node_filter, arc_filter);
+		    }
 		    /// \brief Sets the status of the given node
 		    ///
 		    /// This function sets the status of the given node.
 		    /// It is done by simply setting the assigned value of \c n
 		    /// to \c v in the node filter map.
 		    void status(const Node& n, bool v) const { Parent::status(n, v); }
 		    /// \brief Sets the status of the given arc
 		    ///
 		    /// This function sets the status of the given arc.
 		    /// It is done by simply setting the assigned value of \c a
 		    /// to \c v in the arc filter map.
 		    void status(const Arc& a, bool v) const { Parent::status(a, v); }
 		    /// \brief Returns the status of the given node
 		    ///
 		    /// This function returns the status of the given node.
 		    /// It is \c true if the given node is enabled (i.e. not hidden).
 		    bool status(const Node& n) const { return Parent::status(n); }
 		    /// \brief Returns the status of the given arc
 		    ///
 		    /// This function returns the status of the given arc.
 		    /// It is \c true if the given arc is enabled (i.e. not hidden).
 		    bool status(const Arc& a) const { return Parent::status(a); }
 		    /// \brief Disables the given node
 		    ///
 		    /// This function disables the given node in the subdigraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(n, false)".
 		    void disable(const Node& n) const { Parent::status(n, false); }
 		    /// \brief Disables the given arc
 		    ///
 		    /// This function disables the given arc in the subdigraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(a, false)".
 		    void disable(const Arc& a) const { Parent::status(a, false); }
 		    /// \brief Enables the given node
 		    ///
 		    /// This function enables the given node in the subdigraph.
 		    /// It is the same as \ref status() "status(n, true)".
 		    void enable(const Node& n) const { Parent::status(n, true); }
 		    /// \brief Enables the given arc
 		    ///
 		    /// This function enables the given arc in the subdigraph.
 		    /// It is the same as \ref status() "status(a, true)".
 		    void enable(const Arc& a) const { Parent::status(a, true); }
 		  };
 		  /// \brief Returns a read-only SubDigraph adaptor
 		  ///
 		  /// This function just returns a read-only \ref SubDigraph adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates SubDigraph
 		  template<typename DGR, typename NF, typename AF>
 		  SubDigraph<const DGR, NF, AF>
 		  subDigraph(const DGR& digraph,
 		             NF& node_filter, AF& arc_filter) {
 		    return SubDigraph<const DGR, NF, AF>
 		      (digraph, node_filter, arc_filter);
+		  }
 		  template<typename DGR, typename NF, typename AF>
 		  SubDigraph<const DGR, const NF, AF>
 		  subDigraph(const DGR& digraph,
 		             const NF& node_filter, AF& arc_filter) {
 		    return SubDigraph<const DGR, const NF, AF>
 		      (digraph, node_filter, arc_filter);
+		  }
 		  template<typename DGR, typename NF, typename AF>
 		  SubDigraph<const DGR, NF, const AF>
 		  subDigraph(const DGR& digraph,
 		             NF& node_filter, const AF& arc_filter) {
 		    return SubDigraph<const DGR, NF, const AF>
 		      (digraph, node_filter, arc_filter);
+		  }
 		  template<typename DGR, typename NF, typename AF>
 		  SubDigraph<const DGR, const NF, const AF>
 		  subDigraph(const DGR& digraph,
 		             const NF& node_filter, const AF& arc_filter) {
 		    return SubDigraph<const DGR, const NF, const AF>
 		      (digraph, node_filter, arc_filter);
+		  }
 		  template <typename GR, typename NF, typename EF, bool ch = true>
 		  class SubGraphBase : public GraphAdaptorBase<GR> {
 		  public:
 		    typedef GR Graph;
 		    typedef NF NodeFilterMap;
 		    typedef EF EdgeFilterMap;
 		    typedef SubGraphBase Adaptor;
 		    typedef GraphAdaptorBase<GR> Parent;
 		  protected:
 		    NF* _node_filter;
 		    EF* _edge_filter;
 		    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:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::source(i)]
 		                            || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void first(Edge& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::u(i)]
 		                            || !(*_node_filter)[Parent::v(i)]))
 		        Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void firstInc(Edge& i, bool& d, const Node& n) const {
 		      Parent::firstInc(i, d, n);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::u(i)]
 		                            || !(*_node_filter)[Parent::v(i)]))
 		        Parent::nextInc(i, d);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::source(i)]
 		                            || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void next(Edge& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::u(i)]
 		                            || !(*_node_filter)[Parent::v(i)]))
 		        Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void nextInc(Edge& i, bool& d) const {
 		      Parent::nextInc(i, d);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::u(i)]
 		                            || !(*_node_filter)[Parent::v(i)]))
 		        Parent::nextInc(i, d);
+		    }
 		    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
 		    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
 		    bool status(const Node& n) const { return (*_node_filter)[n]; }
 		    bool status(const Edge& e) const { return (*_edge_filter)[e]; }
 		    typedef False NodeNumTag;
 		    typedef False ArcNumTag;
 		    typedef False EdgeNumTag;
 		    typedef FindArcTagIndicator<Graph> FindArcTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) const {
 		      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(u, v, prev);
 		      while (arc != INVALID && !(*_edge_filter)[arc]) {
 		        arc = Parent::findArc(u, v, arc);
+		      }
 		      return arc;
+		    }
 		    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
 		    Edge findEdge(const Node& u, const Node& v,
 		                  const Edge& prev = INVALID) const {
 		      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
 		        return INVALID;
+		      }
 		      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
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
 		    public:
 		      typedef V Value;
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
 		      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
 		    public:
 		      typedef V Value;
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
 		      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);

lemon/bits/edge_set_extender.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_EDGE_SET_EXTENDER_H
 		#define LEMON_BITS_EDGE_SET_EXTENDER_H
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/bits/default_map.h>
 		#include <lemon/bits/map_extender.h>
 		///\ingroup digraphbits
 		///\file
 		///\brief Extenders for the arc set types
 		namespace lemon {
 		  /// \ingroup digraphbits
 		  ///
 		  /// \brief Extender for the ArcSets
 		  template <typename Base>
 		  class ArcSetExtender : public Base {
 		  public:
 		    typedef Base Parent;
 		    typedef ArcSetExtender Digraph;
 		    // Base extensions
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
 		    Node fromId(int id, Node) const {
 		      return Parent::nodeFromId(id);
+		    }
 		    Arc fromId(int id, Arc) const {
 		      return Parent::arcFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Arc &e) const {
 		      if (n == Parent::source(e))
 			return Parent::target(e);
 		      else if(n==Parent::target(e))
 			return Parent::source(e);
 		      else
 			return INVALID;
+		    }
 		    // Alteration notifier extensions
 		    /// The arc observer registry.
 		    typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
 		  protected:
 		    mutable ArcNotifier arc_notifier;
 		  public:
 		    using Parent::notifier;
 		    /// \brief Gives back the arc alteration notifier.
 		    ///
 		    /// Gives back the arc alteration notifier.
 		    ArcNotifier& notifier(Arc) const {
 		      return arc_notifier;
+		    }
 		    // Iterable extensions
 		    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));
+		      }
 		      NodeIt(const Digraph& _graph, const Node& node)
 			: Node(node), digraph(&_graph) {}
 		      NodeIt& operator++() {
 			digraph->next(*this);
 			return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
 			_graph.first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Digraph& _graph, const Arc& e) :
 			Arc(e), digraph(&_graph) { }
 		      ArcIt& operator++() {
 			digraph->next(*this);
 			return *this;
+		      }
 		    };
 		    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 Arc& arc)
 			: Arc(arc), digraph(&_graph) {}
 		      OutArcIt& operator++() {
 			digraph->nextOut(*this);
 			return *this;
+		      }
 		    };
 		    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 Arc& arc) :
 			Arc(arc), digraph(&_graph) {}
 		      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 {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the target in this case) of the
 		    /// iterator
 		    Node runningNode(const OutArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Base node of the iterator
 		    ///
 		    /// Returns the base node (ie. the target in this case) of the iterator
 		    Node baseNode(const InArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the source in this case) of the
 		    /// iterator
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    using Parent::first;
 		    // Mappable extension
 		    template <typename _Value>
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
 		    public:
 		      typedef ArcSetExtender Digraph;
 		      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
 		      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);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 			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);
+		    }
 		    ArcSetExtender() {
 		      arc_notifier.setContainer(*this);
+		    }
 		    ~ArcSetExtender() {
 		      arc_notifier.clear();
+		    }
 		  };
 		  /// \ingroup digraphbits
 		  ///
 		  /// \brief Extender for the EdgeSets
 		  template <typename Base>
 		  class EdgeSetExtender : public Base {
 		  public:
 		    typedef Base Parent;
 		    typedef EdgeSetExtender Digraph;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
 		    int maxId(Edge) const {
 		      return Parent::maxEdgeId();
+		    }
 		    Node fromId(int id, Node) const {
 		      return Parent::nodeFromId(id);
+		    }
 		    Arc fromId(int id, Arc) const {
 		      return Parent::arcFromId(id);
+		    }
 		    Edge fromId(int id, Edge) const {
 		      return Parent::edgeFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Edge &e) const {
 		      if( n == Parent::u(e))
 			return Parent::v(e);
 		      else if( n == Parent::v(e))
 			return Parent::u(e);
 		      else
 			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 {
 		      return Parent::direct(e, Parent::u(e) == s);
+		    }
 		    typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;
 		    typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
 		  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 {
 		      const Digraph* digraph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
 			_graph.first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Digraph& _graph, const Node& node)
 			: Node(node), digraph(&_graph) {}
 		      NodeIt& operator++() {
 			digraph->next(*this);
 			return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
 			_graph.first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Digraph& _graph, const Arc& e) :
 			Arc(e), digraph(&_graph) { }
 		      ArcIt& operator++() {
 			digraph->next(*this);
 			return *this;
+		      }
 		    };
 		    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 Arc& arc)
 			: Arc(arc), digraph(&_graph) {}
 		      OutArcIt& operator++() {
 			digraph->nextOut(*this);
 			return *this;
+		      }
 		    };
 		    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 Arc& arc) :
 			Arc(arc), digraph(&_graph) {}
 		      InArcIt& operator++() {
 			digraph->nextIn(*this);
 			return *this;
+		      }
 		    };
 		    class EdgeIt : public Parent::Edge {
 		      const Digraph* digraph;
 		    public:
 		      EdgeIt() { }
 		      EdgeIt(Invalid i) : Edge(i) { }
 		      explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {
 			_graph.first(static_cast<Edge&>(*this));
+		      }
 		      EdgeIt(const Digraph& _graph, const Edge& e) :
 			Edge(e), digraph(&_graph) { }
 		      EdgeIt& operator++() {
 			digraph->next(*this);
 			return *this;
+		      }
 		    };
 		    class IncEdgeIt : public Parent::Edge {
 		      friend class EdgeSetExtender;
 		      const Digraph* digraph;
 		      bool direction;
 		    public:
 		      IncEdgeIt() { }
 		      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
 		      IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {
 			_graph.firstInc(*this, direction, n);
+		      }
 		      IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)
 			: digraph(&_graph), Edge(ue) {
 			direction = (_graph.source(ue) == n);
+		      }
 		      IncEdgeIt& operator++() {
 			digraph->nextInc(*this, direction);
 			return *this;
+		      }
 		    };
 		    /// \brief Base node of the iterator
 		    ///
 		    /// Returns the base node (ie. the source in this case) of the iterator
 		    Node baseNode(const OutArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the target in this case) of the
 		    /// iterator
 		    Node runningNode(const OutArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Base node of the iterator
 		    ///
 		    /// Returns the base node (ie. the target in this case) of the iterator
 		    Node baseNode(const InArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the source in this case) of the
 		    /// iterator
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    /// Base node of the iterator
 		    ///
 		    /// Returns the base node of the iterator
 		    Node baseNode(const IncEdgeIt &e) const {
 		      return e.direction ? u(e) : v(e);
+		    }
 		    /// Running node of the iterator
 		    ///
 		    /// 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
 		      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
 		    public:
 		      typedef EdgeSetExtender Digraph;
 		      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
 		      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);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap
 		      : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
 		    public:
 		      typedef EdgeSetExtender Digraph;
 		      typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
 		      EdgeMap(const Digraph& _g)
 			: Parent(_g) {}
 		      EdgeMap(const Digraph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 			return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 			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;
 		      arcs.push_back(Parent::direct(edge, true));
 		      arcs.push_back(Parent::direct(edge, false));
 		      notifier(Arc()).erase(arcs);
 		      notifier(Edge()).erase(edge);
 		      Parent::erase(edge);
+		    }
 		    EdgeSetExtender() {
 		      arc_notifier.setContainer(*this);
 		      edge_notifier.setContainer(*this);
+		    }
 		    ~EdgeSetExtender() {
 		      edge_notifier.clear();
 		      arc_notifier.clear();
+		    }
 		  };
+		}
 		#endif

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
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_PRED_MAP_PATH_H
 		#define LEMON_BITS_PRED_MAP_PATH_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  template <typename _Digraph, typename _PredMap>
 		  class PredMapPath {
 		  public:
 		    typedef True RevPathTag;
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef _PredMap PredMap;
 		    PredMapPath(const Digraph& _digraph, const PredMap& _predMap,
 		                typename Digraph::Node _target)
 		      : digraph(_digraph), predMap(_predMap), target(_target) {}
 		    int length() const {
 		      int len = 0;
 		      typename Digraph::Node node = target;
 		      typename Digraph::Arc arc;
 		      while ((arc = predMap[node]) != INVALID) {
 		        node = digraph.source(arc);
 		        ++len;
+		      }
 		      return len;
+		    }
 		    bool empty() const {
 		      return predMap[target] != INVALID;
+		    }
 		    class RevArcIt {
 		    public:
 		      RevArcIt() {}
 		      RevArcIt(Invalid) : path(0), current(INVALID) {}
 		      RevArcIt(const PredMapPath& _path)
 		        : path(&_path), current(_path.target) {
 		        if (path->predMap[current] == INVALID) current = INVALID;
+		      }
 		      operator const typename Digraph::Arc() const {
 		        return path->predMap[current];
+		      }
 		      RevArcIt& operator++() {
 		        current = path->digraph.source(path->predMap[current]);
 		        if (path->predMap[current] == INVALID) current = INVALID;
 		        return *this;
+		      }
 		      bool operator==(const RevArcIt& e) const {
 		        return current == e.current;
+		      }
 		      bool operator!=(const RevArcIt& e) const {
 		        return current != e.current;
+		      }
 		      bool operator<(const RevArcIt& e) const {
 		        return current < e.current;
+		      }
 		    private:
 		      const PredMapPath* path;
 		      typename Digraph::Node current;
 		    };
 		  private:
 		    const Digraph& digraph;
 		    const PredMap& predMap;
 		    typename Digraph::Node target;
 		  };
 		  template <typename _Digraph, typename _PredMatrixMap>
 		  class PredMatrixMapPath {
 		  public:
 		    typedef True RevPathTag;
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef _PredMatrixMap PredMatrixMap;
 		    PredMatrixMapPath(const Digraph& _digraph,
 		                      const PredMatrixMap& _predMatrixMap,
 		                      typename Digraph::Node _source,
 		                      typename Digraph::Node _target)
 		      : digraph(_digraph), predMatrixMap(_predMatrixMap),
 		        source(_source), target(_target) {}
 		    int length() const {
 		      int len = 0;
 		      typename Digraph::Node node = target;
 		      typename Digraph::Arc arc;
 		      while ((arc = predMatrixMap(source, node)) != INVALID) {
 		        node = digraph.source(arc);
 		        ++len;
+		      }
 		      return len;
+		    }
 		    bool empty() const {
 		      return source != target;
+		    }
 		    class RevArcIt {
 		    public:
 		      RevArcIt() {}
 		      RevArcIt(Invalid) : path(0), current(INVALID) {}
 		      RevArcIt(const PredMatrixMapPath& _path)
 		        : path(&_path), current(_path.target) {
 		        if (path->predMatrixMap(path->source, current) == INVALID)
 		          current = INVALID;
+		      }
 		      operator const typename Digraph::Arc() const {
 		        return path->predMatrixMap(path->source, current);
+		      }
 		      RevArcIt& operator++() {
 		        current =
 		          path->digraph.source(path->predMatrixMap(path->source, current));
 		        if (path->predMatrixMap(path->source, current) == INVALID)
 		          current = INVALID;
 		        return *this;
+		      }
 		      bool operator==(const RevArcIt& e) const {
 		        return current == e.current;
+		      }
 		      bool operator!=(const RevArcIt& e) const {
 		        return current != e.current;
+		      }
 		      bool operator<(const RevArcIt& e) const {
 		        return current < e.current;
+		      }
 		    private:
 		      const PredMatrixMapPath* path;
 		      typename Digraph::Node current;
 		    };
 		  private:
 		    const Digraph& digraph;
 		    const PredMatrixMap& predMatrixMap;
 		    typename Digraph::Node source;
 		    typename Digraph::Node target;
 		  };
+		}
 		#endif

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
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_BITS_SOLVER_BITS_H
#define LEMON_BITS_SOLVER_BITS_H

#include <vector>

namespace lemon {

  namespace _solver_bits {

    class VarIndex {
    private:
      struct ItemT {
        int prev, next;
        int index;
      };
      std::vector<ItemT> items;
      int first_item, last_item, first_free_item;

      std::vector<int> cross;

    public:

      VarIndex()
        : first_item(-1), last_item(-1), first_free_item(-1) {
      }

      void clear() {
        first_item = -1;
        first_free_item = -1;
        items.clear();
        cross.clear();
      }

      int addIndex(int idx) {
        int n;
        if (first_free_item == -1) {
          n = items.size();
          items.push_back(ItemT());
        } else {
          n = first_free_item;
          first_free_item = items[n].next;
          if (first_free_item != -1) {
            items[first_free_item].prev = -1;
          }
        }
        items[n].index = idx;
        if (static_cast<int>(cross.size()) <= idx) {
          cross.resize(idx + 1, -1);
        }
        cross[idx] = n;

        items[n].prev = last_item;
        items[n].next = -1;
        if (last_item != -1) {
          items[last_item].next = n;
        } else {
          first_item = n;
        }
        last_item = n;

        return n;
      }

      int addIndex(int idx, int n) {
        while (n >= static_cast<int>(items.size())) {
          items.push_back(ItemT());
          items.back().prev = -1;
          items.back().next = first_free_item;
          if (first_free_item != -1) {
            items[first_free_item].prev = items.size() - 1;
          }
          first_free_item = items.size() - 1;
        }
        if (items[n].next != -1) {
          items[items[n].next].prev = items[n].prev;
        }
        if (items[n].prev != -1) {
          items[items[n].prev].next = items[n].next;
        } else {
          first_free_item = items[n].next;
        }

        items[n].index = idx;
        if (static_cast<int>(cross.size()) <= idx) {
          cross.resize(idx + 1, -1);
        }
        cross[idx] = n;

        items[n].prev = last_item;
        items[n].next = -1;
        if (last_item != -1) {
          items[last_item].next = n;
        } else {
          first_item = n;
        }
        last_item = n;

        return n;
      }

      void eraseIndex(int idx) {
        int n = cross[idx];

        if (items[n].prev != -1) {
          items[items[n].prev].next = items[n].next;
        } else {
          first_item = items[n].next;
        }
        if (items[n].next != -1) {
          items[items[n].next].prev = items[n].prev;
        } else {
          last_item = items[n].prev;
        }

        if (first_free_item != -1) {
          items[first_free_item].prev = n;
        }
        items[n].next = first_free_item;
        items[n].prev = -1;
        first_free_item = n;

        while (!cross.empty() && cross.back() == -1) {
          cross.pop_back();
        }
      }

      int maxIndex() const {
        return cross.size() - 1;
      }

      void shiftIndices(int idx) {
        for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
          cross[i - 1] = cross[i];
          if (cross[i] != -1) {
            --items[cross[i]].index;
          }
        }
        cross.back() = -1;
        cross.pop_back();
        while (!cross.empty() && cross.back() == -1) {
          cross.pop_back();
        }
      }

      void relocateIndex(int idx, int jdx) {
        cross[idx] = cross[jdx];
        items[cross[jdx]].index = idx;
        cross[jdx] = -1;

        while (!cross.empty() && cross.back() == -1) {
          cross.pop_back();
        }
      }

      int operator[](int idx) const {
        return cross[idx];
      }

      int operator()(int fdx) const {
        return items[fdx].index;
      }

      void firstItem(int& fdx) const {
        fdx = first_item;
      }

      void nextItem(int& fdx) const {
        fdx = items[fdx].next;
      }

    };
  }
}

#endif

lemon/concepts/heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup concept
 		///\file
 		///\brief The concept of heaps.
 		#ifndef LEMON_CONCEPT_HEAP_H
 		#define LEMON_CONCEPT_HEAP_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief The heap concept.
 		    ///
 		    /// Concept class describing the main interface of heaps.
 		    template <typename Priority, typename ItemIntMap>
 		    class Heap {
 		    public:
 		      /// Type of the items stored in the heap.
 		      typedef typename ItemIntMap::Key Item;
 		      /// Type of the priorities.
 		      typedef Priority Prio;
 		      /// \brief Type to represent the states of the items.
 		      ///
 		      /// Each item has a state associated to it. It can be "in heap",
 		      /// "pre heap" or "post heap". The later two are indifferent
 		      /// from the point of view of the heap, but may be useful for
 		      /// the user.
 		      ///
 		      /// The \c ItemIntMap must be initialized in such a way, that it
 		      /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
 		      enum State {
 		        IN_HEAP = 0,
 		        PRE_HEAP = -1,
 		        POST_HEAP = -2
 		      };
 		      /// \brief The constructor.
 		      ///
 		      /// The constructor.
 		      /// \param map A map that assigns \c int values to keys of type
 		      /// \c Item. It is used internally by the heap implementations to
 		      /// handle the cross references. The assigned value must be
 		      /// \c PRE_HEAP (<tt>-1</tt>) for every item.
 		      explicit Heap(ItemIntMap &map) {}
 		      /// \brief The number of items stored in the heap.
 		      ///
 		      /// Returns the number of items stored in the heap.
 		      int size() const { return 0; }
 		      /// \brief Checks if the heap is empty.
 		      ///
 		      /// Returns \c true if the heap is empty.
 		      bool empty() const { return false; }
 		      /// \brief Makes the heap empty.
 		      ///
 		      /// Makes the heap empty.
 		      void clear();
 		      /// \brief Inserts an item into the heap with the given priority.
 		      ///
 		      /// Inserts the given item into the heap with the given priority.
 		      /// \param i The item to insert.
 		      /// \param p The priority of the item.
 		      void push(const Item &i, const Prio &p) {}
 		      /// \brief Returns the item having minimum priority.
 		      ///
 		      /// Returns the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Item top() const {}
 		      /// \brief The minimum priority.
 		      ///
 		      /// Returns the minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Prio prio() const {}
 		      /// \brief Removes the item having minimum priority.
 		      ///
 		      /// Removes the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      void pop() {}
 		      /// \brief Removes an item from the heap.
 		      ///
 		      /// Removes the given item from the heap if it is already stored.
 		      /// \param i The item to delete.
 		      void erase(const Item &i) {}
 		      /// \brief The priority of an item.
 		      ///
 		      /// Returns the priority of the given item.
 		      /// \pre \c i must be in the heap.
 		      /// \param i The item.
 		      Prio operator[](const Item &i) const {}
 		      /// \brief Sets the priority of an item or inserts it, if it is
 		      /// not stored in the heap.
 		      ///
 		      /// This method sets the priority of the given item if it is
 		      /// already stored in the heap.
 		      /// Otherwise it inserts the given item with the given priority.
 		      ///
 		      /// \param i The item.
 		      /// \param p The priority.
 		      void set(const Item &i, const Prio &p) {}
 		      /// \brief Decreases the priority of an item to the given value.
 		      ///
 		      /// Decreases the priority of an item to the given value.
 		      /// \pre \c i must be stored in the heap with priority at least \c p.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      void decrease(const Item &i, const Prio &p) {}
 		      /// \brief Increases the priority of an item to the given value.
 		      ///
 		      /// Increases the priority of an item to the given value.
 		      /// \pre \c i must be stored in the heap with priority at most \c p.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      void increase(const Item &i, const Prio &p) {}
 		      /// \brief Returns if an item is in, has already been in, or has
 		      /// never been in the heap.
 		      ///
 		      /// This method returns \c PRE_HEAP if the given item has never
 		      /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		      /// and \c POST_HEAP otherwise.
 		      /// In the latter case it is possible that the item will get back
 		      /// to the heap again.
 		      /// \param i The item.
 		      State state(const Item &i) const {}
 		      /// \brief Sets the state of an item in the heap.
 		      ///
 		      /// Sets the state of the given item in the heap. It can be used
 		      /// to manually clear the heap when it is important to achive the
 		      /// better time complexity.
 		      /// \param i The item.
 		      /// \param st The state. It should not be \c IN_HEAP.
 		      void state(const Item& i, State st) {}
 		      template <typename _Heap>
 		      struct Constraints {
 		      public:
 		        void constraints() {
 		          typedef typename _Heap::Item OwnItem;
 		          typedef typename _Heap::Prio OwnPrio;
 		          typedef typename _Heap::State OwnState;
 		          Item item;
 		          Prio prio;
 		          item=Item();
 		          prio=Prio();
 		          ignore_unused_variable_warning(item);
 		          ignore_unused_variable_warning(prio);
 		          OwnItem own_item;
 		          OwnPrio own_prio;
 		          OwnState own_state;
 		          own_item=Item();
 		          own_prio=Prio();
 		          ignore_unused_variable_warning(own_item);
 		          ignore_unused_variable_warning(own_prio);
 		          ignore_unused_variable_warning(own_state);
 		          _Heap heap1(map);
 		          _Heap heap2 = heap1;
 		          ignore_unused_variable_warning(heap1);
 		          ignore_unused_variable_warning(heap2);
 		          int s = heap.size();
 		          ignore_unused_variable_warning(s);
 		          bool e = heap.empty();
 		          ignore_unused_variable_warning(e);
 		          prio = heap.prio();
 		          item = heap.top();
 		          prio = heap[item];
 		          own_prio = heap.prio();
 		          own_item = heap.top();
 		          own_prio = heap[own_item];
 		          heap.push(item, prio);
 		          heap.push(own_item, own_prio);
 		          heap.pop();
 		          heap.set(item, prio);
 		          heap.decrease(item, prio);
 		          heap.increase(item, prio);
 		          heap.set(own_item, own_prio);
 		          heap.decrease(own_item, own_prio);
 		          heap.increase(own_item, own_prio);
 		          heap.erase(item);
 		          heap.erase(own_item);
 		          heap.clear();
 		          own_state = heap.state(own_item);
 		          heap.state(own_item, own_state);
 		          own_state = _Heap::PRE_HEAP;
 		          own_state = _Heap::IN_HEAP;
 		          own_state = _Heap::POST_HEAP;
+		        }
 		        _Heap& heap;
 		        ItemIntMap& map;
 		      };
 		    };
 		    /// @}
 		  } // namespace lemon
+		}
 		#endif // LEMON_CONCEPT_PATH_H

lemon/elevator.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_ELEVATOR_H
 		#define LEMON_ELEVATOR_H
 		///\ingroup auxdat
 		///\file
 		///\brief Elevator class
 		///
 		///Elevator class implements an efficient data structure
 		///for labeling items in push-relabel type algorithms.
 		///
 		#include <lemon/core.h>
 		#include <lemon/bits/traits.h>
 		namespace lemon {
 		  ///Class for handling "labels" in push-relabel type algorithms.
 		  ///A class for handling "labels" in push-relabel type algorithms.
 		  ///
 		  ///\ingroup auxdat
 		  ///Using this class you can assign "labels" (nonnegative integer numbers)
 		  ///to the edges or nodes of a graph, manipulate and query them through
 		  ///operations typically arising in "push-relabel" type algorithms.
 		  ///
 		  ///Each item is either \em active or not, and you can also choose a
 		  ///highest level active item.
 		  ///
 		  ///\sa LinkedElevator
 		  ///
 		  ///\param Graph Type of the underlying graph.
 		  ///\param Item Type of the items the data is assigned to (Graph::Node,
 		  ///Graph::Arc, Graph::Edge).
 		  template<class Graph, class Item>
 		  class Elevator
+		  {
 		  public:
 		    typedef Item Key;
 		    typedef int Value;
 		  private:
 		    typedef Item *Vit;
 		    typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
 		    typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
 		    const Graph &_g;
 		    int _max_level;
 		    int _item_num;
 		    VitMap _where;
 		    IntMap _level;
 		    std::vector<Item> _items;
 		    std::vector<Vit> _first;
 		    std::vector<Vit> _last_active;
 		    int _highest_active;
 		    void copy(Item i, Vit p)
+		    {
 		      _where.set(*p=i,p);
+		    }
 		    void copy(Vit s, Vit p)
+		    {
 		      if(s!=p)
+		        {
 		          Item i=*s;
 		          *p=i;
 		          _where.set(i,p);
+		        }
+		    }
 		    void swap(Vit i, Vit j)
+		    {
 		      Item ti=*i;
 		      Vit ct = _where[ti];
 		      _where.set(ti,_where[*i=*j]);
 		      _where.set(*j,ct);
 		      *j=ti;
+		    }
 		  public:
 		    ///Constructor with given maximum level.
 		    ///Constructor with given maximum level.
 		    ///
 		    ///\param graph The underlying graph.
 		    ///\param max_level The maximum allowed level.
 		    ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
 		    Elevator(const Graph &graph,int max_level) :
 		      _g(graph),
 		      _max_level(max_level),
 		      _item_num(_max_level),
 		      _where(graph),
 		      _level(graph,0),
 		      _items(_max_level),
 		      _first(_max_level+2),
 		      _last_active(_max_level+2),
 		      _highest_active(-1) {}
 		    ///Constructor.
 		    ///Constructor.
 		    ///
 		    ///\param graph The underlying graph.
 		    ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
 		    ///where \c max_level is equal to the number of labeled items in the graph.
 		    Elevator(const Graph &graph) :
 		      _g(graph),
 		      _max_level(countItems<Graph, Item>(graph)),
 		      _item_num(_max_level),
 		      _where(graph),
 		      _level(graph,0),
 		      _items(_max_level),
 		      _first(_max_level+2),
 		      _last_active(_max_level+2),
 		      _highest_active(-1)
+		    {
+		    }
 		    ///Activate item \c i.
 		    ///Activate item \c i.
 		    ///\pre Item \c i shouldn't be active before.
 		    void activate(Item i)
+		    {
 		      const int l=_level[i];
 		      swap(_where[i],++_last_active[l]);
 		      if(l>_highest_active) _highest_active=l;
+		    }
 		    ///Deactivate item \c i.
 		    ///Deactivate item \c i.
 		    ///\pre Item \c i must be active before.
 		    void deactivate(Item i)
+		    {
 		      swap(_where[i],_last_active[_level[i]]--);
 		      while(_highest_active>=0 &&
 		            _last_active[_highest_active]<_first[_highest_active])
 		        _highest_active--;
+		    }
 		    ///Query whether item \c i is active
 		    bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
 		    ///Return the level of item \c i.
 		    int operator[](Item i) const { return _level[i]; }
 		    ///Return the number of items on level \c l.
 		    int onLevel(int l) const
+		    {
 		      return _first[l+1]-_first[l];
+		    }
 		    ///Return true if level \c l is empty.
 		    bool emptyLevel(int l) const
+		    {
 		      return _first[l+1]-_first[l]==0;
+		    }
 		    ///Return the number of items above level \c l.
 		    int aboveLevel(int l) const
+		    {
 		      return _first[_max_level+1]-_first[l+1];
+		    }
 		    ///Return the number of active items on level \c l.
 		    int activesOnLevel(int l) const
+		    {
 		      return _last_active[l]-_first[l]+1;
+		    }
 		    ///Return true if there is no active item on level \c l.
 		    bool activeFree(int l) const
+		    {
 		      return _last_active[l]<_first[l];
+		    }
 		    ///Return the maximum allowed level.
 		    int maxLevel() const
+		    {
 		      return _max_level;
+		    }
 		    ///\name Highest Active Item
 		    ///Functions for working with the highest level
 		    ///active item.
 		    ///@{
 		    ///Return a highest level active item.
 		    ///Return a highest level active item or INVALID if there is no active
 		    ///item.
 		    Item highestActive() const
+		    {
 		      return _highest_active>=0?*_last_active[_highest_active]:INVALID;
+		    }
 		    ///Return the highest active level.
 		    ///Return the level of the highest active item or -1 if there is no active
 		    ///item.
 		    int highestActiveLevel() const
+		    {
 		      return _highest_active;
+		    }
 		    ///Lift the highest active item by one.
 		    ///Lift the item returned by highestActive() by one.
 		    ///
 		    void liftHighestActive()
+		    {
 		      Item it = *_last_active[_highest_active];
 		      _level.set(it,_level[it]+1);
 		      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
 		      --_first[++_highest_active];
+		    }
 		    ///Lift the highest active item to the given level.
 		    ///Lift the item returned by highestActive() to level \c new_level.
 		    ///
 		    ///\warning \c new_level must be strictly higher
 		    ///than the current level.
 		    ///
 		    void liftHighestActive(int new_level)
+		    {
 		      const Item li = *_last_active[_highest_active];
 		      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
 		      for(int l=_highest_active+1;l<new_level;l++)
+		        {
 		          copy(--_first[l+1],_first[l]);
 		          --_last_active[l];
+		        }
 		      copy(li,_first[new_level]);
 		      _level.set(li,new_level);
 		      _highest_active=new_level;
+		    }
 		    ///Lift the highest active item to the top level.
 		    ///Lift the item returned by highestActive() to the top level and
 		    ///deactivate it.
 		    void liftHighestActiveToTop()
+		    {
 		      const Item li = *_last_active[_highest_active];
 		      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
 		      for(int l=_highest_active+1;l<_max_level;l++)
+		        {
 		          copy(--_first[l+1],_first[l]);
 		          --_last_active[l];
+		        }
 		      copy(li,_first[_max_level]);
 		      --_last_active[_max_level];
 		      _level.set(li,_max_level);
 		      while(_highest_active>=0 &&
 		            _last_active[_highest_active]<_first[_highest_active])
 		        _highest_active--;
+		    }
 		    ///@}
 		    ///\name Active Item on Certain Level
 		    ///Functions for working with the active items.
 		    ///@{
 		    ///Return an active item on level \c l.
 		    ///Return an active item on level \c l or \ref INVALID if there is no such
 		    ///an item. (\c l must be from the range [0...\c max_level].
 		    Item activeOn(int l) const
+		    {
 		      return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
+		    }
 		    ///Lift the active item returned by \c activeOn(level) by one.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
 		    ///by one.
 		    Item liftActiveOn(int level)
+		    {
 		      Item it =*_last_active[level];
 		      _level.set(it,_level[it]+1);
 		      swap(_last_active[level]--, --_first[level+1]);
 		      if (level+1>_highest_active) ++_highest_active;
+		    }
 		    ///Lift the active item returned by \c activeOn(level) to the given level.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
 		    ///to the given level.
 		    void liftActiveOn(int level, int new_level)
+		    {
 		      const Item ai = *_last_active[level];
 		      copy(--_first[level+1], _last_active[level]--);
 		      for(int l=level+1;l<new_level;l++)
+		        {
 		          copy(_last_active[l],_first[l]);
 		          copy(--_first[l+1], _last_active[l]--);
+		        }
 		      copy(ai,_first[new_level]);
 		      _level.set(ai,new_level);
 		      if (new_level>_highest_active) _highest_active=new_level;
+		    }
 		    ///Lift the active item returned by \c activeOn(level) to the top level.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
 		    ///to the top level and deactivate it.
 		    void liftActiveToTop(int level)
+		    {
 		      const Item ai = *_last_active[level];
 		      copy(--_first[level+1],_last_active[level]--);
 		      for(int l=level+1;l<_max_level;l++)
+		        {
 		          copy(_last_active[l],_first[l]);
 		          copy(--_first[l+1], _last_active[l]--);
+		        }
 		      copy(ai,_first[_max_level]);
 		      --_last_active[_max_level];
 		      _level.set(ai,_max_level);
 		      if (_highest_active==level) {
 		        while(_highest_active>=0 &&
 		              _last_active[_highest_active]<_first[_highest_active])
 		          _highest_active--;
+		      }
+		    }
 		    ///@}
 		    ///Lift an active item to a higher level.
 		    ///Lift an active item to a higher level.
 		    ///\param i The item to be lifted. It must be active.
 		    ///\param new_level The new level of \c i. It must be strictly higher
 		    ///than the current level.
 		    ///
 		    void lift(Item i, int new_level)
+		    {
 		      const int lo = _level[i];
 		      const Vit w = _where[i];
 		      copy(_last_active[lo],w);
 		      copy(--_first[lo+1],_last_active[lo]--);
 		      for(int l=lo+1;l<new_level;l++)
+		        {
 		          copy(_last_active[l],_first[l]);
 		          copy(--_first[l+1],_last_active[l]--);
+		        }
 		      copy(i,_first[new_level]);
 		      _level.set(i,new_level);
 		      if(new_level>_highest_active) _highest_active=new_level;
+		    }
 		    ///Move an inactive item to the top but one level (in a dirty way).
 		    ///This function moves an inactive item from the top level to the top
 		    ///but one level (in a dirty way).
 		    ///\warning It makes the underlying datastructure corrupt, so use it
 		    ///only if you really know what it is for.
 		    ///\pre The item is on the top level.
 		    void dirtyTopButOne(Item i) {
 		      _level.set(i,_max_level - 1);
+		    }
 		    ///Lift all items on and above the given level to the top level.
 		    ///This function lifts all items on and above level \c l to the top
 		    ///level and deactivates them.
 		    void liftToTop(int l)
+		    {
 		      const Vit f=_first[l];
 		      const Vit tl=_first[_max_level];
 		      for(Vit i=f;i!=tl;++i)
 		        _level.set(*i,_max_level);
 		      for(int i=l;i<=_max_level;i++)
+		        {
 		          _first[i]=f;
 		          _last_active[i]=f-1;
+		        }
 		      for(_highest_active=l-1;
 		          _highest_active>=0 &&
 		            _last_active[_highest_active]<_first[_highest_active];
 		          _highest_active--) ;
+		    }
 		  private:
 		    int _init_lev;
 		    Vit _init_num;
 		  public:
 		    ///\name Initialization
 		    ///Using these functions you can initialize the levels of the items.
 		    ///\n
 		    ///The initialization must be started with calling \c initStart().
 		    ///Then the items should be listed level by level starting with the
 		    ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
 		    ///Finally \c initFinish() must be called.
 		    ///The items not listed are put on the highest level.
 		    ///@{
 		    ///Start the initialization process.
 		    void initStart()
+		    {
 		      _init_lev=0;
 		      _init_num=&_items[0];
 		      _first[0]=&_items[0];
 		      _last_active[0]=&_items[0]-1;
 		      Vit n=&_items[0];
 		      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
+		        {
 		          *n=i;
 		          _where.set(i,n);
 		          _level.set(i,_max_level);
 		          ++n;
+		        }
+		    }
 		    ///Add an item to the current level.
 		    void initAddItem(Item i)
+		    {
 		      swap(_where[i],_init_num);
 		      _level.set(i,_init_lev);
 		      ++_init_num;
+		    }
 		    ///Start a new level.
 		    ///Start a new level.
 		    ///It shouldn't be used before the items on level 0 are listed.
 		    void initNewLevel()
+		    {
 		      _init_lev++;
 		      _first[_init_lev]=_init_num;
 		      _last_active[_init_lev]=_init_num-1;
+		    }
 		    ///Finalize the initialization process.
 		    void initFinish()
+		    {
 		      for(_init_lev++;_init_lev<=_max_level;_init_lev++)
+		        {
 		          _first[_init_lev]=_init_num;
 		          _last_active[_init_lev]=_init_num-1;
+		        }
 		      _first[_max_level+1]=&_items[0]+_item_num;
 		      _last_active[_max_level+1]=&_items[0]+_item_num-1;
 		      _highest_active = -1;
+		    }
 		    ///@}
 		  };
 		  ///Class for handling "labels" in push-relabel type algorithms.
 		  ///A class for handling "labels" in push-relabel type algorithms.
 		  ///
 		  ///\ingroup auxdat
 		  ///Using this class you can assign "labels" (nonnegative integer numbers)
 		  ///to the edges or nodes of a graph, manipulate and query them through
 		  ///operations typically arising in "push-relabel" type algorithms.
 		  ///
 		  ///Each item is either \em active or not, and you can also choose a
 		  ///highest level active item.
 		  ///
 		  ///\sa Elevator
 		  ///
 		  ///\param Graph Type of the underlying graph.
 		  ///\param Item Type of the items the data is assigned to (Graph::Node,
 		  ///Graph::Arc, Graph::Edge).
 		  template <class Graph, class Item>
 		  class LinkedElevator {
 		  public:
 		    typedef Item Key;
 		    typedef int Value;
 		  private:
 		    typedef typename ItemSetTraits<Graph,Item>::
 		    template Map<Item>::Type ItemMap;
 		    typedef typename ItemSetTraits<Graph,Item>::
 		    template Map<int>::Type IntMap;
 		    typedef typename ItemSetTraits<Graph,Item>::
 		    template Map<bool>::Type BoolMap;
 		    const Graph &_graph;
 		    int _max_level;
 		    int _item_num;
 		    std::vector<Item> _first, _last;
 		    ItemMap _prev, _next;
 		    int _highest_active;
 		    IntMap _level;
 		    BoolMap _active;
 		  public:
 		    ///Constructor with given maximum level.
 		    ///Constructor with given maximum level.
 		    ///
 		    ///\param graph The underlying graph.
 		    ///\param max_level The maximum allowed level.
 		    ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
 		    LinkedElevator(const Graph& graph, int max_level)
 		      : _graph(graph), _max_level(max_level), _item_num(_max_level),
 		        _first(_max_level + 1), _last(_max_level + 1),
 		        _prev(graph), _next(graph),
 		        _highest_active(-1), _level(graph), _active(graph) {}
 		    ///Constructor.
 		    ///Constructor.
 		    ///
 		    ///\param graph The underlying graph.
 		    ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
 		    ///where \c max_level is equal to the number of labeled items in the graph.
 		    LinkedElevator(const Graph& graph)
 		      : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
 		        _item_num(_max_level),
 		        _first(_max_level + 1), _last(_max_level + 1),
 		        _prev(graph, INVALID), _next(graph, INVALID),
 		        _highest_active(-1), _level(graph), _active(graph) {}
 		    ///Activate item \c i.
 		    ///Activate item \c i.
 		    ///\pre Item \c i shouldn't be active before.
 		    void activate(Item i) {
 		      _active.set(i, true);
 		      int level = _level[i];
 		      if (level > _highest_active) {
 		        _highest_active = level;
+		      }
 		      if (_prev[i] == INVALID || _active[_prev[i]]) return;
 		      //unlace
 		      _next.set(_prev[i], _next[i]);
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], _prev[i]);
 		      } else {
 		        _last[level] = _prev[i];
+		      }
 		      //lace
 		      _next.set(i, _first[level]);
 		      _prev.set(_first[level], i);
 		      _prev.set(i, INVALID);
 		      _first[level] = i;
+		    }
 		    ///Deactivate item \c i.
 		    ///Deactivate item \c i.
 		    ///\pre Item \c i must be active before.
 		    void deactivate(Item i) {
 		      _active.set(i, false);
 		      int level = _level[i];
 		      if (_next[i] == INVALID || !_active[_next[i]])
 		        goto find_highest_level;
 		      //unlace
 		      _prev.set(_next[i], _prev[i]);
 		      if (_prev[i] != INVALID) {
 		        _next.set(_prev[i], _next[i]);
 		      } else {
 		        _first[_level[i]] = _next[i];
+		      }
 		      //lace
 		      _prev.set(i, _last[level]);
 		      _next.set(_last[level], i);
 		      _next.set(i, INVALID);
 		      _last[level] = i;
 		    find_highest_level:
 		      if (level == _highest_active) {
 		        while (_highest_active >= 0 && activeFree(_highest_active))
 		          --_highest_active;
+		      }
+		    }
 		    ///Query whether item \c i is active
 		    bool active(Item i) const { return _active[i]; }
 		    ///Return the level of item \c i.
 		    int operator[](Item i) const { return _level[i]; }
 		    ///Return the number of items on level \c l.
 		    int onLevel(int l) const {
 		      int num = 0;
 		      Item n = _first[l];
 		      while (n != INVALID) {
 		        ++num;
 		        n = _next[n];
+		      }
 		      return num;
+		    }
 		    ///Return true if the level is empty.
 		    bool emptyLevel(int l) const {
 		      return _first[l] == INVALID;
+		    }
 		    ///Return the number of items above level \c l.
 		    int aboveLevel(int l) const {
 		      int num = 0;
 		      for (int level = l + 1; level < _max_level; ++level)
 		        num += onLevel(level);
 		      return num;
+		    }
 		    ///Return the number of active items on level \c l.
 		    int activesOnLevel(int l) const {
 		      int num = 0;
 		      Item n = _first[l];
 		      while (n != INVALID && _active[n]) {
 		        ++num;
 		        n = _next[n];
+		      }
 		      return num;
+		    }
 		    ///Return true if there is no active item on level \c l.
 		    bool activeFree(int l) const {
 		      return _first[l] == INVALID || !_active[_first[l]];
+		    }
 		    ///Return the maximum allowed level.
 		    int maxLevel() const {
 		      return _max_level;
+		    }
 		    ///\name Highest Active Item
 		    ///Functions for working with the highest level
 		    ///active item.
 		    ///@{
 		    ///Return a highest level active item.
 		    ///Return a highest level active item or INVALID if there is no active
 		    ///item.
 		    Item highestActive() const {
 		      return _highest_active >= 0 ? _first[_highest_active] : INVALID;
+		    }
 		    ///Return the highest active level.
 		    ///Return the level of the highest active item or -1 if there is no active
 		    ///item.
 		    int highestActiveLevel() const {
 		      return _highest_active;
+		    }
 		    ///Lift the highest active item by one.
 		    ///Lift the item returned by highestActive() by one.
 		    ///
 		    void liftHighestActive() {
 		      Item i = _first[_highest_active];
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[_highest_active] = _next[i];
 		      } else {
 		        _first[_highest_active] = INVALID;
 		        _last[_highest_active] = INVALID;
+		      }
 		      _level.set(i, ++_highest_active);
 		      if (_first[_highest_active] == INVALID) {
 		        _first[_highest_active] = i;
 		        _last[_highest_active] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(_first[_highest_active], i);
 		        _next.set(i, _first[_highest_active]);
 		        _first[_highest_active] = i;
+		      }
+		    }
 		    ///Lift the highest active item to the given level.
 		    ///Lift the item returned by highestActive() to level \c new_level.
 		    ///
 		    ///\warning \c new_level must be strictly higher
 		    ///than the current level.
 		    ///
 		    void liftHighestActive(int new_level) {
 		      Item i = _first[_highest_active];
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[_highest_active] = _next[i];
 		      } else {
 		        _first[_highest_active] = INVALID;
 		        _last[_highest_active] = INVALID;
+		      }
 		      _level.set(i, _highest_active = new_level);
 		      if (_first[_highest_active] == INVALID) {
 		        _first[_highest_active] = _last[_highest_active] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(_first[_highest_active], i);
 		        _next.set(i, _first[_highest_active]);
 		        _first[_highest_active] = i;
+		      }
+		    }
 		    ///Lift the highest active item to the top level.
 		    ///Lift the item returned by highestActive() to the top level and
 		    ///deactivate it.
 		    void liftHighestActiveToTop() {
 		      Item i = _first[_highest_active];
 		      _level.set(i, _max_level);
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[_highest_active] = _next[i];
 		      } else {
 		        _first[_highest_active] = INVALID;
 		        _last[_highest_active] = INVALID;
+		      }
 		      while (_highest_active >= 0 && activeFree(_highest_active))
 		        --_highest_active;
+		    }
 		    ///@}
 		    ///\name Active Item on Certain Level
 		    ///Functions for working with the active items.
 		    ///@{
 		    ///Return an active item on level \c l.
 		    ///Return an active item on level \c l or \ref INVALID if there is no such
 		    ///an item. (\c l must be from the range [0...\c max_level].
 		    Item activeOn(int l) const
+		    {
 		      return _active[_first[l]] ? _first[l] : INVALID;
+		    }
 		    ///Lift the active item returned by \c activeOn(l) by one.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(l)"
 		    ///by one.
 		    Item liftActiveOn(int l)
+		    {
 		      Item i = _first[l];
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[l] = _next[i];
 		      } else {
 		        _first[l] = INVALID;
 		        _last[l] = INVALID;
+		      }
 		      _level.set(i, ++l);
 		      if (_first[l] == INVALID) {
 		        _first[l] = _last[l] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(_first[l], i);
 		        _next.set(i, _first[l]);
 		        _first[l] = i;
+		      }
 		      if (_highest_active < l) {
 		        _highest_active = l;
+		      }
+		    }
 		    ///Lift the active item returned by \c activeOn(l) to the given level.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(l)"
 		    ///to the given level.
 		    void liftActiveOn(int l, int new_level)
+		    {
 		      Item i = _first[l];
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[l] = _next[i];
 		      } else {
 		        _first[l] = INVALID;
 		        _last[l] = INVALID;
+		      }
 		      _level.set(i, l = new_level);
 		      if (_first[l] == INVALID) {
 		        _first[l] = _last[l] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(_first[l], i);
 		        _next.set(i, _first[l]);
 		        _first[l] = i;
+		      }
 		      if (_highest_active < l) {
 		        _highest_active = l;
+		      }
+		    }
 		    ///Lift the active item returned by \c activeOn(l) to the top level.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(l)"
 		    ///to the top level and deactivate it.
 		    void liftActiveToTop(int l)
+		    {
 		      Item i = _first[l];
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[l] = _next[i];
 		      } else {
 		        _first[l] = INVALID;
 		        _last[l] = INVALID;
+		      }
 		      _level.set(i, _max_level);
 		      if (l == _highest_active) {
 		        while (_highest_active >= 0 && activeFree(_highest_active))
 		          --_highest_active;
+		      }
+		    }
 		    ///@}
 		    /// \brief Lift an active item to a higher level.
 		    ///
 		    /// Lift an active item to a higher level.
 		    /// \param i The item to be lifted. It must be active.
 		    /// \param new_level The new level of \c i. It must be strictly higher
 		    /// than the current level.
 		    ///
 		    void lift(Item i, int new_level) {
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], _prev[i]);
 		      } else {
 		        _last[new_level] = _prev[i];
+		      }
 		      if (_prev[i] != INVALID) {
 		        _next.set(_prev[i], _next[i]);
 		      } else {
 		        _first[new_level] = _next[i];
+		      }
 		      _level.set(i, new_level);
 		      if (_first[new_level] == INVALID) {
 		        _first[new_level] = _last[new_level] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(_first[new_level], i);
 		        _next.set(i, _first[new_level]);
 		        _first[new_level] = i;
+		      }
 		      if (_highest_active < new_level) {
 		        _highest_active = new_level;
+		      }
+		    }
 		    ///Move an inactive item to the top but one level (in a dirty way).
 		    ///This function moves an inactive item from the top level to the top
 		    ///but one level (in a dirty way).
 		    ///\warning It makes the underlying datastructure corrupt, so use it
 		    ///only if you really know what it is for.
 		    ///\pre The item is on the top level.
 		    void dirtyTopButOne(Item i) {
 		      _level.set(i, _max_level - 1);
+		    }
 		    ///Lift all items on and above the given level to the top level.
 		    ///This function lifts all items on and above level \c l to the top
 		    ///level and deactivates them.
 		    void liftToTop(int l)  {
 		      for (int i = l + 1; _first[i] != INVALID; ++i) {
 		        Item n = _first[i];
 		        while (n != INVALID) {
 		          _level.set(n, _max_level);
 		          n = _next[n];
+		        }
 		        _first[i] = INVALID;
 		        _last[i] = INVALID;
+		      }
 		      if (_highest_active > l - 1) {
 		        _highest_active = l - 1;
 		        while (_highest_active >= 0 && activeFree(_highest_active))
 		          --_highest_active;
+		      }
+		    }
 		  private:
 		    int _init_level;
 		  public:
 		    ///\name Initialization
 		    ///Using these functions you can initialize the levels of the items.
 		    ///\n
 		    ///The initialization must be started with calling \c initStart().
 		    ///Then the items should be listed level by level starting with the
 		    ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
 		    ///Finally \c initFinish() must be called.
 		    ///The items not listed are put on the highest level.
 		    ///@{
 		    ///Start the initialization process.
 		    void initStart() {
 		      for (int i = 0; i <= _max_level; ++i) {
 		        _first[i] = _last[i] = INVALID;
+		      }
 		      _init_level = 0;
 		      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
 		          i != INVALID; ++i) {
 		        _level.set(i, _max_level);
 		        _active.set(i, false);
+		      }
+		    }
 		    ///Add an item to the current level.
 		    void initAddItem(Item i) {
 		      _level.set(i, _init_level);
 		      if (_last[_init_level] == INVALID) {
 		        _first[_init_level] = i;
 		        _last[_init_level] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(i, _last[_init_level]);
 		        _next.set(i, INVALID);
 		        _next.set(_last[_init_level], i);
 		        _last[_init_level] = i;
+		      }
+		    }
 		    ///Start a new level.
 		    ///Start a new level.
 		    ///It shouldn't be used before the items on level 0 are listed.
 		    void initNewLevel() {
 		      ++_init_level;
+		    }
 		    ///Finalize the initialization process.
 		    void initFinish() {
 		      _highest_active = -1;
+		    }
 		    ///@}
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif

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
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_SUURBALLE_H
 		#define LEMON_SUURBALLE_H
 		///\ingroup shortest_path
 		///\file
 		///\brief An algorithm for finding arc-disjoint paths between two
 		/// nodes having minimum total length.
 		#include <vector>
 		#include <lemon/bin_heap.h>
 		#include <lemon/path.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/maps.h>
 		namespace lemon {
 		  /// \addtogroup shortest_path
 		  /// @{
 		  /// \brief Algorithm for finding arc-disjoint paths between two nodes
 		  /// having minimum total length.
 		  ///
 		  /// \ref lemon::Suurballe "Suurballe" implements an algorithm for
 		  /// finding arc-disjoint paths having minimum total length (cost)
 		  /// from a given source node to a given target node in a digraph.
 		  ///
 		  /// In fact, this implementation is the specialization of the
 		  /// \ref CapacityScaling "successive shortest path" algorithm.
 		  ///
 		  /// \tparam Digraph The digraph type the algorithm runs on.
 		  /// The default value is \c ListDigraph.
 		  /// \tparam LengthMap The type of the length (cost) map.
 		  /// The default value is <tt>Digraph::ArcMap<int></tt>.
 		  ///
 		  /// \warning Length values should be \e non-negative \e integers.
 		  ///
 		  /// \note For finding node-disjoint paths this algorithm can be used
 		  /// with \ref SplitNodes.
 		#ifdef DOXYGEN
 		  template <typename Digraph, typename LengthMap>
 		#else
 		  template < typename Digraph = ListDigraph,
 		             typename LengthMap = typename Digraph::template ArcMap<int> >
 		#endif
 		  class Suurballe
+		  {
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    typedef typename LengthMap::Value Length;
 		    typedef ConstMap<Arc, int> ConstArcMap;
 		    typedef typename Digraph::template NodeMap<Arc> PredMap;
 		  public:
 		    /// The type of the flow map.
 		    typedef typename Digraph::template ArcMap<int> FlowMap;
 		    /// The type of the potential map.
 		    typedef typename Digraph::template NodeMap<Length> PotentialMap;
 		    /// The type of the path structures.
 		    typedef SimplePath<Digraph> Path;
 		  private:
 		    /// \brief Special implementation of the Dijkstra algorithm
 		    /// for finding shortest paths in the residual network.
 		    ///
 		    /// \ref ResidualDijkstra is a special implementation of the
 		    /// \ref Dijkstra algorithm for finding shortest paths in the
 		    /// residual network of the digraph with respect to the reduced arc
 		    /// lengths and modifying the node potentials according to the
 		    /// distance of the nodes.
 		    class ResidualDijkstra
+		    {
 		      typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 		      typedef BinHeap<Length, HeapCrossRef> Heap;
 		    private:
 		      // The digraph the algorithm runs on
 		      const Digraph &_graph;
 		      // The main maps
 		      const FlowMap &_flow;
 		      const LengthMap &_length;
 		      PotentialMap &_potential;
 		      // The distance map
 		      PotentialMap _dist;
 		      // The pred arc map
 		      PredMap &_pred;
 		      // The processed (i.e. permanently labeled) nodes
 		      std::vector<Node> _proc_nodes;
 		      Node _s;
 		      Node _t;
 		    public:
 		      /// Constructor.
 		      ResidualDijkstra( const Digraph &digraph,
 		                        const FlowMap &flow,
 		                        const LengthMap &length,
 		                        PotentialMap &potential,
 		                        PredMap &pred,
 		                        Node s, Node t ) :
 		        _graph(digraph), _flow(flow), _length(length), _potential(potential),
 		        _dist(digraph), _pred(pred), _s(s), _t(t) {}
 		      /// \brief Run the algorithm. It returns \c true if a path is found
 		      /// from the source node to the target node.
 		      bool run() {
 		        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
 		        Heap heap(heap_cross_ref);
 		        heap.push(_s, 0);
 		        _pred[_s] = INVALID;
 		        _proc_nodes.clear();
 		        // Process nodes
 		        while (!heap.empty() && heap.top() != _t) {
 		          Node u = heap.top(), v;
 		          Length d = heap.prio() + _potential[u], nd;
 		          _dist[u] = heap.prio();
 		          heap.pop();
 		          _proc_nodes.push_back(u);
 		          // Traverse outgoing arcs
 		          for (OutArcIt e(_graph, u); e != INVALID; ++e) {
 		            if (_flow[e] == 0) {
 		              v = _graph.target(e);
 		              switch(heap.state(v)) {
 		              case Heap::PRE_HEAP:
 		                heap.push(v, d + _length[e] - _potential[v]);
 		                _pred[v] = e;
 		                break;
 		              case Heap::IN_HEAP:
 		                nd = d + _length[e] - _potential[v];
 		                if (nd < heap[v]) {
 		                  heap.decrease(v, nd);
 		                  _pred[v] = e;
+		                }
 		                break;
 		              case Heap::POST_HEAP:
 		                break;
+		              }
+		            }
+		          }
 		          // Traverse incoming arcs
 		          for (InArcIt e(_graph, u); e != INVALID; ++e) {
 		            if (_flow[e] == 1) {
 		              v = _graph.source(e);
 		              switch(heap.state(v)) {
 		              case Heap::PRE_HEAP:
 		                heap.push(v, d - _length[e] - _potential[v]);
 		                _pred[v] = e;
 		                break;
 		              case Heap::IN_HEAP:
 		                nd = d - _length[e] - _potential[v];
 		                if (nd < heap[v]) {
 		                  heap.decrease(v, nd);
 		                  _pred[v] = e;
+		                }
 		                break;
 		              case Heap::POST_HEAP:
 		                break;
+		              }
+		            }
+		          }
+		        }
 		        if (heap.empty()) return false;
 		        // Update potentials of processed nodes
 		        Length t_dist = heap.prio();
 		        for (int i = 0; i < int(_proc_nodes.size()); ++i)
 		          _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
 		        return true;
+		      }
 		    }; //class ResidualDijkstra
 		  private:
 		    // The digraph the algorithm runs on
 		    const Digraph &_graph;
 		    // The length map
 		    const LengthMap &_length;
 		    // Arc map of the current flow
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    // Node map of the current potentials
 		    PotentialMap *_potential;
 		    bool _local_potential;
 		    // The source node
 		    Node _source;
 		    // The target node
 		    Node _target;
 		    // Container to store the found paths
 		    std::vector< SimplePath<Digraph> > paths;
 		    int _path_num;
 		    // The pred arc map
 		    PredMap _pred;
 		    // Implementation of the Dijkstra algorithm for finding augmenting
 		    // shortest paths in the residual network
 		    ResidualDijkstra *_dijkstra;
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param length The length (cost) values of the arcs.
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    Suurballe( const Digraph &digraph,
 		               const LengthMap &length,
 		               Node s, Node t ) :
 		      _graph(digraph), _length(length), _flow(0), _local_flow(false),
 		      _potential(0), _local_potential(false), _source(s), _target(t),
 		      _pred(digraph) {}
 		    /// Destructor.
 		    ~Suurballe() {
 		      if (_local_flow) delete _flow;
 		      if (_local_potential) delete _potential;
 		      delete _dijkstra;
+		    }
 		    /// \brief Set the flow map.
 		    ///
 		    /// This function sets the flow map.
 		    ///
 		    /// The found flow contains only 0 and 1 values. It is the union of
 		    /// the found arc-disjoint paths.
 		    ///
 		    /// \return \c (*this)
 		    Suurballe& flowMap(FlowMap &map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \brief Set the potential map.
 		    ///
 		    /// This function sets the potential map.
 		    ///
 		    /// The potentials provide the dual solution of the underlying
 		    /// minimum cost flow problem.
 		    ///
 		    /// \return \c (*this)
 		    Suurballe& potentialMap(PotentialMap &map) {
 		      if (_local_potential) {
 		        delete _potential;
 		        _local_potential = false;
+		      }
 		      _potential = &map;
 		      return *this;
+		    }
 		    /// \name Execution control
 		    /// The simplest way to execute the algorithm is to call the run()
 		    /// function.
 		    /// \n
 		    /// If you only need the flow that is the union of the found
 		    /// arc-disjoint paths, you may call init() and findFlow().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    ///
 		    /// \param k The number of paths to be found.
 		    ///
 		    /// \return \c k if there are at least \c k arc-disjoint paths from
 		    /// \c s to \c t in the digraph. Otherwise it returns the number of
 		    /// arc-disjoint paths found.
 		    ///
 		    /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
 		    /// shortcut of the following code.
 		    /// \code
 		    ///   s.init();
 		    ///   s.findFlow(k);
 		    ///   s.findPaths();
 		    /// \endcode
 		    int run(int k = 2) {
 		      init();
 		      findFlow(k);
 		      findPaths();
 		      return _path_num;
+		    }
 		    /// \brief Initialize the algorithm.
 		    ///
 		    /// This function initializes the algorithm.
 		    void init() {
 		      // Initialize maps
 		      if (!_flow) {
 		        _flow = new FlowMap(_graph);
 		        _local_flow = true;
+		      }
 		      if (!_potential) {
 		        _potential = new PotentialMap(_graph);
 		        _local_potential = true;
+		      }
 		      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
 		      _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
 		                                        *_potential, _pred,
 		                                        _source, _target );
+		    }
 		    /// \brief Execute the successive shortest path algorithm to find
 		    /// an optimal flow.
 		    ///
 		    /// This function executes the successive shortest path algorithm to
 		    /// find a minimum cost flow, which is the union of \c k or less
 		    /// arc-disjoint paths.
 		    ///
 		    /// \return \c k if there are at least \c k arc-disjoint paths from
 		    /// \c s to \c t in the digraph. Otherwise it returns the number of
 		    /// arc-disjoint paths found.
 		    ///
 		    /// \pre \ref init() must be called before using this function.
 		    int findFlow(int k = 2) {
 		      // Find shortest paths
 		      _path_num = 0;
 		      while (_path_num < k) {
 		        // Run Dijkstra
 		        if (!_dijkstra->run()) break;
 		        ++_path_num;
 		        // Set the flow along the found shortest path
 		        Node u = _target;
 		        Arc e;
 		        while ((e = _pred[u]) != INVALID) {
 		          if (u == _graph.target(e)) {
 		            (*_flow)[e] = 1;
 		            u = _graph.source(e);
 		          } else {
 		            (*_flow)[e] = 0;
 		            u = _graph.target(e);
+		          }
+		        }
+		      }
 		      return _path_num;
+		    }
 		    /// \brief Compute the paths from the flow.
 		    ///
 		    /// This function computes the paths from the flow.
 		    ///
 		    /// \pre \ref init() and \ref findFlow() must be called before using
 		    /// this function.
 		    void findPaths() {
 		      // Create the residual flow map (the union of the paths not found
 		      // so far)
 		      FlowMap res_flow(_graph);
 		      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
 		      paths.clear();
 		      paths.resize(_path_num);
 		      for (int i = 0; i < _path_num; ++i) {
 		        Node n = _source;
 		        while (n != _target) {
 		          OutArcIt e(_graph, n);
 		          for ( ; res_flow[e] == 0; ++e) ;
 		          n = _graph.target(e);
 		          paths[i].addBack(e);
 		          res_flow[e] = 0;
+		        }
+		      }
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.
 		    /// \n The algorithm should be executed before using them.
 		    /// @{
 		    /// \brief Return a const reference to the arc map storing the
 		    /// found flow.
 		    ///
 		    /// This function returns a const reference to the arc map storing
 		    /// the flow that is the union of the found arc-disjoint paths.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    const FlowMap& flowMap() const {
 		      return *_flow;
+		    }
 		    /// \brief Return a const reference to the node map storing the
 		    /// found potentials (the dual solution).
 		    ///
 		    /// This function returns a const reference to the node map storing
 		    /// the found potentials that provide the dual solution of the
 		    /// underlying minimum cost flow problem.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    const PotentialMap& potentialMap() const {
 		      return *_potential;
+		    }
 		    /// \brief Return the flow on the given arc.
 		    ///
 		    /// This function returns the flow on the given arc.
 		    /// It is \c 1 if the arc is involved in one of the found paths,
 		    /// otherwise it is \c 0.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    int flow(const Arc& arc) const {
 		      return (*_flow)[arc];
+		    }
 		    /// \brief Return the potential of the given node.
 		    ///
 		    /// This function returns the potential of the given node.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    Length potential(const Node& node) const {
 		      return (*_potential)[node];
+		    }
 		    /// \brief Return the total length (cost) of the found paths (flow).
 		    ///
 		    /// This function returns the total length (cost) of the found paths
 		    /// (flow). The complexity of the function is \f$ O(e) \f$.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    Length totalLength() const {
 		      Length c = 0;
 		      for (ArcIt e(_graph); e != INVALID; ++e)
 		        c += (*_flow)[e] * _length[e];
 		      return c;
+		    }
 		    /// \brief Return the number of the found paths.
 		    ///
 		    /// This function returns the number of the found paths.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    int pathNum() const {
 		      return _path_num;
+		    }
 		    /// \brief Return a const reference to the specified path.
 		    ///
 		    /// This function returns a const reference to the specified path.
 		    ///
 		    /// \param i The function returns the \c i-th path.
 		    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
 		    ///
 		    /// \pre \ref run() or \ref findPaths() must be called before using
 		    /// this function.
 		    Path path(int i) const {
 		      return paths[i];
+		    }
 		    /// @}
 		  }; //class Suurballe
 		  ///@}
 		} //namespace lemon
 		#endif //LEMON_SUURBALLE_H

0 comments (0 inline)

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	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#ifndef LEMON_BITS_SOLVER_BITS_H
20	20	#define LEMON_BITS_SOLVER_BITS_H
21	21
	22	#include <vector>
	23
22	24	namespace lemon {
23	25
24	26	namespace _solver_bits {
25	27
26	28	class VarIndex {
27	29	private:
28	30	struct ItemT {
29	31	int prev, next;
30	32	int index;
31	33	};
32	34	std::vector<ItemT> items;
33	35	int first_item, last_item, first_free_item;
34	36
35	37	std::vector<int> cross;
36	38
37	39	public:
38	40
39	41	VarIndex()
40	42	: first_item(-1), last_item(-1), first_free_item(-1) {
41	43	}
42	44
43	45	void clear() {
44	46	first_item = -1;
45	47	first_free_item = -1;
46	48	items.clear();
47	49	cross.clear();
48	50	}
49	51
50	52	int addIndex(int idx) {
51	53	int n;
52	54	if (first_free_item == -1) {
53	55	n = items.size();
54	56	items.push_back(ItemT());
55	57	} else {
56	58	n = first_free_item;
57	59	first_free_item = items[n].next;
58	60	if (first_free_item != -1) {
59	61	items[first_free_item].prev = -1;
60	62	}
61	63	}
62	64	items[n].index = idx;
63	65	if (static_cast<int>(cross.size()) <= idx) {
64	66	cross.resize(idx + 1, -1);
65	67	}
66	68	cross[idx] = n;
67	69
68	70	items[n].prev = last_item;
69	71	items[n].next = -1;
70	72	if (last_item != -1) {
71	73	items[last_item].next = n;
72	74	} else {
73	75	first_item = n;
74	76	}
75	77	last_item = n;
76	78
77	79	return n;
78	80	}
79	81
80	82	int addIndex(int idx, int n) {
81	83	while (n >= static_cast<int>(items.size())) {
82	84	items.push_back(ItemT());
83	85	items.back().prev = -1;
84	86	items.back().next = first_free_item;
85	87	if (first_free_item != -1) {
86	88	items[first_free_item].prev = items.size() - 1;
87	89	}
88	90	first_free_item = items.size() - 1;
89	91	}
90	92	if (items[n].next != -1) {
91	93	items[items[n].next].prev = items[n].prev;
92	94	}
93	95	if (items[n].prev != -1) {
94	96	items[items[n].prev].next = items[n].next;
95	97	} else {
96	98	first_free_item = items[n].next;
97	99	}
98	100
99	101	items[n].index = idx;
100	102	if (static_cast<int>(cross.size()) <= idx) {
101	103	cross.resize(idx + 1, -1);
102	104	}
103	105	cross[idx] = n;
104	106
105	107	items[n].prev = last_item;
106	108	items[n].next = -1;
107	109	if (last_item != -1) {
108	110	items[last_item].next = n;
109	111	} else {
110	112	first_item = n;
111	113	}
112	114	last_item = n;
113	115
114	116	return n;
115	117	}
116	118
117	119	void eraseIndex(int idx) {
118	120	int n = cross[idx];
119	121
120	122	if (items[n].prev != -1) {
121	123	items[items[n].prev].next = items[n].next;
122	124	} else {
123	125	first_item = items[n].next;
124	126	}
125	127	if (items[n].next != -1) {
126	128	items[items[n].next].prev = items[n].prev;
127	129	} else {
128	130	last_item = items[n].prev;
129	131	}
130	132
131	133	if (first_free_item != -1) {
132	134	items[first_free_item].prev = n;
133	135	}
134	136	items[n].next = first_free_item;
135	137	items[n].prev = -1;
136	138	first_free_item = n;
137	139
138	140	while (!cross.empty() && cross.back() == -1) {
139	141	cross.pop_back();
140	142	}
141	143	}
142	144
143	145	int maxIndex() const {
144	146	return cross.size() - 1;
145	147	}
146	148
147	149	void shiftIndices(int idx) {
148	150	for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
149	151	cross[i - 1] = cross[i];
150	152	if (cross[i] != -1) {
151	153	--items[cross[i]].index;
152	154	}
153	155	}
154	156	cross.back() = -1;
155	157	cross.pop_back();
156	158	while (!cross.empty() && cross.back() == -1) {
157	159	cross.pop_back();
158	160	}
159	161	}
160	162
161	163	void relocateIndex(int idx, int jdx) {
162	164	cross[idx] = cross[jdx];
163	165	items[cross[jdx]].index = idx;
164	166	cross[jdx] = -1;
165	167
166	168	while (!cross.empty() && cross.back() == -1) {
167	169	cross.pop_back();
168	170	}
169	171	}
170	172
171	173	int operator[](int idx) const {
172	174	return cross[idx];
173	175	}
174	176
175	177	int operator()(int fdx) const {
176	178	return items[fdx].index;
177	179	}
178	180
179	181	void firstItem(int& fdx) const {
180	182	fdx = first_item;
181	183	}
182	184
183	185	void nextItem(int& fdx) const {
184	186	fdx = items[fdx].next;
185	187	}
186	188
187	189	};
188	190	}
189	191	}
190	192
191	193	#endif

RhodeCode

Login to your account