TD03 - Flow

Implementation in Python 3 of the Ford-Fulkerson algorithm seen during the course and during the TD 3. A set of functions are defined and loaded during the execution of the first cell. They help to load graphs to test and to verify the produced solutions, etc.

Each function you need to complete is followed by tests to verify that the data produced when the function was called is correct.

Each edge of the graph is oriented and labeled with its capacity and its current flow. Graphs are implemented using dictionaries and you can use the following Python functions:

• nodes (graph): returns the list of vertices of graph.
• successors (graph, x): returns the list of neighboring vertices that are successors of x in the graph.
• predecessors (graph, x): returns the list of neighboring vertices that are predecessors of x in the graph.
• capacity (graph, x, y): returns the capacity of the edge going from vertex x to vertex y of the graph, or None if there is no such edge.
• flow (graph, x, y): returns the current flow of the edge going from vertex x to vertex y of the graph, or None if there is no such edge.
• set_flow (graph, x, y, f): sets to f the current flow of the edge going from vertex x to vertex y, it raises an error if there is no such edge.

Exercise plan :

• Ford-Fulkerson algorithm

Optional:

• Edmonds-Karp algorithm

The next cell allows the loading of the graph flow and displays it using the Python module NetworkX. If there are two arcs (in both directions) connecting two vertices, they are represented with a double arrow holding informations of the two corresponding flows.

# TO RUN
import zlib, base64
exec(zlib.decompress(base64.b64decode(b'eJy9V81u40YMPtdPQagHSYhWteNs4rjwoUAXRi976NUwhIk0igeRRoI0sq0GeaDd18iLlfOjPytKFgW6AuLYwyH5kfzIGbE0zwoBnIpTVjydgZTAzzOmV1Mi8iQTCXvw81p+k+I8EY2cV2leK5W8p3KYzSIaQ0FJFMRJdnJillBOUuquZ4CPZVnq/9+4AcSBgtwEjIN4jCHOCjThg9Uo+bhqDfROTBwgyynvDEsMsbYuH2VwA88v7UopiKC4ZH3NImp1G7MCEuk6hk5bPiwG61dLSpKhYGDsS/TYMyYfmqCmkTfexgY4Kid+UYqC5Y47Ekv4O74fRqCtlxTG5s4e1B5E6Dv1IBzY9ss8YcKxwJpwc97vauXJju313AM7tNcoIALACV3tvqCiKrjaP9O1jRjaJbUub1oHjwXJDx5wDDcIsyQrNs8vHlBMT/vzovh/xDELsfYVB6VMgXKoBEtYSbiAhACyrqWlP9BVHwl5KCVutgab23CFWS8c5vpVntPCcVVpmSxgA+9l9otS5AoRqu72M1PqDres2vNLl+J2s13Ys6YEb4h3nQn/kQqHeVLjDRT7Rlf936IqP/t/sq2UGSpsfRJFgTRYBnGRpW2C/Sdal47rGiAmAbpG0tG572g9IHndF2HRhyTSHmW5HMkl94J06GiHgtqVRHHs5/naX8Yvtq971emZRS7tkEh7tyGgPbe77z4m5Ars37BaIzL2nw89hO94cGc6PS33grJOVZ7arMuEVN5RpqTbZpLbJWZoYeccvUoloFvfOWjF3V/4QwZG2P/OUN8UreVLb7/ki7LkgfWQkPDJ0rxRaxLk1pe7Edy+o3+elZo7ISvCKiFFgP2YVcLZunoDiqKCnJytJ1sFabuRdfSGiY8zLoKS/UM3i4VpX/Xrbj6/2In+Nvh3sdpreN0Kg6anZunEInHYLPzPbo/6Bl/QtLiiX6ChImjpq7eyUSz01I9AYpn7S51SPI788oBjyNWjSfWNo+hiimnGF04W4Qz7SGuUVRjSsswKo+adu1kF5qTix4xRSGgJ+KVkvGy0aFWUg+GkxonQvXjRiAVhOL+/nEOaC5Zxx1ZdD1GGZqVOiNUgqCZDABxrV3KknU2/j6LAZmgCkTnVseQFjeh/iKbVa+P5K80TmlJEJLEiJv4J8eHRxoWa1YKmeYnHPSshxOLA67cjQwkiDw+EP9JCznAMoAoRN4XfP7k/JU0ykLIb7u3su/CB7jvXOFPWMCC2suITPEp45NSuoawpgXZhEh6SnIRM1CbZ6iyeTDhptr9+g8iuOAVSvH4X9P3MAMYgV7o4BgPcoPqacdpHeTkw9eiQkNWh/SNw1c1M/FykeHiYrqQiuETqQXwJNs0iFv8vYH+QhUQfIiBPaslGcxM5q6NOZL2l2lD0Ml5ka4xsksHOF+oqlttr/FyqT7yWgbmXwa0/x2uVfTMSLD6jRIq0zmK8YalVr0eSlRbkI0FjUhsrR/K7KYtGMIZ/PQV/aVxpJ2P59QcWxxgWJlXjTDRhXU+EtZhPobwzmjcTOV5NgrmZwn87lfx76esFWZET3QaKFye1T7yBeW6wnd/dgT9OI9Hcv12s5svl/Wp1d3O/ur+579WimrZ0nhYd30F4nLI7hW9hFKsPg1cylTU5QPAlpnn/dM14b2ZBRGmODYzvrnJcmBeQdq6Mnu7WFQdKC2vB13ihlKcLV6+P3SVc/x7evlO1hq90w2u3tobLu1QOgYiFwon1z8GZb7zKQ/5fMgNTlQ==')))

my_graph = load_flow(flow01)
display_flow(my_graph)

Ford-Fulkerson algorithm

Next cell, we provide the code of function find_path_DFS(graph, s, p) that takes a source vertex s and a target/sink p and returns a path from s to p. It implements a Depth-First Traversal using a stack where it saves the node to visit together with the path from s to that node. It returns the path linking s to p when p is reached, None if no such path exists.

def find_path_DFS(graph, s, p):

    # DFS => stack
    # we use a stack, an entry is a pair: (a node to visit, the path to that node)
    stack = [(s, [s])]
    visited = []

    # DFS loop 
    while len(stack) > 0 :
        # LIFO
        c, path = stack.pop()

        # if we reach the sink, no need to continue the DFS
        if c == p:
            return path   

        if c not in visited:
            visited.append(c)
            # loop over successors
            for y in successors(graph, c):
                stack.append((y, path + [y]))

    return None

find_path_DFS(my_graph, 's', 'p') # >>> ['s', '1', '4', 'p']

Inspire from the previous code to complete the following function find_augmenting_path_DFS(graph, s, p) which finds an augmenting path from s to p. It returns a pair: the path and the corresponding flow (to augment).

Verify the path and flow results when calling the function on the above graph.

def find_augmenting_path_DFS(graph, s, p):

    # DFS => stack
    # we use a stack with a 3-tuple (node to visit, path from s, available flow from s)
    stack = [(s, [s], math.inf)]
    visited = []

    # DFS loop 
    while len(stack) > 0 :
        # LIFO
        c, path, current_flow = stack.pop()

        # if we reach the sink, we return the augmenting path together with the augmenting flow
        if c == p:
            return path, current_flow   

        ############### TODO : complete code #####################


    return None, 0

# a small test, a more exhaustive test is comming next cell
print(find_augmenting_path_DFS(my_graph, 's', 'p'))

Complete the following function ford_fulkerson(find_augmenting_path, graph, s, p) that implements the Ford-Fulkerson algorithm. It takes as parameters an augmenting path search function, a graph, a source and a sink and computes the maximum flow. It also prints the augmenting path and flow at each step.

Test your code on the above example using a DFS strategy.

def ford_fulkerson(find_augmenting_path, graph, s, p):
    # we compute the current flow at the source node 
    # It is the outgoing flow from the source minus the incoming flow to the source
    current_flow = sum([flow(graph, s, y) for y in successors(graph, s)]
                      +[-flow(graph, y, s) for y in predecessors(graph, s)])

    # first call to find an augmenting path
    augmenting_path, augmenting_flow = find_augmenting_path(graph, s, p)

    while augmenting_flow != 0:
        print(augmenting_path, augmenting_flow)
        ############### TODO : complete code #####################



    return current_flow

assert ford_fulkerson(find_augmenting_path_DFS, my_graph, 's', 'p') == 14
display_flow(my_graph)

The next cell will test whether you consider ingoing edges... we initialize the same example with an existing flow from the sink to the source. The maximum flow remains unchanged.

my_graph_ = load_flow(flow01)
set_flow(my_graph_, 'p', '4', 10)
set_flow(my_graph_, '4', '2', 10)
set_flow(my_graph_, '2', 's', 10)
assert ford_fulkerson(find_augmenting_path_DFS, my_graph_, 's', 'p') == 14 # (unchanged)
display_flow(my_graph_)

[Optional]

On the pages of Princeton University, you will find an example of a pathological graph for which the Ford-Fulkerson algorithm may fail: here

Is it the case?

my_graph_pat = load_flow(pat_flow)
print(ford_fulkerson(find_augmenting_path_DFS, my_graph_pat, 's', 't'))
display_flow(my_graph_pat) # >>> 201 (no)

Edmonds-Karp algorithm

The Edmonds-Karp algorithm is identical to the Ford–Fulkerson algorithm, except that the search of the augmenting path is defined. The path found must be a shortest path that has available capacity. This can be found by a Breadth-First Search.

Modify the function find_augmenting_path_DFS(graph, s, p) to obtain a find_augmenting_path_BFS(graph, s, p) and replay tests.