Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/preflow.h
changeset 2019 e70c1f6849bc
parent 1993 2115143eceea
child 2024 4ab8a25def3c
equal deleted inserted replaced
11:5e50aaeb53f4 12:09110be0a48d 
    60   ///\param CapacityMap The capacity map type.
 
    60   ///\param CapacityMap The capacity map type.
 
    61   ///\param FlowMap The flow map type.
 
    61   ///\param FlowMap The flow map type.
 
    62   ///
 
    62   ///
 
    63   ///\author Jacint Szabo 
    63   ///\author Jacint Szabo 
    64   ///\todo Second template parameter is superfluous
 
    64   ///\todo Second template parameter is superfluous
 
       
    65   ///\todo Using tolerance
 
    65   template <typename Graph, typename Num,
 
    66   template <typename Graph, typename Num,
 
    66 	    typename CapacityMap=typename Graph::template EdgeMap<Num>,
 
    67 	    typename CapacityMap=typename Graph::template EdgeMap<Num>,
 
    67             typename FlowMap=typename Graph::template EdgeMap<Num>,
 
    68             typename FlowMap=typename Graph::template EdgeMap<Num>,
 
    68 	    typename TOL=Tolerance<Num> >
 
    69 	    typename Tolerance=Tolerance<Num> >
 
    69   class Preflow {
 
    70   class Preflow {
 
    70   protected:
 
    71   protected:
 
    71     typedef typename Graph::Node Node;
 
    72     typedef typename Graph::Node Node;
 
    72     typedef typename Graph::NodeIt NodeIt;
 
    73     typedef typename Graph::NodeIt NodeIt;
 
    73     typedef typename Graph::EdgeIt EdgeIt;
 
    74     typedef typename Graph::EdgeIt EdgeIt;
 
    81     Node _source;
 
    82     Node _source;
 
    82     Node _target;
 
    83     Node _target;
 
    83     const CapacityMap* _capacity;
 
    84     const CapacityMap* _capacity;
 
    84     FlowMap* _flow;
 
    85     FlowMap* _flow;
 
    85 
    86 
    86     TOL surely;
 
    87     Tolerance _surely;
 
    87     
    88     
    88     int _node_num;      //the number of nodes of G
 
    89     int _node_num;      //the number of nodes of G
 
    89     
    90     
    90     typename Graph::template NodeMap<int> level;  
    91     typename Graph::template NodeMap<int> level;  
    91     typename Graph::template NodeMap<Num> excess;
 
    92     typename Graph::template NodeMap<Num> excess;
 
   158     ///Except the graph, all of these parameters can be reset by
 
   159     ///Except the graph, all of these parameters can be reset by
 
   159     ///calling \ref source, \ref target, \ref capacityMap and \ref
 
   160     ///calling \ref source, \ref target, \ref capacityMap and \ref
 
   160     ///flowMap, resp.
 
   161     ///flowMap, resp.
 
   161       Preflow(const Graph& _gr, Node _s, Node _t, 
   162       Preflow(const Graph& _gr, Node _s, Node _t, 
   162 	      const CapacityMap& _cap, FlowMap& _f,
 
   163 	      const CapacityMap& _cap, FlowMap& _f,
 
   163 	      const TOL &tol=TOL()) :
 
   164 	      const Tolerance &_sr=Tolerance()) :
 
   164 	_g(&_gr), _source(_s), _target(_t), _capacity(&_cap),
 
   165 	_g(&_gr), _source(_s), _target(_t), _capacity(&_cap),
 
   165 	_flow(&_f), surely(tol),
 
   166 	_flow(&_f), _surely(_sr),
 
   166 	_node_num(countNodes(_gr)), level(_gr), excess(_gr,0), 
   167 	_node_num(countNodes(_gr)), level(_gr), excess(_gr,0), 
   167 	flow_prop(NO_FLOW), status(AFTER_NOTHING) { 
   168 	flow_prop(NO_FLOW), status(AFTER_NOTHING) { 
   168 	if ( _source==_target )
 
   169 	if ( _source==_target )
 
   169 	  throw InvalidArgument();
 
   170 	  throw InvalidArgument();
 
   170       }
 
   171       }
 
   171     
   172     
   172     ///Give a reference to the tolerance handler class
 
   173     ///Give a reference to the tolerance handler class
 
   173 
   174 
   174     ///Give a reference to the tolerance handler class
 
   175     ///Give a reference to the tolerance handler class
 
   175     ///\sa Tolerance
 
   176     ///\sa Tolerance
 
   176     TOL &tolerance() { return surely; }
 
   177     Tolerance &tolerance() { return _surely; }
 
   177 
   178 
   178     ///Runs the preflow algorithm.  
   179     ///Runs the preflow algorithm.  
   179 
   180 
   180     ///Runs the preflow algorithm.
 
   181     ///Runs the preflow algorithm.
 
   181     ///
 
   182     ///
lemon-0.x