Python/networking_flow/ford_fulkerson.py at master · TheAlgorithms/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
"""
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
"""

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],
]


def 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 path from source to sink

    >>> breadth_first_search(graph, 0, 5, [-1, -1, -1, -1, -1, -1])
    True
    """
    num_nodes = len(graph)
    visited = [False] * num_nodes
    queue = []  # Using list instead of deque

    queue.append(source)
    visited[source] = True

    while queue:
        # Use pop(0) to simulate deque's popleft()
        current_node = queue.pop(0)

        # If we reached the sink, we can stop early
        if current_node == sink:
            return True

        # Check all adjacent nodes
        for neighbor, capacity in enumerate(graph[current_node]):
            if not visited[neighbor] and capacity > 0:
                visited[neighbor] = True
                parents[neighbor] = current_node
                queue.append(neighbor)

    return visited[sink]


def 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
    """
    # Create a copy of the graph to avoid modifying the original
    residual_graph = [row[:] for row in graph]
    num_nodes = len(residual_graph)
    parents = [-1] * num_nodes
    max_flow = 0

    # Augment the flow while there is a path from source to sink
    while breadth_first_search(residual_graph, source, sink, parents):
        # Find the minimum residual capacity along the path
        path_flow = float("inf")
        current_node = sink

        # Find the minimum capacity in the path
        while current_node != source:
            parent_node = parents[current_node]
            path_flow = min(path_flow, residual_graph[parent_node][current_node])
            current_node = parent_node

        # Add path flow to overall flow
        max_flow += path_flow

        # Update residual capacities of the edges and reverse edges
        current_node = sink
        while current_node != source:
            parent_node = parents[current_node]
            residual_graph[parent_node][current_node] -= path_flow
            residual_graph[current_node][parent_node] += path_flow
            current_node = parent_node

    return max_flow


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    print(f"{ford_fulkerson(graph, source=0, sink=5) = }")