LEMON/LEMON-main Changeset - r888:5205145fabf6

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r888:5205145fabf6

« 867:5b926c

891:bb70ad »
889:0bca98 »

r888:5205145fabf6

Sun, 02 May 2010 18:53:56

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Fix the usage of min() (#368)

0 1 0

default

1 file changed with 2 insertions and 2 deletions:

lemon/network_simplex.h

↑ Collapse diff ↑

lemon/network_simplex.h

Show inline comments

@@ -1021,49 +1021,49 @@

      // Remove non-zero lower bounds
      if (_have_lower) {
        for (int i = 0; i != _arc_num; ++i) {
          Value c = _lower[i];
          if (c >= 0) {
            _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
          } else {
            _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
          }
          _supply[_source[i]] -= c;
          _supply[_target[i]] += c;
        }
      } else {
        for (int i = 0; i != _arc_num; ++i) {
          _cap[i] = _upper[i];
        }
      }

      // Initialize artifical cost
      Cost ART_COST;
      if (std::numeric_limits<Cost>::is_exact) {
        ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
      } else {
        ART_COST = std::numeric_limits<Cost>::min();
        ART_COST = 0;
        for (int i = 0; i != _arc_num; ++i) {
          if (_cost[i] > ART_COST) ART_COST = _cost[i];
        }
        ART_COST = (ART_COST + 1) * _node_num;
      }

      // Initialize arc maps
      for (int i = 0; i != _arc_num; ++i) {
        _flow[i] = 0;
        _state[i] = STATE_LOWER;
      }
      
      // Set data for the artificial root node
      _root = _node_num;
      _parent[_root] = -1;
      _pred[_root] = -1;
      _thread[_root] = 0;
      _rev_thread[0] = _root;
      _succ_num[_root] = _node_num + 1;
      _last_succ[_root] = _root - 1;
      _supply[_root] = -_sum_supply;
      _pi[_root] = 0;

      // Add artificial arcs and initialize the spanning tree data structure
@@ -1436,49 +1436,49 @@
        }
      }
      
      // Check feasibility
      for (int e = _search_arc_num; e != _all_arc_num; ++e) {
        if (_flow[e] != 0) return INFEASIBLE;
      }

      // Transform the solution and the supply map to the original form
      if (_have_lower) {
        for (int i = 0; i != _arc_num; ++i) {
          Value c = _lower[i];
          if (c != 0) {
            _flow[i] += c;
            _supply[_source[i]] += c;
            _supply[_target[i]] -= c;
          }
        }
      }
      
      // Shift potentials to meet the requirements of the GEQ/LEQ type
      // optimality conditions
      if (_sum_supply == 0) {
        if (_stype == GEQ) {
          Cost max_pot = std::numeric_limits<Cost>::min();
          Cost max_pot = -std::numeric_limits<Cost>::max();
          for (int i = 0; i != _node_num; ++i) {
            if (_pi[i] > max_pot) max_pot = _pi[i];
          }
          if (max_pot > 0) {
            for (int i = 0; i != _node_num; ++i)
              _pi[i] -= max_pot;
          }
        } else {
          Cost min_pot = std::numeric_limits<Cost>::max();
          for (int i = 0; i != _node_num; ++i) {
            if (_pi[i] < min_pot) min_pot = _pi[i];
          }
          if (min_pot < 0) {
            for (int i = 0; i != _node_num; ++i)
              _pi[i] -= min_pot;
          }
        }
      }

      return OPTIMAL;
    }

  }; //class NetworkSimplex


0 comments (0 inline)

...	...	@@ -1021,49 +1021,49 @@
1021	1021
1022	1022	// Remove non-zero lower bounds
1023	1023	if (_have_lower) {
1024	1024	for (int i = 0; i != _arc_num; ++i) {
1025	1025	Value c = _lower[i];
1026	1026	if (c >= 0) {
1027	1027	_cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
1028	1028	} else {
1029	1029	_cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
1030	1030	}
1031	1031	_supply[_source[i]] -= c;
1032	1032	_supply[_target[i]] += c;
1033	1033	}
1034	1034	} else {
1035	1035	for (int i = 0; i != _arc_num; ++i) {
1036	1036	_cap[i] = _upper[i];
1037	1037	}
1038	1038	}
1039	1039
1040	1040	// Initialize artifical cost
1041	1041	Cost ART_COST;
1042	1042	if (std::numeric_limits<Cost>::is_exact) {
1043	1043	ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
1044	1044	} else {
1045		ART_COST = ~~std::numeric_limits<Cost>::min()~~;
	1045	ART_COST = 0;
1046	1046	for (int i = 0; i != _arc_num; ++i) {
1047	1047	if (_cost[i] > ART_COST) ART_COST = _cost[i];
1048	1048	}
1049	1049	ART_COST = (ART_COST + 1) * _node_num;
1050	1050	}
1051	1051
1052	1052	// Initialize arc maps
1053	1053	for (int i = 0; i != _arc_num; ++i) {
1054	1054	_flow[i] = 0;
1055	1055	_state[i] = STATE_LOWER;
1056	1056	}
1057	1057
1058	1058	// Set data for the artificial root node
1059	1059	_root = _node_num;
1060	1060	_parent[_root] = -1;
1061	1061	_pred[_root] = -1;
1062	1062	_thread[_root] = 0;
1063	1063	_rev_thread[0] = _root;
1064	1064	_succ_num[_root] = _node_num + 1;
1065	1065	_last_succ[_root] = _root - 1;
1066	1066	_supply[_root] = -_sum_supply;
1067	1067	_pi[_root] = 0;
1068	1068
1069	1069	// Add artificial arcs and initialize the spanning tree data structure
...	...	@@ -1436,49 +1436,49 @@
1436	1436	}
1437	1437	}
1438	1438
1439	1439	// Check feasibility
1440	1440	for (int e = _search_arc_num; e != _all_arc_num; ++e) {
1441	1441	if (_flow[e] != 0) return INFEASIBLE;
1442	1442	}
1443	1443
1444	1444	// Transform the solution and the supply map to the original form
1445	1445	if (_have_lower) {
1446	1446	for (int i = 0; i != _arc_num; ++i) {
1447	1447	Value c = _lower[i];
1448	1448	if (c != 0) {
1449	1449	_flow[i] += c;
1450	1450	_supply[_source[i]] += c;
1451	1451	_supply[_target[i]] -= c;
1452	1452	}
1453	1453	}
1454	1454	}
1455	1455
1456	1456	// Shift potentials to meet the requirements of the GEQ/LEQ type
1457	1457	// optimality conditions
1458	1458	if (_sum_supply == 0) {
1459	1459	if (_stype == GEQ) {
1460		Cost max_pot = std::numeric_limits<Cost>::~~min~~();
	1460	Cost max_pot = -std::numeric_limits<Cost>::max();
1461	1461	for (int i = 0; i != _node_num; ++i) {
1462	1462	if (_pi[i] > max_pot) max_pot = _pi[i];
1463	1463	}
1464	1464	if (max_pot > 0) {
1465	1465	for (int i = 0; i != _node_num; ++i)
1466	1466	_pi[i] -= max_pot;
1467	1467	}
1468	1468	} else {
1469	1469	Cost min_pot = std::numeric_limits<Cost>::max();
1470	1470	for (int i = 0; i != _node_num; ++i) {
1471	1471	if (_pi[i] < min_pot) min_pot = _pi[i];
1472	1472	}
1473	1473	if (min_pot < 0) {
1474	1474	for (int i = 0; i != _node_num; ++i)
1475	1475	_pi[i] -= min_pot;
1476	1476	}
1477	1477	}
1478	1478	}
1479	1479
1480	1480	return OPTIMAL;
1481	1481	}
1482	1482
1483	1483	}; //class NetworkSimplex
1484	1484

RhodeCode

Login to your account