networking_flow.ford_fulkerson

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

graph

Functions

breadth_first_search(→ bool)

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

ford_fulkerson(→ int)

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

Module Contents

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
networking_flow.ford_fulkerson.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
networking_flow.ford_fulkerson.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,...