COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/network_simplex.h @ 2476:059dcdda37c5

Last change on this file since 2476:059dcdda37c5 was 2471:ed70b226cc48, checked in by Peter Kovacs, 12 years ago

Small changes in min. cost flow algorithms.

File size: 27.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_NETWORK_SIMPLEX_H
20#define LEMON_NETWORK_SIMPLEX_H
21
22/// \ingroup min_cost_flow
23///
24/// \file
25/// \brief The network simplex algorithm for finding a minimum cost
26/// flow.
27
28#include <limits>
29#include <lemon/smart_graph.h>
30#include <lemon/graph_utils.h>
31
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
38
39//#define _DEBUG_ITER_
40
41
42/// \brief State constant for edges at their lower bounds.
43#define LOWER   1
44/// \brief State constant for edges in the spanning tree.
45#define TREE    0
46/// \brief State constant for edges at their upper bounds.
47#define UPPER   -1
48
49#ifdef EDGE_BLOCK_PIVOT
50  #include <cmath>
51  /// \brief Lower bound for the size of blocks.
52  #define MIN_BLOCK_SIZE        10
53#endif
54
55#ifdef CANDIDATE_LIST_PIVOT
56  #include <vector>
57  #define LIST_LENGTH_DIV           50
58  #define MINOR_LIMIT_DIV           200
59#endif
60
61#ifdef SORTED_LIST_PIVOT
62  #include <vector>
63  #include <algorithm>
64  #define LIST_LENGTH_DIV       100
65  #define LOWER_DIV             4
66#endif
67
68namespace lemon {
69
70  /// \addtogroup min_cost_flow
71  /// @{
72
73  /// \brief Implementation of the network simplex algorithm for
74  /// finding a minimum cost flow.
75  ///
76  /// \ref lemon::NetworkSimplex "NetworkSimplex" implements the
77  /// network simplex algorithm for finding a minimum cost flow.
78  ///
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.
84  ///
85  /// \warning
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.
92  ///
93  /// \author Peter Kovacs
94
95template < 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> >
101  class NetworkSimplex
102  {
103    typedef typename LowerMap::Value Lower;
104    typedef typename CapacityMap::Value Capacity;
105    typedef typename CostMap::Value Cost;
106    typedef typename SupplyMap::Value Supply;
107
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;
115
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;
121
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;
127
128    typedef typename Graph::template NodeMap<Node> NodeRefMap;
129    typedef typename Graph::template EdgeMap<Edge> EdgeRefMap;
130
131  public:
132
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;
137
138  protected:
139
140    /// \brief Map adaptor class for handling reduced edge costs.
141    class ReducedCostMap : public MapBase<Edge, Cost>
142    {
143    private:
144
145      const SGraph &gr;
146      const SCostMap &cost_map;
147      const SPotentialMap &pot_map;
148
149    public:
150
151      typedef typename MapBase<Edge, Cost>::Value Value;
152      typedef typename MapBase<Edge, Cost>::Key Key;
153
154      ReducedCostMap( const SGraph &_gr,
155                      const SCostMap &_cm,
156                      const SPotentialMap &_pm ) :
157        gr(_gr), cost_map(_cm), pot_map(_pm) {}
158
159      Value operator[](const Key &e) const {
160        return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
161      }
162
163    }; //class ReducedCostMap
164
165  protected:
166
167    /// \brief The directed graph the algorithm runs on.
168    SGraph graph;
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.
176    SCostMap cost;
177    /// \brief The supply map.
178    SSupplyMap supply;
179    /// \brief The reduced cost map.
180    ReducedCostMap red_cost;
181    /// \brief The sum of supply values equals zero.
182    bool valid_supply;
183
184    /// \brief The edge map of the current flow.
185    SCapacityMap flow;
186    /// \brief The edge map of the found flow on the original graph.
187    FlowMap flow_result;
188    /// \brief The potential node map.
189    SPotentialMap potential;
190    /// \brief The potential node map on the original graph.
191    PotentialMap potential_result;
192
193    /// \brief Node reference for the original graph.
194    NodeRefMap node_ref;
195    /// \brief Edge reference for the original graph.
196    EdgeRefMap edge_ref;
197
198    /// \brief The depth node map of the spanning tree structure.
199    IntNodeMap depth;
200    /// \brief The parent node map of the spanning tree structure.
201    NodeNodeMap parent;
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.
205    NodeNodeMap thread;
206    /// \brief The forward node map of the spanning tree structure.
207    BoolNodeMap forward;
208    /// \brief The state edge map.
209    IntEdgeMap state;
210
211
212#ifdef EDGE_BLOCK_PIVOT
213    /// \brief The size of blocks for the "Edge Block" pivot rule.
214    int block_size;
215#endif
216#ifdef CANDIDATE_LIST_PIVOT
217    /// \brief The list of candidate edges for the "Candidate List"
218    /// pivot rule.
219    std::vector<Edge> candidates;
220    /// \brief The maximum length of the edge list for the
221    /// "Candidate List" pivot rule.
222    int list_length;
223    /// \brief The maximum number of minor iterations between two major
224    /// itarations.
225    int minor_limit;
226    /// \brief The number of minor iterations.
227    int minor_count;
228#endif
229#ifdef SORTED_LIST_PIVOT
230    /// \brief The list of candidate edges for the "Sorted List"
231    /// pivot rule.
232    std::vector<Edge> candidates;
233    /// \brief The maximum length of the edge list for the
234    /// "Sorted List" pivot rule.
235    int list_length;
236    int list_index;
237#endif
238
239    // Root node of the starting spanning tree.
240    Node root;
241    // The entering edge of the current pivot iteration.
242    Edge in_edge;
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
248    // iteration.
249    Capacity delta;
250
251  public :
252
253    /// \brief General constructor of the class (with lower bounds).
254    ///
255    /// General constructor of the class (with lower bounds).
256    ///
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)
273    {
274      // Checking the sum of supply values
275      Supply sum = 0;
276      for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
277        sum += _supply[n];
278      if (!(valid_supply = sum == 0)) return;
279
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)
285        .nodeRef(node_ref)
286        .edgeRef(edge_ref)
287        .run();
288
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];
292      }
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)
296          s += _lower[e];
297        for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
298          s -= _lower[e];
299        supply[node_ref[n]] = s;
300      }
301    }
302
303    /// \brief General constructor of the class (without lower bounds).
304    ///
305    /// General constructor of the class (without lower bounds).
306    ///
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)
321    {
322      // Checking the sum of supply values
323      Supply sum = 0;
324      for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
325        sum += _supply[n];
326      if (!(valid_supply = sum == 0)) return;
327
328      // Copying graph_ref to graph
329      copyGraph(graph, graph_ref)
330        .edgeMap(capacity, _capacity)
331        .edgeMap(cost, _cost)
332        .nodeMap(supply, _supply)
333        .nodeRef(node_ref)
334        .edgeRef(edge_ref)
335        .run();
336    }
337
338    /// \brief Simple constructor of the class (with lower bounds).
339    ///
340    /// Simple constructor of the class (with lower bounds).
341    ///
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
350    /// \c _t).
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)
364    {
365      // Copying graph_ref to graph
366      copyGraph(graph, graph_ref)
367        .edgeMap(cost, _cost)
368        .nodeRef(node_ref)
369        .edgeRef(edge_ref)
370        .run();
371
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];
375      }
376      for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) {
377        Supply s = 0;
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)
381          s += _lower[e];
382        for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
383          s -= _lower[e];
384        supply[node_ref[n]] = s;
385      }
386      valid_supply = true;
387    }
388
389    /// \brief Simple constructor of the class (without lower bounds).
390    ///
391    /// Simple constructor of the class (without lower bounds).
392    ///
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
400    /// \c _t).
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)
413    {
414      // Copying graph_ref to graph
415      copyGraph(graph, graph_ref)
416        .edgeMap(capacity, _capacity)
417        .edgeMap(cost, _cost)
418        .nodeRef(node_ref)
419        .edgeRef(edge_ref)
420        .run();
421      supply[node_ref[_s]] =  _flow_value;
422      supply[node_ref[_t]] = -_flow_value;
423      valid_supply = true;
424    }
425
426    /// \brief Returns a const reference to the flow map.
427    ///
428    /// Returns a const reference to the flow map.
429    ///
430    /// \pre \ref run() must be called before using this function.
431    const FlowMap& flowMap() const {
432      return flow_result;
433    }
434
435    /// \brief Returns a const reference to the potential map (the dual
436    /// solution).
437    ///
438    /// Returns a const reference to the potential map (the dual
439    /// solution).
440    ///
441    /// \pre \ref run() must be called before using this function.
442    const PotentialMap& potentialMap() const {
443      return potential_result;
444    }
445
446    /// \brief Returns the total cost of the found flow.
447    ///
448    /// Returns the total cost of the found flow. The complexity of the
449    /// function is \f$ O(e) \f$.
450    ///
451    /// \pre \ref run() must be called before using this function.
452    Cost totalCost() const {
453      Cost c = 0;
454      for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
455        c += flow_result[e] * cost[edge_ref[e]];
456      return c;
457    }
458
459    /// \brief Runs the algorithm.
460    ///
461    /// Runs the algorithm.
462    ///
463    /// \return \c true if a feasible flow can be found.
464    bool run() {
465      return init() && start();
466    }
467
468  protected:
469
470    /// \brief Extends the underlaying graph and initializes all the
471    /// node and edge maps.
472    bool init() {
473      if (!valid_supply) return false;
474
475      // Initializing state and flow maps
476      for (EdgeIt e(graph); e != INVALID; ++e) {
477        flow[e] = 0;
478        state[e] = LOWER;
479      }
480
481      // Adding an artificial root node to the graph
482      root = graph.addNode();
483      parent[root] = INVALID;
484      pred_edge[root] = INVALID;
485      depth[root] = 0;
486      supply[root] = 0;
487      potential[root] = 0;
488
489      // Adding artificial edges to the graph and initializing the node
490      // maps of the spanning tree data structure
491      Supply sum = 0;
492      Node last = root;
493      Edge e;
494      Cost max_cost = std::numeric_limits<Cost>::max() / 4;
495      for (NodeIt u(graph); u != INVALID; ++u) {
496        if (u == root) continue;
497        thread[last] = u;
498        last = u;
499        parent[u] = root;
500        depth[u] = 1;
501        sum += supply[u];
502        if (supply[u] >= 0) {
503          e = graph.addEdge(u, root);
504          flow[e] = supply[u];
505          forward[u] = true;
506          potential[u] = max_cost;
507        } else {
508          e = graph.addEdge(root, u);
509          flow[e] = -supply[u];
510          forward[u] = false;
511          potential[u] = -max_cost;
512        }
513        cost[e] = max_cost;
514        capacity[e] = std::numeric_limits<Capacity>::max();
515        state[e] = TREE;
516        pred_edge[u] = e;
517      }
518      thread[last] = root;
519
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;
527#endif
528#ifdef CANDIDATE_LIST_PIVOT
529      int edge_num = countEdges(graph);
530      minor_count = 0;
531      list_length = edge_num / LIST_LENGTH_DIV;
532      minor_limit = edge_num / MINOR_LIMIT_DIV;
533#endif
534#ifdef SORTED_LIST_PIVOT
535      int edge_num = countEdges(graph);
536      list_index = 0;
537      list_length = edge_num / LIST_LENGTH_DIV;
538#endif
539
540      return sum == 0;
541    }
542
543#ifdef FIRST_ELIGIBLE_PIVOT
544    /// \brief Finds entering edge according to the "First Eligible"
545    /// pivot rule.
546    bool findEnteringEdge(EdgeIt &next_edge) {
547      for (EdgeIt e = next_edge; e != INVALID; ++e) {
548        if (state[e] * red_cost[e] < 0) {
549          in_edge = e;
550          next_edge = ++e;
551          return true;
552        }
553      }
554      for (EdgeIt e(graph); e != next_edge; ++e) {
555        if (state[e] * red_cost[e] < 0) {
556          in_edge = e;
557          next_edge = ++e;
558          return true;
559        }
560      }
561      return false;
562    }
563#endif
564
565#ifdef BEST_ELIGIBLE_PIVOT
566    /// \brief Finds entering edge according to the "Best Eligible"
567    /// pivot rule.
568    bool findEnteringEdge() {
569      Cost min = 0;
570      for (EdgeIt e(graph); e != INVALID; ++e) {
571        if (state[e] * red_cost[e] < min) {
572          min = state[e] * red_cost[e];
573          in_edge = e;
574        }
575      }
576      return min < 0;
577    }
578#endif
579
580#ifdef EDGE_BLOCK_PIVOT
581    /// \brief Finds entering edge according to the "Edge Block"
582    /// pivot rule.
583    bool findEnteringEdge(EdgeIt &next_edge) {
584      // Performing edge block selection
585      Cost curr, min = 0;
586      EdgeIt min_edge(graph);
587      int cnt = 0;
588      for (EdgeIt e = next_edge; e != INVALID; ++e) {
589        if ((curr = state[e] * red_cost[e]) < min) {
590          min = curr;
591          min_edge = e;
592        }
593        if (++cnt == block_size) {
594          if (min < 0) break;
595          cnt = 0;
596        }
597      }
598      if (!(min < 0)) {
599        for (EdgeIt e(graph); e != next_edge; ++e) {
600          if ((curr = state[e] * red_cost[e]) < min) {
601            min = curr;
602            min_edge = e;
603          }
604          if (++cnt == block_size) {
605            if (min < 0) break;
606            cnt = 0;
607          }
608        }
609      }
610      in_edge = min_edge;
611      if ((next_edge = ++min_edge) == INVALID)
612        next_edge = EdgeIt(graph);
613      return min < 0;
614    }
615#endif
616
617#ifdef CANDIDATE_LIST_PIVOT
618    /// \brief Finds entering edge according to the "Candidate List"
619    /// pivot rule.
620    bool findEnteringEdge() {
621      typedef typename std::vector<Edge>::iterator ListIt;
622
623      if (minor_count >= minor_limit || candidates.size() == 0) {
624        // Major iteration
625        candidates.clear();
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;
630          }
631        }
632        if (candidates.size() == 0) return false;
633      }
634
635      // Minor iteration
636      ++minor_count;
637      Cost min = 0;
638      Edge e;
639      for (int i = 0; i < candidates.size(); ++i) {
640        e = candidates[i];
641        if (state[e] * red_cost[e] < min) {
642          min = state[e] * red_cost[e];
643          in_edge = e;
644        }
645      }
646      return true;
647    }
648#endif
649
650#ifdef SORTED_LIST_PIVOT
651    /// \brief Functor class to compare edges during sort of the
652    /// candidate list.
653    class SortFunc
654    {
655    private:
656      const IntEdgeMap &st;
657      const ReducedCostMap &rc;
658    public:
659      SortFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) :
660        st(_st), rc(_rc) {}
661      bool operator()(const Edge &e1, const Edge &e2) {
662        return st[e1] * rc[e1] < st[e2] * rc[e2];
663      }
664    };
665
666    /// \brief Finds entering edge according to the "Sorted List"
667    /// pivot rule.
668    bool findEnteringEdge() {
669      static SortFunc sort_func(state, red_cost);
670
671      // Minor iteration
672      while (list_index < candidates.size()) {
673        in_edge = candidates[list_index++];
674        if (state[in_edge] * red_cost[in_edge] < 0) return true;
675      }
676
677      // Major iteration
678      candidates.clear();
679      Cost curr, min = 0;
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;
685        }
686      }
687      if (candidates.size() == 0) return false;
688      sort(candidates.begin(), candidates.end(), sort_func);
689      in_edge = candidates[0];
690      list_index = 1;
691      return true;
692    }
693#endif
694
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);
700      while (u != v) {
701        if (depth[u] == depth[v]) {
702          u = parent[u];
703          v = parent[v];
704        }
705        else if (depth[u] > depth[v]) u = parent[u];
706        else v = parent[v];
707      }
708      return u;
709    }
710
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
715      // of the cycle
716      if (state[in_edge] == LOWER) {
717        first = graph.source(in_edge);
718        second  = graph.target(in_edge);
719      } else {
720        first = graph.target(in_edge);
721        second  = graph.source(in_edge);
722      }
723      delta = capacity[in_edge];
724      bool result = false;
725      Capacity d;
726      Edge e;
727
728      // Searching the cycle along the path form the first node to the
729      // root node
730      for (Node u = first; u != join; u = parent[u]) {
731        e = pred_edge[u];
732        d = forward[u] ? flow[e] : capacity[e] - flow[e];
733        if (d < delta) {
734          delta = d;
735          u_out = u;
736          u_in = first;
737          v_in = second;
738          result = true;
739        }
740      }
741      // Searching the cycle along the path form the second node to the
742      // root node
743      for (Node u = second; u != join; u = parent[u]) {
744        e = pred_edge[u];
745        d = forward[u] ? capacity[e] - flow[e] : flow[e];
746        if (d <= delta) {
747          delta = d;
748          u_out = u;
749          u_in = second;
750          v_in = first;
751          result = true;
752        }
753      }
754      return result;
755    }
756
757    /// \brief Changes flow and state edge maps.
758    void changeFlows(bool change) {
759      // Augmenting along the cycle
760      if (delta > 0) {
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;
765        }
766        for (Node u = graph.target(in_edge); u != join; u = parent[u]) {
767          flow[pred_edge[u]] += forward[u] ? val : -val;
768        }
769      }
770      // Updating the state of the entering and leaving edges
771      if (change) {
772        state[in_edge] = TREE;
773        state[pred_edge[u_out]] =
774          (flow[pred_edge[u_out]] == 0) ? LOWER : UPPER;
775      } else {
776        state[in_edge] = -state[in_edge];
777      }
778    }
779
780    /// \brief Updates thread and parent node maps.
781    void updateThreadParent() {
782      Node u;
783      v_out = parent[u_out];
784
785      // Handling the case when join and v_out coincide
786      bool par_first = false;
787      if (join == v_out) {
788        for (u = join; u != u_in && u != v_in; u = thread[u]) ;
789        if (u == v_in) {
790          par_first = true;
791          while (thread[u] != u_out) u = thread[u];
792          first = u;
793        }
794      }
795
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]) ;
799      right = 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];
803      }
804      else last = thread[v_in];
805
806      // Updating stem nodes
807      thread[v_in] = stem = u_in;
808      par_stem = v_in;
809      while (stem != u_out) {
810        thread[u] = new_stem = parent[stem];
811
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]) ;
815        thread[u] = right;
816
817        // Changing the parent node of stem and shifting stem and
818        // par_stem nodes
819        parent[stem] = par_stem;
820        par_stem = stem;
821        stem = new_stem;
822
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]) ;
826        right = thread[u];
827      }
828      parent[u_out] = par_stem;
829      thread[u] = last;
830
831      if (join == v_out && par_first) {
832        if (first != v_in) thread[first] = right;
833      } else {
834        for (u = v_out; thread[u] != u_out; u = thread[u]) ;
835        thread[u] = right;
836      }
837    }
838
839    /// \brief Updates pred_edge and forward node maps.
840    void updatePredEdge() {
841      Node u = u_out, v;
842      while (u != u_in) {
843        v = parent[u];
844        pred_edge[u] = pred_edge[v];
845        forward[u] = !forward[v];
846        u = v;
847      }
848      pred_edge[u_in] = in_edge;
849      forward[u_in] = (u_in == graph.source(in_edge));
850    }
851
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]];
858
859      Node u = thread[u_in], v;
860      while (true) {
861        v = parent[u];
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;
868        u = thread[u];
869      }
870    }
871
872    /// \brief Executes the algorithm.
873    bool start() {
874      // Processing pivots
875#ifdef _DEBUG_ITER_
876      int iter_num = 0;
877#endif
878#if defined(FIRST_ELIGIBLE_PIVOT) || defined(EDGE_BLOCK_PIVOT)
879      EdgeIt next_edge(graph);
880      while (findEnteringEdge(next_edge))
881#else
882      while (findEnteringEdge())
883#endif
884      {
885        join = findJoinNode();
886        bool change = findLeavingEdge();
887        changeFlows(change);
888        if (change) {
889          updateThreadParent();
890          updatePredEdge();
891          updateDepthPotential();
892        }
893#ifdef _DEBUG_ITER_
894        ++iter_num;
895#endif
896      }
897
898#ifdef _DEBUG_ITER_
899      std::cout << "Network Simplex algorithm finished. " << iter_num
900                << " pivot iterations performed." << std::endl;
901#endif
902
903      // Checking if the flow amount equals zero on all the
904      // artificial edges
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;
909
910      // Copying flow values to flow_result
911      if (lower) {
912        for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
913          flow_result[e] = (*lower)[e] + flow[edge_ref[e]];
914      } else {
915        for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
916          flow_result[e] = flow[edge_ref[e]];
917      }
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]];
921
922      return true;
923    }
924
925  }; //class NetworkSimplex
926
927  ///@}
928
929} //namespace lemon
930
931#endif //LEMON_NETWORK_SIMPLEX_H
Note: See TracBrowser for help on using the repository browser.