networking_flow.dinic
=====================

.. py:module:: networking_flow.dinic

.. autoapi-nested-parse::

   Dinic's algorithm for the maximum-flow problem.

   Dinic's algorithm repeatedly builds a *level graph* with a breadth-first search
   (shortest augmenting paths, measured in edges) and then, in one pass, saturates
   a *blocking flow* on that level graph using depth-first search.  Grouping the
   augmenting paths by length this way gives a much better worst case than the
   plain Ford-Fulkerson / Edmonds-Karp augmenting-path method:

   * Dinic's algorithm:            O(V^2 * E)
   * on unit-capacity networks:    O(E * sqrt(V))

   Unlike the adjacency-matrix implementations in ``ford_fulkerson.py`` and
   ``minimum_cut.py`` in this directory, this version stores the graph as an
   adjacency list of residual edges, so it also handles graphs with parallel edges
   and is efficient on sparse graphs.

   Reference: https://en.wikipedia.org/wiki/Dinic%27s_algorithm



Classes
-------

.. autoapisummary::

   networking_flow.dinic.Dinic


Module Contents
---------------

.. py:class:: Dinic(vertices: int)

   Maximum flow in a directed graph with non-negative integer capacities.

   Add edges with :meth:`add_edge`, then call :meth:`max_flow`.

   >>> g = Dinic(6)
   >>> capacities = {
   ...     (0, 1): 16, (0, 2): 13, (1, 2): 10, (1, 3): 12,
   ...     (2, 1): 4, (2, 4): 14, (3, 2): 9, (3, 5): 20,
   ...     (4, 3): 7, (4, 5): 4,
   ... }
   >>> for (u, v), cap in capacities.items():
   ...     g.add_edge(u, v, cap)
   >>> g.max_flow(0, 5)
   23

   A source with no outgoing edges (or a sink with no incoming edges) has zero
   maximum flow:

   >>> Dinic(3).max_flow(0, 2)
   0

   Parallel edges between the same pair of vertices are supported and their
   capacities add up:

   >>> h = Dinic(2)
   >>> h.add_edge(0, 1, 3)
   >>> h.add_edge(0, 1, 5)
   >>> h.max_flow(0, 1)
   8


   .. py:method:: _build_level_graph(source: int) -> list[int]

      Breadth-first search; return per-vertex levels (-1 if unreachable).



   .. py:method:: _send_flow(vertex: int, pushed: int, sink: int, level: list[int], progress: list[int]) -> int

      Depth-first search that pushes a blocking flow along the level graph.



   .. py:method:: add_edge(source: int, destination: int, capacity: int) -> None

      Add a directed edge ``source -> destination`` with the given capacity.

      >>> g = Dinic(2)
      >>> g.add_edge(0, 1, 5)
      >>> g.add_edge(0, 1, -1)
      Traceback (most recent call last):
          ...
      ValueError: capacity must be non-negative
      >>> g.add_edge(0, 2, 5)
      Traceback (most recent call last):
          ...
      ValueError: vertex out of range



   .. py:method:: max_flow(source: int, sink: int) -> int

      Return the maximum flow from ``source`` to ``sink``.

      >>> g = Dinic(4)
      >>> for (u, v), cap in {(0, 1): 3, (0, 2): 2, (1, 2): 5,
      ...                     (1, 3): 2, (2, 3): 3}.items():
      ...     g.add_edge(u, v, cap)
      >>> g.max_flow(0, 3)
      5
      >>> g.max_flow(0, 0)
      Traceback (most recent call last):
          ...
      ValueError: source and sink must be different



   .. py:attribute:: edges
      :type:  list[list[int]]
      :value: []



   .. py:attribute:: graph
      :type:  list[list[int]]


   .. py:attribute:: size