COIN-OR::LEMON - Graph Library

Changeset 877:141f9c0db4a3 in lemon-1.2


Ignore:
Timestamp:
03/06/10 15:35:12 (14 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
878:f802439d2b58, 880:38213abd2911, 909:f112c18bc304
Phase:
public
Message:

Unify the sources (#339)

Files:
89 edited

Legend:

Unmodified
Added
Removed
  • demo/arg_parser_demo.cc

    r842 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7070  // about memory leaks.
    7171  ap.throwOnProblems();
    72  
     72
    7373  // Perform the parsing process
    7474  // (in case of any error it terminates the program)
  • doc/groups.dox

    r874 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/mainpage.dox

    r848 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2626It is a C++ template library providing efficient implementations of common
    2727data structures and algorithms with focus on combinatorial optimization
    28 tasks connected mainly with graphs and networks. 
     28tasks connected mainly with graphs and networks.
    2929
    3030<b>
     
    3636</b>
    3737
    38 The project is maintained by the 
     38The project is maintained by the
    3939<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
    4040Combinatorial Optimization</a> \ref egres
  • doc/min_cost_flow.dox

    r788 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8282   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    8383     then \f$\pi(u)=0\f$.
    84  
     84
    8585Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
    8686\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
     
    120120\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
    121121
    122 It means that the total demand must be less or equal to the 
     122It means that the total demand must be less or equal to the
    123123total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
    124124positive) and all the demands have to be satisfied, but there
  • lemon/adaptors.h

    r787 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    422422      Parent::initialize(digraph);
    423423      _node_filter = &node_filter;
    424       _arc_filter = &arc_filter;     
     424      _arc_filter = &arc_filter;
    425425    }
    426426
     
    509509
    510510    template <typename V>
    511     class NodeMap 
    512       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
    513               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     511    class NodeMap
     512      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     513              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    514514      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    515         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     515        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    516516
    517517    public:
     
    536536
    537537    template <typename V>
    538     class ArcMap 
     538    class ArcMap
    539539      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    540               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     540              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    541541      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    542542        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     
    583583      Parent::initialize(digraph);
    584584      _node_filter = &node_filter;
    585       _arc_filter = &arc_filter;     
     585      _arc_filter = &arc_filter;
    586586    }
    587587
     
    652652
    653653    template <typename V>
    654     class NodeMap 
     654    class NodeMap
    655655      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    656656          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    657       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
     657      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    658658        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    659659
     
    679679
    680680    template <typename V>
    681     class ArcMap 
     681    class ArcMap
    682682      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    683683          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     
    10221022
    10231023    template <typename V>
    1024     class NodeMap 
     1024    class NodeMap
    10251025      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10261026          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1027       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1027      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10281028        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    10291029
     
    10491049
    10501050    template <typename V>
    1051     class ArcMap 
     1051    class ArcMap
    10521052      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10531053          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1054       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1054      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10551055        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    10561056
     
    10761076
    10771077    template <typename V>
    1078     class EdgeMap 
     1078    class EdgeMap
    10791079      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10801080        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1081       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1081      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10821082        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    10831083
     
    11181118    NF* _node_filter;
    11191119    EF* _edge_filter;
    1120     SubGraphBase() 
    1121           : Parent(), _node_filter(0), _edge_filter(0) { }
     1120    SubGraphBase()
     1121          : Parent(), _node_filter(0), _edge_filter(0) { }
    11221122
    11231123    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
     
    12201220
    12211221    template <typename V>
    1222     class NodeMap 
     1222    class NodeMap
    12231223      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12241224          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1225       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1225      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12261226        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    12271227
     
    12471247
    12481248    template <typename V>
    1249     class ArcMap 
     1249    class ArcMap
    12501250      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12511251          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1252       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1252      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12531253        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    12541254
     
    12741274
    12751275    template <typename V>
    1276     class EdgeMap 
     1276    class EdgeMap
    12771277      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12781278        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1279       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
    1280         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1279      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1280        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    12811281
    12821282    public:
     
    15051505#endif
    15061506    typedef DigraphAdaptorExtender<
    1507       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
     1507      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
    15081508                     true> > Parent;
    15091509
     
    15261526    /// Creates a subgraph for the given digraph or graph with the
    15271527    /// given node filter map.
    1528     FilterNodes(GR& graph, NF& node_filter) 
     1528    FilterNodes(GR& graph, NF& node_filter)
    15291529      : Parent(), const_true_map()
    15301530    {
     
    15641564                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
    15651565    public GraphAdaptorExtender<
    1566       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1566      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15671567                   true> > {
    15681568
    15691569    typedef GraphAdaptorExtender<
    1570       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1570      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15711571                   true> > Parent;
    15721572
     
    16541654#endif
    16551655    typedef DigraphAdaptorExtender<
    1656       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
     1656      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
    16571657                     AF, false> > Parent;
    16581658
     
    17621762  class FilterEdges :
    17631763    public GraphAdaptorExtender<
    1764       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
     1764      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
    17651765                   EF, false> > {
    17661766#endif
    17671767    typedef GraphAdaptorExtender<
    1768       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
     1768      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
    17691769                   EF, false> > Parent;
    17701770
     
    17911791    /// Creates a subgraph for the given graph with the given edge
    17921792    /// filter map.
    1793     FilterEdges(GR& graph, EF& edge_filter) 
     1793    FilterEdges(GR& graph, EF& edge_filter)
    17941794      : Parent(), const_true_map() {
    17951795      Parent::initialize(graph, const_true_map, edge_filter);
     
    18591859      bool _forward;
    18601860
    1861       Arc(const Edge& edge, bool forward) 
     1861      Arc(const Edge& edge, bool forward)
    18621862        : _edge(edge), _forward(forward) {}
    18631863
     
    20992099
    21002100      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
    2101         : _forward(*adaptor._digraph, value), 
     2101        : _forward(*adaptor._digraph, value),
    21022102          _backward(*adaptor._digraph, value) {}
    21032103
     
    22172217    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    22182218    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    2219    
     2219
    22202220    typedef EdgeNotifier ArcNotifier;
    22212221    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
     
    27292729           typename FM = CM,
    27302730           typename TL = Tolerance<typename CM::Value> >
    2731   class ResidualDigraph 
     2731  class ResidualDigraph
    27322732    : public SubDigraph<
    27332733        Undirector<const DGR>,
     
    27862786    ResidualDigraph(const DGR& digraph, const CM& capacity,
    27872787                    FM& flow, const TL& tolerance = Tolerance())
    2788       : Parent(), _capacity(&capacity), _flow(&flow), 
     2788      : Parent(), _capacity(&capacity), _flow(&flow),
    27892789        _graph(digraph), _node_filter(),
    27902790        _forward_filter(capacity, flow, tolerance),
     
    28682868
    28692869      /// Constructor
    2870       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
     2870      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
    28712871        : _adaptor(&adaptor) {}
    28722872
     
    34483448    /// to get a node map of the split digraph.
    34493449    /// Its value type is inherited from the first node map type (\c IN).
    3450     /// \tparam IN The type of the node map for the in-nodes. 
     3450    /// \tparam IN The type of the node map for the in-nodes.
    34513451    /// \tparam OUT The type of the node map for the out-nodes.
    34523452    template <typename IN, typename OUT>
  • lemon/arg_parser.cc

    r842 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2727    else throw(ArgParserException(reason));
    2828  }
    29  
    30  
     29
     30
    3131  void ArgParser::_showHelp(void *p)
    3232  {
  • lemon/arg_parser.h

    r842 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4343      INVALID_OPT   /// Invalid combination of options
    4444    };
    45    
     45
    4646  private:
    4747    Reason _reason;
    48    
     48
    4949  public:
    5050    ///Constructor
     
    142142    std::string _command_name;
    143143
    144    
     144
    145145  private:
    146146    //Bind a function to an option.
     
    156156
    157157    bool _exit_on_problems;
    158    
     158
    159159    void _terminate(ArgParserException::Reason reason) const;
    160160
     
    424424
    425425    ///Throw instead of exit in case of problems
    426     void throwOnProblems() 
     426    void throwOnProblems()
    427427    {
    428428      _exit_on_problems=false;
  • lemon/bellman_ford.h

    r844 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3737
    3838  /// \brief Default operation traits for the BellmanFord algorithm class.
    39   /// 
     39  ///
    4040  /// This operation traits class defines all computational operations
    4141  /// and constants that are used in the Bellman-Ford algorithm.
     
    4646  /// \see BellmanFordToleranceOperationTraits
    4747  template <
    48     typename V, 
     48    typename V,
    4949    bool has_inf = std::numeric_limits<V>::has_infinity>
    5050  struct BellmanFordDefaultOperationTraits {
     
    8787    }
    8888  };
    89  
     89
    9090  /// \brief Operation traits for the BellmanFord algorithm class
    9191  /// using tolerance.
     
    140140  template<typename GR, typename LEN>
    141141  struct BellmanFordDefaultTraits {
    142     /// The type of the digraph the algorithm runs on. 
     142    /// The type of the digraph the algorithm runs on.
    143143    typedef GR Digraph;
    144144
     
    159159    /// BellmanFordToleranceOperationTraits
    160160    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    161  
    162     /// \brief The type of the map that stores the last arcs of the 
     161
     162    /// \brief The type of the map that stores the last arcs of the
    163163    /// shortest paths.
    164     /// 
     164    ///
    165165    /// The type of the map that stores the last
    166166    /// arcs of the shortest paths.
     
    169169
    170170    /// \brief Instantiates a \c PredMap.
    171     /// 
    172     /// This function instantiates a \ref PredMap. 
     171    ///
     172    /// This function instantiates a \ref PredMap.
    173173    /// \param g is the digraph to which we would like to define the
    174174    /// \ref PredMap.
     
    185185    /// \brief Instantiates a \c DistMap.
    186186    ///
    187     /// This function instantiates a \ref DistMap. 
    188     /// \param g is the digraph to which we would like to define the 
     187    /// This function instantiates a \ref DistMap.
     188    /// \param g is the digraph to which we would like to define the
    189189    /// \ref DistMap.
    190190    static DistMap *createDistMap(const GR& g) {
     
    193193
    194194  };
    195  
     195
    196196  /// \brief %BellmanFord algorithm class.
    197197  ///
    198198  /// \ingroup shortest_path
    199   /// This class provides an efficient implementation of the Bellman-Ford 
     199  /// This class provides an efficient implementation of the Bellman-Ford
    200200  /// algorithm. The maximum time complexity of the algorithm is
    201201  /// <tt>O(ne)</tt>.
     
    208208  ///
    209209  /// The arc lengths are passed to the algorithm using a
    210   /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
     210  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
    211211  /// kind of length. The type of the length values is determined by the
    212212  /// \ref concepts::ReadMap::Value "Value" type of the length map.
     
    238238    ///The type of the underlying digraph.
    239239    typedef typename TR::Digraph Digraph;
    240    
     240
    241241    /// \brief The type of the arc lengths.
    242242    typedef typename TR::LengthMap::Value Value;
     
    285285    void create_maps() {
    286286      if(!_pred) {
    287         _local_pred = true;
    288         _pred = Traits::createPredMap(*_gr);
     287        _local_pred = true;
     288        _pred = Traits::createPredMap(*_gr);
    289289      }
    290290      if(!_dist) {
    291         _local_dist = true;
    292         _dist = Traits::createDistMap(*_gr);
     291        _local_dist = true;
     292        _dist = Traits::createDistMap(*_gr);
    293293      }
    294294      if(!_mask) {
     
    296296      }
    297297    }
    298    
     298
    299299  public :
    300  
     300
    301301    typedef BellmanFord Create;
    302302
     
    321321    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    322322    template <class T>
    323     struct SetPredMap 
     323    struct SetPredMap
    324324      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
    325325      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
    326326    };
    327    
     327
    328328    template <class T>
    329329    struct SetDistMapTraits : public Traits {
     
    342342    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    343343    template <class T>
    344     struct SetDistMap 
     344    struct SetDistMap
    345345      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
    346346      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
     
    351351      typedef T OperationTraits;
    352352    };
    353    
    354     /// \brief \ref named-templ-param "Named parameter" for setting 
     353
     354    /// \brief \ref named-templ-param "Named parameter" for setting
    355355    /// \c OperationTraits type.
    356356    ///
     
    364364      Create;
    365365    };
    366    
     366
    367367    ///@}
    368368
    369369  protected:
    370    
     370
    371371    BellmanFord() {}
    372372
    373   public:     
    374    
     373  public:
     374
    375375    /// \brief Constructor.
    376376    ///
     
    382382      _pred(0), _local_pred(false),
    383383      _dist(0), _local_dist(false), _mask(0) {}
    384    
     384
    385385    ///Destructor.
    386386    ~BellmanFord() {
     
    409409    BellmanFord &predMap(PredMap &map) {
    410410      if(_local_pred) {
    411         delete _pred;
    412         _local_pred=false;
     411        delete _pred;
     412        _local_pred=false;
    413413      }
    414414      _pred = &map;
     
    427427    BellmanFord &distMap(DistMap &map) {
    428428      if(_local_dist) {
    429         delete _dist;
    430         _local_dist=false;
     429        delete _dist;
     430        _local_dist=false;
    431431      }
    432432      _dist = &map;
     
    446446
    447447    /// \brief Initializes the internal data structures.
    448     /// 
     448    ///
    449449    /// Initializes the internal data structures. The optional parameter
    450450    /// is the initial distance of each node.
     
    452452      create_maps();
    453453      for (NodeIt it(*_gr); it != INVALID; ++it) {
    454         _pred->set(it, INVALID);
    455         _dist->set(it, value);
     454        _pred->set(it, INVALID);
     455        _dist->set(it, value);
    456456      }
    457457      _process.clear();
    458458      if (OperationTraits::less(value, OperationTraits::infinity())) {
    459         for (NodeIt it(*_gr); it != INVALID; ++it) {
    460           _process.push_back(it);
    461           _mask->set(it, true);
    462         }
     459        for (NodeIt it(*_gr); it != INVALID; ++it) {
     460          _process.push_back(it);
     461          _mask->set(it, true);
     462        }
    463463      } else {
    464         for (NodeIt it(*_gr); it != INVALID; ++it) {
    465           _mask->set(it, false);
    466         }
    467       }
    468     }
    469    
     464        for (NodeIt it(*_gr); it != INVALID; ++it) {
     465          _mask->set(it, false);
     466        }
     467      }
     468    }
     469
    470470    /// \brief Adds a new source node.
    471471    ///
     
    475475      _dist->set(source, dst);
    476476      if (!(*_mask)[source]) {
    477         _process.push_back(source);
    478         _mask->set(source, true);
     477        _process.push_back(source);
     478        _mask->set(source, true);
    479479      }
    480480    }
     
    501501    bool processNextRound() {
    502502      for (int i = 0; i < int(_process.size()); ++i) {
    503         _mask->set(_process[i], false);
     503        _mask->set(_process[i], false);
    504504      }
    505505      std::vector<Node> nextProcess;
    506506      std::vector<Value> values(_process.size());
    507507      for (int i = 0; i < int(_process.size()); ++i) {
    508         values[i] = (*_dist)[_process[i]];
     508        values[i] = (*_dist)[_process[i]];
    509509      }
    510510      for (int i = 0; i < int(_process.size()); ++i) {
    511         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
    512           Node target = _gr->target(it);
    513           Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
    514           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    515             _pred->set(target, it);
    516             _dist->set(target, relaxed);
    517             if (!(*_mask)[target]) {
    518               _mask->set(target, true);
    519               nextProcess.push_back(target);
    520             }
    521           }       
    522         }
     511        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
     512          Node target = _gr->target(it);
     513          Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
     514          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     515            _pred->set(target, it);
     516            _dist->set(target, relaxed);
     517            if (!(*_mask)[target]) {
     518              _mask->set(target, true);
     519              nextProcess.push_back(target);
     520            }
     521          }
     522        }
    523523      }
    524524      _process.swap(nextProcess);
     
    542542    bool processNextWeakRound() {
    543543      for (int i = 0; i < int(_process.size()); ++i) {
    544         _mask->set(_process[i], false);
     544        _mask->set(_process[i], false);
    545545      }
    546546      std::vector<Node> nextProcess;
    547547      for (int i = 0; i < int(_process.size()); ++i) {
    548         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
    549           Node target = _gr->target(it);
    550           Value relaxed =
    551             OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
    552           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    553             _pred->set(target, it);
    554             _dist->set(target, relaxed);
    555             if (!(*_mask)[target]) {
    556               _mask->set(target, true);
    557               nextProcess.push_back(target);
    558             }
    559           }       
    560         }
     548        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
     549          Node target = _gr->target(it);
     550          Value relaxed =
     551            OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
     552          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     553            _pred->set(target, it);
     554            _dist->set(target, relaxed);
     555            if (!(*_mask)[target]) {
     556              _mask->set(target, true);
     557              nextProcess.push_back(target);
     558            }
     559          }
     560        }
    561561      }
    562562      _process.swap(nextProcess);
     
    580580      int num = countNodes(*_gr) - 1;
    581581      for (int i = 0; i < num; ++i) {
    582         if (processNextWeakRound()) break;
     582        if (processNextWeakRound()) break;
    583583      }
    584584    }
     
    592592    /// if the digraph contains cycles with negative total length.
    593593    ///
    594     /// The algorithm computes 
     594    /// The algorithm computes
    595595    /// - the shortest path tree (forest),
    596596    /// - the distance of each node from the root(s).
    597     /// 
     597    ///
    598598    /// \return \c false if there is a negative cycle in the digraph.
    599599    ///
    600600    /// \pre init() must be called and at least one root node should be
    601     /// added with addSource() before using this function. 
     601    /// added with addSource() before using this function.
    602602    bool checkedStart() {
    603603      int num = countNodes(*_gr);
    604604      for (int i = 0; i < num; ++i) {
    605         if (processNextWeakRound()) return true;
     605        if (processNextWeakRound()) return true;
    606606      }
    607607      return _process.empty();
     
    627627    ///
    628628    /// \pre init() must be called and at least one root node should be
    629     /// added with addSource() before using this function. 
     629    /// added with addSource() before using this function.
    630630    void limitedStart(int num) {
    631631      for (int i = 0; i < num; ++i) {
    632         if (processNextRound()) break;
    633       }
    634     }
    635    
     632        if (processNextRound()) break;
     633      }
     634    }
     635
    636636    /// \brief Runs the algorithm from the given root node.
    637     ///   
     637    ///
    638638    /// This method runs the Bellman-Ford algorithm from the given root
    639639    /// node \c s in order to compute the shortest path to each node.
     
    654654      start();
    655655    }
    656    
     656
    657657    /// \brief Runs the algorithm from the given root node with arc
    658658    /// number limit.
    659     ///   
     659    ///
    660660    /// This method runs the Bellman-Ford algorithm from the given root
    661661    /// node \c s in order to compute the shortest path distance for each
     
    683683      limitedStart(num);
    684684    }
    685    
     685
    686686    ///@}
    687687
     
    698698      ///
    699699      /// Constructor for getting the active nodes of the given BellmanFord
    700       /// instance. 
     700      /// instance.
    701701      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
    702702      {
     
    712712      ///
    713713      /// Conversion to \c Node.
    714       operator Node() const { 
     714      operator Node() const {
    715715        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
    716716      }
     
    721721      ActiveIt& operator++() {
    722722        --_index;
    723         return *this; 
    724       }
    725 
    726       bool operator==(const ActiveIt& it) const { 
    727         return static_cast<Node>(*this) == static_cast<Node>(it); 
    728       }
    729       bool operator!=(const ActiveIt& it) const { 
    730         return static_cast<Node>(*this) != static_cast<Node>(it); 
    731       }
    732       bool operator<(const ActiveIt& it) const { 
    733         return static_cast<Node>(*this) < static_cast<Node>(it); 
    734       }
    735      
     723        return *this;
     724      }
     725
     726      bool operator==(const ActiveIt& it) const {
     727        return static_cast<Node>(*this) == static_cast<Node>(it);
     728      }
     729      bool operator!=(const ActiveIt& it) const {
     730        return static_cast<Node>(*this) != static_cast<Node>(it);
     731      }
     732      bool operator<(const ActiveIt& it) const {
     733        return static_cast<Node>(*this) < static_cast<Node>(it);
     734      }
     735
    736736    private:
    737737      const BellmanFord* _algorithm;
    738738      int _index;
    739739    };
    740    
     740
    741741    /// \name Query Functions
    742742    /// The result of the Bellman-Ford algorithm can be obtained using these
    743743    /// functions.\n
    744744    /// Either \ref run() or \ref init() should be called before using them.
    745    
     745
    746746    ///@{
    747747
    748748    /// \brief The shortest path to the given node.
    749     ///   
     749    ///
    750750    /// Gives back the shortest path to the given node from the root(s).
    751751    ///
     
    758758      return Path(*_gr, *_pred, t);
    759759    }
    760          
     760
    761761    /// \brief The distance of the given node from the root(s).
    762762    ///
     
    798798    /// \pre Either \ref run() or \ref init() must be called before
    799799    /// using this function.
    800     Node predNode(Node v) const { 
    801       return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 
    802     }
    803    
     800    Node predNode(Node v) const {
     801      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
     802    }
     803
    804804    /// \brief Returns a const reference to the node map that stores the
    805805    /// distances of the nodes.
     
    811811    /// using this function.
    812812    const DistMap &distMap() const { return *_dist;}
    813  
     813
    814814    /// \brief Returns a const reference to the node map that stores the
    815815    /// predecessor arcs.
     
    821821    /// using this function.
    822822    const PredMap &predMap() const { return *_pred; }
    823  
     823
    824824    /// \brief Checks if a node is reached from the root(s).
    825825    ///
     
    833833
    834834    /// \brief Gives back a negative cycle.
    835     ///   
     835    ///
    836836    /// This function gives back a directed cycle with negative total
    837837    /// length if the algorithm has already found one.
     
    860860      return cycle;
    861861    }
    862    
     862
    863863    ///@}
    864864  };
    865  
     865
    866866  /// \brief Default traits class of bellmanFord() function.
    867867  ///
     
    871871  template <typename GR, typename LEN>
    872872  struct BellmanFordWizardDefaultTraits {
    873     /// The type of the digraph the algorithm runs on. 
     873    /// The type of the digraph the algorithm runs on.
    874874    typedef GR Digraph;
    875875
     
    893893    /// \brief The type of the map that stores the last
    894894    /// arcs of the shortest paths.
    895     /// 
     895    ///
    896896    /// The type of the map that stores the last arcs of the shortest paths.
    897897    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     
    899899
    900900    /// \brief Instantiates a \c PredMap.
    901     /// 
     901    ///
    902902    /// This function instantiates a \ref PredMap.
    903903    /// \param g is the digraph to which we would like to define the
     
    915915    /// \brief Instantiates a \c DistMap.
    916916    ///
    917     /// This function instantiates a \ref DistMap. 
     917    /// This function instantiates a \ref DistMap.
    918918    /// \param g is the digraph to which we would like to define the
    919919    /// \ref DistMap.
     
    928928    typedef lemon::Path<Digraph> Path;
    929929  };
    930  
     930
    931931  /// \brief Default traits class used by BellmanFordWizard.
    932932  ///
     
    935935  /// \tparam LEN The type of the length map.
    936936  template <typename GR, typename LEN>
    937   class BellmanFordWizardBase 
     937  class BellmanFordWizardBase
    938938    : public BellmanFordWizardDefaultTraits<GR, LEN> {
    939939
     
    958958    public:
    959959    /// Constructor.
    960    
     960
    961961    /// This constructor does not require parameters, it initiates
    962962    /// all of the attributes to default values \c 0.
     
    965965
    966966    /// Constructor.
    967    
     967
    968968    /// This constructor requires two parameters,
    969969    /// others are initiated to \c 0.
    970970    /// \param gr The digraph the algorithm runs on.
    971971    /// \param len The length map.
    972     BellmanFordWizardBase(const GR& gr, 
    973                           const LEN& len) :
    974       _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 
    975       _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 
     972    BellmanFordWizardBase(const GR& gr,
     973                          const LEN& len) :
     974      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
     975      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
    976976      _pred(0), _dist(0), _path(0), _di(0) {}
    977977
    978978  };
    979  
     979
    980980  /// \brief Auxiliary class for the function-type interface of the
    981981  /// \ref BellmanFord "Bellman-Ford" algorithm.
     
    10021002    typedef typename Digraph::Arc Arc;
    10031003    typedef typename Digraph::OutArcIt ArcIt;
    1004    
     1004
    10051005    typedef typename TR::LengthMap LengthMap;
    10061006    typedef typename LengthMap::Value Value;
     
    10191019    /// \param gr The digraph the algorithm runs on.
    10201020    /// \param len The length map.
    1021     BellmanFordWizard(const Digraph& gr, const LengthMap& len) 
     1021    BellmanFordWizard(const Digraph& gr, const LengthMap& len)
    10221022      : TR(gr, len) {}
    10231023
     
    10281028
    10291029    /// \brief Runs the Bellman-Ford algorithm from the given source node.
    1030     ///   
     1030    ///
    10311031    /// This method runs the Bellman-Ford algorithm from the given source
    10321032    /// node in order to compute the shortest path to each node.
    10331033    void run(Node s) {
    1034       BellmanFord<Digraph,LengthMap,TR> 
    1035         bf(*reinterpret_cast<const Digraph*>(Base::_graph),
     1034      BellmanFord<Digraph,LengthMap,TR>
     1035        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
    10361036           *reinterpret_cast<const LengthMap*>(Base::_length));
    10371037      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     
    10681068      SetPredMapBase(const TR &b) : TR(b) {}
    10691069    };
    1070    
     1070
    10711071    /// \brief \ref named-templ-param "Named parameter" for setting
    10721072    /// the predecessor map.
     
    10791079      return BellmanFordWizard<SetPredMapBase<T> >(*this);
    10801080    }
    1081    
     1081
    10821082    template<class T>
    10831083    struct SetDistMapBase : public Base {
     
    10861086      SetDistMapBase(const TR &b) : TR(b) {}
    10871087    };
    1088    
     1088
    10891089    /// \brief \ref named-templ-param "Named parameter" for setting
    10901090    /// the distance map.
     
    11271127      return *this;
    11281128    }
    1129    
     1129
    11301130  };
    1131  
     1131
    11321132  /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
    11331133  /// algorithm.
     
    11371137  /// algorithm.
    11381138  ///
    1139   /// This function also has several \ref named-templ-func-param 
    1140   /// "named parameters", they are declared as the members of class 
     1139  /// This function also has several \ref named-templ-func-param
     1140  /// "named parameters", they are declared as the members of class
    11411141  /// \ref BellmanFordWizard.
    11421142  /// The following examples show how to use these parameters.
     
    11551155  BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
    11561156  bellmanFord(const GR& digraph,
    1157               const LEN& length)
     1157              const LEN& length)
    11581158  {
    11591159    return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
  • lemon/bfs.h

    r825 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8383
    8484    ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8687    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8788    ///Instantiates a \c ReachedMap.
     
    272273    ///\ref named-templ-param "Named parameter" for setting
    273274    ///\c ReachedMap type.
    274     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     275    ///It must conform to
     276    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    275277    template <class T>
    276278    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    873875
    874876    ///The type of the map that indicates which nodes are reached.
    875     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     877    ///It must conform to
     878    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    876879    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    877880    ///Instantiates a ReachedMap.
     
    12661269    ///
    12671270    /// The type of the map that indicates which nodes are reached.
    1268     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1271    /// It must conform to
     1272    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12691273    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12701274
  • lemon/binomial_heap.h

    r855 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    259259      int p=_data[i].parent;
    260260      _data[i].prio=value;
    261      
     261
    262262      while( p!=-1 && _comp(value, _data[p].prio) ) {
    263263        _data[i].name=_data[p].name;
     
    323323
    324324  private:
    325    
     325
    326326    // Find the minimum of the roots
    327327    int findMin() {
     
    351351      }
    352352      if( _data[_head].right_neighbor==-1 ) return;
    353      
     353
    354354      int x=_head;
    355355      int x_prev=-1, x_next=_data[x].right_neighbor;
     
    385385      int curr=_data.size();
    386386      _data.push_back(Store());
    387      
     387
    388388      while( p!=-1 || q!=-1 ) {
    389389        if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
     
    398398        }
    399399      }
    400      
     400
    401401      _head=_data.back().right_neighbor;
    402402      _data.pop_back();
  • lemon/bits/array_map.h

    r617 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7171
    7272  private:
    73  
     73
    7474    // The MapBase of the Map which imlements the core regisitry function.
    7575    typedef typename Notifier::ObserverBase Parent;
  • lemon/bits/default_map.h

    r627 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    158158  public:
    159159    typedef DefaultMap<_Graph, _Item, _Value> Map;
    160    
     160
    161161    typedef typename Parent::GraphType GraphType;
    162162    typedef typename Parent::Value Value;
  • lemon/bits/edge_set_extender.h

    r685 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6464    Node oppositeNode(const Node &n, const Arc &e) const {
    6565      if (n == Parent::source(e))
    66         return Parent::target(e);
     66        return Parent::target(e);
    6767      else if(n==Parent::target(e))
    68         return Parent::source(e);
     68        return Parent::source(e);
    6969      else
    70         return INVALID;
     70        return INVALID;
    7171    }
    7272
     
    9292    // Iterable extensions
    9393
    94     class NodeIt : public Node { 
     94    class NodeIt : public Node {
    9595      const Digraph* digraph;
    9696    public:
     
    101101
    102102      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
    103         _graph.first(static_cast<Node&>(*this));
    104       }
    105 
    106       NodeIt(const Digraph& _graph, const Node& node) 
    107         : Node(node), digraph(&_graph) {}
    108 
    109       NodeIt& operator++() { 
    110         digraph->next(*this);
    111         return *this;
    112       }
    113 
    114     };
    115 
    116 
    117     class ArcIt : public Arc { 
     103        _graph.first(static_cast<Node&>(*this));
     104      }
     105
     106      NodeIt(const Digraph& _graph, const Node& node)
     107        : Node(node), digraph(&_graph) {}
     108
     109      NodeIt& operator++() {
     110        digraph->next(*this);
     111        return *this;
     112      }
     113
     114    };
     115
     116
     117    class ArcIt : public Arc {
    118118      const Digraph* digraph;
    119119    public:
     
    124124
    125125      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
    126         _graph.first(static_cast<Arc&>(*this));
    127       }
    128 
    129       ArcIt(const Digraph& _graph, const Arc& e) : 
    130         Arc(e), digraph(&_graph) { }
    131 
    132       ArcIt& operator++() { 
    133         digraph->next(*this);
    134         return *this;
    135       }
    136 
    137     };
    138 
    139 
    140     class OutArcIt : public Arc { 
     126        _graph.first(static_cast<Arc&>(*this));
     127      }
     128
     129      ArcIt(const Digraph& _graph, const Arc& e) :
     130        Arc(e), digraph(&_graph) { }
     131
     132      ArcIt& operator++() {
     133        digraph->next(*this);
     134        return *this;
     135      }
     136
     137    };
     138
     139
     140    class OutArcIt : public Arc {
    141141      const Digraph* digraph;
    142142    public:
     
    146146      OutArcIt(Invalid i) : Arc(i) { }
    147147
    148       OutArcIt(const Digraph& _graph, const Node& node) 
    149         : digraph(&_graph) {
    150         _graph.firstOut(*this, node);
    151       }
    152 
    153       OutArcIt(const Digraph& _graph, const Arc& arc) 
    154         : Arc(arc), digraph(&_graph) {}
    155 
    156       OutArcIt& operator++() { 
    157         digraph->nextOut(*this);
    158         return *this;
    159       }
    160 
    161     };
    162 
    163 
    164     class InArcIt : public Arc { 
     148      OutArcIt(const Digraph& _graph, const Node& node)
     149        : digraph(&_graph) {
     150        _graph.firstOut(*this, node);
     151      }
     152
     153      OutArcIt(const Digraph& _graph, const Arc& arc)
     154        : Arc(arc), digraph(&_graph) {}
     155
     156      OutArcIt& operator++() {
     157        digraph->nextOut(*this);
     158        return *this;
     159      }
     160
     161    };
     162
     163
     164    class InArcIt : public Arc {
    165165      const Digraph* digraph;
    166166    public:
     
    170170      InArcIt(Invalid i) : Arc(i) { }
    171171
    172       InArcIt(const Digraph& _graph, const Node& node) 
    173         : digraph(&_graph) {
    174         _graph.firstIn(*this, node);
    175       }
    176 
    177       InArcIt(const Digraph& _graph, const Arc& arc) : 
    178         Arc(arc), digraph(&_graph) {}
    179 
    180       InArcIt& operator++() { 
    181         digraph->nextIn(*this);
    182         return *this;
     172      InArcIt(const Digraph& _graph, const Node& node)
     173        : digraph(&_graph) {
     174        _graph.firstIn(*this, node);
     175      }
     176
     177      InArcIt(const Digraph& _graph, const Arc& arc) :
     178        Arc(arc), digraph(&_graph) {}
     179
     180      InArcIt& operator++() {
     181        digraph->nextIn(*this);
     182        return *this;
    183183      }
    184184
     
    216216
    217217    // Mappable extension
    218    
     218
    219219    template <typename _Value>
    220     class ArcMap 
     220    class ArcMap
    221221      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    222222      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    223223
    224224    public:
    225       explicit ArcMap(const Digraph& _g) 
    226         : Parent(_g) {}
    227       ArcMap(const Digraph& _g, const _Value& _v) 
    228         : Parent(_g, _v) {}
     225      explicit ArcMap(const Digraph& _g)
     226        : Parent(_g) {}
     227      ArcMap(const Digraph& _g, const _Value& _v)
     228        : Parent(_g, _v) {}
    229229
    230230      ArcMap& operator=(const ArcMap& cmap) {
    231         return operator=<ArcMap>(cmap);
     231        return operator=<ArcMap>(cmap);
    232232      }
    233233
     
    235235      ArcMap& operator=(const CMap& cmap) {
    236236        Parent::operator=(cmap);
    237         return *this;
     237        return *this;
    238238      }
    239239
     
    248248      return arc;
    249249    }
    250    
     250
    251251    void clear() {
    252252      notifier(Arc()).clear();
     
    311311    Node oppositeNode(const Node &n, const Edge &e) const {
    312312      if( n == Parent::u(e))
    313         return Parent::v(e);
     313        return Parent::v(e);
    314314      else if( n == Parent::v(e))
    315         return Parent::u(e);
     315        return Parent::u(e);
    316316      else
    317         return INVALID;
     317        return INVALID;
    318318    }
    319319
     
    339339
    340340    using Parent::notifier;
    341    
     341
    342342    ArcNotifier& notifier(Arc) const {
    343343      return arc_notifier;
     
    349349
    350350
    351     class NodeIt : public Node { 
     351    class NodeIt : public Node {
    352352      const Graph* graph;
    353353    public:
     
    358358
    359359      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    360         _graph.first(static_cast<Node&>(*this));
    361       }
    362 
    363       NodeIt(const Graph& _graph, const Node& node) 
    364         : Node(node), graph(&_graph) {}
    365 
    366       NodeIt& operator++() { 
    367         graph->next(*this);
    368         return *this;
    369       }
    370 
    371     };
    372 
    373 
    374     class ArcIt : public Arc { 
     360        _graph.first(static_cast<Node&>(*this));
     361      }
     362
     363      NodeIt(const Graph& _graph, const Node& node)
     364        : Node(node), graph(&_graph) {}
     365
     366      NodeIt& operator++() {
     367        graph->next(*this);
     368        return *this;
     369      }
     370
     371    };
     372
     373
     374    class ArcIt : public Arc {
    375375      const Graph* graph;
    376376    public:
     
    381381
    382382      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
    383         _graph.first(static_cast<Arc&>(*this));
    384       }
    385 
    386       ArcIt(const Graph& _graph, const Arc& e) : 
    387         Arc(e), graph(&_graph) { }
    388 
    389       ArcIt& operator++() { 
    390         graph->next(*this);
    391         return *this;
    392       }
    393 
    394     };
    395 
    396 
    397     class OutArcIt : public Arc { 
     383        _graph.first(static_cast<Arc&>(*this));
     384      }
     385
     386      ArcIt(const Graph& _graph, const Arc& e) :
     387        Arc(e), graph(&_graph) { }
     388
     389      ArcIt& operator++() {
     390        graph->next(*this);
     391        return *this;
     392      }
     393
     394    };
     395
     396
     397    class OutArcIt : public Arc {
    398398      const Graph* graph;
    399399    public:
     
    403403      OutArcIt(Invalid i) : Arc(i) { }
    404404
    405       OutArcIt(const Graph& _graph, const Node& node) 
    406         : graph(&_graph) {
    407         _graph.firstOut(*this, node);
    408       }
    409 
    410       OutArcIt(const Graph& _graph, const Arc& arc) 
    411         : Arc(arc), graph(&_graph) {}
    412 
    413       OutArcIt& operator++() { 
    414         graph->nextOut(*this);
    415         return *this;
    416       }
    417 
    418     };
    419 
    420 
    421     class InArcIt : public Arc { 
     405      OutArcIt(const Graph& _graph, const Node& node)
     406        : graph(&_graph) {
     407        _graph.firstOut(*this, node);
     408      }
     409
     410      OutArcIt(const Graph& _graph, const Arc& arc)
     411        : Arc(arc), graph(&_graph) {}
     412
     413      OutArcIt& operator++() {
     414        graph->nextOut(*this);
     415        return *this;
     416      }
     417
     418    };
     419
     420
     421    class InArcIt : public Arc {
    422422      const Graph* graph;
    423423    public:
     
    427427      InArcIt(Invalid i) : Arc(i) { }
    428428
    429       InArcIt(const Graph& _graph, const Node& node) 
    430         : graph(&_graph) {
    431         _graph.firstIn(*this, node);
    432       }
    433 
    434       InArcIt(const Graph& _graph, const Arc& arc) : 
    435         Arc(arc), graph(&_graph) {}
    436 
    437       InArcIt& operator++() { 
    438         graph->nextIn(*this);
    439         return *this;
    440       }
    441 
    442     };
    443 
    444 
    445     class EdgeIt : public Parent::Edge { 
     429      InArcIt(const Graph& _graph, const Node& node)
     430        : graph(&_graph) {
     431        _graph.firstIn(*this, node);
     432      }
     433
     434      InArcIt(const Graph& _graph, const Arc& arc) :
     435        Arc(arc), graph(&_graph) {}
     436
     437      InArcIt& operator++() {
     438        graph->nextIn(*this);
     439        return *this;
     440      }
     441
     442    };
     443
     444
     445    class EdgeIt : public Parent::Edge {
    446446      const Graph* graph;
    447447    public:
     
    452452
    453453      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    454         _graph.first(static_cast<Edge&>(*this));
    455       }
    456 
    457       EdgeIt(const Graph& _graph, const Edge& e) : 
    458         Edge(e), graph(&_graph) { }
    459 
    460       EdgeIt& operator++() { 
    461         graph->next(*this);
    462         return *this;
     454        _graph.first(static_cast<Edge&>(*this));
     455      }
     456
     457      EdgeIt(const Graph& _graph, const Edge& e) :
     458        Edge(e), graph(&_graph) { }
     459
     460      EdgeIt& operator++() {
     461        graph->next(*this);
     462        return *this;
    463463      }
    464464
     
    476476
    477477      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    478         _graph.firstInc(*this, direction, n);
     478        _graph.firstInc(*this, direction, n);
    479479      }
    480480
    481481      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
    482         : graph(&_graph), Edge(ue) {
    483         direction = (_graph.source(ue) == n);
     482        : graph(&_graph), Edge(ue) {
     483        direction = (_graph.source(ue) == n);
    484484      }
    485485
    486486      IncEdgeIt& operator++() {
    487         graph->nextInc(*this, direction);
    488         return *this;
     487        graph->nextInc(*this, direction);
     488        return *this;
    489489      }
    490490    };
     
    533533
    534534    template <typename _Value>
    535     class ArcMap 
     535    class ArcMap
    536536      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    537537      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    538538
    539539    public:
    540       explicit ArcMap(const Graph& _g) 
    541         : Parent(_g) {}
    542       ArcMap(const Graph& _g, const _Value& _v) 
    543         : Parent(_g, _v) {}
     540      explicit ArcMap(const Graph& _g)
     541        : Parent(_g) {}
     542      ArcMap(const Graph& _g, const _Value& _v)
     543        : Parent(_g, _v) {}
    544544
    545545      ArcMap& operator=(const ArcMap& cmap) {
    546         return operator=<ArcMap>(cmap);
     546        return operator=<ArcMap>(cmap);
    547547      }
    548548
     
    550550      ArcMap& operator=(const CMap& cmap) {
    551551        Parent::operator=(cmap);
    552         return *this;
     552        return *this;
    553553      }
    554554
     
    557557
    558558    template <typename _Value>
    559     class EdgeMap 
     559    class EdgeMap
    560560      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    561561      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    562562
    563563    public:
    564       explicit EdgeMap(const Graph& _g) 
    565         : Parent(_g) {}
    566 
    567       EdgeMap(const Graph& _g, const _Value& _v) 
    568         : Parent(_g, _v) {}
     564      explicit EdgeMap(const Graph& _g)
     565        : Parent(_g) {}
     566
     567      EdgeMap(const Graph& _g, const _Value& _v)
     568        : Parent(_g, _v) {}
    569569
    570570      EdgeMap& operator=(const EdgeMap& cmap) {
    571         return operator=<EdgeMap>(cmap);
     571        return operator=<EdgeMap>(cmap);
    572572      }
    573573
     
    575575      EdgeMap& operator=(const CMap& cmap) {
    576576        Parent::operator=(cmap);
    577         return *this;
     577        return *this;
    578578      }
    579579
     
    592592      return edge;
    593593    }
    594    
     594
    595595    void clear() {
    596596      notifier(Arc()).clear();
     
    618618      arc_notifier.clear();
    619619    }
    620    
     620
    621621  };
    622622
  • lemon/bits/solver_bits.h

    r519 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/windows.cc

    r483 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9797      GetSystemTime(&time);
    9898      char buf1[11], buf2[9], buf3[5];
    99           if (GetDateFormat(MY_LOCALE, 0, &time,
     99          if (GetDateFormat(MY_LOCALE, 0, &time,
    100100                        ("ddd MMM dd"), buf1, 11) &&
    101101          GetTimeFormat(MY_LOCALE, 0, &time,
  • lemon/bucket_heap.h

    r711 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    385385  ///
    386386  /// Note that this implementation does not conform to the
    387   /// \ref concepts::Heap "heap concept" due to the lack of some 
     387  /// \ref concepts::Heap "heap concept" due to the lack of some
    388388  /// functionality.
    389389  ///
  • lemon/capacity_scaling.h

    r863 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    134134      UNBOUNDED
    135135    };
    136  
     136
    137137  private:
    138138
     
    185185
    186186  public:
    187  
     187
    188188    /// \brief Constant for infinite upper bounds (capacities).
    189189    ///
     
    212212      CostVector &_pi;
    213213      IntVector &_pred;
    214      
     214
    215215      IntVector _proc_nodes;
    216216      CostVector _dist;
    217      
     217
    218218    public:
    219219
     
    440440      return *this;
    441441    }
    442    
     442
    443443    /// @}
    444444
     
    576576      _cost.resize(_res_arc_num);
    577577      _supply.resize(_node_num);
    578      
     578
    579579      _res_cap.resize(_res_arc_num);
    580580      _pi.resize(_node_num);
     
    620620        _reverse[bi] = fi;
    621621      }
    622      
     622
    623623      // Reset parameters
    624624      resetParams();
     
    729729      }
    730730      if (_sum_supply > 0) return INFEASIBLE;
    731      
     731
    732732      // Initialize vectors
    733733      for (int i = 0; i != _root; ++i) {
     
    777777        }
    778778      }
    779      
     779
    780780      // Handle GEQ supply type
    781781      if (_sum_supply < 0) {
     
    845845        for (int i = 0; i != _node_num; ++i) {
    846846          _pi[i] -= pr;
    847         }       
    848       }
    849      
     847        }
     848      }
     849
    850850      return pt;
    851851    }
  • lemon/cbc.h

    r746 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    122122    int _message_level;
    123123
    124    
     124
    125125
    126126  };
  • lemon/circulation.h

    r825 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6060    /// \brief The type of supply map.
    6161    ///
    62     /// The type of the map that stores the signed supply values of the 
    63     /// nodes. 
     62    /// The type of the map that stores the signed supply values of the
     63    /// nodes.
    6464    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    6565    typedef SM SupplyMap;
     
    142142     \geq sup(u) \quad \forall u\in V, \f]
    143143     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
    144      
     144
    145145     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    146146     zero or negative in order to have a feasible solution (since the sum
     
    152152     constraints have to be satisfied with equality, i.e. all demands
    153153     have to be satisfied and all supplies have to be used.
    154      
     154
    155155     If you need the opposite inequalities in the supply/demand constraints
    156156     (i.e. the total demand is less than the total supply and all the demands
     
    338338    /// \param graph The digraph the algorithm runs on.
    339339    /// \param lower The lower bounds for the flow values on the arcs.
    340     /// \param upper The upper bounds (capacities) for the flow values 
     340    /// \param upper The upper bounds (capacities) for the flow values
    341341    /// on the arcs.
    342342    /// \param supply The signed supply values of the nodes.
  • lemon/clp.cc

    r746 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/clp.h

    r746 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    139139
    140140    virtual void _messageLevel(MessageLevel);
    141    
     141
    142142  public:
    143143
  • lemon/concepts/digraph.h

    r786 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    435435      private:
    436436        ///Copy constructor
    437         NodeMap(const NodeMap& nm) : 
     437        NodeMap(const NodeMap& nm) :
    438438          ReferenceMap<Node, T, T&, const T&>(nm) { }
    439439        ///Assignment operator
  • lemon/concepts/graph.h

    r786 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4444    /// run properly, of course.
    4545    /// An actual graph implementation like \ref ListGraph or
    46     /// \ref SmartGraph may have additional functionality.   
     46    /// \ref SmartGraph may have additional functionality.
    4747    ///
    4848    /// The undirected graphs also fulfill the concept of \ref Digraph
     
    8686      ///
    8787      /// Undirected graphs should be tagged with \c UndirectedTag.
    88       /// 
     88      ///
    8989      /// This tag helps the \c enable_if technics to make compile time
    9090      /// specializations for undirected graphs.
     
    361361
    362362        /// Converison to \c Edge
    363        
     363
    364364        /// Converison to \c Edge.
    365365        ///
  • lemon/concepts/graph_components.h

    r786 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3939    /// \note This class is a template class so that we can use it to
    4040    /// create graph skeleton classes. The reason for this is that \c Node
    41     /// and \c Arc (or \c Edge) types should \e not derive from the same 
     41    /// and \c Arc (or \c Edge) types should \e not derive from the same
    4242    /// base class. For \c Node you should instantiate it with character
    4343    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
     
    9090      ///
    9191      /// This operator defines an ordering of the items.
    92       /// It makes possible to use graph item types as key types in 
     92      /// It makes possible to use graph item types as key types in
    9393      /// associative containers (e.g. \c std::map).
    9494      ///
     
    123123    /// This class describes the base interface of directed graph types.
    124124    /// All digraph %concepts have to conform to this class.
    125     /// It just provides types for nodes and arcs and functions 
     125    /// It just provides types for nodes and arcs and functions
    126126    /// to get the source and the target nodes of arcs.
    127127    class BaseDigraphComponent {
     
    427427    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
    428428    ///
    429     /// This class describes the concept of \c NodeIt, \c ArcIt and 
     429    /// This class describes the concept of \c NodeIt, \c ArcIt and
    430430    /// \c EdgeIt subtypes of digraph and graph types.
    431431    template <typename GR, typename Item>
     
    467467      /// next item.
    468468      GraphItemIt& operator++() { return *this; }
    469  
     469
    470470      /// \brief Equality operator
    471471      ///
     
    502502    };
    503503
    504     /// \brief Concept class for \c InArcIt, \c OutArcIt and 
     504    /// \brief Concept class for \c InArcIt, \c OutArcIt and
    505505    /// \c IncEdgeIt types.
    506506    ///
    507     /// This class describes the concept of \c InArcIt, \c OutArcIt 
     507    /// This class describes the concept of \c InArcIt, \c OutArcIt
    508508    /// and \c IncEdgeIt subtypes of digraph and graph types.
    509509    ///
    510510    /// \note Since these iterator classes do not inherit from the same
    511511    /// base class, there is an additional template parameter (selector)
    512     /// \c sel. For \c InArcIt you should instantiate it with character 
     512    /// \c sel. For \c InArcIt you should instantiate it with character
    513513    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
    514514    template <typename GR,
     
    531531      GraphIncIt(const GraphIncIt& it) : Item(it) {}
    532532
    533       /// \brief Constructor that sets the iterator to the first 
     533      /// \brief Constructor that sets the iterator to the first
    534534      /// incoming or outgoing arc.
    535535      ///
    536       /// Constructor that sets the iterator to the first arc 
     536      /// Constructor that sets the iterator to the first arc
    537537      /// incoming to or outgoing from the given node.
    538538      explicit GraphIncIt(const GR&, const Base&) {}
     
    805805      /// \brief Return the first edge incident to the given node.
    806806      ///
    807       /// This function gives back the first edge incident to the given 
     807      /// This function gives back the first edge incident to the given
    808808      /// node. The bool parameter gives back the direction for which the
    809       /// source node of the directed arc representing the edge is the 
     809      /// source node of the directed arc representing the edge is the
    810810      /// given node.
    811811      void firstInc(Edge&, bool&, const Node&) const {}
     
    814814      /// given node.
    815815      ///
    816       /// This function gives back the next edge incident to the given 
     816      /// This function gives back the next edge incident to the given
    817817      /// node. The bool parameter should be used as \c firstInc() use it.
    818818      void nextInc(Edge&, bool&) const {}
     
    991991    ///
    992992    /// This class describes the concept of standard graph maps, i.e.
    993     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 
     993    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
    994994    /// graph types, which can be used for associating data to graph items.
    995995    /// The standard graph maps must conform to the ReferenceMap concept.
     
    10461046          _Map m1(g);
    10471047          _Map m2(g,t);
    1048          
     1048
    10491049          // Copy constructor
    10501050          // _Map m3(m);
     
    10691069    ///
    10701070    /// This class describes the interface of mappable directed graphs.
    1071     /// It extends \ref BaseDigraphComponent with the standard digraph 
     1071    /// It extends \ref BaseDigraphComponent with the standard digraph
    10721072    /// map classes, namely \c NodeMap and \c ArcMap.
    10731073    /// This concept is part of the Digraph concept.
     
    12061206    ///
    12071207    /// This class describes the interface of mappable undirected graphs.
    1208     /// It extends \ref MappableDigraphComponent with the standard graph 
     1208    /// It extends \ref MappableDigraphComponent with the standard graph
    12091209    /// map class for edges (\c EdgeMap).
    12101210    /// This concept is part of the Graph concept.
     
    12911291    ///
    12921292    /// This class describes the interface of extendable directed graphs.
    1293     /// It extends \ref BaseDigraphComponent with functions for adding 
     1293    /// It extends \ref BaseDigraphComponent with functions for adding
    12941294    /// nodes and arcs to the digraph.
    12951295    /// This concept requires \ref AlterableDigraphComponent.
     
    13351335    ///
    13361336    /// This class describes the interface of extendable undirected graphs.
    1337     /// It extends \ref BaseGraphComponent with functions for adding 
     1337    /// It extends \ref BaseGraphComponent with functions for adding
    13381338    /// nodes and edges to the graph.
    13391339    /// This concept requires \ref AlterableGraphComponent.
     
    13791379    ///
    13801380    /// This class describes the interface of erasable directed graphs.
    1381     /// It extends \ref BaseDigraphComponent with functions for removing 
     1381    /// It extends \ref BaseDigraphComponent with functions for removing
    13821382    /// nodes and arcs from the digraph.
    13831383    /// This concept requires \ref AlterableDigraphComponent.
     
    13921392      /// \brief Erase a node from the digraph.
    13931393      ///
    1394       /// This function erases the given node from the digraph and all arcs 
     1394      /// This function erases the given node from the digraph and all arcs
    13951395      /// connected to the node.
    13961396      void erase(const Node&) {}
     
    14181418    ///
    14191419    /// This class describes the interface of erasable undirected graphs.
    1420     /// It extends \ref BaseGraphComponent with functions for removing 
     1420    /// It extends \ref BaseGraphComponent with functions for removing
    14211421    /// nodes and edges from the graph.
    14221422    /// This concept requires \ref AlterableGraphComponent.
  • lemon/concepts/heap.h

    r817 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9393#else
    9494      explicit Heap(ItemIntMap&) {}
    95 #endif     
     95#endif
    9696
    9797      /// \brief Constructor.
     
    107107#else
    108108      explicit Heap(ItemIntMap&, const CMP&) {}
    109 #endif     
     109#endif
    110110
    111111      /// \brief The number of items stored in the heap.
     
    139139#else
    140140      void push(const Item&, const Prio&) {}
    141 #endif     
     141#endif
    142142
    143143      /// \brief Return the item having minimum priority.
     
    169169#else
    170170      void erase(const Item&) {}
    171 #endif     
     171#endif
    172172
    173173      /// \brief The priority of the given item.
     
    180180#else
    181181      Prio operator[](const Item&) const { return Prio(); }
    182 #endif     
     182#endif
    183183
    184184      /// \brief Set the priority of an item or insert it, if it is
     
    195195#else
    196196      void set(const Item&, const Prio&) {}
    197 #endif     
     197#endif
    198198
    199199      /// \brief Decrease the priority of an item to the given value.
     
    207207#else
    208208      void decrease(const Item&, const Prio&) {}
    209 #endif     
     209#endif
    210210
    211211      /// \brief Increase the priority of an item to the given value.
     
    219219#else
    220220      void increase(const Item&, const Prio&) {}
    221 #endif     
     221#endif
    222222
    223223      /// \brief Return the state of an item.
     
    233233#else
    234234      State state(const Item&) const { return PRE_HEAP; }
    235 #endif     
     235#endif
    236236
    237237      /// \brief Set the state of an item in the heap.
     
    246246#else
    247247      void state(const Item&, State) {}
    248 #endif     
     248#endif
    249249
    250250
  • lemon/connectivity.h

    r648 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    259259  /// \return \c true if the digraph is strongly connected.
    260260  /// \note By definition, the empty digraph is strongly connected.
    261   /// 
     261  ///
    262262  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
    263263  /// \see connected()
     
    311311  /// \ingroup graph_properties
    312312  ///
    313   /// \brief Count the number of strongly connected components of a 
     313  /// \brief Count the number of strongly connected components of a
    314314  /// directed graph
    315315  ///
     
    745745  /// \brief Check whether an undirected graph is bi-node-connected.
    746746  ///
    747   /// This function checks whether the given undirected graph is 
     747  /// This function checks whether the given undirected graph is
    748748  /// bi-node-connected, i.e. any two edges are on same circle.
    749749  ///
     
    759759  /// \ingroup graph_properties
    760760  ///
    761   /// \brief Count the number of bi-node-connected components of an 
     761  /// \brief Count the number of bi-node-connected components of an
    762762  /// undirected graph.
    763763  ///
     
    813813  /// \retval compMap A writable edge map. The values will be set from 0
    814814  /// to the number of the bi-node-connected components minus one. Each
    815   /// value of the map will be set exactly once, and the values of a 
     815  /// value of the map will be set exactly once, and the values of a
    816816  /// certain component will be set continuously.
    817817  /// \return The number of bi-node-connected components.
     
    859859  ///
    860860  /// \param graph The undirected graph.
    861   /// \retval cutMap A writable node map. The values will be set to 
     861  /// \retval cutMap A writable node map. The values will be set to
    862862  /// \c true for the nodes that separate two or more components
    863863  /// (exactly once for each cut node), and will not be changed for
     
    10861086  /// \brief Check whether an undirected graph is bi-edge-connected.
    10871087  ///
    1088   /// This function checks whether the given undirected graph is 
     1088  /// This function checks whether the given undirected graph is
    10891089  /// bi-edge-connected, i.e. any two nodes are connected with at least
    10901090  /// two edge-disjoint paths.
     
    11931193  ///
    11941194  /// This function finds the bi-edge-connected cut edges in the given
    1195   /// undirected graph. 
     1195  /// undirected graph.
    11961196  ///
    11971197  /// The bi-edge-connected components are the classes of an equivalence
     
    13501350  /// \param digraph The digraph.
    13511351  /// \retval order A readable and writable node map. The values will be
    1352   /// set from 0 to the number of the nodes in the digraph minus one. 
     1352  /// set from 0 to the number of the nodes in the digraph minus one.
    13531353  /// Each value of the map will be set exactly once, and the values will
    13541354  /// be set descending order.
  • lemon/core.h

    r671 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    12401240  protected:
    12411241
    1242     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1242    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
     1243    {
    12431244      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
    12441245
     
    12791280    };
    12801281
    1281   protected: 
     1282  protected:
    12821283
    12831284    const Digraph &_g;
  • lemon/cost_scaling.h

    r863 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9393  /// push/augment and relabel operations for finding a \ref min_cost_flow
    9494  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
    95   /// \ref goldberg97efficient, \ref bunnagel98efficient. 
     95  /// \ref goldberg97efficient, \ref bunnagel98efficient.
    9696  /// It is a highly efficient primal-dual solution method, which
    9797  /// can be viewed as the generalization of the \ref Preflow
     
    190190      /// paths from a node with excess to a node with deficit.
    191191      AUGMENT,
    192       /// Partial augment operations are used, i.e. flow is moved on 
     192      /// Partial augment operations are used, i.e. flow is moved on
    193193      /// admissible paths started from a node with excess, but the
    194194      /// lengths of these paths are limited. This method can be viewed
     
    209209
    210210  private:
    211  
     211
    212212    template <typename KT, typename VT>
    213213    class StaticVectorMap {
     
    215215      typedef KT Key;
    216216      typedef VT Value;
    217      
     217
    218218      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
    219      
     219
    220220      const Value& operator[](const Key& key) const {
    221221        return _v[StaticDigraph::id(key)];
     
    225225        return _v[StaticDigraph::id(key)];
    226226      }
    227      
     227
    228228      void set(const Key& key, const Value& val) {
    229229        _v[StaticDigraph::id(key)] = val;
     
    284284    IntVector _rank;
    285285    int _max_rank;
    286  
     286
    287287    // Data for a StaticDigraph structure
    288288    typedef std::pair<int, int> IntPair;
     
    292292    LargeCostArcMap _cost_map;
    293293    LargeCostNodeMap _pi_map;
    294  
     294
    295295  public:
    296  
     296
    297297    /// \brief Constant for infinite upper bounds (capacities).
    298298    ///
     
    349349      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
    350350        "The cost type of CostScaling must be signed");
    351      
     351
    352352      // Reset data structures
    353353      reset();
     
    465465      return *this;
    466466    }
    467    
     467
    468468    /// @}
    469469
     
    567567        _scost[j] = 0;
    568568        _scost[_reverse[j]] = 0;
    569       }     
     569      }
    570570      _have_lower = false;
    571571      return *this;
     
    602602      _scost.resize(_res_arc_num);
    603603      _supply.resize(_res_node_num);
    604      
     604
    605605      _res_cap.resize(_res_arc_num);
    606606      _cost.resize(_res_arc_num);
     
    650650        _reverse[bi] = fi;
    651651      }
    652      
     652
    653653      // Reset parameters
    654654      resetParams();
     
    759759      }
    760760      if (_sum_supply > 0) return INFEASIBLE;
    761      
     761
    762762
    763763      // Initialize vectors
     
    766766        _excess[i] = _supply[i];
    767767      }
    768      
     768
    769769      // Remove infinite upper bounds and check negative arcs
    770770      const Value MAX = std::numeric_limits<Value>::max();
     
    886886        }
    887887      }
    888      
     888
    889889      return OPTIMAL;
    890890    }
     
    895895      const int MAX_PATH_LENGTH = 4;
    896896
    897       // Initialize data structures for buckets     
     897      // Initialize data structures for buckets
    898898      _max_rank = _alpha * _res_node_num;
    899899      _buckets.resize(_max_rank);
     
    901901      _bucket_prev.resize(_res_node_num + 1);
    902902      _rank.resize(_res_node_num + 1);
    903  
     903
    904904      // Execute the algorithm
    905905      switch (method) {
     
    940940      }
    941941    }
    942    
     942
    943943    // Initialize a cost scaling phase
    944944    void initPhase() {
     
    958958        }
    959959      }
    960      
     960
    961961      // Find active nodes (i.e. nodes with positive excess)
    962962      for (int u = 0; u != _res_node_num; ++u) {
     
    969969      }
    970970    }
    971    
     971
    972972    // Early termination heuristic
    973973    bool earlyTermination() {
     
    999999    void globalUpdate() {
    10001000      int bucket_end = _root + 1;
    1001    
     1001
    10021002      // Initialize buckets
    10031003      for (int r = 0; r != _max_rank; ++r) {
     
    10251025          int u = _buckets[r];
    10261026          _buckets[r] = _bucket_next[u];
    1027          
     1027
    10281028          // Search the incomming arcs of u
    10291029          LargeCost pi_u = _pi[u];
     
    10401040                if (nrc < LargeCost(_max_rank))
    10411041                  new_rank_v = r + 1 + int(nrc);
    1042                  
     1042
    10431043                // Change the rank of v
    10441044                if (new_rank_v < old_rank_v) {
    10451045                  _rank[v] = new_rank_v;
    10461046                  _next_out[v] = _first_out[v];
    1047                  
     1047
    10481048                  // Remove v from its old bucket
    10491049                  if (old_rank_v < _max_rank) {
     
    10551055                    }
    10561056                  }
    1057                  
     1057
    10581058                  // Insert v to its new bucket
    10591059                  _bucket_next[v] = _buckets[new_rank_v];
     
    10731073        if (total_excess <= 0) break;
    10741074      }
    1075      
     1075
    10761076      // Relabel nodes
    10771077      for (int u = 0; u != _res_node_num; ++u) {
     
    10931093        (_res_node_num + _sup_node_num * _sup_node_num));
    10941094      int next_update_limit = global_update_freq;
    1095      
     1095
    10961096      int relabel_cnt = 0;
    1097      
     1097
    10981098      // Perform cost scaling phases
    10991099      std::vector<int> path;
     
    11051105          if (earlyTermination()) break;
    11061106        }
    1107        
     1107
    11081108        // Initialize current phase
    11091109        initPhase();
    1110        
     1110
    11111111        // Perform partial augment and relabel operations
    11121112        while (true) {
     
    11971197
    11981198      int relabel_cnt = 0;
    1199      
     1199
    12001200      // Perform cost scaling phases
    12011201      BoolVector hyper(_res_node_num, false);
     
    12081208          if (earlyTermination()) break;
    12091209        }
    1210        
     1210
    12111211        // Initialize current phase
    12121212        initPhase();
     
    12231223          last_out = _first_out[n+1];
    12241224          pi_n = _pi[n];
    1225          
     1225
    12261226          // Perform push operations if there are admissible arcs
    12271227          if (_excess[n] > 0) {
     
    12371237                LargeCost pi_t = _pi[t];
    12381238                for (int ta = _next_out[t]; ta != last_out_t; ++ta) {
    1239                   if (_res_cap[ta] > 0 && 
     1239                  if (_res_cap[ta] > 0 &&
    12401240                      _cost[ta] + pi_t - _pi[_target[ta]] < 0)
    12411241                    ahead += _res_cap[ta];
     
    12881288            ++relabel_cnt;
    12891289          }
    1290        
     1290
    12911291          // Remove nodes that are not active nor hyper
    12921292        remove_nodes:
     
    12961296            _active_nodes.pop_front();
    12971297          }
    1298          
     1298
    12991299          // Global update heuristic
    13001300          if (relabel_cnt >= next_update_limit) {
  • lemon/cplex.cc

    r746 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    112112  }
    113113
    114   int CplexBase::_addRow(Value lb, ExprIterator b, 
     114  int CplexBase::_addRow(Value lb, ExprIterator b,
    115115                         ExprIterator e, Value ub) {
    116116    int i = CPXgetnumrows(cplexEnv(), _prob);
     
    490490
    491491  void CplexBase::_applyMessageLevel() {
    492     CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, 
     492    CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
    493493                   _message_enabled ? CPX_ON : CPX_OFF);
    494494  }
  • lemon/cycle_canceling.h

    r864 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    143143
    144144    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    145    
     145
    146146    typedef std::vector<int> IntVector;
    147147    typedef std::vector<double> DoubleVector;
     
    152152
    153153  private:
    154  
     154
    155155    template <typename KT, typename VT>
    156156    class StaticVectorMap {
     
    158158      typedef KT Key;
    159159      typedef VT Value;
    160      
     160
    161161      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
    162      
     162
    163163      const Value& operator[](const Key& key) const {
    164164        return _v[StaticDigraph::id(key)];
     
    168168        return _v[StaticDigraph::id(key)];
    169169      }
    170      
     170
    171171      void set(const Key& key, const Value& val) {
    172172        _v[StaticDigraph::id(key)] = val;
     
    222222    CostArcMap _cost_map;
    223223    CostNodeMap _pi_map;
    224  
     224
    225225  public:
    226  
     226
    227227    /// \brief Constant for infinite upper bounds (capacities).
    228228    ///
     
    367367      return *this;
    368368    }
    369    
     369
    370370    /// @}
    371371
     
    467467        _cost[j] = 0;
    468468        _cost[_reverse[j]] = 0;
    469       }     
     469      }
    470470      _have_lower = false;
    471471      return *this;
     
    509509      _cost.resize(_res_arc_num);
    510510      _supply.resize(_res_node_num);
    511      
     511
    512512      _res_cap.resize(_res_arc_num);
    513513      _pi.resize(_res_node_num);
     
    555555        _reverse[bi] = fi;
    556556      }
    557      
     557
    558558      // Reset parameters
    559559      resetParams();
     
    664664      }
    665665      if (_sum_supply > 0) return INFEASIBLE;
    666      
     666
    667667
    668668      // Initialize vectors
     
    671671      }
    672672      ValueVector excess(_supply);
    673      
     673
    674674      // Remove infinite upper bounds and check negative arcs
    675675      const Value MAX = std::numeric_limits<Value>::max();
     
    771771        }
    772772      }
    773      
     773
    774774      return OPTIMAL;
    775775    }
    776    
     776
    777777    // Build a StaticDigraph structure containing the current
    778778    // residual network
     
    830830      const int BF_FIRST_LIMIT  = 2;
    831831      const double BF_LIMIT_FACTOR = 1.5;
    832      
     832
    833833      typedef StaticVectorMap<StaticDigraph::Arc, Value> FilterMap;
    834834      typedef FilterArcs<StaticDigraph, FilterMap> ResDigraph;
     
    837837        ::template SetDistMap<CostNodeMap>
    838838        ::template SetPredMap<PredMap>::Create BF;
    839      
     839
    840840      // Build the residual network
    841841      _arc_vec.clear();
     
    927927      typedef typename HowardMmc<StaticDigraph, CostArcMap>
    928928        ::template SetPath<SPath>::Create MMC;
    929      
     929
    930930      SPath cycle;
    931931      MMC mmc(_sgr, _cost_map);
     
    950950        }
    951951
    952         // Rebuild the residual network       
     952        // Rebuild the residual network
    953953        buildResidualNetwork();
    954954      }
     
    11441144          Cost cycle_cost = mmc.cycleCost();
    11451145          int cycle_size = mmc.cycleSize();
    1146          
     1146
    11471147          // Compute feasible potentials for the current epsilon
    11481148          for (int i = 0; i != int(_cost_vec.size()); ++i) {
     
    11561156            pi[u] = static_cast<double>(_pi[u]) / cycle_size;
    11571157          }
    1158        
     1158
    11591159          iter = limit;
    11601160        }
  • lemon/dfs.h

    r825 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8383
    8484    ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8687    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8788    ///Instantiates a \c ReachedMap.
     
    271272    ///\ref named-templ-param "Named parameter" for setting
    272273    ///\c ReachedMap type.
    273     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     274    ///It must conform to
     275    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    274276    template <class T>
    275277    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    803805
    804806    ///The type of the map that indicates which nodes are reached.
    805     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     807    ///It must conform to
     808    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    806809    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    807810    ///Instantiates a ReachedMap.
     
    12081211    ///
    12091212    /// The type of the map that indicates which nodes are reached.
    1210     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1213    /// It must conform to the
     1214    /// \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12111215    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12121216
  • lemon/dijkstra.h

    r825 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/dimacs.h

    r584 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6262
    6363  ///This function starts seeking the beginning of the given file for the
    64   ///problem type and size info. 
     64  ///problem type and size info.
    6565  ///The found data is returned in a special struct that can be evaluated
    6666  ///and passed to the appropriate reader function.
     
    213213        std::numeric_limits<Capacity>::infinity() :
    214214        std::numeric_limits<Capacity>::max();
    215  
     215
    216216    while (is >> c) {
    217217      switch (c) {
     
    238238          e = g.addArc(nodes[i], nodes[j]);
    239239          capacity.set(e, _cap);
    240         } 
     240        }
    241241        else if (desc.type==DimacsDescriptor::MAX) {
    242242          is >> i >> j >> _cap;
     
    363363    g.addArc(s,t);
    364364  }
    365  
     365
    366366  /// \brief DIMACS plain (di)graph reader function.
    367367  ///
    368368  /// This function reads a plain (di)graph without any designated nodes
    369   /// and maps (e.g. a matching instance) from DIMACS format, i.e. from 
     369  /// and maps (e.g. a matching instance) from DIMACS format, i.e. from
    370370  /// DIMACS files having a line starting with
    371371  /// \code
     
    393393      nodes[k] = g.addNode();
    394394    }
    395    
     395
    396396    while (is >> c) {
    397397      switch (c) {
  • lemon/edge_set.h

    r787 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/euler.h

    r648 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2727/// \ingroup graph_properties
    2828/// \file
    29 /// \brief Euler tour iterators and a function for checking the \e Eulerian 
     29/// \brief Euler tour iterators and a function for checking the \e Eulerian
    3030/// property.
    3131///
     
    4242  ///
    4343  ///For example, if the given digraph has an Euler tour (i.e it has only one
    44   ///non-trivial component and the in-degree is equal to the out-degree 
     44  ///non-trivial component and the in-degree is equal to the out-degree
    4545  ///for all nodes), then the following code will put the arcs of \c g
    4646  ///to the vector \c et according to an Euler tour of \c g.
     
    139139  ///and \c Edge types of the graph.
    140140  ///
    141   ///For example, if the given graph has an Euler tour (i.e it has only one 
     141  ///For example, if the given graph has an Euler tour (i.e it has only one
    142142  ///non-trivial component and the degree of each node is even),
    143143  ///the following code will print the arc IDs according to an
     
    148148  ///  }
    149149  ///\endcode
    150   ///Although this iterator is for undirected graphs, it still returns 
     150  ///Although this iterator is for undirected graphs, it still returns
    151151  ///arcs in order to indicate the direction of the tour.
    152152  ///(But arcs convert to edges, of course.)
     
    234234    /// Postfix incrementation.
    235235    ///
    236     ///\warning This incrementation returns an \c Arc (which converts to 
     236    ///\warning This incrementation returns an \c Arc (which converts to
    237237    ///an \c Edge), not an \ref EulerIt, as one may expect.
    238238    Arc operator++(int)
  • lemon/fractional_matching.h

    r876 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    20102010    /// \brief Run the algorithm.
    20112011    ///
    2012     /// This method runs the \c %MaxWeightedPerfectFractionalMatching 
     2012    /// This method runs the \c %MaxWeightedPerfectFractionalMatching
    20132013    /// algorithm.
    20142014    ///
  • lemon/full_graph.h

    r787 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    204204    /// \brief Returns the node with the given index.
    205205    ///
    206     /// Returns the node with the given index. Since this structure is 
     206    /// Returns the node with the given index. Since this structure is
    207207    /// completely static, the nodes can be indexed with integers from
    208208    /// the range <tt>[0..nodeNum()-1]</tt>.
     
    213213    /// \brief Returns the index of the given node.
    214214    ///
    215     /// Returns the index of the given node. Since this structure is 
     215    /// Returns the index of the given node. Since this structure is
    216216    /// completely static, the nodes can be indexed with integers from
    217217    /// the range <tt>[0..nodeNum()-1]</tt>.
     
    583583    /// \brief Returns the node with the given index.
    584584    ///
    585     /// Returns the node with the given index. Since this structure is 
     585    /// Returns the node with the given index. Since this structure is
    586586    /// completely static, the nodes can be indexed with integers from
    587587    /// the range <tt>[0..nodeNum()-1]</tt>.
     
    592592    /// \brief Returns the index of the given node.
    593593    ///
    594     /// Returns the index of the given node. Since this structure is 
     594    /// Returns the index of the given node. Since this structure is
    595595    /// completely static, the nodes can be indexed with integers from
    596596    /// the range <tt>[0..nodeNum()-1]</tt>.
  • lemon/glpk.cc

    r746 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6060  }
    6161
    62   int GlpkBase::_addRow(Value lo, ExprIterator b, 
     62  int GlpkBase::_addRow(Value lo, ExprIterator b,
    6363                        ExprIterator e, Value up) {
    6464    int i = glp_add_rows(lp, 1);
     
    6969      } else {
    7070        glp_set_row_bnds(lp, i, GLP_UP, lo, up);
    71       }   
     71      }
    7272    } else {
    7373      if (up == INF) {
    7474        glp_set_row_bnds(lp, i, GLP_LO, lo, up);
    75       } else if (lo != up) {       
     75      } else if (lo != up) {
    7676        glp_set_row_bnds(lp, i, GLP_DB, lo, up);
    7777      } else {
  • lemon/glpk.h

    r833 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3131    class VoidPtr {
    3232    private:
    33       void *_ptr;     
     33      void *_ptr;
    3434    public:
    3535      VoidPtr() : _ptr(0) {}
     
    3939
    4040      template <typename T>
    41       VoidPtr& operator=(T* ptr) { 
    42         _ptr = reinterpret_cast<void*>(ptr); 
     41      VoidPtr& operator=(T* ptr) {
     42        _ptr = reinterpret_cast<void*>(ptr);
    4343        return *this;
    4444      }
     
    125125      }
    126126    };
    127    
     127
    128128    static FreeEnvHelper freeEnvHelper;
    129129
    130130  protected:
    131    
     131
    132132    int _message_level;
    133    
     133
    134134  public:
    135135
  • lemon/gomory_hu.h

    r786 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2828
    2929/// \ingroup min_cut
    30 /// \file 
     30/// \file
    3131/// \brief Gomory-Hu cut tree in graphs.
    3232
     
    3939  /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
    4040  /// may contain edges which are not in the original graph. It has the
    41   /// property that the minimum capacity edge of the path between two nodes 
     41  /// property that the minimum capacity edge of the path between two nodes
    4242  /// in this tree has the same weight as the minimum cut in the graph
    4343  /// between these nodes. Moreover the components obtained by removing
     
    4545  /// Therefore once this tree is computed, the minimum cut between any pair
    4646  /// of nodes can easily be obtained.
    47   /// 
     47  ///
    4848  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
    4949  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
     
    6161#ifdef DOXYGEN
    6262  template <typename GR,
    63             typename CAP>
     63            typename CAP>
    6464#else
    6565  template <typename GR,
    66             typename CAP = typename GR::template EdgeMap<int> >
     66            typename CAP = typename GR::template EdgeMap<int> >
    6767#endif
    6868  class GomoryHu {
     
    7575    /// The value type of capacities
    7676    typedef typename Capacity::Value Value;
    77    
     77
    7878  private:
    7979
     
    9090    void createStructures() {
    9191      if (!_pred) {
    92         _pred = new typename Graph::template NodeMap<Node>(_graph);
     92        _pred = new typename Graph::template NodeMap<Node>(_graph);
    9393      }
    9494      if (!_weight) {
    95         _weight = new typename Graph::template NodeMap<Value>(_graph);
     95        _weight = new typename Graph::template NodeMap<Value>(_graph);
    9696      }
    9797      if (!_order) {
    98         _order = new typename Graph::template NodeMap<int>(_graph);
     98        _order = new typename Graph::template NodeMap<int>(_graph);
    9999      }
    100100    }
     
    102102    void destroyStructures() {
    103103      if (_pred) {
    104         delete _pred;
     104        delete _pred;
    105105      }
    106106      if (_weight) {
    107         delete _weight;
     107        delete _weight;
    108108      }
    109109      if (_order) {
    110         delete _order;
    111       }
    112     }
    113  
     110        delete _order;
     111      }
     112    }
     113
    114114  public:
    115115
     
    119119    /// \param graph The undirected graph the algorithm runs on.
    120120    /// \param capacity The edge capacity map.
    121     GomoryHu(const Graph& graph, const Capacity& capacity) 
     121    GomoryHu(const Graph& graph, const Capacity& capacity)
    122122      : _graph(graph), _capacity(capacity),
    123         _pred(0), _weight(0), _order(0)
     123        _pred(0), _weight(0), _order(0)
    124124    {
    125125      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
     
    135135
    136136  private:
    137  
     137
    138138    // Initialize the internal data structures
    139139    void init() {
     
    146146      }
    147147      (*_pred)[_root] = INVALID;
    148       (*_weight)[_root] = std::numeric_limits<Value>::max(); 
     148      (*_weight)[_root] = std::numeric_limits<Value>::max();
    149149    }
    150150
     
    155155
    156156      for (NodeIt n(_graph); n != INVALID; ++n) {
    157         if (n == _root) continue;
    158 
    159         Node pn = (*_pred)[n];
    160         fa.source(n);
    161         fa.target(pn);
    162 
    163         fa.runMinCut();
    164 
    165         (*_weight)[n] = fa.flowValue();
    166 
    167         for (NodeIt nn(_graph); nn != INVALID; ++nn) {
    168           if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
    169             (*_pred)[nn] = n;
    170           }
    171         }
    172         if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
    173           (*_pred)[n] = (*_pred)[pn];
    174           (*_pred)[pn] = n;
    175           (*_weight)[n] = (*_weight)[pn];
    176           (*_weight)[pn] = fa.flowValue();
    177         }
     157        if (n == _root) continue;
     158
     159        Node pn = (*_pred)[n];
     160        fa.source(n);
     161        fa.target(pn);
     162
     163        fa.runMinCut();
     164
     165        (*_weight)[n] = fa.flowValue();
     166
     167        for (NodeIt nn(_graph); nn != INVALID; ++nn) {
     168          if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
     169            (*_pred)[nn] = n;
     170          }
     171        }
     172        if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
     173          (*_pred)[n] = (*_pred)[pn];
     174          (*_pred)[pn] = n;
     175          (*_weight)[n] = (*_weight)[pn];
     176          (*_weight)[pn] = fa.flowValue();
     177        }
    178178      }
    179179
     
    182182
    183183      for (NodeIt n(_graph); n != INVALID; ++n) {
    184         std::vector<Node> st;
    185         Node nn = n;
    186         while ((*_order)[nn] == -1) {
    187           st.push_back(nn);
    188           nn = (*_pred)[nn];
    189         }
    190         while (!st.empty()) {
    191           (*_order)[st.back()] = index++;
    192           st.pop_back();
    193         }
     184        std::vector<Node> st;
     185        Node nn = n;
     186        while ((*_order)[nn] == -1) {
     187          st.push_back(nn);
     188          nn = (*_pred)[nn];
     189        }
     190        while (!st.empty()) {
     191          (*_order)[st.back()] = index++;
     192          st.pop_back();
     193        }
    194194      }
    195195    }
     
    198198
    199199    ///\name Execution Control
    200  
     200
    201201    ///@{
    202202
     
    208208      start();
    209209    }
    210    
     210
    211211    /// @}
    212212
     
    233233    /// Gomory-Hu tree.
    234234    ///
    235     /// This function returns the weight of the predecessor edge of the 
     235    /// This function returns the weight of the predecessor edge of the
    236236    /// given node in the Gomory-Hu tree.
    237237    /// If \c node is the root of the tree, the result is undefined.
     
    255255    ///
    256256    /// This function returns the minimum cut value between the nodes
    257     /// \c s and \c t. 
     257    /// \c s and \c t.
    258258    /// It finds the nearest common ancestor of the given nodes in the
    259259    /// Gomory-Hu tree and calculates the minimum weight edge on the
     
    264264      Node sn = s, tn = t;
    265265      Value value = std::numeric_limits<Value>::max();
    266      
     266
    267267      while (sn != tn) {
    268         if ((*_order)[sn] < (*_order)[tn]) {
    269           if ((*_weight)[tn] <= value) value = (*_weight)[tn];
    270           tn = (*_pred)[tn];
    271         } else {
    272           if ((*_weight)[sn] <= value) value = (*_weight)[sn];
    273           sn = (*_pred)[sn];
    274         }
     268        if ((*_order)[sn] < (*_order)[tn]) {
     269          if ((*_weight)[tn] <= value) value = (*_weight)[tn];
     270          tn = (*_pred)[tn];
     271        } else {
     272          if ((*_weight)[sn] <= value) value = (*_weight)[sn];
     273          sn = (*_pred)[sn];
     274        }
    275275      }
    276276      return value;
     
    303303      Node rn = INVALID;
    304304      Value value = std::numeric_limits<Value>::max();
    305      
     305
    306306      while (sn != tn) {
    307         if ((*_order)[sn] < (*_order)[tn]) {
    308           if ((*_weight)[tn] <= value) {
    309             rn = tn;
     307        if ((*_order)[sn] < (*_order)[tn]) {
     308          if ((*_weight)[tn] <= value) {
     309            rn = tn;
    310310            s_root = false;
    311             value = (*_weight)[tn];
    312           }
    313           tn = (*_pred)[tn];
    314         } else {
    315           if ((*_weight)[sn] <= value) {
    316             rn = sn;
     311            value = (*_weight)[tn];
     312          }
     313          tn = (*_pred)[tn];
     314        } else {
     315          if ((*_weight)[sn] <= value) {
     316            rn = sn;
    317317            s_root = true;
    318             value = (*_weight)[sn];
    319           }
    320           sn = (*_pred)[sn];
    321         }
     318            value = (*_weight)[sn];
     319          }
     320          sn = (*_pred)[sn];
     321        }
    322322      }
    323323
     
    330330      std::vector<Node> st;
    331331      for (NodeIt n(_graph); n != INVALID; ++n) {
    332         st.clear();
     332        st.clear();
    333333        Node nn = n;
    334         while (!reached[nn]) {
    335           st.push_back(nn);
    336           nn = (*_pred)[nn];
    337         }
    338         while (!st.empty()) {
    339           cutMap.set(st.back(), cutMap[nn]);
    340           st.pop_back();
    341         }
    342       }
    343      
     334        while (!reached[nn]) {
     335          st.push_back(nn);
     336          nn = (*_pred)[nn];
     337        }
     338        while (!st.empty()) {
     339          cutMap.set(st.back(), cutMap[nn]);
     340          st.pop_back();
     341        }
     342      }
     343
    344344      return value;
    345345    }
     
    350350
    351351    /// Iterate on the nodes of a minimum cut
    352    
     352
    353353    /// This iterator class lists the nodes of a minimum cut found by
    354354    /// GomoryHu. Before using it, you must allocate a GomoryHu class
     
    443443      }
    444444    };
    445    
     445
    446446    friend class MinCutEdgeIt;
    447    
     447
    448448    /// Iterate on the edges of a minimum cut
    449    
     449
    450450    /// This iterator class lists the edges of a minimum cut found by
    451451    /// GomoryHu. Before using it, you must allocate a GomoryHu class
     
    480480          }
    481481      }
    482      
     482
    483483    public:
    484484      /// Constructor
     
    549549      }
    550550      /// Postfix incrementation
    551      
     551
    552552      /// Postfix incrementation.
    553553      ///
  • lemon/graph_to_eps.h

    r838 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/hao_orlin.h

    r860 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3232/// \brief Implementation of the Hao-Orlin algorithm.
    3333///
    34 /// Implementation of the Hao-Orlin algorithm for finding a minimum cut 
     34/// Implementation of the Hao-Orlin algorithm for finding a minimum cut
    3535/// in a digraph.
    3636
     
    4242  ///
    4343  /// This class implements the Hao-Orlin algorithm for finding a minimum
    44   /// value cut in a directed graph \f$D=(V,A)\f$. 
     44  /// value cut in a directed graph \f$D=(V,A)\f$.
    4545  /// It takes a fixed node \f$ source \in V \f$ and
    4646  /// consists of two phases: in the first phase it determines a
     
    5959  /// For an undirected graph you can run just the first phase of the
    6060  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
    61   /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ 
     61  /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$
    6262  /// time. It is implemented in the NagamochiIbaraki algorithm class.
    6363  ///
     
    7777  class HaoOrlin {
    7878  public:
    79    
     79
    8080    /// The digraph type of the algorithm
    8181    typedef GR Digraph;
     
    865865    ///
    866866    /// This function initializes the internal data structures. It creates
    867     /// the maps and some bucket structures for the algorithm. 
     867    /// the maps and some bucket structures for the algorithm.
    868868    /// The given node is used as the source node for the push-relabel
    869869    /// algorithm.
     
    945945    /// \brief Run the algorithm.
    946946    ///
    947     /// This function runs the algorithm. It uses the given \c source node, 
     947    /// This function runs the algorithm. It uses the given \c source node,
    948948    /// finds a proper \c target node and then calls the \ref init(),
    949949    /// \ref calculateOut() and \ref calculateIn().
     
    959959    /// The result of the %HaoOrlin algorithm
    960960    /// can be obtained using these functions.\n
    961     /// \ref run(), \ref calculateOut() or \ref calculateIn() 
     961    /// \ref run(), \ref calculateOut() or \ref calculateIn()
    962962    /// should be called before using them.
    963963
     
    968968    /// This function returns the value of the minimum cut.
    969969    ///
    970     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 
     970    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
    971971    /// must be called before using this function.
    972972    Value minCutValue() const {
     
    987987    /// \return The value of the minimum cut.
    988988    ///
    989     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 
     989    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
    990990    /// must be called before using this function.
    991991    template <typename CutMap>
  • lemon/hartmann_orlin_mmc.h

    r864 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    344344      init();
    345345      findComponents();
    346      
     346
    347347      // Find the minimum cycle mean in the components
    348348      for (int comp = 0; comp < _comp_num; ++comp) {
    349349        if (!initComponent(comp)) continue;
    350350        processRounds();
    351        
     351
    352352        // Update the best cycle (global minimum mean cycle)
    353         if ( _curr_found && (!_best_found || 
     353        if ( _curr_found && (!_best_found ||
    354354             _curr_cost * _best_size < _best_cost * _curr_size) ) {
    355355          _best_found = true;
     
    504504      if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {
    505505        return false;
    506       }     
     506      }
    507507      for (int i = 0; i < n; ++i) {
    508508        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
     
    577577      }
    578578    }
    579    
     579
    580580    // Check early termination
    581581    bool checkTermination(int k) {
     
    587587      int size;
    588588      Node u;
    589      
     589
    590590      // Search for cycles that are already found
    591591      _curr_found = false;
     
    608608          level[u] = Pair(i, j);
    609609          if (j != 0) {
    610             u = _gr.source(_data[u][j].pred);
    611           }
     610            u = _gr.source(_data[u][j].pred);
     611          }
    612612        }
    613613      }
  • lemon/howard_mmc.h

    r864 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    122122  {
    123123  public:
    124  
     124
    125125    /// The type of the digraph
    126126    typedef typename TR::Digraph Digraph;
     
    153153
    154154    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    155  
     155
    156156    // The digraph the algorithm runs on
    157157    const Digraph &_gr;
     
    180180    std::vector<Node>* _nodes;
    181181    typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
    182    
     182
    183183    // Queue used for BFS search
    184184    std::vector<Node> _queue;
     
    186186
    187187    Tolerance _tolerance;
    188  
     188
    189189    // Infinite constant
    190190    const LargeCost INF;
    191191
    192192  public:
    193  
     193
    194194    /// \name Named Template Parameters
    195195    /// @{
     
    229229      typedef HowardMmc<GR, CM, SetPathTraits<T> > Create;
    230230    };
    231    
     231
    232232    /// @}
    233233
     
    335335      init();
    336336      findComponents();
    337      
     337
    338338      // Find the minimum cycle mean in the components
    339339      for (int comp = 0; comp < _comp_num; ++comp) {
     
    446446      _cycle_path->clear();
    447447    }
    448    
     448
    449449    // Find strongly connected components and initialize _comp_nodes
    450450    // and _in_arcs
  • lemon/karp_mmc.h

    r864 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    192192
    193193    Tolerance _tolerance;
    194    
     194
    195195    // Infinite constant
    196196    const LargeCost INF;
     
    340340      init();
    341341      findComponents();
    342      
     342
    343343      // Find the minimum cycle mean in the components
    344344      for (int comp = 0; comp < _comp_num; ++comp) {
     
    490490      if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {
    491491        return false;
    492       }     
     492      }
    493493      for (int i = 0; i < n; ++i) {
    494494        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
  • lemon/lgf_reader.h

    r786 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    563563    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is);
    564564    template <typename TDGR>
    565     friend DigraphReader<TDGR> digraphReader(TDGR& digraph, 
     565    friend DigraphReader<TDGR> digraphReader(TDGR& digraph,
    566566                                             const std::string& fn);
    567567    template <typename TDGR>
     
    11881188
    11891189  };
    1190  
     1190
    11911191  /// \ingroup lemon_io
    11921192  ///
     
    11951195  /// This function just returns a \ref DigraphReader class.
    11961196  ///
    1197   /// With this function a digraph can be read from an 
     1197  /// With this function a digraph can be read from an
    11981198  /// \ref lgf-format "LGF" file or input stream with several maps and
    11991199  /// attributes. For example, there is network flow problem on a
     
    12501250  template <typename GR>
    12511251  class GraphReader;
    1252  
     1252
    12531253  template <typename TGR>
    12541254  GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin);
     
    13871387    friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is);
    13881388    template <typename TGR>
    1389     friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn); 
     1389    friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
    13901390    template <typename TGR>
    13911391    friend GraphReader<TGR> graphReader(TGR& graph, const char *fn);
     
    20642064  /// \brief Return a \ref GraphReader class
    20652065  ///
    2066   /// This function just returns a \ref GraphReader class. 
    2067   ///
    2068   /// With this function a graph can be read from an 
     2066  /// This function just returns a \ref GraphReader class.
     2067  ///
     2068  /// With this function a graph can be read from an
    20692069  /// \ref lgf-format "LGF" file or input stream with several maps and
    20702070  /// attributes. For example, there is weighted matching problem on a
  • lemon/lgf_writer.h

    r599 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    352352
    353353  template <typename TDGR>
    354   DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 
     354  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
    355355                                   std::ostream& os = std::cout);
    356356  template <typename TDGR>
     
    505505
    506506    template <typename TDGR>
    507     friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 
     507    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
    508508                                             std::ostream& os);
    509509    template <typename TDGR>
     
    918918  /// \brief Return a \ref DigraphWriter class
    919919  ///
    920   /// This function just returns a \ref DigraphWriter class. 
     920  /// This function just returns a \ref DigraphWriter class.
    921921  ///
    922922  /// With this function a digraph can be write to a file or output
     
    958958  /// \sa digraphWriter(const TDGR& digraph, std::ostream& os)
    959959  template <typename TDGR>
    960   DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 
     960  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
    961961                                    const std::string& fn) {
    962962    DigraphWriter<TDGR> tmp(digraph, fn);
     
    11021102    friend GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os);
    11031103    template <typename TGR>
    1104     friend GraphWriter<TGR> graphWriter(const TGR& graph, 
     1104    friend GraphWriter<TGR> graphWriter(const TGR& graph,
    11051105                                        const std::string& fn);
    11061106    template <typename TGR>
    11071107    friend GraphWriter<TGR> graphWriter(const TGR& graph, const char *fn);
    1108    
     1108
    11091109    GraphWriter(GraphWriter& other)
    11101110      : _os(other._os), local_os(other.local_os), _graph(other._graph),
     
    15571557  /// \brief Return a \ref GraphWriter class
    15581558  ///
    1559   /// This function just returns a \ref GraphWriter class. 
     1559  /// This function just returns a \ref GraphWriter class.
    15601560  ///
    15611561  /// With this function a graph can be write to a file or output
  • lemon/list_graph.h

    r788 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    447447    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
    448448    ///iterators are invalidated for the incomming arcs of \c v.
    449     ///Moreover all iterators referencing node \c v or the removed 
     449    ///Moreover all iterators referencing node \c v or the removed
    450450    ///loops are also invalidated. Other iterators remain valid.
    451451    ///
     
    553553    /// restore() function.
    554554    ///
    555     /// \note After a state is restored, you cannot restore a later state, 
     555    /// \note After a state is restored, you cannot restore a later state,
    556556    /// i.e. you cannot add the removed nodes and arcs again using
    557557    /// another Snapshot instance.
     
    13081308    /// or changeV(), thus all edge and arc iterators whose base node is
    13091309    /// \c b are invalidated.
    1310     /// Moreover all iterators referencing node \c b or the removed 
     1310    /// Moreover all iterators referencing node \c b or the removed
    13111311    /// loops are also invalidated. Other iterators remain valid.
    13121312    ///
     
    13651365    /// using the restore() function.
    13661366    ///
    1367     /// \note After a state is restored, you cannot restore a later state, 
     1367    /// \note After a state is restored, you cannot restore a later state,
    13681368    /// i.e. you cannot add the removed nodes and edges again using
    13691369    /// another Snapshot instance.
  • lemon/lp.h

    r627 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8585#elif LEMON_HAVE_CLP
    8686# define DEFAULT_LP CLP
    87   typedef ClpLp Lp; 
     87  typedef ClpLp Lp;
    8888#endif
    8989#endif
  • lemon/lp_base.cc

    r510 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/lp_base.h

    r834 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8383      MESSAGE_VERBOSE
    8484    };
    85    
     85
    8686
    8787    ///The floating point type used by the solver
     
    115115      typedef True LpCol;
    116116      /// Default constructor
    117      
     117
    118118      /// \warning The default constructor sets the Col to an
    119119      /// undefined value.
    120120      Col() {}
    121121      /// Invalid constructor \& conversion.
    122      
     122
    123123      /// This constructor initializes the Col to be invalid.
    124       /// \sa Invalid for more details.     
     124      /// \sa Invalid for more details.
    125125      Col(const Invalid&) : _id(-1) {}
    126126      /// Equality operator
     
    157157    public:
    158158      /// Default constructor
    159      
     159
    160160      /// \warning The default constructor sets the iterator
    161161      /// to an undefined value.
    162162      ColIt() {}
    163163      /// Sets the iterator to the first Col
    164      
     164
    165165      /// Sets the iterator to the first Col.
    166166      ///
     
    170170      }
    171171      /// Invalid constructor \& conversion
    172      
     172
    173173      /// Initialize the iterator to be invalid.
    174174      /// \sa Invalid for more details.
    175175      ColIt(const Invalid&) : Col(INVALID) {}
    176176      /// Next column
    177      
     177
    178178      /// Assign the iterator to the next column.
    179179      ///
     
    210210      typedef True LpRow;
    211211      /// Default constructor
    212      
     212
    213213      /// \warning The default constructor sets the Row to an
    214214      /// undefined value.
    215215      Row() {}
    216216      /// Invalid constructor \& conversion.
    217      
     217
    218218      /// This constructor initializes the Row to be invalid.
    219       /// \sa Invalid for more details.     
     219      /// \sa Invalid for more details.
    220220      Row(const Invalid&) : _id(-1) {}
    221221      /// Equality operator
     
    225225      bool operator==(Row r) const  {return _id == r._id;}
    226226      /// Inequality operator
    227      
     227
    228228      /// \sa operator==(Row r)
    229229      ///
     
    252252    public:
    253253      /// Default constructor
    254      
     254
    255255      /// \warning The default constructor sets the iterator
    256256      /// to an undefined value.
    257257      RowIt() {}
    258258      /// Sets the iterator to the first Row
    259      
     259
    260260      /// Sets the iterator to the first Row.
    261261      ///
     
    265265      }
    266266      /// Invalid constructor \& conversion
    267      
     267
    268268      /// Initialize the iterator to be invalid.
    269269      /// \sa Invalid for more details.
    270270      RowIt(const Invalid&) : Row(INVALID) {}
    271271      /// Next row
    272      
     272
    273273      /// Assign the iterator to the next row.
    274274      ///
     
    348348      typedef True SolverExpr;
    349349      /// Default constructor
    350      
     350
    351351      /// Construct an empty expression, the coefficients and
    352352      /// the constant component are initialized to zero.
     
    449449
    450450      ///Iterator over the expression
    451      
    452       ///The iterator iterates over the terms of the expression. 
    453       /// 
     451
     452      ///The iterator iterates over the terms of the expression.
     453      ///
    454454      ///\code
    455455      ///double s=0;
     
    465465
    466466        /// Sets the iterator to the first term
    467        
     467
    468468        /// Sets the iterator to the first term of the expression.
    469469        ///
     
    482482        const Value& operator*() const { return _it->second; }
    483483        /// Next term
    484        
     484
    485485        /// Assign the iterator to the next term.
    486486        ///
     
    494494
    495495      /// Const iterator over the expression
    496      
    497       ///The iterator iterates over the terms of the expression. 
    498       /// 
     496
     497      ///The iterator iterates over the terms of the expression.
     498      ///
    499499      ///\code
    500500      ///double s=0;
     
    510510
    511511        /// Sets the iterator to the first term
    512        
     512
    513513        /// Sets the iterator to the first term of the expression.
    514514        ///
     
    525525
    526526        /// Next term
    527        
     527
    528528        /// Assign the iterator to the next term.
    529529        ///
     
    674674      typedef True SolverExpr;
    675675      /// Default constructor
    676      
     676
    677677      /// Construct an empty expression, the coefficients are
    678678      /// initialized to zero.
     
    709709      }
    710710      /// \brief Removes the coefficients which's absolute value does
    711       /// not exceed \c epsilon. 
     711      /// not exceed \c epsilon.
    712712      void simplify(Value epsilon = 0.0) {
    713713        std::map<int, Value>::iterator it=comps.begin();
     
    758758
    759759      ///Iterator over the expression
    760      
    761       ///The iterator iterates over the terms of the expression. 
    762       /// 
     760
     761      ///The iterator iterates over the terms of the expression.
     762      ///
    763763      ///\code
    764764      ///double s=0;
     
    774774
    775775        /// Sets the iterator to the first term
    776        
     776
    777777        /// Sets the iterator to the first term of the expression.
    778778        ///
     
    792792
    793793        /// Next term
    794        
     794
    795795        /// Assign the iterator to the next term.
    796796        ///
     
    804804
    805805      ///Iterator over the expression
    806      
    807       ///The iterator iterates over the terms of the expression. 
    808       /// 
     806
     807      ///The iterator iterates over the terms of the expression.
     808      ///
    809809      ///\code
    810810      ///double s=0;
     
    820820
    821821        /// Sets the iterator to the first term
    822        
     822
    823823        /// Sets the iterator to the first term of the expression.
    824824        ///
     
    835835
    836836        /// Next term
    837        
     837
    838838        /// Assign the iterator to the next term.
    839839        ///
     
    12301230      Row r;
    12311231      c.expr().simplify();
    1232       r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF, 
     1232      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
    12331233                                ExprIterator(c.expr().comps.begin(), cols),
    12341234                                ExprIterator(c.expr().comps.end(), cols),
     
    18181818    enum VarStatus {
    18191819      /// The variable is in the basis
    1820       BASIC, 
     1820      BASIC,
    18211821      /// The variable is free, but not basic
    18221822      FREE,
    1823       /// The variable has active lower bound 
     1823      /// The variable has active lower bound
    18241824      LOWER,
    18251825      /// The variable has active upper bound
     
    19001900    }
    19011901    /// Returns a component of the primal ray
    1902    
     1902
    19031903    /// The primal ray is solution of the modified primal problem,
    19041904    /// where we change each finite bound to 0, and we looking for a
     
    19341934
    19351935    /// Returns a component of the dual ray
    1936    
     1936
    19371937    /// The dual ray is solution of the modified primal problem, where
    19381938    /// we change each finite bound to 0 (i.e. the objective function
     
    20762076    }
    20772077    ///The value of the objective function
    2078    
     2078
    20792079    ///\return
    20802080    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
  • lemon/lp_skeleton.cc

    r746 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/lp_skeleton.h

    r746 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2424///\file
    2525///\brief Skeleton file to implement LP/MIP solver interfaces
    26 /// 
     26///
    2727///The classes in this file do nothing, but they can serve as skeletons when
    2828///implementing an interface to new solvers.
     
    3030
    3131  ///A skeleton class to implement LP/MIP solver base interface
    32  
     32
    3333  ///This class does nothing, but it can serve as a skeleton when
    3434  ///implementing an interface to new solvers.
  • lemon/maps.h

    r792 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    234234  /// heap types and \c UnionFind, when the used items are small
    235235  /// integers. This map conforms to the \ref concepts::ReferenceMap
    236   /// "ReferenceMap" concept. 
     236  /// "ReferenceMap" concept.
    237237  ///
    238238  /// The simplest way of using this map is through the rangeMap()
     
    19171917  /// \c InverseMap or \c operator()(), and the values of the map can be
    19181918  /// accessed with an STL compatible forward iterator (\c ValueIt).
    1919   /// 
     1919  ///
    19201920  /// This map is intended to be used when all associated values are
    19211921  /// different (the map is actually invertable) or there are only a few
    19221922  /// items with the same value.
    1923   /// Otherwise consider to use \c IterableValueMap, which is more 
     1923  /// Otherwise consider to use \c IterableValueMap, which is more
    19241924  /// suitable and more efficient for such cases. It provides iterators
    19251925  /// to traverse the items with the same associated value, but
     
    20032003      typename Container::const_iterator it;
    20042004    };
    2005    
     2005
    20062006    /// Alias for \c ValueIt
    20072007    typedef ValueIt ValueIterator;
     
    20622062      return it != _inv_map.end() ? it->second : INVALID;
    20632063    }
    2064    
     2064
    20652065    /// \brief Returns the number of items with the given value.
    20662066    ///
     
    23792379    return RangeIdMap<GR, K>(graph);
    23802380  }
    2381  
     2381
    23822382  /// \brief Dynamic iterable \c bool map.
    23832383  ///
     
    26392639      /// \param value The value.
    26402640      ItemIt(const IterableBoolMap& map, bool value)
    2641         : Parent(value ? 
     2641        : Parent(value ?
    26422642                 (map._sep > 0 ?
    26432643                  map._array[map._sep - 1] : INVALID) :
     
    37873787    typedef typename To::Key Item;
    37883788    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
    3789    
     3789
    37903790    for (ItemIt it(gr); it != INVALID; ++it) {
    37913791      to.set(it, from[it]);
     
    37953795  /// \brief Compare two graph maps.
    37963796  ///
    3797   /// This function compares the values of two graph maps. It returns 
     3797  /// This function compares the values of two graph maps. It returns
    37983798  /// \c true if the maps assign the same value for all items in the graph.
    37993799  /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
     
    38073807    typedef typename Map2::Key Item;
    38083808    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
    3809    
     3809
    38103810    for (ItemIt it(gr); it != INVALID; ++it) {
    38113811      if (!(map1[it] == map2[it])) return false;
  • lemon/matching.h

    r876 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    16241624        (*_delta4_index)[i] = _delta4->PRE_HEAP;
    16251625      }
    1626      
     1626
    16271627      _unmatched = _node_num;
    16281628
     
    16791679      _blossom_node_list.clear();
    16801680      _blossom_potential.clear();
    1681      
     1681
    16821682      if (_fractional == 0) {
    16831683        _fractional = new FractionalMatching(_graph, _weight, false);
     
    17511751            subblossoms[--num] = _blossom_set->find(v);
    17521752            _delta1->push(v, _fractional->nodeValue(v));
    1753             v = _graph.target(_fractional->matching(v));           
     1753            v = _graph.target(_fractional->matching(v));
    17541754          }
    1755          
    1756           int surface = 
     1755
     1756          int surface =
    17571757            _blossom_set->join(subblossoms.begin(), subblossoms.end());
    17581758          (*_blossom_data)[surface].status = EVEN;
     
    17611761          (*_blossom_data)[surface].pot = 0;
    17621762          (*_blossom_data)[surface].offset = 0;
    1763          
     1763
    17641764          _tree_set->insert(surface);
    17651765          ++_unmatched;
     
    18111811          }
    18121812        }
    1813            
     1813
    18141814        if (!(*_node_data)[ni].heap.empty()) {
    18151815          _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());
     
    22702270    int _unmatched;
    22712271
    2272     typedef MaxWeightedPerfectFractionalMatching<Graph, WeightMap> 
     2272    typedef MaxWeightedPerfectFractionalMatching<Graph, WeightMap>
    22732273    FractionalMatching;
    22742274    FractionalMatching *_fractional;
     
    30963096      _blossom_node_list.clear();
    30973097      _blossom_potential.clear();
    3098      
     3098
    30993099      if (_fractional == 0) {
    31003100        _fractional = new FractionalMatching(_graph, _weight, false);
     
    31623162          while (n != v) {
    31633163            subblossoms[--num] = _blossom_set->find(v);
    3164             v = _graph.target(_fractional->matching(v));           
     3164            v = _graph.target(_fractional->matching(v));
    31653165          }
    3166          
    3167           int surface = 
     3166
     3167          int surface =
    31683168            _blossom_set->join(subblossoms.begin(), subblossoms.end());
    31693169          (*_blossom_data)[surface].status = EVEN;
     
    31723172          (*_blossom_data)[surface].pot = 0;
    31733173          (*_blossom_data)[surface].offset = 0;
    3174          
     3174
    31753175          _tree_set->insert(surface);
    31763176          ++_unmatched;
     
    32223222          }
    32233223        }
    3224            
     3224
    32253225        if (!(*_node_data)[ni].heap.empty()) {
    32263226          _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());
  • lemon/math.h

    r511 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5757
    5858  ///Check whether the parameter is NaN or not
    59  
     59
    6060  ///This function checks whether the parameter is NaN or not.
    6161  ///Is should be equivalent with std::isnan(), but it is not
  • lemon/min_cost_arborescence.h

    r825 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    129129  public:
    130130
    131     /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 
    132     /// of the algorithm. 
     131    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class"
     132    /// of the algorithm.
    133133    typedef TR Traits;
    134134    /// The type of the underlying digraph.
     
    437437    /// \ref named-templ-param "Named parameter" for setting
    438438    /// \c PredMap type.
    439     /// It must meet the \ref concepts::WriteMap "WriteMap" concept, 
     439    /// It must meet the \ref concepts::WriteMap "WriteMap" concept,
    440440    /// and its value type must be the \c Arc type of the digraph.
    441441    template <class T>
  • lemon/network_simplex.h

    r862 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9898      UNBOUNDED
    9999    };
    100    
     100
    101101    /// \brief Constants for selecting the type of the supply constraints.
    102102    ///
     
    116116      LEQ
    117117    };
    118    
     118
    119119    /// \brief Constants for selecting the pivot rule.
    120120    ///
     
    159159      ALTERING_LIST
    160160    };
    161    
     161
    162162  private:
    163163
     
    228228    int stem, par_stem, new_stem;
    229229    Value delta;
    230    
     230
    231231    const Value MAX;
    232232
    233233  public:
    234  
     234
    235235    /// \brief Constant for infinite upper bounds (capacities).
    236236    ///
     
    499499        }
    500500        if (_curr_length == 0) return false;
    501      
    502       search_end:       
     501
     502      search_end:
    503503        _minor_count = 1;
    504504        _next_arc = e;
     
    609609        }
    610610        if (_curr_length == 0) return false;
    611        
     611
    612612      search_end:
    613613
     
    635635    /// \param graph The digraph the algorithm runs on.
    636636    /// \param arc_mixing Indicate if the arcs have to be stored in a
    637     /// mixed order in the internal data structure. 
     637    /// mixed order in the internal data structure.
    638638    /// In special cases, it could lead to better overall performance,
    639639    /// but it is usually slower. Therefore it is disabled by default.
     
    650650      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
    651651        "The cost type of NetworkSimplex must be signed");
    652        
     652
    653653      // Reset data structures
    654654      reset();
     
    764764      return *this;
    765765    }
    766    
     766
    767767    /// \brief Set the type of the supply constraints.
    768768    ///
     
    790790    /// This function runs the algorithm.
    791791    /// The paramters can be specified using functions \ref lowerMap(),
    792     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 
     792    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
    793793    /// \ref supplyType().
    794794    /// For example,
     
    945945        }
    946946      }
    947      
     947
    948948      // Reset parameters
    949949      resetParams();
    950950      return *this;
    951951    }
    952    
     952
    953953    /// @}
    954954
     
    10901090        _state[i] = STATE_LOWER;
    10911091      }
    1092      
     1092
    10931093      // Set data for the artificial root node
    10941094      _root = _node_num;
     
    12641264      for (int u = second; u != join; u = _parent[u]) {
    12651265        e = _pred[u];
    1266         d = _forward[u] ? 
     1266        d = _forward[u] ?
    12671267          (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
    12681268        if (d <= delta) {
     
    15681568        }
    15691569      }
    1570      
     1570
    15711571      // Check feasibility
    15721572      for (int e = _search_arc_num; e != _all_arc_num; ++e) {
     
    15851585        }
    15861586      }
    1587      
     1587
    15881588      // Shift potentials to meet the requirements of the GEQ/LEQ type
    15891589      // optimality conditions
  • lemon/path.h

    r803 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    967967    };
    968968
    969    
     969
    970970    template <typename From, typename To,
    971971              bool revEnable = RevPathTagIndicator<From>::value>
     
    973973      static void copy(const From& from, To& to) {
    974974        PathCopySelectorForward<From, To>::copy(from, to);
    975       }     
     975      }
    976976    };
    977977
     
    980980      static void copy(const From& from, To& to) {
    981981        PathCopySelectorBackward<From, To>::copy(from, to);
    982       }     
     982      }
    983983    };
    984984
  • lemon/planarity.h

    r828 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    141141    class PlanarityChecking {
    142142    private:
    143      
     143
    144144      TEMPLATE_GRAPH_TYPEDEFS(Graph);
    145145
     
    147147
    148148    private:
    149      
     149
    150150      typedef typename Graph::template NodeMap<Arc> PredMap;
    151      
     151
    152152      typedef typename Graph::template EdgeMap<bool> TreeMap;
    153      
     153
    154154      typedef typename Graph::template NodeMap<int> OrderMap;
    155155      typedef std::vector<Node> OrderList;
     
    222222
    223223          for (typename MergeRoots::Value::iterator it =
    224                  merge_roots[node].begin(); 
     224                 merge_roots[node].begin();
    225225               it != merge_roots[node].end(); ++it) {
    226226            int rn = *it;
     
    433433
    434434              bool rd;
    435               if (!external(xnode, rorder, child_lists, 
     435              if (!external(xnode, rorder, child_lists,
    436436                            ancestor_map, low_map)) {
    437437                rd = true;
  • lemon/preflow.h

    r825 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/smart_graph.h

    r787 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    187187  ///\ref SmartDigraph is a simple and fast digraph implementation.
    188188  ///It is also quite memory efficient but at the price
    189   ///that it does not support node and arc deletion 
     189  ///that it does not support node and arc deletion
    190190  ///(except for the Snapshot feature).
    191191  ///
     
    336336    ///arcs from a SmartDigraph structure.
    337337    ///
    338     ///\note After a state is restored, you cannot restore a later state, 
     338    ///\note After a state is restored, you cannot restore a later state,
    339339    ///i.e. you cannot add the removed nodes and arcs again using
    340340    ///another Snapshot instance.
     
    615615  /// \ref SmartGraph is a simple and fast graph implementation.
    616616  /// It is also quite memory efficient but at the price
    617   /// that it does not support node and edge deletion 
     617  /// that it does not support node and edge deletion
    618618  /// (except for the Snapshot feature).
    619619  ///
     
    762762    ///edges from a SmartGraph structure.
    763763    ///
    764     ///\note After a state is restored, you cannot restore a later state, 
     764    ///\note After a state is restored, you cannot restore a later state,
    765765    ///i.e. you cannot add the removed nodes and edges again using
    766766    ///another Snapshot instance.
  • lemon/soplex.cc

    r746 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    288288
    289289    _clear_temporals();
    290    
     290
    291291    _applyMessageLevel();
    292292
  • lemon/soplex.h

    r746 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/static_graph.h

    r787 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3232  public:
    3333
    34     StaticDigraphBase() 
    35       : built(false), node_num(0), arc_num(0), 
     34    StaticDigraphBase()
     35      : built(false), node_num(0), arc_num(0),
    3636        node_first_out(NULL), node_first_in(NULL),
    37         arc_source(NULL), arc_target(NULL), 
     37        arc_source(NULL), arc_target(NULL),
    3838        arc_next_in(NULL), arc_next_out(NULL) {}
    39    
     39
    4040    ~StaticDigraphBase() {
    4141      if (built) {
     
    6363
    6464    class Arc {
    65       friend class StaticDigraphBase;     
     65      friend class StaticDigraphBase;
    6666    protected:
    6767      int id;
     
    8484    static void next(Arc& e) { --e.id; }
    8585
    86     void firstOut(Arc& e, const Node& n) const { 
    87       e.id = node_first_out[n.id] != node_first_out[n.id + 1] ? 
     86    void firstOut(Arc& e, const Node& n) const {
     87      e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
    8888        node_first_out[n.id] : -1;
    8989    }
     
    114114      typedef typename Digraph::Arc Arc;
    115115
    116       ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef) 
     116      ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
    117117        : digraph(_graph), nodeRef(_nodeRef) {}
    118      
     118
    119119      bool operator()(const Arc& left, const Arc& right) const {
    120         return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
     120        return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
    121121      }
    122122    private:
     
    124124      const NodeRefMap& nodeRef;
    125125    };
    126    
     126
    127127  public:
    128128
    129129    typedef True BuildTag;
    130    
     130
    131131    void clear() {
    132132      if (built) {
     
    142142      arc_num = 0;
    143143    }
    144    
     144
    145145    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
    146146    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
     
    184184            int target = nodeRef[digraph.target(*it)].id;
    185185            arcRef[*it] = Arc(arc_index);
    186             arc_source[arc_index] = source; 
     186            arc_source[arc_index] = source;
    187187            arc_target[arc_index] = target;
    188188            arc_next_in[arc_index] = node_first_in[target];
     
    198198      node_first_out[node_num] = arc_num;
    199199    }
    200    
     200
    201201    template <typename ArcListIterator>
    202202    void build(int n, ArcListIterator first, ArcListIterator last) {
     
    213213      arc_next_out = new int[arc_num];
    214214      arc_next_in = new int[arc_num];
    215      
     215
    216216      for (int i = 0; i != node_num; ++i) {
    217217        node_first_in[i] = -1;
    218       }     
    219      
     218      }
     219
    220220      int arc_index = 0;
    221221      for (int i = 0; i != node_num; ++i) {
     
    283283  /// Since this digraph structure is completely static, its nodes and arcs
    284284  /// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>
    285   /// and <tt>[0..arcNum()-1]</tt>, respectively. 
     285  /// and <tt>[0..arcNum()-1]</tt>, respectively.
    286286  /// The index of an item is the same as its ID, it can be obtained
    287287  /// using the corresponding \ref index() or \ref concepts::Digraph::id()
     
    300300
    301301    typedef ExtendedStaticDigraphBase Parent;
    302  
     302
    303303  public:
    304  
     304
    305305    /// \brief Constructor
    306306    ///
     
    350350    /// This method also makes possible to copy a digraph to a StaticDigraph
    351351    /// structure using \ref DigraphCopy.
    352     /// 
     352    ///
    353353    /// \param digraph An existing digraph to be copied.
    354354    /// \param nodeRef The node references will be copied into this map.
     
    371371      Parent::build(digraph, nodeRef, arcRef);
    372372    }
    373  
     373
    374374    /// \brief Build the digraph from an arc list.
    375375    ///
     
    422422    using Parent::fastNextOut;
    423423    using Parent::fastLastOut;
    424    
     424
    425425  public:
    426426
     
    433433
    434434      OutArcIt(const StaticDigraph& digraph, const Node& node) {
    435         digraph.fastFirstOut(*this, node);
    436         digraph.fastLastOut(last, node);
     435        digraph.fastFirstOut(*this, node);
     436        digraph.fastLastOut(last, node);
    437437        if (last == *this) *this = INVALID;
    438438      }
     
    444444      }
    445445
    446       OutArcIt& operator++() { 
     446      OutArcIt& operator++() {
    447447        StaticDigraph::fastNextOut(*this);
    448448        if (last == *this) *this = INVALID;
    449         return *this; 
     449        return *this;
    450450      }
    451451
  • lemon/suurballe.h

    r863 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6666    /// and it must have an \c addBack() function.
    6767    typedef lemon::Path<Digraph> Path;
    68    
     68
    6969    /// The cross reference type used for the heap.
    7070    typedef typename GR::template NodeMap<int> HeapCrossRef;
     
    159159      Node _s;
    160160      Node _t;
    161      
     161
    162162      PotentialMap _dist;
    163163      std::vector<Node> _proc_nodes;
     
    168168      ResidualDijkstra(Suurballe &srb) :
    169169        _graph(srb._graph), _length(srb._length),
    170         _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred), 
     170        _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred),
    171171        _s(srb._s), _t(srb._t), _dist(_graph) {}
    172        
     172
    173173      // Run the algorithm and return true if a path is found
    174174      // from the source node to the target node.
     
    178178
    179179    private:
    180    
     180
    181181      // Execute the algorithm for the first time (the flow and potential
    182182      // functions have to be identically zero).
     
    349349      typedef Suurballe<GR, LEN, SetPathTraits<T> > Create;
    350350    };
    351    
     351
    352352    template <typename H, typename CR>
    353353    struct SetHeapTraits : public Traits {
     
    360360    ///
    361361    /// \ref named-templ-param "Named parameter" for setting \c Heap
    362     /// and \c HeapCrossRef types with automatic allocation. 
     362    /// and \c HeapCrossRef types with automatic allocation.
    363363    /// They will be used for internal Dijkstra computations.
    364364    /// The heap type must conform to the \ref lemon::concepts::Heap "Heap"
     
    398398    // The pred arc map
    399399    PredMap _pred;
    400    
     400
    401401    // Data for full init
    402402    PotentialMap *_init_dist;
     
    556556      dijk.distMap(*_init_dist).predMap(*_init_pred);
    557557      dijk.run(s);
    558      
     558
    559559      _full_init = true;
    560560    }
     
    600600      _t = t;
    601601      ResidualDijkstra dijkstra(*this);
    602      
     602
    603603      // Initialization
    604604      for (ArcIt e(_graph); e != INVALID; ++e) {
     
    614614          (*_flow)[e] = 1;
    615615          u = _graph.source(e);
    616         }       
     616        }
    617617        _path_num = 1;
    618618      } else {
  • lemon/unionfind.h

    r875 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • test/bellman_ford_test.cc

    r844 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9898    pp = const_bf_test.path(t);
    9999    pp = const_bf_test.negativeCycle();
    100    
     100
    101101    for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
    102102  }
     
    111111    concepts::ReadWriteMap<Node,Arc> pred_map;
    112112    concepts::ReadWriteMap<Node,Value> dist_map;
    113    
     113
    114114    bf_test
    115115      .lengthMap(length_map)
     
    190190  check(pathSource(gr, p) == s, "path() found a wrong path.");
    191191  check(pathTarget(gr, p) == t, "path() found a wrong path.");
    192  
     192
    193193  ListPath<Digraph> path;
    194194  Value dist;
     
    229229  SmartDigraph gr;
    230230  IntArcMap length(gr);
    231  
     231
    232232  Node n1 = gr.addNode();
    233233  Node n2 = gr.addNode();
    234234  Node n3 = gr.addNode();
    235235  Node n4 = gr.addNode();
    236  
     236
    237237  Arc a1 = gr.addArc(n1, n2);
    238238  Arc a2 = gr.addArc(n2, n2);
    239  
     239
    240240  length[a1] = 2;
    241241  length[a2] = -1;
    242  
     242
    243243  {
    244244    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
     
    248248          "Wrong negative cycle.");
    249249  }
    250  
     250
    251251  length[a2] = 0;
    252  
     252
    253253  {
    254254    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
     
    257257          "Negative cycle should not be found.");
    258258  }
    259  
     259
    260260  length[gr.addArc(n1, n3)] = 5;
    261261  length[gr.addArc(n4, n3)] = 1;
    262262  length[gr.addArc(n2, n4)] = 2;
    263263  length[gr.addArc(n3, n2)] = -4;
    264  
     264
    265265  {
    266266    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
  • test/bfs_test.cc

    r585 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8484    b = const_bfs_test.emptyQueue();
    8585    i = const_bfs_test.queueSize();
    86    
     86
    8787    bfs_test.start();
    8888    bfs_test.start(t);
     
    105105      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    106106      ::Create bfs_test(G);
    107      
     107
    108108    concepts::ReadWriteMap<Node,Arc> pred_map;
    109109    concepts::ReadWriteMap<Node,int> dist_map;
    110110    concepts::ReadWriteMap<Node,bool> reached_map;
    111111    concepts::WriteMap<Node,bool> processed_map;
    112    
     112
    113113    bfs_test
    114114      .predMap(pred_map)
     
    120120    bfs_test.run(s,t);
    121121    bfs_test.run();
    122    
     122
    123123    bfs_test.init();
    124124    bfs_test.addSource(s);
     
    129129    b = bfs_test.emptyQueue();
    130130    i = bfs_test.queueSize();
    131    
     131
    132132    bfs_test.start();
    133133    bfs_test.start(t);
  • test/circulation_test.cc

    r689 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8282  CirculationType circ_test(g, lcap, ucap, supply);
    8383  const CirculationType& const_circ_test = circ_test;
    84    
     84
    8585  circ_test
    8686    .lowerMap(lcap)
     
    8888    .supplyMap(supply)
    8989    .flowMap(flow);
    90  
     90
    9191  const CirculationType::Elevator& elev = const_circ_test.elevator();
    9292  circ_test.elevator(const_cast<CirculationType::Elevator&>(elev));
     
    103103  b = const_circ_test.barrier(n);
    104104  const_circ_test.barrierMap(bar);
    105  
     105
    106106  ignore_unused_variable_warning(fm);
    107107}
  • test/connectivity_test.cc

    r649 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030  typedef ListDigraph Digraph;
    3131  typedef Undirector<Digraph> Graph;
    32  
    33   {
    34     Digraph d;
    35     Digraph::NodeMap<int> order(d);
    36     Graph g(d);
    37    
     32
     33  {
     34    Digraph d;
     35    Digraph::NodeMap<int> order(d);
     36    Graph g(d);
     37
    3838    check(stronglyConnected(d), "The empty digraph is strongly connected");
    3939    check(countStronglyConnectedComponents(d) == 0,
     
    4949    check(countBiEdgeConnectedComponents(g) == 0,
    5050          "The empty graph has 0 bi-edge-connected component");
    51          
     51
    5252    check(dag(d), "The empty digraph is DAG.");
    5353    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
     
    8383    check(countBiEdgeConnectedComponents(g) == 1,
    8484          "This graph has 1 bi-edge-connected component");
    85          
     85
    8686    check(dag(d), "This digraph is DAG.");
    8787    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
     
    102102    Digraph::NodeMap<int> order(d);
    103103    Graph g(d);
    104    
     104
    105105    Digraph::Node n1 = d.addNode();
    106106    Digraph::Node n2 = d.addNode();
     
    109109    Digraph::Node n5 = d.addNode();
    110110    Digraph::Node n6 = d.addNode();
    111    
     111
    112112    d.addArc(n1, n3);
    113113    d.addArc(n3, n2);
     
    137137    check(!parallelFree(g), "This graph is not parallel-free.");
    138138    check(!simpleGraph(g), "This graph is not simple.");
    139    
     139
    140140    d.addArc(n3, n3);
    141    
     141
    142142    check(!loopFree(d), "This digraph is not loop-free.");
    143143    check(!loopFree(g), "This graph is not loop-free.");
    144144    check(!simpleGraph(d), "This digraph is not simple.");
    145    
     145
    146146    d.addArc(n3, n2);
    147    
     147
    148148    check(!parallelFree(d), "This digraph is not parallel-free.");
    149149  }
    150  
     150
    151151  {
    152152    Digraph d;
    153153    Digraph::ArcMap<bool> cutarcs(d, false);
    154154    Graph g(d);
    155    
     155
    156156    Digraph::Node n1 = d.addNode();
    157157    Digraph::Node n2 = d.addNode();
     
    173173    d.addArc(n6, n7);
    174174    d.addArc(n7, n6);
    175    
     175
    176176    check(!stronglyConnected(d), "This digraph is not strongly connected");
    177177    check(countStronglyConnectedComponents(d) == 3,
     
    236236    Digraph d;
    237237    Digraph::NodeMap<int> order(d);
    238    
     238
    239239    Digraph::Node belt = d.addNode();
    240240    Digraph::Node trousers = d.addNode();
     
    256256    d.addArc(shirt, necktie);
    257257    d.addArc(necktie, coat);
    258    
     258
    259259    check(dag(d), "This digraph is DAG.");
    260260    topologicalSort(d, order);
     
    268268    ListGraph g;
    269269    ListGraph::NodeMap<bool> map(g);
    270    
     270
    271271    ListGraph::Node n1 = g.addNode();
    272272    ListGraph::Node n2 = g.addNode();
     
    284284    g.addEdge(n4, n7);
    285285    g.addEdge(n5, n7);
    286    
     286
    287287    check(bipartite(g), "This graph is bipartite");
    288288    check(bipartitePartitions(g, map), "This graph is bipartite");
    289    
     289
    290290    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
    291291          "Wrong bipartitePartitions()");
  • test/dfs_test.cc

    r585 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8484    b = const_dfs_test.emptyQueue();
    8585    i = const_dfs_test.queueSize();
    86    
     86
    8787    dfs_test.start();
    8888    dfs_test.start(t);
     
    110110    concepts::ReadWriteMap<Node,bool> reached_map;
    111111    concepts::WriteMap<Node,bool> processed_map;
    112    
     112
    113113    dfs_test
    114114      .predMap(pred_map)
     
    127127    b = dfs_test.emptyQueue();
    128128    i = dfs_test.queueSize();
    129    
     129
    130130    dfs_test.start();
    131131    dfs_test.start(t);
  • test/digraph_test.cc

    r780 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    393393  SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
    394394  SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
    395  
     395
    396396  StaticDigraph G;
    397  
     397
    398398  checkGraphNodeList(G, 0);
    399399  checkGraphArcList(G, 0);
     
    465465
    466466  G.build(6, arcs.begin(), arcs.end());
    467  
     467
    468468  checkGraphNodeList(G, 6);
    469469  checkGraphArcList(G, 9);
     
    489489  checkGraphNodeMap(G);
    490490  checkGraphArcMap(G);
    491  
     491
    492492  int n = G.nodeNum();
    493493  int m = G.arcNum();
  • test/dijkstra_test.cc

    r585 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8686    b = const_dijkstra_test.emptyQueue();
    8787    i = const_dijkstra_test.queueSize();
    88    
     88
    8989    dijkstra_test.start();
    9090    dijkstra_test.start(t);
     
    110110      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    111111      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    112       ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >, 
     112      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
    113113                concepts::ReadWriteMap<Node,int> >
    114114      ::Create dijkstra_test(G,length);
     
    120120    concepts::ReadWriteMap<Node,int> heap_cross_ref;
    121121    BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref);
    122    
     122
    123123    dijkstra_test
    124124      .lengthMap(length_map)
     
    137137    b = dijkstra_test.emptyQueue();
    138138    i = dijkstra_test.queueSize();
    139    
     139
    140140    dijkstra_test.start();
    141141    dijkstra_test.start(t);
  • test/edge_set_test.cc

    r512 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • test/euler_test.cc

    r592 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8686  typedef ListDigraph Digraph;
    8787  typedef Undirector<Digraph> Graph;
    88  
    89   {
    90     Digraph d;
    91     Graph g(d);
    92    
     88
     89  {
     90    Digraph d;
     91    Graph g(d);
     92
    9393    checkDiEulerIt(d);
    9494    checkDiEulerIt(g);
     
    129129    Digraph::Node n2 = d.addNode();
    130130    Digraph::Node n3 = d.addNode();
    131    
     131
    132132    d.addArc(n1, n2);
    133133    d.addArc(n2, n1);
     
    154154    Digraph::Node n5 = d.addNode();
    155155    Digraph::Node n6 = d.addNode();
    156    
     156
    157157    d.addArc(n1, n2);
    158158    d.addArc(n2, n4);
     
    190190    Digraph::Node n4 = d.addNode();
    191191    Digraph::Node n5 = d.addNode();
    192    
     192
    193193    d.addArc(n1, n2);
    194194    d.addArc(n2, n3);
     
    212212    Digraph::Node n2 = d.addNode();
    213213    Digraph::Node n3 = d.addNode();
    214    
     214
    215215    d.addArc(n1, n2);
    216216    d.addArc(n2, n3);
  • test/fractional_matching_test.cc

    r872 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    239239  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
    240240    check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
    241           (e == mfm.matching(graph.v(e)) ? 1 : 0) == 
     241          (e == mfm.matching(graph.v(e)) ? 1 : 0) ==
    242242          mfm.matching(e), "Invalid matching");
    243243  }
     
    293293    for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
    294294      check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
    295             (e == mfm.matching(graph.v(e)) ? 1 : 0) == 
     295            (e == mfm.matching(graph.v(e)) ? 1 : 0) ==
    296296            mfm.matching(e), "Invalid matching");
    297297    }
     
    351351  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
    352352    check((e == mwfm.matching(graph.u(e)) ? 1 : 0) +
    353           (e == mwfm.matching(graph.v(e)) ? 1 : 0) == 
     353          (e == mwfm.matching(graph.v(e)) ? 1 : 0) ==
    354354          mwfm.matching(e), "Invalid matching");
    355355  }
     
    411411  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
    412412    check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) +
    413           (e == mwpfm.matching(graph.v(e)) ? 1 : 0) == 
     413          (e == mwpfm.matching(graph.v(e)) ? 1 : 0) ==
    414414          mwpfm.matching(e), "Invalid matching");
    415415  }
  • test/gomory_hu_test.cc

    r596 r877  
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
     4 *
     5 * Copyright (C) 2003-2010
     6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8 *
     9 * Permission to use, modify and distribute this software is granted
     10 * provided that this copyright notice appears in all copies. For
     11 * precise terms see the accompanying LICENSE file.
     12 *
     13 * This software is provided "AS IS" with no warranty of any kind,
     14 * express or implied, and with no claim as to its suitability for any
     15 * purpose.
     16 *
     17 */
     18
    119#include <iostream>
    220
     
    3452  "source 0\n"
    3553  "target 3\n";
    36  
     54
    3755void checkGomoryHuCompile()
    3856{
     
    7088
    7189int cutValue(const Graph& graph, const BoolNodeMap& cut,
    72              const IntEdgeMap& capacity) {
     90             const IntEdgeMap& capacity) {
    7391
    7492  int sum = 0;
     
    108126      int sum=0;
    109127      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
    110         sum+=capacity[a]; 
     128        sum+=capacity[a];
    111129      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
    112130
     
    119137    }
    120138  }
    121  
     139
    122140  return 0;
    123141}
  • test/graph_test.cc

    r740 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    265265  checkGraphEdgeList(G, 3);
    266266  checkGraphArcList(G, 6);
    267  
     267
    268268  G.addEdge(G.addNode(), G.addNode());
    269269
     
    514514  G.resize(dim);
    515515  check(G.dimension() == dim, "Wrong dimension");
    516  
     516
    517517  checkGraphNodeList(G, 1 << dim);
    518518  checkGraphEdgeList(G, dim * (1 << (dim-1)));
  • test/hao_orlin_test.cc

    r597 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8484
    8585template <typename Graph, typename CapMap, typename CutMap>
    86 typename CapMap::Value 
     86typename CapMap::Value
    8787  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
    8888{
     
    111111    ho.run();
    112112    ho.minCutMap(cut);
    113    
     113
    114114    check(ho.minCutValue() == 1, "Wrong cut value");
    115115    check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
     
    127127    ho.run();
    128128    ho.minCutMap(cut);
    129    
     129
    130130    check(ho.minCutValue() == 1, "Wrong cut value");
    131131    check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
    132132  }
    133  
     133
    134134  typedef Undirector<SmartDigraph> UGraph;
    135135  UGraph ugraph(graph);
    136  
     136
    137137  {
    138138    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
    139139    ho.run();
    140140    ho.minCutMap(cut);
    141    
     141
    142142    check(ho.minCutValue() == 2, "Wrong cut value");
    143143    check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
     
    147147    ho.run();
    148148    ho.minCutMap(cut);
    149    
     149
    150150    check(ho.minCutValue() == 5, "Wrong cut value");
    151151    check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
     
    155155    ho.run();
    156156    ho.minCutMap(cut);
    157    
     157
    158158    check(ho.minCutValue() == 5, "Wrong cut value");
    159159    check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
  • test/maps_test.cc

    r789 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    226226
    227227    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
    228     MapToFunctor<ReadMap<A,B> > map = MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
     228    MapToFunctor<ReadMap<A,B> > map =
     229      MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
    229230
    230231    check(functorToMap(&func)[A()] == 3,
     
    378379          it != map2.end(); ++it )
    379380      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    380    
     381
    381382    typedef ListDigraph Graph;
    382383    DIGRAPH_TYPEDEFS(Graph);
     
    387388    Node n2 = gr.addNode();
    388389    Node n3 = gr.addNode();
    389    
     390
    390391    gr.addArc(n3, n0);
    391392    gr.addArc(n3, n2);
     
    393394    gr.addArc(n2, n1);
    394395    gr.addArc(n0, n1);
    395    
     396
    396397    {
    397398      std::vector<Node> v;
     
    404405      std::vector<Node> v(countNodes(gr));
    405406      dfs(gr).processedMap(loggerBoolMap(v.begin())).run();
    406      
     407
    407408      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
    408409            "Something is wrong with LoggerBoolMap");
    409410    }
    410411  }
    411  
     412
    412413  // IdMap, RangeIdMap
    413414  {
     
    419420    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();
    420421    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();
    421    
     422
    422423    Graph gr;
    423424    IdMap<Graph, Node> nmap(gr);
     
    425426    RangeIdMap<Graph, Node> nrmap(gr);
    426427    RangeIdMap<Graph, Arc> armap(gr);
    427    
     428
    428429    Node n0 = gr.addNode();
    429430    Node n1 = gr.addNode();
    430431    Node n2 = gr.addNode();
    431    
     432
    432433    Arc a0 = gr.addArc(n0, n1);
    433434    Arc a1 = gr.addArc(n0, n2);
    434435    Arc a2 = gr.addArc(n2, n1);
    435436    Arc a3 = gr.addArc(n2, n0);
    436    
     437
    437438    check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap");
    438439    check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap");
     
    446447    check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap");
    447448    check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap");
    448    
     449
    449450    check(nrmap.size() == 3 && armap.size() == 4,
    450451          "Wrong RangeIdMap::size()");
     
    453454    check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap");
    454455    check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap");
    455    
     456
    456457    check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap");
    457458    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
     
    461462    check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap");
    462463    check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap");
    463    
     464
    464465    gr.erase(n1);
    465    
     466
    466467    if (nrmap[n0] == 1) nrmap.swap(n0, n2);
    467468    nrmap.swap(n2, n0);
    468469    if (armap[a1] == 1) armap.swap(a1, a3);
    469470    armap.swap(a3, a1);
    470    
     471
    471472    check(nrmap.size() == 2 && armap.size() == 2,
    472473          "Wrong RangeIdMap::size()");
     
    474475    check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap");
    475476    check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap");
    476    
     477
    477478    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
    478479    check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap");
     
    481482    check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap");
    482483  }
    483  
     484
    484485  // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap
    485486  {
    486487    typedef ListGraph Graph;
    487488    GRAPH_TYPEDEFS(Graph);
    488    
     489
    489490    checkConcept<ReadMap<Arc, Node>, SourceMap<Graph> >();
    490491    checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >();
     
    498499    Node n1 = gr.addNode();
    499500    Node n2 = gr.addNode();
    500    
     501
    501502    gr.addEdge(n0,n1);
    502503    gr.addEdge(n1,n2);
     
    505506    gr.addEdge(n1,n2);
    506507    gr.addEdge(n0,n1);
    507    
     508
    508509    for (EdgeIt e(gr); e != INVALID; ++e) {
    509510      check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");
    510511      check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");
    511512    }
    512    
     513
    513514    check(mapCompare(gr,
    514515          sourceMap(orienter(gr, constMap<Edge, bool>(true))),
     
    520521    OutDegMap<Digraph> odm(dgr);
    521522    InDegMap<Digraph> idm(dgr);
    522    
     523
    523524    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap");
    524525    check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
    525    
     526
    526527    gr.addEdge(n2, n0);
    527528
     
    529530    check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
    530531  }
    531  
     532
    532533  // CrossRefMap
    533534  {
     
    541542    checkConcept<ReadWriteMap<Node, double>,
    542543                 CrossRefMap<Graph, Node, double> >();
    543    
     544
    544545    Graph gr;
    545546    typedef CrossRefMap<Graph, Node, char> CRMap;
    546547    CRMap map(gr);
    547    
     548
    548549    Node n0 = gr.addNode();
    549550    Node n1 = gr.addNode();
    550551    Node n2 = gr.addNode();
    551    
     552
    552553    map.set(n0, 'A');
    553554    map.set(n1, 'B');
    554555    map.set(n2, 'C');
    555    
     556
    556557    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,
    557558          "Wrong CrossRefMap");
     
    562563    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
    563564          "Wrong CrossRefMap::count()");
    564    
     565
    565566    CRMap::ValueIt it = map.beginValue();
    566567    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
    567568          it == map.endValue(), "Wrong value iterator");
    568    
     569
    569570    map.set(n2, 'A');
    570571
     
    604605    checkConcept<ReadWriteMap<Node, int>,
    605606                 CrossRefMap<Graph, Node, int> >();
    606    
     607
    607608    Graph gr;
    608609    typedef CrossRefMap<Graph, Node, char> CRMap;
    609610    typedef CRMap::ValueIterator ValueIt;
    610611    CRMap map(gr);
    611    
     612
    612613    Node n0 = gr.addNode();
    613614    Node n1 = gr.addNode();
    614615    Node n2 = gr.addNode();
    615    
     616
    616617    map.set(n0, 'A');
    617618    map.set(n1, 'B');
     
    630631          it == map.endValue(), "Wrong value iterator");
    631632  }
    632  
     633
    633634  // Iterable bool map
    634635  {
     
    818819
    819820  }
    820  
     821
    821822  // Graph map utilities:
    822823  // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
     
    830831    Node n2 = g.addNode();
    831832    Node n3 = g.addNode();
    832    
     833
    833834    SmartDigraph::NodeMap<int> map1(g);
    834835    SmartDigraph::ArcMap<char> map2(g);
    835836    ConstMap<Node, A> cmap1 = A();
    836837    ConstMap<Arc, C> cmap2 = C(0);
    837    
     838
    838839    map1[n1] = 10;
    839840    map1[n2] = 5;
    840841    map1[n3] = 12;
    841    
     842
    842843    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
    843844    check(mapMin(g, map1) == n2, "Wrong mapMin()");
     
    858859    Arc a3 = g.addArc(n2, n3);
    859860    Arc a4 = g.addArc(n3, n1);
    860    
     861
    861862    map2[a1] = 'b';
    862863    map2[a2] = 'a';
     
    925926    check(mapCountIf(g, map2, Less<char>('a')) == 0,
    926927          "Wrong mapCountIf()");
    927      
     928
    928929    // MapIt, ConstMapIt
    929930/*
     
    935936    check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12,
    936937          "Wrong NodeMap<>::MapIt");
    937    
     938
    938939    int sum = 0;
    939940    std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum));
     
    952953    SmartDigraph::NodeMap<int> map3(g, 0);
    953954    SmartDigraph::ArcMap<char> map4(g, 'a');
    954    
     955
    955956    check(!mapCompare(g, map1, map3), "Wrong mapCompare()");
    956     check(!mapCompare(g, map2, map4), "Wrong mapCompare()");   
    957    
     957    check(!mapCompare(g, map2, map4), "Wrong mapCompare()");
     958
    958959    mapCopy(g, map1, map3);
    959960    mapCopy(g, map2, map4);
    960961
    961962    check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()");
    962     check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");   
    963    
     963    check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");
     964
    964965    Undirector<SmartDigraph> ug(g);
    965966    Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x');
    966967    Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14);
    967    
     968
    968969    check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
    969970    check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
    970971    check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
    971972    check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
    972    
     973
    973974    mapCopy(g, map2, umap1);
    974975
     
    977978    check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
    978979    check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
    979    
     980
    980981    mapCopy(g, map2, umap1);
    981982    mapCopy(g, umap1, map2);
    982983    mapCopy(ug, map2, umap1);
    983984    mapCopy(ug, umap1, map2);
    984    
     985
    985986    check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
    986987    mapCopy(ug, umap1, umap2);
    987988    check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
    988    
     989
    989990    check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()");
    990991    mapFill(g, map1, 2);
     
    995996    check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()");
    996997  }
    997  
     998
    998999  return 0;
    9991000}
  • test/matching_test.cc

    r870 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    135135  mat_test.startDense();
    136136  mat_test.run();
    137  
     137
    138138  const_mat_test.matchingSize();
    139139  const_mat_test.matching(e);
     
    144144  const_mat_test.mate(n);
    145145
    146   MaxMatching<Graph>::Status stat = 
     146  MaxMatching<Graph>::Status stat =
    147147    const_mat_test.status(n);
    148148  const MaxMatching<Graph>::StatusMap& smap =
     
    171171  mat_test.start();
    172172  mat_test.run();
    173  
     173
    174174  const_mat_test.matchingWeight();
    175175  const_mat_test.matchingSize();
     
    180180  e = mmap[n];
    181181  const_mat_test.mate(n);
    182  
     182
    183183  int k = 0;
    184184  const_mat_test.dualValue();
     
    208208  mat_test.start();
    209209  mat_test.run();
    210  
     210
    211211  const_mat_test.matchingWeight();
    212212  const_mat_test.matching(e);
     
    216216  e = mmap[n];
    217217  const_mat_test.mate(n);
    218  
     218
    219219  int k = 0;
    220220  const_mat_test.dualValue();
     
    426426      MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
    427427      bool result = mwpm.run();
    428      
     428
    429429      check(result == perfect, "Perfect matching found");
    430430      if (perfect) {
     
    437437      mwpm.init();
    438438      bool result = mwpm.start();
    439      
     439
    440440      check(result == perfect, "Perfect matching found");
    441441      if (perfect) {
  • test/min_cost_arborescence_test.cc

    r625 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    111111  b = const_mcarb_test.emptyQueue();
    112112  i = const_mcarb_test.queueSize();
    113  
     113
    114114  c = const_mcarb_test.arborescenceCost();
    115115  b = const_mcarb_test.arborescence(e);
     
    121121  b = const_mcarb_test.reached(n);
    122122  b = const_mcarb_test.processed(n);
    123  
     123
    124124  i = const_mcarb_test.dualNum();
    125125  c = const_mcarb_test.dualValue();
    126126  i = const_mcarb_test.dualSize(i);
    127127  c = const_mcarb_test.dualValue(i);
    128  
     128
    129129  ignore_unused_variable_warning(am);
    130130  ignore_unused_variable_warning(pm);
  • test/min_cost_flow_test.cc

    r830 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5353  "   11     0    0    0    0  -10    0\n"
    5454  "   12   -20  -27    0  -30  -30  -20\n"
    55   "\n"               
     55  "\n"
    5656  "@arcs\n"
    5757  "       cost  cap low1 low2 low3\n"
     
    103103  "6 7     30      0  -1000\n"
    104104  "7 5   -120      0      0\n";
    105  
     105
    106106char test_neg2_lgf[] =
    107107  "@nodes\n"
     
    152152    void constraints() {
    153153      checkConcept<concepts::Digraph, GR>();
    154      
     154
    155155      const Constraints& me = *this;
    156156
     
    181181    typedef concepts::WriteMap<Arc, Value> FlowMap;
    182182    typedef concepts::WriteMap<Node, Cost> PotMap;
    183  
     183
    184184    GR g;
    185185    VAM lower;
     
    235235           typename CM, typename SM, typename FM, typename PM >
    236236bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
    237                      const CM& cost, const SM& supply, const FM& flow, 
     237                     const CM& cost, const SM& supply, const FM& flow,
    238238                     const PM& pi, SupplyType type )
    239239{
     
    248248          (red_cost < 0 && flow[e] == upper[e]);
    249249  }
    250  
     250
    251251  for (NodeIt n(gr); opt && n != INVALID; ++n) {
    252252    typename SM::Value sum = 0;
     
    261261    }
    262262  }
    263  
     263
    264264  return opt;
    265265}
     
    286286    }
    287287  }
    288  
     288
    289289  for (NodeIt n(gr); n != INVALID; ++n) {
    290290    dual_cost -= red_supply[n] * pi[n];
     
    295295    dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0);
    296296  }
    297  
     297
    298298  return dual_cost == total;
    299299}
     
    333333{
    334334  MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr);
    335  
     335
    336336  // Basic tests
    337337  mcf1.upperMap(u).costMap(c).supplyMap(s1);
     
    436436    .node("target", w)
    437437    .run();
    438  
     438
    439439  std::istringstream neg_inp1(test_neg1_lgf);
    440440  DigraphReader<Digraph>(neg1_gr, neg_inp1)
     
    444444    .nodeMap("sup", neg1_s)
    445445    .run();
    446  
     446
    447447  std::istringstream neg_inp2(test_neg2_lgf);
    448448  DigraphReader<Digraph>(neg2_gr, neg_inp2)
     
    450450    .nodeMap("sup", neg2_s)
    451451    .run();
    452  
     452
    453453  // Check the interface of NetworkSimplex
    454454  {
     
    502502
    503503  // Test NetworkSimplex
    504   { 
     504  {
    505505    typedef NetworkSimplex<Digraph> MCF;
    506506    runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true);
     
    515515    runMcfLeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL");
    516516  }
    517  
     517
    518518  // Test CapacityScaling
    519519  {
  • test/min_mean_cycle_test.cc

    r864 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6262  "7 7    4    4    4   -1   0  0  0  1\n";
    6363
    64                        
     64
    6565// Check the interface of an MMC algorithm
    6666template <typename GR, typename Cost>
     
    7878      MmcAlg mmc(me.g, me.cost);
    7979      const MmcAlg& const_mmc = mmc;
    80      
     80
    8181      typename MmcAlg::Tolerance tol = const_mmc.tolerance();
    8282      mmc.tolerance(tol);
    83      
     83
    8484      b = mmc.cycle(p).run();
    8585      b = mmc.findCycleMean();
     
    9393
    9494    typedef concepts::ReadMap<typename GR::Arc, Cost> CM;
    95  
     95
    9696    GR g;
    9797    CM cost;
     
    154154    checkConcept< MmcClassConcept<GR, float>,
    155155                  KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
    156    
     156
    157157    // HartmannOrlinMmc
    158158    checkConcept< MmcClassConcept<GR, int>,
     
    160160    checkConcept< MmcClassConcept<GR, float>,
    161161                  HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
    162    
     162
    163163    // HowardMmc
    164164    checkConcept< MmcClassConcept<GR, int>,
     
    177177    typedef SmartDigraph GR;
    178178    DIGRAPH_TYPEDEFS(GR);
    179    
     179
    180180    GR gr;
    181181    IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
    182182    IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
    183    
     183
    184184    std::istringstream input(test_lgf);
    185185    digraphReader(gr, input).
  • test/preflow_test.cc

    r689 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9595  PreflowType preflow_test(g, cap, n, n);
    9696  const PreflowType& const_preflow_test = preflow_test;
    97  
     97
    9898  const PreflowType::Elevator& elev = const_preflow_test.elevator();
    9999  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
     
    119119  b = const_preflow_test.minCut(n);
    120120  const_preflow_test.minCutMap(cut);
    121  
     121
    122122  ignore_unused_variable_warning(fm);
    123123}
  • test/suurballe_test.cc

    r858 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8282  typedef Digraph::Arc Arc;
    8383  typedef concepts::ReadMap<Arc, VType> LengthMap;
    84  
     84
    8585  typedef Suurballe<Digraph, LengthMap> ST;
    8686  typedef Suurballe<Digraph, LengthMap>
     
    115115  k = suurb_test.findFlow(n, k);
    116116  suurb_test.findPaths();
    117  
     117
    118118  int f;
    119119  VType c;
     
    127127  k = const_suurb_test.pathNum();
    128128  Path<Digraph> p = const_suurb_test.path(k);
    129  
     129
    130130  ignore_unused_variable_warning(fm);
    131131  ignore_unused_variable_warning(pm);
     
    209209  {
    210210    Suurballe<ListDigraph> suurballe(digraph, length);
    211    
     211
    212212    // Find 2 paths
    213213    check(suurballe.run(s, t) == 2, "Wrong number of paths");
     
    220220    for (int i = 0; i < suurballe.pathNum(); ++i)
    221221      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    222    
     222
    223223    // Find 3 paths
    224224    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
     
    231231    for (int i = 0; i < suurballe.pathNum(); ++i)
    232232      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    233    
     233
    234234    // Find 5 paths (only 3 can be found)
    235235    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
     
    243243      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    244244  }
    245  
     245
    246246  // Check fullInit() + start()
    247247  {
    248248    Suurballe<ListDigraph> suurballe(digraph, length);
    249249    suurballe.fullInit(s);
    250    
     250
    251251    // Find 2 paths
    252252    check(suurballe.start(t) == 2, "Wrong number of paths");
  • test/test_tools.h

    r763 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4646    } else { }                                                          \
    4747  }                                                                     \
    48    
     48
    4949
    5050#endif
  • tools/dimacs-solver.cc

    r846 r877  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8989  pre.run();
    9090  if(report) std::cerr << "Run Preflow: " << ti << '\n';
    91   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; 
     91  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
    9292}
    9393
     
    149149  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
    150150  if(report) std::cerr << "\nCardinality of max matching: "
    151                        << mat.matchingSize() << '\n'; 
     151                       << mat.matchingSize() << '\n';
    152152}
    153153
     
    167167      exit(1);
    168168    }
    169  
     169
    170170  switch(desc.type)
    171171    {
     
    239239
    240240  DimacsDescriptor desc = dimacsType(is);
    241  
     241
    242242  if(!ap.given("q"))
    243243    {
     
    264264      std::cout << "\n\n";
    265265    }
    266    
     266
    267267  if(ap.given("double"))
    268268    solve<double, double>(ap,is,os,desc);
Note: See TracChangeset for help on using the changeset viewer.