Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
what can i do diffrently to slim down my python code?
!/usr/bin/python
import sys
import os
#the edge object holds information about an edge, that is, a vector joining two nodes on the network
class Edge(object):
def __init__(self, fromSource, toSink, capacity):
self.source = fromSource
self.sink = toSink
self.capacity = capacity
def __repr__(self):
return self.fromSource.name.strip() + " - " + self.toSink.name.strip()
class FlowNetwork(object):
def __init__(self):
self.adj = {}
self.flow = {}
# add a vertes to the known list of verteces
def add_vertex(self, vertex):
self.adj[vertex] = []
def get_edges(self, toSink):
return self.adj[toSink]
# add information about an edge to the known network topography
def add_edge(self, fromSource, toSink, capacity=0):
if fromSource == toSink:
raise ValueError("fromSource == toSink")
edge = Edge(fromSource,toSink,capacity)
redge = Edge(toSink,fromSource,0)
edge.redge = redge
redge.redge = edge
self.adj[fromSource].append(edge)
self.adj[toSink].append(redge)
self.flow[edge] = 0
self.flow[redge] = 0
# seraches for a path fromsource to sink
def find_path(self, source, sink, path):
if source == sink:
return path
for edge in self.get_edges(source):
residual = edge.capacity - self.flow[edge]
if residual > 0 and not (edge,residual) in path:
result = self.find_path( edge.sink, sink, path + [(edge,residual)] )
if result != None:
return result
# given a source and a sink within the knwon network topograhpy,
# uses the ford fulkerson algorithim to find the maximum flw between source and sink
def max_flow(self, source, sink):
print("finding path from %s to %s" % (source, sink))
path = self.find_path(source, sink, [])
while path != None:
print(path)
flow = min(res for edge,res in path)
for edge,res in path:
self.flow[edge] += flow
self.flow[edge.redge] -= flow
path = self.find_path(source, sink, [])
return sum(self.flow[edge] for edge in self.get_edges(source))
1 Answer
- Anonymous8 years agoFavorite Answer
Remove
def add_edge(self, u, v, w=0):
if u == v:
raise ValueError("u == v")
edge = Edge(u,v,w)
redge = Edge(v,u,0)
edge.redge = redge
redge.redge = edge
self.adj[u].append(edge)
self.adj[v].append(redge)
self.flow[edge] = 0
self.flow[redge] = 0 and change
class FlowNetwork(object):
def __init__(self): to return self.adj[v]