With this code below I will get the result

Total flow through all doors after first run: 110 Total flow is 110. Remaining flow to send: 10

But the total flow I need to send is 120. So I want to send the remaining 10 but somehow it is not starting the second run. Which condition should I change to do so? I think the way the way finding the path is wrong or treating the residual graph is wrong. Ideally, I would like to send the last 10 through D01 -> D02 -> D04

Thank you,

def build_graph(nodes, edges):
    node_index = {node: i for i, node in enumerate(nodes)}
    n = len(nodes)
    graph = [[0] * n for _ in range(n)]
    for room_a, room_b, capacity in edges:
        graph[node_index[room_a]][node_index[room_b]] = capacity
    return graph, node_index


def bfs(residual_graph, source, sink, parent):
    visited = [False] * len(residual_graph)
    queue = [source]
    visited[source] = True
    while queue:
        u = queue.pop(0)
        for v in range(len(residual_graph)):
            if not visited[v] and residual_graph[u][v] > 0:
                queue.append(v)
                visited[v] = True
                parent[v] = u
                if v == sink:
                    return True
    return False


def edmonds_karp(graph, source, sink):
    residual_graph = [row[:] for row in graph]
    parent = [-1] * len(graph)
    max_flow = 0
    search_count = 0
    door_flows = [[0] * len(graph) for _ in range(len(graph))]
    while bfs(residual_graph, source, sink, parent):
        search_count += 1
        path_flow = float('Inf')
        s = sink
        while s != source:
            path_flow = min(path_flow, residual_graph[parent[s]][s])
            s = parent[s]
        max_flow += path_flow
        v = sink
        while v != source:
            u = parent[v]
            residual_graph[u][v] -= path_flow
            residual_graph[v][u] += path_flow
            door_flows[u][v] += path_flow
            v = parent[v]
    return max_flow, search_count, door_flows


def final_flow(graph, source, sink, target_flow, edges, node_index):
    max_flow, search_count, door_flows = edmonds_karp(graph, source, sink)
    print(f"Maximum evacuation flow (students per minute): {max_flow}")
    print(f"Number of searches (BFS executions): {search_count}")
    actual_total_flow = sum(door_flows[node_index[room_a]][node_index[room_b]] for room_a, room_b, _ in edges)
    print(f"\nTotal flow through all doors after first run: {actual_total_flow}")
    if actual_total_flow < target_flow:
        remaining_flow = target_flow - actual_total_flow
        print(f"Total flow is {actual_total_flow}. Remaining flow to send: {remaining_flow}")


# Input data directly in the code
nodes = ["M01", "M02", "M03", "M04", "M05", "EXIT"]
edges = [
    ("M01", "M02", 15),
    ("M02", "M03", 15),
    ("M01", "M03", 25),
    ("M03", "EXIT", 15),
    ("M03", "M04", 15),
    ("M03", "M05", 5),
    ("M01", "M04", 15),
    ("M04", "M05", 25),
    ("M05", "EXIT", 25),
]
source = "M01"
target_flow = 120

# Build the graph and run the algorithm
graph, node_index = build_graph(nodes, edges)
source_index = node_index[source]
sink_index = node_index["EXIT"]
final_flow(graph, source_index, sink_index, target_flow, edges, node_index)

With this code below I will get the result

Total flow through all doors after first run: 110 Total flow is 110. Remaining flow to send: 10

But the total flow I need to send is 120. So I want to send the remaining 10 but somehow it is not starting the second run. Which condition should I change to do so? I think the way the way finding the path is wrong or treating the residual graph is wrong. Ideally, I would like to send the last 10 through D01 -> D02 -> D04

Thank you,

def build_graph(nodes, edges):
    node_index = {node: i for i, node in enumerate(nodes)}
    n = len(nodes)
    graph = [[0] * n for _ in range(n)]
    for room_a, room_b, capacity in edges:
        graph[node_index[room_a]][node_index[room_b]] = capacity
    return graph, node_index


def bfs(residual_graph, source, sink, parent):
    visited = [False] * len(residual_graph)
    queue = [source]
    visited[source] = True
    while queue:
        u = queue.pop(0)
        for v in range(len(residual_graph)):
            if not visited[v] and residual_graph[u][v] > 0:
                queue.append(v)
                visited[v] = True
                parent[v] = u
                if v == sink:
                    return True
    return False


def edmonds_karp(graph, source, sink):
    residual_graph = [row[:] for row in graph]
    parent = [-1] * len(graph)
    max_flow = 0
    search_count = 0
    door_flows = [[0] * len(graph) for _ in range(len(graph))]
    while bfs(residual_graph, source, sink, parent):
        search_count += 1
        path_flow = float('Inf')
        s = sink
        while s != source:
            path_flow = min(path_flow, residual_graph[parent[s]][s])
            s = parent[s]
        max_flow += path_flow
        v = sink
        while v != source:
            u = parent[v]
            residual_graph[u][v] -= path_flow
            residual_graph[v][u] += path_flow
            door_flows[u][v] += path_flow
            v = parent[v]
    return max_flow, search_count, door_flows


def final_flow(graph, source, sink, target_flow, edges, node_index):
    max_flow, search_count, door_flows = edmonds_karp(graph, source, sink)
    print(f"Maximum evacuation flow (students per minute): {max_flow}")
    print(f"Number of searches (BFS executions): {search_count}")
    actual_total_flow = sum(door_flows[node_index[room_a]][node_index[room_b]] for room_a, room_b, _ in edges)
    print(f"\nTotal flow through all doors after first run: {actual_total_flow}")
    if actual_total_flow < target_flow:
        remaining_flow = target_flow - actual_total_flow
        print(f"Total flow is {actual_total_flow}. Remaining flow to send: {remaining_flow}")


# Input data directly in the code
nodes = ["M01", "M02", "M03", "M04", "M05", "EXIT"]
edges = [
    ("M01", "M02", 15),
    ("M02", "M03", 15),
    ("M01", "M03", 25),
    ("M03", "EXIT", 15),
    ("M03", "M04", 15),
    ("M03", "M05", 5),
    ("M01", "M04", 15),
    ("M04", "M05", 25),
    ("M05", "EXIT", 25),
]
source = "M01"
target_flow = 120

# Build the graph and run the algorithm
graph, node_index = build_graph(nodes, edges)
source_index = node_index[source]
sink_index = node_index["EXIT"]
final_flow(graph, source_index, sink_index, target_flow, edges, node_index)

• python
• algorithm

1 Answer 1

Ford-Fulkerson guarantees that at the end of the algorithm, there is no possible flow left, and that maximum possible flow is 110 (even if you make the wrong choice at first! It is a form of greedy algorithm that can't be wrong, because of the idea to add "indirect" arcs to the possibilities. So that even wrong decision, wrong choice for first flow, don't need to be, from the algorithm point of view canceled: you add a new flow, at each step (some effectively canceling the wrong ones).

If you obtained anything other than 0 for your "resent", the only thing it would have proven is that your implementation was incorrect.

So, the second time, it doesn't even start, because, the second time, their not a single chain from source to sink.

So, normally, target 120 is simply unreachable

(I say normally, because any way, I don't see how even 110 is possible in your graph. I mean, total capacity of edges to sink is 40. So, maximum flow should be at most 40 anyway. And you said that you would like to have the rest going through chain 1->2->4. But - even ignoring the fact that I don't get why using an algorithm if you want to choose the path yourself :D - in the graph in your code, there is no edge 2->4. Are you sure the graph in your code is the one you want to work with?)

EDIT: ok, from the code it is clearer what you call "total flow", and how come you claim to have it at 110: it is the total flow of all edges. But that is not what we call the total flow of a graph. Total flow is the total of all chains, not all edges. It is the amount of people that can run from E1 to Exit per minutes (If I understand correctly the application). Not the number of people running through any door per minute. One of the print of your code tells that this is what you were asked to compute. So be it. If your teacher ask you something, of course, that is what you need to do. But still, words have an objective meaning, and "total flow of a graph" doesn't mean "total of the flow of all edges". (Besides, practically, that total is meaningless: a graph is a modelisation of a network. You could always split an edge into two successive edges, and that would of course change only the model, not reality. That would not change the total flow (in Fulkerson meaning of the word). Yet it would change the total you compute, 110. Which proves enough that this total has no practical meaning: practical meaning should be independent of the models, once removed approximations of models)

Not criticizing the teacher for asking this question, if they did: I already asked the exact same thing to my students (it is some "easy points" question. Plus, sometimes, I even use it as a "checksum": I ask them for the code to compute that, but I tell them "result should be 110", so that it helps them to know when they have an error). But, well, when I do, I don't call it "total flow", since "total flow" has a precise meaning. Which is not that.

But well, I feel that I lack some other context element. You seem to expect to do "rerun" to an already saturated graph. Which makes no sense, unless there is a rule telling how that graph "desaturates". You seem to have a specific target, which is, as is, impossible to reach (again maximum is not even 110. It is 40).

So, clearly part of the "rules of the game" escape me. Maybe you are asked to simulate what happens after 1 minute of the best flow (students in M1 are now in M3 and M4 and your new problem is to have 25 person in M3 + 15 in M4 + still 80 in M1 to Exit, needing for that a new graph, with a virtual source connected to M1, M3, M4.... then 1minute later again... etc. And to compute how much times it takes to make all 120 person to evacuate, adding the capacity to "pipeline" people in time).

Just trying to imagine (I have no reason to believe that this is what you have to do. Just, putting myself in your teacher shoes, which, as you may understand, is not very hard to do, since I wear very similar shoes, and trying to imagine what kind of question I could ask to make people "rerun" and try to evacuate 120 persons through a graph with maximum capacity of 40, and with an answer more subtle than "120/40 = 3 minutes".

But whatever is what you have to do, it has to be more that what you told us. Because, otherwise, the only thing we can say is "40 persons per minute". Not 110, not 120.