Index: .hgignore =================================================================== --- .hgignore (revision 385) +++ .hgignore (revision 298) @@ -37,5 +37,4 @@ ^objs.*/.* ^test/[a-z_]*$ -^tools/[a-z-_]*$ ^demo/.*_demo$ ^build/.* Index: demo/Makefile.am =================================================================== --- demo/Makefile.am (revision 164) +++ demo/Makefile.am (revision 399) @@ -1,4 +1,5 @@ EXTRA_DIST += \ demo/CMakeLists.txt \ + demo/circulation-input.lgf \ demo/digraph.lgf @@ -7,4 +8,5 @@ noinst_PROGRAMS += \ demo/arg_parser_demo \ + demo/circulation_demo \ demo/graph_to_eps_demo \ demo/lgf_demo @@ -13,4 +15,5 @@ demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc +demo_circulation_demo_SOURCES = demo/circulation_demo.cc demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc demo_lgf_demo_SOURCES = demo/lgf_demo.cc Index: demo/circulation-input.lgf =================================================================== --- demo/circulation-input.lgf (revision 399) +++ demo/circulation-input.lgf (revision 399) @@ -0,0 +1,32 @@ +@nodes +coordinates_x coordinates_y delta label +-396.638 -311.798 0 0 +154.409 -214.714 13 1 +-378.119 -135.808 0 2 +-138.182 -58.0452 0 3 +55 -76.1018 0 4 +-167.302 169.88 0 5 +71.6876 38.7452 0 6 +-328.784 257.777 0 7 +354.242 67.9628 -13 8 +147 266 0 9 +@edges + label lo_cap up_cap +0 1 0 0 20 +0 2 1 0 0 +1 1 2 0 3 +1 2 3 0 8 +1 3 4 0 8 +2 5 5 0 5 +3 2 6 0 5 +3 5 7 0 5 +3 6 8 0 5 +4 3 9 0 3 +5 7 10 0 3 +5 6 11 0 10 +5 8 12 0 10 +6 8 13 0 8 +8 9 14 0 20 +8 1 15 0 5 +9 5 16 0 5 +@end Index: demo/circulation_demo.cc =================================================================== --- demo/circulation_demo.cc (revision 399) +++ demo/circulation_demo.cc (revision 399) @@ -0,0 +1,107 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2008 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +///\ingroup demos +///\file +///\brief Demonstrating the usage of LEMON's General Flow algorithm +/// +/// This demo program reads a general network circulation problem from the +/// file 'circulation-input.lgf', runs the preflow based algorithm for +/// finding a feasible solution and writes the output +/// to 'circulation-input.lgf' +/// +/// \include circulation_demo.cc + +#include + +#include +#include +#include +#include + +using namespace lemon; + + +int main (int, char*[]) +{ + + typedef ListDigraph Digraph; + typedef Digraph::Node Node; + typedef Digraph::NodeIt NodeIt; + typedef Digraph::Arc Arc; + typedef Digraph::ArcIt ArcIt; + typedef Digraph::ArcMap ArcMap; + typedef Digraph::NodeMap NodeMap; + typedef Digraph::NodeMap DNodeMap; + + Digraph g; + ArcMap lo(g); + ArcMap up(g); + NodeMap delta(g); + NodeMap nid(g); + ArcMap eid(g); + DNodeMap cx(g); + DNodeMap cy(g); + + DigraphReader(g,"circulation-input.lgf"). + arcMap("lo_cap", lo). + arcMap("up_cap", up). + nodeMap("delta", delta). + arcMap("label", eid). + nodeMap("label", nid). + nodeMap("coordinates_x", cx). + nodeMap("coordinates_y", cy). + run(); + + Circulation gen(g,lo,up,delta); + bool ret=gen.run(); + if(ret) + { + std::cout << "\nA feasible flow has been found.\n"; + if(!gen.checkFlow()) std::cerr << "Oops!!!\n"; + DigraphWriter(g, "circulation-output.lgf"). + arcMap("lo_cap", lo). + arcMap("up_cap", up). + arcMap("flow", gen.flowMap()). + nodeMap("delta", delta). + arcMap("label", eid). + nodeMap("label", nid). + nodeMap("coordinates_x", cx). + nodeMap("coordinates_y", cy). + run(); + } + else { + std::cout << "\nThere is no such a flow\n"; + Digraph::NodeMap bar(g); + gen.barrierMap(bar); + if(!gen.checkBarrier()) std::cerr << "Dual Oops!!!\n"; + + DigraphWriter(g, "circulation-output.lgf"). + arcMap("lo_cap", lo). + arcMap("up_cap", up). + nodeMap("barrier", bar). + nodeMap("delta", delta). + arcMap("label", eid). + nodeMap("label", nid). + nodeMap("coordinates_x", cx). + nodeMap("coordinates_y", cy). + run(); + } + std::cout << "The output is written to file 'circulation-output.lgf'\n\n"; + +} Index: doc/groups.dox =================================================================== --- doc/groups.dox (revision 388) +++ doc/groups.dox (revision 351) @@ -483,16 +483,7 @@ /** -@defgroup dimacs_group DIMACS format -@ingroup io_group -\brief Read and write files in DIMACS format - -Tools to read a digraph from or write it to a file in DIMACS format data. -*/ - -/** @defgroup nauty_group NAUTY Format @ingroup io_group \brief Read \e Nauty format - Tool to read graphs from \e Nauty format data. */ Index: lemon/Makefile.am =================================================================== --- lemon/Makefile.am (revision 395) +++ lemon/Makefile.am (revision 399) @@ -21,4 +21,5 @@ lemon/bfs.h \ lemon/bin_heap.h \ + lemon/circulation.h \ lemon/color.h \ lemon/concept_check.h \ @@ -28,5 +29,4 @@ lemon/dijkstra.h \ lemon/dim2.h \ - lemon/dimacs.h \ lemon/elevator.h \ lemon/error.h \ @@ -44,5 +44,4 @@ lemon/nauty_reader.h \ lemon/path.h \ - lemon/preflow.h \ lemon/random.h \ lemon/smart_graph.h \ Index: lemon/circulation.h =================================================================== --- lemon/circulation.h (revision 399) +++ lemon/circulation.h (revision 399) @@ -0,0 +1,656 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2008 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_CIRCULATION_H +#define LEMON_CIRCULATION_H + +#include +#include +#include +#include + +///\ingroup max_flow +///\file +///\brief Push-prelabel algorithm for finding a feasible circulation. +/// +namespace lemon { + + /// \brief Default traits class of Circulation class. + /// + /// Default traits class of Circulation class. + /// \param _Graph Digraph type. + /// \param _CapacityMap Type of capacity map. + template + struct CirculationDefaultTraits { + + /// \brief The digraph type the algorithm runs on. + typedef _Graph Digraph; + + /// \brief The type of the map that stores the circulation lower + /// bound. + /// + /// The type of the map that stores the circulation lower bound. + /// It must meet the \ref concepts::ReadMap "ReadMap" concept. + typedef _LCapMap LCapMap; + + /// \brief The type of the map that stores the circulation upper + /// bound. + /// + /// The type of the map that stores the circulation upper bound. + /// It must meet the \ref concepts::ReadMap "ReadMap" concept. + typedef _UCapMap UCapMap; + + /// \brief The type of the map that stores the upper bound of + /// node excess. + /// + /// The type of the map that stores the lower bound of node + /// excess. It must meet the \ref concepts::ReadMap "ReadMap" + /// concept. + typedef _DeltaMap DeltaMap; + + /// \brief The type of the length of the arcs. + typedef typename DeltaMap::Value Value; + + /// \brief The map type that stores the flow values. + /// + /// The map type that stores the flow values. + /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + typedef typename Digraph::template ArcMap FlowMap; + + /// \brief Instantiates a FlowMap. + /// + /// This function instantiates a \ref FlowMap. + /// \param digraph The digraph, to which we would like to define + /// the flow map. + static FlowMap* createFlowMap(const Digraph& digraph) { + return new FlowMap(digraph); + } + + /// \brief The eleavator type used by Circulation algorithm. + /// + /// The elevator type used by Circulation algorithm. + /// + /// \sa Elevator + /// \sa LinkedElevator + typedef lemon::Elevator Elevator; + + /// \brief Instantiates an Elevator. + /// + /// This function instantiates a \ref Elevator. + /// \param digraph The digraph, to which we would like to define + /// the elevator. + /// \param max_level The maximum level of the elevator. + static Elevator* createElevator(const Digraph& digraph, int max_level) { + return new Elevator(digraph, max_level); + } + + /// \brief The tolerance used by the algorithm + /// + /// The tolerance used by the algorithm to handle inexact computation. + typedef lemon::Tolerance Tolerance; + + }; + + ///Push-relabel algorithm for the Network Circulation Problem. + + /** + \ingroup max_flow + This class implements a push-relabel algorithm + or the Network Circulation Problem. + The exact formulation of this problem is the following. + \f[\sum_{e\in\rho(v)}x(e)-\sum_{e\in\delta(v)}x(e)\leq + -delta(v)\quad \forall v\in V \f] + \f[ lo(e)\leq x(e) \leq up(e) \quad \forall e\in E \f] + */ + template, + class _UCapMap=_LCapMap, + class _DeltaMap=typename _Graph::template NodeMap< + typename _UCapMap::Value>, + class _Traits=CirculationDefaultTraits<_Graph, _LCapMap, + _UCapMap, _DeltaMap> > + class Circulation { + + typedef _Traits Traits; + typedef typename Traits::Digraph Digraph; + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); + + typedef typename Traits::Value Value; + + typedef typename Traits::LCapMap LCapMap; + typedef typename Traits::UCapMap UCapMap; + typedef typename Traits::DeltaMap DeltaMap; + typedef typename Traits::FlowMap FlowMap; + typedef typename Traits::Elevator Elevator; + typedef typename Traits::Tolerance Tolerance; + + typedef typename Digraph::template NodeMap ExcessMap; + + const Digraph &_g; + int _node_num; + + const LCapMap *_lo; + const UCapMap *_up; + const DeltaMap *_delta; + + FlowMap *_flow; + bool _local_flow; + + Elevator* _level; + bool _local_level; + + ExcessMap* _excess; + + Tolerance _tol; + int _el; + + public: + + typedef Circulation Create; + + ///\name Named template parameters + + ///@{ + + template + struct DefFlowMapTraits : public Traits { + typedef _FlowMap FlowMap; + static FlowMap *createFlowMap(const Digraph&) { + LEMON_ASSERT(false, "FlowMap is not initialized"); + return 0; // ignore warnings + } + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// FlowMap type + /// + /// \ref named-templ-param "Named parameter" for setting FlowMap + /// type + template + struct DefFlowMap + : public Circulation > { + typedef Circulation > Create; + }; + + template + struct DefElevatorTraits : public Traits { + typedef _Elevator Elevator; + static Elevator *createElevator(const Digraph&, int) { + LEMON_ASSERT(false, "Elevator is not initialized"); + return 0; // ignore warnings + } + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// Elevator type + /// + /// \ref named-templ-param "Named parameter" for setting Elevator + /// type + template + struct DefElevator + : public Circulation > { + typedef Circulation > Create; + }; + + template + struct DefStandardElevatorTraits : public Traits { + typedef _Elevator Elevator; + static Elevator *createElevator(const Digraph& digraph, int max_level) { + return new Elevator(digraph, max_level); + } + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// Elevator type + /// + /// \ref named-templ-param "Named parameter" for setting Elevator + /// type. The Elevator should be standard constructor interface, ie. + /// the digraph and the maximum level should be passed to it. + template + struct DefStandardElevator + : public Circulation > { + typedef Circulation > Create; + }; + + /// @} + + protected: + + Circulation() {} + + public: + + /// The constructor of the class. + + /// The constructor of the class. + /// \param g The digraph the algorithm runs on. + /// \param lo The lower bound capacity of the arcs. + /// \param up The upper bound capacity of the arcs. + /// \param delta The lower bound on node excess. + Circulation(const Digraph &g,const LCapMap &lo, + const UCapMap &up,const DeltaMap &delta) + : _g(g), _node_num(), + _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false), + _level(0), _local_level(false), _excess(0), _el() {} + + /// Destrcutor. + ~Circulation() { + destroyStructures(); + } + + private: + + void createStructures() { + _node_num = _el = countNodes(_g); + + if (!_flow) { + _flow = Traits::createFlowMap(_g); + _local_flow = true; + } + if (!_level) { + _level = Traits::createElevator(_g, _node_num); + _local_level = true; + } + if (!_excess) { + _excess = new ExcessMap(_g); + } + } + + void destroyStructures() { + if (_local_flow) { + delete _flow; + } + if (_local_level) { + delete _level; + } + if (_excess) { + delete _excess; + } + } + + public: + + /// Sets the lower bound capacity map. + + /// Sets the lower bound capacity map. + /// \return \c (*this) + Circulation& lowerCapMap(const LCapMap& map) { + _lo = ↦ + return *this; + } + + /// Sets the upper bound capacity map. + + /// Sets the upper bound capacity map. + /// \return \c (*this) + Circulation& upperCapMap(const LCapMap& map) { + _up = ↦ + return *this; + } + + /// Sets the lower bound map on excess. + + /// Sets the lower bound map on excess. + /// \return \c (*this) + Circulation& deltaMap(const DeltaMap& map) { + _delta = ↦ + return *this; + } + + /// Sets the flow map. + + /// Sets the flow map. + /// \return \c (*this) + Circulation& flowMap(FlowMap& map) { + if (_local_flow) { + delete _flow; + _local_flow = false; + } + _flow = ↦ + return *this; + } + + /// Returns the flow map. + + /// \return The flow map. + /// + const FlowMap& flowMap() { + return *_flow; + } + + /// Sets the elevator. + + /// Sets the elevator. + /// \return \c (*this) + Circulation& elevator(Elevator& elevator) { + if (_local_level) { + delete _level; + _local_level = false; + } + _level = &elevator; + return *this; + } + + /// Returns the elevator. + + /// \return The elevator. + /// + const Elevator& elevator() { + return *_level; + } + + /// Sets the tolerance used by algorithm. + + /// Sets the tolerance used by algorithm. + /// + Circulation& tolerance(const Tolerance& tolerance) const { + _tol = tolerance; + return *this; + } + + /// Returns the tolerance used by algorithm. + + /// Returns the tolerance used by algorithm. + /// + const Tolerance& tolerance() const { + return tolerance; + } + + /// \name Execution control + /// The simplest way to execute the algorithm is to use one of the + /// member functions called \c run(). + /// \n + /// If you need more control on initial solution or execution then + /// you have to call one \ref init() function and then the start() + /// function. + + ///@{ + + /// Initializes the internal data structures. + + /// Initializes the internal data structures. This function sets + /// all flow values to the lower bound. + /// \return This function returns false if the initialization + /// process found a barrier. + void init() + { + createStructures(); + + for(NodeIt n(_g);n!=INVALID;++n) { + _excess->set(n, (*_delta)[n]); + } + + for (ArcIt e(_g);e!=INVALID;++e) { + _flow->set(e, (*_lo)[e]); + _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]); + _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]); + } + + // global relabeling tested, but in general case it provides + // worse performance for random digraphs + _level->initStart(); + for(NodeIt n(_g);n!=INVALID;++n) + _level->initAddItem(n); + _level->initFinish(); + for(NodeIt n(_g);n!=INVALID;++n) + if(_tol.positive((*_excess)[n])) + _level->activate(n); + } + + /// Initializes the internal data structures. + + /// Initializes the internal data structures. This functions uses + /// greedy approach to construct the initial solution. + void greedyInit() + { + createStructures(); + + for(NodeIt n(_g);n!=INVALID;++n) { + _excess->set(n, (*_delta)[n]); + } + + for (ArcIt e(_g);e!=INVALID;++e) { + if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) { + _flow->set(e, (*_up)[e]); + _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]); + _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]); + } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) { + _flow->set(e, (*_lo)[e]); + _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]); + _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]); + } else { + Value fc = -(*_excess)[_g.target(e)]; + _flow->set(e, fc); + _excess->set(_g.target(e), 0); + _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc); + } + } + + _level->initStart(); + for(NodeIt n(_g);n!=INVALID;++n) + _level->initAddItem(n); + _level->initFinish(); + for(NodeIt n(_g);n!=INVALID;++n) + if(_tol.positive((*_excess)[n])) + _level->activate(n); + } + + ///Starts the algorithm + + ///This function starts the algorithm. + ///\return This function returns true if it found a feasible circulation. + /// + ///\sa barrier() + bool start() + { + + Node act; + Node bact=INVALID; + Node last_activated=INVALID; + while((act=_level->highestActive())!=INVALID) { + int actlevel=(*_level)[act]; + int mlevel=_node_num; + Value exc=(*_excess)[act]; + + for(OutArcIt e(_g,act);e!=INVALID; ++e) { + Node v = _g.target(e); + Value fc=(*_up)[e]-(*_flow)[e]; + if(!_tol.positive(fc)) continue; + if((*_level)[v]set(e, (*_flow)[e] + exc); + _excess->set(v, (*_excess)[v] + exc); + if(!_level->active(v) && _tol.positive((*_excess)[v])) + _level->activate(v); + _excess->set(act,0); + _level->deactivate(act); + goto next_l; + } + else { + _flow->set(e, (*_up)[e]); + _excess->set(v, (*_excess)[v] + fc); + if(!_level->active(v) && _tol.positive((*_excess)[v])) + _level->activate(v); + exc-=fc; + } + } + else if((*_level)[v]set(e, (*_flow)[e] - exc); + _excess->set(v, (*_excess)[v] + exc); + if(!_level->active(v) && _tol.positive((*_excess)[v])) + _level->activate(v); + _excess->set(act,0); + _level->deactivate(act); + goto next_l; + } + else { + _flow->set(e, (*_lo)[e]); + _excess->set(v, (*_excess)[v] + fc); + if(!_level->active(v) && _tol.positive((*_excess)[v])) + _level->activate(v); + exc-=fc; + } + } + else if((*_level)[v]set(act, exc); + if(!_tol.positive(exc)) _level->deactivate(act); + else if(mlevel==_node_num) { + _level->liftHighestActiveToTop(); + _el = _node_num; + return false; + } + else { + _level->liftHighestActive(mlevel+1); + if(_level->onLevel(actlevel)==0) { + _el = actlevel; + return false; + } + } + next_l: + ; + } + return true; + } + + /// Runs the circulation algorithm. + + /// Runs the circulation algorithm. + /// \note fc.run() is just a shortcut of the following code. + /// \code + /// fc.greedyInit(); + /// return fc.start(); + /// \endcode + bool run() { + greedyInit(); + return start(); + } + + /// @} + + /// \name Query Functions + /// The result of the %Circulation algorithm can be obtained using + /// these functions. + /// \n + /// Before the use of these functions, + /// either run() or start() must be called. + + ///@{ + + /** + \brief Returns a barrier + + Barrier is a set \e B of nodes for which + \f[ \sum_{v\in B}-delta(v)< + \sum_{e\in\rho(B)}lo(e)-\sum_{e\in\delta(B)}up(e) \f] + holds. The existence of a set with this property prooves that a feasible + flow cannot exists. + \sa checkBarrier() + \sa run() + */ + template + void barrierMap(GT &bar) + { + for(NodeIt n(_g);n!=INVALID;++n) + bar.set(n, (*_level)[n] >= _el); + } + + ///Returns true if the node is in the barrier + + ///Returns true if the node is in the barrier + ///\sa barrierMap() + bool barrier(const Node& node) + { + return (*_level)[node] >= _el; + } + + /// \brief Returns the flow on the arc. + /// + /// Sets the \c flowMap to the flow on the arcs. This method can + /// be called after the second phase of algorithm. + Value flow(const Arc& arc) const { + return (*_flow)[arc]; + } + + /// @} + + /// \name Checker Functions + /// The feasibility of the results can be checked using + /// these functions. + /// \n + /// Before the use of these functions, + /// either run() or start() must be called. + + ///@{ + + ///Check if the \c flow is a feasible circulation + bool checkFlow() { + for(ArcIt e(_g);e!=INVALID;++e) + if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false; + for(NodeIt n(_g);n!=INVALID;++n) + { + Value dif=-(*_delta)[n]; + for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e]; + for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e]; + if(_tol.negative(dif)) return false; + } + return true; + } + + ///Check whether or not the last execution provides a barrier + + ///Check whether or not the last execution provides a barrier + ///\sa barrier() + bool checkBarrier() + { + Value delta=0; + for(NodeIt n(_g);n!=INVALID;++n) + if(barrier(n)) + delta-=(*_delta)[n]; + for(ArcIt e(_g);e!=INVALID;++e) + { + Node s=_g.source(e); + Node t=_g.target(e); + if(barrier(s)&&!barrier(t)) delta+=(*_up)[e]; + else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e]; + } + return _tol.negative(delta); + } + + /// @} + + }; + +} + +#endif Index: lemon/dijkstra.h =================================================================== --- lemon/dijkstra.h (revision 397) +++ lemon/dijkstra.h (revision 313) @@ -48,4 +48,27 @@ static Value plus(const Value& left, const Value& right) { return left + right; + } + /// \brief Gives back true only if the first value is less than the second. + static bool less(const Value& left, const Value& right) { + return left < right; + } + }; + + /// \brief Widest path operation traits for the Dijkstra algorithm class. + /// + /// This operation traits class defines all computational operations and + /// constants which are used in the Dijkstra algorithm for widest path + /// computation. + /// + /// \see DijkstraDefaultOperationTraits + template + struct DijkstraWidestPathOperationTraits { + /// \brief Gives back the maximum value of the type. + static Value zero() { + return std::numeric_limits::max(); + } + /// \brief Gives back the minimum of the given two elements. + static Value plus(const Value& left, const Value& right) { + return std::min(left, right); } /// \brief Gives back true only if the first value is less than the second. Index: mon/dimacs.h =================================================================== --- lemon/dimacs.h (revision 388) +++ (revision ) @@ -1,357 +1,0 @@ -/* -*- mode: C++; indent-tabs-mode: nil; -*- - * - * This file is a part of LEMON, a generic C++ optimization library. - * - * Copyright (C) 2003-2008 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_DIMACS_H -#define LEMON_DIMACS_H - -#include -#include -#include -#include -#include - -/// \ingroup dimacs_group -/// \file -/// \brief DIMACS file format reader. - -namespace lemon { - - /// \addtogroup dimacs_group - /// @{ - - /// DIMACS file type descriptor. - struct DimacsDescriptor - { - ///File type enum - enum Type - { - NONE, MIN, MAX, SP, MAT - }; - ///The file type - Type type; - ///The number of nodes in the graph - int nodeNum; - ///The number of edges in the graph - int edgeNum; - int lineShift; - /// Constructor. Sets the type to NONE. - DimacsDescriptor() : type(NONE) {} - }; - - ///Discover the type of a DIMACS file - - ///It starts seeking the begining of the file for the problem type - ///and size info. The found data is returned in a special struct - ///that can be evaluated and passed to the appropriate reader - ///function. - DimacsDescriptor dimacsType(std::istream& is) - { - DimacsDescriptor r; - std::string problem,str; - char c; - r.lineShift=0; - while (is >> c) - switch(c) - { - case 'p': - if(is >> problem >> r.nodeNum >> r.edgeNum) - { - getline(is, str); - r.lineShift++; - if(problem=="min") r.type=DimacsDescriptor::MIN; - else if(problem=="max") r.type=DimacsDescriptor::MAX; - else if(problem=="sp") r.type=DimacsDescriptor::SP; - else if(problem=="mat") r.type=DimacsDescriptor::MAT; - else throw FormatError("Unknown problem type"); - return r; - } - else - { - throw FormatError("Missing or wrong problem type declaration."); - } - break; - case 'c': - getline(is, str); - r.lineShift++; - break; - default: - throw FormatError("Unknown DIMACS declaration."); - } - throw FormatError("Missing problem type declaration."); - } - - - - /// DIMACS minimum cost flow reader function. - /// - /// This function reads a minimum cost flow instance from DIMACS format, - /// i.e. from a DIMACS file having a line starting with - /// \code - /// p min - /// \endcode - /// At the beginning, \c g is cleared by \c g.clear(). The supply - /// amount of the nodes are written to \c supply (signed). The - /// lower bounds, capacities and costs of the arcs are written to - /// \c lower, \c capacity and \c cost. - /// - /// If the file type was previously evaluated by dimacsType(), then - /// the descriptor struct should be given by the \c dest parameter. - template - void readDimacsMin(std::istream& is, - Digraph &g, - LowerMap& lower, - CapacityMap& capacity, - CostMap& cost, - SupplyMap& supply, - DimacsDescriptor desc=DimacsDescriptor()) - { - g.clear(); - std::vector nodes; - typename Digraph::Arc e; - std::string problem, str; - char c; - int i, j; - if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); - if(desc.type!=DimacsDescriptor::MIN) - throw FormatError("Problem type mismatch"); - - nodes.resize(desc.nodeNum + 1); - for (int k = 1; k <= desc.nodeNum; ++k) { - nodes[k] = g.addNode(); - supply.set(nodes[k], 0); - } - - typename SupplyMap::Value sup; - typename CapacityMap::Value low; - typename CapacityMap::Value cap; - typename CostMap::Value co; - while (is >> c) { - switch (c) { - case 'c': // comment line - getline(is, str); - break; - case 'n': // node definition line - is >> i >> sup; - getline(is, str); - supply.set(nodes[i], sup); - break; - case 'a': // arc (arc) definition line - is >> i >> j >> low >> cap >> co; - getline(is, str); - e = g.addArc(nodes[i], nodes[j]); - lower.set(e, low); - if (cap >= 0) - capacity.set(e, cap); - else - capacity.set(e, -1); - cost.set(e, co); - break; - } - } - } - - template - void _readDimacs(std::istream& is, - Digraph &g, - CapacityMap& capacity, - typename Digraph::Node &s, - typename Digraph::Node &t, - DimacsDescriptor desc=DimacsDescriptor()) { - g.clear(); - s=t=INVALID; - std::vector nodes; - typename Digraph::Arc e; - char c, d; - int i, j; - typename CapacityMap::Value _cap; - std::string str; - nodes.resize(desc.nodeNum + 1); - for (int k = 1; k <= desc.nodeNum; ++k) { - nodes[k] = g.addNode(); - } - - while (is >> c) { - switch (c) { - case 'c': // comment line - getline(is, str); - break; - case 'n': // node definition line - if (desc.type==DimacsDescriptor::SP) { // shortest path problem - is >> i; - getline(is, str); - s = nodes[i]; - } - if (desc.type==DimacsDescriptor::MAX) { // max flow problem - is >> i >> d; - getline(is, str); - if (d == 's') s = nodes[i]; - if (d == 't') t = nodes[i]; - } - break; - case 'a': // arc (arc) definition line - if (desc.type==DimacsDescriptor::SP || - desc.type==DimacsDescriptor::MAX) { - is >> i >> j >> _cap; - getline(is, str); - e = g.addArc(nodes[i], nodes[j]); - capacity.set(e, _cap); - } else { - is >> i >> j; - getline(is, str); - g.addArc(nodes[i], nodes[j]); - } - break; - } - } - } - - /// DIMACS maximum flow reader function. - /// - /// This function reads a maximum flow instance from DIMACS format, - /// i.e. from a DIMACS file having a line starting with - /// \code - /// p max - /// \endcode - /// At the beginning, \c g is cleared by \c g.clear(). The arc - /// capacities are written to \c capacity and \c s and \c t are - /// set to the source and the target nodes. - /// - /// If the file type was previously evaluated by dimacsType(), then - /// the descriptor struct should be given by the \c dest parameter. - template - void readDimacsMax(std::istream& is, - Digraph &g, - CapacityMap& capacity, - typename Digraph::Node &s, - typename Digraph::Node &t, - DimacsDescriptor desc=DimacsDescriptor()) { - if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); - if(desc.type!=DimacsDescriptor::MAX) - throw FormatError("Problem type mismatch"); - _readDimacs(is,g,capacity,s,t,desc); - } - - /// DIMACS shortest path reader function. - /// - /// This function reads a shortest path instance from DIMACS format, - /// i.e. from a DIMACS file having a line starting with - /// \code - /// p sp - /// \endcode - /// At the beginning, \c g is cleared by \c g.clear(). The arc - /// lengths are written to \c length and \c s is set to the - /// source node. - /// - /// If the file type was previously evaluated by dimacsType(), then - /// the descriptor struct should be given by the \c dest parameter. - template - void readDimacsSp(std::istream& is, - Digraph &g, - LengthMap& length, - typename Digraph::Node &s, - DimacsDescriptor desc=DimacsDescriptor()) { - typename Digraph::Node t; - if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); - if(desc.type!=DimacsDescriptor::SP) - throw FormatError("Problem type mismatch"); - _readDimacs(is, g, length, s, t,desc); - } - - /// DIMACS capacitated digraph reader function. - /// - /// This function reads an arc capacitated digraph instance from - /// DIMACS 'mat' or 'sp' format. - /// At the beginning, \c g is cleared by \c g.clear() - /// and the arc capacities/lengths are written to \c capacity. - /// - /// If the file type was previously evaluated by dimacsType(), then - /// the descriptor struct should be given by the \c dest parameter. - template - void readDimacsCap(std::istream& is, - Digraph &g, - CapacityMap& capacity, - DimacsDescriptor desc=DimacsDescriptor()) { - typename Digraph::Node u,v; - if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); - if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP) - throw FormatError("Problem type mismatch"); - _readDimacs(is, g, capacity, u, v, desc); - } - - /// DIMACS plain digraph reader function. - /// - /// This function reads a digraph without any designated nodes and - /// maps from DIMACS format, i.e. from DIMACS files having a line - /// starting with - /// \code - /// p mat - /// \endcode - /// At the beginning, \c g is cleared by \c g.clear(). - /// - /// If the file type was previously evaluated by dimacsType(), then - /// the descriptor struct should be given by the \c dest parameter. - template - void readDimacsMat(std::istream& is, Digraph &g, - DimacsDescriptor desc=DimacsDescriptor()) { - typename Digraph::Node u,v; - NullMap n; - if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); - if(desc.type!=DimacsDescriptor::MAT) - throw FormatError("Problem type mismatch"); - _readDimacs(is, g, n, u, v, desc); - } - - /// DIMACS plain digraph writer function. - /// - /// This function writes a digraph without any designated nodes and - /// maps into DIMACS format, i.e. into DIMACS file having a line - /// starting with - /// \code - /// p mat - /// \endcode - /// If \c comment is not empty, then it will be printed in the first line - /// prefixed by 'c'. - template - void writeDimacsMat(std::ostream& os, const Digraph &g, - std::string comment="") { - typedef typename Digraph::NodeIt NodeIt; - typedef typename Digraph::ArcIt ArcIt; - - if(!comment.empty()) - os << "c " << comment << std::endl; - os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl; - - typename Digraph::template NodeMap nodes(g); - int i = 1; - for(NodeIt v(g); v != INVALID; ++v) { - nodes.set(v, i); - ++i; - } - for(ArcIt e(g); e != INVALID; ++e) { - os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] - << std::endl; - } - } - - /// @} - -} //namespace lemon - -#endif //LEMON_DIMACS_H Index: mon/preflow.h =================================================================== --- lemon/preflow.h (revision 393) +++ (revision ) @@ -1,964 +1,0 @@ -/* -*- mode: C++; indent-tabs-mode: nil; -*- - * - * This file is a part of LEMON, a generic C++ optimization library. - * - * Copyright (C) 2003-2008 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_PREFLOW_H -#define LEMON_PREFLOW_H - -#include -#include - -/// \file -/// \ingroup max_flow -/// \brief Implementation of the preflow algorithm. - -namespace lemon { - - /// \brief Default traits class of Preflow class. - /// - /// Default traits class of Preflow class. - /// \tparam _Digraph Digraph type. - /// \tparam _CapacityMap Capacity map type. - template - struct PreflowDefaultTraits { - - /// \brief The type of the digraph the algorithm runs on. - typedef _Digraph Digraph; - - /// \brief The type of the map that stores the arc capacities. - /// - /// The type of the map that stores the arc capacities. - /// It must meet the \ref concepts::ReadMap "ReadMap" concept. - typedef _CapacityMap CapacityMap; - - /// \brief The type of the flow values. - typedef typename CapacityMap::Value Value; - - /// \brief The type of the map that stores the flow values. - /// - /// The type of the map that stores the flow values. - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. - typedef typename Digraph::template ArcMap FlowMap; - - /// \brief Instantiates a FlowMap. - /// - /// This function instantiates a \ref FlowMap. - /// \param digraph The digraph, to which we would like to define - /// the flow map. - static FlowMap* createFlowMap(const Digraph& digraph) { - return new FlowMap(digraph); - } - - /// \brief The elevator type used by Preflow algorithm. - /// - /// The elevator type used by Preflow algorithm. - /// - /// \sa Elevator - /// \sa LinkedElevator - typedef LinkedElevator Elevator; - - /// \brief Instantiates an Elevator. - /// - /// This function instantiates an \ref Elevator. - /// \param digraph The digraph, to which we would like to define - /// the elevator. - /// \param max_level The maximum level of the elevator. - static Elevator* createElevator(const Digraph& digraph, int max_level) { - return new Elevator(digraph, max_level); - } - - /// \brief The tolerance used by the algorithm - /// - /// The tolerance used by the algorithm to handle inexact computation. - typedef lemon::Tolerance Tolerance; - - }; - - - /// \ingroup max_flow - /// - /// \brief %Preflow algorithm class. - /// - /// This class provides an implementation of Goldberg-Tarjan's \e preflow - /// \e push-relabel algorithm producing a flow of maximum value in a - /// digraph. The preflow algorithms are the fastest known maximum - /// flow algorithms. The current implementation use a mixture of the - /// \e "highest label" and the \e "bound decrease" heuristics. - /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. - /// - /// The algorithm consists of two phases. After the first phase - /// the maximum flow value and the minimum cut is obtained. The - /// second phase constructs a feasible maximum flow on each arc. - /// - /// \tparam _Digraph The type of the digraph the algorithm runs on. - /// \tparam _CapacityMap The type of the capacity map. The default map - /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap". -#ifdef DOXYGEN - template -#else - template , - typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> > -#endif - class Preflow { - public: - - ///The \ref PreflowDefaultTraits "traits class" of the algorithm. - typedef _Traits Traits; - ///The type of the digraph the algorithm runs on. - typedef typename Traits::Digraph Digraph; - ///The type of the capacity map. - typedef typename Traits::CapacityMap CapacityMap; - ///The type of the flow values. - typedef typename Traits::Value Value; - - ///The type of the flow map. - typedef typename Traits::FlowMap FlowMap; - ///The type of the elevator. - typedef typename Traits::Elevator Elevator; - ///The type of the tolerance. - typedef typename Traits::Tolerance Tolerance; - - private: - - TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); - - const Digraph& _graph; - const CapacityMap* _capacity; - - int _node_num; - - Node _source, _target; - - FlowMap* _flow; - bool _local_flow; - - Elevator* _level; - bool _local_level; - - typedef typename Digraph::template NodeMap ExcessMap; - ExcessMap* _excess; - - Tolerance _tolerance; - - bool _phase; - - - void createStructures() { - _node_num = countNodes(_graph); - - if (!_flow) { - _flow = Traits::createFlowMap(_graph); - _local_flow = true; - } - if (!_level) { - _level = Traits::createElevator(_graph, _node_num); - _local_level = true; - } - if (!_excess) { - _excess = new ExcessMap(_graph); - } - } - - void destroyStructures() { - if (_local_flow) { - delete _flow; - } - if (_local_level) { - delete _level; - } - if (_excess) { - delete _excess; - } - } - - public: - - typedef Preflow Create; - - ///\name Named Template Parameters - - ///@{ - - template - struct SetFlowMapTraits : public Traits { - typedef _FlowMap FlowMap; - static FlowMap *createFlowMap(const Digraph&) { - LEMON_ASSERT(false, "FlowMap is not initialized"); - return 0; // ignore warnings - } - }; - - /// \brief \ref named-templ-param "Named parameter" for setting - /// FlowMap type - /// - /// \ref named-templ-param "Named parameter" for setting FlowMap - /// type. - template - struct SetFlowMap - : public Preflow > { - typedef Preflow > Create; - }; - - template - struct SetElevatorTraits : public Traits { - typedef _Elevator Elevator; - static Elevator *createElevator(const Digraph&, int) { - LEMON_ASSERT(false, "Elevator is not initialized"); - return 0; // ignore warnings - } - }; - - /// \brief \ref named-templ-param "Named parameter" for setting - /// Elevator type - /// - /// \ref named-templ-param "Named parameter" for setting Elevator - /// type. If this named parameter is used, then an external - /// elevator object must be passed to the algorithm using the - /// \ref elevator(Elevator&) "elevator()" function before calling - /// \ref run() or \ref init(). - /// \sa SetStandardElevator - template - struct SetElevator - : public Preflow > { - typedef Preflow > Create; - }; - - template - struct SetStandardElevatorTraits : public Traits { - typedef _Elevator Elevator; - static Elevator *createElevator(const Digraph& digraph, int max_level) { - return new Elevator(digraph, max_level); - } - }; - - /// \brief \ref named-templ-param "Named parameter" for setting - /// Elevator type with automatic allocation - /// - /// \ref named-templ-param "Named parameter" for setting Elevator - /// type with automatic allocation. - /// The Elevator should have standard constructor interface to be - /// able to automatically created by the algorithm (i.e. the - /// digraph and the maximum level should be passed to it). - /// However an external elevator object could also be passed to the - /// algorithm with the \ref elevator(Elevator&) "elevator()" function - /// before calling \ref run() or \ref init(). - /// \sa SetElevator - template - struct SetStandardElevator - : public Preflow > { - typedef Preflow > Create; - }; - - /// @} - - protected: - - Preflow() {} - - public: - - - /// \brief The constructor of the class. - /// - /// The constructor of the class. - /// \param digraph The digraph the algorithm runs on. - /// \param capacity The capacity of the arcs. - /// \param source The source node. - /// \param target The target node. - Preflow(const Digraph& digraph, const CapacityMap& capacity, - Node source, Node target) - : _graph(digraph), _capacity(&capacity), - _node_num(0), _source(source), _target(target), - _flow(0), _local_flow(false), - _level(0), _local_level(false), - _excess(0), _tolerance(), _phase() {} - - /// \brief Destructor. - /// - /// Destructor. - ~Preflow() { - destroyStructures(); - } - - /// \brief Sets the capacity map. - /// - /// Sets the capacity map. - /// \return (*this) - Preflow& capacityMap(const CapacityMap& map) { - _capacity = ↦ - return *this; - } - - /// \brief Sets the flow map. - /// - /// Sets the flow map. - /// If you don't use this function before calling \ref run() or - /// \ref init(), an instance will be allocated automatically. - /// The destructor deallocates this automatically allocated map, - /// of course. - /// \return (*this) - Preflow& flowMap(FlowMap& map) { - if (_local_flow) { - delete _flow; - _local_flow = false; - } - _flow = ↦ - return *this; - } - - /// \brief Sets the source node. - /// - /// Sets the source node. - /// \return (*this) - Preflow& source(const Node& node) { - _source = node; - return *this; - } - - /// \brief Sets the target node. - /// - /// Sets the target node. - /// \return (*this) - Preflow& target(const Node& node) { - _target = node; - return *this; - } - - /// \brief Sets the elevator used by algorithm. - /// - /// Sets the elevator used by algorithm. - /// If you don't use this function before calling \ref run() or - /// \ref init(), an instance will be allocated automatically. - /// The destructor deallocates this automatically allocated elevator, - /// of course. - /// \return (*this) - Preflow& elevator(Elevator& elevator) { - if (_local_level) { - delete _level; - _local_level = false; - } - _level = &elevator; - return *this; - } - - /// \brief Returns a const reference to the elevator. - /// - /// Returns a const reference to the elevator. - /// - /// \pre Either \ref run() or \ref init() must be called before - /// using this function. - const Elevator& elevator() { - return *_level; - } - - /// \brief Sets the tolerance used by algorithm. - /// - /// Sets the tolerance used by algorithm. - Preflow& tolerance(const Tolerance& tolerance) const { - _tolerance = tolerance; - return *this; - } - - /// \brief Returns a const reference to the tolerance. - /// - /// Returns a const reference to the tolerance. - const Tolerance& tolerance() const { - return tolerance; - } - - /// \name Execution Control - /// The simplest way to execute the preflow algorithm is to use - /// \ref run() or \ref runMinCut().\n - /// If you need more control on the initial solution or the execution, - /// first you have to call one of the \ref init() functions, then - /// \ref startFirstPhase() and if you need it \ref startSecondPhase(). - - ///@{ - - /// \brief Initializes the internal data structures. - /// - /// Initializes the internal data structures and sets the initial - /// flow to zero on each arc. - void init() { - createStructures(); - - _phase = true; - for (NodeIt n(_graph); n != INVALID; ++n) { - _excess->set(n, 0); - } - - for (ArcIt e(_graph); e != INVALID; ++e) { - _flow->set(e, 0); - } - - typename Digraph::template NodeMap reached(_graph, false); - - _level->initStart(); - _level->initAddItem(_target); - - std::vector queue; - reached.set(_source, true); - - queue.push_back(_target); - reached.set(_target, true); - while (!queue.empty()) { - _level->initNewLevel(); - std::vector nqueue; - for (int i = 0; i < int(queue.size()); ++i) { - Node n = queue[i]; - for (InArcIt e(_graph, n); e != INVALID; ++e) { - Node u = _graph.source(e); - if (!reached[u] && _tolerance.positive((*_capacity)[e])) { - reached.set(u, true); - _level->initAddItem(u); - nqueue.push_back(u); - } - } - } - queue.swap(nqueue); - } - _level->initFinish(); - - for (OutArcIt e(_graph, _source); e != INVALID; ++e) { - if (_tolerance.positive((*_capacity)[e])) { - Node u = _graph.target(e); - if ((*_level)[u] == _level->maxLevel()) continue; - _flow->set(e, (*_capacity)[e]); - _excess->set(u, (*_excess)[u] + (*_capacity)[e]); - if (u != _target && !_level->active(u)) { - _level->activate(u); - } - } - } - } - - /// \brief Initializes the internal data structures using the - /// given flow map. - /// - /// Initializes the internal data structures and sets the initial - /// flow to the given \c flowMap. The \c flowMap should contain a - /// flow or at least a preflow, i.e. at each node excluding the - /// source node the incoming flow should greater or equal to the - /// outgoing flow. - /// \return \c false if the given \c flowMap is not a preflow. - template - bool init(const FlowMap& flowMap) { - createStructures(); - - for (ArcIt e(_graph); e != INVALID; ++e) { - _flow->set(e, flowMap[e]); - } - - for (NodeIt n(_graph); n != INVALID; ++n) { - Value excess = 0; - for (InArcIt e(_graph, n); e != INVALID; ++e) { - excess += (*_flow)[e]; - } - for (OutArcIt e(_graph, n); e != INVALID; ++e) { - excess -= (*_flow)[e]; - } - if (excess < 0 && n != _source) return false; - _excess->set(n, excess); - } - - typename Digraph::template NodeMap reached(_graph, false); - - _level->initStart(); - _level->initAddItem(_target); - - std::vector queue; - reached.set(_source, true); - - queue.push_back(_target); - reached.set(_target, true); - while (!queue.empty()) { - _level->initNewLevel(); - std::vector nqueue; - for (int i = 0; i < int(queue.size()); ++i) { - Node n = queue[i]; - for (InArcIt e(_graph, n); e != INVALID; ++e) { - Node u = _graph.source(e); - if (!reached[u] && - _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { - reached.set(u, true); - _level->initAddItem(u); - nqueue.push_back(u); - } - } - for (OutArcIt e(_graph, n); e != INVALID; ++e) { - Node v = _graph.target(e); - if (!reached[v] && _tolerance.positive((*_flow)[e])) { - reached.set(v, true); - _level->initAddItem(v); - nqueue.push_back(v); - } - } - } - queue.swap(nqueue); - } - _level->initFinish(); - - for (OutArcIt e(_graph, _source); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; - if (_tolerance.positive(rem)) { - Node u = _graph.target(e); - if ((*_level)[u] == _level->maxLevel()) continue; - _flow->set(e, (*_capacity)[e]); - _excess->set(u, (*_excess)[u] + rem); - if (u != _target && !_level->active(u)) { - _level->activate(u); - } - } - } - for (InArcIt e(_graph, _source); e != INVALID; ++e) { - Value rem = (*_flow)[e]; - if (_tolerance.positive(rem)) { - Node v = _graph.source(e); - if ((*_level)[v] == _level->maxLevel()) continue; - _flow->set(e, 0); - _excess->set(v, (*_excess)[v] + rem); - if (v != _target && !_level->active(v)) { - _level->activate(v); - } - } - } - return true; - } - - /// \brief Starts the first phase of the preflow algorithm. - /// - /// The preflow algorithm consists of two phases, this method runs - /// the first phase. After the first phase the maximum flow value - /// and a minimum value cut can already be computed, although a - /// maximum flow is not yet obtained. So after calling this method - /// \ref flowValue() returns the value of a maximum flow and \ref - /// minCut() returns a minimum cut. - /// \pre One of the \ref init() functions must be called before - /// using this function. - void startFirstPhase() { - _phase = true; - - Node n = _level->highestActive(); - int level = _level->highestActiveLevel(); - while (n != INVALID) { - int num = _node_num; - - while (num > 0 && n != INVALID) { - Value excess = (*_excess)[n]; - int new_level = _level->maxLevel(); - - for (OutArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; - if (!_tolerance.positive(rem)) continue; - Node v = _graph.target(e); - if ((*_level)[v] < level) { - if (!_level->active(v) && v != _target) { - _level->activate(v); - } - if (!_tolerance.less(rem, excess)) { - _flow->set(e, (*_flow)[e] + excess); - _excess->set(v, (*_excess)[v] + excess); - excess = 0; - goto no_more_push_1; - } else { - excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(e, (*_capacity)[e]); - } - } else if (new_level > (*_level)[v]) { - new_level = (*_level)[v]; - } - } - - for (InArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_flow)[e]; - if (!_tolerance.positive(rem)) continue; - Node v = _graph.source(e); - if ((*_level)[v] < level) { - if (!_level->active(v) && v != _target) { - _level->activate(v); - } - if (!_tolerance.less(rem, excess)) { - _flow->set(e, (*_flow)[e] - excess); - _excess->set(v, (*_excess)[v] + excess); - excess = 0; - goto no_more_push_1; - } else { - excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(e, 0); - } - } else if (new_level > (*_level)[v]) { - new_level = (*_level)[v]; - } - } - - no_more_push_1: - - _excess->set(n, excess); - - if (excess != 0) { - if (new_level + 1 < _level->maxLevel()) { - _level->liftHighestActive(new_level + 1); - } else { - _level->liftHighestActiveToTop(); - } - if (_level->emptyLevel(level)) { - _level->liftToTop(level); - } - } else { - _level->deactivate(n); - } - - n = _level->highestActive(); - level = _level->highestActiveLevel(); - --num; - } - - num = _node_num * 20; - while (num > 0 && n != INVALID) { - Value excess = (*_excess)[n]; - int new_level = _level->maxLevel(); - - for (OutArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; - if (!_tolerance.positive(rem)) continue; - Node v = _graph.target(e); - if ((*_level)[v] < level) { - if (!_level->active(v) && v != _target) { - _level->activate(v); - } - if (!_tolerance.less(rem, excess)) { - _flow->set(e, (*_flow)[e] + excess); - _excess->set(v, (*_excess)[v] + excess); - excess = 0; - goto no_more_push_2; - } else { - excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(e, (*_capacity)[e]); - } - } else if (new_level > (*_level)[v]) { - new_level = (*_level)[v]; - } - } - - for (InArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_flow)[e]; - if (!_tolerance.positive(rem)) continue; - Node v = _graph.source(e); - if ((*_level)[v] < level) { - if (!_level->active(v) && v != _target) { - _level->activate(v); - } - if (!_tolerance.less(rem, excess)) { - _flow->set(e, (*_flow)[e] - excess); - _excess->set(v, (*_excess)[v] + excess); - excess = 0; - goto no_more_push_2; - } else { - excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(e, 0); - } - } else if (new_level > (*_level)[v]) { - new_level = (*_level)[v]; - } - } - - no_more_push_2: - - _excess->set(n, excess); - - if (excess != 0) { - if (new_level + 1 < _level->maxLevel()) { - _level->liftActiveOn(level, new_level + 1); - } else { - _level->liftActiveToTop(level); - } - if (_level->emptyLevel(level)) { - _level->liftToTop(level); - } - } else { - _level->deactivate(n); - } - - while (level >= 0 && _level->activeFree(level)) { - --level; - } - if (level == -1) { - n = _level->highestActive(); - level = _level->highestActiveLevel(); - } else { - n = _level->activeOn(level); - } - --num; - } - } - } - - /// \brief Starts the second phase of the preflow algorithm. - /// - /// The preflow algorithm consists of two phases, this method runs - /// the second phase. After calling one of the \ref init() functions - /// and \ref startFirstPhase() and then \ref startSecondPhase(), - /// \ref flowMap() returns a maximum flow, \ref flowValue() returns the - /// value of a maximum flow, \ref minCut() returns a minimum cut - /// \pre One of the \ref init() functions and \ref startFirstPhase() - /// must be called before using this function. - void startSecondPhase() { - _phase = false; - - typename Digraph::template NodeMap reached(_graph); - for (NodeIt n(_graph); n != INVALID; ++n) { - reached.set(n, (*_level)[n] < _level->maxLevel()); - } - - _level->initStart(); - _level->initAddItem(_source); - - std::vector queue; - queue.push_back(_source); - reached.set(_source, true); - - while (!queue.empty()) { - _level->initNewLevel(); - std::vector nqueue; - for (int i = 0; i < int(queue.size()); ++i) { - Node n = queue[i]; - for (OutArcIt e(_graph, n); e != INVALID; ++e) { - Node v = _graph.target(e); - if (!reached[v] && _tolerance.positive((*_flow)[e])) { - reached.set(v, true); - _level->initAddItem(v); - nqueue.push_back(v); - } - } - for (InArcIt e(_graph, n); e != INVALID; ++e) { - Node u = _graph.source(e); - if (!reached[u] && - _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { - reached.set(u, true); - _level->initAddItem(u); - nqueue.push_back(u); - } - } - } - queue.swap(nqueue); - } - _level->initFinish(); - - for (NodeIt n(_graph); n != INVALID; ++n) { - if (!reached[n]) { - _level->dirtyTopButOne(n); - } else if ((*_excess)[n] > 0 && _target != n) { - _level->activate(n); - } - } - - Node n; - while ((n = _level->highestActive()) != INVALID) { - Value excess = (*_excess)[n]; - int level = _level->highestActiveLevel(); - int new_level = _level->maxLevel(); - - for (OutArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; - if (!_tolerance.positive(rem)) continue; - Node v = _graph.target(e); - if ((*_level)[v] < level) { - if (!_level->active(v) && v != _source) { - _level->activate(v); - } - if (!_tolerance.less(rem, excess)) { - _flow->set(e, (*_flow)[e] + excess); - _excess->set(v, (*_excess)[v] + excess); - excess = 0; - goto no_more_push; - } else { - excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(e, (*_capacity)[e]); - } - } else if (new_level > (*_level)[v]) { - new_level = (*_level)[v]; - } - } - - for (InArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_flow)[e]; - if (!_tolerance.positive(rem)) continue; - Node v = _graph.source(e); - if ((*_level)[v] < level) { - if (!_level->active(v) && v != _source) { - _level->activate(v); - } - if (!_tolerance.less(rem, excess)) { - _flow->set(e, (*_flow)[e] - excess); - _excess->set(v, (*_excess)[v] + excess); - excess = 0; - goto no_more_push; - } else { - excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(e, 0); - } - } else if (new_level > (*_level)[v]) { - new_level = (*_level)[v]; - } - } - - no_more_push: - - _excess->set(n, excess); - - if (excess != 0) { - if (new_level + 1 < _level->maxLevel()) { - _level->liftHighestActive(new_level + 1); - } else { - // Calculation error - _level->liftHighestActiveToTop(); - } - if (_level->emptyLevel(level)) { - // Calculation error - _level->liftToTop(level); - } - } else { - _level->deactivate(n); - } - - } - } - - /// \brief Runs the preflow algorithm. - /// - /// Runs the preflow algorithm. - /// \note pf.run() is just a shortcut of the following code. - /// \code - /// pf.init(); - /// pf.startFirstPhase(); - /// pf.startSecondPhase(); - /// \endcode - void run() { - init(); - startFirstPhase(); - startSecondPhase(); - } - - /// \brief Runs the preflow algorithm to compute the minimum cut. - /// - /// Runs the preflow algorithm to compute the minimum cut. - /// \note pf.runMinCut() is just a shortcut of the following code. - /// \code - /// pf.init(); - /// pf.startFirstPhase(); - /// \endcode - void runMinCut() { - init(); - startFirstPhase(); - } - - /// @} - - /// \name Query Functions - /// The results of the preflow algorithm can be obtained using these - /// functions.\n - /// Either one of the \ref run() "run*()" functions or one of the - /// \ref startFirstPhase() "start*()" functions should be called - /// before using them. - - ///@{ - - /// \brief Returns the value of the maximum flow. - /// - /// Returns the value of the maximum flow by returning the excess - /// of the target node. This value equals to the value of - /// the maximum flow already after the first phase of the algorithm. - /// - /// \pre Either \ref run() or \ref init() must be called before - /// using this function. - Value flowValue() const { - return (*_excess)[_target]; - } - - /// \brief Returns the flow on the given arc. - /// - /// Returns the flow on the given arc. This method can - /// be called after the second phase of the algorithm. - /// - /// \pre Either \ref run() or \ref init() must be called before - /// using this function. - Value flow(const Arc& arc) const { - return (*_flow)[arc]; - } - - /// \brief Returns a const reference to the flow map. - /// - /// Returns a const reference to the arc map storing the found flow. - /// This method can be called after the second phase of the algorithm. - /// - /// \pre Either \ref run() or \ref init() must be called before - /// using this function. - const FlowMap& flowMap() { - return *_flow; - } - - /// \brief Returns \c true when the node is on the source side of the - /// minimum cut. - /// - /// Returns true when the node is on the source side of the found - /// minimum cut. This method can be called both after running \ref - /// startFirstPhase() and \ref startSecondPhase(). - /// - /// \pre Either \ref run() or \ref init() must be called before - /// using this function. - bool minCut(const Node& node) const { - return ((*_level)[node] == _level->maxLevel()) == _phase; - } - - /// \brief Gives back a minimum value cut. - /// - /// Sets \c cutMap to the characteristic vector of a minimum value - /// cut. \c cutMap should be a \ref concepts::WriteMap "writable" - /// node map with \c bool (or convertible) value type. - /// - /// This method can be called both after running \ref startFirstPhase() - /// and \ref startSecondPhase(). The result after the second phase - /// could be slightly different if inexact computation is used. - /// - /// \note This function calls \ref minCut() for each node, so it runs in - /// \f$O(n)\f$ time. - /// - /// \pre Either \ref run() or \ref init() must be called before - /// using this function. - template - void minCutMap(CutMap& cutMap) const { - for (NodeIt n(_graph); n != INVALID; ++n) { - cutMap.set(n, minCut(n)); - } - } - - /// @} - }; -} - -#endif Index: scripts/unify-sources.sh =================================================================== --- scripts/unify-sources.sh (revision 396) +++ scripts/unify-sources.sh (revision 341) @@ -131,9 +131,12 @@ echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings. - if [ $WARNED_FILES -gt 0 -o $FAILED_FILES -gt 0 ] + if [ $FAILED_FILES -gt 0 ] + then + return 1 + elif [ $WARNED_FILES -gt 0 ] then if [ "$WARNING" == 'INTERACTIVE' ] then - echo -n "Are the files with errors/warnings acceptable? (yes/no) " + echo -n "Are the files with warnings acceptable? (yes/no) " while read answer do @@ -145,5 +148,5 @@ return 1 fi - echo -n "Are the files with errors/warnings acceptable? (yes/no) " + echo -n "Are the files with warnings acceptable? (yes/no) " done elif [ "$WARNING" == 'WERROR' ] Index: test/Makefile.am =================================================================== --- test/Makefile.am (revision 389) +++ test/Makefile.am (revision 345) @@ -1,6 +1,5 @@ EXTRA_DIST += \ test/CMakeLists.txt \ - test/min_cost_flow_test.lgf \ - test/preflow_graph.lgf + test/min_cost_flow_test.lgf noinst_HEADERS += \ @@ -25,5 +24,4 @@ test/random_test \ test/path_test \ - test/preflow_test \ test/suurballe_test \ test/test_tools_fail \ @@ -50,5 +48,4 @@ test_max_matching_test_SOURCES = test/max_matching_test.cc test_path_test_SOURCES = test/path_test.cc -test_preflow_test_SOURCES = test/preflow_test.cc test_suurballe_test_SOURCES = test/suurballe_test.cc test_random_test_SOURCES = test/random_test.cc Index: test/dijkstra_test.cc =================================================================== --- test/dijkstra_test.cc (revision 397) +++ test/dijkstra_test.cc (revision 293) @@ -90,5 +90,5 @@ ::SetProcessedMap > ::SetStandardProcessedMap - ::SetOperationTraits > + ::SetOperationTraits > ::SetHeap > > ::SetStandardHeap > > Index: st/preflow_graph.lgf =================================================================== --- test/preflow_graph.lgf (revision 394) +++ (revision ) @@ -1,34 +1,0 @@ -@nodes -label -0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -@arcs - label capacity -0 1 0 20 -0 2 1 0 -1 1 2 3 -1 2 3 8 -1 3 4 8 -2 5 5 5 -3 2 6 5 -3 5 7 5 -3 6 8 5 -4 3 9 3 -5 7 10 3 -5 6 11 10 -5 8 12 10 -6 8 13 8 -8 9 14 20 -8 1 15 5 -9 5 16 5 -@attributes -source 1 -target 8 Index: st/preflow_test.cc =================================================================== --- test/preflow_test.cc (revision 394) +++ (revision ) @@ -1,213 +1,0 @@ -/* -*- mode: C++; indent-tabs-mode: nil; -*- - * - * This file is a part of LEMON, a generic C++ optimization library. - * - * Copyright (C) 2003-2008 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#include -#include - -#include "test_tools.h" -#include -#include -#include -#include -#include -#include - -using namespace lemon; - -void checkPreflowCompile() -{ - typedef int VType; - typedef concepts::Digraph Digraph; - - typedef Digraph::Node Node; - typedef Digraph::Arc Arc; - typedef concepts::ReadMap CapMap; - typedef concepts::ReadWriteMap FlowMap; - typedef concepts::WriteMap CutMap; - - typedef Elevator Elev; - typedef LinkedElevator LinkedElev; - - Digraph g; - Node n; - Arc e; - CapMap cap; - FlowMap flow; - CutMap cut; - - Preflow - ::SetFlowMap - ::SetElevator - ::SetStandardElevator - ::Create preflow_test(g,cap,n,n); - - preflow_test.capacityMap(cap); - flow = preflow_test.flowMap(); - preflow_test.flowMap(flow); - preflow_test.source(n); - preflow_test.target(n); - - preflow_test.init(); - preflow_test.init(cap); - preflow_test.startFirstPhase(); - preflow_test.startSecondPhase(); - preflow_test.run(); - preflow_test.runMinCut(); - - preflow_test.flowValue(); - preflow_test.minCut(n); - preflow_test.minCutMap(cut); - preflow_test.flow(e); - -} - -int cutValue (const SmartDigraph& g, - const SmartDigraph::NodeMap& cut, - const SmartDigraph::ArcMap& cap) { - - int c=0; - for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { - if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; - } - return c; -} - -bool checkFlow(const SmartDigraph& g, - const SmartDigraph::ArcMap& flow, - const SmartDigraph::ArcMap& cap, - SmartDigraph::Node s, SmartDigraph::Node t) { - - for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { - if (flow[e] < 0 || flow[e] > cap[e]) return false; - } - - for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { - if (n == s || n == t) continue; - int sum = 0; - for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { - sum += flow[e]; - } - for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { - sum -= flow[e]; - } - if (sum != 0) return false; - } - return true; -} - -int main() { - - typedef SmartDigraph Digraph; - - typedef Digraph::Node Node; - typedef Digraph::NodeIt NodeIt; - typedef Digraph::ArcIt ArcIt; - typedef Digraph::ArcMap CapMap; - typedef Digraph::ArcMap FlowMap; - typedef Digraph::NodeMap CutMap; - - typedef Preflow PType; - - std::string f_name; - if( getenv("srcdir") ) - f_name = std::string(getenv("srcdir")); - else f_name = "."; - f_name += "/test/preflow_graph.lgf"; - - std::ifstream file(f_name.c_str()); - - check(file, "Input file '" << f_name << "' not found."); - - Digraph g; - Node s, t; - CapMap cap(g); - DigraphReader(g,file). - arcMap("capacity", cap). - node("source",s). - node("target",t). - run(); - - PType preflow_test(g, cap, s, t); - preflow_test.run(); - - check(checkFlow(g, preflow_test.flowMap(), cap, s, t), - "The flow is not feasible."); - - CutMap min_cut(g); - preflow_test.minCutMap(min_cut); - int min_cut_value=cutValue(g,min_cut,cap); - - check(preflow_test.flowValue() == min_cut_value, - "The max flow value is not equal to the three min cut values."); - - FlowMap flow(g); - for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e]; - - int flow_value=preflow_test.flowValue(); - - for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; - preflow_test.init(flow); - preflow_test.startFirstPhase(); - - CutMap min_cut1(g); - preflow_test.minCutMap(min_cut1); - min_cut_value=cutValue(g,min_cut1,cap); - - check(preflow_test.flowValue() == min_cut_value && - min_cut_value == 2*flow_value, - "The max flow value or the min cut value is wrong."); - - preflow_test.startSecondPhase(); - - check(checkFlow(g, preflow_test.flowMap(), cap, s, t), - "The flow is not feasible."); - - CutMap min_cut2(g); - preflow_test.minCutMap(min_cut2); - min_cut_value=cutValue(g,min_cut2,cap); - - check(preflow_test.flowValue() == min_cut_value && - min_cut_value == 2*flow_value, - "The max flow value or the three min cut values were not doubled"); - - - preflow_test.flowMap(flow); - - NodeIt tmp1(g,s); - ++tmp1; - if ( tmp1 != INVALID ) s=tmp1; - - NodeIt tmp2(g,t); - ++tmp2; - if ( tmp2 != INVALID ) t=tmp2; - - preflow_test.source(s); - preflow_test.target(t); - - preflow_test.run(); - - CutMap min_cut3(g); - preflow_test.minCutMap(min_cut3); - min_cut_value=cutValue(g,min_cut3,cap); - - - check(preflow_test.flowValue() == min_cut_value, - "The max flow value or the three min cut values are incorrect."); - - return 0; -} Index: tools/Makefile.am =================================================================== --- tools/Makefile.am (revision 385) +++ tools/Makefile.am (revision 310) @@ -1,10 +1,6 @@ if WANT_TOOLS -bin_PROGRAMS += \ - tools/dimacs-to-lgf - +bin_PROGRAMS += dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh endif WANT_TOOLS - -tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc Index: ols/dimacs-to-lgf.cc =================================================================== --- tools/dimacs-to-lgf.cc (revision 387) +++ (revision ) @@ -1,149 +1,0 @@ -/* -*- mode: C++; indent-tabs-mode: nil; -*- - * - * This file is a part of LEMON, a generic C++ optimization library. - * - * Copyright (C) 2003-2008 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -///\ingroup tools -///\file -///\brief DIMACS to LGF converter. -/// -/// This program converts various DIMACS formats to the LEMON Digraph Format -/// (LGF). -/// -/// See -/// \verbatim -/// dimacs-to-lgf --help -/// \endverbatim -/// for more info on usage. -/// - -#include -#include -#include - -#include -#include -#include - -#include -#include - -using namespace std; -using namespace lemon; - - -int main(int argc, const char *argv[]) { - typedef SmartDigraph Digraph; - - typedef Digraph::Arc Arc; - typedef Digraph::Node Node; - typedef Digraph::ArcIt ArcIt; - typedef Digraph::NodeIt NodeIt; - typedef Digraph::ArcMap DoubleArcMap; - typedef Digraph::NodeMap DoubleNodeMap; - - std::string inputName; - std::string outputName; - - ArgParser ap(argc, argv); - ap.other("[INFILE [OUTFILE]]", - "If either the INFILE or OUTFILE file is missing the standard\n" - " input/output will be used instead.") - .run(); - - ifstream input; - ofstream output; - - switch(ap.files().size()) - { - case 2: - output.open(ap.files()[1].c_str()); - if (!output) { - throw IoError("Cannot open the file for writing", ap.files()[1]); - } - case 1: - input.open(ap.files()[0].c_str()); - if (!input) { - throw IoError("File cannot be found", ap.files()[0]); - } - case 0: - break; - default: - cerr << ap.commandName() << ": too many arguments\n"; - return 1; - } - istream& is = (ap.files().size()<1 ? cin : input); - ostream& os = (ap.files().size()<2 ? cout : output); - - DimacsDescriptor desc = dimacsType(is); - switch(desc.type) - { - case DimacsDescriptor::MIN: - { - Digraph digraph; - DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); - DoubleNodeMap supply(digraph); - readDimacsMin(is, digraph, lower, capacity, cost, supply, desc); - DigraphWriter(digraph, os). - nodeMap("supply", supply). - arcMap("lower", lower). - arcMap("capacity", capacity). - arcMap("cost", cost). - attribute("problem","min"). - run(); - } - break; - case DimacsDescriptor::MAX: - { - Digraph digraph; - Node s, t; - DoubleArcMap capacity(digraph); - readDimacsMax(is, digraph, capacity, s, t, desc); - DigraphWriter(digraph, os). - arcMap("capacity", capacity). - node("source", s). - node("target", t). - attribute("problem","max"). - run(); - } - break; - case DimacsDescriptor::SP: - { - Digraph digraph; - Node s; - DoubleArcMap capacity(digraph); - readDimacsSp(is, digraph, capacity, s, desc); - DigraphWriter(digraph, os). - arcMap("capacity", capacity). - node("source", s). - attribute("problem","sp"). - run(); - } - break; - case DimacsDescriptor::MAT: - { - Digraph digraph; - readDimacsMat(is, digraph,desc); - DigraphWriter(digraph, os). - attribute("problem","mat"). - run(); - } - break; - default: - break; - } - return 0; -}