diff --git a/demo/arg_parser_demo.cc b/demo/arg_parser_demo.cc --- a/demo/arg_parser_demo.cc +++ b/demo/arg_parser_demo.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -69,7 +69,7 @@ // exit(1) on these cases, but this makes Valgrind falsely warn // about memory leaks. ap.throwOnProblems(); - + // Perform the parsing process // (in case of any error it terminates the program) // The try {} construct is necessary only if the ap.trowOnProblems() diff --git a/doc/groups.dox b/doc/groups.dox --- a/doc/groups.dox +++ b/doc/groups.dox @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/doc/mainpage.dox b/doc/mainpage.dox --- a/doc/mainpage.dox +++ b/doc/mainpage.dox @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -25,7 +25,7 @@ and Optimization in Networks. It is a C++ template library providing efficient implementations of common data structures and algorithms with focus on combinatorial optimization -tasks connected mainly with graphs and networks. +tasks connected mainly with graphs and networks. LEMON is an open source @@ -35,7 +35,7 @@ \ref license "license terms". -The project is maintained by the +The project is maintained by the Egerváry Research Group on Combinatorial Optimization \ref egres at the Operations Research Department of the diff --git a/doc/min_cost_flow.dox b/doc/min_cost_flow.dox --- a/doc/min_cost_flow.dox +++ b/doc/min_cost_flow.dox @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -81,7 +81,7 @@ - \f$\pi(u)\leq 0\f$; - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, then \f$\pi(u)=0\f$. - + Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f] @@ -119,7 +119,7 @@ sup(u) \quad \forall u\in V \f] \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] -It means that the total demand must be less or equal to the +It means that the total demand must be less or equal to the total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or positive) and all the demands have to be satisfied, but there could be supplies that are not carried out from the supply diff --git a/lemon/adaptors.h b/lemon/adaptors.h --- a/lemon/adaptors.h +++ b/lemon/adaptors.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -421,7 +421,7 @@ void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { Parent::initialize(digraph); _node_filter = &node_filter; - _arc_filter = &arc_filter; + _arc_filter = &arc_filter; } public: @@ -508,11 +508,11 @@ public: template - class NodeMap - : public SubMapExtender, - LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> { + class NodeMap + : public SubMapExtender, + LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> { typedef SubMapExtender, - LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent; + LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent; public: typedef V Value; @@ -535,9 +535,9 @@ }; template - class ArcMap + class ArcMap : public SubMapExtender, - LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> { + LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> { typedef SubMapExtender, LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> Parent; @@ -582,7 +582,7 @@ void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { Parent::initialize(digraph); _node_filter = &node_filter; - _arc_filter = &arc_filter; + _arc_filter = &arc_filter; } public: @@ -651,10 +651,10 @@ } template - class NodeMap + class NodeMap : public SubMapExtender, LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent; public: @@ -678,7 +678,7 @@ }; template - class ArcMap + class ArcMap : public SubMapExtender, LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> { typedef SubMapExtender, @@ -1021,10 +1021,10 @@ } template - class NodeMap + class NodeMap : public SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent; public: @@ -1048,10 +1048,10 @@ }; template - class ArcMap + class ArcMap : public SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent; public: @@ -1075,10 +1075,10 @@ }; template - class EdgeMap + class EdgeMap : public SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent; public: @@ -1117,8 +1117,8 @@ protected: NF* _node_filter; EF* _edge_filter; - SubGraphBase() - : Parent(), _node_filter(0), _edge_filter(0) { } + SubGraphBase() + : Parent(), _node_filter(0), _edge_filter(0) { } void initialize(GR& graph, NF& node_filter, EF& edge_filter) { Parent::initialize(graph); @@ -1219,10 +1219,10 @@ } template - class NodeMap + class NodeMap : public SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent; public: @@ -1246,10 +1246,10 @@ }; template - class ArcMap + class ArcMap : public SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent; public: @@ -1273,11 +1273,11 @@ }; template - class EdgeMap + class EdgeMap : public SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> { - typedef SubMapExtender, - LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent; + typedef SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent; public: typedef V Value; @@ -1504,7 +1504,7 @@ true> > { #endif typedef DigraphAdaptorExtender< - SubDigraphBase >, + SubDigraphBase >, true> > Parent; public: @@ -1525,7 +1525,7 @@ /// /// Creates a subgraph for the given digraph or graph with the /// given node filter map. - FilterNodes(GR& graph, NF& node_filter) + FilterNodes(GR& graph, NF& node_filter) : Parent(), const_true_map() { Parent::initialize(graph, node_filter, const_true_map); @@ -1563,11 +1563,11 @@ class FilterNodes >::type> : public GraphAdaptorExtender< - SubGraphBase >, + SubGraphBase >, true> > { typedef GraphAdaptorExtender< - SubGraphBase >, + SubGraphBase >, true> > Parent; public: @@ -1653,7 +1653,7 @@ AF, false> > { #endif typedef DigraphAdaptorExtender< - SubDigraphBase >, + SubDigraphBase >, AF, false> > Parent; public: @@ -1761,11 +1761,11 @@ typename EF = typename GR::template EdgeMap > class FilterEdges : public GraphAdaptorExtender< - SubGraphBase >, + SubGraphBase >, EF, false> > { #endif typedef GraphAdaptorExtender< - SubGraphBase >, + SubGraphBase >, EF, false> > Parent; public: @@ -1790,7 +1790,7 @@ /// /// Creates a subgraph for the given graph with the given edge /// filter map. - FilterEdges(GR& graph, EF& edge_filter) + FilterEdges(GR& graph, EF& edge_filter) : Parent(), const_true_map() { Parent::initialize(graph, const_true_map, edge_filter); } @@ -1858,7 +1858,7 @@ Edge _edge; bool _forward; - Arc(const Edge& edge, bool forward) + Arc(const Edge& edge, bool forward) : _edge(edge), _forward(forward) {} public: @@ -2098,7 +2098,7 @@ _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} ArcMapBase(const UndirectorBase& adaptor, const V& value) - : _forward(*adaptor._digraph, value), + : _forward(*adaptor._digraph, value), _backward(*adaptor._digraph, value) {} void set(const Arc& a, const V& value) { @@ -2216,7 +2216,7 @@ typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); } - + typedef EdgeNotifier ArcNotifier; ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); } @@ -2728,7 +2728,7 @@ typename CM = typename DGR::template ArcMap, typename FM = CM, typename TL = Tolerance > - class ResidualDigraph + class ResidualDigraph : public SubDigraph< Undirector, ConstMap >, @@ -2785,7 +2785,7 @@ /// digraph, the capacity map, the flow map, and a tolerance object. ResidualDigraph(const DGR& digraph, const CM& capacity, FM& flow, const TL& tolerance = Tolerance()) - : Parent(), _capacity(&capacity), _flow(&flow), + : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), _node_filter(), _forward_filter(capacity, flow, tolerance), _backward_filter(capacity, flow, tolerance), @@ -2867,7 +2867,7 @@ typedef typename CapacityMap::Value Value; /// Constructor - ResidualCapacity(const ResidualDigraph& adaptor) + ResidualCapacity(const ResidualDigraph& adaptor) : _adaptor(&adaptor) {} /// Returns the value associated with the given residual arc @@ -3447,7 +3447,7 @@ /// This map adaptor class adapts two node maps of the original digraph /// to get a node map of the split digraph. /// Its value type is inherited from the first node map type (\c IN). - /// \tparam IN The type of the node map for the in-nodes. + /// \tparam IN The type of the node map for the in-nodes. /// \tparam OUT The type of the node map for the out-nodes. template class CombinedNodeMap { diff --git a/lemon/arg_parser.cc b/lemon/arg_parser.cc --- a/lemon/arg_parser.cc +++ b/lemon/arg_parser.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -26,8 +26,8 @@ exit(1); else throw(ArgParserException(reason)); } - - + + void ArgParser::_showHelp(void *p) { (static_cast(p))->showHelp(); diff --git a/lemon/arg_parser.h b/lemon/arg_parser.h --- a/lemon/arg_parser.h +++ b/lemon/arg_parser.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -42,10 +42,10 @@ UNKNOWN_OPT, /// Unknown option was given INVALID_OPT /// Invalid combination of options }; - + private: Reason _reason; - + public: ///Constructor ArgParserException(Reason r) throw() : _reason(r) {} @@ -141,7 +141,7 @@ std::vector _file_args; std::string _command_name; - + private: //Bind a function to an option. @@ -155,7 +155,7 @@ void (*func)(void *),void *data); bool _exit_on_problems; - + void _terminate(ArgParserException::Reason reason) const; public: @@ -423,7 +423,7 @@ const std::vector &files() const { return _file_args; } ///Throw instead of exit in case of problems - void throwOnProblems() + void throwOnProblems() { _exit_on_problems=false; } diff --git a/lemon/bellman_ford.h b/lemon/bellman_ford.h --- a/lemon/bellman_ford.h +++ b/lemon/bellman_ford.h @@ -1,8 +1,8 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -36,7 +36,7 @@ namespace lemon { /// \brief Default operation traits for the BellmanFord algorithm class. - /// + /// /// This operation traits class defines all computational operations /// and constants that are used in the Bellman-Ford algorithm. /// The default implementation is based on the \c numeric_limits class. @@ -45,7 +45,7 @@ /// /// \see BellmanFordToleranceOperationTraits template < - typename V, + typename V, bool has_inf = std::numeric_limits::has_infinity> struct BellmanFordDefaultOperationTraits { /// \brief Value type for the algorithm. @@ -86,7 +86,7 @@ return left < right; } }; - + /// \brief Operation traits for the BellmanFord algorithm class /// using tolerance. /// @@ -139,7 +139,7 @@ /// \param LEN The type of the length map. template struct BellmanFordDefaultTraits { - /// The type of the digraph the algorithm runs on. + /// The type of the digraph the algorithm runs on. typedef GR Digraph; /// \brief The type of the map that stores the arc lengths. @@ -158,18 +158,18 @@ /// \see BellmanFordDefaultOperationTraits, /// BellmanFordToleranceOperationTraits typedef BellmanFordDefaultOperationTraits OperationTraits; - - /// \brief The type of the map that stores the last arcs of the + + /// \brief The type of the map that stores the last arcs of the /// shortest paths. - /// + /// /// The type of the map that stores the last /// arcs of the shortest paths. /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename GR::template NodeMap PredMap; /// \brief Instantiates a \c PredMap. - /// - /// This function instantiates a \ref PredMap. + /// + /// This function instantiates a \ref PredMap. /// \param g is the digraph to which we would like to define the /// \ref PredMap. static PredMap *createPredMap(const GR& g) { @@ -184,19 +184,19 @@ /// \brief Instantiates a \c DistMap. /// - /// This function instantiates a \ref DistMap. - /// \param g is the digraph to which we would like to define the + /// This function instantiates a \ref DistMap. + /// \param g is the digraph to which we would like to define the /// \ref DistMap. static DistMap *createDistMap(const GR& g) { return new DistMap(g); } }; - + /// \brief %BellmanFord algorithm class. /// /// \ingroup shortest_path - /// This class provides an efficient implementation of the Bellman-Ford + /// This class provides an efficient implementation of the Bellman-Ford /// algorithm. The maximum time complexity of the algorithm is /// O(ne). /// @@ -207,7 +207,7 @@ /// algorithm instead, since it is more efficient. /// /// The arc lengths are passed to the algorithm using a - /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any + /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any /// kind of length. The type of the length values is determined by the /// \ref concepts::ReadMap::Value "Value" type of the length map. /// @@ -237,7 +237,7 @@ ///The type of the underlying digraph. typedef typename TR::Digraph Digraph; - + /// \brief The type of the arc lengths. typedef typename TR::LengthMap::Value Value; /// \brief The type of the map that stores the arc lengths. @@ -284,20 +284,20 @@ // Creates the maps if necessary. void create_maps() { if(!_pred) { - _local_pred = true; - _pred = Traits::createPredMap(*_gr); + _local_pred = true; + _pred = Traits::createPredMap(*_gr); } if(!_dist) { - _local_dist = true; - _dist = Traits::createDistMap(*_gr); + _local_dist = true; + _dist = Traits::createDistMap(*_gr); } if(!_mask) { _mask = new MaskMap(*_gr); } } - + public : - + typedef BellmanFord Create; /// \name Named Template Parameters @@ -320,11 +320,11 @@ /// \c PredMap type. /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. template - struct SetPredMap + struct SetPredMap : public BellmanFord< Digraph, LengthMap, SetPredMapTraits > { typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits > Create; }; - + template struct SetDistMapTraits : public Traits { typedef T DistMap; @@ -341,7 +341,7 @@ /// \c DistMap type. /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. template - struct SetDistMap + struct SetDistMap : public BellmanFord< Digraph, LengthMap, SetDistMapTraits > { typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits > Create; }; @@ -350,8 +350,8 @@ struct SetOperationTraitsTraits : public Traits { typedef T OperationTraits; }; - - /// \brief \ref named-templ-param "Named parameter" for setting + + /// \brief \ref named-templ-param "Named parameter" for setting /// \c OperationTraits type. /// /// \ref named-templ-param "Named parameter" for setting @@ -363,15 +363,15 @@ typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits > Create; }; - + ///@} protected: - + BellmanFord() {} - public: - + public: + /// \brief Constructor. /// /// Constructor. @@ -381,7 +381,7 @@ _gr(&g), _length(&length), _pred(0), _local_pred(false), _dist(0), _local_dist(false), _mask(0) {} - + ///Destructor. ~BellmanFord() { if(_local_pred) delete _pred; @@ -408,8 +408,8 @@ /// \return (*this) BellmanFord &predMap(PredMap &map) { if(_local_pred) { - delete _pred; - _local_pred=false; + delete _pred; + _local_pred=false; } _pred = ↦ return *this; @@ -426,8 +426,8 @@ /// \return (*this) BellmanFord &distMap(DistMap &map) { if(_local_dist) { - delete _dist; - _local_dist=false; + delete _dist; + _local_dist=false; } _dist = ↦ return *this; @@ -445,28 +445,28 @@ ///@{ /// \brief Initializes the internal data structures. - /// + /// /// Initializes the internal data structures. The optional parameter /// is the initial distance of each node. void init(const Value value = OperationTraits::infinity()) { create_maps(); for (NodeIt it(*_gr); it != INVALID; ++it) { - _pred->set(it, INVALID); - _dist->set(it, value); + _pred->set(it, INVALID); + _dist->set(it, value); } _process.clear(); if (OperationTraits::less(value, OperationTraits::infinity())) { - for (NodeIt it(*_gr); it != INVALID; ++it) { - _process.push_back(it); - _mask->set(it, true); - } + for (NodeIt it(*_gr); it != INVALID; ++it) { + _process.push_back(it); + _mask->set(it, true); + } } else { - for (NodeIt it(*_gr); it != INVALID; ++it) { - _mask->set(it, false); - } + for (NodeIt it(*_gr); it != INVALID; ++it) { + _mask->set(it, false); + } } } - + /// \brief Adds a new source node. /// /// This function adds a new source node. The optional second parameter @@ -474,8 +474,8 @@ void addSource(Node source, Value dst = OperationTraits::zero()) { _dist->set(source, dst); if (!(*_mask)[source]) { - _process.push_back(source); - _mask->set(source, true); + _process.push_back(source); + _mask->set(source, true); } } @@ -500,26 +500,26 @@ /// \see ActiveIt bool processNextRound() { for (int i = 0; i < int(_process.size()); ++i) { - _mask->set(_process[i], false); + _mask->set(_process[i], false); } std::vector nextProcess; std::vector values(_process.size()); for (int i = 0; i < int(_process.size()); ++i) { - values[i] = (*_dist)[_process[i]]; + values[i] = (*_dist)[_process[i]]; } for (int i = 0; i < int(_process.size()); ++i) { - for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { - Node target = _gr->target(it); - Value relaxed = OperationTraits::plus(values[i], (*_length)[it]); - if (OperationTraits::less(relaxed, (*_dist)[target])) { - _pred->set(target, it); - _dist->set(target, relaxed); - if (!(*_mask)[target]) { - _mask->set(target, true); - nextProcess.push_back(target); - } - } - } + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { + Node target = _gr->target(it); + Value relaxed = OperationTraits::plus(values[i], (*_length)[it]); + if (OperationTraits::less(relaxed, (*_dist)[target])) { + _pred->set(target, it); + _dist->set(target, relaxed); + if (!(*_mask)[target]) { + _mask->set(target, true); + nextProcess.push_back(target); + } + } + } } _process.swap(nextProcess); return _process.empty(); @@ -541,23 +541,23 @@ /// \see ActiveIt bool processNextWeakRound() { for (int i = 0; i < int(_process.size()); ++i) { - _mask->set(_process[i], false); + _mask->set(_process[i], false); } std::vector nextProcess; for (int i = 0; i < int(_process.size()); ++i) { - for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { - Node target = _gr->target(it); - Value relaxed = - OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]); - if (OperationTraits::less(relaxed, (*_dist)[target])) { - _pred->set(target, it); - _dist->set(target, relaxed); - if (!(*_mask)[target]) { - _mask->set(target, true); - nextProcess.push_back(target); - } - } - } + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { + Node target = _gr->target(it); + Value relaxed = + OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]); + if (OperationTraits::less(relaxed, (*_dist)[target])) { + _pred->set(target, it); + _dist->set(target, relaxed); + if (!(*_mask)[target]) { + _mask->set(target, true); + nextProcess.push_back(target); + } + } + } } _process.swap(nextProcess); return _process.empty(); @@ -579,7 +579,7 @@ void start() { int num = countNodes(*_gr) - 1; for (int i = 0; i < num; ++i) { - if (processNextWeakRound()) break; + if (processNextWeakRound()) break; } } @@ -591,18 +591,18 @@ /// in order to compute the shortest path to each node and also checks /// if the digraph contains cycles with negative total length. /// - /// The algorithm computes + /// The algorithm computes /// - the shortest path tree (forest), /// - the distance of each node from the root(s). - /// + /// /// \return \c false if there is a negative cycle in the digraph. /// /// \pre init() must be called and at least one root node should be - /// added with addSource() before using this function. + /// added with addSource() before using this function. bool checkedStart() { int num = countNodes(*_gr); for (int i = 0; i < num; ++i) { - if (processNextWeakRound()) return true; + if (processNextWeakRound()) return true; } return _process.empty(); } @@ -626,15 +626,15 @@ /// and build the path manually. /// /// \pre init() must be called and at least one root node should be - /// added with addSource() before using this function. + /// added with addSource() before using this function. void limitedStart(int num) { for (int i = 0; i < num; ++i) { - if (processNextRound()) break; + if (processNextRound()) break; } } - + /// \brief Runs the algorithm from the given root node. - /// + /// /// This method runs the Bellman-Ford algorithm from the given root /// node \c s in order to compute the shortest path to each node. /// @@ -653,10 +653,10 @@ addSource(s); start(); } - + /// \brief Runs the algorithm from the given root node with arc /// number limit. - /// + /// /// This method runs the Bellman-Ford algorithm from the given root /// node \c s in order to compute the shortest path distance for each /// node using only the paths consisting of at most \c num arcs. @@ -682,7 +682,7 @@ addSource(s); limitedStart(num); } - + ///@} /// \brief LEMON iterator for getting the active nodes. @@ -697,7 +697,7 @@ /// \brief Constructor. /// /// Constructor for getting the active nodes of the given BellmanFord - /// instance. + /// instance. ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) { _index = _algorithm->_process.size() - 1; @@ -711,7 +711,7 @@ /// \brief Conversion to \c Node. /// /// Conversion to \c Node. - operator Node() const { + operator Node() const { return _index >= 0 ? _algorithm->_process[_index] : INVALID; } @@ -720,33 +720,33 @@ /// Increment operator. ActiveIt& operator++() { --_index; - return *this; + return *this; } - bool operator==(const ActiveIt& it) const { - return static_cast(*this) == static_cast(it); + bool operator==(const ActiveIt& it) const { + return static_cast(*this) == static_cast(it); } - bool operator!=(const ActiveIt& it) const { - return static_cast(*this) != static_cast(it); + bool operator!=(const ActiveIt& it) const { + return static_cast(*this) != static_cast(it); } - bool operator<(const ActiveIt& it) const { - return static_cast(*this) < static_cast(it); + bool operator<(const ActiveIt& it) const { + return static_cast(*this) < static_cast(it); } - + private: const BellmanFord* _algorithm; int _index; }; - + /// \name Query Functions /// The result of the Bellman-Ford algorithm can be obtained using these /// functions.\n /// Either \ref run() or \ref init() should be called before using them. - + ///@{ /// \brief The shortest path to the given node. - /// + /// /// Gives back the shortest path to the given node from the root(s). /// /// \warning \c t should be reached from the root(s). @@ -757,7 +757,7 @@ { return Path(*_gr, *_pred, t); } - + /// \brief The distance of the given node from the root(s). /// /// Returns the distance of the given node from the root(s). @@ -797,10 +797,10 @@ /// /// \pre Either \ref run() or \ref init() must be called before /// using this function. - Node predNode(Node v) const { - return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); + Node predNode(Node v) const { + return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); } - + /// \brief Returns a const reference to the node map that stores the /// distances of the nodes. /// @@ -810,7 +810,7 @@ /// \pre Either \ref run() or \ref init() must be called before /// using this function. const DistMap &distMap() const { return *_dist;} - + /// \brief Returns a const reference to the node map that stores the /// predecessor arcs. /// @@ -820,7 +820,7 @@ /// \pre Either \ref run() or \ref init() must be called before /// using this function. const PredMap &predMap() const { return *_pred; } - + /// \brief Checks if a node is reached from the root(s). /// /// Returns \c true if \c v is reached from the root(s). @@ -832,7 +832,7 @@ } /// \brief Gives back a negative cycle. - /// + /// /// This function gives back a directed cycle with negative total /// length if the algorithm has already found one. /// Otherwise it gives back an empty path. @@ -859,10 +859,10 @@ } return cycle; } - + ///@} }; - + /// \brief Default traits class of bellmanFord() function. /// /// Default traits class of bellmanFord() function. @@ -870,7 +870,7 @@ /// \tparam LEN The type of the length map. template struct BellmanFordWizardDefaultTraits { - /// The type of the digraph the algorithm runs on. + /// The type of the digraph the algorithm runs on. typedef GR Digraph; /// \brief The type of the map that stores the arc lengths. @@ -892,13 +892,13 @@ /// \brief The type of the map that stores the last /// arcs of the shortest paths. - /// + /// /// The type of the map that stores the last arcs of the shortest paths. /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename GR::template NodeMap PredMap; /// \brief Instantiates a \c PredMap. - /// + /// /// This function instantiates a \ref PredMap. /// \param g is the digraph to which we would like to define the /// \ref PredMap. @@ -914,7 +914,7 @@ /// \brief Instantiates a \c DistMap. /// - /// This function instantiates a \ref DistMap. + /// This function instantiates a \ref DistMap. /// \param g is the digraph to which we would like to define the /// \ref DistMap. static DistMap *createDistMap(const GR &g) { @@ -927,14 +927,14 @@ ///It must meet the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; - + /// \brief Default traits class used by BellmanFordWizard. /// /// Default traits class used by BellmanFordWizard. /// \tparam GR The type of the digraph. /// \tparam LEN The type of the length map. template - class BellmanFordWizardBase + class BellmanFordWizardBase : public BellmanFordWizardDefaultTraits { typedef BellmanFordWizardDefaultTraits Base; @@ -957,26 +957,26 @@ public: /// Constructor. - + /// This constructor does not require parameters, it initiates /// all of the attributes to default values \c 0. BellmanFordWizardBase() : _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {} /// Constructor. - + /// This constructor requires two parameters, /// others are initiated to \c 0. /// \param gr The digraph the algorithm runs on. /// \param len The length map. - BellmanFordWizardBase(const GR& gr, - const LEN& len) : - _graph(reinterpret_cast(const_cast(&gr))), - _length(reinterpret_cast(const_cast(&len))), + BellmanFordWizardBase(const GR& gr, + const LEN& len) : + _graph(reinterpret_cast(const_cast(&gr))), + _length(reinterpret_cast(const_cast(&len))), _pred(0), _dist(0), _path(0), _di(0) {} }; - + /// \brief Auxiliary class for the function-type interface of the /// \ref BellmanFord "Bellman-Ford" algorithm. /// @@ -1001,7 +1001,7 @@ typedef typename Digraph::NodeIt NodeIt; typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt ArcIt; - + typedef typename TR::LengthMap LengthMap; typedef typename LengthMap::Value Value; typedef typename TR::PredMap PredMap; @@ -1018,7 +1018,7 @@ /// These parameters will be the default values for the traits class. /// \param gr The digraph the algorithm runs on. /// \param len The length map. - BellmanFordWizard(const Digraph& gr, const LengthMap& len) + BellmanFordWizard(const Digraph& gr, const LengthMap& len) : TR(gr, len) {} /// \brief Copy constructor @@ -1027,12 +1027,12 @@ ~BellmanFordWizard() {} /// \brief Runs the Bellman-Ford algorithm from the given source node. - /// + /// /// This method runs the Bellman-Ford algorithm from the given source /// node in order to compute the shortest path to each node. void run(Node s) { - BellmanFord - bf(*reinterpret_cast(Base::_graph), + BellmanFord + bf(*reinterpret_cast(Base::_graph), *reinterpret_cast(Base::_length)); if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred)); if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist)); @@ -1067,7 +1067,7 @@ static PredMap *createPredMap(const Digraph &) { return 0; }; SetPredMapBase(const TR &b) : TR(b) {} }; - + /// \brief \ref named-templ-param "Named parameter" for setting /// the predecessor map. /// @@ -1078,14 +1078,14 @@ Base::_pred=reinterpret_cast(const_cast(&t)); return BellmanFordWizard >(*this); } - + template struct SetDistMapBase : public Base { typedef T DistMap; static DistMap *createDistMap(const Digraph &) { return 0; }; SetDistMapBase(const TR &b) : TR(b) {} }; - + /// \brief \ref named-templ-param "Named parameter" for setting /// the distance map. /// @@ -1126,9 +1126,9 @@ Base::_di=reinterpret_cast(const_cast(&d)); return *this; } - + }; - + /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford" /// algorithm. /// @@ -1136,8 +1136,8 @@ /// Function type interface for the \ref BellmanFord "Bellman-Ford" /// algorithm. /// - /// This function also has several \ref named-templ-func-param - /// "named parameters", they are declared as the members of class + /// This function also has several \ref named-templ-func-param + /// "named parameters", they are declared as the members of class /// \ref BellmanFordWizard. /// The following examples show how to use these parameters. /// \code @@ -1154,7 +1154,7 @@ template BellmanFordWizard > bellmanFord(const GR& digraph, - const LEN& length) + const LEN& length) { return BellmanFordWizard >(digraph, length); } diff --git a/lemon/bfs.h b/lemon/bfs.h --- a/lemon/bfs.h +++ b/lemon/bfs.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -82,7 +82,8 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to + ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a \c ReachedMap. @@ -271,7 +272,8 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ReachedMap type. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to + ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. template struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > { typedef Bfs< Digraph, SetReachedMapTraits > Create; @@ -872,7 +874,8 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to + ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. @@ -1265,7 +1268,8 @@ /// \brief The type of the map that indicates which nodes are reached. /// /// The type of the map that indicates which nodes are reached. - /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// It must conform to + ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; /// \brief Instantiates a ReachedMap. diff --git a/lemon/binomial_heap.h b/lemon/binomial_heap.h --- a/lemon/binomial_heap.h +++ b/lemon/binomial_heap.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -258,7 +258,7 @@ int i=_iim[item]; int p=_data[i].parent; _data[i].prio=value; - + while( p!=-1 && _comp(value, _data[p].prio) ) { _data[i].name=_data[p].name; _data[i].prio=_data[p].prio; @@ -322,7 +322,7 @@ } private: - + // Find the minimum of the roots int findMin() { if( _head!=-1 ) { @@ -350,7 +350,7 @@ interleave(a); } if( _data[_head].right_neighbor==-1 ) return; - + int x=_head; int x_prev=-1, x_next=_data[x].right_neighbor; while( x_next!=-1 ) { @@ -384,7 +384,7 @@ int p=_head, q=a; int curr=_data.size(); _data.push_back(Store()); - + while( p!=-1 || q!=-1 ) { if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) { _data[curr].right_neighbor=p; @@ -397,7 +397,7 @@ q=_data[q].right_neighbor; } } - + _head=_data.back().right_neighbor; _data.pop_back(); } diff --git a/lemon/bits/array_map.h b/lemon/bits/array_map.h --- a/lemon/bits/array_map.h +++ b/lemon/bits/array_map.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -70,7 +70,7 @@ typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; private: - + // The MapBase of the Map which imlements the core regisitry function. typedef typename Notifier::ObserverBase Parent; diff --git a/lemon/bits/default_map.h b/lemon/bits/default_map.h --- a/lemon/bits/default_map.h +++ b/lemon/bits/default_map.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -157,7 +157,7 @@ public: typedef DefaultMap<_Graph, _Item, _Value> Map; - + typedef typename Parent::GraphType GraphType; typedef typename Parent::Value Value; diff --git a/lemon/bits/edge_set_extender.h b/lemon/bits/edge_set_extender.h --- a/lemon/bits/edge_set_extender.h +++ b/lemon/bits/edge_set_extender.h @@ -1,8 +1,8 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -63,11 +63,11 @@ Node oppositeNode(const Node &n, const Arc &e) const { if (n == Parent::source(e)) - return Parent::target(e); + return Parent::target(e); else if(n==Parent::target(e)) - return Parent::source(e); + return Parent::source(e); else - return INVALID; + return INVALID; } @@ -91,7 +91,7 @@ // Iterable extensions - class NodeIt : public Node { + class NodeIt : public Node { const Digraph* digraph; public: @@ -100,21 +100,21 @@ NodeIt(Invalid i) : Node(i) { } explicit NodeIt(const Digraph& _graph) : digraph(&_graph) { - _graph.first(static_cast(*this)); + _graph.first(static_cast(*this)); } - NodeIt(const Digraph& _graph, const Node& node) - : Node(node), digraph(&_graph) {} + NodeIt(const Digraph& _graph, const Node& node) + : Node(node), digraph(&_graph) {} - NodeIt& operator++() { - digraph->next(*this); - return *this; + NodeIt& operator++() { + digraph->next(*this); + return *this; } }; - class ArcIt : public Arc { + class ArcIt : public Arc { const Digraph* digraph; public: @@ -123,21 +123,21 @@ ArcIt(Invalid i) : Arc(i) { } explicit ArcIt(const Digraph& _graph) : digraph(&_graph) { - _graph.first(static_cast(*this)); + _graph.first(static_cast(*this)); } - ArcIt(const Digraph& _graph, const Arc& e) : - Arc(e), digraph(&_graph) { } + ArcIt(const Digraph& _graph, const Arc& e) : + Arc(e), digraph(&_graph) { } - ArcIt& operator++() { - digraph->next(*this); - return *this; + ArcIt& operator++() { + digraph->next(*this); + return *this; } }; - class OutArcIt : public Arc { + class OutArcIt : public Arc { const Digraph* digraph; public: @@ -145,23 +145,23 @@ OutArcIt(Invalid i) : Arc(i) { } - OutArcIt(const Digraph& _graph, const Node& node) - : digraph(&_graph) { - _graph.firstOut(*this, node); + OutArcIt(const Digraph& _graph, const Node& node) + : digraph(&_graph) { + _graph.firstOut(*this, node); } - OutArcIt(const Digraph& _graph, const Arc& arc) - : Arc(arc), digraph(&_graph) {} + OutArcIt(const Digraph& _graph, const Arc& arc) + : Arc(arc), digraph(&_graph) {} - OutArcIt& operator++() { - digraph->nextOut(*this); - return *this; + OutArcIt& operator++() { + digraph->nextOut(*this); + return *this; } }; - class InArcIt : public Arc { + class InArcIt : public Arc { const Digraph* digraph; public: @@ -169,17 +169,17 @@ InArcIt(Invalid i) : Arc(i) { } - InArcIt(const Digraph& _graph, const Node& node) - : digraph(&_graph) { - _graph.firstIn(*this, node); + InArcIt(const Digraph& _graph, const Node& node) + : digraph(&_graph) { + _graph.firstIn(*this, node); } - InArcIt(const Digraph& _graph, const Arc& arc) : - Arc(arc), digraph(&_graph) {} + InArcIt(const Digraph& _graph, const Arc& arc) : + Arc(arc), digraph(&_graph) {} - InArcIt& operator++() { - digraph->nextIn(*this); - return *this; + InArcIt& operator++() { + digraph->nextIn(*this); + return *this; } }; @@ -215,26 +215,26 @@ using Parent::first; // Mappable extension - + template - class ArcMap + class ArcMap : public MapExtender > { typedef MapExtender > Parent; public: - explicit ArcMap(const Digraph& _g) - : Parent(_g) {} - ArcMap(const Digraph& _g, const _Value& _v) - : Parent(_g, _v) {} + explicit ArcMap(const Digraph& _g) + : Parent(_g) {} + ArcMap(const Digraph& _g, const _Value& _v) + : Parent(_g, _v) {} ArcMap& operator=(const ArcMap& cmap) { - return operator=(cmap); + return operator=(cmap); } template ArcMap& operator=(const CMap& cmap) { Parent::operator=(cmap); - return *this; + return *this; } }; @@ -247,7 +247,7 @@ notifier(Arc()).add(arc); return arc; } - + void clear() { notifier(Arc()).clear(); Parent::clear(); @@ -310,11 +310,11 @@ Node oppositeNode(const Node &n, const Edge &e) const { if( n == Parent::u(e)) - return Parent::v(e); + return Parent::v(e); else if( n == Parent::v(e)) - return Parent::u(e); + return Parent::u(e); else - return INVALID; + return INVALID; } Arc oppositeArc(const Arc &e) const { @@ -338,7 +338,7 @@ public: using Parent::notifier; - + ArcNotifier& notifier(Arc) const { return arc_notifier; } @@ -348,7 +348,7 @@ } - class NodeIt : public Node { + class NodeIt : public Node { const Graph* graph; public: @@ -357,21 +357,21 @@ NodeIt(Invalid i) : Node(i) { } explicit NodeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(static_cast(*this)); + _graph.first(static_cast(*this)); } - NodeIt(const Graph& _graph, const Node& node) - : Node(node), graph(&_graph) {} + NodeIt(const Graph& _graph, const Node& node) + : Node(node), graph(&_graph) {} - NodeIt& operator++() { - graph->next(*this); - return *this; + NodeIt& operator++() { + graph->next(*this); + return *this; } }; - class ArcIt : public Arc { + class ArcIt : public Arc { const Graph* graph; public: @@ -380,21 +380,21 @@ ArcIt(Invalid i) : Arc(i) { } explicit ArcIt(const Graph& _graph) : graph(&_graph) { - _graph.first(static_cast(*this)); + _graph.first(static_cast(*this)); } - ArcIt(const Graph& _graph, const Arc& e) : - Arc(e), graph(&_graph) { } + ArcIt(const Graph& _graph, const Arc& e) : + Arc(e), graph(&_graph) { } - ArcIt& operator++() { - graph->next(*this); - return *this; + ArcIt& operator++() { + graph->next(*this); + return *this; } }; - class OutArcIt : public Arc { + class OutArcIt : public Arc { const Graph* graph; public: @@ -402,23 +402,23 @@ OutArcIt(Invalid i) : Arc(i) { } - OutArcIt(const Graph& _graph, const Node& node) - : graph(&_graph) { - _graph.firstOut(*this, node); + OutArcIt(const Graph& _graph, const Node& node) + : graph(&_graph) { + _graph.firstOut(*this, node); } - OutArcIt(const Graph& _graph, const Arc& arc) - : Arc(arc), graph(&_graph) {} + OutArcIt(const Graph& _graph, const Arc& arc) + : Arc(arc), graph(&_graph) {} - OutArcIt& operator++() { - graph->nextOut(*this); - return *this; + OutArcIt& operator++() { + graph->nextOut(*this); + return *this; } }; - class InArcIt : public Arc { + class InArcIt : public Arc { const Graph* graph; public: @@ -426,23 +426,23 @@ InArcIt(Invalid i) : Arc(i) { } - InArcIt(const Graph& _graph, const Node& node) - : graph(&_graph) { - _graph.firstIn(*this, node); + InArcIt(const Graph& _graph, const Node& node) + : graph(&_graph) { + _graph.firstIn(*this, node); } - InArcIt(const Graph& _graph, const Arc& arc) : - Arc(arc), graph(&_graph) {} + InArcIt(const Graph& _graph, const Arc& arc) : + Arc(arc), graph(&_graph) {} - InArcIt& operator++() { - graph->nextIn(*this); - return *this; + InArcIt& operator++() { + graph->nextIn(*this); + return *this; } }; - class EdgeIt : public Parent::Edge { + class EdgeIt : public Parent::Edge { const Graph* graph; public: @@ -451,15 +451,15 @@ EdgeIt(Invalid i) : Edge(i) { } explicit EdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(static_cast(*this)); + _graph.first(static_cast(*this)); } - EdgeIt(const Graph& _graph, const Edge& e) : - Edge(e), graph(&_graph) { } + EdgeIt(const Graph& _graph, const Edge& e) : + Edge(e), graph(&_graph) { } - EdgeIt& operator++() { - graph->next(*this); - return *this; + EdgeIt& operator++() { + graph->next(*this); + return *this; } }; @@ -475,17 +475,17 @@ IncEdgeIt(Invalid i) : Edge(i), direction(false) { } IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { - _graph.firstInc(*this, direction, n); + _graph.firstInc(*this, direction, n); } IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n) - : graph(&_graph), Edge(ue) { - direction = (_graph.source(ue) == n); + : graph(&_graph), Edge(ue) { + direction = (_graph.source(ue) == n); } IncEdgeIt& operator++() { - graph->nextInc(*this, direction); - return *this; + graph->nextInc(*this, direction); + return *this; } }; @@ -532,49 +532,49 @@ template - class ArcMap + class ArcMap : public MapExtender > { typedef MapExtender > Parent; public: - explicit ArcMap(const Graph& _g) - : Parent(_g) {} - ArcMap(const Graph& _g, const _Value& _v) - : Parent(_g, _v) {} + explicit ArcMap(const Graph& _g) + : Parent(_g) {} + ArcMap(const Graph& _g, const _Value& _v) + : Parent(_g, _v) {} ArcMap& operator=(const ArcMap& cmap) { - return operator=(cmap); + return operator=(cmap); } template ArcMap& operator=(const CMap& cmap) { Parent::operator=(cmap); - return *this; + return *this; } }; template - class EdgeMap + class EdgeMap : public MapExtender > { typedef MapExtender > Parent; public: - explicit EdgeMap(const Graph& _g) - : Parent(_g) {} + explicit EdgeMap(const Graph& _g) + : Parent(_g) {} - EdgeMap(const Graph& _g, const _Value& _v) - : Parent(_g, _v) {} + EdgeMap(const Graph& _g, const _Value& _v) + : Parent(_g, _v) {} EdgeMap& operator=(const EdgeMap& cmap) { - return operator=(cmap); + return operator=(cmap); } template EdgeMap& operator=(const CMap& cmap) { Parent::operator=(cmap); - return *this; + return *this; } }; @@ -591,7 +591,7 @@ notifier(Arc()).add(arcs); return edge; } - + void clear() { notifier(Arc()).clear(); notifier(Edge()).clear(); @@ -617,7 +617,7 @@ edge_notifier.clear(); arc_notifier.clear(); } - + }; } diff --git a/lemon/bits/solver_bits.h b/lemon/bits/solver_bits.h --- a/lemon/bits/solver_bits.h +++ b/lemon/bits/solver_bits.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/lemon/bits/windows.cc b/lemon/bits/windows.cc --- a/lemon/bits/windows.cc +++ b/lemon/bits/windows.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -96,7 +96,7 @@ SYSTEMTIME time; GetSystemTime(&time); char buf1[11], buf2[9], buf3[5]; - if (GetDateFormat(MY_LOCALE, 0, &time, + if (GetDateFormat(MY_LOCALE, 0, &time, ("ddd MMM dd"), buf1, 11) && GetTimeFormat(MY_LOCALE, 0, &time, ("HH':'mm':'ss"), buf2, 9) && diff --git a/lemon/bucket_heap.h b/lemon/bucket_heap.h --- a/lemon/bucket_heap.h +++ b/lemon/bucket_heap.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -384,7 +384,7 @@ /// key increasing and decreasing. /// /// Note that this implementation does not conform to the - /// \ref concepts::Heap "heap concept" due to the lack of some + /// \ref concepts::Heap "heap concept" due to the lack of some /// functionality. /// /// \tparam IM A read-writable item map with \c int values, used diff --git a/lemon/capacity_scaling.h b/lemon/capacity_scaling.h --- a/lemon/capacity_scaling.h +++ b/lemon/capacity_scaling.h @@ -1,8 +1,8 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -133,7 +133,7 @@ /// these cases. UNBOUNDED }; - + private: TEMPLATE_DIGRAPH_TYPEDEFS(GR); @@ -184,7 +184,7 @@ IntVector _pred; public: - + /// \brief Constant for infinite upper bounds (capacities). /// /// Constant for infinite upper bounds (capacities). @@ -211,10 +211,10 @@ const ValueVector &_excess; CostVector &_pi; IntVector &_pred; - + IntVector _proc_nodes; CostVector _dist; - + public: ResidualDijkstra(CapacityScaling& cs) : @@ -439,7 +439,7 @@ _supply[_node_id[t]] = -k; return *this; } - + /// @} /// \name Execution control @@ -575,7 +575,7 @@ _upper.resize(_res_arc_num); _cost.resize(_res_arc_num); _supply.resize(_node_num); - + _res_cap.resize(_res_arc_num); _pi.resize(_node_num); _excess.resize(_node_num); @@ -619,7 +619,7 @@ _reverse[fi] = bi; _reverse[bi] = fi; } - + // Reset parameters resetParams(); return *this; @@ -728,7 +728,7 @@ _sum_supply += _supply[i]; } if (_sum_supply > 0) return INFEASIBLE; - + // Initialize vectors for (int i = 0; i != _root; ++i) { _pi[i] = 0; @@ -776,7 +776,7 @@ } } } - + // Handle GEQ supply type if (_sum_supply < 0) { _pi[_root] = 0; @@ -844,9 +844,9 @@ if (_sum_supply < 0 || pr > 0) { for (int i = 0; i != _node_num; ++i) { _pi[i] -= pr; - } + } } - + return pt; } diff --git a/lemon/cbc.h b/lemon/cbc.h --- a/lemon/cbc.h +++ b/lemon/cbc.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -121,7 +121,7 @@ int _message_level; - + }; diff --git a/lemon/circulation.h b/lemon/circulation.h --- a/lemon/circulation.h +++ b/lemon/circulation.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -59,8 +59,8 @@ /// \brief The type of supply map. /// - /// The type of the map that stores the signed supply values of the - /// nodes. + /// The type of the map that stores the signed supply values of the + /// nodes. /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. typedef SM SupplyMap; @@ -141,7 +141,7 @@ \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq sup(u) \quad \forall u\in V, \f] \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f] - + The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or negative in order to have a feasible solution (since the sum of the expressions on the left-hand side of the inequalities is zero). @@ -151,7 +151,7 @@ If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand constraints have to be satisfied with equality, i.e. all demands have to be satisfied and all supplies have to be used. - + If you need the opposite inequalities in the supply/demand constraints (i.e. the total demand is less than the total supply and all the demands have to be satisfied while there could be supplies that are not used), @@ -337,7 +337,7 @@ /// /// \param graph The digraph the algorithm runs on. /// \param lower The lower bounds for the flow values on the arcs. - /// \param upper The upper bounds (capacities) for the flow values + /// \param upper The upper bounds (capacities) for the flow values /// on the arcs. /// \param supply The signed supply values of the nodes. Circulation(const Digraph &graph, const LowerMap &lower, diff --git a/lemon/clp.cc b/lemon/clp.cc --- a/lemon/clp.cc +++ b/lemon/clp.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/lemon/clp.h b/lemon/clp.h --- a/lemon/clp.h +++ b/lemon/clp.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -138,7 +138,7 @@ virtual void _clear(); virtual void _messageLevel(MessageLevel); - + public: ///Solves LP with primal simplex method. diff --git a/lemon/concepts/digraph.h b/lemon/concepts/digraph.h --- a/lemon/concepts/digraph.h +++ b/lemon/concepts/digraph.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -434,7 +434,7 @@ private: ///Copy constructor - NodeMap(const NodeMap& nm) : + NodeMap(const NodeMap& nm) : ReferenceMap(nm) { } ///Assignment operator template diff --git a/lemon/concepts/graph.h b/lemon/concepts/graph.h --- a/lemon/concepts/graph.h +++ b/lemon/concepts/graph.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -43,7 +43,7 @@ /// undirected graphs should compile with this class, but it will not /// run properly, of course. /// An actual graph implementation like \ref ListGraph or - /// \ref SmartGraph may have additional functionality. + /// \ref SmartGraph may have additional functionality. /// /// The undirected graphs also fulfill the concept of \ref Digraph /// "directed graphs", since each edge can also be regarded as two @@ -85,7 +85,7 @@ /// \brief Undirected graphs should be tagged with \c UndirectedTag. /// /// Undirected graphs should be tagged with \c UndirectedTag. - /// + /// /// This tag helps the \c enable_if technics to make compile time /// specializations for undirected graphs. typedef True UndirectedTag; @@ -360,7 +360,7 @@ bool operator<(Arc) const { return false; } /// Converison to \c Edge - + /// Converison to \c Edge. /// operator Edge() const { return Edge(); } diff --git a/lemon/concepts/graph_components.h b/lemon/concepts/graph_components.h --- a/lemon/concepts/graph_components.h +++ b/lemon/concepts/graph_components.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -38,7 +38,7 @@ /// /// \note This class is a template class so that we can use it to /// create graph skeleton classes. The reason for this is that \c Node - /// and \c Arc (or \c Edge) types should \e not derive from the same + /// and \c Arc (or \c Edge) types should \e not derive from the same /// base class. For \c Node you should instantiate it with character /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'. #ifndef DOXYGEN @@ -89,7 +89,7 @@ /// \brief Ordering operator. /// /// This operator defines an ordering of the items. - /// It makes possible to use graph item types as key types in + /// It makes possible to use graph item types as key types in /// associative containers (e.g. \c std::map). /// /// \note This operator only has to define some strict ordering of @@ -122,7 +122,7 @@ /// /// This class describes the base interface of directed graph types. /// All digraph %concepts have to conform to this class. - /// It just provides types for nodes and arcs and functions + /// It just provides types for nodes and arcs and functions /// to get the source and the target nodes of arcs. class BaseDigraphComponent { public: @@ -426,7 +426,7 @@ /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types. /// - /// This class describes the concept of \c NodeIt, \c ArcIt and + /// This class describes the concept of \c NodeIt, \c ArcIt and /// \c EdgeIt subtypes of digraph and graph types. template class GraphItemIt : public Item { @@ -466,7 +466,7 @@ /// This operator increments the iterator, i.e. assigns it to the /// next item. GraphItemIt& operator++() { return *this; } - + /// \brief Equality operator /// /// Equality operator. @@ -501,15 +501,15 @@ }; }; - /// \brief Concept class for \c InArcIt, \c OutArcIt and + /// \brief Concept class for \c InArcIt, \c OutArcIt and /// \c IncEdgeIt types. /// - /// This class describes the concept of \c InArcIt, \c OutArcIt + /// This class describes the concept of \c InArcIt, \c OutArcIt /// and \c IncEdgeIt subtypes of digraph and graph types. /// /// \note Since these iterator classes do not inherit from the same /// base class, there is an additional template parameter (selector) - /// \c sel. For \c InArcIt you should instantiate it with character + /// \c sel. For \c InArcIt you should instantiate it with character /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'. template @@ -1045,7 +1045,7 @@ , _Map>(); _Map m1(g); _Map m2(g,t); - + // Copy constructor // _Map m3(m); @@ -1068,7 +1068,7 @@ /// \brief Skeleton class for mappable directed graphs. /// /// This class describes the interface of mappable directed graphs. - /// It extends \ref BaseDigraphComponent with the standard digraph + /// It extends \ref BaseDigraphComponent with the standard digraph /// map classes, namely \c NodeMap and \c ArcMap. /// This concept is part of the Digraph concept. template @@ -1205,7 +1205,7 @@ /// \brief Skeleton class for mappable undirected graphs. /// /// This class describes the interface of mappable undirected graphs. - /// It extends \ref MappableDigraphComponent with the standard graph + /// It extends \ref MappableDigraphComponent with the standard graph /// map class for edges (\c EdgeMap). /// This concept is part of the Graph concept. template @@ -1290,7 +1290,7 @@ /// \brief Skeleton class for extendable directed graphs. /// /// This class describes the interface of extendable directed graphs. - /// It extends \ref BaseDigraphComponent with functions for adding + /// It extends \ref BaseDigraphComponent with functions for adding /// nodes and arcs to the digraph. /// This concept requires \ref AlterableDigraphComponent. template @@ -1334,7 +1334,7 @@ /// \brief Skeleton class for extendable undirected graphs. /// /// This class describes the interface of extendable undirected graphs. - /// It extends \ref BaseGraphComponent with functions for adding + /// It extends \ref BaseGraphComponent with functions for adding /// nodes and edges to the graph. /// This concept requires \ref AlterableGraphComponent. template @@ -1378,7 +1378,7 @@ /// \brief Skeleton class for erasable directed graphs. /// /// This class describes the interface of erasable directed graphs. - /// It extends \ref BaseDigraphComponent with functions for removing + /// It extends \ref BaseDigraphComponent with functions for removing /// nodes and arcs from the digraph. /// This concept requires \ref AlterableDigraphComponent. template @@ -1391,7 +1391,7 @@ /// \brief Erase a node from the digraph. /// - /// This function erases the given node from the digraph and all arcs + /// This function erases the given node from the digraph and all arcs /// connected to the node. void erase(const Node&) {} @@ -1417,7 +1417,7 @@ /// \brief Skeleton class for erasable undirected graphs. /// /// This class describes the interface of erasable undirected graphs. - /// It extends \ref BaseGraphComponent with functions for removing + /// It extends \ref BaseGraphComponent with functions for removing /// nodes and edges from the graph. /// This concept requires \ref AlterableGraphComponent. template diff --git a/lemon/concepts/heap.h b/lemon/concepts/heap.h --- a/lemon/concepts/heap.h +++ b/lemon/concepts/heap.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -92,7 +92,7 @@ explicit Heap(ItemIntMap &map) {} #else explicit Heap(ItemIntMap&) {} -#endif +#endif /// \brief Constructor. /// @@ -106,7 +106,7 @@ explicit Heap(ItemIntMap &map, const CMP &comp) {} #else explicit Heap(ItemIntMap&, const CMP&) {} -#endif +#endif /// \brief The number of items stored in the heap. /// @@ -138,7 +138,7 @@ void push(const Item &i, const Prio &p) {} #else void push(const Item&, const Prio&) {} -#endif +#endif /// \brief Return the item having minimum priority. /// @@ -168,7 +168,7 @@ void erase(const Item &i) {} #else void erase(const Item&) {} -#endif +#endif /// \brief The priority of the given item. /// @@ -179,7 +179,7 @@ Prio operator[](const Item &i) const {} #else Prio operator[](const Item&) const { return Prio(); } -#endif +#endif /// \brief Set the priority of an item or insert it, if it is /// not stored in the heap. @@ -194,7 +194,7 @@ void set(const Item &i, const Prio &p) {} #else void set(const Item&, const Prio&) {} -#endif +#endif /// \brief Decrease the priority of an item to the given value. /// @@ -206,7 +206,7 @@ void decrease(const Item &i, const Prio &p) {} #else void decrease(const Item&, const Prio&) {} -#endif +#endif /// \brief Increase the priority of an item to the given value. /// @@ -218,7 +218,7 @@ void increase(const Item &i, const Prio &p) {} #else void increase(const Item&, const Prio&) {} -#endif +#endif /// \brief Return the state of an item. /// @@ -232,7 +232,7 @@ State state(const Item &i) const {} #else State state(const Item&) const { return PRE_HEAP; } -#endif +#endif /// \brief Set the state of an item in the heap. /// @@ -245,7 +245,7 @@ void state(const Item& i, State st) {} #else void state(const Item&, State) {} -#endif +#endif template diff --git a/lemon/connectivity.h b/lemon/connectivity.h --- a/lemon/connectivity.h +++ b/lemon/connectivity.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -258,7 +258,7 @@ /// /// \return \c true if the digraph is strongly connected. /// \note By definition, the empty digraph is strongly connected. - /// + /// /// \see countStronglyConnectedComponents(), stronglyConnectedComponents() /// \see connected() template @@ -310,7 +310,7 @@ /// \ingroup graph_properties /// - /// \brief Count the number of strongly connected components of a + /// \brief Count the number of strongly connected components of a /// directed graph /// /// This function counts the number of strongly connected components of @@ -744,7 +744,7 @@ /// /// \brief Check whether an undirected graph is bi-node-connected. /// - /// This function checks whether the given undirected graph is + /// This function checks whether the given undirected graph is /// bi-node-connected, i.e. any two edges are on same circle. /// /// \return \c true if the graph bi-node-connected. @@ -758,7 +758,7 @@ /// \ingroup graph_properties /// - /// \brief Count the number of bi-node-connected components of an + /// \brief Count the number of bi-node-connected components of an /// undirected graph. /// /// This function counts the number of bi-node-connected components of @@ -812,7 +812,7 @@ /// \param graph The undirected graph. /// \retval compMap A writable edge map. The values will be set from 0 /// to the number of the bi-node-connected components minus one. Each - /// value of the map will be set exactly once, and the values of a + /// value of the map will be set exactly once, and the values of a /// certain component will be set continuously. /// \return The number of bi-node-connected components. /// @@ -858,7 +858,7 @@ /// the components. /// /// \param graph The undirected graph. - /// \retval cutMap A writable node map. The values will be set to + /// \retval cutMap A writable node map. The values will be set to /// \c true for the nodes that separate two or more components /// (exactly once for each cut node), and will not be changed for /// other nodes. @@ -1085,7 +1085,7 @@ /// /// \brief Check whether an undirected graph is bi-edge-connected. /// - /// This function checks whether the given undirected graph is + /// This function checks whether the given undirected graph is /// bi-edge-connected, i.e. any two nodes are connected with at least /// two edge-disjoint paths. /// @@ -1192,7 +1192,7 @@ /// \brief Find the bi-edge-connected cut edges in an undirected graph. /// /// This function finds the bi-edge-connected cut edges in the given - /// undirected graph. + /// undirected graph. /// /// The bi-edge-connected components are the classes of an equivalence /// relation on the nodes of an undirected graph. Two nodes are in the @@ -1349,7 +1349,7 @@ /// /// \param digraph The digraph. /// \retval order A readable and writable node map. The values will be - /// set from 0 to the number of the nodes in the digraph minus one. + /// set from 0 to the number of the nodes in the digraph minus one. /// Each value of the map will be set exactly once, and the values will /// be set descending order. /// \return \c false if the digraph is not DAG. diff --git a/lemon/core.h b/lemon/core.h --- a/lemon/core.h +++ b/lemon/core.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -1239,7 +1239,8 @@ protected: - class AutoNodeMap : public ItemSetTraits::template Map::Type { + class AutoNodeMap : public ItemSetTraits::template Map::Type + { typedef typename ItemSetTraits::template Map::Type Parent; public: @@ -1278,7 +1279,7 @@ } }; - protected: + protected: const Digraph &_g; AutoNodeMap _head; diff --git a/lemon/cost_scaling.h b/lemon/cost_scaling.h --- a/lemon/cost_scaling.h +++ b/lemon/cost_scaling.h @@ -1,8 +1,8 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -92,7 +92,7 @@ /// \ref CostScaling implements a cost scaling algorithm that performs /// push/augment and relabel operations for finding a \ref min_cost_flow /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation, - /// \ref goldberg97efficient, \ref bunnagel98efficient. + /// \ref goldberg97efficient, \ref bunnagel98efficient. /// It is a highly efficient primal-dual solution method, which /// can be viewed as the generalization of the \ref Preflow /// "preflow push-relabel" algorithm for the maximum flow problem. @@ -189,7 +189,7 @@ /// Augment operations are used, i.e. flow is moved on admissible /// paths from a node with excess to a node with deficit. AUGMENT, - /// Partial augment operations are used, i.e. flow is moved on + /// Partial augment operations are used, i.e. flow is moved on /// admissible paths started from a node with excess, but the /// lengths of these paths are limited. This method can be viewed /// as a combined version of the previous two operations. @@ -208,15 +208,15 @@ // Note: vector is used instead of vector for efficiency reasons private: - + template class StaticVectorMap { public: typedef KT Key; typedef VT Value; - + StaticVectorMap(std::vector& v) : _v(v) {} - + const Value& operator[](const Key& key) const { return _v[StaticDigraph::id(key)]; } @@ -224,7 +224,7 @@ Value& operator[](const Key& key) { return _v[StaticDigraph::id(key)]; } - + void set(const Key& key, const Value& val) { _v[StaticDigraph::id(key)] = val; } @@ -283,7 +283,7 @@ IntVector _bucket_prev; IntVector _rank; int _max_rank; - + // Data for a StaticDigraph structure typedef std::pair IntPair; StaticDigraph _sgr; @@ -291,9 +291,9 @@ std::vector _cost_vec; LargeCostArcMap _cost_map; LargeCostNodeMap _pi_map; - + public: - + /// \brief Constant for infinite upper bounds (capacities). /// /// Constant for infinite upper bounds (capacities). @@ -348,7 +348,7 @@ "The flow type of CostScaling must be signed"); LEMON_ASSERT(std::numeric_limits::is_signed, "The cost type of CostScaling must be signed"); - + // Reset data structures reset(); } @@ -464,7 +464,7 @@ _supply[_node_id[t]] = -k; return *this; } - + /// @} /// \name Execution control @@ -566,7 +566,7 @@ _upper[j] = INF; _scost[j] = 0; _scost[_reverse[j]] = 0; - } + } _have_lower = false; return *this; } @@ -601,7 +601,7 @@ _upper.resize(_res_arc_num); _scost.resize(_res_arc_num); _supply.resize(_res_node_num); - + _res_cap.resize(_res_arc_num); _cost.resize(_res_arc_num); _pi.resize(_res_node_num); @@ -649,7 +649,7 @@ _reverse[fi] = bi; _reverse[bi] = fi; } - + // Reset parameters resetParams(); return *this; @@ -758,14 +758,14 @@ _sum_supply += _supply[i]; } if (_sum_supply > 0) return INFEASIBLE; - + // Initialize vectors for (int i = 0; i != _res_node_num; ++i) { _pi[i] = 0; _excess[i] = _supply[i]; } - + // Remove infinite upper bounds and check negative arcs const Value MAX = std::numeric_limits::max(); int last_out; @@ -885,7 +885,7 @@ _cost[ra] = 0; } } - + return OPTIMAL; } @@ -894,13 +894,13 @@ // Maximum path length for partial augment const int MAX_PATH_LENGTH = 4; - // Initialize data structures for buckets + // Initialize data structures for buckets _max_rank = _alpha * _res_node_num; _buckets.resize(_max_rank); _bucket_next.resize(_res_node_num + 1); _bucket_prev.resize(_res_node_num + 1); _rank.resize(_res_node_num + 1); - + // Execute the algorithm switch (method) { case PUSH: @@ -939,7 +939,7 @@ } } } - + // Initialize a cost scaling phase void initPhase() { // Saturate arcs not satisfying the optimality condition @@ -957,7 +957,7 @@ } } } - + // Find active nodes (i.e. nodes with positive excess) for (int u = 0; u != _res_node_num; ++u) { if (_excess[u] > 0) _active_nodes.push_back(u); @@ -968,7 +968,7 @@ _next_out[u] = _first_out[u]; } } - + // Early termination heuristic bool earlyTermination() { const double EARLY_TERM_FACTOR = 3.0; @@ -998,7 +998,7 @@ // Global potential update heuristic void globalUpdate() { int bucket_end = _root + 1; - + // Initialize buckets for (int r = 0; r != _max_rank; ++r) { _buckets[r] = bucket_end; @@ -1024,7 +1024,7 @@ // Remove the first node from the current bucket int u = _buckets[r]; _buckets[r] = _bucket_next[u]; - + // Search the incomming arcs of u LargeCost pi_u = _pi[u]; int last_out = _first_out[u+1]; @@ -1039,12 +1039,12 @@ int new_rank_v = old_rank_v; if (nrc < LargeCost(_max_rank)) new_rank_v = r + 1 + int(nrc); - + // Change the rank of v if (new_rank_v < old_rank_v) { _rank[v] = new_rank_v; _next_out[v] = _first_out[v]; - + // Remove v from its old bucket if (old_rank_v < _max_rank) { if (_buckets[old_rank_v] == v) { @@ -1054,7 +1054,7 @@ _bucket_prev[_bucket_next[v]] = _bucket_prev[v]; } } - + // Insert v to its new bucket _bucket_next[v] = _buckets[new_rank_v]; _bucket_prev[_buckets[new_rank_v]] = v; @@ -1072,7 +1072,7 @@ } if (total_excess <= 0) break; } - + // Relabel nodes for (int u = 0; u != _res_node_num; ++u) { int k = std::min(_rank[u], r); @@ -1092,9 +1092,9 @@ const int global_update_freq = int(GLOBAL_UPDATE_FACTOR * (_res_node_num + _sup_node_num * _sup_node_num)); int next_update_limit = global_update_freq; - + int relabel_cnt = 0; - + // Perform cost scaling phases std::vector path; for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? @@ -1104,10 +1104,10 @@ if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) { if (earlyTermination()) break; } - + // Initialize current phase initPhase(); - + // Perform partial augment and relabel operations while (true) { // Select an active node (FIFO selection) @@ -1196,7 +1196,7 @@ int next_update_limit = global_update_freq; int relabel_cnt = 0; - + // Perform cost scaling phases BoolVector hyper(_res_node_num, false); LargeCostVector hyper_cost(_res_node_num); @@ -1207,7 +1207,7 @@ if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) { if (earlyTermination()) break; } - + // Initialize current phase initPhase(); @@ -1222,7 +1222,7 @@ n = _active_nodes.front(); last_out = _first_out[n+1]; pi_n = _pi[n]; - + // Perform push operations if there are admissible arcs if (_excess[n] > 0) { for (a = _next_out[n]; a != last_out; ++a) { @@ -1236,7 +1236,7 @@ int last_out_t = _first_out[t+1]; LargeCost pi_t = _pi[t]; for (int ta = _next_out[t]; ta != last_out_t; ++ta) { - if (_res_cap[ta] > 0 && + if (_res_cap[ta] > 0 && _cost[ta] + pi_t - _pi[_target[ta]] < 0) ahead += _res_cap[ta]; if (ahead >= delta) break; @@ -1287,7 +1287,7 @@ hyper[n] = false; ++relabel_cnt; } - + // Remove nodes that are not active nor hyper remove_nodes: while ( _active_nodes.size() > 0 && @@ -1295,7 +1295,7 @@ !hyper[_active_nodes.front()] ) { _active_nodes.pop_front(); } - + // Global update heuristic if (relabel_cnt >= next_update_limit) { globalUpdate(); diff --git a/lemon/cplex.cc b/lemon/cplex.cc --- a/lemon/cplex.cc +++ b/lemon/cplex.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -111,7 +111,7 @@ return i; } - int CplexBase::_addRow(Value lb, ExprIterator b, + int CplexBase::_addRow(Value lb, ExprIterator b, ExprIterator e, Value ub) { int i = CPXgetnumrows(cplexEnv(), _prob); if (lb == -INF) { @@ -489,7 +489,7 @@ } void CplexBase::_applyMessageLevel() { - CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, + CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, _message_enabled ? CPX_ON : CPX_OFF); } diff --git a/lemon/cycle_canceling.h b/lemon/cycle_canceling.h --- a/lemon/cycle_canceling.h +++ b/lemon/cycle_canceling.h @@ -1,8 +1,8 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -142,7 +142,7 @@ private: TEMPLATE_DIGRAPH_TYPEDEFS(GR); - + typedef std::vector IntVector; typedef std::vector DoubleVector; typedef std::vector ValueVector; @@ -151,15 +151,15 @@ // Note: vector is used instead of vector for efficiency reasons private: - + template class StaticVectorMap { public: typedef KT Key; typedef VT Value; - + StaticVectorMap(std::vector& v) : _v(v) {} - + const Value& operator[](const Key& key) const { return _v[StaticDigraph::id(key)]; } @@ -167,7 +167,7 @@ Value& operator[](const Key& key) { return _v[StaticDigraph::id(key)]; } - + void set(const Key& key, const Value& val) { _v[StaticDigraph::id(key)] = val; } @@ -221,9 +221,9 @@ IntVector _id_vec; CostArcMap _cost_map; CostNodeMap _pi_map; - + public: - + /// \brief Constant for infinite upper bounds (capacities). /// /// Constant for infinite upper bounds (capacities). @@ -366,7 +366,7 @@ _supply[_node_id[t]] = -k; return *this; } - + /// @} /// \name Execution control @@ -466,7 +466,7 @@ _upper[j] = INF; _cost[j] = 0; _cost[_reverse[j]] = 0; - } + } _have_lower = false; return *this; } @@ -508,7 +508,7 @@ _upper.resize(_res_arc_num); _cost.resize(_res_arc_num); _supply.resize(_res_node_num); - + _res_cap.resize(_res_arc_num); _pi.resize(_res_node_num); @@ -554,7 +554,7 @@ _reverse[fi] = bi; _reverse[bi] = fi; } - + // Reset parameters resetParams(); return *this; @@ -663,14 +663,14 @@ _sum_supply += _supply[i]; } if (_sum_supply > 0) return INFEASIBLE; - + // Initialize vectors for (int i = 0; i != _res_node_num; ++i) { _pi[i] = 0; } ValueVector excess(_supply); - + // Remove infinite upper bounds and check negative arcs const Value MAX = std::numeric_limits::max(); int last_out; @@ -770,10 +770,10 @@ _cost[ra] = 0; } } - + return OPTIMAL; } - + // Build a StaticDigraph structure containing the current // residual network void buildResidualNetwork() { @@ -829,14 +829,14 @@ // Constants for computing the iteration limits const int BF_FIRST_LIMIT = 2; const double BF_LIMIT_FACTOR = 1.5; - + typedef StaticVectorMap FilterMap; typedef FilterArcs ResDigraph; typedef StaticVectorMap PredMap; typedef typename BellmanFord ::template SetDistMap ::template SetPredMap::Create BF; - + // Build the residual network _arc_vec.clear(); _cost_vec.clear(); @@ -926,7 +926,7 @@ typedef typename SPath::ArcIt SPathArcIt; typedef typename HowardMmc ::template SetPath::Create MMC; - + SPath cycle; MMC mmc(_sgr, _cost_map); mmc.cycle(cycle); @@ -949,7 +949,7 @@ _res_cap[_reverse[j]] += delta; } - // Rebuild the residual network + // Rebuild the residual network buildResidualNetwork(); } } @@ -1143,7 +1143,7 @@ epsilon = -mmc.cycleMean(); Cost cycle_cost = mmc.cycleCost(); int cycle_size = mmc.cycleSize(); - + // Compute feasible potentials for the current epsilon for (int i = 0; i != int(_cost_vec.size()); ++i) { _cost_vec[i] = cycle_size * _cost_vec[i] - cycle_cost; @@ -1155,7 +1155,7 @@ for (int u = 0; u != _res_node_num; ++u) { pi[u] = static_cast(_pi[u]) / cycle_size; } - + iter = limit; } } diff --git a/lemon/dfs.h b/lemon/dfs.h --- a/lemon/dfs.h +++ b/lemon/dfs.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -82,7 +82,8 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to + ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a \c ReachedMap. @@ -270,7 +271,8 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ReachedMap type. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to + ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. template struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits > { typedef Dfs< Digraph, SetReachedMapTraits > Create; @@ -802,7 +804,8 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to + ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. @@ -1207,7 +1210,8 @@ /// \brief The type of the map that indicates which nodes are reached. /// /// The type of the map that indicates which nodes are reached. - /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// It must conform to the + /// \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; /// \brief Instantiates a ReachedMap. diff --git a/lemon/dijkstra.h b/lemon/dijkstra.h --- a/lemon/dijkstra.h +++ b/lemon/dijkstra.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/lemon/dimacs.h b/lemon/dimacs.h --- a/lemon/dimacs.h +++ b/lemon/dimacs.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -61,7 +61,7 @@ ///Discover the type of a DIMACS file ///This function starts seeking the beginning of the given file for the - ///problem type and size info. + ///problem type and size info. ///The found data is returned in a special struct that can be evaluated ///and passed to the appropriate reader function. DimacsDescriptor dimacsType(std::istream& is) @@ -212,7 +212,7 @@ infty = std::numeric_limits::has_infinity ? std::numeric_limits::infinity() : std::numeric_limits::max(); - + while (is >> c) { switch (c) { case 'c': // comment line @@ -237,7 +237,7 @@ getline(is, str); e = g.addArc(nodes[i], nodes[j]); capacity.set(e, _cap); - } + } else if (desc.type==DimacsDescriptor::MAX) { is >> i >> j >> _cap; getline(is, str); @@ -362,11 +362,11 @@ { g.addArc(s,t); } - + /// \brief DIMACS plain (di)graph reader function. /// /// This function reads a plain (di)graph without any designated nodes - /// and maps (e.g. a matching instance) from DIMACS format, i.e. from + /// and maps (e.g. a matching instance) from DIMACS format, i.e. from /// DIMACS files having a line starting with /// \code /// p mat @@ -392,7 +392,7 @@ for (int k = 1; k <= desc.nodeNum; ++k) { nodes[k] = g.addNode(); } - + while (is >> c) { switch (c) { case 'c': // comment line diff --git a/lemon/edge_set.h b/lemon/edge_set.h --- a/lemon/edge_set.h +++ b/lemon/edge_set.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/lemon/euler.h b/lemon/euler.h --- a/lemon/euler.h +++ b/lemon/euler.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -26,7 +26,7 @@ /// \ingroup graph_properties /// \file -/// \brief Euler tour iterators and a function for checking the \e Eulerian +/// \brief Euler tour iterators and a function for checking the \e Eulerian /// property. /// ///This file provides Euler tour iterators and a function to check @@ -41,7 +41,7 @@ ///graph (if there exists) and it converts to the \c Arc type of the digraph. /// ///For example, if the given digraph has an Euler tour (i.e it has only one - ///non-trivial component and the in-degree is equal to the out-degree + ///non-trivial component and the in-degree is equal to the out-degree ///for all nodes), then the following code will put the arcs of \c g ///to the vector \c et according to an Euler tour of \c g. ///\code @@ -138,7 +138,7 @@ ///\e undirected graph (if there exists) and it converts to the \c Arc ///and \c Edge types of the graph. /// - ///For example, if the given graph has an Euler tour (i.e it has only one + ///For example, if the given graph has an Euler tour (i.e it has only one ///non-trivial component and the degree of each node is even), ///the following code will print the arc IDs according to an ///Euler tour of \c g. @@ -147,7 +147,7 @@ /// std::cout << g.id(Edge(e)) << std::eol; /// } ///\endcode - ///Although this iterator is for undirected graphs, it still returns + ///Although this iterator is for undirected graphs, it still returns ///arcs in order to indicate the direction of the tour. ///(But arcs convert to edges, of course.) /// @@ -233,7 +233,7 @@ /// Postfix incrementation. /// - ///\warning This incrementation returns an \c Arc (which converts to + ///\warning This incrementation returns an \c Arc (which converts to ///an \c Edge), not an \ref EulerIt, as one may expect. Arc operator++(int) { diff --git a/lemon/fractional_matching.h b/lemon/fractional_matching.h --- a/lemon/fractional_matching.h +++ b/lemon/fractional_matching.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -2009,7 +2009,7 @@ /// \brief Run the algorithm. /// - /// This method runs the \c %MaxWeightedPerfectFractionalMatching + /// This method runs the \c %MaxWeightedPerfectFractionalMatching /// algorithm. /// /// \note mwfm.run() is just a shortcut of the following code. diff --git a/lemon/full_graph.h b/lemon/full_graph.h --- a/lemon/full_graph.h +++ b/lemon/full_graph.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -203,7 +203,7 @@ /// \brief Returns the node with the given index. /// - /// Returns the node with the given index. Since this structure is + /// Returns the node with the given index. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// The index of a node is the same as its ID. @@ -212,7 +212,7 @@ /// \brief Returns the index of the given node. /// - /// Returns the index of the given node. Since this structure is + /// Returns the index of the given node. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// The index of a node is the same as its ID. @@ -582,7 +582,7 @@ /// \brief Returns the node with the given index. /// - /// Returns the node with the given index. Since this structure is + /// Returns the node with the given index. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// The index of a node is the same as its ID. @@ -591,7 +591,7 @@ /// \brief Returns the index of the given node. /// - /// Returns the index of the given node. Since this structure is + /// Returns the index of the given node. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// The index of a node is the same as its ID. diff --git a/lemon/glpk.cc b/lemon/glpk.cc --- a/lemon/glpk.cc +++ b/lemon/glpk.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -59,7 +59,7 @@ return i; } - int GlpkBase::_addRow(Value lo, ExprIterator b, + int GlpkBase::_addRow(Value lo, ExprIterator b, ExprIterator e, Value up) { int i = glp_add_rows(lp, 1); @@ -68,11 +68,11 @@ glp_set_row_bnds(lp, i, GLP_FR, lo, up); } else { glp_set_row_bnds(lp, i, GLP_UP, lo, up); - } + } } else { if (up == INF) { glp_set_row_bnds(lp, i, GLP_LO, lo, up); - } else if (lo != up) { + } else if (lo != up) { glp_set_row_bnds(lp, i, GLP_DB, lo, up); } else { glp_set_row_bnds(lp, i, GLP_FX, lo, up); diff --git a/lemon/glpk.h b/lemon/glpk.h --- a/lemon/glpk.h +++ b/lemon/glpk.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -30,7 +30,7 @@ namespace _solver_bits { class VoidPtr { private: - void *_ptr; + void *_ptr; public: VoidPtr() : _ptr(0) {} @@ -38,8 +38,8 @@ VoidPtr(T* ptr) : _ptr(reinterpret_cast(ptr)) {} template - VoidPtr& operator=(T* ptr) { - _ptr = reinterpret_cast(ptr); + VoidPtr& operator=(T* ptr) { + _ptr = reinterpret_cast(ptr); return *this; } @@ -124,13 +124,13 @@ freeEnv(); } }; - + static FreeEnvHelper freeEnvHelper; protected: - + int _message_level; - + public: ///Pointer to the underlying GLPK data structure. diff --git a/lemon/gomory_hu.h b/lemon/gomory_hu.h --- a/lemon/gomory_hu.h +++ b/lemon/gomory_hu.h @@ -1,8 +1,8 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -27,7 +27,7 @@ #include /// \ingroup min_cut -/// \file +/// \file /// \brief Gomory-Hu cut tree in graphs. namespace lemon { @@ -38,13 +38,13 @@ /// /// The Gomory-Hu tree is a tree on the node set of a given graph, but it /// may contain edges which are not in the original graph. It has the - /// property that the minimum capacity edge of the path between two nodes + /// property that the minimum capacity edge of the path between two nodes /// in this tree has the same weight as the minimum cut in the graph /// between these nodes. Moreover the components obtained by removing /// this edge from the tree determine the corresponding minimum cut. /// Therefore once this tree is computed, the minimum cut between any pair /// of nodes can easily be obtained. - /// + /// /// The algorithm calculates \e n-1 distinct minimum cuts (currently with /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall /// time complexity. It calculates a rooted Gomory-Hu tree. @@ -60,10 +60,10 @@ /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap". #ifdef DOXYGEN template + typename CAP> #else template > + typename CAP = typename GR::template EdgeMap > #endif class GomoryHu { public: @@ -74,7 +74,7 @@ typedef CAP Capacity; /// The value type of capacities typedef typename Capacity::Value Value; - + private: TEMPLATE_GRAPH_TYPEDEFS(Graph); @@ -89,28 +89,28 @@ void createStructures() { if (!_pred) { - _pred = new typename Graph::template NodeMap(_graph); + _pred = new typename Graph::template NodeMap(_graph); } if (!_weight) { - _weight = new typename Graph::template NodeMap(_graph); + _weight = new typename Graph::template NodeMap(_graph); } if (!_order) { - _order = new typename Graph::template NodeMap(_graph); + _order = new typename Graph::template NodeMap(_graph); } } void destroyStructures() { if (_pred) { - delete _pred; + delete _pred; } if (_weight) { - delete _weight; + delete _weight; } if (_order) { - delete _order; + delete _order; } } - + public: /// \brief Constructor @@ -118,9 +118,9 @@ /// Constructor. /// \param graph The undirected graph the algorithm runs on. /// \param capacity The edge capacity map. - GomoryHu(const Graph& graph, const Capacity& capacity) + GomoryHu(const Graph& graph, const Capacity& capacity) : _graph(graph), _capacity(capacity), - _pred(0), _weight(0), _order(0) + _pred(0), _weight(0), _order(0) { checkConcept, Capacity>(); } @@ -134,7 +134,7 @@ } private: - + // Initialize the internal data structures void init() { createStructures(); @@ -145,7 +145,7 @@ (*_order)[n] = -1; } (*_pred)[_root] = INVALID; - (*_weight)[_root] = std::numeric_limits::max(); + (*_weight)[_root] = std::numeric_limits::max(); } @@ -154,50 +154,50 @@ Preflow fa(_graph, _capacity, _root, INVALID); for (NodeIt n(_graph); n != INVALID; ++n) { - if (n == _root) continue; + if (n == _root) continue; - Node pn = (*_pred)[n]; - fa.source(n); - fa.target(pn); + Node pn = (*_pred)[n]; + fa.source(n); + fa.target(pn); - fa.runMinCut(); + fa.runMinCut(); - (*_weight)[n] = fa.flowValue(); + (*_weight)[n] = fa.flowValue(); - for (NodeIt nn(_graph); nn != INVALID; ++nn) { - if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) { - (*_pred)[nn] = n; - } - } - if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) { - (*_pred)[n] = (*_pred)[pn]; - (*_pred)[pn] = n; - (*_weight)[n] = (*_weight)[pn]; - (*_weight)[pn] = fa.flowValue(); - } + for (NodeIt nn(_graph); nn != INVALID; ++nn) { + if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) { + (*_pred)[nn] = n; + } + } + if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) { + (*_pred)[n] = (*_pred)[pn]; + (*_pred)[pn] = n; + (*_weight)[n] = (*_weight)[pn]; + (*_weight)[pn] = fa.flowValue(); + } } (*_order)[_root] = 0; int index = 1; for (NodeIt n(_graph); n != INVALID; ++n) { - std::vector st; - Node nn = n; - while ((*_order)[nn] == -1) { - st.push_back(nn); - nn = (*_pred)[nn]; - } - while (!st.empty()) { - (*_order)[st.back()] = index++; - st.pop_back(); - } + std::vector st; + Node nn = n; + while ((*_order)[nn] == -1) { + st.push_back(nn); + nn = (*_pred)[nn]; + } + while (!st.empty()) { + (*_order)[st.back()] = index++; + st.pop_back(); + } } } public: ///\name Execution Control - + ///@{ /// \brief Run the Gomory-Hu algorithm. @@ -207,7 +207,7 @@ init(); start(); } - + /// @} ///\name Query Functions @@ -232,7 +232,7 @@ /// \brief Return the weight of the predecessor edge in the /// Gomory-Hu tree. /// - /// This function returns the weight of the predecessor edge of the + /// This function returns the weight of the predecessor edge of the /// given node in the Gomory-Hu tree. /// If \c node is the root of the tree, the result is undefined. /// @@ -254,7 +254,7 @@ /// \brief Return the minimum cut value between two nodes /// /// This function returns the minimum cut value between the nodes - /// \c s and \c t. + /// \c s and \c t. /// It finds the nearest common ancestor of the given nodes in the /// Gomory-Hu tree and calculates the minimum weight edge on the /// paths to the ancestor. @@ -263,15 +263,15 @@ Value minCutValue(const Node& s, const Node& t) const { Node sn = s, tn = t; Value value = std::numeric_limits::max(); - + while (sn != tn) { - if ((*_order)[sn] < (*_order)[tn]) { - if ((*_weight)[tn] <= value) value = (*_weight)[tn]; - tn = (*_pred)[tn]; - } else { - if ((*_weight)[sn] <= value) value = (*_weight)[sn]; - sn = (*_pred)[sn]; - } + if ((*_order)[sn] < (*_order)[tn]) { + if ((*_weight)[tn] <= value) value = (*_weight)[tn]; + tn = (*_pred)[tn]; + } else { + if ((*_weight)[sn] <= value) value = (*_weight)[sn]; + sn = (*_pred)[sn]; + } } return value; } @@ -302,23 +302,23 @@ bool s_root=false; Node rn = INVALID; Value value = std::numeric_limits::max(); - + while (sn != tn) { - if ((*_order)[sn] < (*_order)[tn]) { - if ((*_weight)[tn] <= value) { - rn = tn; + if ((*_order)[sn] < (*_order)[tn]) { + if ((*_weight)[tn] <= value) { + rn = tn; s_root = false; - value = (*_weight)[tn]; - } - tn = (*_pred)[tn]; - } else { - if ((*_weight)[sn] <= value) { - rn = sn; + value = (*_weight)[tn]; + } + tn = (*_pred)[tn]; + } else { + if ((*_weight)[sn] <= value) { + rn = sn; s_root = true; - value = (*_weight)[sn]; - } - sn = (*_pred)[sn]; - } + value = (*_weight)[sn]; + } + sn = (*_pred)[sn]; + } } typename Graph::template NodeMap reached(_graph, false); @@ -329,18 +329,18 @@ std::vector st; for (NodeIt n(_graph); n != INVALID; ++n) { - st.clear(); + st.clear(); Node nn = n; - while (!reached[nn]) { - st.push_back(nn); - nn = (*_pred)[nn]; - } - while (!st.empty()) { - cutMap.set(st.back(), cutMap[nn]); - st.pop_back(); - } + while (!reached[nn]) { + st.push_back(nn); + nn = (*_pred)[nn]; + } + while (!st.empty()) { + cutMap.set(st.back(), cutMap[nn]); + st.pop_back(); + } } - + return value; } @@ -349,7 +349,7 @@ friend class MinCutNodeIt; /// Iterate on the nodes of a minimum cut - + /// This iterator class lists the nodes of a minimum cut found by /// GomoryHu. Before using it, you must allocate a GomoryHu class /// and call its \ref GomoryHu::run() "run()" method. @@ -442,11 +442,11 @@ return n; } }; - + friend class MinCutEdgeIt; - + /// Iterate on the edges of a minimum cut - + /// This iterator class lists the edges of a minimum cut found by /// GomoryHu. Before using it, you must allocate a GomoryHu class /// and call its \ref GomoryHu::run() "run()" method. @@ -479,7 +479,7 @@ _arc_it=typename Graph::OutArcIt(_graph,_node_it); } } - + public: /// Constructor @@ -548,7 +548,7 @@ return *this; } /// Postfix incrementation - + /// Postfix incrementation. /// /// \warning This incrementation diff --git a/lemon/graph_to_eps.h b/lemon/graph_to_eps.h --- a/lemon/graph_to_eps.h +++ b/lemon/graph_to_eps.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/lemon/hao_orlin.h b/lemon/hao_orlin.h --- a/lemon/hao_orlin.h +++ b/lemon/hao_orlin.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -31,7 +31,7 @@ /// \ingroup min_cut /// \brief Implementation of the Hao-Orlin algorithm. /// -/// Implementation of the Hao-Orlin algorithm for finding a minimum cut +/// Implementation of the Hao-Orlin algorithm for finding a minimum cut /// in a digraph. namespace lemon { @@ -41,7 +41,7 @@ /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph. /// /// This class implements the Hao-Orlin algorithm for finding a minimum - /// value cut in a directed graph \f$D=(V,A)\f$. + /// value cut in a directed graph \f$D=(V,A)\f$. /// It takes a fixed node \f$ source \in V \f$ and /// consists of two phases: in the first phase it determines a /// minimum cut with \f$ source \f$ on the source-side (i.e. a set @@ -58,7 +58,7 @@ /// /// For an undirected graph you can run just the first phase of the /// algorithm or you can use the algorithm of Nagamochi and Ibaraki, - /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ + /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ /// time. It is implemented in the NagamochiIbaraki algorithm class. /// /// \tparam GR The type of the digraph the algorithm runs on. @@ -76,7 +76,7 @@ #endif class HaoOrlin { public: - + /// The digraph type of the algorithm typedef GR Digraph; /// The capacity map type of the algorithm @@ -864,7 +864,7 @@ /// \brief Initialize the internal data structures. /// /// This function initializes the internal data structures. It creates - /// the maps and some bucket structures for the algorithm. + /// the maps and some bucket structures for the algorithm. /// The given node is used as the source node for the push-relabel /// algorithm. void init(const Node& source) { @@ -944,7 +944,7 @@ /// \brief Run the algorithm. /// - /// This function runs the algorithm. It uses the given \c source node, + /// This function runs the algorithm. It uses the given \c source node, /// finds a proper \c target node and then calls the \ref init(), /// \ref calculateOut() and \ref calculateIn(). void run(const Node& s) { @@ -958,7 +958,7 @@ /// \name Query Functions /// The result of the %HaoOrlin algorithm /// can be obtained using these functions.\n - /// \ref run(), \ref calculateOut() or \ref calculateIn() + /// \ref run(), \ref calculateOut() or \ref calculateIn() /// should be called before using them. /// @{ @@ -967,7 +967,7 @@ /// /// This function returns the value of the minimum cut. /// - /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() + /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() /// must be called before using this function. Value minCutValue() const { return _min_cut; @@ -986,7 +986,7 @@ /// /// \return The value of the minimum cut. /// - /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() + /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() /// must be called before using this function. template Value minCutMap(CutMap& cutMap) const { diff --git a/lemon/hartmann_orlin_mmc.h b/lemon/hartmann_orlin_mmc.h --- a/lemon/hartmann_orlin_mmc.h +++ b/lemon/hartmann_orlin_mmc.h @@ -1,8 +1,8 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -343,14 +343,14 @@ // Initialization and find strongly connected components init(); findComponents(); - + // Find the minimum cycle mean in the components for (int comp = 0; comp < _comp_num; ++comp) { if (!initComponent(comp)) continue; processRounds(); - + // Update the best cycle (global minimum mean cycle) - if ( _curr_found && (!_best_found || + if ( _curr_found && (!_best_found || _curr_cost * _best_size < _best_cost * _curr_size) ) { _best_found = true; _best_cost = _curr_cost; @@ -503,7 +503,7 @@ int n = _nodes->size(); if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) { return false; - } + } for (int i = 0; i < n; ++i) { _data[(*_nodes)[i]].resize(n + 1, PathData(INF)); } @@ -576,7 +576,7 @@ } } } - + // Check early termination bool checkTermination(int k) { typedef std::pair Pair; @@ -586,7 +586,7 @@ LargeCost cost; int size; Node u; - + // Search for cycles that are already found _curr_found = false; for (int i = 0; i < n; ++i) { @@ -607,8 +607,8 @@ } level[u] = Pair(i, j); if (j != 0) { - u = _gr.source(_data[u][j].pred); - } + u = _gr.source(_data[u][j].pred); + } } } diff --git a/lemon/howard_mmc.h b/lemon/howard_mmc.h --- a/lemon/howard_mmc.h +++ b/lemon/howard_mmc.h @@ -1,8 +1,8 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -121,7 +121,7 @@ class HowardMmc { public: - + /// The type of the digraph typedef typename TR::Digraph Digraph; /// The type of the cost map @@ -152,7 +152,7 @@ private: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); - + // The digraph the algorithm runs on const Digraph &_gr; // The cost of the arcs @@ -179,18 +179,18 @@ std::vector > _comp_nodes; std::vector* _nodes; typename Digraph::template NodeMap > _in_arcs; - + // Queue used for BFS search std::vector _queue; int _qfront, _qback; Tolerance _tolerance; - + // Infinite constant const LargeCost INF; public: - + /// \name Named Template Parameters /// @{ @@ -228,7 +228,7 @@ : public HowardMmc > { typedef HowardMmc > Create; }; - + /// @} protected: @@ -334,7 +334,7 @@ // Initialize and find strongly connected components init(); findComponents(); - + // Find the minimum cycle mean in the components for (int comp = 0; comp < _comp_num; ++comp) { // Find the minimum mean cycle in the current component @@ -445,7 +445,7 @@ _best_size = 1; _cycle_path->clear(); } - + // Find strongly connected components and initialize _comp_nodes // and _in_arcs void findComponents() { diff --git a/lemon/karp_mmc.h b/lemon/karp_mmc.h --- a/lemon/karp_mmc.h +++ b/lemon/karp_mmc.h @@ -1,8 +1,8 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -191,7 +191,7 @@ std::vector _process; Tolerance _tolerance; - + // Infinite constant const LargeCost INF; @@ -339,7 +339,7 @@ // Initialization and find strongly connected components init(); findComponents(); - + // Find the minimum cycle mean in the components for (int comp = 0; comp < _comp_num; ++comp) { if (!initComponent(comp)) continue; @@ -489,7 +489,7 @@ int n = _nodes->size(); if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) { return false; - } + } for (int i = 0; i < n; ++i) { _data[(*_nodes)[i]].resize(n + 1, PathData(INF)); } diff --git a/lemon/lgf_reader.h b/lemon/lgf_reader.h --- a/lemon/lgf_reader.h +++ b/lemon/lgf_reader.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -562,7 +562,7 @@ template friend DigraphReader digraphReader(TDGR& digraph, std::istream& is); template - friend DigraphReader digraphReader(TDGR& digraph, + friend DigraphReader digraphReader(TDGR& digraph, const std::string& fn); template friend DigraphReader digraphReader(TDGR& digraph, const char *fn); @@ -1187,14 +1187,14 @@ /// @} }; - + /// \ingroup lemon_io /// /// \brief Return a \ref DigraphReader class /// /// This function just returns a \ref DigraphReader class. /// - /// With this function a digraph can be read from an + /// With this function a digraph can be read from an /// \ref lgf-format "LGF" file or input stream with several maps and /// attributes. For example, there is network flow problem on a /// digraph, i.e. a digraph with a \e capacity map on the arcs and @@ -1249,7 +1249,7 @@ template class GraphReader; - + template GraphReader graphReader(TGR& graph, std::istream& is = std::cin); template @@ -1386,7 +1386,7 @@ template friend GraphReader graphReader(TGR& graph, std::istream& is); template - friend GraphReader graphReader(TGR& graph, const std::string& fn); + friend GraphReader graphReader(TGR& graph, const std::string& fn); template friend GraphReader graphReader(TGR& graph, const char *fn); @@ -2063,9 +2063,9 @@ /// /// \brief Return a \ref GraphReader class /// - /// This function just returns a \ref GraphReader class. + /// This function just returns a \ref GraphReader class. /// - /// With this function a graph can be read from an + /// With this function a graph can be read from an /// \ref lgf-format "LGF" file or input stream with several maps and /// attributes. For example, there is weighted matching problem on a /// graph, i.e. a graph with a \e weight map on the edges. This diff --git a/lemon/lgf_writer.h b/lemon/lgf_writer.h --- a/lemon/lgf_writer.h +++ b/lemon/lgf_writer.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -351,7 +351,7 @@ class DigraphWriter; template - DigraphWriter digraphWriter(const TDGR& digraph, + DigraphWriter digraphWriter(const TDGR& digraph, std::ostream& os = std::cout); template DigraphWriter digraphWriter(const TDGR& digraph, const std::string& fn); @@ -504,7 +504,7 @@ private: template - friend DigraphWriter digraphWriter(const TDGR& digraph, + friend DigraphWriter digraphWriter(const TDGR& digraph, std::ostream& os); template friend DigraphWriter digraphWriter(const TDGR& digraph, @@ -917,7 +917,7 @@ /// /// \brief Return a \ref DigraphWriter class /// - /// This function just returns a \ref DigraphWriter class. + /// This function just returns a \ref DigraphWriter class. /// /// With this function a digraph can be write to a file or output /// stream in \ref lgf-format "LGF" format with several maps and @@ -957,7 +957,7 @@ /// \relates DigraphWriter /// \sa digraphWriter(const TDGR& digraph, std::ostream& os) template - DigraphWriter digraphWriter(const TDGR& digraph, + DigraphWriter digraphWriter(const TDGR& digraph, const std::string& fn) { DigraphWriter tmp(digraph, fn); return tmp; @@ -1101,11 +1101,11 @@ template friend GraphWriter graphWriter(const TGR& graph, std::ostream& os); template - friend GraphWriter graphWriter(const TGR& graph, + friend GraphWriter graphWriter(const TGR& graph, const std::string& fn); template friend GraphWriter graphWriter(const TGR& graph, const char *fn); - + GraphWriter(GraphWriter& other) : _os(other._os), local_os(other.local_os), _graph(other._graph), _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) { @@ -1556,7 +1556,7 @@ /// /// \brief Return a \ref GraphWriter class /// - /// This function just returns a \ref GraphWriter class. + /// This function just returns a \ref GraphWriter class. /// /// With this function a graph can be write to a file or output /// stream in \ref lgf-format "LGF" format with several maps and diff --git a/lemon/list_graph.h b/lemon/list_graph.h --- a/lemon/list_graph.h +++ b/lemon/list_graph.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -446,7 +446,7 @@ ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are ///invalidated for the outgoing arcs of node \c v and \c InArcIt ///iterators are invalidated for the incomming arcs of \c v. - ///Moreover all iterators referencing node \c v or the removed + ///Moreover all iterators referencing node \c v or the removed ///loops are also invalidated. Other iterators remain valid. /// ///\warning This functionality cannot be used together with the Snapshot @@ -552,7 +552,7 @@ /// The newly added nodes and arcs can be removed using the /// restore() function. /// - /// \note After a state is restored, you cannot restore a later state, + /// \note After a state is restored, you cannot restore a later state, /// i.e. you cannot add the removed nodes and arcs again using /// another Snapshot instance. /// @@ -1307,7 +1307,7 @@ /// \note The moved edges are joined to node \c a using changeU() /// or changeV(), thus all edge and arc iterators whose base node is /// \c b are invalidated. - /// Moreover all iterators referencing node \c b or the removed + /// Moreover all iterators referencing node \c b or the removed /// loops are also invalidated. Other iterators remain valid. /// ///\warning This functionality cannot be used together with the @@ -1364,7 +1364,7 @@ /// The newly added nodes and edges can be removed /// using the restore() function. /// - /// \note After a state is restored, you cannot restore a later state, + /// \note After a state is restored, you cannot restore a later state, /// i.e. you cannot add the removed nodes and edges again using /// another Snapshot instance. /// diff --git a/lemon/lp.h b/lemon/lp.h --- a/lemon/lp.h +++ b/lemon/lp.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -84,7 +84,7 @@ typedef SoplexLp Lp; #elif LEMON_HAVE_CLP # define DEFAULT_LP CLP - typedef ClpLp Lp; + typedef ClpLp Lp; #endif #endif diff --git a/lemon/lp_base.cc b/lemon/lp_base.cc --- a/lemon/lp_base.cc +++ b/lemon/lp_base.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/lemon/lp_base.h b/lemon/lp_base.h --- a/lemon/lp_base.h +++ b/lemon/lp_base.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -82,7 +82,7 @@ /// Verbose output. MESSAGE_VERBOSE }; - + ///The floating point type used by the solver typedef double Value; @@ -114,14 +114,14 @@ typedef Value ExprValue; typedef True LpCol; /// Default constructor - + /// \warning The default constructor sets the Col to an /// undefined value. Col() {} /// Invalid constructor \& conversion. - + /// This constructor initializes the Col to be invalid. - /// \sa Invalid for more details. + /// \sa Invalid for more details. Col(const Invalid&) : _id(-1) {} /// Equality operator @@ -156,12 +156,12 @@ const LpBase *_solver; public: /// Default constructor - + /// \warning The default constructor sets the iterator /// to an undefined value. ColIt() {} /// Sets the iterator to the first Col - + /// Sets the iterator to the first Col. /// ColIt(const LpBase &solver) : _solver(&solver) @@ -169,12 +169,12 @@ _solver->cols.firstItem(_id); } /// Invalid constructor \& conversion - + /// Initialize the iterator to be invalid. /// \sa Invalid for more details. ColIt(const Invalid&) : Col(INVALID) {} /// Next column - + /// Assign the iterator to the next column. /// ColIt &operator++() @@ -209,14 +209,14 @@ typedef Value ExprValue; typedef True LpRow; /// Default constructor - + /// \warning The default constructor sets the Row to an /// undefined value. Row() {} /// Invalid constructor \& conversion. - + /// This constructor initializes the Row to be invalid. - /// \sa Invalid for more details. + /// \sa Invalid for more details. Row(const Invalid&) : _id(-1) {} /// Equality operator @@ -224,7 +224,7 @@ /// the same LP row or both are invalid. bool operator==(Row r) const {return _id == r._id;} /// Inequality operator - + /// \sa operator==(Row r) /// bool operator!=(Row r) const {return _id != r._id;} @@ -251,12 +251,12 @@ const LpBase *_solver; public: /// Default constructor - + /// \warning The default constructor sets the iterator /// to an undefined value. RowIt() {} /// Sets the iterator to the first Row - + /// Sets the iterator to the first Row. /// RowIt(const LpBase &solver) : _solver(&solver) @@ -264,12 +264,12 @@ _solver->rows.firstItem(_id); } /// Invalid constructor \& conversion - + /// Initialize the iterator to be invalid. /// \sa Invalid for more details. RowIt(const Invalid&) : Row(INVALID) {} /// Next row - + /// Assign the iterator to the next row. /// RowIt &operator++() @@ -347,7 +347,7 @@ public: typedef True SolverExpr; /// Default constructor - + /// Construct an empty expression, the coefficients and /// the constant component are initialized to zero. Expr() : const_comp(0) {} @@ -448,9 +448,9 @@ } ///Iterator over the expression - - ///The iterator iterates over the terms of the expression. - /// + + ///The iterator iterates over the terms of the expression. + /// ///\code ///double s=0; ///for(LpBase::Expr::CoeffIt i(e);i!=INVALID;++i) @@ -464,7 +464,7 @@ public: /// Sets the iterator to the first term - + /// Sets the iterator to the first term of the expression. /// CoeffIt(Expr& e) @@ -481,7 +481,7 @@ /// Returns the coefficient of the term const Value& operator*() const { return _it->second; } /// Next term - + /// Assign the iterator to the next term. /// CoeffIt& operator++() { ++_it; return *this; } @@ -493,9 +493,9 @@ }; /// Const iterator over the expression - - ///The iterator iterates over the terms of the expression. - /// + + ///The iterator iterates over the terms of the expression. + /// ///\code ///double s=0; ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i) @@ -509,7 +509,7 @@ public: /// Sets the iterator to the first term - + /// Sets the iterator to the first term of the expression. /// ConstCoeffIt(const Expr& e) @@ -524,7 +524,7 @@ const Value& operator*() const { return _it->second; } /// Next term - + /// Assign the iterator to the next term. /// ConstCoeffIt& operator++() { ++_it; return *this; } @@ -673,7 +673,7 @@ public: typedef True SolverExpr; /// Default constructor - + /// Construct an empty expression, the coefficients are /// initialized to zero. DualExpr() {} @@ -708,7 +708,7 @@ } } /// \brief Removes the coefficients which's absolute value does - /// not exceed \c epsilon. + /// not exceed \c epsilon. void simplify(Value epsilon = 0.0) { std::map::iterator it=comps.begin(); while (it != comps.end()) { @@ -757,9 +757,9 @@ } ///Iterator over the expression - - ///The iterator iterates over the terms of the expression. - /// + + ///The iterator iterates over the terms of the expression. + /// ///\code ///double s=0; ///for(LpBase::DualExpr::CoeffIt i(e);i!=INVALID;++i) @@ -773,7 +773,7 @@ public: /// Sets the iterator to the first term - + /// Sets the iterator to the first term of the expression. /// CoeffIt(DualExpr& e) @@ -791,7 +791,7 @@ const Value& operator*() const { return _it->second; } /// Next term - + /// Assign the iterator to the next term. /// CoeffIt& operator++() { ++_it; return *this; } @@ -803,9 +803,9 @@ }; ///Iterator over the expression - - ///The iterator iterates over the terms of the expression. - /// + + ///The iterator iterates over the terms of the expression. + /// ///\code ///double s=0; ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i) @@ -819,7 +819,7 @@ public: /// Sets the iterator to the first term - + /// Sets the iterator to the first term of the expression. /// ConstCoeffIt(const DualExpr& e) @@ -834,7 +834,7 @@ const Value& operator*() const { return _it->second; } /// Next term - + /// Assign the iterator to the next term. /// ConstCoeffIt& operator++() { ++_it; return *this; } @@ -1229,7 +1229,7 @@ Row addRow(const Constr &c) { Row r; c.expr().simplify(); - r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF, + r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF, ExprIterator(c.expr().comps.begin(), cols), ExprIterator(c.expr().comps.end(), cols), c.upperBounded()?c.upperBound()-*c.expr():INF)); @@ -1817,10 +1817,10 @@ ///The basis status of variables enum VarStatus { /// The variable is in the basis - BASIC, + BASIC, /// The variable is free, but not basic FREE, - /// The variable has active lower bound + /// The variable has active lower bound LOWER, /// The variable has active upper bound UPPER, @@ -1899,7 +1899,7 @@ return res; } /// Returns a component of the primal ray - + /// The primal ray is solution of the modified primal problem, /// where we change each finite bound to 0, and we looking for a /// negative objective value in case of minimization, and positive @@ -1933,7 +1933,7 @@ } /// Returns a component of the dual ray - + /// The dual ray is solution of the modified primal problem, where /// we change each finite bound to 0 (i.e. the objective function /// coefficients in the primal problem), and we looking for a @@ -2075,7 +2075,7 @@ return res; } ///The value of the objective function - + ///\return ///- \ref INF or -\ref INF means either infeasibility or unboundedness /// of the problem, depending on whether we minimize or maximize. diff --git a/lemon/lp_skeleton.cc b/lemon/lp_skeleton.cc --- a/lemon/lp_skeleton.cc +++ b/lemon/lp_skeleton.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/lemon/lp_skeleton.h b/lemon/lp_skeleton.h --- a/lemon/lp_skeleton.h +++ b/lemon/lp_skeleton.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -23,13 +23,13 @@ ///\file ///\brief Skeleton file to implement LP/MIP solver interfaces -/// +/// ///The classes in this file do nothing, but they can serve as skeletons when ///implementing an interface to new solvers. namespace lemon { ///A skeleton class to implement LP/MIP solver base interface - + ///This class does nothing, but it can serve as a skeleton when ///implementing an interface to new solvers. class SkeletonSolverBase : public virtual LpBase { diff --git a/lemon/maps.h b/lemon/maps.h --- a/lemon/maps.h +++ b/lemon/maps.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -233,7 +233,7 @@ /// It can be used together with some data structures, e.g. /// heap types and \c UnionFind, when the used items are small /// integers. This map conforms to the \ref concepts::ReferenceMap - /// "ReferenceMap" concept. + /// "ReferenceMap" concept. /// /// The simplest way of using this map is through the rangeMap() /// function. @@ -1916,11 +1916,11 @@ /// The graph items can be accessed by their values either using /// \c InverseMap or \c operator()(), and the values of the map can be /// accessed with an STL compatible forward iterator (\c ValueIt). - /// + /// /// This map is intended to be used when all associated values are /// different (the map is actually invertable) or there are only a few /// items with the same value. - /// Otherwise consider to use \c IterableValueMap, which is more + /// Otherwise consider to use \c IterableValueMap, which is more /// suitable and more efficient for such cases. It provides iterators /// to traverse the items with the same associated value, but /// it does not have \c InverseMap. @@ -2002,7 +2002,7 @@ private: typename Container::const_iterator it; }; - + /// Alias for \c ValueIt typedef ValueIt ValueIterator; @@ -2061,7 +2061,7 @@ typename Container::const_iterator it = _inv_map.find(val); return it != _inv_map.end() ? it->second : INVALID; } - + /// \brief Returns the number of items with the given value. /// /// This function returns the number of items with the given value @@ -2378,7 +2378,7 @@ inline RangeIdMap rangeIdMap(const GR& graph) { return RangeIdMap(graph); } - + /// \brief Dynamic iterable \c bool map. /// /// This class provides a special graph map type which can store a @@ -2638,7 +2638,7 @@ /// \param map The IterableBoolMap. /// \param value The value. ItemIt(const IterableBoolMap& map, bool value) - : Parent(value ? + : Parent(value ? (map._sep > 0 ? map._array[map._sep - 1] : INVALID) : (map._sep < int(map._array.size()) ? @@ -3786,7 +3786,7 @@ void mapCopy(const GR& gr, const From& from, To& to) { typedef typename To::Key Item; typedef typename ItemSetTraits::ItemIt ItemIt; - + for (ItemIt it(gr); it != INVALID; ++it) { to.set(it, from[it]); } @@ -3794,7 +3794,7 @@ /// \brief Compare two graph maps. /// - /// This function compares the values of two graph maps. It returns + /// This function compares the values of two graph maps. It returns /// \c true if the maps assign the same value for all items in the graph. /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal /// and their \c Value types must be comparable using \c %operator==(). @@ -3806,7 +3806,7 @@ bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) { typedef typename Map2::Key Item; typedef typename ItemSetTraits::ItemIt ItemIt; - + for (ItemIt it(gr); it != INVALID; ++it) { if (!(map1[it] == map2[it])) return false; } diff --git a/lemon/matching.h b/lemon/matching.h --- a/lemon/matching.h +++ b/lemon/matching.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -1623,7 +1623,7 @@ (*_delta2_index)[i] = _delta2->PRE_HEAP; (*_delta4_index)[i] = _delta4->PRE_HEAP; } - + _unmatched = _node_num; _delta1->clear(); @@ -1678,7 +1678,7 @@ _blossom_node_list.clear(); _blossom_potential.clear(); - + if (_fractional == 0) { _fractional = new FractionalMatching(_graph, _weight, false); } @@ -1750,17 +1750,17 @@ while (n != v) { subblossoms[--num] = _blossom_set->find(v); _delta1->push(v, _fractional->nodeValue(v)); - v = _graph.target(_fractional->matching(v)); + v = _graph.target(_fractional->matching(v)); } - - int surface = + + int surface = _blossom_set->join(subblossoms.begin(), subblossoms.end()); (*_blossom_data)[surface].status = EVEN; (*_blossom_data)[surface].pred = INVALID; (*_blossom_data)[surface].next = INVALID; (*_blossom_data)[surface].pot = 0; (*_blossom_data)[surface].offset = 0; - + _tree_set->insert(surface); ++_unmatched; } @@ -1810,7 +1810,7 @@ } } } - + if (!(*_node_data)[ni].heap.empty()) { _blossom_set->decrease(n, (*_node_data)[ni].heap.prio()); _delta2->push(nb, _blossom_set->classPrio(nb)); @@ -2269,7 +2269,7 @@ Value _delta_sum; int _unmatched; - typedef MaxWeightedPerfectFractionalMatching + typedef MaxWeightedPerfectFractionalMatching FractionalMatching; FractionalMatching *_fractional; @@ -3095,7 +3095,7 @@ _blossom_node_list.clear(); _blossom_potential.clear(); - + if (_fractional == 0) { _fractional = new FractionalMatching(_graph, _weight, false); } @@ -3161,17 +3161,17 @@ v = _graph.target(_fractional->matching(n)); while (n != v) { subblossoms[--num] = _blossom_set->find(v); - v = _graph.target(_fractional->matching(v)); + v = _graph.target(_fractional->matching(v)); } - - int surface = + + int surface = _blossom_set->join(subblossoms.begin(), subblossoms.end()); (*_blossom_data)[surface].status = EVEN; (*_blossom_data)[surface].pred = INVALID; (*_blossom_data)[surface].next = INVALID; (*_blossom_data)[surface].pot = 0; (*_blossom_data)[surface].offset = 0; - + _tree_set->insert(surface); ++_unmatched; } @@ -3221,7 +3221,7 @@ } } } - + if (!(*_node_data)[ni].heap.empty()) { _blossom_set->decrease(n, (*_node_data)[ni].heap.prio()); _delta2->push(nb, _blossom_set->classPrio(nb)); diff --git a/lemon/math.h b/lemon/math.h --- a/lemon/math.h +++ b/lemon/math.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -56,7 +56,7 @@ const long double SQRT1_2 = 0.7071067811865475244008443621048490L; ///Check whether the parameter is NaN or not - + ///This function checks whether the parameter is NaN or not. ///Is should be equivalent with std::isnan(), but it is not ///provided by all compilers. diff --git a/lemon/min_cost_arborescence.h b/lemon/min_cost_arborescence.h --- a/lemon/min_cost_arborescence.h +++ b/lemon/min_cost_arborescence.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -128,8 +128,8 @@ class MinCostArborescence { public: - /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" - /// of the algorithm. + /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" + /// of the algorithm. typedef TR Traits; /// The type of the underlying digraph. typedef typename Traits::Digraph Digraph; @@ -436,7 +436,7 @@ /// /// \ref named-templ-param "Named parameter" for setting /// \c PredMap type. - /// It must meet the \ref concepts::WriteMap "WriteMap" concept, + /// It must meet the \ref concepts::WriteMap "WriteMap" concept, /// and its value type must be the \c Arc type of the digraph. template struct SetPredMap diff --git a/lemon/network_simplex.h b/lemon/network_simplex.h --- a/lemon/network_simplex.h +++ b/lemon/network_simplex.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -97,7 +97,7 @@ /// infinite upper bound. UNBOUNDED }; - + /// \brief Constants for selecting the type of the supply constraints. /// /// Enum type containing constants for selecting the supply type, @@ -115,7 +115,7 @@ /// supply/demand constraints in the definition of the problem. LEQ }; - + /// \brief Constants for selecting the pivot rule. /// /// Enum type containing constants for selecting the pivot rule for @@ -158,7 +158,7 @@ /// candidate list and extends this list in every iteration. ALTERING_LIST }; - + private: TEMPLATE_DIGRAPH_TYPEDEFS(GR); @@ -227,11 +227,11 @@ int first, second, right, last; int stem, par_stem, new_stem; Value delta; - + const Value MAX; public: - + /// \brief Constant for infinite upper bounds (capacities). /// /// Constant for infinite upper bounds (capacities). @@ -498,8 +498,8 @@ } } if (_curr_length == 0) return false; - - search_end: + + search_end: _minor_count = 1; _next_arc = e; return true; @@ -608,7 +608,7 @@ } } if (_curr_length == 0) return false; - + search_end: // Make heap of the candidate list (approximating a partial sort) @@ -634,7 +634,7 @@ /// /// \param graph The digraph the algorithm runs on. /// \param arc_mixing Indicate if the arcs have to be stored in a - /// mixed order in the internal data structure. + /// mixed order in the internal data structure. /// In special cases, it could lead to better overall performance, /// but it is usually slower. Therefore it is disabled by default. NetworkSimplex(const GR& graph, bool arc_mixing = false) : @@ -649,7 +649,7 @@ "The flow type of NetworkSimplex must be signed"); LEMON_ASSERT(std::numeric_limits::is_signed, "The cost type of NetworkSimplex must be signed"); - + // Reset data structures reset(); } @@ -763,7 +763,7 @@ _supply[_node_id[t]] = -k; return *this; } - + /// \brief Set the type of the supply constraints. /// /// This function sets the type of the supply/demand constraints. @@ -789,7 +789,7 @@ /// /// This function runs the algorithm. /// The paramters can be specified using functions \ref lowerMap(), - /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), + /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), /// \ref supplyType(). /// For example, /// \code @@ -944,12 +944,12 @@ _target[i] = _node_id[_graph.target(a)]; } } - + // Reset parameters resetParams(); return *this; } - + /// @} /// \name Query Functions @@ -1089,7 +1089,7 @@ _flow[i] = 0; _state[i] = STATE_LOWER; } - + // Set data for the artificial root node _root = _node_num; _parent[_root] = -1; @@ -1263,7 +1263,7 @@ // Search the cycle along the path form the second node to the root for (int u = second; u != join; u = _parent[u]) { e = _pred[u]; - d = _forward[u] ? + d = _forward[u] ? (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e]; if (d <= delta) { delta = d; @@ -1567,7 +1567,7 @@ updatePotential(); } } - + // Check feasibility for (int e = _search_arc_num; e != _all_arc_num; ++e) { if (_flow[e] != 0) return INFEASIBLE; @@ -1584,7 +1584,7 @@ } } } - + // Shift potentials to meet the requirements of the GEQ/LEQ type // optimality conditions if (_sum_supply == 0) { diff --git a/lemon/path.h b/lemon/path.h --- a/lemon/path.h +++ b/lemon/path.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -966,20 +966,20 @@ } }; - + template ::value> struct PathCopySelector { static void copy(const From& from, To& to) { PathCopySelectorForward::copy(from, to); - } + } }; template struct PathCopySelector { static void copy(const From& from, To& to) { PathCopySelectorBackward::copy(from, to); - } + } }; } diff --git a/lemon/planarity.h b/lemon/planarity.h --- a/lemon/planarity.h +++ b/lemon/planarity.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -140,17 +140,17 @@ template class PlanarityChecking { private: - + TEMPLATE_GRAPH_TYPEDEFS(Graph); const Graph& _graph; private: - + typedef typename Graph::template NodeMap PredMap; - + typedef typename Graph::template EdgeMap TreeMap; - + typedef typename Graph::template NodeMap OrderMap; typedef std::vector OrderList; @@ -221,7 +221,7 @@ } for (typename MergeRoots::Value::iterator it = - merge_roots[node].begin(); + merge_roots[node].begin(); it != merge_roots[node].end(); ++it) { int rn = *it; walkDown(rn, i, node_data, order_list, child_lists, @@ -432,7 +432,7 @@ Node ynode = order_list[yn]; bool rd; - if (!external(xnode, rorder, child_lists, + if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) { rd = true; } else if (!external(ynode, rorder, child_lists, diff --git a/lemon/preflow.h b/lemon/preflow.h --- a/lemon/preflow.h +++ b/lemon/preflow.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/lemon/smart_graph.h b/lemon/smart_graph.h --- a/lemon/smart_graph.h +++ b/lemon/smart_graph.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -186,7 +186,7 @@ /// ///\ref SmartDigraph is a simple and fast digraph implementation. ///It is also quite memory efficient but at the price - ///that it does not support node and arc deletion + ///that it does not support node and arc deletion ///(except for the Snapshot feature). /// ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" @@ -335,7 +335,7 @@ ///restore() function. This is the only way for deleting nodes and/or ///arcs from a SmartDigraph structure. /// - ///\note After a state is restored, you cannot restore a later state, + ///\note After a state is restored, you cannot restore a later state, ///i.e. you cannot add the removed nodes and arcs again using ///another Snapshot instance. /// @@ -614,7 +614,7 @@ /// /// \ref SmartGraph is a simple and fast graph implementation. /// It is also quite memory efficient but at the price - /// that it does not support node and edge deletion + /// that it does not support node and edge deletion /// (except for the Snapshot feature). /// /// This type fully conforms to the \ref concepts::Graph "Graph concept" @@ -761,7 +761,7 @@ ///restore() function. This is the only way for deleting nodes and/or ///edges from a SmartGraph structure. /// - ///\note After a state is restored, you cannot restore a later state, + ///\note After a state is restored, you cannot restore a later state, ///i.e. you cannot add the removed nodes and edges again using ///another Snapshot instance. /// diff --git a/lemon/soplex.cc b/lemon/soplex.cc --- a/lemon/soplex.cc +++ b/lemon/soplex.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -287,7 +287,7 @@ SoplexLp::SolveExitStatus SoplexLp::_solve() { _clear_temporals(); - + _applyMessageLevel(); soplex::SPxSolver::Status status = soplex->solve(); diff --git a/lemon/soplex.h b/lemon/soplex.h --- a/lemon/soplex.h +++ b/lemon/soplex.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/lemon/static_graph.h b/lemon/static_graph.h --- a/lemon/static_graph.h +++ b/lemon/static_graph.h @@ -1,8 +1,8 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -31,12 +31,12 @@ class StaticDigraphBase { public: - StaticDigraphBase() - : built(false), node_num(0), arc_num(0), + StaticDigraphBase() + : built(false), node_num(0), arc_num(0), node_first_out(NULL), node_first_in(NULL), - arc_source(NULL), arc_target(NULL), + arc_source(NULL), arc_target(NULL), arc_next_in(NULL), arc_next_out(NULL) {} - + ~StaticDigraphBase() { if (built) { delete[] node_first_out; @@ -62,7 +62,7 @@ }; class Arc { - friend class StaticDigraphBase; + friend class StaticDigraphBase; protected: int id; Arc(int _id) : id(_id) {} @@ -83,8 +83,8 @@ void first(Arc& e) const { e.id = arc_num - 1; } static void next(Arc& e) { --e.id; } - void firstOut(Arc& e, const Node& n) const { - e.id = node_first_out[n.id] != node_first_out[n.id + 1] ? + void firstOut(Arc& e, const Node& n) const { + e.id = node_first_out[n.id] != node_first_out[n.id + 1] ? node_first_out[n.id] : -1; } void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; } @@ -113,21 +113,21 @@ public: typedef typename Digraph::Arc Arc; - ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef) + ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef) : digraph(_graph), nodeRef(_nodeRef) {} - + bool operator()(const Arc& left, const Arc& right) const { - return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)]; + return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)]; } private: const Digraph& digraph; const NodeRefMap& nodeRef; }; - + public: typedef True BuildTag; - + void clear() { if (built) { delete[] node_first_out; @@ -141,7 +141,7 @@ node_num = 0; arc_num = 0; } - + template void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) { typedef typename Digraph::Node GNode; @@ -183,7 +183,7 @@ it != arcs.end(); ++it) { int target = nodeRef[digraph.target(*it)].id; arcRef[*it] = Arc(arc_index); - arc_source[arc_index] = source; + arc_source[arc_index] = source; arc_target[arc_index] = target; arc_next_in[arc_index] = node_first_in[target]; node_first_in[target] = arc_index; @@ -197,7 +197,7 @@ } node_first_out[node_num] = arc_num; } - + template void build(int n, ArcListIterator first, ArcListIterator last) { built = true; @@ -212,11 +212,11 @@ arc_target = new int[arc_num]; arc_next_out = new int[arc_num]; arc_next_in = new int[arc_num]; - + for (int i = 0; i != node_num; ++i) { node_first_in[i] = -1; - } - + } + int arc_index = 0; for (int i = 0; i != node_num; ++i) { node_first_out[i] = arc_index; @@ -282,7 +282,7 @@ /// /// Since this digraph structure is completely static, its nodes and arcs /// can be indexed with integers from the ranges [0..nodeNum()-1] - /// and [0..arcNum()-1], respectively. + /// and [0..arcNum()-1], respectively. /// The index of an item is the same as its ID, it can be obtained /// using the corresponding \ref index() or \ref concepts::Digraph::id() /// "id()" function. A node or arc with a certain index can be obtained @@ -299,9 +299,9 @@ public: typedef ExtendedStaticDigraphBase Parent; - + public: - + /// \brief Constructor /// /// Default constructor. @@ -349,7 +349,7 @@ /// /// This method also makes possible to copy a digraph to a StaticDigraph /// structure using \ref DigraphCopy. - /// + /// /// \param digraph An existing digraph to be copied. /// \param nodeRef The node references will be copied into this map. /// Its key type must be \c Digraph::Node and its value type must be @@ -370,7 +370,7 @@ if (built) Parent::clear(); Parent::build(digraph, nodeRef, arcRef); } - + /// \brief Build the digraph from an arc list. /// /// This function builds the digraph from the given arc list. @@ -421,7 +421,7 @@ using Parent::fastFirstOut; using Parent::fastNextOut; using Parent::fastLastOut; - + public: class OutArcIt : public Arc { @@ -432,8 +432,8 @@ OutArcIt(Invalid i) : Arc(i) { } OutArcIt(const StaticDigraph& digraph, const Node& node) { - digraph.fastFirstOut(*this, node); - digraph.fastLastOut(last, node); + digraph.fastFirstOut(*this, node); + digraph.fastLastOut(last, node); if (last == *this) *this = INVALID; } @@ -443,10 +443,10 @@ } } - OutArcIt& operator++() { + OutArcIt& operator++() { StaticDigraph::fastNextOut(*this); if (last == *this) *this = INVALID; - return *this; + return *this; } private: diff --git a/lemon/suurballe.h b/lemon/suurballe.h --- a/lemon/suurballe.h +++ b/lemon/suurballe.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -65,7 +65,7 @@ /// It must conform to the \ref lemon::concepts::Path "Path" concept /// and it must have an \c addBack() function. typedef lemon::Path Path; - + /// The cross reference type used for the heap. typedef typename GR::template NodeMap HeapCrossRef; @@ -158,7 +158,7 @@ PredMap &_pred; Node _s; Node _t; - + PotentialMap _dist; std::vector _proc_nodes; @@ -167,9 +167,9 @@ // Constructor ResidualDijkstra(Suurballe &srb) : _graph(srb._graph), _length(srb._length), - _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred), + _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred), _s(srb._s), _t(srb._t), _dist(_graph) {} - + // Run the algorithm and return true if a path is found // from the source node to the target node. bool run(int cnt) { @@ -177,7 +177,7 @@ } private: - + // Execute the algorithm for the first time (the flow and potential // functions have to be identically zero). bool startFirst() { @@ -348,7 +348,7 @@ : public Suurballe > { typedef Suurballe > Create; }; - + template struct SetHeapTraits : public Traits { typedef H Heap; @@ -359,7 +359,7 @@ /// \c Heap and \c HeapCrossRef types. /// /// \ref named-templ-param "Named parameter" for setting \c Heap - /// and \c HeapCrossRef types with automatic allocation. + /// and \c HeapCrossRef types with automatic allocation. /// They will be used for internal Dijkstra computations. /// The heap type must conform to the \ref lemon::concepts::Heap "Heap" /// concept and its priority type must be \c Length. @@ -397,7 +397,7 @@ // The pred arc map PredMap _pred; - + // Data for full init PotentialMap *_init_dist; PredMap *_init_pred; @@ -555,7 +555,7 @@ ::Create dijk(_graph, _length); dijk.distMap(*_init_dist).predMap(*_init_pred); dijk.run(s); - + _full_init = true; } @@ -599,7 +599,7 @@ int findFlow(const Node& t, int k = 2) { _t = t; ResidualDijkstra dijkstra(*this); - + // Initialization for (ArcIt e(_graph); e != INVALID; ++e) { (*_flow)[e] = 0; @@ -613,7 +613,7 @@ while ((e = (*_init_pred)[u]) != INVALID) { (*_flow)[e] = 1; u = _graph.source(e); - } + } _path_num = 1; } else { for (NodeIt n(_graph); n != INVALID; ++n) { diff --git a/lemon/unionfind.h b/lemon/unionfind.h --- a/lemon/unionfind.h +++ b/lemon/unionfind.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/test/bellman_ford_test.cc b/test/bellman_ford_test.cc --- a/test/bellman_ford_test.cc +++ b/test/bellman_ford_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -97,7 +97,7 @@ p = const_bf_test.predMap(); pp = const_bf_test.path(t); pp = const_bf_test.negativeCycle(); - + for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {} } { @@ -110,7 +110,7 @@ LengthMap length_map; concepts::ReadWriteMap pred_map; concepts::ReadWriteMap dist_map; - + bf_test .lengthMap(length_map) .predMap(pred_map) @@ -189,7 +189,7 @@ check(checkPath(gr, p), "path() found a wrong path."); check(pathSource(gr, p) == s, "path() found a wrong path."); check(pathTarget(gr, p) == t, "path() found a wrong path."); - + ListPath path; Value dist; bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t); @@ -228,18 +228,18 @@ SmartDigraph gr; IntArcMap length(gr); - + Node n1 = gr.addNode(); Node n2 = gr.addNode(); Node n3 = gr.addNode(); Node n4 = gr.addNode(); - + Arc a1 = gr.addArc(n1, n2); Arc a2 = gr.addArc(n2, n2); - + length[a1] = 2; length[a2] = -1; - + { BellmanFord bf(gr, length); bf.run(n1); @@ -247,21 +247,21 @@ check(p.length() == 1 && p.front() == p.back() && p.front() == a2, "Wrong negative cycle."); } - + length[a2] = 0; - + { BellmanFord bf(gr, length); bf.run(n1); check(bf.negativeCycle().empty(), "Negative cycle should not be found."); } - + length[gr.addArc(n1, n3)] = 5; length[gr.addArc(n4, n3)] = 1; length[gr.addArc(n2, n4)] = 2; length[gr.addArc(n3, n2)] = -4; - + { BellmanFord bf(gr, length); bf.init(); diff --git a/test/bfs_test.cc b/test/bfs_test.cc --- a/test/bfs_test.cc +++ b/test/bfs_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -83,7 +83,7 @@ n = const_bfs_test.nextNode(); b = const_bfs_test.emptyQueue(); i = const_bfs_test.queueSize(); - + bfs_test.start(); bfs_test.start(t); bfs_test.start(nm); @@ -104,12 +104,12 @@ ::SetStandardProcessedMap ::SetProcessedMap > ::Create bfs_test(G); - + concepts::ReadWriteMap pred_map; concepts::ReadWriteMap dist_map; concepts::ReadWriteMap reached_map; concepts::WriteMap processed_map; - + bfs_test .predMap(pred_map) .distMap(dist_map) @@ -119,7 +119,7 @@ bfs_test.run(s); bfs_test.run(s,t); bfs_test.run(); - + bfs_test.init(); bfs_test.addSource(s); n = bfs_test.processNextNode(); @@ -128,7 +128,7 @@ n = bfs_test.nextNode(); b = bfs_test.emptyQueue(); i = bfs_test.queueSize(); - + bfs_test.start(); bfs_test.start(t); bfs_test.start(nm); diff --git a/test/circulation_test.cc b/test/circulation_test.cc --- a/test/circulation_test.cc +++ b/test/circulation_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -81,13 +81,13 @@ ::Create CirculationType; CirculationType circ_test(g, lcap, ucap, supply); const CirculationType& const_circ_test = circ_test; - + circ_test .lowerMap(lcap) .upperMap(ucap) .supplyMap(supply) .flowMap(flow); - + const CirculationType::Elevator& elev = const_circ_test.elevator(); circ_test.elevator(const_cast(elev)); CirculationType::Tolerance tol = const_circ_test.tolerance(); @@ -102,7 +102,7 @@ const FlowMap& fm = const_circ_test.flowMap(); b = const_circ_test.barrier(n); const_circ_test.barrierMap(bar); - + ignore_unused_variable_warning(fm); } diff --git a/test/connectivity_test.cc b/test/connectivity_test.cc --- a/test/connectivity_test.cc +++ b/test/connectivity_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -29,12 +29,12 @@ { typedef ListDigraph Digraph; typedef Undirector Graph; - + { Digraph d; Digraph::NodeMap order(d); Graph g(d); - + check(stronglyConnected(d), "The empty digraph is strongly connected"); check(countStronglyConnectedComponents(d) == 0, "The empty digraph has 0 strongly connected component"); @@ -48,7 +48,7 @@ check(biEdgeConnected(g), "The empty graph is bi-edge-connected"); check(countBiEdgeConnectedComponents(g) == 0, "The empty graph has 0 bi-edge-connected component"); - + check(dag(d), "The empty digraph is DAG."); check(checkedTopologicalSort(d, order), "The empty digraph is DAG."); check(loopFree(d), "The empty digraph is loop-free."); @@ -82,7 +82,7 @@ check(biEdgeConnected(g), "This graph is bi-edge-connected"); check(countBiEdgeConnectedComponents(g) == 1, "This graph has 1 bi-edge-connected component"); - + check(dag(d), "This digraph is DAG."); check(checkedTopologicalSort(d, order), "This digraph is DAG."); check(loopFree(d), "This digraph is loop-free."); @@ -101,14 +101,14 @@ Digraph d; Digraph::NodeMap order(d); Graph g(d); - + Digraph::Node n1 = d.addNode(); Digraph::Node n2 = d.addNode(); Digraph::Node n3 = d.addNode(); Digraph::Node n4 = d.addNode(); Digraph::Node n5 = d.addNode(); Digraph::Node n6 = d.addNode(); - + d.addArc(n1, n3); d.addArc(n3, n2); d.addArc(n2, n1); @@ -136,23 +136,23 @@ check(loopFree(g), "This graph is loop-free."); check(!parallelFree(g), "This graph is not parallel-free."); check(!simpleGraph(g), "This graph is not simple."); - + d.addArc(n3, n3); - + check(!loopFree(d), "This digraph is not loop-free."); check(!loopFree(g), "This graph is not loop-free."); check(!simpleGraph(d), "This digraph is not simple."); - + d.addArc(n3, n2); - + check(!parallelFree(d), "This digraph is not parallel-free."); } - + { Digraph d; Digraph::ArcMap cutarcs(d, false); Graph g(d); - + Digraph::Node n1 = d.addNode(); Digraph::Node n2 = d.addNode(); Digraph::Node n3 = d.addNode(); @@ -172,7 +172,7 @@ d.addArc(n1, n8); d.addArc(n6, n7); d.addArc(n7, n6); - + check(!stronglyConnected(d), "This digraph is not strongly connected"); check(countStronglyConnectedComponents(d) == 3, "This digraph has 3 strongly connected components"); @@ -235,7 +235,7 @@ // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein) Digraph d; Digraph::NodeMap order(d); - + Digraph::Node belt = d.addNode(); Digraph::Node trousers = d.addNode(); Digraph::Node necktie = d.addNode(); @@ -255,7 +255,7 @@ d.addArc(shirt, belt); d.addArc(shirt, necktie); d.addArc(necktie, coat); - + check(dag(d), "This digraph is DAG."); topologicalSort(d, order); for (Digraph::ArcIt a(d); a != INVALID; ++a) { @@ -267,7 +267,7 @@ { ListGraph g; ListGraph::NodeMap map(g); - + ListGraph::Node n1 = g.addNode(); ListGraph::Node n2 = g.addNode(); ListGraph::Node n3 = g.addNode(); @@ -283,10 +283,10 @@ g.addEdge(n4, n6); g.addEdge(n4, n7); g.addEdge(n5, n7); - + check(bipartite(g), "This graph is bipartite"); check(bipartitePartitions(g, map), "This graph is bipartite"); - + check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7], "Wrong bipartitePartitions()"); check(map[n3] == map[n4] && map[n3] == map[n5], diff --git a/test/dfs_test.cc b/test/dfs_test.cc --- a/test/dfs_test.cc +++ b/test/dfs_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -83,7 +83,7 @@ e = const_dfs_test.nextArc(); b = const_dfs_test.emptyQueue(); i = const_dfs_test.queueSize(); - + dfs_test.start(); dfs_test.start(t); dfs_test.start(am); @@ -109,7 +109,7 @@ concepts::ReadWriteMap dist_map; concepts::ReadWriteMap reached_map; concepts::WriteMap processed_map; - + dfs_test .predMap(pred_map) .distMap(dist_map) @@ -126,7 +126,7 @@ e = dfs_test.nextArc(); b = dfs_test.emptyQueue(); i = dfs_test.queueSize(); - + dfs_test.start(); dfs_test.start(t); dfs_test.start(am); diff --git a/test/digraph_test.cc b/test/digraph_test.cc --- a/test/digraph_test.cc +++ b/test/digraph_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -392,9 +392,9 @@ SmartDigraph g; SmartDigraph::NodeMap nref(g); SmartDigraph::ArcMap aref(g); - + StaticDigraph G; - + checkGraphNodeList(G, 0); checkGraphArcList(G, 0); @@ -464,7 +464,7 @@ arcs.push_back(std::make_pair(4,1)); G.build(6, arcs.begin(), arcs.end()); - + checkGraphNodeList(G, 6); checkGraphArcList(G, 9); @@ -488,7 +488,7 @@ checkArcIds(G); checkGraphNodeMap(G); checkGraphArcMap(G); - + int n = G.nodeNum(); int m = G.arcNum(); check(G.index(G.node(n-1)) == n-1, "Wrong index."); diff --git a/test/dijkstra_test.cc b/test/dijkstra_test.cc --- a/test/dijkstra_test.cc +++ b/test/dijkstra_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -85,7 +85,7 @@ n = const_dijkstra_test.nextNode(); b = const_dijkstra_test.emptyQueue(); i = const_dijkstra_test.queueSize(); - + dijkstra_test.start(); dijkstra_test.start(t); dijkstra_test.start(nm); @@ -109,7 +109,7 @@ ::SetOperationTraits > ::SetHeap > > ::SetStandardHeap > > - ::SetHeap >, + ::SetHeap >, concepts::ReadWriteMap > ::Create dijkstra_test(G,length); @@ -119,7 +119,7 @@ concepts::WriteMap processed_map; concepts::ReadWriteMap heap_cross_ref; BinHeap > heap(heap_cross_ref); - + dijkstra_test .lengthMap(length_map) .predMap(pred_map) @@ -136,7 +136,7 @@ n = dijkstra_test.nextNode(); b = dijkstra_test.emptyQueue(); i = dijkstra_test.queueSize(); - + dijkstra_test.start(); dijkstra_test.start(t); dijkstra_test.start(nm); diff --git a/test/edge_set_test.cc b/test/edge_set_test.cc --- a/test/edge_set_test.cc +++ b/test/edge_set_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/test/euler_test.cc b/test/euler_test.cc --- a/test/euler_test.cc +++ b/test/euler_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -85,11 +85,11 @@ { typedef ListDigraph Digraph; typedef Undirector Graph; - + { Digraph d; Graph g(d); - + checkDiEulerIt(d); checkDiEulerIt(g); checkEulerIt(g); @@ -128,7 +128,7 @@ Digraph::Node n1 = d.addNode(); Digraph::Node n2 = d.addNode(); Digraph::Node n3 = d.addNode(); - + d.addArc(n1, n2); d.addArc(n2, n1); d.addArc(n2, n3); @@ -153,7 +153,7 @@ Digraph::Node n4 = d.addNode(); Digraph::Node n5 = d.addNode(); Digraph::Node n6 = d.addNode(); - + d.addArc(n1, n2); d.addArc(n2, n4); d.addArc(n1, n3); @@ -189,7 +189,7 @@ Digraph::Node n3 = d.addNode(); Digraph::Node n4 = d.addNode(); Digraph::Node n5 = d.addNode(); - + d.addArc(n1, n2); d.addArc(n2, n3); d.addArc(n3, n1); @@ -211,7 +211,7 @@ Digraph::Node n1 = d.addNode(); Digraph::Node n2 = d.addNode(); Digraph::Node n3 = d.addNode(); - + d.addArc(n1, n2); d.addArc(n2, n3); diff --git a/test/fractional_matching_test.cc b/test/fractional_matching_test.cc --- a/test/fractional_matching_test.cc +++ b/test/fractional_matching_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -238,7 +238,7 @@ for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { check((e == mfm.matching(graph.u(e)) ? 1 : 0) + - (e == mfm.matching(graph.v(e)) ? 1 : 0) == + (e == mfm.matching(graph.v(e)) ? 1 : 0) == mfm.matching(e), "Invalid matching"); } @@ -292,7 +292,7 @@ } for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { check((e == mfm.matching(graph.u(e)) ? 1 : 0) + - (e == mfm.matching(graph.v(e)) ? 1 : 0) == + (e == mfm.matching(graph.v(e)) ? 1 : 0) == mfm.matching(e), "Invalid matching"); } } else { @@ -350,7 +350,7 @@ for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { check((e == mwfm.matching(graph.u(e)) ? 1 : 0) + - (e == mwfm.matching(graph.v(e)) ? 1 : 0) == + (e == mwfm.matching(graph.v(e)) ? 1 : 0) == mwfm.matching(e), "Invalid matching"); } @@ -410,7 +410,7 @@ for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) + - (e == mwpfm.matching(graph.v(e)) ? 1 : 0) == + (e == mwpfm.matching(graph.v(e)) ? 1 : 0) == mwpfm.matching(e), "Invalid matching"); } diff --git a/test/gomory_hu_test.cc b/test/gomory_hu_test.cc --- a/test/gomory_hu_test.cc +++ b/test/gomory_hu_test.cc @@ -1,3 +1,21 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + #include #include "test_tools.h" @@ -33,7 +51,7 @@ "@attributes\n" "source 0\n" "target 3\n"; - + void checkGomoryHuCompile() { typedef int Value; @@ -69,7 +87,7 @@ typedef Graph::NodeMap BoolNodeMap; int cutValue(const Graph& graph, const BoolNodeMap& cut, - const IntEdgeMap& capacity) { + const IntEdgeMap& capacity) { int sum = 0; for (EdgeIt e(graph); e != INVALID; ++e) { @@ -107,7 +125,7 @@ int sum=0; for(GomoryHu::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) - sum+=capacity[a]; + sum+=capacity[a]; check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); sum=0; @@ -118,6 +136,6 @@ check(sum == countNodes(graph), "Problem with MinCutNodeIt"); } } - + return 0; } diff --git a/test/graph_test.cc b/test/graph_test.cc --- a/test/graph_test.cc +++ b/test/graph_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -264,7 +264,7 @@ checkGraphNodeList(G, 4); checkGraphEdgeList(G, 3); checkGraphArcList(G, 6); - + G.addEdge(G.addNode(), G.addNode()); snapshot.restore(); @@ -513,7 +513,7 @@ G.resize(dim); check(G.dimension() == dim, "Wrong dimension"); - + checkGraphNodeList(G, 1 << dim); checkGraphEdgeList(G, dim * (1 << (dim-1))); checkGraphArcList(G, dim * (1 << dim)); diff --git a/test/hao_orlin_test.cc b/test/hao_orlin_test.cc --- a/test/hao_orlin_test.cc +++ b/test/hao_orlin_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -83,7 +83,7 @@ } template -typename CapMap::Value +typename CapMap::Value cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) { typename CapMap::Value sum = 0; @@ -110,7 +110,7 @@ HaoOrlin ho(graph, cap1); ho.run(); ho.minCutMap(cut); - + check(ho.minCutValue() == 1, "Wrong cut value"); check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); } @@ -126,19 +126,19 @@ HaoOrlin ho(graph, cap3); ho.run(); ho.minCutMap(cut); - + check(ho.minCutValue() == 1, "Wrong cut value"); check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); } - + typedef Undirector UGraph; UGraph ugraph(graph); - + { HaoOrlin > ho(ugraph, cap1); ho.run(); ho.minCutMap(cut); - + check(ho.minCutValue() == 2, "Wrong cut value"); check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); } @@ -146,7 +146,7 @@ HaoOrlin > ho(ugraph, cap2); ho.run(); ho.minCutMap(cut); - + check(ho.minCutValue() == 5, "Wrong cut value"); check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); } @@ -154,7 +154,7 @@ HaoOrlin > ho(ugraph, cap3); ho.run(); ho.minCutMap(cut); - + check(ho.minCutValue() == 5, "Wrong cut value"); check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); } diff --git a/test/maps_test.cc b/test/maps_test.cc --- a/test/maps_test.cc +++ b/test/maps_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -225,7 +225,8 @@ B b = functorToMap(F())[A()]; checkConcept, MapToFunctor > >(); - MapToFunctor > map = MapToFunctor >(ReadMap()); + MapToFunctor > map = + MapToFunctor >(ReadMap()); check(functorToMap(&func)[A()] == 3, "Something is wrong with FunctorToMap"); @@ -377,7 +378,7 @@ for ( LoggerBoolMap::Iterator it = map2.begin(); it != map2.end(); ++it ) check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); - + typedef ListDigraph Graph; DIGRAPH_TYPEDEFS(Graph); Graph gr; @@ -386,13 +387,13 @@ Node n1 = gr.addNode(); Node n2 = gr.addNode(); Node n3 = gr.addNode(); - + gr.addArc(n3, n0); gr.addArc(n3, n2); gr.addArc(n0, n2); gr.addArc(n2, n1); gr.addArc(n0, n1); - + { std::vector v; dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run(); @@ -403,12 +404,12 @@ { std::vector v(countNodes(gr)); dfs(gr).processedMap(loggerBoolMap(v.begin())).run(); - + check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3, "Something is wrong with LoggerBoolMap"); } } - + // IdMap, RangeIdMap { typedef ListDigraph Graph; @@ -418,22 +419,22 @@ checkConcept, IdMap >(); checkConcept, RangeIdMap >(); checkConcept, RangeIdMap >(); - + Graph gr; IdMap nmap(gr); IdMap amap(gr); RangeIdMap nrmap(gr); RangeIdMap armap(gr); - + Node n0 = gr.addNode(); Node n1 = gr.addNode(); Node n2 = gr.addNode(); - + Arc a0 = gr.addArc(n0, n1); Arc a1 = gr.addArc(n0, n2); Arc a2 = gr.addArc(n2, n1); Arc a3 = gr.addArc(n2, n0); - + check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap"); check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap"); check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap"); @@ -445,14 +446,14 @@ check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap"); check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap"); - + check(nrmap.size() == 3 && armap.size() == 4, "Wrong RangeIdMap::size()"); check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap"); check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap"); check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap"); - + check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap"); check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap"); @@ -460,32 +461,32 @@ check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap"); check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap"); - + gr.erase(n1); - + if (nrmap[n0] == 1) nrmap.swap(n0, n2); nrmap.swap(n2, n0); if (armap[a1] == 1) armap.swap(a1, a3); armap.swap(a3, a1); - + check(nrmap.size() == 2 && armap.size() == 2, "Wrong RangeIdMap::size()"); check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap"); check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap"); - + check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap"); check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap"); check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap"); } - + // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap { typedef ListGraph Graph; GRAPH_TYPEDEFS(Graph); - + checkConcept, SourceMap >(); checkConcept, TargetMap >(); checkConcept, ForwardMap >(); @@ -497,19 +498,19 @@ Node n0 = gr.addNode(); Node n1 = gr.addNode(); Node n2 = gr.addNode(); - + gr.addEdge(n0,n1); gr.addEdge(n1,n2); gr.addEdge(n0,n2); gr.addEdge(n2,n1); gr.addEdge(n1,n2); gr.addEdge(n0,n1); - + for (EdgeIt e(gr); e != INVALID; ++e) { check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap"); check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap"); } - + check(mapCompare(gr, sourceMap(orienter(gr, constMap(true))), targetMap(orienter(gr, constMap(false)))), @@ -519,16 +520,16 @@ Digraph dgr(gr, constMap(true)); OutDegMap odm(dgr); InDegMap idm(dgr); - + check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap"); check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap"); - + gr.addEdge(n2, n0); check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap"); check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap"); } - + // CrossRefMap { typedef ListDigraph Graph; @@ -540,19 +541,19 @@ CrossRefMap >(); checkConcept, CrossRefMap >(); - + Graph gr; typedef CrossRefMap CRMap; CRMap map(gr); - + Node n0 = gr.addNode(); Node n1 = gr.addNode(); Node n2 = gr.addNode(); - + map.set(n0, 'A'); map.set(n1, 'B'); map.set(n2, 'C'); - + check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap"); check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1, @@ -561,11 +562,11 @@ "Wrong CrossRefMap"); check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1, "Wrong CrossRefMap::count()"); - + CRMap::ValueIt it = map.beginValue(); check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && it == map.endValue(), "Wrong value iterator"); - + map.set(n2, 'A'); check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A', @@ -603,16 +604,16 @@ checkConcept, CrossRefMap >(); - + Graph gr; typedef CrossRefMap CRMap; typedef CRMap::ValueIterator ValueIt; CRMap map(gr); - + Node n0 = gr.addNode(); Node n1 = gr.addNode(); Node n2 = gr.addNode(); - + map.set(n0, 'A'); map.set(n1, 'B'); map.set(n2, 'C'); @@ -629,7 +630,7 @@ check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && it == map.endValue(), "Wrong value iterator"); } - + // Iterable bool map { typedef SmartGraph Graph; @@ -817,7 +818,7 @@ check(n == num, "Wrong number"); } - + // Graph map utilities: // mapMin(), mapMax(), mapMinValue(), mapMaxValue() // mapFind(), mapFindIf(), mapCount(), mapCountIf() @@ -829,16 +830,16 @@ Node n1 = g.addNode(); Node n2 = g.addNode(); Node n3 = g.addNode(); - + SmartDigraph::NodeMap map1(g); SmartDigraph::ArcMap map2(g); ConstMap cmap1 = A(); ConstMap cmap2 = C(0); - + map1[n1] = 10; map1[n2] = 5; map1[n3] = 12; - + // mapMin(), mapMax(), mapMinValue(), mapMaxValue() check(mapMin(g, map1) == n2, "Wrong mapMin()"); check(mapMax(g, map1) == n3, "Wrong mapMax()"); @@ -857,7 +858,7 @@ Arc a2 = g.addArc(n1, n3); Arc a3 = g.addArc(n2, n3); Arc a4 = g.addArc(n3, n1); - + map2[a1] = 'b'; map2[a2] = 'a'; map2[a3] = 'b'; @@ -924,7 +925,7 @@ "Wrong mapCountIf()"); check(mapCountIf(g, map2, Less('a')) == 0, "Wrong mapCountIf()"); - + // MapIt, ConstMapIt /* These tests can be used after applying bugfix #330 @@ -934,7 +935,7 @@ "Wrong NodeMap<>::MapIt"); check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12, "Wrong NodeMap<>::MapIt"); - + int sum = 0; std::for_each(MapIt(map1), MapIt(INVALID), Sum(sum)); check(sum == 27, "Wrong NodeMap<>::MapIt"); @@ -951,41 +952,41 @@ SmartDigraph::NodeMap map3(g, 0); SmartDigraph::ArcMap map4(g, 'a'); - + check(!mapCompare(g, map1, map3), "Wrong mapCompare()"); - check(!mapCompare(g, map2, map4), "Wrong mapCompare()"); - + check(!mapCompare(g, map2, map4), "Wrong mapCompare()"); + mapCopy(g, map1, map3); mapCopy(g, map2, map4); check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()"); - check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()"); - + check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()"); + Undirector ug(g); Undirector::EdgeMap umap1(ug, 'x'); Undirector::ArcMap umap2(ug, 3.14); - + check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()"); check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()"); check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()"); check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()"); - + mapCopy(g, map2, umap1); check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()"); check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()"); check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()"); check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()"); - + mapCopy(g, map2, umap1); mapCopy(g, umap1, map2); mapCopy(ug, map2, umap1); mapCopy(ug, umap1, map2); - + check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()"); mapCopy(ug, umap1, umap2); check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()"); - + check(!mapCompare(g, map1, constMap(2)), "Wrong mapCompare()"); mapFill(g, map1, 2); check(mapCompare(g, constMap(2), map1), "Wrong mapFill()"); @@ -994,6 +995,6 @@ mapCopy(g, constMap('z'), map2); check(mapCompare(g, constMap('z'), map2), "Wrong mapCopy()"); } - + return 0; } diff --git a/test/matching_test.cc b/test/matching_test.cc --- a/test/matching_test.cc +++ b/test/matching_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -134,7 +134,7 @@ mat_test.startSparse(); mat_test.startDense(); mat_test.run(); - + const_mat_test.matchingSize(); const_mat_test.matching(e); const_mat_test.matching(n); @@ -143,7 +143,7 @@ e = mmap[n]; const_mat_test.mate(n); - MaxMatching::Status stat = + MaxMatching::Status stat = const_mat_test.status(n); const MaxMatching::StatusMap& smap = const_mat_test.statusMap(); @@ -170,7 +170,7 @@ mat_test.init(); mat_test.start(); mat_test.run(); - + const_mat_test.matchingWeight(); const_mat_test.matchingSize(); const_mat_test.matching(e); @@ -179,7 +179,7 @@ const_mat_test.matchingMap(); e = mmap[n]; const_mat_test.mate(n); - + int k = 0; const_mat_test.dualValue(); const_mat_test.nodeValue(n); @@ -207,7 +207,7 @@ mat_test.init(); mat_test.start(); mat_test.run(); - + const_mat_test.matchingWeight(); const_mat_test.matching(e); const_mat_test.matching(n); @@ -215,7 +215,7 @@ const_mat_test.matchingMap(); e = mmap[n]; const_mat_test.mate(n); - + int k = 0; const_mat_test.dualValue(); const_mat_test.nodeValue(n); @@ -425,7 +425,7 @@ { MaxWeightedPerfectMatching mwpm(graph, weight); bool result = mwpm.run(); - + check(result == perfect, "Perfect matching found"); if (perfect) { checkWeightedPerfectMatching(graph, weight, mwpm); @@ -436,7 +436,7 @@ MaxWeightedPerfectMatching mwpm(graph, weight); mwpm.init(); bool result = mwpm.start(); - + check(result == perfect, "Perfect matching found"); if (perfect) { checkWeightedPerfectMatching(graph, weight, mwpm); diff --git a/test/min_cost_arborescence_test.cc b/test/min_cost_arborescence_test.cc --- a/test/min_cost_arborescence_test.cc +++ b/test/min_cost_arborescence_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -110,7 +110,7 @@ n = mcarb_test.processNextNode(); b = const_mcarb_test.emptyQueue(); i = const_mcarb_test.queueSize(); - + c = const_mcarb_test.arborescenceCost(); b = const_mcarb_test.arborescence(e); e = const_mcarb_test.pred(n); @@ -120,12 +120,12 @@ const_mcarb_test.predMap(); b = const_mcarb_test.reached(n); b = const_mcarb_test.processed(n); - + i = const_mcarb_test.dualNum(); c = const_mcarb_test.dualValue(); i = const_mcarb_test.dualSize(i); c = const_mcarb_test.dualValue(i); - + ignore_unused_variable_warning(am); ignore_unused_variable_warning(pm); } diff --git a/test/min_cost_flow_test.cc b/test/min_cost_flow_test.cc --- a/test/min_cost_flow_test.cc +++ b/test/min_cost_flow_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -52,7 +52,7 @@ " 10 -2 0 0 0 -7 -2\n" " 11 0 0 0 0 -10 0\n" " 12 -20 -27 0 -30 -30 -20\n" - "\n" + "\n" "@arcs\n" " cost cap low1 low2 low3\n" " 1 2 70 11 0 8 8\n" @@ -102,7 +102,7 @@ "5 6 80 0 1000\n" "6 7 30 0 -1000\n" "7 5 -120 0 0\n"; - + char test_neg2_lgf[] = "@nodes\n" "label sup\n" @@ -151,7 +151,7 @@ struct Constraints { void constraints() { checkConcept(); - + const Constraints& me = *this; MCF mcf(me.g); @@ -180,7 +180,7 @@ typedef concepts::ReadMap CAM; typedef concepts::WriteMap FlowMap; typedef concepts::WriteMap PotMap; - + GR g; VAM lower; VAM upper; @@ -234,7 +234,7 @@ template < typename GR, typename LM, typename UM, typename CM, typename SM, typename FM, typename PM > bool checkPotential( const GR& gr, const LM& lower, const UM& upper, - const CM& cost, const SM& supply, const FM& flow, + const CM& cost, const SM& supply, const FM& flow, const PM& pi, SupplyType type ) { TEMPLATE_DIGRAPH_TYPEDEFS(GR); @@ -247,7 +247,7 @@ (red_cost > 0 && flow[e] == lower[e]) || (red_cost < 0 && flow[e] == upper[e]); } - + for (NodeIt n(gr); opt && n != INVALID; ++n) { typename SM::Value sum = 0; for (OutArcIt e(gr, n); e != INVALID; ++e) @@ -260,7 +260,7 @@ opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0); } } - + return opt; } @@ -285,7 +285,7 @@ red_supply[gr.target(a)] += lower[a]; } } - + for (NodeIt n(gr); n != INVALID; ++n) { dual_cost -= red_supply[n] * pi[n]; } @@ -294,7 +294,7 @@ cost[a] + pi[gr.source(a)] - pi[gr.target(a)]; dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0); } - + return dual_cost == total; } @@ -332,7 +332,7 @@ bool full_neg_cost_support = false ) { MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr); - + // Basic tests mcf1.upperMap(u).costMap(c).supplyMap(s1); checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1, @@ -435,7 +435,7 @@ .node("source", v) .node("target", w) .run(); - + std::istringstream neg_inp1(test_neg1_lgf); DigraphReader(neg1_gr, neg_inp1) .arcMap("cost", neg1_c) @@ -443,13 +443,13 @@ .arcMap("low2", neg1_l2) .nodeMap("sup", neg1_s) .run(); - + std::istringstream neg_inp2(test_neg2_lgf); DigraphReader(neg2_gr, neg_inp2) .arcMap("cost", neg2_c) .nodeMap("sup", neg2_s) .run(); - + // Check the interface of NetworkSimplex { typedef concepts::Digraph GR; @@ -501,7 +501,7 @@ } // Test NetworkSimplex - { + { typedef NetworkSimplex MCF; runMcfGeqTests(MCF::FIRST_ELIGIBLE, "NS-FE", true); runMcfLeqTests(MCF::FIRST_ELIGIBLE, "NS-FE"); @@ -514,7 +514,7 @@ runMcfGeqTests(MCF::ALTERING_LIST, "NS-AL", true); runMcfLeqTests(MCF::ALTERING_LIST, "NS-AL"); } - + // Test CapacityScaling { typedef CapacityScaling MCF; diff --git a/test/min_mean_cycle_test.cc b/test/min_mean_cycle_test.cc --- a/test/min_mean_cycle_test.cc +++ b/test/min_mean_cycle_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -61,7 +61,7 @@ "6 7 1 1 1 1 0 0 0 0\n" "7 7 4 4 4 -1 0 0 0 1\n"; - + // Check the interface of an MMC algorithm template struct MmcClassConcept @@ -77,10 +77,10 @@ ::Create MmcAlg; MmcAlg mmc(me.g, me.cost); const MmcAlg& const_mmc = mmc; - + typename MmcAlg::Tolerance tol = const_mmc.tolerance(); mmc.tolerance(tol); - + b = mmc.cycle(p).run(); b = mmc.findCycleMean(); b = mmc.findCycle(); @@ -92,7 +92,7 @@ } typedef concepts::ReadMap CM; - + GR g; CM cost; ListPath p; @@ -153,13 +153,13 @@ KarpMmc > >(); checkConcept< MmcClassConcept, KarpMmc > >(); - + // HartmannOrlinMmc checkConcept< MmcClassConcept, HartmannOrlinMmc > >(); checkConcept< MmcClassConcept, HartmannOrlinMmc > >(); - + // HowardMmc checkConcept< MmcClassConcept, HowardMmc > >(); @@ -176,11 +176,11 @@ { typedef SmartDigraph GR; DIGRAPH_TYPEDEFS(GR); - + GR gr; IntArcMap l1(gr), l2(gr), l3(gr), l4(gr); IntArcMap c1(gr), c2(gr), c3(gr), c4(gr); - + std::istringstream input(test_lgf); digraphReader(gr, input). arcMap("len1", l1). diff --git a/test/preflow_test.cc b/test/preflow_test.cc --- a/test/preflow_test.cc +++ b/test/preflow_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -94,7 +94,7 @@ ::Create PreflowType; PreflowType preflow_test(g, cap, n, n); const PreflowType& const_preflow_test = preflow_test; - + const PreflowType::Elevator& elev = const_preflow_test.elevator(); preflow_test.elevator(const_cast(elev)); PreflowType::Tolerance tol = const_preflow_test.tolerance(); @@ -118,7 +118,7 @@ const FlowMap& fm = const_preflow_test.flowMap(); b = const_preflow_test.minCut(n); const_preflow_test.minCutMap(cut); - + ignore_unused_variable_warning(fm); } diff --git a/test/suurballe_test.cc b/test/suurballe_test.cc --- a/test/suurballe_test.cc +++ b/test/suurballe_test.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -81,7 +81,7 @@ typedef Digraph::Node Node; typedef Digraph::Arc Arc; typedef concepts::ReadMap LengthMap; - + typedef Suurballe ST; typedef Suurballe ::SetFlowMap @@ -114,7 +114,7 @@ k = suurb_test.findFlow(n); k = suurb_test.findFlow(n, k); suurb_test.findPaths(); - + int f; VType c; c = const_suurb_test.totalLength(); @@ -126,7 +126,7 @@ const_suurb_test.potentialMap(); k = const_suurb_test.pathNum(); Path p = const_suurb_test.path(k); - + ignore_unused_variable_warning(fm); ignore_unused_variable_warning(pm); } @@ -208,7 +208,7 @@ // Check run() { Suurballe suurballe(digraph, length); - + // Find 2 paths check(suurballe.run(s, t) == 2, "Wrong number of paths"); check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), @@ -219,7 +219,7 @@ "Wrong potentials"); for (int i = 0; i < suurballe.pathNum(); ++i) check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); - + // Find 3 paths check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), @@ -230,7 +230,7 @@ "Wrong potentials"); for (int i = 0; i < suurballe.pathNum(); ++i) check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); - + // Find 5 paths (only 3 can be found) check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), @@ -242,12 +242,12 @@ for (int i = 0; i < suurballe.pathNum(); ++i) check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); } - + // Check fullInit() + start() { Suurballe suurballe(digraph, length); suurballe.fullInit(s); - + // Find 2 paths check(suurballe.start(t) == 2, "Wrong number of paths"); check(suurballe.totalLength() == 510, "The flow is not optimal"); diff --git a/test/test_tools.h b/test/test_tools.h --- a/test/test_tools.h +++ b/test/test_tools.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -45,6 +45,6 @@ abort(); \ } else { } \ } \ - + #endif diff --git a/tools/dimacs-solver.cc b/tools/dimacs-solver.cc --- a/tools/dimacs-solver.cc +++ b/tools/dimacs-solver.cc @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -88,7 +88,7 @@ ti.restart(); pre.run(); if(report) std::cerr << "Run Preflow: " << ti << '\n'; - if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; + if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; } template @@ -148,7 +148,7 @@ mat.run(); if(report) std::cerr << "Run MaxMatching: " << ti << '\n'; if(report) std::cerr << "\nCardinality of max matching: " - << mat.matchingSize() << '\n'; + << mat.matchingSize() << '\n'; } @@ -166,7 +166,7 @@ << std::endl; exit(1); } - + switch(desc.type) { case DimacsDescriptor::MIN: @@ -238,7 +238,7 @@ std::ostream& os = (ap.files().size()<2 ? std::cout : output); DimacsDescriptor desc = dimacsType(is); - + if(!ap.given("q")) { std::cout << "Problem type: "; @@ -263,7 +263,7 @@ std::cout << "\nNum of arcs: " << desc.edgeNum; std::cout << "\n\n"; } - + if(ap.given("double")) solve(ap,is,os,desc); else if(ap.given("ldouble"))