2023年11月25日

Python代写 | Assignment 9 – The Maximum Flow Problem

本次Python代写是实现最大流程图算法

Assignment 9 – The Maximum Flow Problem
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
classes.
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)
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.show_res_adj_table()
my_graph.show_flow_adj_table()
my_graph.start = “s”
my_graph.end = “t”
final_flow = my_graph.find_max_flow()
print(f”Final flow: {final_flow}”)
my_graph.show_res_adj_table()
my_graph.show_flow_adj_table()
if __name__ == “__main__”:
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)
Flow list for d: t(3)
Flow list for t: “””
Hints:
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().
Max_Flow_Graph
__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
my_graph.end.
We need to modify add_edge() – it will still add vertices as before, but adjacency lists are handled as
follows:
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.