lemon-0.x: comparison lemon/network

equal deleted inserted replaced

-:caab3b168187
+:584dd37f6410
 #define LEMON_NETWORK_SIMPLEX_H
 /// \ingroup min_cost_flow
 ///
 /// \file
-/// \brief The network simplex algorithm for finding a minimum cost
+/// \brief The network simplex algorithm for finding a minimum cost flow.
-/// flow.
 #include <limits>
 #include <lemon/graph_adaptor.h>
 #include <lemon/graph_utils.h>
 #include <lemon/smart_graph.h>
 //#define SORTED_LIST_PIVOT
 //#define _DEBUG_ITER_
-/// \brief State constant for edges at their lower bounds.
+// State constant for edges at their lower bounds.
-#define LOWER	1
+#define LOWER   1
-/// \brief State constant for edges in the spanning tree.
+// State constant for edges in the spanning tree.
-#define TREE	0
+#define TREE    0
-/// \brief State constant for edges at their upper bounds.
+// State constant for edges at their upper bounds.
-#define UPPER	-1
+#define UPPER   -1
 #ifdef EDGE_BLOCK_PIVOT
 #include <cmath>
-/// \brief Lower bound for the size of blocks.
+#define MIN_BLOCK_SIZE        10
-#define MIN_BLOCK_SIZE	10
 #endif
 #ifdef CANDIDATE_LIST_PIVOT
 #include <vector>
-#define LIST_LENGTH_DIV           50
+#define LIST_LENGTH_DIV       50
-#define MINOR_LIMIT_DIV           200
+#define MINOR_LIMIT_DIV       200
 #endif
 #ifdef SORTED_LIST_PIVOT
 #include <vector>
 #include <algorithm>
 #define LIST_LENGTH_DIV       100
-#define LOWER_DIV		4
+#define LOWER_DIV             4
 #endif
 namespace lemon {
 /// \addtogroup min_cost_flow
 /// @{
 /// \brief Implementation of the network simplex algorithm for
 /// finding a minimum cost flow.
 ///
-/// \ref lemon::NetworkSimplex "NetworkSimplex" implements the
+/// \ref NetworkSimplex implements the network simplex algorithm for
-/// network simplex algorithm for finding a minimum cost flow.
+/// finding a minimum cost flow.
 ///
 /// \param Graph The directed graph type the algorithm runs on.
 /// \param LowerMap The type of the lower bound map.
 /// \param CapacityMap The type of the capacity (upper bound) map.
 /// \param CostMap The type of the cost (length) map.
 /// \param SupplyMap The type of the supply map.
 ///
 /// \warning
-/// - Edge capacities and costs should be nonnegative integers.
+/// - Edge capacities and costs should be non-negative integers.
-///	However \c CostMap::Value should be signed type.
+///   However \c CostMap::Value should be signed type.
 /// - Supply values should be signed integers.
 /// - \c LowerMap::Value must be convertible to
-///	\c CapacityMap::Value and \c CapacityMap::Value must be
+///   \c CapacityMap::Value and \c CapacityMap::Value must be
-///	convertible to \c SupplyMap::Value.
+///   convertible to \c SupplyMap::Value.
 ///
 /// \author Peter Kovacs
 template < typename Graph,
 typename LowerMap = typename Graph::template EdgeMap<int>,
 typedef typename CapacityMap::Value Capacity;
 typedef typename CostMap::Value Cost;
 typedef typename SupplyMap::Value Supply;
 typedef SmartGraph SGraph;
-typedef typename SGraph::Node Node;
+GRAPH_TYPEDEFS(typename SGraph);
-typedef typename SGraph::NodeIt NodeIt;
-typedef typename SGraph::Edge Edge;
-typedef typename SGraph::EdgeIt EdgeIt;
-typedef typename SGraph::InEdgeIt InEdgeIt;
-typedef typename SGraph::OutEdgeIt OutEdgeIt;
 typedef typename SGraph::template EdgeMap<Lower> SLowerMap;
 typedef typename SGraph::template EdgeMap<Capacity> SCapacityMap;
 typedef typename SGraph::template EdgeMap<Cost> SCostMap;
 typedef typename SGraph::template NodeMap<Supply> SSupplyMap;
 typedef typename Graph::template NodeMap<Node> NodeRefMap;
 typedef typename Graph::template EdgeMap<Edge> EdgeRefMap;
 public:
-/// \brief The type of the flow map.
+/// The type of the flow map.
 typedef typename Graph::template EdgeMap<Capacity> FlowMap;
-/// \brief The type of the potential map.
+/// The type of the potential map.
 typedef typename Graph::template NodeMap<Cost> PotentialMap;
 protected:
-/// \brief Map adaptor class for handling reduced edge costs.
+/// Map adaptor class for handling reduced edge costs.
 class ReducedCostMap : public MapBase<Edge, Cost>
 {
 private:
 const SGraph &gr;
 const SPotentialMap &pot_map;
 public:
 ReducedCostMap( const SGraph &_gr,
-		      const SCostMap &_cm,
+const SCostMap &_cm,
-		      const SPotentialMap &_pm ) :
+const SPotentialMap &_pm ) :
-	gr(_gr), cost_map(_cm), pot_map(_pm) {}
+gr(_gr), cost_map(_cm), pot_map(_pm) {}
 Cost operator[](const Edge &e) const {
-	return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
+return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
 }
 }; //class ReducedCostMap
 protected:
-/// \brief The directed graph the algorithm runs on.
+/// The directed graph the algorithm runs on.
 SGraph graph;
-/// \brief The original graph.
+/// The original graph.
 const Graph &graph_ref;
-/// \brief The original lower bound map.
+/// The original lower bound map.
 const LowerMap *lower;
-/// \brief The capacity map.
+/// The capacity map.
 SCapacityMap capacity;
-/// \brief The cost map.
+/// The cost map.
 SCostMap cost;
-/// \brief The supply map.
+/// The supply map.
 SSupplyMap supply;
-/// \brief The reduced cost map.
+/// The reduced cost map.
 ReducedCostMap red_cost;
-/// \brief The sum of supply values equals zero.
 bool valid_supply;
-/// \brief The edge map of the current flow.
+/// The edge map of the current flow.
 SCapacityMap flow;
-/// \brief The edge map of the found flow on the original graph.
+/// The potential node map.
+SPotentialMap potential;
 FlowMap flow_result;
-/// \brief The potential node map.
-SPotentialMap potential;
-/// \brief The potential node map on the original graph.
 PotentialMap potential_result;
-/// \brief Node reference for the original graph.
+/// Node reference for the original graph.
 NodeRefMap node_ref;
-/// \brief Edge reference for the original graph.
+/// Edge reference for the original graph.
 EdgeRefMap edge_ref;
-/// \brief The depth node map of the spanning tree structure.
+/// The \c depth node map of the spanning tree structure.
 IntNodeMap depth;
-/// \brief The parent node map of the spanning tree structure.
+/// The \c parent node map of the spanning tree structure.
 NodeNodeMap parent;
-/// \brief The pred_edge node map of the spanning tree structure.
+/// The \c pred_edge node map of the spanning tree structure.
 EdgeNodeMap pred_edge;
-/// \brief The thread node map of the spanning tree structure.
+/// The \c thread node map of the spanning tree structure.
 NodeNodeMap thread;
-/// \brief The forward node map of the spanning tree structure.
+/// The \c forward node map of the spanning tree structure.
 BoolNodeMap forward;
-/// \brief The state edge map.
+/// The state edge map.
 IntEdgeMap state;
+/// The root node of the starting spanning tree.
+Node root;
+// The entering edge of the current pivot iteration.
+Edge in_edge;
+// Temporary nodes used in the current pivot iteration.
+Node join, u_in, v_in, u_out, v_out;
+Node right, first, second, last;
+Node stem, par_stem, new_stem;
+// The maximum augment amount along the found cycle in the current
+// pivot iteration.
+Capacity delta;
 #ifdef EDGE_BLOCK_PIVOT
-/// \brief The size of blocks for the "Edge Block" pivot rule.
+/// The size of blocks for the "Edge Block" pivot rule.
 int block_size;
 #endif
 #ifdef CANDIDATE_LIST_PIVOT
 /// \brief The list of candidate edges for the "Candidate List"
 /// pivot rule.
 /// "Sorted List" pivot rule.
 int list_length;
 int list_index;
 #endif
-// Root node of the starting spanning tree.
-Node root;
-// The entering edge of the current pivot iteration.
-Edge in_edge;
-// Temporary nodes used in the current pivot iteration.
-Node join, u_in, v_in, u_out, v_out;
-Node right, first, second, last;
-Node stem, par_stem, new_stem;
-// The maximum augment amount along the cycle in the current pivot
-// iteration.
-Capacity delta;
 public :
 /// \brief General constructor of the class (with lower bounds).
 ///
 /// General constructor of the class (with lower bounds).
 /// \param _lower The lower bounds of the edges.
 /// \param _capacity The capacities (upper bounds) of the edges.
 /// \param _cost The cost (length) values of the edges.
 /// \param _supply The supply values of the nodes (signed).
 NetworkSimplex( const Graph &_graph,
-		    const LowerMap &_lower,
+const LowerMap &_lower,
-		    const CapacityMap &_capacity,
+const CapacityMap &_capacity,
-		    const CostMap &_cost,
+const CostMap &_cost,
-		    const SupplyMap &_supply ) :
+const SupplyMap &_supply ) :
 graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph),
 supply(graph), flow(graph), flow_result(_graph), potential(graph),
 potential_result(_graph), depth(graph), parent(graph),
 pred_edge(graph), thread(graph), forward(graph), state(graph),
 node_ref(graph_ref), edge_ref(graph_ref),
 red_cost(graph, cost, potential)
 {
 // Checking the sum of supply values
 Supply sum = 0;
 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
-	sum += _supply[n];
+sum += _supply[n];
 if (!(valid_supply = sum == 0)) return;
 // Copying graph_ref to graph
 graph.reserveNode(countNodes(graph_ref) + 1);
 graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref));
 copyGraph(graph, graph_ref)
-	.edgeMap(cost, _cost)
+.edgeMap(cost, _cost)
-	.nodeRef(node_ref)
+.nodeRef(node_ref)
-	.edgeRef(edge_ref)
+.edgeRef(edge_ref)
-	.run();
+.run();
-// Removing nonzero lower bounds
+// Removing non-zero lower bounds
 for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) {
-	capacity[edge_ref[e]] = _capacity[e] - _lower[e];
+capacity[edge_ref[e]] = _capacity[e] - _lower[e];
 }
 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) {
-	Supply s = _supply[n];
+Supply s = _supply[n];
-	for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
+for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
-	  s += _lower[e];
+s += _lower[e];
-	for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
+for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
-	  s -= _lower[e];
+s -= _lower[e];
-	supply[node_ref[n]] = s;
+supply[node_ref[n]] = s;
 }
 }
 /// \brief General constructor of the class (without lower bounds).
 ///
 /// \param _graph The directed graph the algorithm runs on.
 /// \param _capacity The capacities (upper bounds) of the edges.
 /// \param _cost The cost (length) values of the edges.
 /// \param _supply The supply values of the nodes (signed).
 NetworkSimplex( const Graph &_graph,
-		    const CapacityMap &_capacity,
+const CapacityMap &_capacity,
-		    const CostMap &_cost,
+const CostMap &_cost,
-		    const SupplyMap &_supply ) :
+const SupplyMap &_supply ) :
 graph_ref(_graph), lower(NULL), capacity(graph), cost(graph),
 supply(graph), flow(graph), flow_result(_graph), potential(graph),
 potential_result(_graph), depth(graph), parent(graph),
 pred_edge(graph), thread(graph), forward(graph), state(graph),
 node_ref(graph_ref), edge_ref(graph_ref),
 red_cost(graph, cost, potential)
 {
 // Checking the sum of supply values
 Supply sum = 0;
 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
-	sum += _supply[n];
+sum += _supply[n];
 if (!(valid_supply = sum == 0)) return;
 // Copying graph_ref to graph
 copyGraph(graph, graph_ref)
-	.edgeMap(capacity, _capacity)
+.edgeMap(capacity, _capacity)
-	.edgeMap(cost, _cost)
+.edgeMap(cost, _cost)
-	.nodeMap(supply, _supply)
+.nodeMap(supply, _supply)
-	.nodeRef(node_ref)
+.nodeRef(node_ref)
-	.edgeRef(edge_ref)
+.edgeRef(edge_ref)
-	.run();
+.run();
 }
 /// \brief Simple constructor of the class (with lower bounds).
 ///
 /// Simple constructor of the class (with lower bounds).
 /// \param _capacity The capacities (upper bounds) of the edges.
 /// \param _cost The cost (length) values of the edges.
 /// \param _s The source node.
 /// \param _t The target node.
 /// \param _flow_value The required amount of flow from node \c _s
-/// to node \c _t (i.e. the supply of \c _s and the demand of
+/// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
-/// \c _t).
 NetworkSimplex( const Graph &_graph,
-		    const LowerMap &_lower,
+const LowerMap &_lower,
-		    const CapacityMap &_capacity,
+const CapacityMap &_capacity,
-		    const CostMap &_cost,
+const CostMap &_cost,
-		    typename Graph::Node _s,
+typename Graph::Node _s,
-		    typename Graph::Node _t,
+typename Graph::Node _t,
-		    typename SupplyMap::Value _flow_value ) :
+typename SupplyMap::Value _flow_value ) :
 graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph),
 supply(graph), flow(graph), flow_result(_graph), potential(graph),
 potential_result(_graph), depth(graph), parent(graph),
 pred_edge(graph), thread(graph), forward(graph), state(graph),
 node_ref(graph_ref), edge_ref(graph_ref),
 red_cost(graph, cost, potential)
 {
 // Copying graph_ref to graph
 copyGraph(graph, graph_ref)
-	.edgeMap(cost, _cost)
+.edgeMap(cost, _cost)
-	.nodeRef(node_ref)
+.nodeRef(node_ref)
-	.edgeRef(edge_ref)
+.edgeRef(edge_ref)
-	.run();
+.run();
-// Removing nonzero lower bounds
+// Removing non-zero lower bounds
 for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) {
-	capacity[edge_ref[e]] = _capacity[e] - _lower[e];
+capacity[edge_ref[e]] = _capacity[e] - _lower[e];
 }
 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) {
-	Supply s = 0;
+Supply s = 0;
-	if (n == _s) s =  _flow_value;
+if (n == _s) s =  _flow_value;
-	if (n == _t) s = -_flow_value;
+if (n == _t) s = -_flow_value;
-	for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
+for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
-	  s += _lower[e];
+s += _lower[e];
-	for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
+for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
-	  s -= _lower[e];
+s -= _lower[e];
-	supply[node_ref[n]] = s;
+supply[node_ref[n]] = s;
 }
 valid_supply = true;
 }
 /// \brief Simple constructor of the class (without lower bounds).
 /// \param _capacity The capacities (upper bounds) of the edges.
 /// \param _cost The cost (length) values of the edges.
 /// \param _s The source node.
 /// \param _t The target node.
 /// \param _flow_value The required amount of flow from node \c _s
-/// to node \c _t (i.e. the supply of \c _s and the demand of
+/// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
-/// \c _t).
 NetworkSimplex( const Graph &_graph,
-		    const CapacityMap &_capacity,
+const CapacityMap &_capacity,
-		    const CostMap &_cost,
+const CostMap &_cost,
-		    typename Graph::Node _s,
+typename Graph::Node _s,
-		    typename Graph::Node _t,
+typename Graph::Node _t,
-		    typename SupplyMap::Value _flow_value ) :
+typename SupplyMap::Value _flow_value ) :
 graph_ref(_graph), lower(NULL), capacity(graph), cost(graph),
 supply(graph, 0), flow(graph), flow_result(_graph), potential(graph),
 potential_result(_graph), depth(graph), parent(graph),
 pred_edge(graph), thread(graph), forward(graph), state(graph),
 node_ref(graph_ref), edge_ref(graph_ref),
 red_cost(graph, cost, potential)
 {
 // Copying graph_ref to graph
 copyGraph(graph, graph_ref)
-	.edgeMap(capacity, _capacity)
+.edgeMap(capacity, _capacity)
-	.edgeMap(cost, _cost)
+.edgeMap(cost, _cost)
-	.nodeRef(node_ref)
+.nodeRef(node_ref)
-	.edgeRef(edge_ref)
+.edgeRef(edge_ref)
-	.run();
+.run();
 supply[node_ref[_s]] =  _flow_value;
 supply[node_ref[_t]] = -_flow_value;
 valid_supply = true;
+}
+/// \brief Runs the algorithm.
+///
+/// Runs the algorithm.
+///
+/// \return \c true if a feasible flow can be found.
+bool run() {
+return init() && start();
 }
 /// \brief Returns a const reference to the flow map.
 ///
 /// Returns a const reference to the flow map.
 ///
 /// \pre \ref run() must be called before using this function.
 Cost totalCost() const {
 Cost c = 0;
 for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
-	c += flow_result[e] * cost[edge_ref[e]];
+c += flow_result[e] * cost[edge_ref[e]];
 return c;
-}
-/// \brief Runs the algorithm.
-///
-/// Runs the algorithm.
-///
-/// \return \c true if a feasible flow can be found.
-bool run() {
-return init() && start();
 }
 protected:
 /// \brief Extends the underlaying graph and initializes all the
 bool init() {
 if (!valid_supply) return false;
 // Initializing state and flow maps
 for (EdgeIt e(graph); e != INVALID; ++e) {
-	flow[e] = 0;
+flow[e] = 0;
-	state[e] = LOWER;
+state[e] = LOWER;
 }
 // Adding an artificial root node to the graph
 root = graph.addNode();
 parent[root] = INVALID;
 Supply sum = 0;
 Node last = root;
 Edge e;
 Cost max_cost = std::numeric_limits<Cost>::max() / 4;
 for (NodeIt u(graph); u != INVALID; ++u) {
-	if (u == root) continue;
+if (u == root) continue;
-	thread[last] = u;
+thread[last] = u;
-	last = u;
+last = u;
-	parent[u] = root;
+parent[u] = root;
-	depth[u] = 1;
+depth[u] = 1;
-	sum += supply[u];
+sum += supply[u];
-	if (supply[u] >= 0) {
+if (supply[u] >= 0) {
-	  e = graph.addEdge(u, root);
+e = graph.addEdge(u, root);
-	  flow[e] = supply[u];
+flow[e] = supply[u];
-	  forward[u] = true;
+forward[u] = true;
-	  potential[u] = max_cost;
+potential[u] = max_cost;
-	} else {
+} else {
-	  e = graph.addEdge(root, u);
+e = graph.addEdge(root, u);
-	  flow[e] = -supply[u];
+flow[e] = -supply[u];
-	  forward[u] = false;
+forward[u] = false;
-	  potential[u] = -max_cost;
+potential[u] = -max_cost;
-	}
+}
-	cost[e] = max_cost;
+cost[e] = max_cost;
-	capacity[e] = std::numeric_limits<Capacity>::max();
+capacity[e] = std::numeric_limits<Capacity>::max();
-	state[e] = TREE;
+state[e] = TREE;
-	pred_edge[u] = e;
+pred_edge[u] = e;
 }
 thread[last] = root;
 #ifdef EDGE_BLOCK_PIVOT
 // Initializing block_size for the edge block pivot rule
 int edge_num = countEdges(graph);
 block_size = 2 * int(sqrt(countEdges(graph)));
 if (block_size < MIN_BLOCK_SIZE) block_size = MIN_BLOCK_SIZE;
-//      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
-//                   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
 #endif
 #ifdef CANDIDATE_LIST_PIVOT
 int edge_num = countEdges(graph);
 minor_count = 0;
 list_length = edge_num / LIST_LENGTH_DIV;
 #ifdef FIRST_ELIGIBLE_PIVOT
 /// \brief Finds entering edge according to the "First Eligible"
 /// pivot rule.
 bool findEnteringEdge(EdgeIt &next_edge) {
 for (EdgeIt e = next_edge; e != INVALID; ++e) {
-	if (state[e] * red_cost[e] < 0) {
+if (state[e] * red_cost[e] < 0) {
-	  in_edge = e;
+in_edge = e;
-	  next_edge = ++e;
+next_edge = ++e;
-	  return true;
+return true;
-	}
+}
 }
 for (EdgeIt e(graph); e != next_edge; ++e) {
-	if (state[e] * red_cost[e] < 0) {
+if (state[e] * red_cost[e] < 0) {
-	  in_edge = e;
+in_edge = e;
-	  next_edge = ++e;
+next_edge = ++e;
-	  return true;
+return true;
-	}
+}
 }
 return false;
 }
 #endif
 /// \brief Finds entering edge according to the "Best Eligible"
 /// pivot rule.
 bool findEnteringEdge() {
 Cost min = 0;
 for (EdgeIt e(graph); e != INVALID; ++e) {
-	if (state[e] * red_cost[e] < min) {
+if (state[e] * red_cost[e] < min) {
-	  min = state[e] * red_cost[e];
+min = state[e] * red_cost[e];
-	  in_edge = e;
+in_edge = e;
-	}
+}
 }
 return min < 0;
 }
 #endif
 // Performing edge block selection
 Cost curr, min = 0;
 EdgeIt min_edge(graph);
 int cnt = 0;
 for (EdgeIt e = next_edge; e != INVALID; ++e) {
-	if ((curr = state[e] * red_cost[e]) < min) {
+if ((curr = state[e] * red_cost[e]) < min) {
-	  min = curr;
+min = curr;
-	  min_edge = e;
+min_edge = e;
-	}
+}
-	if (++cnt == block_size) {
+if (++cnt == block_size) {
-	  if (min < 0) break;
+if (min < 0) break;
-	  cnt = 0;
+cnt = 0;
-	}
+}
 }
 if (!(min < 0)) {
-	for (EdgeIt e(graph); e != next_edge; ++e) {
+for (EdgeIt e(graph); e != next_edge; ++e) {
-	  if ((curr = state[e] * red_cost[e]) < min) {
+if ((curr = state[e] * red_cost[e]) < min) {
-	    min = curr;
+min = curr;
-	    min_edge = e;
+min_edge = e;
-	  }
+}
-	  if (++cnt == block_size) {
+if (++cnt == block_size) {
-	    if (min < 0) break;
+if (min < 0) break;
-	    cnt = 0;
+cnt = 0;
-	  }
+}
-	}
+}
 }
 in_edge = min_edge;
 if ((next_edge = ++min_edge) == INVALID)
-	next_edge = EdgeIt(graph);
+next_edge = EdgeIt(graph);
 return min < 0;
 }
 #endif
 #ifdef CANDIDATE_LIST_PIVOT
 /// pivot rule.
 bool findEnteringEdge() {
 typedef typename std::vector<Edge>::iterator ListIt;
 if (minor_count >= minor_limit || candidates.size() == 0) {
-	// Major iteration
+// Major iteration
-	candidates.clear();
+candidates.clear();
-	for (EdgeIt e(graph); e != INVALID; ++e) {
+for (EdgeIt e(graph); e != INVALID; ++e) {
-	  if (state[e] * red_cost[e] < 0) {
+if (state[e] * red_cost[e] < 0) {
-	    candidates.push_back(e);
+candidates.push_back(e);
-	    if (candidates.size() == list_length) break;
+if (candidates.size() == list_length) break;
-	  }
+}
-	}
+}
-	if (candidates.size() == 0) return false;
+if (candidates.size() == 0) return false;
 }
 // Minor iteration
 ++minor_count;
 Cost min = 0;
 Edge e;
 for (int i = 0; i < candidates.size(); ++i) {
 e = candidates[i];
-	if (state[e] * red_cost[e] < min) {
+if (state[e] * red_cost[e] < min) {
-	  min = state[e] * red_cost[e];
+min = state[e] * red_cost[e];
-	  in_edge = e;
+in_edge = e;
-	}
+}
 }
 return true;
 }
 #endif
 private:
 const IntEdgeMap &st;
 const ReducedCostMap &rc;
 public:
 SortFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) :
-	st(_st), rc(_rc) {}
+st(_st), rc(_rc) {}
 bool operator()(const Edge &e1, const Edge &e2) {
-	return st[e1] * rc[e1] < st[e2] * rc[e2];
+return st[e1] * rc[e1] < st[e2] * rc[e2];
 }
 };
 /// \brief Finds entering edge according to the "Sorted List"
 /// pivot rule.
 bool findEnteringEdge() {
 static SortFunc sort_func(state, red_cost);
 // Minor iteration
 while (list_index < candidates.size()) {
-	in_edge = candidates[list_index++];
+in_edge = candidates[list_index++];
-	if (state[in_edge] * red_cost[in_edge] < 0) return true;
+if (state[in_edge] * red_cost[in_edge] < 0) return true;
 }
 // Major iteration
 candidates.clear();
 Cost curr, min = 0;
 for (EdgeIt e(graph); e != INVALID; ++e) {
-	if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
+if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
-	  candidates.push_back(e);
+candidates.push_back(e);
-	  if (curr < min) min = curr;
+if (curr < min) min = curr;
-	  if (candidates.size() == list_length) break;
+if (candidates.size() == list_length) break;
-	}
+}
 }
 if (candidates.size() == 0) return false;
 sort(candidates.begin(), candidates.end(), sort_func);
 in_edge = candidates[0];
 list_index = 1;
 Node findJoinNode() {
 // Finding the join node
 Node u = graph.source(in_edge);
 Node v = graph.target(in_edge);
 while (u != v) {
-	if (depth[u] == depth[v]) {
+if (depth[u] == depth[v]) {
-	  u = parent[u];
+u = parent[u];
-	  v = parent[v];
+v = parent[v];
-	}
+}
-	else if (depth[u] > depth[v]) u = parent[u];
+else if (depth[u] > depth[v]) u = parent[u];
-	else v = parent[v];
+else v = parent[v];
 }
 return u;
 }
 /// \brief Finds the leaving edge of the cycle. Returns \c true if
 /// the leaving edge is not the same as the entering edge.
 bool findLeavingEdge() {
 // Initializing first and second nodes according to the direction
 // of the cycle
 if (state[in_edge] == LOWER) {
-	first = graph.source(in_edge);
+first = graph.source(in_edge);
-	second	= graph.target(in_edge);
+second  = graph.target(in_edge);
 } else {
-	first = graph.target(in_edge);
+first = graph.target(in_edge);
-	second	= graph.source(in_edge);
+second  = graph.source(in_edge);
 }
 delta = capacity[in_edge];
 bool result = false;
 Capacity d;
 Edge e;
 // Searching the cycle along the path form the first node to the
 // root node
 for (Node u = first; u != join; u = parent[u]) {
-	e = pred_edge[u];
+e = pred_edge[u];
-	d = forward[u] ? flow[e] : capacity[e] - flow[e];
+d = forward[u] ? flow[e] : capacity[e] - flow[e];
-	if (d < delta) {
+if (d < delta) {
-	  delta = d;
+delta = d;
-	  u_out = u;
+u_out = u;
-	  u_in = first;
+u_in = first;
-	  v_in = second;
+v_in = second;
-	  result = true;
+result = true;
-	}
+}
 }
 // Searching the cycle along the path form the second node to the
 // root node
 for (Node u = second; u != join; u = parent[u]) {
-	e = pred_edge[u];
+e = pred_edge[u];
-	d = forward[u] ? capacity[e] - flow[e] : flow[e];
+d = forward[u] ? capacity[e] - flow[e] : flow[e];
-	if (d <= delta) {
+if (d <= delta) {
-	  delta = d;
+delta = d;
-	  u_out = u;
+u_out = u;
-	  u_in = second;
+u_in = second;
-	  v_in = first;
+v_in = first;
-	  result = true;
+result = true;
-	}
+}
 }
 return result;
 }
-/// \brief Changes flow and state edge maps.
+/// \brief Changes \c flow and \c state edge maps.
 void changeFlows(bool change) {
 // Augmenting along the cycle
 if (delta > 0) {
-	Capacity val = state[in_edge] * delta;
+Capacity val = state[in_edge] * delta;
-	flow[in_edge] += val;
+flow[in_edge] += val;
-	for (Node u = graph.source(in_edge); u != join; u = parent[u]) {
+for (Node u = graph.source(in_edge); u != join; u = parent[u]) {
-	  flow[pred_edge[u]] += forward[u] ? -val : val;
+flow[pred_edge[u]] += forward[u] ? -val : val;
-	}
+}
-	for (Node u = graph.target(in_edge); u != join; u = parent[u]) {
+for (Node u = graph.target(in_edge); u != join; u = parent[u]) {
-	  flow[pred_edge[u]] += forward[u] ? val : -val;
+flow[pred_edge[u]] += forward[u] ? val : -val;
-	}
+}
 }
 // Updating the state of the entering and leaving edges
 if (change) {
-	state[in_edge] = TREE;
+state[in_edge] = TREE;
-	state[pred_edge[u_out]] =
+state[pred_edge[u_out]] =
-	  (flow[pred_edge[u_out]] == 0) ? LOWER : UPPER;
+(flow[pred_edge[u_out]] == 0) ? LOWER : UPPER;
 } else {
-	state[in_edge] = -state[in_edge];
+state[in_edge] = -state[in_edge];
 }
 }
-/// \brief Updates thread and parent node maps.
+/// \brief Updates \c thread and \c parent node maps.
 void updateThreadParent() {
 Node u;
 v_out = parent[u_out];
 // Handling the case when join and v_out coincide
 bool par_first = false;
 if (join == v_out) {
-	for (u = join; u != u_in && u != v_in; u = thread[u]) ;
+for (u = join; u != u_in && u != v_in; u = thread[u]) ;
-	if (u == v_in) {
+if (u == v_in) {
-	  par_first = true;
+par_first = true;
-	  while (thread[u] != u_out) u = thread[u];
+while (thread[u] != u_out) u = thread[u];
-	  first = u;
+first = u;
-	}
+}
 }
 // Finding the last successor of u_in (u) and the node after it
 // (right) according to the thread index
 for (u = u_in; depth[thread[u]] > depth[u_in]; u = thread[u]) ;
 right = thread[u];
 if (thread[v_in] == u_out) {
-	for (last = u; depth[last] > depth[u_out]; last = thread[last]) ;
+for (last = u; depth[last] > depth[u_out]; last = thread[last]) ;
-	if (last == u_out) last = thread[last];
+if (last == u_out) last = thread[last];
 }
 else last = thread[v_in];
 // Updating stem nodes
 thread[v_in] = stem = u_in;
 par_stem = v_in;
 while (stem != u_out) {
-	thread[u] = new_stem = parent[stem];
+thread[u] = new_stem = parent[stem];
-	// Finding the node just before the stem node (u) according to
+// Finding the node just before the stem node (u) according to
-	// the original thread index
+// the original thread index
-	for (u = new_stem; thread[u] != stem; u = thread[u]) ;
+for (u = new_stem; thread[u] != stem; u = thread[u]) ;
-	thread[u] = right;
+thread[u] = right;
-	// Changing the parent node of stem and shifting stem and
+// Changing the parent node of stem and shifting stem and
-	// par_stem nodes
+// par_stem nodes
-	parent[stem] = par_stem;
+parent[stem] = par_stem;
-	par_stem = stem;
+par_stem = stem;
-	stem = new_stem;
+stem = new_stem;
-	// Finding the last successor of stem (u) and the node after it
+// Finding the last successor of stem (u) and the node after it
-	// (right) according to the thread index
+// (right) according to the thread index
-	for (u = stem; depth[thread[u]] > depth[stem]; u = thread[u]) ;
+for (u = stem; depth[thread[u]] > depth[stem]; u = thread[u]) ;
-	right = thread[u];
+right = thread[u];
 }
 parent[u_out] = par_stem;
 thread[u] = last;
 if (join == v_out && par_first) {
-	if (first != v_in) thread[first] = right;
+if (first != v_in) thread[first] = right;
 } else {
-	for (u = v_out; thread[u] != u_out; u = thread[u]) ;
+for (u = v_out; thread[u] != u_out; u = thread[u]) ;
-	thread[u] = right;
+thread[u] = right;
 }
 }
-/// \brief Updates pred_edge and forward node maps.
+/// \brief Updates \c pred_edge and \c forward node maps.
 void updatePredEdge() {
 Node u = u_out, v;
 while (u != u_in) {
-	v = parent[u];
+v = parent[u];
-	pred_edge[u] = pred_edge[v];
+pred_edge[u] = pred_edge[v];
-	forward[u] = !forward[v];
+forward[u] = !forward[v];
-	u = v;
+u = v;
 }
 pred_edge[u_in] = in_edge;
 forward[u_in] = (u_in == graph.source(in_edge));
 }
-/// \brief Updates depth and potential node maps.
+/// \brief Updates \c depth and \c potential node maps.
 void updateDepthPotential() {
 depth[u_in] = depth[v_in] + 1;
 potential[u_in] = forward[u_in] ?
-	potential[v_in] + cost[pred_edge[u_in]] :
+potential[v_in] + cost[pred_edge[u_in]] :
-	potential[v_in] - cost[pred_edge[u_in]];
+potential[v_in] - cost[pred_edge[u_in]];
 Node u = thread[u_in], v;
 while (true) {
-	v = parent[u];
+v = parent[u];
-	if (v == INVALID) break;
+if (v == INVALID) break;
-	depth[u] = depth[v] + 1;
+depth[u] = depth[v] + 1;
-	potential[u] = forward[u] ?
+potential[u] = forward[u] ?
-	  potential[v] + cost[pred_edge[u]] :
+potential[v] + cost[pred_edge[u]] :
-	  potential[v] - cost[pred_edge[u]];
+potential[v] - cost[pred_edge[u]];
-	if (depth[u] <= depth[v_in]) break;
+if (depth[u] <= depth[v_in]) break;
-	u = thread[u];
+u = thread[u];
 }
 }
 /// \brief Executes the algorithm.
 bool start() {
 while (findEnteringEdge(next_edge))
 #else
 while (findEnteringEdge())
 #endif
 {
-	join = findJoinNode();
+join = findJoinNode();
-	bool change = findLeavingEdge();
+bool change = findLeavingEdge();
-	changeFlows(change);
+changeFlows(change);
-	if (change) {
+if (change) {
-	  updateThreadParent();
+updateThreadParent();
-	  updatePredEdge();
+updatePredEdge();
-	  updateDepthPotential();
+updateDepthPotential();
-	}
+}
 #ifdef _DEBUG_ITER_
-	++iter_num;
+++iter_num;
 #endif
 }
 #ifdef _DEBUG_ITER_
 std::cout << "Network Simplex algorithm finished. " << iter_num
-		<< " pivot iterations performed." << std::endl;
+<< " pivot iterations performed." << std::endl;
 #endif
 // Checking if the flow amount equals zero on all the
 // artificial edges
 for (InEdgeIt e(graph, root); e != INVALID; ++e)
-	if (flow[e] > 0) return false;
+if (flow[e] > 0) return false;
 for (OutEdgeIt e(graph, root); e != INVALID; ++e)
-	if (flow[e] > 0) return false;
+if (flow[e] > 0) return false;
 // Copying flow values to flow_result
 if (lower) {
-	for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
+for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
-	  flow_result[e] = (*lower)[e] + flow[edge_ref[e]];
+flow_result[e] = (*lower)[e] + flow[edge_ref[e]];
 } else {
-	for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
+for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
-	  flow_result[e] = flow[edge_ref[e]];
+flow_result[e] = flow[edge_ref[e]];
 }
 // Copying potential values to potential_result
 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
-	potential_result[n] = potential[node_ref[n]];
+potential_result[n] = potential[node_ref[n]];
 return true;
 }
 }; //class NetworkSimplex

changeset 2560	635e7985be46
parent 2553	bfced05fa852
child 2569	12c2c5c4330b