সর্বোচ্চ প্রবাহ

নিম্নলিখিত বিভাগগুলিতে, আপনি সর্বাধিক প্রবাহ ( সর্বোচ্চ প্রবাহ ) সমস্যার একটি উদাহরণ পান।

সর্বাধিক প্রবাহের উদাহরণ

সমস্যাটি নিম্নলিখিত গ্রাফ দ্বারা সংজ্ঞায়িত করা হয়েছে, যা একটি পরিবহন নেটওয়ার্কের প্রতিনিধিত্ব করে:

আপনি নোড 0 ( উৎস ) থেকে নোড 4 ( সিঙ্ক ) এ উপাদান পরিবহন করতে চান। আর্কসের পাশের সংখ্যাগুলি হল তাদের ধারণক্ষমতা — একটি চাপের ধারণক্ষমতা হল সর্বোচ্চ পরিমাণ যা একটি নির্দিষ্ট সময়ের মধ্যে এটি জুড়ে পরিবহন করা যেতে পারে। সামর্থ্যগুলি সমস্যার জন্য সীমাবদ্ধতা।

একটি প্রবাহ হল প্রতিটি আর্কের ( প্রবাহের পরিমাণ ) একটি অ-ঋণাত্মক সংখ্যার একটি অ্যাসাইনমেন্ট যা নিম্নলিখিত প্রবাহ সংরক্ষণের নিয়মকে সন্তুষ্ট করে:

দ্রষ্টব্য: উৎস বা সিঙ্ক ব্যতীত প্রতিটি নোডে, নোডের দিকে অগ্রসর হওয়া সমস্ত আর্কের মোট প্রবাহ এটি থেকে বেরিয়ে আসা সমস্ত আর্কের মোট প্রবাহের সমান।

সর্বাধিক প্রবাহের সমস্যা হল এমন একটি প্রবাহ খুঁজে বের করা যার জন্য সমগ্র নেটওয়ার্কের জন্য প্রবাহের পরিমাণ যতটা সম্ভব বড়।

নিম্নলিখিত বিভাগগুলি উৎস (0) থেকে সিঙ্ক (4) পর্যন্ত সর্বাধিক প্রবাহ খুঁজে পেতে একটি প্রোগ্রাম উপস্থাপন করে।

লাইব্রেরি আমদানি করুন

নিম্নলিখিত কোড প্রয়োজনীয় লাইব্রেরি আমদানি করে।

পাইথন

import numpy as np

from ortools.graph.python import max_flow

সি++

#include <cstdint>
#include <vector>

#include "ortools/graph/max_flow.h"

জাভা

import com.google.ortools.Loader;
import com.google.ortools.graph.MaxFlow;

সি#

using System;
using Google.OrTools.Graph;

সমাধানকারী ঘোষণা করুন

সমস্যা সমাধানের জন্য, আপনি SimpleMaxFlow সমাধানকারী ব্যবহার করতে পারেন।

পাইথন

# Instantiate a SimpleMaxFlow solver.
smf = max_flow.SimpleMaxFlow()

সি++

// Instantiate a SimpleMaxFlow solver.
SimpleMaxFlow max_flow;

জাভা

// Instantiate a SimpleMaxFlow solver.
MaxFlow maxFlow = new MaxFlow();

সি#

// Instantiate a SimpleMaxFlow solver.
MaxFlow maxFlow = new MaxFlow();

ডেটা সংজ্ঞায়িত করুন

আপনি সূচনা নোড, শেষ নোড এবং আর্কসের ক্ষমতার জন্য তিনটি অ্যারে সহ সমস্যার জন্য গ্রাফটি সংজ্ঞায়িত করুন। প্রতিটি অ্যারের দৈর্ঘ্য গ্রাফের আর্কের সংখ্যার সমান।

প্রতিটি i এর জন্য, arc i start_nodes[i] থেকে end_nodes[i] এ যায় এবং এর ক্ষমতা capacities[i] দ্বারা দেওয়া হয়। পরবর্তী বিভাগ দেখায় কিভাবে এই ডেটা ব্যবহার করে আর্ক তৈরি করতে হয়।

পাইথন

# 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])

সি++

// 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};

সি#

// 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 পদ্ধতিটি ব্যবহার করে প্রদত্ত ক্ষমতা সহ স্টার্ট নোড থেকে শেষ নোড পর্যন্ত একটি চাপ তৈরি করেন। সামর্থ্যগুলি সমস্যার জন্য সীমাবদ্ধতা।

পাইথন

# 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)

সি++

// 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");
  }
}

সি#

// 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");
}

সমাধানকারীকে আহ্বান করুন

এখন সমস্ত আর্ক সংজ্ঞায়িত করা হয়েছে, যা বাকি আছে তা হল সমাধানকারীকে আহ্বান করা এবং ফলাফলগুলি প্রদর্শন করা। আপনি সোর্স (0) এবং সিঙ্ক (4) প্রদান করে Solve() পদ্ধতি ব্যবহার করুন।

পাইথন

# Find the maximum flow between node 0 and node 4.
status = smf.solve(0, 4)

সি++

// 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);

সি#

// Find the maximum flow between node 0 and node 4.
MaxFlow.Status status = maxFlow.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 (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);
}

সি#

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 অধীনে প্রদর্শিত হয়।

সম্পূর্ণ প্রোগ্রাম

এটি সব একসাথে করা, এখানে সম্পূর্ণ প্রোগ্রাম আছে.

পাইথন

"""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()

সি++

// 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() {}
}

সি#

// 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);
        }
    }
}