lemon/network_simplex.h
changeset 831 cc9e0c15d747
parent 812 4b1b378823dc
child 840 2914b6f0fde0
equal deleted inserted replaced
24:e623f11c9e8f 25:29f2d3636085
   192     // Data structures for storing the digraph
   192     // Data structures for storing the digraph
   193     IntNodeMap _node_id;
   193     IntNodeMap _node_id;
   194     IntArcMap _arc_id;
   194     IntArcMap _arc_id;
   195     IntVector _source;
   195     IntVector _source;
   196     IntVector _target;
   196     IntVector _target;
       
   197     bool _arc_mixing;
   197 
   198 
   198     // Node and arc data
   199     // Node and arc data
   199     ValueVector _lower;
   200     ValueVector _lower;
   200     ValueVector _upper;
   201     ValueVector _upper;
   201     ValueVector _cap;
   202     ValueVector _cap;
   631     /// mixed order in the internal data structure. 
   632     /// mixed order in the internal data structure. 
   632     /// In special cases, it could lead to better overall performance,
   633     /// In special cases, it could lead to better overall performance,
   633     /// but it is usually slower. Therefore it is disabled by default.
   634     /// but it is usually slower. Therefore it is disabled by default.
   634     NetworkSimplex(const GR& graph, bool arc_mixing = false) :
   635     NetworkSimplex(const GR& graph, bool arc_mixing = false) :
   635       _graph(graph), _node_id(graph), _arc_id(graph),
   636       _graph(graph), _node_id(graph), _arc_id(graph),
       
   637       _arc_mixing(arc_mixing),
   636       MAX(std::numeric_limits<Value>::max()),
   638       MAX(std::numeric_limits<Value>::max()),
   637       INF(std::numeric_limits<Value>::has_infinity ?
   639       INF(std::numeric_limits<Value>::has_infinity ?
   638           std::numeric_limits<Value>::infinity() : MAX)
   640           std::numeric_limits<Value>::infinity() : MAX)
   639     {
   641     {
   640       // Check the number types
   642       // Check the number types
   641       LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
   643       LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
   642         "The flow type of NetworkSimplex must be signed");
   644         "The flow type of NetworkSimplex must be signed");
   643       LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
   645       LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
   644         "The cost type of NetworkSimplex must be signed");
   646         "The cost type of NetworkSimplex must be signed");
   645         
   647         
   646       // Resize vectors
   648       // Reset data structures
   647       _node_num = countNodes(_graph);
       
   648       _arc_num = countArcs(_graph);
       
   649       int all_node_num = _node_num + 1;
       
   650       int max_arc_num = _arc_num + 2 * _node_num;
       
   651 
       
   652       _source.resize(max_arc_num);
       
   653       _target.resize(max_arc_num);
       
   654 
       
   655       _lower.resize(_arc_num);
       
   656       _upper.resize(_arc_num);
       
   657       _cap.resize(max_arc_num);
       
   658       _cost.resize(max_arc_num);
       
   659       _supply.resize(all_node_num);
       
   660       _flow.resize(max_arc_num);
       
   661       _pi.resize(all_node_num);
       
   662 
       
   663       _parent.resize(all_node_num);
       
   664       _pred.resize(all_node_num);
       
   665       _forward.resize(all_node_num);
       
   666       _thread.resize(all_node_num);
       
   667       _rev_thread.resize(all_node_num);
       
   668       _succ_num.resize(all_node_num);
       
   669       _last_succ.resize(all_node_num);
       
   670       _state.resize(max_arc_num);
       
   671 
       
   672       // Copy the graph
       
   673       int i = 0;
       
   674       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
       
   675         _node_id[n] = i;
       
   676       }
       
   677       if (arc_mixing) {
       
   678         // Store the arcs in a mixed order
       
   679         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
       
   680         int i = 0, j = 0;
       
   681         for (ArcIt a(_graph); a != INVALID; ++a) {
       
   682           _arc_id[a] = i;
       
   683           _source[i] = _node_id[_graph.source(a)];
       
   684           _target[i] = _node_id[_graph.target(a)];
       
   685           if ((i += k) >= _arc_num) i = ++j;
       
   686         }
       
   687       } else {
       
   688         // Store the arcs in the original order
       
   689         int i = 0;
       
   690         for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
       
   691           _arc_id[a] = i;
       
   692           _source[i] = _node_id[_graph.source(a)];
       
   693           _target[i] = _node_id[_graph.target(a)];
       
   694         }
       
   695       }
       
   696       
       
   697       // Reset parameters
       
   698       reset();
   649       reset();
   699     }
   650     }
   700 
   651 
   701     /// \name Parameters
   652     /// \name Parameters
   702     /// The parameters of the algorithm can be specified using these
   653     /// The parameters of the algorithm can be specified using these
   840     ///   NetworkSimplex<ListDigraph> ns(graph);
   791     ///   NetworkSimplex<ListDigraph> ns(graph);
   841     ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
   792     ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
   842     ///     .supplyMap(sup).run();
   793     ///     .supplyMap(sup).run();
   843     /// \endcode
   794     /// \endcode
   844     ///
   795     ///
   845     /// This function can be called more than once. All the parameters
   796     /// This function can be called more than once. All the given parameters
   846     /// that have been given are kept for the next call, unless
   797     /// are kept for the next call, unless \ref resetParams() or \ref reset()
   847     /// \ref reset() is called, thus only the modified parameters
   798     /// is used, thus only the modified parameters have to be set again.
   848     /// have to be set again. See \ref reset() for examples.
   799     /// If the underlying digraph was also modified after the construction
   849     /// However, the underlying digraph must not be modified after this
   800     /// of the class (or the last \ref reset() call), then the \ref reset()
   850     /// class have been constructed, since it copies and extends the graph.
   801     /// function must be called.
   851     ///
   802     ///
   852     /// \param pivot_rule The pivot rule that will be used during the
   803     /// \param pivot_rule The pivot rule that will be used during the
   853     /// algorithm. For more information, see \ref PivotRule.
   804     /// algorithm. For more information, see \ref PivotRule.
   854     ///
   805     ///
   855     /// \return \c INFEASIBLE if no feasible flow exists,
   806     /// \return \c INFEASIBLE if no feasible flow exists,
   859     /// \n \c UNBOUNDED if the objective function of the problem is
   810     /// \n \c UNBOUNDED if the objective function of the problem is
   860     /// unbounded, i.e. there is a directed cycle having negative total
   811     /// unbounded, i.e. there is a directed cycle having negative total
   861     /// cost and infinite upper bound.
   812     /// cost and infinite upper bound.
   862     ///
   813     ///
   863     /// \see ProblemType, PivotRule
   814     /// \see ProblemType, PivotRule
       
   815     /// \see resetParams(), reset()
   864     ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
   816     ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
   865       if (!init()) return INFEASIBLE;
   817       if (!init()) return INFEASIBLE;
   866       return start(pivot_rule);
   818       return start(pivot_rule);
   867     }
   819     }
   868 
   820 
   870     ///
   822     ///
   871     /// This function resets all the paramaters that have been given
   823     /// This function resets all the paramaters that have been given
   872     /// before using functions \ref lowerMap(), \ref upperMap(),
   824     /// before using functions \ref lowerMap(), \ref upperMap(),
   873     /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
   825     /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
   874     ///
   826     ///
   875     /// It is useful for multiple run() calls. If this function is not
   827     /// It is useful for multiple \ref run() calls. Basically, all the given
   876     /// used, all the parameters given before are kept for the next
   828     /// parameters are kept for the next \ref run() call, unless
   877     /// \ref run() call.
   829     /// \ref resetParams() or \ref reset() is used.
   878     /// However, the underlying digraph must not be modified after this
   830     /// If the underlying digraph was also modified after the construction
   879     /// class have been constructed, since it copies and extends the graph.
   831     /// of the class or the last \ref reset() call, then the \ref reset()
       
   832     /// function must be used, otherwise \ref resetParams() is sufficient.
   880     ///
   833     ///
   881     /// For example,
   834     /// For example,
   882     /// \code
   835     /// \code
   883     ///   NetworkSimplex<ListDigraph> ns(graph);
   836     ///   NetworkSimplex<ListDigraph> ns(graph);
   884     ///
   837     ///
   885     ///   // First run
   838     ///   // First run
   886     ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
   839     ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
   887     ///     .supplyMap(sup).run();
   840     ///     .supplyMap(sup).run();
   888     ///
   841     ///
   889     ///   // Run again with modified cost map (reset() is not called,
   842     ///   // Run again with modified cost map (resetParams() is not called,
   890     ///   // so only the cost map have to be set again)
   843     ///   // so only the cost map have to be set again)
   891     ///   cost[e] += 100;
   844     ///   cost[e] += 100;
   892     ///   ns.costMap(cost).run();
   845     ///   ns.costMap(cost).run();
   893     ///
   846     ///
   894     ///   // Run again from scratch using reset()
   847     ///   // Run again from scratch using resetParams()
   895     ///   // (the lower bounds will be set to zero on all arcs)
   848     ///   // (the lower bounds will be set to zero on all arcs)
   896     ///   ns.reset();
   849     ///   ns.resetParams();
   897     ///   ns.upperMap(capacity).costMap(cost)
   850     ///   ns.upperMap(capacity).costMap(cost)
   898     ///     .supplyMap(sup).run();
   851     ///     .supplyMap(sup).run();
   899     /// \endcode
   852     /// \endcode
   900     ///
   853     ///
   901     /// \return <tt>(*this)</tt>
   854     /// \return <tt>(*this)</tt>
   902     NetworkSimplex& reset() {
   855     ///
       
   856     /// \see reset(), run()
       
   857     NetworkSimplex& resetParams() {
   903       for (int i = 0; i != _node_num; ++i) {
   858       for (int i = 0; i != _node_num; ++i) {
   904         _supply[i] = 0;
   859         _supply[i] = 0;
   905       }
   860       }
   906       for (int i = 0; i != _arc_num; ++i) {
   861       for (int i = 0; i != _arc_num; ++i) {
   907         _lower[i] = 0;
   862         _lower[i] = 0;
   911       _have_lower = false;
   866       _have_lower = false;
   912       _stype = GEQ;
   867       _stype = GEQ;
   913       return *this;
   868       return *this;
   914     }
   869     }
   915 
   870 
       
   871     /// \brief Reset the internal data structures and all the parameters
       
   872     /// that have been given before.
       
   873     ///
       
   874     /// This function resets the internal data structures and all the
       
   875     /// paramaters that have been given before using functions \ref lowerMap(),
       
   876     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
       
   877     /// \ref supplyType().
       
   878     ///
       
   879     /// It is useful for multiple \ref run() calls. Basically, all the given
       
   880     /// parameters are kept for the next \ref run() call, unless
       
   881     /// \ref resetParams() or \ref reset() is used.
       
   882     /// If the underlying digraph was also modified after the construction
       
   883     /// of the class or the last \ref reset() call, then the \ref reset()
       
   884     /// function must be used, otherwise \ref resetParams() is sufficient.
       
   885     ///
       
   886     /// See \ref resetParams() for examples.
       
   887     ///
       
   888     /// \return <tt>(*this)</tt>
       
   889     ///
       
   890     /// \see resetParams(), run()
       
   891     NetworkSimplex& reset() {
       
   892       // Resize vectors
       
   893       _node_num = countNodes(_graph);
       
   894       _arc_num = countArcs(_graph);
       
   895       int all_node_num = _node_num + 1;
       
   896       int max_arc_num = _arc_num + 2 * _node_num;
       
   897 
       
   898       _source.resize(max_arc_num);
       
   899       _target.resize(max_arc_num);
       
   900 
       
   901       _lower.resize(_arc_num);
       
   902       _upper.resize(_arc_num);
       
   903       _cap.resize(max_arc_num);
       
   904       _cost.resize(max_arc_num);
       
   905       _supply.resize(all_node_num);
       
   906       _flow.resize(max_arc_num);
       
   907       _pi.resize(all_node_num);
       
   908 
       
   909       _parent.resize(all_node_num);
       
   910       _pred.resize(all_node_num);
       
   911       _forward.resize(all_node_num);
       
   912       _thread.resize(all_node_num);
       
   913       _rev_thread.resize(all_node_num);
       
   914       _succ_num.resize(all_node_num);
       
   915       _last_succ.resize(all_node_num);
       
   916       _state.resize(max_arc_num);
       
   917 
       
   918       // Copy the graph
       
   919       int i = 0;
       
   920       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
       
   921         _node_id[n] = i;
       
   922       }
       
   923       if (_arc_mixing) {
       
   924         // Store the arcs in a mixed order
       
   925         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
       
   926         int i = 0, j = 0;
       
   927         for (ArcIt a(_graph); a != INVALID; ++a) {
       
   928           _arc_id[a] = i;
       
   929           _source[i] = _node_id[_graph.source(a)];
       
   930           _target[i] = _node_id[_graph.target(a)];
       
   931           if ((i += k) >= _arc_num) i = ++j;
       
   932         }
       
   933       } else {
       
   934         // Store the arcs in the original order
       
   935         int i = 0;
       
   936         for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
       
   937           _arc_id[a] = i;
       
   938           _source[i] = _node_id[_graph.source(a)];
       
   939           _target[i] = _node_id[_graph.target(a)];
       
   940         }
       
   941       }
       
   942       
       
   943       // Reset parameters
       
   944       resetParams();
       
   945       return *this;
       
   946     }
       
   947     
   916     /// @}
   948     /// @}
   917 
   949 
   918     /// \name Query Functions
   950     /// \name Query Functions
   919     /// The results of the algorithm can be obtained using these
   951     /// The results of the algorithm can be obtained using these
   920     /// functions.\n
   952     /// functions.\n