Aşağıdaki bölümlerde maksimum akış (maksimum akış) problemiyle ilgili bir örnek verilmiştir.
Maksimum akış örneği
Sorun, bir ulaşım ağını temsil eden aşağıdaki grafikle tanımlanmaktadır:
Düğüm 0'dan (kaynak) düğüm 4'e (havuz) malzeme taşımak istiyorsunuz. Yayların yanındaki sayılar kapasitelerini ifade eder. Bir yay kapasitesi, sabit bir süre içinde kendi üzerinde aktarılabilecek maksimum tutardır. Kapasiteler, problemin kısıtlarıdır.
Akış, aşağıdaki akışın korunması kuralını karşılayan her bir yay için negatif olmayan bir sayı (akış miktarı) atamasıdır:
Maksimum akış sorunu, tüm ağın akış miktarları toplamının mümkün olduğunca büyük olduğu bir akış bulmaktır.
Aşağıdaki bölümlerde, kaynaktan (0) havuza (4) doğru maksimum akışı bulan bir program sunulmaktadır.
Kitaplıkları içe aktarın
Aşağıdaki kod gerekli kitaplığı içe aktarır.
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;
Çözücüyü bildirme
Sorunu çözmek için SimpleMaxFlow çözücüyü kullanabilirsiniz.
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();
Verileri tanımlama
Sorunun grafiğini; başlangıç düğümleri, bitiş düğümleri ve yay kapasiteleri için üç diziyle tanımlarsınız. Her dizinin uzunluğu, grafikteki yayların sayısına eşittir.
Her i için i yayı start_nodes[i] ile end_nodes[i] arasında gidip gelir ve kapasitesi capacities[i] ile belirtilir. Bir sonraki bölümde, bu veriler kullanılarak yayların nasıl oluşturulacağı gösterilmektedir.
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 };
Yayları ekleyin
Her başlangıç düğümü ve bitiş düğümü için, AddArcWithCapacity yöntemini kullanarak belirtilen kapasiteye sahip bir başlangıç düğümü ile bitiş düğümü arasında bir yay oluşturursunuz. Kapasiteler, problemin kısıtlarıdır.
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");
}
Çözücüyü çağır
Tüm yaylar tanımlandığına göre, geriye kalan tek şey çözücüyü çağırmak ve sonuçları görüntülemektir. Kaynak (0) ve havuzu (4) sağlayarak Solve() yöntemini çağırırsınız.
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);
Sonuçları görüntüleyin
Artık her bir yaydaki akışı görüntüleyebilirsiniz.
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);
}
Programın çıktısı aşağıdaki gibidir:
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]
Her bir yaydaki akış miktarları Flow altında gösterilir.
Programları tamamlayın
Programların tümünü bir araya getirdiğimizde aşağıdaki programlardan yararlanabilirsiniz.
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);
}
}
}