networking_flow.push_relabel
============================

.. py:module:: networking_flow.push_relabel

.. autoapi-nested-parse::

   Push-relabel (Goldberg-Tarjan) algorithm for the maximum-flow problem.

   The push-relabel method takes a very different approach from the augmenting-path
   algorithms in this directory (``ford_fulkerson.py`` builds up a valid flow one
   path at a time).  Instead it works with a *preflow*, in which a vertex may
   temporarily receive more flow than it sends out.  Each active vertex either
   *pushes* its excess towards a neighbour that is one level lower, or is *relabeled*
   to a higher level so that a push becomes possible.  When no vertex other than the
   source and sink has excess, the preflow has become a maximum flow.

   Using the highest-label selection rule (always discharge an active vertex whose
   label is largest) this implementation runs in O(V^2 * sqrt(E)) time, which beats
   the augmenting-path methods on dense graphs.

   Reference: https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm



Classes
-------

.. autoapisummary::

   networking_flow.push_relabel.PushRelabel


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

.. py:class:: PushRelabel(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 = PushRelabel(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

   It agrees with the classic four-vertex example:

   >>> h = PushRelabel(4)
   >>> for (u, v), cap in {(0, 1): 3, (0, 2): 2, (1, 2): 5,
   ...                     (1, 3): 2, (2, 3): 3}.items():
   ...     h.add_edge(u, v, cap)
   >>> h.max_flow(0, 3)
   5

   Parallel edges add up, and a disconnected sink gives zero flow:

   >>> p = PushRelabel(2)
   >>> p.add_edge(0, 1, 3)
   >>> p.add_edge(0, 1, 5)
   >>> p.max_flow(0, 1)
   8
   >>> PushRelabel(3).max_flow(0, 2)
   0


   .. py:method:: _apply_pushes(u: int, height: list[int], excess: list[int]) -> None

      Push as much excess as possible from ``u`` along admissible edges.



   .. py:method:: _discharge(u: int, height: list[int]) -> bool

      Return ``True`` if ``u`` has at least one admissible outgoing edge.



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

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

      >>> g = PushRelabel(2)
      >>> g.add_edge(0, 1, -1)
      Traceback (most recent call last):
          ...
      ValueError: capacity must be non-negative
      >>> g.add_edge(2, 0, 1)
      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``.

      >>> PushRelabel(2).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