forked from google/or-tools
-
Notifications
You must be signed in to change notification settings - Fork 0
/
simple_max_flow_program.cc
72 lines (62 loc) · 2.32 KB
/
simple_max_flow_program.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// Copyright 2010-2021 Google LLC
// 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.
// [START program]
// From Taha 'Introduction to Operations Research', example 6.4-2."""
// [START import]
#include <cstdint>
#include "ortools/graph/max_flow.h"
// [END import]
namespace operations_research {
// MaxFlow simple interface example.
void SimpleMaxFlowProgram() {
// [START data]
// Define three parallel arrays: start_nodes, end_nodes, and the capacities
// between each pair. For instance, the arc from node 0 to node 1 has a
// capacity of 20.
std::vector<int64_t> start_nodes = {0, 0, 0, 1, 1, 2, 2, 3, 3};
std::vector<int64_t> end_nodes = {1, 2, 3, 2, 4, 3, 4, 2, 4};
std::vector<int64_t> capacities = {20, 30, 10, 40, 30, 10, 20, 5, 20};
// [END data]
// [START constraints]
// Instantiate a SimpleMaxFlow solver.
SimpleMaxFlow max_flow;
// Add each arc.
for (int i = 0; i < start_nodes.size(); ++i) {
max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i]);
}
// [END constraints]
// [START solve]
// Find the maximum flow between node 0 and node 4.
int solve_status = max_flow.Solve(0, 4);
// [END solve]
// [START print_solution]
if (solve_status == MaxFlow::OPTIMAL) {
LOG(INFO) << "Max flow: " << max_flow.OptimalFlow();
LOG(INFO) << "";
LOG(INFO) << " Arc Flow / Capacity";
for (std::size_t i = 0; i < max_flow.NumArcs(); ++i) {
LOG(INFO) << max_flow.Tail(i) << " -> " << max_flow.Head(i) << " "
<< max_flow.Flow(i) << " / " << max_flow.Capacity(i);
}
} else {
LOG(INFO) << "Solving the max flow problem failed. Solver status: "
<< solve_status;
}
// [END print_solution]
}
} // namespace operations_research
int main() {
operations_research::SimpleMaxFlowProgram();
return EXIT_SUCCESS;
}
// [END program]