Python代写 | Assignment 9 – The Maximum Flow Problem


Assignment 9 – The Maximum Flow Problem
A Flow Graph Algorithm
For this assignment we will implement a maximum flow graph algorithm as Max_Flow_Graph().
The class should implement the following public methods:
add_edge(), exactly as in our Graph class
find_max_flow() should start the algorithm and return the maximum flow supported by the graph
show_flow_adj_table() and show_res_adj_table() should display the flow graph and residual graph
using the same format we used for Graph.show_adj_table()
Also implement the following attributes as properties:
start – the “source” of the flow
end – the “sink” of the flow
Final Approach
You will have two weeks to complete this project, so you might want to spend a few days trying to come
up with your own design before using the hints below.
I recommend that you modify a copy of Graph() and Vertex(), rather than trying to inherit from these
A Sample Main to Test your Code
Run at least two flow problems. One should be the flow problem from the modules or text in order to
easily check the algorithm is correctly coded, and a second of your choice. Here is a sample source and
output for you to use as you near the final hours of debugging:
def main():
my_graph = Max_Flow_Graph()
my_graph.add_edge(“s”, “a”, 3)
my_graph.add_edge(“s”, “b”, 2)
my_graph.add_edge(“a”, “b”, 1)
my_graph.add_edge(“a”, “c”, 3)
6/16/2020 LAB Assignment 9 – The Maximum Flow Problem 2/4
my_graph.add_edge(“a”, “d”, 4)
my_graph.add_edge(“b”, “d”, 2)
my_graph.add_edge(“c”, “t”, 2)
my_graph.add_edge(“d”, “t”, 3)
my_graph.start = “s”
my_graph.end = “t”
final_flow = my_graph.find_max_flow()
print(f”Final flow: {final_flow}”)
if __name__ == “__main__”:
“”” ——— output ———–
Adj list for s: a(3) b(2)
Adj list for a: s(0) b(1) c(3) d(4)
Adj list for b: s(0) a(0) d(2)
Adj list for c: a(0) t(2)
Adj list for d: a(0) b(0) t(3)
Adj list for t: c(0) d(0)
Flow list for s: a(0) b(0)
Flow list for a: b(0) c(0) d(0)
Flow list for b: d(0)
Flow list for c: t(0)
Flow list for d: t(0)
Flow list for t:
Final flow: 5
Adj list for s: a(0) b(0)
Adj list for a: s(3) b(1) c(1) d(3)
Adj list for b: s(2) a(0) d(0)
Adj list for c: a(2) t(0)
Adj list for d: a(1) b(2) t(0)
Adj list for t: c(2) d(3)
Flow list for s: a(3) b(2)
Flow list for a: b(0) c(2) d(1)
Flow list for b: d(2)
Flow list for c: t(2)
6/16/2020 LAB Assignment 9 – The Maximum Flow Problem 3/4
Flow list for d: t(3)
Flow list for t: “””
The discussion in the modules has explanation and diagrams that will be useful — probably necessary —
to turn the following instructions into working code. Don’t try to use the steps below until you have read
and understood the graph/dijkstra and maximum flow material in Module 10
Morphing Vertex to Flow_Vertex is very easy. edge_pairs is converted to two dicts, flow_pairs and
res_pairs. We’ll need to update some other code in the class to accommodate this change. For
example, think about what to do with add_adj() and show_adj_list().
__init__() still contains the self._vertices dictionary. The only additional data is start and end, which
represent the start and end of the flow process, and should be references to two vertices in the graph.
Implement these as properties, so the client can get and set these with my_graph.start and
We need to modify add_edge() – it will still add vertices as before, but adjacency lists are handled as
res_pairs will receive two edges based on this one call: a forward edge, exactly as before and a
reverse edge with cost 0
flow_pairs is built as before but with all costs = 0
We need to implement find_max_flow() – the main public algorithm. It returns the maximum flow found.
The method loops, calling establish_next_flow_path() followed by get_limiting_flow_on_res_path() and
follows those calls by adjusting the residual and flow graphs using adjust_path_by_cost(). When
establish_next_flow_path() returns false (or adjust_path_by_cost() returns false or the limiting flow
becomes 0, take your pick), the loop ends. Finally, the flow graph is probed to find the total flow for the
functional return.
establish_next_flow_path() – this is based on the dijkstra() method. It is less demanding than dijkstra
because any path that connects _start to _end will do. The simplest way to convert dijkstra to this
method is:
Remove the functional parameter, since we will always start at the vertex start.
When traversing a newly popped v’s adjacency lists, skip edges with costVW == 0 since they
have been reduced to nothing (and are effectively no longer in the residual graph).
End the loop as soon as it finds a path to end. We don’t care about finding other flow paths
since, in this version, it will be looking for “shorter” paths, something that is not necessarily good
for us here.
It returns true if end was successfully reached and false, otherwise.
6/16/2020 LAB Assignment 9 – The Maximum Flow Problem 4/4
This method will create the same prev_in_path trail that dijkstra did. That path is used in the
subsequent methods to adjust vertex costs in each of the two graphs.
get_limiting_flow_on_res_path() – a helper for find_max_flow() which follows on the coattails of
establish_next_flow_path() and uses the data and path just created to find the limiting flow
(minimum) of the residual path just found. The method show_shortest_path() (which we don’t need
for this class) demonstrates how to trace the path from end to start, a maneuver that is useful here.
adjust_path_by_cost(cost) – a helper for find_max_flow() which takes the result of
get_limiting_flow_on_res_path() and uses it to modify the costs of edges in both the residual graph
and the flow graph. Again, chasing the path from end-to-start will be the dominant action here.
Because the path was based on an ad-hoc linked list using prev_in_path, from end-to-start, the two
vertices in each loop pass (say, current_vert and current_vert->prev_in_path) must be used to
access the correct cost on the correct adjacency list. That’s the job of the next two methods:
add_cost_to_res_edge(src, dst, cost) – a helper to adjust_path_by_cost(), this method examines
src’s residual adjacency list to find dst and then add cost to that edge (cost can be negative if
adjust_path_by_cost() wants to subtract rather than add).
add_cost_to_flow_edge(src, dst, cost) – a helper to adjust_path_by_cost(), this method examines
src’s flow adjacency list to find dst and then adds cost to that edge. If dst is not found in src’s list,
that implies that the edge passed in was actually a reverse edge, in which case the flow edge we
need to adjust is (dst, src). Further, this means we need to subtract the flow because residual flow in
the reverse direction is a signal that we are undoing some flow previously added.
That’s it! This is your final assignment for the course. It’s not easy, but you are well prepared for this
final challenge. Start early, stay in touch when you need clarification and assume you will hit a couple
roadblocks that require debugging and help.


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: [email protected]  微信:itcsdx