ज़्यादा से ज़्यादा फ़्लो

नीचे दिए गए सेक्शन में, आपको सबसे ज़्यादा फ़्लो का उदाहरण दिया गया है (मैक्स फ़्लो) की समस्या.

मैक्स फ़्लो का उदाहरण

समस्या को नीचे दिए गए ग्राफ़ से बताया गया है, जो परिवहन का प्रतिनिधित्व करता है नेटवर्क:

आपको नोड 0 (सोर्स) से नोड 4 ( sink). चाप के बगल में मौजूद संख्याएं उनकी क्षमता होती हैं — चाप की क्षमता, वह ज़्यादा से ज़्यादा उतनी होती है जितनी तय समयावधि. क्षमता, समस्या की सीमा है.

फ़्लो हर आर्क के लिए एक नॉन-नेगेटिव नंबर असाइन करता है ( flow की रकम) जो नीचे दिए गए फ़्लो संरक्षण नियम के मुताबिक है:

ध्यान दें: सोर्स या सिंक के अलावा, हर नोड में, सभी सोर्स का कुल फ़्लो नोड तक ले जाने वाले चाप, इससे जाने वाले सभी चाप के कुल फ़्लो के बराबर होते हैं.

मैक्स फ़्लो से जुड़ी समस्या उस फ़्लो का पता लगाना है जिसके लिए फ़्लो का योग होता है पूरा नेटवर्क जितना हो सके उतना बड़ा हो.

नीचे दिए गए सेक्शन में प्रोग्राम के बारे में बताया गया है, ताकि आपको सोर्स (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);
        }
    }
}