networking_flow.ford_fulkerson
==============================

.. py:module:: networking_flow.ford_fulkerson

.. autoapi-nested-parse::

   Ford-Fulkerson Algorithm for Maximum Flow Problem
   * https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

   Description:
       (1) Start with initial flow as 0
       (2) Choose the augmenting path from source to sink and add the path to flow



Attributes
----------

.. autoapisummary::

   networking_flow.ford_fulkerson.graph


Functions
---------

.. autoapisummary::

   networking_flow.ford_fulkerson.breadth_first_search
   networking_flow.ford_fulkerson.ford_fulkerson


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

.. py:function:: breadth_first_search(graph: list, source: int, sink: int, parents: list) -> bool

   This function returns True if there is a node that has not iterated.

   Args:
       graph: Adjacency matrix of graph
       source: Source
       sink: Sink
       parents: Parent list

   Returns:
       True if there is a node that has not iterated.

   >>> breadth_first_search(graph, 0, 5, [-1, -1, -1, -1, -1, -1])
   True
   >>> breadth_first_search(graph, 0, 6, [-1, -1, -1, -1, -1, -1])
   Traceback (most recent call last):
       ...
   IndexError: list index out of range


.. py:function:: ford_fulkerson(graph: list, source: int, sink: int) -> int

   This function returns the maximum flow from source to sink in the given graph.

   CAUTION: This function changes the given graph.

   Args:
       graph: Adjacency matrix of graph
       source: Source
       sink: Sink

   Returns:
       Maximum flow

   >>> test_graph = [
   ...     [0, 16, 13, 0, 0, 0],
   ...     [0, 0, 10, 12, 0, 0],
   ...     [0, 4, 0, 0, 14, 0],
   ...     [0, 0, 9, 0, 0, 20],
   ...     [0, 0, 0, 7, 0, 4],
   ...     [0, 0, 0, 0, 0, 0],
   ... ]
   >>> ford_fulkerson(test_graph, 0, 5)
   23


.. py:data:: graph
   :value: [[0, 16, 13, 0, 0, 0], [0, 0, 10, 12, 0, 0], [0, 4, 0, 0, 14, 0], [0, 0, 9, 0, 0, 20], [0, 0, 0,...