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

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

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)

6/16/2020 LAB Assignment 9 – The Maximum Flow Problem

https://foothillcollege.instructure.com/courses/12889/assignments/324303 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.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)

6/16/2020 LAB Assignment 9 – The Maximum Flow Problem

https://foothillcollege.instructure.com/courses/12889/assignments/324303 3/4

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.

It returns true if end was successfully reached and false, otherwise.

6/16/2020 LAB Assignment 9 – The Maximum Flow Problem

https://foothillcollege.instructure.com/courses/12889/assignments/324303 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.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

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

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

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。