I am trying to find the max flow of a flow network and the final pattern of the network. But the program is giving me 1 answer and when i try and do it on paper i get a different answer, not sure if one is right or both is wrong. Here the network; Am getting 5 on the program and 6 on paper :/
0,2,4,1,6,0,0
2,0,0,0,5,0,0
4,0,0,0,0,5,0
1,0,0,0,1,1,0
6,5,0,1,0,5,5
0,0,5,1,5,0,0
0,0,0,0,5,0,0
Here my code for the program
"""""
Using the Ford-Fulkerson Algorithm to find the max flow of a network.
This program will read a file called network.txt and determine the max flow from S to T.
"""""
class FordFulkersonEdge(object):
"""
This creates the edges in the paths.
"""
def __init__(self, source, sink, capacity):
"""
Parameters:
Source - Start of the node for the flow
Sink - End of the node for the flow
Capacity - Available capacity on all edges in the path.
"""
self.source = source
self.sink = sink
self.capacity = capacity
def __repr__(self):
"""
This returns the string of self.source, self.sink, and self.capacity.
"""
return "%s->%s:%s" % (self.source, self.sink, self.capacity)
class FordFulkersonFlowNetwork(object):
"""
This creates the flow network.
"""
def __init__(self):
"""
This initalises the adjacey list which contains as the key a vertex
and then as the value a list of edges are connected to the vertex.
it initlises the flow value lookup for each edge.
"""
self.adj = {}
self.flow = {}
def AddVertex(self, vertex):
"""
This adds a vertex to the adjacency list.
"""
self.adj[vertex] = []
def GetEdges(self, sink):
"""
This returns the list of edges connected given vertex.
"""
return self.adj[sink]
def AddEdge(self, source, sink, capacity = 0):
"""
This adds an edge from the given source to the given sink node to the network.
if no capacity is given, it is set to 0.
Adding an extra residual edge for the residual capacity.
"""
if source == sink:
raise ValueError("source == sink")
edge = FordFulkersonEdge(source, sink, capacity)
redge = FordFulkersonEdge(sink, source, 0)
edge.redge = redge
redge.redge = edge
self.adj[source].append(edge)
self.adj[sink].append(redge)
self.flow[edge] = 0
self.flow[redge] = 0
def FindPath(self, source, sink, path):
"""
This tries to find a path from the given source to the given sink node,
by repeating itself until reaching the sink node.
"""
if source == sink:
return path
for edge in self.GetEdges(source):
residual = edge.capacity - self.flow[edge]
if residual > 0 and not (edge, residual) in path:
result = self.FindPath(edge.sink, sink, path + [(edge, residual)])
if result != None:
return result
def MaxFlow(self, source, sink):
"""
This iterates over all the paths from the source to the sink node adding flow to the
edges along the path equivalent to the flow passable through the bottle neck.
Returns the sum of the flow leaving the source node, which is the same as the amount
of the flow arrving at the sink node.
"""
path = self.FindPath(source, sink, [])
while path != None:
flow = min(res for edge, res in path)
for edge, res in path:
self.flow[edge] += flow
self.flow[edge.redge] -= flow
path = self.FindPath(source, sink, [])
return sum(self.flow[edge] for edge in self.GetEdges(source))
"""
This opens the network.txt file and reads each line.
It split the content by commas and removes all space and commas from network.txt
Assigns the FordFulkersonFlowNetwork to fn.
"""
print "Calculating Max Flow total from S to T..."
myFile = open("network.txt", "r")
content = myFile.readlines()
n = len(content[0].strip().split(","))
fn = FordFulkersonFlowNetwork()
"""
This assigns the nodes S, A, B, C, D, E and T to the correct column
It creats an array called vertices and append to this array.
map() function executes the fn.AddVertex Method on each of the elements of the vertices list.
"""
vertices = ["S"]
for i in range (n - 2):
vertices.append(chr(ord('A') + i))
vertices.append("T")
map(fn.AddVertex, vertices)
"""
Reads the values in the table and from the combination of column and row,
addding the related edge to the network.
"""
for lineCount, line in enumerate(content):
for colCount, value in enumerate(line.strip().split(",")):
if lineCount < colCount:
fn.AddEdge(vertices[lineCount], vertices[colCount], int(value))
"""
This creats the 10025928mf.txt file and records the Max Flow information in the text file.
"""
maxFlow = open("mf.txt", "w")
maxFlow.write("Max Flow: {0}".format(fn.MaxFlow("S","T")) + "\n")
"""
The first line of the vertex name
"""
maxFlow.write(" ")
for vertex in vertices:
maxFlow.write(vertex + " ")
maxFlow.write("\n")
"""
The Matrix
"""
for sourceNo, source in enumerate(vertices):
adjuster = 0
maxFlow.write(source + " ")
for sinkNo in range(len(vertices)):
if sinkNo is sourceNo:
maxFlow.write(str(0) + " ")
adjuster = -1
else:
maxFlow.write(str(fn.flow[fn.adj[source][sinkNo + adjuster]]) + " ")
maxFlow.write("\n")
"""
Closes the network2.txt and 10025928mfownexample.txt text files.
"""
myFile.close()
maxFlow.close()
"""
This prints out the max flow total for the user to see and tells you the number of file that it been saved in.
"""
print ("\nMax Flow: {0}".format(fn.MaxFlow("S","T")))
print "Max Flow pattern and Max Flow total saved in mf.txt"