84 /// \c CapacityMap::Value and \c CapacityMap::Value must be |
84 /// \c CapacityMap::Value and \c CapacityMap::Value must be |
85 /// convertible to \c SupplyMap::Value. |
85 /// convertible to \c SupplyMap::Value. |
86 /// |
86 /// |
87 /// \author Peter Kovacs |
87 /// \author Peter Kovacs |
88 |
88 |
89 template < typename Graph, |
89 template < typename Graph, |
90 typename LowerMap = typename Graph::template EdgeMap<int>, |
90 typename LowerMap = typename Graph::template EdgeMap<int>, |
91 typename CapacityMap = LowerMap, |
91 typename CapacityMap = LowerMap, |
92 typename CostMap = typename Graph::template EdgeMap<int>, |
92 typename CostMap = typename Graph::template EdgeMap<int>, |
93 typename SupplyMap = typename Graph::template NodeMap |
93 typename SupplyMap = typename Graph::template NodeMap |
94 <typename CapacityMap::Value> > |
94 <typename CapacityMap::Value> > |
95 class CycleCanceling |
95 class CycleCanceling |
96 { |
96 { |
97 typedef typename Graph::Node Node; |
97 typedef typename Graph::Node Node; |
98 typedef typename Graph::NodeIt NodeIt; |
98 typedef typename Graph::NodeIt NodeIt; |
99 typedef typename Graph::Edge Edge; |
99 typedef typename Graph::Edge Edge; |
321 Supply sum = 0; |
321 Supply sum = 0; |
322 for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n]; |
322 for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n]; |
323 if (sum != 0) return false; |
323 if (sum != 0) return false; |
324 |
324 |
325 // Finding a feasible flow |
325 // Finding a feasible flow |
326 Circulation< Graph, Capacity, ConstMap<Edge, Capacity>, |
326 Circulation< Graph, ConstMap<Edge, Capacity>, CapacityRefMap, |
327 CapacityRefMap, SupplyMap >::DefFlowMap<FlowMap>::Create |
327 SupplyMap > |
328 circulation( graph, constMap<Edge>((Capacity)0), |
328 circulation( graph, constMap<Edge>((Capacity)0), capacity, |
329 capacity, supply); |
329 supply ); |
330 circulation.flowMap(flowMap); |
330 circulation.flowMap(flow); |
331 return circulation.run(); |
331 return circulation.run() == -1; |
332 } |
332 } |
333 |
333 |
334 #ifdef LIMITED_CYCLE_CANCELING |
334 #ifdef LIMITED_CYCLE_CANCELING |
335 /// \brief Executes a cycle-canceling algorithm using |
335 /// \brief Executes a cycle-canceling algorithm using |
336 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited |
336 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited |