2025-01-10 11:35:44 +01:00
|
|
|
// Copyright 2010-2025 Google LLC
|
2011-03-16 15:32:09 +00:00
|
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
|
|
|
// you may not use this file except in compliance with the License.
|
|
|
|
|
// You may obtain a copy of the License at
|
|
|
|
|
//
|
|
|
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
|
|
|
//
|
|
|
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
|
|
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
|
|
|
|
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
|
|
|
// See the License for the specific language governing permissions and
|
|
|
|
|
// limitations under the License.
|
|
|
|
|
|
2021-01-14 10:48:19 +01:00
|
|
|
#include <cstdlib>
|
|
|
|
|
|
2022-02-25 09:47:52 +01:00
|
|
|
#include "ortools/base/init_google.h"
|
2017-04-26 17:30:25 +02:00
|
|
|
#include "ortools/base/logging.h"
|
2024-12-29 19:21:42 +01:00
|
|
|
#include "ortools/graph/generic_max_flow.h"
|
|
|
|
|
#include "ortools/graph/graph.h"
|
2017-04-26 17:30:25 +02:00
|
|
|
#include "ortools/graph/min_cost_flow.h"
|
2011-03-16 15:32:09 +00:00
|
|
|
|
|
|
|
|
namespace operations_research {
|
|
|
|
|
|
2024-12-29 19:21:42 +01:00
|
|
|
using Graph = ::util::ReverseArcListGraph<>;
|
|
|
|
|
using NodeIndex = Graph::NodeIndex;
|
|
|
|
|
using ArcIndex = Graph::ArcIndex;
|
|
|
|
|
using CostValue = GenericMinCostFlow<Graph>::CostValue;
|
|
|
|
|
using FlowQuantity = GenericMinCostFlow<Graph>::FlowQuantity;
|
|
|
|
|
|
2011-03-16 15:32:09 +00:00
|
|
|
// ----- Min Cost Flow -----
|
|
|
|
|
|
|
|
|
|
// Test on a 4x4 matrix. Example taken from
|
|
|
|
|
// http://www.ee.oulu.fi/~mpa/matreng/eem1_2-1.htm
|
|
|
|
|
void MinCostFlowOn4x4Matrix() {
|
|
|
|
|
LOG(INFO) << "Min Cost Flow on 4x4 Matrix";
|
|
|
|
|
const int kNumSources = 4;
|
|
|
|
|
const int kNumTargets = 4;
|
2020-10-22 23:36:58 +02:00
|
|
|
const CostValue kCost[kNumSources][kNumTargets] = {{90, 75, 75, 80},
|
|
|
|
|
{35, 85, 55, 65},
|
|
|
|
|
{125, 95, 90, 105},
|
|
|
|
|
{45, 110, 95, 115}};
|
2011-03-16 15:32:09 +00:00
|
|
|
const CostValue kExpectedCost = 275;
|
2024-12-29 19:21:42 +01:00
|
|
|
Graph graph(kNumSources + kNumTargets, kNumSources * kNumTargets);
|
|
|
|
|
GenericMinCostFlow<Graph> min_cost_flow(&graph);
|
2011-05-17 20:38:55 +00:00
|
|
|
for (NodeIndex source = 0; source < kNumSources; ++source) {
|
|
|
|
|
for (NodeIndex target = 0; target < kNumTargets; ++target) {
|
2011-03-16 15:32:09 +00:00
|
|
|
ArcIndex arc = graph.AddArc(source, kNumSources + target);
|
2011-05-17 20:38:55 +00:00
|
|
|
min_cost_flow.SetArcUnitCost(arc, kCost[source][target]);
|
2011-03-16 15:32:09 +00:00
|
|
|
min_cost_flow.SetArcCapacity(arc, 1);
|
|
|
|
|
}
|
|
|
|
|
}
|
2011-05-17 20:38:55 +00:00
|
|
|
for (NodeIndex source = 0; source < kNumSources; ++source) {
|
2011-03-16 15:32:09 +00:00
|
|
|
min_cost_flow.SetNodeSupply(source, 1);
|
|
|
|
|
}
|
2011-05-17 20:38:55 +00:00
|
|
|
for (NodeIndex target = 0; target < kNumTargets; ++target) {
|
2011-03-16 15:32:09 +00:00
|
|
|
min_cost_flow.SetNodeSupply(kNumSources + target, -1);
|
|
|
|
|
}
|
2011-07-06 21:23:48 +00:00
|
|
|
CHECK(min_cost_flow.Solve());
|
2025-01-15 13:51:40 +01:00
|
|
|
CHECK_EQ(GenericMinCostFlow<Graph>::OPTIMAL, min_cost_flow.status());
|
2011-07-06 21:23:48 +00:00
|
|
|
CostValue total_flow_cost = min_cost_flow.GetOptimalCost();
|
2011-03-16 15:32:09 +00:00
|
|
|
CHECK_EQ(kExpectedCost, total_flow_cost);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// ----- Max Flow -----
|
|
|
|
|
|
|
|
|
|
void MaxFeasibleFlow() {
|
|
|
|
|
LOG(INFO) << "Max Feasible Flow";
|
|
|
|
|
const int kNumNodes = 6;
|
|
|
|
|
const int kNumArcs = 9;
|
2020-10-22 23:36:58 +02:00
|
|
|
const NodeIndex kTail[kNumArcs] = {0, 0, 0, 0, 1, 2, 3, 3, 4};
|
|
|
|
|
const NodeIndex kHead[kNumArcs] = {1, 2, 3, 4, 3, 4, 4, 5, 5};
|
|
|
|
|
const FlowQuantity kCapacity[kNumArcs] = {5, 8, 5, 3, 4, 5, 6, 6, 4};
|
|
|
|
|
const FlowQuantity kExpectedFlow[kNumArcs] = {1, 1, 5, 3, 1, 1, 0, 6, 4};
|
2011-03-16 15:32:09 +00:00
|
|
|
const FlowQuantity kExpectedTotalFlow = 10;
|
2024-12-29 19:21:42 +01:00
|
|
|
Graph graph(kNumNodes, kNumArcs);
|
|
|
|
|
GenericMaxFlow<Graph> max_flow(&graph, 0, kNumNodes - 1);
|
2011-03-16 15:32:09 +00:00
|
|
|
for (int i = 0; i < kNumArcs; ++i) {
|
|
|
|
|
ArcIndex arc = graph.AddArc(kTail[i], kHead[i]);
|
|
|
|
|
max_flow.SetArcCapacity(arc, kCapacity[i]);
|
|
|
|
|
}
|
2011-07-06 21:23:48 +00:00
|
|
|
CHECK(max_flow.Solve());
|
2024-12-29 19:21:42 +01:00
|
|
|
CHECK_EQ(MaxFlowStatusClass::OPTIMAL, max_flow.status());
|
2011-07-06 21:23:48 +00:00
|
|
|
FlowQuantity total_flow = max_flow.GetOptimalFlow();
|
2011-03-16 15:32:09 +00:00
|
|
|
CHECK_EQ(total_flow, kExpectedTotalFlow);
|
|
|
|
|
for (int i = 0; i < kNumArcs; ++i) {
|
2011-05-17 20:38:55 +00:00
|
|
|
CHECK_EQ(kExpectedFlow[i], max_flow.Flow(i)) << " i = " << i;
|
2011-03-16 15:32:09 +00:00
|
|
|
}
|
|
|
|
|
}
|
2020-10-22 23:36:58 +02:00
|
|
|
} // namespace operations_research
|
2011-03-16 15:32:09 +00:00
|
|
|
|
2020-10-29 14:25:39 +01:00
|
|
|
int main(int argc, char** argv) {
|
2022-02-25 09:47:52 +01:00
|
|
|
InitGoogle(argv[0], &argc, &argv, true);
|
2011-03-16 15:32:09 +00:00
|
|
|
operations_research::MinCostFlowOn4x4Matrix();
|
|
|
|
|
operations_research::MaxFeasibleFlow();
|
2018-11-07 09:52:37 +01:00
|
|
|
return EXIT_SUCCESS;
|
2011-03-16 15:32:09 +00:00
|
|
|
}
|
