다음 섹션에서는 최대 흐름(최대 흐름) 문제의 예를 보여줍니다.
최대 흐름의 예
문제는 전송 네트워크를 나타내는 다음 그래프로 정의됩니다.
여러분은 노드 0 (소스)에서 노드 4 (싱크)로 머티리얼을 전송하려고 합니다. 호 옆에 있는 숫자는 용량입니다. 원호의 용량은 고정된 시간 동안 원호를 가로질러 운반할 수 있는 최대 양입니다. 용량은 문제의 제약조건입니다.
흐름은 다음 흐름 보존 규칙을 충족하는 각 원호 (유량)에 음수가 아닌 숫자를 할당하는 것입니다.
최대 흐름 문제는 전체 네트워크의 흐름량 합계가 최대한 큰 흐름을 찾는 것입니다.
다음 섹션에서는 소스 (0)에서 싱크 (4)로의 최대 흐름을 찾는 프로그램을 보여줍니다.
라이브러리 가져오기
다음 코드는 필요한 라이브러리를 가져옵니다.
Python
import numpy as np from ortools.graph.python import max_flow
C++
#include <cstdint> #include <vector> #include "ortools/graph/max_flow.h"
Java
import com.google.ortools.Loader; import com.google.ortools.graph.MaxFlow;
C#
using System; using Google.OrTools.Graph;
문제 해결사 선언
이 문제를 해결하려면 SimpleMaxFlow 솔버를 사용하면 됩니다.
Python
# Instantiate a SimpleMaxFlow solver. smf = max_flow.SimpleMaxFlow()
C++
// Instantiate a SimpleMaxFlow solver. SimpleMaxFlow max_flow;
Java
// Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow();
C#
// Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow();
데이터 정의
시작 노드, 끝 노드, 원호의 용량에 대한 세 개의 배열이 있는 문제에 대한 그래프를 정의합니다. 각 배열의 길이는 그래프의 호의 수와 같습니다.
각 i의 경우 원호 i는 start_nodes[i]에서 end_nodes[i]까지 진행되며 용량은 capacities[i]로 주어집니다. 다음 섹션에서는 이 데이터를 사용하여 호를 만드는 방법을 보여줍니다.
Python
# 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. start_nodes = np.array([0, 0, 0, 1, 1, 2, 2, 3, 3]) end_nodes = np.array([1, 2, 3, 2, 4, 3, 4, 2, 4]) capacities = np.array([20, 30, 10, 40, 30, 10, 20, 5, 20])
C++
// 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};
Java
// 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.
// From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = new int[] {0, 0, 0, 1, 1, 2, 2, 3, 3};
int[] endNodes = new int[] {1, 2, 3, 2, 4, 3, 4, 2, 4};
int[] capacities = new int[] {20, 30, 10, 40, 30, 10, 20, 5, 20};
C#
// 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.
// From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = { 0, 0, 0, 1, 1, 2, 2, 3, 3 };
int[] endNodes = { 1, 2, 3, 2, 4, 3, 4, 2, 4 };
int[] capacities = { 20, 30, 10, 40, 30, 10, 20, 5, 20 };
호 추가
각 시작 노드와 종료 노드에 대해 AddArcWithCapacity 메서드를 사용하여 주어진 용량으로 시작 노드에서 끝 노드로 호를 만듭니다. 용량은 문제의 제약 조건입니다.
Python
# Add arcs in bulk. # note: we could have used add_arc_with_capacity(start, end, capacity) all_arcs = smf.add_arcs_with_capacity(start_nodes, end_nodes, capacities)
C++
// Add each arc.
for (int i = 0; i < start_nodes.size(); ++i) {
max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i]);
}
Java
// Add each arc.
for (int i = 0; i < startNodes.length; ++i) {
int arc = maxFlow.addArcWithCapacity(startNodes[i], endNodes[i], capacities[i]);
if (arc != i) {
throw new Exception("Internal error");
}
}
C#
// Add each arc.
for (int i = 0; i < startNodes.Length; ++i)
{
int arc = maxFlow.AddArcWithCapacity(startNodes[i], endNodes[i], capacities[i]);
if (arc != i)
throw new Exception("Internal error");
}
솔버 호출
모든 호가 정의되었으므로 이제 솔버를 호출하고 결과를 표시하기만 하면 됩니다. Solve() 메서드를 호출하여 소스 (0)와 싱크 (4)를 제공합니다.
Python
# Find the maximum flow between node 0 and node 4. status = smf.solve(0, 4)
C++
// Find the maximum flow between node 0 and node 4. int status = max_flow.Solve(0, 4);
Java
// Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.solve(0, 4);
C#
// Find the maximum flow between node 0 and node 4. MaxFlow.Status status = maxFlow.Solve(0, 4);
결과 표시
이제 각 원호를 가로지르는 흐름을 표시할 수 있습니다.
Python
if status != smf.OPTIMAL:
print("There was an issue with the max flow input.")
print(f"Status: {status}")
exit(1)
print("Max flow:", smf.optimal_flow())
print("")
print(" Arc Flow / Capacity")
solution_flows = smf.flows(all_arcs)
for arc, flow, capacity in zip(all_arcs, solution_flows, capacities):
print(f"{smf.tail(arc)} / {smf.head(arc)} {flow:3} / {capacity:3}")
print("Source side min-cut:", smf.get_source_side_min_cut())
print("Sink side min-cut:", smf.get_sink_side_min_cut())
C++
if (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: "
<< status;
}
Java
if (status == MaxFlow.Status.OPTIMAL) {
System.out.println("Max. flow: " + maxFlow.getOptimalFlow());
System.out.println();
System.out.println(" Arc Flow / Capacity");
for (int i = 0; i < maxFlow.getNumArcs(); ++i) {
System.out.println(maxFlow.getTail(i) + " -> " + maxFlow.getHead(i) + " "
+ maxFlow.getFlow(i) + " / " + maxFlow.getCapacity(i));
}
} else {
System.out.println("Solving the max flow problem failed. Solver status: " + status);
}
C#
if (status == MaxFlow.Status.OPTIMAL)
{
Console.WriteLine("Max. flow: " + maxFlow.OptimalFlow());
Console.WriteLine("");
Console.WriteLine(" Arc Flow / Capacity");
for (int i = 0; i < maxFlow.NumArcs(); ++i)
{
Console.WriteLine(maxFlow.Tail(i) + " -> " + maxFlow.Head(i) + " " +
string.Format("{0,3}", maxFlow.Flow(i)) + " / " +
string.Format("{0,3}", maxFlow.Capacity(i)));
}
}
else
{
Console.WriteLine("Solving the max flow problem failed. Solver status: " + status);
}
프로그램의 출력은 다음과 같습니다.
Max flow: 60 Arc Flow / Capacity 0 -> 1 20 / 20 0 -> 2 30 / 30 0 -> 3 10 / 10 1 -> 2 0 / 40 1 -> 4 20 / 30 2 -> 3 10 / 10 2 -> 4 20 / 20 3 -> 2 0 / 5 3 -> 4 20 / 20 Source side min-cut: [0] Sink side min-cut: [4, 1]
각 원호를 가로지르는 유량은 Flow 아래에 표시됩니다.
프로그램 이수
종합해보면 다음과 같은 완전한 프로그램이 있습니다.
Python
"""From Taha 'Introduction to Operations Research', example 6.4-2."""
import numpy as np
from ortools.graph.python import max_flow
def main():
"""MaxFlow simple interface example."""
# Instantiate a SimpleMaxFlow solver.
smf = max_flow.SimpleMaxFlow()
# 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.
start_nodes = np.array([0, 0, 0, 1, 1, 2, 2, 3, 3])
end_nodes = np.array([1, 2, 3, 2, 4, 3, 4, 2, 4])
capacities = np.array([20, 30, 10, 40, 30, 10, 20, 5, 20])
# Add arcs in bulk.
# note: we could have used add_arc_with_capacity(start, end, capacity)
all_arcs = smf.add_arcs_with_capacity(start_nodes, end_nodes, capacities)
# Find the maximum flow between node 0 and node 4.
status = smf.solve(0, 4)
if status != smf.OPTIMAL:
print("There was an issue with the max flow input.")
print(f"Status: {status}")
exit(1)
print("Max flow:", smf.optimal_flow())
print("")
print(" Arc Flow / Capacity")
solution_flows = smf.flows(all_arcs)
for arc, flow, capacity in zip(all_arcs, solution_flows, capacities):
print(f"{smf.tail(arc)} / {smf.head(arc)} {flow:3} / {capacity:3}")
print("Source side min-cut:", smf.get_source_side_min_cut())
print("Sink side min-cut:", smf.get_sink_side_min_cut())
if __name__ == "__main__":
main()
C++
// From Taha 'Introduction to Operations Research', example 6.4-2."""
#include <cstdint>
#include <vector>
#include "ortools/graph/max_flow.h"
namespace operations_research {
// MaxFlow simple interface example.
void SimpleMaxFlowProgram() {
// Instantiate a SimpleMaxFlow solver.
SimpleMaxFlow max_flow;
// 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};
// Add each arc.
for (int i = 0; i < start_nodes.size(); ++i) {
max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i]);
}
// Find the maximum flow between node 0 and node 4.
int status = max_flow.Solve(0, 4);
if (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: "
<< status;
}
}
} // namespace operations_research
int main() {
operations_research::SimpleMaxFlowProgram();
return EXIT_SUCCESS;
}
Java
package com.google.ortools.graph.samples;
import com.google.ortools.Loader;
import com.google.ortools.graph.MaxFlow;
/** Minimal MaxFlow program. */
public final class SimpleMaxFlowProgram {
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// Instantiate a SimpleMaxFlow solver.
MaxFlow maxFlow = new MaxFlow();
// 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.
// From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = new int[] {0, 0, 0, 1, 1, 2, 2, 3, 3};
int[] endNodes = new int[] {1, 2, 3, 2, 4, 3, 4, 2, 4};
int[] capacities = new int[] {20, 30, 10, 40, 30, 10, 20, 5, 20};
// Add each arc.
for (int i = 0; i < startNodes.length; ++i) {
int arc = maxFlow.addArcWithCapacity(startNodes[i], endNodes[i], capacities[i]);
if (arc != i) {
throw new Exception("Internal error");
}
}
// Find the maximum flow between node 0 and node 4.
MaxFlow.Status status = maxFlow.solve(0, 4);
if (status == MaxFlow.Status.OPTIMAL) {
System.out.println("Max. flow: " + maxFlow.getOptimalFlow());
System.out.println();
System.out.println(" Arc Flow / Capacity");
for (int i = 0; i < maxFlow.getNumArcs(); ++i) {
System.out.println(maxFlow.getTail(i) + " -> " + maxFlow.getHead(i) + " "
+ maxFlow.getFlow(i) + " / " + maxFlow.getCapacity(i));
}
} else {
System.out.println("Solving the max flow problem failed. Solver status: " + status);
}
}
private SimpleMaxFlowProgram() {}
}
C#
// From Taha 'Introduction to Operations Research', example 6.4-2.
using System;
using Google.OrTools.Graph;
public class SimpleMaxFlowProgram
{
static void Main()
{
// Instantiate a SimpleMaxFlow solver.
MaxFlow maxFlow = new MaxFlow();
// 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.
// From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = { 0, 0, 0, 1, 1, 2, 2, 3, 3 };
int[] endNodes = { 1, 2, 3, 2, 4, 3, 4, 2, 4 };
int[] capacities = { 20, 30, 10, 40, 30, 10, 20, 5, 20 };
// Add each arc.
for (int i = 0; i < startNodes.Length; ++i)
{
int arc = maxFlow.AddArcWithCapacity(startNodes[i], endNodes[i], capacities[i]);
if (arc != i)
throw new Exception("Internal error");
}
// Find the maximum flow between node 0 and node 4.
MaxFlow.Status status = maxFlow.Solve(0, 4);
if (status == MaxFlow.Status.OPTIMAL)
{
Console.WriteLine("Max. flow: " + maxFlow.OptimalFlow());
Console.WriteLine("");
Console.WriteLine(" Arc Flow / Capacity");
for (int i = 0; i < maxFlow.NumArcs(); ++i)
{
Console.WriteLine(maxFlow.Tail(i) + " -> " + maxFlow.Head(i) + " " +
string.Format("{0,3}", maxFlow.Flow(i)) + " / " +
string.Format("{0,3}", maxFlow.Capacity(i)));
}
}
else
{
Console.WriteLine("Solving the max flow problem failed. Solver status: " + status);
}
}
}