i get quite short code of algorithm in python, but i need to translate it to Java. I didnt find any program to do that, so i will really appreciate to help translating it.
I learned python a very little to know the idea how algorithm work.
The biggest problem is because in python all is object and some things are made really very confuzing like
sum(self.flow[(source, vertex)] for vertex, capacity in self.get_edges(source))
and "self.adj" is like hashmap with multiple values which i have no idea how to put all together. Is any better collection for this code in java?
code is:
class FlowNetwork(object):
def __init__(self):
self.adj, self.flow, = {},{}
def add_vertex(self, vertex):
self.adj[vertex] = []
def get_edges(self, v):
return self.adj[v]
def add_edge(self, u,v,w=0):
self.adj[u].append((v,w))
self.adj[v].append((u,0))
self.flow[(u,v)] = self.flow[(v,u)] = 0
def find_path(self, source, sink, path):
if source == sink:
return path
for vertex, capacity in self.get_edges(source):
residual = capacity - self.flow[(source,vertex)]
edge = (source,vertex,residual)
if residual > 0 and not edge in path:
result = self.find_path(vertex, sink, path + [edge])
开发者_JAVA技巧if result != None:
return result
def max_flow(self, source, sink):
path = self.find_path(source, sink, [])
while path != None:
flow = min(r for u,v,r in path)
for u,v,_ in path:
self.flow[(u,v)] += flow
self.flow[(v,u)] -= flow
path = self.find_path(source, sink, [])
return sum(self.flow[(source, vertex)] for vertex, capacity in self.get_edges(source))
g = FlowNetwork()
map(g.add_vertex, ['s','o','p','q','r','t'])
g.add_edge('s','o',3)
g.add_edge('s','p',3)
g.add_edge('o','p',2)
g.add_edge('o','q',3)
g.add_edge('p','r',2)
g.add_edge('r','t',3)
g.add_edge('q','r',4)
g.add_edge('q','t',2)
print g.max_flow('s','t')
result of this example is "5".
algorithm find max flow in graph(linked list or whatever) from source vertex "s" to destination "t".
Many thanks for any idea
Java doesn't have anything like Python's comprehension syntax. You'll have to replace it with code that loops over the list and aggregates the value of sum
as it goes.
Also, self.flow
looks like a dictionary indexed by pairs. The only way to match this, AFAIK, is to create a class with two fields that implements hashCode
and equals
to use as a key for a HashMap.
精彩评论