Added the function isFinite(), and replaced the calls to finite() with it.
This was necessary because finite() is not a standard function. Neither can
we use its standard counterpart isfinite(), because it was introduced only
in C99, and therefore it is not supplied by all C++ implementations.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_NETWORK_SIMPLEX_H
20 #define LEMON_NETWORK_SIMPLEX_H
22 /// \ingroup min_cost_flow
25 /// \brief The network simplex algorithm for finding a minimum cost
29 #include <lemon/smart_graph.h>
30 #include <lemon/graph_utils.h>
32 /// \brief The pivot rule used in the algorithm.
33 //#define FIRST_ELIGIBLE_PIVOT
34 //#define BEST_ELIGIBLE_PIVOT
35 #define EDGE_BLOCK_PIVOT
36 //#define CANDIDATE_LIST_PIVOT
37 //#define SORTED_LIST_PIVOT
39 //#define _DEBUG_ITER_
42 /// \brief State constant for edges at their lower bounds.
44 /// \brief State constant for edges in the spanning tree.
46 /// \brief State constant for edges at their upper bounds.
49 #ifdef EDGE_BLOCK_PIVOT
51 /// \brief Lower bound for the size of blocks.
52 #define MIN_BLOCK_SIZE 10
55 #ifdef CANDIDATE_LIST_PIVOT
57 #define LIST_LENGTH_DIV 50
58 #define MINOR_LIMIT_DIV 200
61 #ifdef SORTED_LIST_PIVOT
64 #define LIST_LENGTH_DIV 100
70 /// \addtogroup min_cost_flow
73 /// \brief Implementation of the network simplex algorithm for
74 /// finding a minimum cost flow.
76 /// \ref lemon::NetworkSimplex "NetworkSimplex" implements the
77 /// network simplex algorithm for finding a minimum cost flow.
79 /// \param Graph The directed graph type the algorithm runs on.
80 /// \param LowerMap The type of the lower bound map.
81 /// \param CapacityMap The type of the capacity (upper bound) map.
82 /// \param CostMap The type of the cost (length) map.
83 /// \param SupplyMap The type of the supply map.
86 /// - Edge capacities and costs should be nonnegative integers.
87 /// However \c CostMap::Value should be signed type.
88 /// - Supply values should be integers.
89 /// - \c LowerMap::Value must be convertible to
90 /// \c CapacityMap::Value and \c CapacityMap::Value must be
91 /// convertible to \c SupplyMap::Value.
93 /// \author Peter Kovacs
95 template < typename Graph,
96 typename LowerMap = typename Graph::template EdgeMap<int>,
97 typename CapacityMap = LowerMap,
98 typename CostMap = typename Graph::template EdgeMap<int>,
99 typename SupplyMap = typename Graph::template NodeMap
100 <typename CapacityMap::Value> >
103 typedef typename LowerMap::Value Lower;
104 typedef typename CapacityMap::Value Capacity;
105 typedef typename CostMap::Value Cost;
106 typedef typename SupplyMap::Value Supply;
108 typedef SmartGraph SGraph;
109 typedef typename SGraph::Node Node;
110 typedef typename SGraph::NodeIt NodeIt;
111 typedef typename SGraph::Edge Edge;
112 typedef typename SGraph::EdgeIt EdgeIt;
113 typedef typename SGraph::InEdgeIt InEdgeIt;
114 typedef typename SGraph::OutEdgeIt OutEdgeIt;
116 typedef typename SGraph::template EdgeMap<Lower> SLowerMap;
117 typedef typename SGraph::template EdgeMap<Capacity> SCapacityMap;
118 typedef typename SGraph::template EdgeMap<Cost> SCostMap;
119 typedef typename SGraph::template NodeMap<Supply> SSupplyMap;
120 typedef typename SGraph::template NodeMap<Cost> SPotentialMap;
122 typedef typename SGraph::template NodeMap<int> IntNodeMap;
123 typedef typename SGraph::template NodeMap<bool> BoolNodeMap;
124 typedef typename SGraph::template NodeMap<Node> NodeNodeMap;
125 typedef typename SGraph::template NodeMap<Edge> EdgeNodeMap;
126 typedef typename SGraph::template EdgeMap<int> IntEdgeMap;
128 typedef typename Graph::template NodeMap<Node> NodeRefMap;
129 typedef typename Graph::template EdgeMap<Edge> EdgeRefMap;
133 /// \brief The type of the flow map.
134 typedef typename Graph::template EdgeMap<Capacity> FlowMap;
135 /// \brief The type of the potential map.
136 typedef typename Graph::template NodeMap<Cost> PotentialMap;
140 /// \brief Map adaptor class for handling reduced edge costs.
141 class ReducedCostMap : public MapBase<Edge, Cost>
146 const SCostMap &cost_map;
147 const SPotentialMap &pot_map;
151 typedef typename MapBase<Edge, Cost>::Value Value;
152 typedef typename MapBase<Edge, Cost>::Key Key;
154 ReducedCostMap( const SGraph &_gr,
156 const SPotentialMap &_pm ) :
157 gr(_gr), cost_map(_cm), pot_map(_pm) {}
159 Value operator[](const Key &e) const {
160 return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
163 }; //class ReducedCostMap
167 /// \brief The directed graph the algorithm runs on.
169 /// \brief The original graph.
170 const Graph &graph_ref;
171 /// \brief The original lower bound map.
172 const LowerMap *lower;
173 /// \brief The capacity map.
174 SCapacityMap capacity;
175 /// \brief The cost map.
177 /// \brief The supply map.
179 /// \brief The reduced cost map.
180 ReducedCostMap red_cost;
181 /// \brief The sum of supply values equals zero.
184 /// \brief The edge map of the current flow.
186 /// \brief The edge map of the found flow on the original graph.
188 /// \brief The potential node map.
189 SPotentialMap potential;
190 /// \brief The potential node map on the original graph.
191 PotentialMap potential_result;
193 /// \brief Node reference for the original graph.
195 /// \brief Edge reference for the original graph.
198 /// \brief The depth node map of the spanning tree structure.
200 /// \brief The parent node map of the spanning tree structure.
202 /// \brief The pred_edge node map of the spanning tree structure.
203 EdgeNodeMap pred_edge;
204 /// \brief The thread node map of the spanning tree structure.
206 /// \brief The forward node map of the spanning tree structure.
208 /// \brief The state edge map.
212 #ifdef EDGE_BLOCK_PIVOT
213 /// \brief The size of blocks for the "Edge Block" pivot rule.
216 #ifdef CANDIDATE_LIST_PIVOT
217 /// \brief The list of candidate edges for the "Candidate List"
219 std::vector<Edge> candidates;
220 /// \brief The maximum length of the edge list for the
221 /// "Candidate List" pivot rule.
223 /// \brief The maximum number of minor iterations between two major
226 /// \brief The number of minor iterations.
229 #ifdef SORTED_LIST_PIVOT
230 /// \brief The list of candidate edges for the "Sorted List"
232 std::vector<Edge> candidates;
233 /// \brief The maximum length of the edge list for the
234 /// "Sorted List" pivot rule.
239 // Root node of the starting spanning tree.
241 // The entering edge of the current pivot iteration.
243 // Temporary nodes used in the current pivot iteration.
244 Node join, u_in, v_in, u_out, v_out;
245 Node right, first, second, last;
246 Node stem, par_stem, new_stem;
247 // The maximum augment amount along the cycle in the current pivot
253 /// \brief General constructor of the class (with lower bounds).
255 /// General constructor of the class (with lower bounds).
257 /// \param _graph The directed graph the algorithm runs on.
258 /// \param _lower The lower bounds of the edges.
259 /// \param _capacity The capacities (upper bounds) of the edges.
260 /// \param _cost The cost (length) values of the edges.
261 /// \param _supply The supply values of the nodes (signed).
262 NetworkSimplex( const Graph &_graph,
263 const LowerMap &_lower,
264 const CapacityMap &_capacity,
265 const CostMap &_cost,
266 const SupplyMap &_supply ) :
267 graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph),
268 supply(graph), flow(graph), flow_result(_graph), potential(graph),
269 potential_result(_graph), depth(graph), parent(graph),
270 pred_edge(graph), thread(graph), forward(graph), state(graph),
271 node_ref(graph_ref), edge_ref(graph_ref),
272 red_cost(graph, cost, potential)
274 // Checking the sum of supply values
276 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
278 if (!(valid_supply = sum == 0)) return;
280 // Copying graph_ref to graph
281 graph.reserveNode(countNodes(graph_ref) + 1);
282 graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref));
283 copyGraph(graph, graph_ref)
284 .edgeMap(cost, _cost)
289 // Removing nonzero lower bounds
290 for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) {
291 capacity[edge_ref[e]] = _capacity[e] - _lower[e];
293 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) {
294 Supply s = _supply[n];
295 for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
297 for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
299 supply[node_ref[n]] = s;
303 /// \brief General constructor of the class (without lower bounds).
305 /// General constructor of the class (without lower bounds).
307 /// \param _graph The directed graph the algorithm runs on.
308 /// \param _capacity The capacities (upper bounds) of the edges.
309 /// \param _cost The cost (length) values of the edges.
310 /// \param _supply The supply values of the nodes (signed).
311 NetworkSimplex( const Graph &_graph,
312 const CapacityMap &_capacity,
313 const CostMap &_cost,
314 const SupplyMap &_supply ) :
315 graph_ref(_graph), lower(NULL), capacity(graph), cost(graph),
316 supply(graph), flow(graph), flow_result(_graph), potential(graph),
317 potential_result(_graph), depth(graph), parent(graph),
318 pred_edge(graph), thread(graph), forward(graph), state(graph),
319 node_ref(graph_ref), edge_ref(graph_ref),
320 red_cost(graph, cost, potential)
322 // Checking the sum of supply values
324 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
326 if (!(valid_supply = sum == 0)) return;
328 // Copying graph_ref to graph
329 copyGraph(graph, graph_ref)
330 .edgeMap(capacity, _capacity)
331 .edgeMap(cost, _cost)
332 .nodeMap(supply, _supply)
338 /// \brief Simple constructor of the class (with lower bounds).
340 /// Simple constructor of the class (with lower bounds).
342 /// \param _graph The directed graph the algorithm runs on.
343 /// \param _lower The lower bounds of the edges.
344 /// \param _capacity The capacities (upper bounds) of the edges.
345 /// \param _cost The cost (length) values of the edges.
346 /// \param _s The source node.
347 /// \param _t The target node.
348 /// \param _flow_value The required amount of flow from node \c _s
349 /// to node \c _t (i.e. the supply of \c _s and the demand of
351 NetworkSimplex( const Graph &_graph,
352 const LowerMap &_lower,
353 const CapacityMap &_capacity,
354 const CostMap &_cost,
355 typename Graph::Node _s,
356 typename Graph::Node _t,
357 typename SupplyMap::Value _flow_value ) :
358 graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph),
359 supply(graph), flow(graph), flow_result(_graph), potential(graph),
360 potential_result(_graph), depth(graph), parent(graph),
361 pred_edge(graph), thread(graph), forward(graph), state(graph),
362 node_ref(graph_ref), edge_ref(graph_ref),
363 red_cost(graph, cost, potential)
365 // Copying graph_ref to graph
366 copyGraph(graph, graph_ref)
367 .edgeMap(cost, _cost)
372 // Removing nonzero lower bounds
373 for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) {
374 capacity[edge_ref[e]] = _capacity[e] - _lower[e];
376 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) {
378 if (n == _s) s = _flow_value;
379 if (n == _t) s = -_flow_value;
380 for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
382 for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
384 supply[node_ref[n]] = s;
389 /// \brief Simple constructor of the class (without lower bounds).
391 /// Simple constructor of the class (without lower bounds).
393 /// \param _graph The directed graph the algorithm runs on.
394 /// \param _capacity The capacities (upper bounds) of the edges.
395 /// \param _cost The cost (length) values of the edges.
396 /// \param _s The source node.
397 /// \param _t The target node.
398 /// \param _flow_value The required amount of flow from node \c _s
399 /// to node \c _t (i.e. the supply of \c _s and the demand of
401 NetworkSimplex( const Graph &_graph,
402 const CapacityMap &_capacity,
403 const CostMap &_cost,
404 typename Graph::Node _s,
405 typename Graph::Node _t,
406 typename SupplyMap::Value _flow_value ) :
407 graph_ref(_graph), lower(NULL), capacity(graph), cost(graph),
408 supply(graph, 0), flow(graph), flow_result(_graph), potential(graph),
409 potential_result(_graph), depth(graph), parent(graph),
410 pred_edge(graph), thread(graph), forward(graph), state(graph),
411 node_ref(graph_ref), edge_ref(graph_ref),
412 red_cost(graph, cost, potential)
414 // Copying graph_ref to graph
415 copyGraph(graph, graph_ref)
416 .edgeMap(capacity, _capacity)
417 .edgeMap(cost, _cost)
421 supply[node_ref[_s]] = _flow_value;
422 supply[node_ref[_t]] = -_flow_value;
426 /// \brief Returns a const reference to the flow map.
428 /// Returns a const reference to the flow map.
430 /// \pre \ref run() must be called before using this function.
431 const FlowMap& flowMap() const {
435 /// \brief Returns a const reference to the potential map (the dual
438 /// Returns a const reference to the potential map (the dual
441 /// \pre \ref run() must be called before using this function.
442 const PotentialMap& potentialMap() const {
443 return potential_result;
446 /// \brief Returns the total cost of the found flow.
448 /// Returns the total cost of the found flow. The complexity of the
449 /// function is \f$ O(e) \f$.
451 /// \pre \ref run() must be called before using this function.
452 Cost totalCost() const {
454 for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
455 c += flow_result[e] * cost[edge_ref[e]];
459 /// \brief Runs the algorithm.
461 /// Runs the algorithm.
463 /// \return \c true if a feasible flow can be found.
465 return init() && start();
470 /// \brief Extends the underlaying graph and initializes all the
471 /// node and edge maps.
473 if (!valid_supply) return false;
475 // Initializing state and flow maps
476 for (EdgeIt e(graph); e != INVALID; ++e) {
481 // Adding an artificial root node to the graph
482 root = graph.addNode();
483 parent[root] = INVALID;
484 pred_edge[root] = INVALID;
489 // Adding artificial edges to the graph and initializing the node
490 // maps of the spanning tree data structure
494 Cost max_cost = std::numeric_limits<Cost>::max() / 4;
495 for (NodeIt u(graph); u != INVALID; ++u) {
496 if (u == root) continue;
502 if (supply[u] >= 0) {
503 e = graph.addEdge(u, root);
506 potential[u] = max_cost;
508 e = graph.addEdge(root, u);
509 flow[e] = -supply[u];
511 potential[u] = -max_cost;
514 capacity[e] = std::numeric_limits<Capacity>::max();
520 #ifdef EDGE_BLOCK_PIVOT
521 // Initializing block_size for the edge block pivot rule
522 int edge_num = countEdges(graph);
523 block_size = 2 * int(sqrt(countEdges(graph)));
524 if (block_size < MIN_BLOCK_SIZE) block_size = MIN_BLOCK_SIZE;
525 // block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
526 // edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
528 #ifdef CANDIDATE_LIST_PIVOT
529 int edge_num = countEdges(graph);
531 list_length = edge_num / LIST_LENGTH_DIV;
532 minor_limit = edge_num / MINOR_LIMIT_DIV;
534 #ifdef SORTED_LIST_PIVOT
535 int edge_num = countEdges(graph);
537 list_length = edge_num / LIST_LENGTH_DIV;
543 #ifdef FIRST_ELIGIBLE_PIVOT
544 /// \brief Finds entering edge according to the "First Eligible"
546 bool findEnteringEdge(EdgeIt &next_edge) {
547 for (EdgeIt e = next_edge; e != INVALID; ++e) {
548 if (state[e] * red_cost[e] < 0) {
554 for (EdgeIt e(graph); e != next_edge; ++e) {
555 if (state[e] * red_cost[e] < 0) {
565 #ifdef BEST_ELIGIBLE_PIVOT
566 /// \brief Finds entering edge according to the "Best Eligible"
568 bool findEnteringEdge() {
570 for (EdgeIt e(graph); e != INVALID; ++e) {
571 if (state[e] * red_cost[e] < min) {
572 min = state[e] * red_cost[e];
580 #ifdef EDGE_BLOCK_PIVOT
581 /// \brief Finds entering edge according to the "Edge Block"
583 bool findEnteringEdge(EdgeIt &next_edge) {
584 // Performing edge block selection
586 EdgeIt min_edge(graph);
588 for (EdgeIt e = next_edge; e != INVALID; ++e) {
589 if ((curr = state[e] * red_cost[e]) < min) {
593 if (++cnt == block_size) {
599 for (EdgeIt e(graph); e != next_edge; ++e) {
600 if ((curr = state[e] * red_cost[e]) < min) {
604 if (++cnt == block_size) {
611 if ((next_edge = ++min_edge) == INVALID)
612 next_edge = EdgeIt(graph);
617 #ifdef CANDIDATE_LIST_PIVOT
618 /// \brief Finds entering edge according to the "Candidate List"
620 bool findEnteringEdge() {
621 typedef typename std::vector<Edge>::iterator ListIt;
623 if (minor_count >= minor_limit || candidates.size() == 0) {
626 for (EdgeIt e(graph); e != INVALID; ++e) {
627 if (state[e] * red_cost[e] < 0) {
628 candidates.push_back(e);
629 if (candidates.size() == list_length) break;
632 if (candidates.size() == 0) return false;
639 for (int i = 0; i < candidates.size(); ++i) {
641 if (state[e] * red_cost[e] < min) {
642 min = state[e] * red_cost[e];
650 #ifdef SORTED_LIST_PIVOT
651 /// \brief Functor class to compare edges during sort of the
656 const IntEdgeMap &st;
657 const ReducedCostMap &rc;
659 SortFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) :
661 bool operator()(const Edge &e1, const Edge &e2) {
662 return st[e1] * rc[e1] < st[e2] * rc[e2];
666 /// \brief Finds entering edge according to the "Sorted List"
668 bool findEnteringEdge() {
669 static SortFunc sort_func(state, red_cost);
672 while (list_index < candidates.size()) {
673 in_edge = candidates[list_index++];
674 if (state[in_edge] * red_cost[in_edge] < 0) return true;
680 for (EdgeIt e(graph); e != INVALID; ++e) {
681 if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
682 candidates.push_back(e);
683 if (curr < min) min = curr;
684 if (candidates.size() == list_length) break;
687 if (candidates.size() == 0) return false;
688 sort(candidates.begin(), candidates.end(), sort_func);
689 in_edge = candidates[0];
695 /// \brief Finds the join node.
696 Node findJoinNode() {
697 // Finding the join node
698 Node u = graph.source(in_edge);
699 Node v = graph.target(in_edge);
701 if (depth[u] == depth[v]) {
705 else if (depth[u] > depth[v]) u = parent[u];
711 /// \brief Finds the leaving edge of the cycle. Returns \c true if
712 /// the leaving edge is not the same as the entering edge.
713 bool findLeavingEdge() {
714 // Initializing first and second nodes according to the direction
716 if (state[in_edge] == LOWER) {
717 first = graph.source(in_edge);
718 second = graph.target(in_edge);
720 first = graph.target(in_edge);
721 second = graph.source(in_edge);
723 delta = capacity[in_edge];
728 // Searching the cycle along the path form the first node to the
730 for (Node u = first; u != join; u = parent[u]) {
732 d = forward[u] ? flow[e] : capacity[e] - flow[e];
741 // Searching the cycle along the path form the second node to the
743 for (Node u = second; u != join; u = parent[u]) {
745 d = forward[u] ? capacity[e] - flow[e] : flow[e];
757 /// \brief Changes flow and state edge maps.
758 void changeFlows(bool change) {
759 // Augmenting along the cycle
761 Capacity val = state[in_edge] * delta;
762 flow[in_edge] += val;
763 for (Node u = graph.source(in_edge); u != join; u = parent[u]) {
764 flow[pred_edge[u]] += forward[u] ? -val : val;
766 for (Node u = graph.target(in_edge); u != join; u = parent[u]) {
767 flow[pred_edge[u]] += forward[u] ? val : -val;
770 // Updating the state of the entering and leaving edges
772 state[in_edge] = TREE;
773 state[pred_edge[u_out]] =
774 (flow[pred_edge[u_out]] == 0) ? LOWER : UPPER;
776 state[in_edge] = -state[in_edge];
780 /// \brief Updates thread and parent node maps.
781 void updateThreadParent() {
783 v_out = parent[u_out];
785 // Handling the case when join and v_out coincide
786 bool par_first = false;
788 for (u = join; u != u_in && u != v_in; u = thread[u]) ;
791 while (thread[u] != u_out) u = thread[u];
796 // Finding the last successor of u_in (u) and the node after it
797 // (right) according to the thread index
798 for (u = u_in; depth[thread[u]] > depth[u_in]; u = thread[u]) ;
800 if (thread[v_in] == u_out) {
801 for (last = u; depth[last] > depth[u_out]; last = thread[last]) ;
802 if (last == u_out) last = thread[last];
804 else last = thread[v_in];
806 // Updating stem nodes
807 thread[v_in] = stem = u_in;
809 while (stem != u_out) {
810 thread[u] = new_stem = parent[stem];
812 // Finding the node just before the stem node (u) according to
813 // the original thread index
814 for (u = new_stem; thread[u] != stem; u = thread[u]) ;
817 // Changing the parent node of stem and shifting stem and
819 parent[stem] = par_stem;
823 // Finding the last successor of stem (u) and the node after it
824 // (right) according to the thread index
825 for (u = stem; depth[thread[u]] > depth[stem]; u = thread[u]) ;
828 parent[u_out] = par_stem;
831 if (join == v_out && par_first) {
832 if (first != v_in) thread[first] = right;
834 for (u = v_out; thread[u] != u_out; u = thread[u]) ;
839 /// \brief Updates pred_edge and forward node maps.
840 void updatePredEdge() {
844 pred_edge[u] = pred_edge[v];
845 forward[u] = !forward[v];
848 pred_edge[u_in] = in_edge;
849 forward[u_in] = (u_in == graph.source(in_edge));
852 /// \brief Updates depth and potential node maps.
853 void updateDepthPotential() {
854 depth[u_in] = depth[v_in] + 1;
855 potential[u_in] = forward[u_in] ?
856 potential[v_in] + cost[pred_edge[u_in]] :
857 potential[v_in] - cost[pred_edge[u_in]];
859 Node u = thread[u_in], v;
862 if (v == INVALID) break;
863 depth[u] = depth[v] + 1;
864 potential[u] = forward[u] ?
865 potential[v] + cost[pred_edge[u]] :
866 potential[v] - cost[pred_edge[u]];
867 if (depth[u] <= depth[v_in]) break;
872 /// \brief Executes the algorithm.
878 #if defined(FIRST_ELIGIBLE_PIVOT) || defined(EDGE_BLOCK_PIVOT)
879 EdgeIt next_edge(graph);
880 while (findEnteringEdge(next_edge))
882 while (findEnteringEdge())
885 join = findJoinNode();
886 bool change = findLeavingEdge();
889 updateThreadParent();
891 updateDepthPotential();
899 std::cout << "Network Simplex algorithm finished. " << iter_num
900 << " pivot iterations performed." << std::endl;
903 // Checking if the flow amount equals zero on all the
905 for (InEdgeIt e(graph, root); e != INVALID; ++e)
906 if (flow[e] > 0) return false;
907 for (OutEdgeIt e(graph, root); e != INVALID; ++e)
908 if (flow[e] > 0) return false;
910 // Copying flow values to flow_result
912 for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
913 flow_result[e] = (*lower)[e] + flow[edge_ref[e]];
915 for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
916 flow_result[e] = flow[edge_ref[e]];
918 // Copying potential values to potential_result
919 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
920 potential_result[n] = potential[node_ref[n]];
925 }; //class NetworkSimplex
931 #endif //LEMON_NETWORK_SIMPLEX_H