گلوگاهِ ظرفیتِ مسیر تماس؛ جریانِ بیشینه و برشِ کمینه با پایتون

۱. ظرفیتِ ورودی با ظرفیتِ مسیرِ کامل یکی نیست

فرض کنید برای بررسیِ یک مسیر تماس، چند بخشِ میانی را با یک گرافِ جهت‌دار نمایش داده‌ایم. روی هر یال، تعدادِ واحدهایی نوشته‌ایم که همان بخش می‌تواند هم‌زمان عبور دهد. جمعِ ظرفیتِ خروجیِ مبدأ، فقط یک سقفِ اولیه است؛ ممکن است همهٔ شاخه‌ها در پایین‌دست به گذرگاهی کوچک برسند. پرسشِ این درس این است: در همین مدلِ داده‌شده، بیشترین مقدارِ قابلِ عبور چقدر است و کدام مرز، آن را محدود می‌کند؟ پاسخ را همراهِ گواهِ برش می‌سازیم تا صرفاً یک عددِ بی‌توضیح نداشته باشیم.

ظرفیت در این مثال، شمارِ صحیحِ واحدهای تجمیعی و هم‌ارز است. نه ثانیه است، نه بیت‌برثانیه و نه تماسِ نام‌داری که الزاماً یک مسیرِ ازپیش‌تعیین‌شده دارد. حفظِ جریان در هر رأسِ میانی برقرار است و فقط یک مبدأ و یک مقصد داریم. محدودیتِ کُدک، اولویت، چند گروهِ مستقلِ ترافیک و تغییرِ ظرفیت با زمان را وارد نکرده‌ایم. بنابراین نتیجه را نباید به ظرفیتِ واقعیِ یک مرکز تلفن یا پذیرشِ تماس‌های دارای محدودیت‌های متفاوت تبدیل کرد.

تابعِ capacity_cut_report بین دو تا شش رأس می‌پذیرد. یال‌ها یک تاپلِ آماده از سه‌تایی‌های مبدأ، مقصد و ظرفیت‌اند؛ ظرفیتِ صحیح از صفر تا چهار است. شمارهٔ رأس‌ها از صفر شروع می‌شود، دو سرِ هر یال متفاوت‌اند و هر زوجِ جهت‌دار فقط یک بار می‌آید. دور و یالِ مخالف مجازند؛ یالِ غایب ظرفیتِ صفر دارد. نوع‌های دقیقِ داخلی را می‌خواهیم، پس بولی، زیرکلاسِ عدد، مولد و تبدیلِ ضمنی پذیرفته نیست. همهٔ ردیف‌ها پیش از ساختِ ماتریس و پیمایش بررسی می‌شوند.

این مسئله با شبیه‌سازیِ پذیرشِ بازه‌های تماس فرق دارد: آنجا زمانِ ورود و آزادشدنِ جایگاه مهم بود؛ اینجا ظرفیتِ یک شبکهٔ ثابت را می‌پرسیم. همچنین مدلِ اتلافِ ارلنگ B دربارهٔ احتمالِ انسداد زیرِ فرض‌های تصادفیِ مشخص است. هیچ احتمالِ ورود یا مدتِ خدمتی در داده‌های این درس وجود ندارد.

۲. باقیمانده و پس‌گرفتنِ انتخابِ قبلی را بسازیم

ماتریسِ باقیمانده ابتدا همان ظرفیت‌های داده‌شده است. با جست‌وجوی سطحی، مسیری با ظرفیتِ مثبت از مبدأ به مقصد پیدا می‌کنیم؛ برای قطعیت، همسایه‌ها را به ترتیبِ شماره می‌خوانیم. کوچک‌ترین ظرفیتِ باقیماندهٔ مسیر، مقدارِ افزایش است. این مقدار از جهتِ رفت کم و به جهتِ برگشت اضافه می‌شود. مسیرِ برگشت اجازه می‌دهد بخشی از تخصیصِ قبلی را پس بگیریم و انتخابِ بهتری بسازیم؛ وجودش به معنای کشفِ یک کانالِ فیزیکیِ تازه نیست.

در نمونهٔ شش‌رأسیِ کد، نخست مسیرِ صفر، یک، سه، پنج انتخاب می‌شود. اگر آن انتخاب را قطعی بدانیم و فقط ظرفیتِ رفتِ باقی‌مانده را ببینیم، واحدِ دیگری عبور نمی‌کند. اما مسیرِ بعدیِ صفر، دو، سه، یک، چهار، پنج از باقیماندهٔ سه به یک استفاده می‌کند. این حرکت، مصرفِ قبلیِ یک به سه را لغو می‌کند. دو واحد در نهایت عبور می‌کنند؛ پس حریصانه مصرف‌کردنِ یک مسیر بدون امکانِ اصلاح، کافی نیست.

وقتی ورودی در هر دو جهت یال دارد، ظرفیتِ اصلیِ هر جهت جدا ثبت می‌شود. مقدارِ باقیمانده در یک جهت می‌تواند هم فرصتِ مصرف‌نشدهٔ همان جهت و هم امکانِ لغوِ جریانِ مخالف را نمایندگی کند. برای محاسبهٔ برش، همیشه به ظرفیتِ اصلی برمی‌گردیم. این نمایشِ ماتریسی، پیاده‌سازیِ خودمان است؛ الزامِ نگاشتِ یالِ معکوس در مستندِ Boost را نباید با قراردادِ ذخیره‌سازیِ کدِ پایتون یکسان گرفت.

پایانِ حلقه در این دامنه روشن است: هر افزایش، دست‌کم یک واحدِ صحیح به مقدار اضافه می‌کند و مقدار از جمعِ ظرفیتِ خروجیِ مبدأ بیشتر نمی‌شود. این جمع حداکثر بیست است؛ بنابراین بیش از بیست افزایشِ موفق نداریم. این استدلال، اندازه‌گیریِ سرعت یا وعدهٔ کارایی برای شبکه‌های بزرگ و ظرفیت‌های اعشاری نیست.

۳. برشِ کمینه، گلوگاهِ قابلِ بررسی می‌دهد

در نمونهٔ پنج‌رأسی، ظرفیتِ صفر به یک و صفر به دو هرکدام چهار است. شاخه‌ها از یک و دو به سه می‌رسند، اما یالِ سه به چهار فقط دو واحد جا دارد. جمعِ ورودی‌ها هشت است، ولی برشِ جداکنندهٔ رأسِ چهار از بقیه فقط دو واحد ظرفیت دارد. جریانِ ساخته‌شده نیز دو است. این برابری نشان می‌دهد در همین مدل، هیچ انتخابِ دیگری نمی‌تواند مقدار را از دو بالاتر ببرد.

برش یعنی تقسیمِ رأس‌ها به دو بخش که مبدأ در بخشِ نخست و مقصد در بخشِ دوم باشد. ظرفیتِ آن، جمعِ ظرفیتِ اصلیِ یال‌های خروجی از بخشِ نخست است. یال‌های ورودی از سمتِ مقابل را جمع نمی‌کنیم. هر جریانِ مجاز حداکثر به اندازهٔ هر برش است. وقتی دیگر مسیرِ باقیمانده‌ای وجود ندارد، رأس‌های قابلِ دسترسی از مبدأ یک برش می‌سازند که ظرفیتش با جریان برابر است؛ این همان گواهِ بهینگیِ موردِ استفادهٔ ماست.

چند برش می‌توانند مقدارِ برابر داشته باشند. در زنجیرهٔ صفر به یک به دو با ظرفیت‌های یک، هم بخشِ نخستِ شاملِ فقط صفر و هم بخشِ شاملِ صفر و یک، برشِ کمینه می‌دهند. خروجیِ ما بخشِ کمینه از نظرِ شمول را برمی‌گرداند: فقط صفر. دلیلش این است که دسترسیِ مثبت در باقیمانده داخلِ بخشِ نخستِ هر برشِ بهینه می‌ماند و خودش نیز برشِ بهینه است؛ پس برابرِ اشتراکِ همهٔ آن بخش‌هاست. این سیاستِ خروجیِ خودمان است، نه ادعای یکسانیِ تقسیم‌بندی با NetworkX.

۴. کدِ کامل و مرجعِ مستقلِ همهٔ برش‌ها

کد فقط به کتابخانهٔ استانداردِ پایتون نیاز دارد. گزارشِ بازگشتی شاملِ مقدار، دو بخشِ مرتب و یال‌های اصلیِ مثبتِ عبوری از مرز است؛ همهٔ اجزای تو‌در‌تو تغییرناپذیرند. کدِ کامل و خروجیِ اجرای ثبت‌شده در ادامه قرار می‌گیرند. نسخهٔ محیط در خودِ خروجی آمده است؛ مستنداتِ NetworkX و Boost منبعِ فنی‌اند و این برنامه هیچ‌کدام از آن دو کتابخانه را اجرا نمی‌کند.

"""Small supplied integer-capacity network, not a real telephony capacity test."""
from itertools import permutations, product
import json
import platform
import sys
from typing import NamedTuple

AUTHOR_MAIN_ENABLED = True
MAX_VERTICES = 6
MAX_CAPACITY = 4


class FlowCutReport(NamedTuple):
    value: int
    source_side: tuple
    sink_side: tuple
    cut_edges: tuple


def _admit(vertex_count, edges, source, sink):
    if type(vertex_count) is not int:
        raise TypeError('vertex_count must be an exact int')
    if not 2 <= vertex_count <= MAX_VERTICES:
        raise ValueError('own vertex range is 2..6')
    if type(source) is not int or type(sink) is not int:
        raise TypeError('terminals must be exact ints')
    if not 0 <= source < vertex_count or not 0 <= sink < vertex_count:
        raise ValueError('terminal outside declared vertex range')
    if source == sink:
        raise ValueError('source and sink must differ')
    if type(edges) is not tuple:
        raise TypeError('edges must be an exact materialized tuple')
    if len(edges) > vertex_count * (vertex_count - 1):
        raise ValueError('too many declared directed pairs')
    seen = set()
    for edge in edges:
        if type(edge) is not tuple or len(edge) != 3:
            raise TypeError('each edge must be an exact triple tuple')
        u, v, capacity = edge
        if any(type(value) is not int for value in edge):
            raise TypeError('endpoints and capacities must be exact ints')
        if not 0 <= u < vertex_count or not 0 <= v < vertex_count or u == v:
            raise ValueError('endpoints must be distinct declared vertices')
        if not 0 <= capacity <= MAX_CAPACITY:
            raise ValueError('own integer capacity range is 0..4')
        if (u, v) in seen:
            raise ValueError('duplicate ordered pair, even with a new capacity')
        seen.add((u, v))
    return tuple(sorted(edges))


def _capacity_matrix(vertex_count, edges):
    matrix = [[0] * vertex_count for _ in range(vertex_count)]
    for u, v, capacity in edges:
        matrix[u][v] = capacity
    return matrix


def _bfs_path(residual, source, sink):
    parent = [-1] * len(residual)
    parent[source] = source
    queue = [source]
    for u in queue:
        for v in range(len(residual)):
            if parent[v] < 0 and residual[u][v] > 0:
                parent[v] = u
                if v == sink:
                    reverse_path = [sink]
                    while reverse_path[-1] != source:
                        reverse_path.append(parent[reverse_path[-1]])
                    return tuple(reversed(reverse_path))
                queue.append(v)
    return None


def capacity_cut_report(vertex_count, edges, source, sink):
    """Return max integer flow and the inclusion-minimal minimum-cut source side.

    Missing edges have zero capacity. Supplied antiparallel edges are admitted.
    Residual reverse increments cancel prior net flow, not physical capacity.
    No named/unsplittable calls, time, probabilities, devices or library API.
    """
    ordered = _admit(vertex_count, edges, source, sink)
    capacity = _capacity_matrix(vertex_count, ordered)
    residual = [row.copy() for row in capacity]
    value = augmentations = 0
    source_bound = sum(capacity[source])
    while True:
        path = _bfs_path(residual, source, sink)
        if path is None:
            break
        amount = min(residual[u][v] for u, v in zip(path, path[1:]))
        for u, v in zip(path, path[1:]):
            residual[u][v] -= amount
            residual[v][u] += amount
        value += amount
        augmentations += 1
        # Each success raises integer value by >=1, while value<=source_bound.
        if amount < 1 or augmentations > source_bound:
            raise ArithmeticError('violated finite integer augmentation bound')

    reached = {source}
    queue = [source]
    for u in queue:
        for v in range(vertex_count):
            if residual[u][v] > 0 and v not in reached:
                reached.add(v)
                queue.append(v)
    source_side = tuple(sorted(reached))
    sink_side = tuple(v for v in range(vertex_count) if v not in reached)
    cut_edges = tuple((u, v, c) for u, v, c in ordered
                      if c > 0 and u in reached and v not in reached)
    if sink in reached or value != sum(c for _, _, c in cut_edges):
        raise ArithmeticError('flow/cut equality certificate failed')
    return FlowCutReport(value, source_side, sink_side, cut_edges)


def exhaustive_cut_reference(vertex_count, edges, source, sink):
    """Trusted fixtures only: enumerate partitions, no flow/residual/traversal.

    The intersection of every minimizing source side gives the expected
    inclusion-minimal source side. No production helper is called here.
    """
    best = None
    common = set(range(vertex_count))
    cut_count = 0
    for mask in range(1 << vertex_count):
        if not (mask & (1 << source)) or mask & (1 << sink):
            continue
        side = {v for v in range(vertex_count) if mask & (1 << v)}
        cost = sum(c for u, v, c in edges if u in side and v not in side)
        if best is None or cost < best:
            best, common = cost, side
        elif cost == best:
            common = common & side
        cut_count += 1
    expected = {'value': best, 'source_side': tuple(sorted(common)),
                'sink_side': tuple(v for v in range(vertex_count) if v not in common),
                'cut_edges': tuple(sorted((u, v, c) for u, v, c in edges
                                         if c > 0 and u in common and v not in common))}
    return expected, cut_count


def _raises(kind, function, *args):
    try:
        function(*args)
    except Exception as error:
        return type(error) is kind
    return False


def run_example():
    checks = {}
    shared_edges = ((0, 1, 4), (0, 2, 4), (1, 3, 3), (2, 3, 2), (3, 4, 2))
    shared = capacity_cut_report(5, shared_edges, 0, 4)
    checks['shared_downstream_cut_two_despite_entry_capacity_eight'] = (
        shared == FlowCutReport(2, (0, 1, 2, 3), (4,), ((3, 4, 2),))
        and sum(c for u, v, c in shared_edges if u == 0) == 8)

    reverse_edges = ((0, 1, 1), (0, 2, 1), (1, 3, 1), (1, 4, 1),
                     (2, 3, 1), (3, 5, 1), (4, 5, 1))
    reverse_case = capacity_cut_report(6, reverse_edges, 0, 5)
    # Ascending BFS first chooses0,1,3,5. The next augmentation must use
    # residual3->1 to undo1->3 and reach1->4->5; forward-only remainder has0.
    forward_only_after_first = tuple((u, v, c - int((u, v) in ((0, 1), (1, 3), (3, 5))))
                                    for u, v, c in reverse_edges)
    forward_bound, _ = exhaustive_cut_reference(6, forward_only_after_first, 0, 5)
    checks['reverse_residual_recovers_route_lost_by_forward_only_commitment'] = (
        reverse_case.value == 2 and reverse_case.source_side == (0,)
        and forward_bound['value'] == 0 and 1 + forward_bound['value'] < reverse_case.value)

    directed_edges = ((0, 1, 2), (1, 0, 4), (1, 2, 1), (2, 1, 4))
    directed = capacity_cut_report(3, directed_edges, 0, 2)
    checks['cut_counts_original_outgoing_capacity_not_incoming_or_residual'] = (
        directed == FlowCutReport(1, (0, 1), (2,), ((1, 2, 1),))
        and sum(c for u, v, c in directed_edges if u == 2 and v in (0, 1)) == 4)

    tied_edges = ((0, 1, 1), (1, 2, 1))
    tied = capacity_cut_report(3, tied_edges, 0, 2)
    checks['equal_cut_values_choose_intersection_not_arbitrary_source_partition'] = (
        tied == FlowCutReport(1, (0,), (1, 2), ((0, 1, 1),))
        and 1 == sum(c for u, v, c in tied_edges if u in (0, 1) and v == 2))

    disconnected = capacity_cut_report(4, ((0, 1, 2), (2, 3, 4)), 0, 3)
    empty = capacity_cut_report(4, (), 0, 3)
    zeros = capacity_cut_report(4, ((0, 1, 0), (1, 3, 0)), 0, 3)
    checks['disconnection_empty_and_zero_edges_are_valid_zero_flow'] = (
        disconnected == FlowCutReport(0, (0, 1), (2, 3), ())
        and empty == zeros == FlowCutReport(0, (0,), (1, 2, 3), ()))

    cyclic_edges = ((0, 1, 3), (1, 2, 2), (2, 1, 1), (2, 3, 2), (1, 3, 1), (3, 0, 4))
    cyclic = capacity_cut_report(4, cyclic_edges, 0, 3)
    cyclic_expected, _ = exhaustive_cut_reference(4, cyclic_edges, 0, 3)
    checks['cycles_antiparallel_edges_and_edges_into_source_are_admitted'] = (
        cyclic.value == 3 and cyclic._asdict() == cyclic_expected)

    family_ok = True
    family_profiles = enumerated_cuts = 0
    pairs = ((0, 1), (0, 2), (1, 2), (2, 1), (1, 3), (2, 3))
    for capacities in product((0, 1, 2), repeat=len(pairs)):
        edges = tuple((u, v, c) for (u, v), c in zip(pairs, capacities))
        actual = capacity_cut_report(4, edges, 0, 3)
        expected, number = exhaustive_cut_reference(4, edges, 0, 3)
        family_ok = family_ok and actual._asdict() == expected
        family_profiles += 1
        enumerated_cuts += number
    checks['independent_all_cut_reference_729_networks_in_ONE_family'] = (
        family_ok and family_profiles == 729 and enumerated_cuts == 2916)

    order_ok = all(capacity_cut_report(5, tuple(order), 0, 4) == shared
                   for order in permutations(shared_edges))
    renaming_count = 0
    for order in permutations(range(1, 5)):
        rename = (0,) + order
        changed = tuple((rename[u], rename[v], c) for u, v, c in shared_edges)
        result = capacity_cut_report(5, changed, rename[0], rename[4])
        expected_side = tuple(sorted(rename[v] for v in shared.source_side))
        expected_edges = tuple(sorted((rename[u], rename[v], c) for u, v, c in shared.cut_edges))
        order_ok = order_ok and result.value == shared.value and result.source_side == expected_side
        order_ok = order_ok and result.cut_edges == expected_edges
        renaming_count += 1
    checks['input_edge_order_and_vertex_renaming_preserve_declared_result'] = (
        order_ok and renaming_count == 24)

    seed = ((0, 1, 1), (0, 2, 2), (1, 3, 1), (2, 3, 1))
    base = capacity_cut_report(4, seed, 0, 3)
    monotone = True
    for index in range(len(seed)):
        enlarged = tuple((u, v, c + int(i == index)) for i, (u, v, c) in enumerate(seed))
        changed = capacity_cut_report(4, enlarged, 0, 3)
        monotone = monotone and base.value <= changed.value <= base.value + 1
    scaled = capacity_cut_report(4, tuple((u, v, 2 * c) for u, v, c in seed), 0, 3)
    checks['one_edge_capacity_monotonicity_and_uniform_integer_scaling'] = (
        monotone and scaled.value == 2 * base.value and scaled.source_side == base.source_side
        and scaled.cut_edges == tuple((u, v, 2 * c) for u, v, c in base.cut_edges))

    checks['adding_zero_capacity_edges_does_not_create_a_path_or_change_report'] = (
        capacity_cut_report(3, tied_edges + ((0, 2, 0), (2, 0, 0)), 0, 2) == tied)

    nonbottleneck = ((0, 1, 3), (0, 2, 3), (1, 3, 2), (2, 3, 2), (3, 4, 1))
    raised = ((0, 1, 4),) + nonbottleneck[1:]
    checks['raising_an_entrance_capacity_can_leave_shared_cut_unchanged'] = (
        capacity_cut_report(5, nonbottleneck, 0, 4)
        == capacity_cut_report(5, raised, 0, 4)
        == FlowCutReport(1, (0, 1, 2, 3), (4,), ((3, 4, 1),)))

    class IntChild(int):
        pass
    class TupleChild(tuple):
        pass
    bad = [(TypeError, (True, (), 0, 1)), (TypeError, (2.0, (), 0, 1)),
           (TypeError, (IntChild(2), (), 0, 1)), (ValueError, (1, (), 0, 0)),
           (ValueError, (7, (), 0, 1)), (TypeError, (2, [], 0, 1)),
           (TypeError, (2, TupleChild(()), 0, 1)), (TypeError, (2, (), True, 1)),
           (TypeError, (2, (), 0, 1.0)), (ValueError, (2, (), -1, 1)),
           (ValueError, (2, (), 0, 2)), (ValueError, (2, (), 0, 0)),
           (TypeError, (2, ([0, 1, 1],), 0, 1)),
           (TypeError, (2, ((0, 1),), 0, 1)),
           (TypeError, (2, (TupleChild((0, 1, 1)),), 0, 1)),
           (ValueError, (2, ((0, 0, 1),), 0, 1)),
           (ValueError, (2, ((0, 2, 1),), 0, 1)),
           (ValueError, (2, ((0, 1, 5),), 0, 1)),
           (ValueError, (2, ((0, 1, -1),), 0, 1)),
           (ValueError, (2, ((0, 1, 1), (0, 1, 2)), 0, 1)),
           (ValueError, (2, ((0, 1, 1),) * 3, 0, 1))]
    for coordinate in range(3):
        for value in (False, 0.0, None, '0', IntChild(0), 1j):
            row = [0, 1, 1]
            row[coordinate] = value
            bad.append((TypeError, (2, (tuple(row),), 0, 1)))
    checks['strict_exact_types_bounds_duplicate_pairs_selfloops_and_terminals'] = all(
        _raises(kind, capacity_cut_report, *args) for kind, args in bad)

    touched = []
    class ForbiddenNumber:
        def __int__(self):
            touched.append('int')
            raise AssertionError('implicit number conversion')
        def __lt__(self, other):
            touched.append('compare')
            raise AssertionError('foreign comparison')
    def lazy():
        touched.append('generator')
        yield (0, 1, 1)
    generated = lazy()
    guarded_bad = [(TypeError, (3, generated, 0, 2)),
                   (TypeError, (3, ((0, 1, 1), (1, 2, ForbiddenNumber())), 0, 2)),
                   (ValueError, (3, ((0, 1, 1), (1, 2, 5)), 0, 2))]
    matrix_calls = []
    real_matrix = _capacity_matrix
    def forbidden_matrix(*args):
        matrix_calls.append(True)
        raise AssertionError('invalid input reached matrix construction')
    try:
        globals()['_capacity_matrix'] = forbidden_matrix
        early = all(_raises(kind, capacity_cut_report, *args) for kind, args in guarded_bad)
    finally:
        globals()['_capacity_matrix'] = real_matrix
        generated.close()
    checks['whole_late_admission_precedes_matrix_allocation_and_lazy_hooks'] = (
        early and matrix_calls == [] and touched == [])

    complete_edges = tuple((u, v, MAX_CAPACITY) for u in range(6) for v in range(6) if u != v)
    maximum = capacity_cut_report(6, complete_edges, 0, 5)
    again = capacity_cut_report(5, shared_edges, 0, 4)
    def assign_field():
        again.value = 999
    def assign_inner():
        again.cut_edges[0][2] = 999
    encoded = json.dumps(again._asdict(), ensure_ascii=True, allow_nan=False)
    checks['maximum_caps_fresh_nested_immutable_report_and_strict_JSON'] = (
        maximum.value == 20 and maximum.source_side == (0,) and len(complete_edges) == 30
        and again == shared and again is not shared and hash(again) == hash(shared)
        and _raises(AttributeError, assign_field) and _raises(TypeError, assign_inner)
        and json.loads(encoded)['value'] == shared.value
        and all(type(x) is int for row in again.cut_edges for x in row))

    assert len(checks) == 14 and all(type(v) is bool and v for v in checks.values()), checks
    return {'runtime': {'python': platform.python_version(), 'implementation': platform.python_implementation(),
                        'dependencies': 'Python standard library only'},
            'scope': 'Supplied finite directed integer-capacity abstraction; no real calls or physical capacity measurement',
            'API': 'capacity_cut_report(vertex_count, edges, source, sink)',
            'own_bounds': {'vertices': [2, 6], 'capacity': [0, 4], 'maximum_augmentation_successes': 20},
            'manual_shared_bottleneck': {'edges': shared_edges, 'entry_capacity': 8, 'result': shared._asdict()},
            'manual_reverse_residual_case': {'edges': reverse_edges, 'result': reverse_case._asdict(),
                'forward_only_remainder_value_after_first_hand_path': forward_bound['value']},
            'manual_directed_cut': directed._asdict(), 'multiple_equal_cuts_example': tied._asdict(),
            'disconnected_example': disconnected._asdict(), 'antiparallel_cycle_example': cyclic._asdict(),
            'maximum_six_vertex_example': maximum._asdict(),
            'independent_expected_path': 'Enumerate source-sink partitions, minimize original outgoing capacity, intersect all minimizing source sides; no residual graph or traversal',
            'finite_network_profiles_ONE_group': family_profiles, 'enumerated_cuts_in_same_group': enumerated_cuts,
            'edge_order_permutations_in_ONE_group': 120, 'vertex_renamings_in_same_group': renaming_count,
            'strict_invalid_profiles_in_ONE_group': len(bad), 'late_guarded_invalid_profiles': len(guarded_bad),
            'invalid_matrix_allocations': len(matrix_calls), 'lazy_or_conversion_hook_calls': len(touched),
            'checks': checks, 'groups_total': len(checks),
            'limits': ['Own small API and source-side tie policy, not NetworkX or Boost API equivalence.',
                       'Integer aggregate interchangeable route units; no named unsplittable-call or codec eligibility constraints.',
                       'No arrival/service times, queue, Erlang probability, multiple commodities, network probe, SIP diagnosis or PBX throughput.',
                       'Reverse residual capacity cancels previous net flow; it is not a new physical channel.',
                       'Min-cut edges form a model bottleneck, not an observed broken component or a repair recommendation.']}


if __name__ == '__main__':
    if not AUTHOR_MAIN_ENABLED:
        raise SystemExit('Await ROOT sole author main authorization')
    sys.stdout.reconfigure(encoding='ascii', newline='\n')
    print(json.dumps(run_example(), ensure_ascii=True, indent=2, allow_nan=False))

مرجعِ آزمون، مسیرِ افزایش را دوباره نمی‌سازد. همهٔ زیرمجموعه‌های مجازِ سمتِ مبدأ را می‌شمارد، هزینهٔ خروجیِ اصلی را حساب می‌کند و اشتراکِ بخش‌های با هزینهٔ کمینه را می‌گیرد. خانوادهٔ محدودِ چهاررأسی شش جایگاهِ یال با سه ظرفیتِ ممکن دارد: ۷۲۹ شبکه و چهار برش برای هرکدام. این مجموعه یک گروهِ آزمون است. گروه‌های دیگر، نمونهٔ دستی، جهتِ برش، اصلاحِ باقیمانده، تساویِ برش‌ها، ورودیِ نامعتبر، ترتیب، مقیاس و تغییرناپذیری را جدا بررسی می‌کنند.

{
  "runtime": {
    "python": "3.14.5",
    "implementation": "CPython",
    "dependencies": "Python standard library only"
  },
  "scope": "Supplied finite directed integer-capacity abstraction; no real calls or physical capacity measurement",
  "API": "capacity_cut_report(vertex_count, edges, source, sink)",
  "own_bounds": {
    "vertices": [
      2,
      6
    ],
    "capacity": [
      0,
      4
    ],
    "maximum_augmentation_successes": 20
  },
  "manual_shared_bottleneck": {
    "edges": [
      [
        0,
        1,
        4
      ],
      [
        0,
        2,
        4
      ],
      [
        1,
        3,
        3
      ],
      [
        2,
        3,
        2
      ],
      [
        3,
        4,
        2
      ]
    ],
    "entry_capacity": 8,
    "result": {
      "value": 2,
      "source_side": [
        0,
        1,
        2,
        3
      ],
      "sink_side": [
        4
      ],
      "cut_edges": [
        [
          3,
          4,
          2
        ]
      ]
    }
  },
  "manual_reverse_residual_case": {
    "edges": [
      [
        0,
        1,
        1
      ],
      [
        0,
        2,
        1
      ],
      [
        1,
        3,
        1
      ],
      [
        1,
        4,
        1
      ],
      [
        2,
        3,
        1
      ],
      [
        3,
        5,
        1
      ],
      [
        4,
        5,
        1
      ]
    ],
    "result": {
      "value": 2,
      "source_side": [
        0
      ],
      "sink_side": [
        1,
        2,
        3,
        4,
        5
      ],
      "cut_edges": [
        [
          0,
          1,
          1
        ],
        [
          0,
          2,
          1
        ]
      ]
    },
    "forward_only_remainder_value_after_first_hand_path": 0
  },
  "manual_directed_cut": {
    "value": 1,
    "source_side": [
      0,
      1
    ],
    "sink_side": [
      2
    ],
    "cut_edges": [
      [
        1,
        2,
        1
      ]
    ]
  },
  "multiple_equal_cuts_example": {
    "value": 1,
    "source_side": [
      0
    ],
    "sink_side": [
      1,
      2
    ],
    "cut_edges": [
      [
        0,
        1,
        1
      ]
    ]
  },
  "disconnected_example": {
    "value": 0,
    "source_side": [
      0,
      1
    ],
    "sink_side": [
      2,
      3
    ],
    "cut_edges": []
  },
  "antiparallel_cycle_example": {
    "value": 3,
    "source_side": [
      0
    ],
    "sink_side": [
      1,
      2,
      3
    ],
    "cut_edges": [
      [
        0,
        1,
        3
      ]
    ]
  },
  "maximum_six_vertex_example": {
    "value": 20,
    "source_side": [
      0
    ],
    "sink_side": [
      1,
      2,
      3,
      4,
      5
    ],
    "cut_edges": [
      [
        0,
        1,
        4
      ],
      [
        0,
        2,
        4
      ],
      [
        0,
        3,
        4
      ],
      [
        0,
        4,
        4
      ],
      [
        0,
        5,
        4
      ]
    ]
  },
  "independent_expected_path": "Enumerate source-sink partitions, minimize original outgoing capacity, intersect all minimizing source sides; no residual graph or traversal",
  "finite_network_profiles_ONE_group": 729,
  "enumerated_cuts_in_same_group": 2916,
  "edge_order_permutations_in_ONE_group": 120,
  "vertex_renamings_in_same_group": 24,
  "strict_invalid_profiles_in_ONE_group": 39,
  "late_guarded_invalid_profiles": 3,
  "invalid_matrix_allocations": 0,
  "lazy_or_conversion_hook_calls": 0,
  "checks": {
    "shared_downstream_cut_two_despite_entry_capacity_eight": true,
    "reverse_residual_recovers_route_lost_by_forward_only_commitment": true,
    "cut_counts_original_outgoing_capacity_not_incoming_or_residual": true,
    "equal_cut_values_choose_intersection_not_arbitrary_source_partition": true,
    "disconnection_empty_and_zero_edges_are_valid_zero_flow": true,
    "cycles_antiparallel_edges_and_edges_into_source_are_admitted": true,
    "independent_all_cut_reference_729_networks_in_ONE_family": true,
    "input_edge_order_and_vertex_renaming_preserve_declared_result": true,
    "one_edge_capacity_monotonicity_and_uniform_integer_scaling": true,
    "adding_zero_capacity_edges_does_not_create_a_path_or_change_report": true,
    "raising_an_entrance_capacity_can_leave_shared_cut_unchanged": true,
    "strict_exact_types_bounds_duplicate_pairs_selfloops_and_terminals": true,
    "whole_late_admission_precedes_matrix_allocation_and_lazy_hooks": true,
    "maximum_caps_fresh_nested_immutable_report_and_strict_JSON": true
  },
  "groups_total": 14,
  "limits": [
    "Own small API and source-side tie policy, not NetworkX or Boost API equivalence.",
    "Integer aggregate interchangeable route units; no named unsplittable-call or codec eligibility constraints.",
    "No arrival/service times, queue, Erlang probability, multiple commodities, network probe, SIP diagnosis or PBX throughput.",
    "Reverse residual capacity cancels previous net flow; it is not a new physical channel.",
    "Min-cut edges form a model bottleneck, not an observed broken component or a repair recommendation."
  ]
}

منبعِ نخست، تمامِ بخشِ API مربوط به minimum_cut در مستنداتِ NetworkX 3.7 است؛ تعریفِ برش و برابریِ جریان و برش را از آن می‌گیریم، نه حل‌گرِ پیش‌فرضش را. منبعِ دوم، تمامِ صفحهٔ Edmonds–Karp در نسخهٔ ثابتِ Boost 1.88.0 است. این نسخه قدیمی‌تر از نسخهٔ جاریِ اعلام‌شدهٔ صفحه است. تاریخِ انتشارِ اولیهٔ این صفحات معلوم نیست؛ تاریخِ دسترسیِ منابع ۲۲ اکتبرِ ۲۰۲۶ است و نباید با تاریخِ انتشار یا نسخهٔ محیطِ اجرا یکی شود.

۵. چهار پرسش دربارهٔ ظرفیت و مرزِ مدل

پرسشِ اول: چرا افزایشِ یکی از ورودی‌های چهارواحدی، الزاماً نتیجه را بیشتر نمی‌کند؟ پاسخ: تا وقتی یالِ مشترکِ سه به چهار ظرفیتِ دو دارد، همان برش سقفِ دو را نگه می‌دارد. برای اثباتِ افزایشِ مقدار، باید نشان دهیم همهٔ برش‌های محدودکننده ظرفیتِ بیشتری پیدا کرده‌اند؛ دیدنِ یک ورودیِ بزرگ‌تر کافی نیست.

پرسشِ دوم: آیا یالِ برگشت یعنی تماس در جهتِ عکس برقرار می‌شود؟ پاسخ: خیر. در محاسبهٔ باقیمانده، برگشت ابزارِ لغوِ تخصیص است. اگر واقعاً ظرفیتِ جهتِ عکس را بخواهیم، باید آن را جدا در ورودی بدهیم. جمع‌زدنِ این دو معنا و گزارش‌کردنِ آن به عنوانِ ظرفیتِ فیزیکی، تفسیرِ نادرستی از متغیرِ الگوریتم است.

پرسشِ سوم: اگر دو برش مقدارِ برابر دارند، آیا خروجی ناپایدار می‌شود؟ پاسخ: مقدار یکتا است و قراردادِ بخشِ نخست نیز ابهام را رفع می‌کند. در زنجیرهٔ سه‌رأسیِ مثال، اشتراکِ دو بخشِ کمینه فقط مبدأ است. مرتب‌کردنِ رأس‌ها و یال‌های خروجی باعث می‌شود جابه‌جاییِ ترتیبِ ورودی، گزارش را عوض نکند؛ این به معنای یکتابودنِ خودِ تخصیصِ جریان نیست.

پرسشِ چهارم: آیا یافتنِ برش، خرابیِ مرکز تلفن را تشخیص می‌دهد؟ پاسخ: خیر. یالِ کم‌ظرفیت می‌تواند یک فرضِ طراحیِ عمدی باشد و هیچ مشاهده‌ای از دستگاه نداریم. برای نتیجه‌گیری دربارهٔ سامانهٔ واقعی، اعتبارِ مدل، اندازه‌گیریِ ظرفیت، سازگاریِ مسیرها، بارِ زمانی و محدودیت‌های پردازشی جدا بررسی می‌شوند. این برنامه فقط یک گواهِ ریاضی برای دادهٔ کوچکِ عرضه‌شده می‌دهد؛ نه دستورِ تعمیر و نه پیش‌بینیِ کیفیتِ تماس.

منابع و مطالعهٔ بیشتر

• NetworkX 3.7؛ تعریفِ برشِ جهت‌دار و برابریِ جریان و برش
• Boost 1.88.0؛ مسیرِ افزایشی، باقیمانده و روشِ Edmonds–Karp

بررسی منابع: ۳۰ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.