다음 섹션에서는 최대 흐름의 예를 보여줍니다. (최대 흐름) 문제입니다.
최대 흐름의 예
이 문제는 교통수단을 나타내는 아래의 그래프로 네트워크:
노드 0 (소스)에서 노드 4( 싱크). 원호 옆의 숫자는 용량이며 원호의 용량은 1시간 내에 원호를 가로질러 운반할 수 있는 설정할 수 있습니다 용량은 문제의 제약 조건입니다.
흐름은 각 원호( 다음 유량 보존 규칙을 충족하는 유량)입니다.
최대 유량 문제는 전체 네트워크가 가능한 한 큰 규모입니다.
다음 섹션에서는 최대 흐름을 찾는 프로그램을 제시합니다. 소스 (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"
자바
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;
자바
// Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow();
C#
// Instantiate a SimpleMaxFlow solver. MaxFlow maxFlow = new MaxFlow();
데이터 정의
3개의 배열(시작 노드, 끝 노드)로 문제에 대한 그래프를 정의합니다. 노드, 원호의 용량을 정의합니다 각 배열의 길이는 나타냅니다.
각 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};
자바
// 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]); }
자바
// 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);
자바
// 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; }
자바
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; }
자바
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); } } }