开发者

Python to Java translation

开发者 https://www.devze.com 2022-12-29 23:29 出处:网络
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 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.

0

精彩评论

暂无评论...
验证码 换一张
取 消