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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -275,7 +275,7 @@ This group contains the algorithms for finding shortest paths in digraphs. - - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a + - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a source node when all arc lengths are non-negative. - \ref Suurballe A successive shortest path algorithm for finding arc-disjoint paths between two nodes having minimum total length. @@ -306,7 +306,7 @@ minimum cut, which is the dual problem of maximum flow. -\ref Circulation is a preflow push-relabel algorithm implemented directly +\ref Circulation is a preflow push-relabel algorithm implemented directly for finding feasible circulations, which is a somewhat different problem, but it is strongly related to maximum flow. For more information, see \ref Circulation. diff --git a/doc/lgf.dox b/doc/lgf.dox --- a/doc/lgf.dox +++ b/doc/lgf.dox @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -81,7 +81,7 @@ - \f$\pi(u)<=0\f$; - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, then \f$\pi(u)=0\f$. - + Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f] @@ -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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -418,7 +418,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: @@ -505,11 +505,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; @@ -532,9 +532,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; @@ -579,7 +579,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: @@ -648,10 +648,10 @@ } template - class NodeMap + class NodeMap : public SubMapExtender, LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent; public: @@ -675,7 +675,7 @@ }; template - class ArcMap + class ArcMap : public SubMapExtender, LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> { typedef SubMapExtender, @@ -1016,10 +1016,10 @@ } template - class NodeMap + class NodeMap : public SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent; public: @@ -1043,10 +1043,10 @@ }; template - class ArcMap + class ArcMap : public SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent; public: @@ -1070,10 +1070,10 @@ }; template - class EdgeMap + class EdgeMap : public SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent; public: @@ -1112,8 +1112,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); @@ -1214,10 +1214,10 @@ } template - class NodeMap + class NodeMap : public SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent; public: @@ -1241,10 +1241,10 @@ }; template - class ArcMap + class ArcMap : public SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> { - typedef SubMapExtender, + typedef SubMapExtender, LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent; public: @@ -1268,11 +1268,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; @@ -1495,7 +1495,7 @@ true> > { #endif typedef DigraphAdaptorExtender< - SubDigraphBase >, + SubDigraphBase >, true> > Parent; public: @@ -1516,7 +1516,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); @@ -1554,11 +1554,11 @@ class FilterNodes >::type> : public GraphAdaptorExtender< - SubGraphBase >, + SubGraphBase >, true> > { typedef GraphAdaptorExtender< - SubGraphBase >, + SubGraphBase >, true> > Parent; public: @@ -1642,7 +1642,7 @@ AF, false> > { #endif typedef DigraphAdaptorExtender< - SubDigraphBase >, + SubDigraphBase >, AF, false> > Parent; public: @@ -1748,11 +1748,11 @@ typename EF = typename GR::template EdgeMap > class FilterEdges : public GraphAdaptorExtender< - SubGraphBase >, + SubGraphBase >, EF, false> > { #endif typedef GraphAdaptorExtender< - SubGraphBase >, + SubGraphBase >, EF, false> > Parent; public: @@ -1777,7 +1777,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); } @@ -1845,7 +1845,7 @@ Edge _edge; bool _forward; - Arc(const Edge& edge, bool forward) + Arc(const Edge& edge, bool forward) : _edge(edge), _forward(forward) {} public: @@ -2085,7 +2085,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) { @@ -2203,7 +2203,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()); } @@ -2707,7 +2707,7 @@ typename CM = typename DGR::template ArcMap, typename FM = CM, typename TL = Tolerance > - class ResidualDigraph + class ResidualDigraph : public SubDigraph< Undirector, ConstMap >, @@ -2764,7 +2764,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), @@ -2846,7 +2846,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 @@ -3423,7 +3423,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/bin_heap.h b/lemon/bin_heap.h --- a/lemon/bin_heap.h +++ b/lemon/bin_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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * 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-2011 * 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-2011 * 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-2011 * 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(); @@ -312,11 +312,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 { @@ -340,7 +340,7 @@ public: using Parent::notifier; - + ArcNotifier& notifier(Arc) const { return arc_notifier; } @@ -350,7 +350,7 @@ } - class NodeIt : public Node { + class NodeIt : public Node { const Graph* graph; public: @@ -359,21 +359,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: @@ -382,21 +382,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: @@ -404,23 +404,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: @@ -428,23 +428,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: @@ -453,15 +453,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; } }; @@ -477,17 +477,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; } }; @@ -534,49 +534,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; } }; @@ -593,7 +593,7 @@ notifier(Arc()).add(arcs); return edge; } - + void clear() { notifier(Arc()).clear(); notifier(Edge()).clear(); @@ -619,7 +619,7 @@ edge_notifier.clear(); arc_notifier.clear(); } - + }; } diff --git a/lemon/bits/graph_adaptor_extender.h b/lemon/bits/graph_adaptor_extender.h --- a/lemon/bits/graph_adaptor_extender.h +++ b/lemon/bits/graph_adaptor_extender.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/lemon/bits/map_extender.h b/lemon/bits/map_extender.h --- a/lemon/bits/map_extender.h +++ b/lemon/bits/map_extender.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/lemon/bits/path_dump.h b/lemon/bits/path_dump.h --- a/lemon/bits/path_dump.h +++ b/lemon/bits/path_dump.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * 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-2011 * 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -98,7 +98,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/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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -120,7 +120,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-2011 * 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; @@ -134,7 +134,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). @@ -144,7 +144,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), @@ -325,7 +325,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-2011 * 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -137,7 +137,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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -435,7 +435,7 @@ private: ///Copy constructor - NodeMap(const NodeMap& nm) : + NodeMap(const NodeMap& nm) : ReferenceMap(nm) { } ///Assignment operator template 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-2011 * 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 have 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/maps.h b/lemon/concepts/maps.h --- a/lemon/concepts/maps.h +++ b/lemon/concepts/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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * 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-2011 * 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -1241,7 +1241,8 @@ protected: - class AutoNodeMap : public ItemSetTraits::template Map::Type { + class AutoNodeMap : + public ItemSetTraits::template Map::Type { typedef typename ItemSetTraits::template Map::Type Parent; public: @@ -1280,7 +1281,7 @@ } }; - protected: + protected: const Digraph &_g; AutoNodeMap _head; 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -456,7 +456,7 @@ } void CplexBase::_applyMessageLevel() { - CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, + CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, _message_enabled ? CPX_ON : CPX_OFF); } 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-2011 * 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-2011 * 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-2011 * 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-2011 * 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/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-2011 * 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; } @@ -123,13 +123,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-2011 * 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; } @@ -294,33 +294,33 @@ /// /// \pre \ref run() must be called before using this function. template - Value minCutMap(const Node& s, ///< + Value minCutMap(const Node& s, ///< const Node& t, - ///< + ///< CutMap& cutMap - ///< + ///< ) const { Node sn = s, tn = t; bool s_root=false; Node rn = INVALID; Value value = std::numeric_limits::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); @@ -331,18 +331,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; } @@ -351,7 +351,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. @@ -444,11 +444,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. @@ -481,7 +481,7 @@ _arc_it=typename Graph::OutArcIt(_graph,_node_it); } } - + public: /// Constructor @@ -550,7 +550,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-2011 * 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-2011 * 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 @@ -847,7 +847,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) { @@ -927,7 +927,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) { @@ -941,7 +941,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. /// @{ @@ -950,7 +950,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; @@ -969,7 +969,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/lgf_reader.h b/lemon/lgf_reader.h --- a/lemon/lgf_reader.h +++ b/lemon/lgf_reader.h @@ -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); @@ -1194,14 +1194,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 @@ -1256,7 +1256,7 @@ template class GraphReader; - + template GraphReader graphReader(TGR& graph, std::istream& is = std::cin); template @@ -1393,7 +1393,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); @@ -2077,9 +2077,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-2011 * 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/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-2011 * 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-2011 * 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-2011 * 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; } @@ -1803,10 +1803,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, @@ -1885,7 +1885,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 @@ -1919,7 +1919,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 @@ -2061,7 +2061,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-2011 * 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-2011 * 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -1818,7 +1818,7 @@ /// \brief Provides an immutable and unique id for each item in a graph. /// /// IdMap provides a unique and immutable id for each item of the - /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is + /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is /// - \b unique: different items get different ids, /// - \b immutable: the id of an item does not change (even if you /// delete other nodes). @@ -2273,7 +2273,7 @@ } /// \brief Gives back the item belonging to a \e RangeId - /// + /// /// Gives back the item belonging to a \e RangeId. Item operator()(int id) const { return _inv_map[id]; @@ -2499,7 +2499,7 @@ /// in constant time. On the other hand, the values are updated automatically /// whenever the digraph changes. /// - /// \warning Besides \c addNode() and \c addArc(), a digraph structure + /// \warning Besides \c addNode() and \c addArc(), a digraph structure /// may provide alternative ways to modify the digraph. /// The correct behavior of InDegMap is not guarantied if these additional /// features are used. For example the functions @@ -2515,7 +2515,7 @@ ::ItemNotifier::ObserverBase { public: - + /// The graph type of InDegMap typedef GR Graph; typedef GR Digraph; @@ -2629,7 +2629,7 @@ /// in constant time. On the other hand, the values are updated automatically /// whenever the digraph changes. /// - /// \warning Besides \c addNode() and \c addArc(), a digraph structure + /// \warning Besides \c addNode() and \c addArc(), a digraph structure /// may provide alternative ways to modify the digraph. /// The correct behavior of OutDegMap is not guarantied if these additional /// features are used. For example the functions 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -41,7 +41,7 @@ /// /// This class implements Edmonds' alternating forest matching algorithm /// for finding a maximum cardinality matching in a general undirected graph. - /// It can be started from an arbitrary initial matching + /// It can be started from an arbitrary initial matching /// (the default is the empty one). /// /// The dual solution of the problem is a map of the nodes to @@ -69,11 +69,11 @@ ///\brief Status constants for Gallai-Edmonds decomposition. /// - ///These constants are used for indicating the Gallai-Edmonds + ///These constants are used for indicating the Gallai-Edmonds ///decomposition of a graph. The nodes with status \c EVEN (or \c D) ///induce a subgraph with factor-critical components, the nodes with ///status \c ODD (or \c A) form the canonical barrier, and the nodes - ///with status \c MATCHED (or \c C) induce a subgraph having a + ///with status \c MATCHED (or \c C) induce a subgraph having a ///perfect matching. enum Status { EVEN = 1, ///< = 1. (\c D is an alias for \c EVEN.) @@ -512,7 +512,7 @@ } } - /// \brief Start Edmonds' algorithm with a heuristic improvement + /// \brief Start Edmonds' algorithm with a heuristic improvement /// for dense graphs /// /// This function runs Edmonds' algorithm with a heuristic of postponing @@ -534,8 +534,8 @@ /// \brief Run Edmonds' algorithm /// - /// This function runs Edmonds' algorithm. An additional heuristic of - /// postponing shrinks is used for relatively dense graphs + /// This function runs Edmonds' algorithm. An additional heuristic of + /// postponing shrinks is used for relatively dense graphs /// (for which m>=2*n holds). void run() { if (countEdges(_graph) < 2 * countNodes(_graph)) { @@ -556,7 +556,7 @@ /// \brief Return the size (cardinality) of the matching. /// - /// This function returns the size (cardinality) of the current matching. + /// This function returns the size (cardinality) of the current matching. /// After run() it returns the size of the maximum matching in the graph. int matchingSize() const { int size = 0; @@ -570,7 +570,7 @@ /// \brief Return \c true if the given edge is in the matching. /// - /// This function returns \c true if the given edge is in the current + /// This function returns \c true if the given edge is in the current /// matching. bool matching(const Edge& edge) const { return edge == (*_matching)[_graph.u(edge)]; @@ -579,7 +579,7 @@ /// \brief Return the matching arc (or edge) incident to the given node. /// /// This function returns the matching arc (or edge) incident to the - /// given node in the current matching or \c INVALID if the node is + /// given node in the current matching or \c INVALID if the node is /// not covered by the matching. Arc matching(const Node& n) const { return (*_matching)[n]; @@ -595,7 +595,7 @@ /// \brief Return the mate of the given node. /// - /// This function returns the mate of the given node in the current + /// This function returns the mate of the given node in the current /// matching or \c INVALID if the node is not covered by the matching. Node mate(const Node& n) const { return (*_matching)[n] != INVALID ? @@ -605,7 +605,7 @@ /// @} /// \name Dual Solution - /// Functions to get the dual solution, i.e. the Gallai-Edmonds + /// Functions to get the dual solution, i.e. the Gallai-Edmonds /// decomposition. /// @{ @@ -648,8 +648,8 @@ /// on extensive use of priority queues and provides /// \f$O(nm\log n)\f$ time complexity. /// - /// The maximum weighted matching problem is to find a subset of the - /// edges in an undirected graph with maximum overall weight for which + /// The maximum weighted matching problem is to find a subset of the + /// edges in an undirected graph with maximum overall weight for which /// each node has at most one incident edge. /// It can be formulated with the following linear program. /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f] @@ -673,16 +673,16 @@ /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}} \frac{\vert B \vert - 1}{2}z_B\f] */ /// - /// The algorithm can be executed with the run() function. + /// The algorithm can be executed with the run() function. /// After it the matching (the primal solution) and the dual solution - /// can be obtained using the query functions and the - /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, - /// which is able to iterate on the nodes of a blossom. + /// can be obtained using the query functions and the + /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, + /// which is able to iterate on the nodes of a blossom. /// If the value type is integer, then the dual solution is multiplied /// by \ref MaxWeightedMatching::dualScale "4". /// /// \tparam GR The undirected graph type the algorithm runs on. - /// \tparam WM The type edge weight map. The default type is + /// \tparam WM The type edge weight map. The default type is /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". #ifdef DOXYGEN template @@ -1720,7 +1720,7 @@ (*_delta2_index)[i] = _delta2->PRE_HEAP; (*_delta4_index)[i] = _delta4->PRE_HEAP; } - + _delta1->clear(); _delta2->clear(); _delta3->clear(); @@ -1868,7 +1868,7 @@ /// @} /// \name Primal Solution - /// Functions to get the primal solution, i.e. the maximum weighted + /// Functions to get the primal solution, i.e. the maximum weighted /// matching.\n /// Either \ref run() or \ref start() function should be called before /// using them. @@ -1907,7 +1907,7 @@ /// \brief Return \c true if the given edge is in the matching. /// - /// This function returns \c true if the given edge is in the found + /// This function returns \c true if the given edge is in the found /// matching. /// /// \pre Either run() or start() must be called before using this function. @@ -1918,7 +1918,7 @@ /// \brief Return the matching arc (or edge) incident to the given node. /// /// This function returns the matching arc (or edge) incident to the - /// given node in the found matching or \c INVALID if the node is + /// given node in the found matching or \c INVALID if the node is /// not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. @@ -1936,7 +1936,7 @@ /// \brief Return the mate of the given node. /// - /// This function returns the mate of the given node in the found + /// This function returns the mate of the given node in the found /// matching or \c INVALID if the node is not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. @@ -1956,8 +1956,8 @@ /// \brief Return the value of the dual solution. /// - /// This function returns the value of the dual solution. - /// It should be equal to the primal value scaled by \ref dualScale + /// This function returns the value of the dual solution. + /// It should be equal to the primal value scaled by \ref dualScale /// "dual scale". /// /// \pre Either run() or start() must be called before using this function. @@ -2012,9 +2012,9 @@ /// \brief Iterator for obtaining the nodes of a blossom. /// - /// This class provides an iterator for obtaining the nodes of the + /// This class provides an iterator for obtaining the nodes of the /// given blossom. It lists a subset of the nodes. - /// Before using this iterator, you must allocate a + /// Before using this iterator, you must allocate a /// MaxWeightedMatching class and execute it. class BlossomIt { public: @@ -2023,8 +2023,8 @@ /// /// Constructor to get the nodes of the given variable. /// - /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or - /// \ref MaxWeightedMatching::start() "algorithm.start()" must be + /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or + /// \ref MaxWeightedMatching::start() "algorithm.start()" must be /// called before initializing this iterator. BlossomIt(const MaxWeightedMatching& algorithm, int variable) : _algorithm(&algorithm) @@ -2077,8 +2077,8 @@ /// is based on extensive use of priority queues and provides /// \f$O(nm\log n)\f$ time complexity. /// - /// The maximum weighted perfect matching problem is to find a subset of - /// the edges in an undirected graph with maximum overall weight for which + /// The maximum weighted perfect matching problem is to find a subset of + /// the edges in an undirected graph with maximum overall weight for which /// each node has exactly one incident edge. /// It can be formulated with the following linear program. /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f] @@ -2101,16 +2101,16 @@ /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}} \frac{\vert B \vert - 1}{2}z_B\f] */ /// - /// The algorithm can be executed with the run() function. + /// The algorithm can be executed with the run() function. /// After it the matching (the primal solution) and the dual solution - /// can be obtained using the query functions and the - /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, - /// which is able to iterate on the nodes of a blossom. + /// can be obtained using the query functions and the + /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, + /// which is able to iterate on the nodes of a blossom. /// If the value type is integer, then the dual solution is multiplied /// by \ref MaxWeightedMatching::dualScale "4". /// /// \tparam GR The undirected graph type the algorithm runs on. - /// \tparam WM The type edge weight map. The default type is + /// \tparam WM The type edge weight map. The default type is /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". #ifdef DOXYGEN template @@ -3115,7 +3115,7 @@ /// @} /// \name Primal Solution - /// Functions to get the primal solution, i.e. the maximum weighted + /// Functions to get the primal solution, i.e. the maximum weighted /// perfect matching.\n /// Either \ref run() or \ref start() function should be called before /// using them. @@ -3139,7 +3139,7 @@ /// \brief Return \c true if the given edge is in the matching. /// - /// This function returns \c true if the given edge is in the found + /// This function returns \c true if the given edge is in the found /// matching. /// /// \pre Either run() or start() must be called before using this function. @@ -3150,7 +3150,7 @@ /// \brief Return the matching arc (or edge) incident to the given node. /// /// This function returns the matching arc (or edge) incident to the - /// given node in the found matching or \c INVALID if the node is + /// given node in the found matching or \c INVALID if the node is /// not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. @@ -3168,7 +3168,7 @@ /// \brief Return the mate of the given node. /// - /// This function returns the mate of the given node in the found + /// This function returns the mate of the given node in the found /// matching or \c INVALID if the node is not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. @@ -3187,8 +3187,8 @@ /// \brief Return the value of the dual solution. /// - /// This function returns the value of the dual solution. - /// It should be equal to the primal value scaled by \ref dualScale + /// This function returns the value of the dual solution. + /// It should be equal to the primal value scaled by \ref dualScale /// "dual scale". /// /// \pre Either run() or start() must be called before using this function. @@ -3243,9 +3243,9 @@ /// \brief Iterator for obtaining the nodes of a blossom. /// - /// This class provides an iterator for obtaining the nodes of the + /// This class provides an iterator for obtaining the nodes of the /// given blossom. It lists a subset of the nodes. - /// Before using this iterator, you must allocate a + /// Before using this iterator, you must allocate a /// MaxWeightedPerfectMatching class and execute it. class BlossomIt { public: @@ -3254,8 +3254,8 @@ /// /// Constructor to get the nodes of the given variable. /// - /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" - /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" + /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" + /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" /// must be called before initializing this iterator. BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable) : _algorithm(&algorithm) 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-2011 * 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -127,8 +127,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; @@ -435,7 +435,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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -95,7 +95,7 @@ /// infinite upper bound. UNBOUNDED }; - + /// \brief Constants for selecting the type of the supply constraints. /// /// Enum type containing constants for selecting the supply type, @@ -113,7 +113,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 @@ -156,7 +156,7 @@ /// candidate list and extends this list in every iteration. ALTERING_LIST }; - + private: TEMPLATE_DIGRAPH_TYPEDEFS(GR); @@ -223,7 +223,7 @@ Value delta; public: - + /// \brief Constant for infinite upper bounds (capacities). /// /// Constant for infinite upper bounds (capacities). @@ -644,7 +644,7 @@ "The flow type of NetworkSimplex must be signed"); LEMON_ASSERT(std::numeric_limits::is_signed, "The cost type of NetworkSimplex must be signed"); - + // Resize vectors _node_num = countNodes(_graph); _arc_num = countArcs(_graph); @@ -684,7 +684,7 @@ _target[i] = _node_id[_graph.target(a)]; if ((i += k) >= _arc_num) i = (i % k) + 1; } - + // Initialize maps for (int i = 0; i != _node_num; ++i) { _supply[i] = 0; @@ -809,7 +809,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. @@ -835,7 +835,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 @@ -1054,7 +1054,7 @@ _flow[i] = 0; _state[i] = STATE_LOWER; } - + // Set data for the artificial root node _root = _node_num; _parent[_root] = -1; @@ -1228,7 +1228,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] == INF ? INF : _cap[e] - _flow[e]) : _flow[e]; if (d <= delta) { delta = d; @@ -1435,7 +1435,7 @@ updatePotential(); } } - + // Check feasibility for (int e = _search_arc_num; e != _all_arc_num; ++e) { if (_flow[e] != 0) return INFEASIBLE; @@ -1452,7 +1452,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-2011 * 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/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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -536,10 +536,10 @@ (*_excess)[v] += rem; } } - for (NodeIt n(_graph); n != INVALID; ++n) + for (NodeIt n(_graph); n != INVALID; ++n) if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n])) _level->activate(n); - + return true; } @@ -567,7 +567,7 @@ if (n == INVALID) goto first_phase_done; level = _level->highestActiveLevel(); --num; - + Value excess = (*_excess)[n]; int new_level = _level->maxLevel(); 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -274,7 +274,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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * 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-2011 * 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -81,7 +81,7 @@ ::Create CirculationType; CirculationType circ_test(g, lcap, ucap, supply); const CirculationType& const_circ_test = circ_test; - + circ_test .lowerMap(lcap) .upperMap(ucap) @@ -97,7 +97,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-2011 * 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -86,7 +86,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); @@ -112,7 +112,7 @@ concepts::ReadWriteMap dist_map; concepts::ReadWriteMap reached_map; concepts::WriteMap processed_map; - + dfs_test .predMap(pred_map) .distMap(dist_map) @@ -129,7 +129,7 @@ e = dfs_test.nextArc(); b = dfs_test.emptyQueue(); i = dfs_test.queueSize(); - + dfs_test.start(); dfs_test.start(t); dfs_test.start(am); @@ -219,7 +219,7 @@ Dfs dfs(G); check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6."); } - + { NullMap myPredMap; dfs(G).predMap(myPredMap).run(s); 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-2011 * 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-2011 * 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-2011 * 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/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-2011 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + #include #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_copy_test.cc b/test/graph_copy_test.cc --- a/test/graph_copy_test.cc +++ b/test/graph_copy_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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -70,7 +70,7 @@ nodeRef(nr).arcRef(er). nodeCrossRef(ncr).arcCrossRef(ecr). node(fn, tn).arc(fa, ta).run(); - + check(countNodes(from) == countNodes(to), "Wrong copy."); check(countArcs(from) == countArcs(to), "Wrong copy."); @@ -98,7 +98,7 @@ // Test repeated copy digraphCopy(from, to).run(); - + check(countNodes(from) == countNodes(to), "Wrong copy."); check(countArcs(from) == countArcs(to), "Wrong copy."); } @@ -200,7 +200,7 @@ // Test repeated copy graphCopy(from, to).run(); - + check(countNodes(from) == countNodes(to), "Wrong copy."); check(countEdges(from) == countEdges(to), "Wrong copy."); check(countArcs(from) == countArcs(to), "Wrong copy."); 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-2011 * 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/heap_test.cc b/test/heap_test.cc --- a/test/heap_test.cc +++ b/test/heap_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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * diff --git a/test/lgf_test.cc b/test/lgf_test.cc --- a/test/lgf_test.cc +++ b/test/lgf_test.cc @@ -63,10 +63,10 @@ "0 1\n"; -int main() +int main() { { - ListDigraph d; + ListDigraph d; ListDigraph::Node s,t; ListDigraph::ArcMap label(d); std::istringstream input(test_lgf); @@ -93,7 +93,7 @@ } { - ListDigraph d; + ListDigraph d; std::istringstream input(test_lgf_nomap); digraphReader(d, input). run(); @@ -110,14 +110,14 @@ } { - ListDigraph d; + ListDigraph d; std::istringstream input(test_lgf_bad1); bool ok=false; try { digraphReader(d, input). run(); } - catch (FormatError& error) + catch (FormatError& error) { ok = true; } @@ -139,7 +139,7 @@ } { - ListDigraph d; + ListDigraph d; std::istringstream input(test_lgf_bad2); bool ok=false; try { 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -70,8 +70,10 @@ checkConcept, WriteMap >(); checkConcept, ReadWriteMap >(); checkConcept, ReadWriteMap >(); - checkConcept, ReferenceMap >(); - checkConcept, ReferenceMap >(); + checkConcept, + ReferenceMap >(); + checkConcept, + ReferenceMap >(); // NullMap { @@ -200,7 +202,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"); @@ -349,7 +352,7 @@ it != map2.end(); ++it ) check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); } - + // CrossRefMap { typedef ListDigraph Graph; @@ -357,16 +360,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'); 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-2011 * 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); 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-2011 * 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -47,7 +47,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" @@ -93,7 +93,7 @@ struct Constraints { void constraints() { checkConcept(); - + const Constraints& me = *this; MCF mcf(me.g); @@ -122,7 +122,7 @@ typedef concepts::ReadMap CAM; typedef concepts::WriteMap FlowMap; typedef concepts::WriteMap PotMap; - + GR g; VAM lower; VAM upper; @@ -176,7 +176,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); @@ -189,7 +189,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) @@ -202,7 +202,7 @@ opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0); } } - + return opt; } @@ -227,7 +227,7 @@ red_supply[gr.target(a)] += lower[a]; } } - + for (NodeIt n(gr); n != INVALID; ++n) { dual_cost -= red_supply[n] * pi[n]; } @@ -236,7 +236,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; } @@ -308,7 +308,7 @@ .node("source", v) .node("target", w) .run(); - + // Build test digraphs with negative costs Digraph neg_gr; Node n1 = neg_gr.addNode(); @@ -318,7 +318,7 @@ Node n5 = neg_gr.addNode(); Node n6 = neg_gr.addNode(); Node n7 = neg_gr.addNode(); - + Arc a1 = neg_gr.addArc(n1, n2); Arc a2 = neg_gr.addArc(n1, n3); Arc a3 = neg_gr.addArc(n2, n4); @@ -328,17 +328,17 @@ Arc a7 = neg_gr.addArc(n5, n6); Arc a8 = neg_gr.addArc(n6, n7); Arc a9 = neg_gr.addArc(n7, n5); - + Digraph::ArcMap neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0); ConstMap neg_u1(std::numeric_limits::max()), neg_u2(5000); Digraph::NodeMap neg_s(neg_gr, 0); - + neg_l2[a7] = 1000; neg_l2[a8] = -1000; - + neg_s[n1] = 100; neg_s[n4] = -100; - + neg_c[a1] = 100; neg_c[a2] = 30; neg_c[a3] = 20; @@ -422,7 +422,7 @@ neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s); checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1, neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A18"); - + NetworkSimplex negs_mcf(negs_gr); negs_mcf.costMap(negs_c).supplyMap(negs_s); checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u, 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -113,7 +113,7 @@ const FlowMap& fm = const_preflow_test.flowMap(); b = const_preflow_test.minCut(n); const_preflow_test.minCutMap(cut); - + ignore_unused_variable_warning(fm); } @@ -154,7 +154,7 @@ void initFlowTest() { DIGRAPH_TYPEDEFS(SmartDigraph); - + SmartDigraph g; SmartDigraph::ArcMap cap(g),iflow(g); Node s=g.addNode(); Node t=g.addNode(); @@ -266,6 +266,6 @@ "The max flow value or the three min cut values are incorrect."); initFlowTest(); - + return 0; } 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-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -80,7 +80,7 @@ typedef Digraph::Node Node; typedef Digraph::Arc Arc; typedef concepts::ReadMap LengthMap; - + typedef Suurballe SuurballeType; Digraph g; @@ -104,7 +104,7 @@ k = suurb_test.findFlow(n); k = suurb_test.findFlow(n, k); suurb_test.findPaths(); - + int f; VType c; c = const_suurb_test.totalLength(); @@ -116,7 +116,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); } 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-2011 * 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 @@ -147,7 +147,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'; } @@ -165,7 +165,7 @@ << std::endl; exit(1); } - + switch(desc.type) { case DimacsDescriptor::MIN: @@ -237,7 +237,7 @@ std::ostream& os = (ap.files().size()<2 ? std::cout : output); DimacsDescriptor desc = dimacsType(is); - + if(!ap.given("q")) { std::cout << "Problem type: "; @@ -262,7 +262,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"))