Simple tool that calculates the max flow in an undirected graph

maxflow.py

#!/usr/bin/python3

class Graph(object):
    def __init__(self, nodes):
        self.nodes = list(nodes)
        self.edges = dict((n, dict()) for n in nodes)

    def add_edge(self, a, b, w):
        if a in self.nodes:
            self.edges[a][b] = w
        else:
            self.nodes.append(a)
            self.edges[a] = {b: w}

    def update_edge(self, a, b, d):
        if a not in self.nodes:
            self.edges[a] = dict()
            self.nodes.append(a)
        if b in self.edges[a]:
            self.edges[a][b] += d
        else:
            self.edges[a][b] = d

    def graphviz(self):
        print('digraph G {')
        for i in self.edges:
            for j in self.edges[i]:
                print('"%s" -> "%s" [label="%d"];' % (i, j, self.edges[i][j]))
        print('}')

    def bfs(self, s, t):
        parent = dict()
        visited = set([s])
        queue = [s]
        while queue:
            a = queue.pop()
            for b in self.edges[a]:
                if b not in visited and self.edges[a][b] > 0:
                    queue.append(b)
                    visited.add(b)
                    parent[b] = a
        return (t in visited), parent

    def max_flow(self, s, t):
        residual = Graph(self.nodes)
        for a in self.nodes:
            for b in self.edges[a]:
                residual.add_edge(a, b, self.edges[a][b])
        flow = 0
        path, parent = residual.bfs(s, t)
        while path:
            path_flow = float("Inf")
            a = t
            while a != s:
                path_flow = min(path_flow, residual.edges[parent[a]][a])
                a = parent[a]
            flow += path_flow
            b = t
            while b != s:
                a = parent[b]
                residual.update_edge(a, b, -path_flow)
                residual.update_edge(b, a, path_flow)
                b = a
            path, parent = residual.bfs(s, t)
        return flow

tn = int(input())
for t in range(1, tn+1):
    n, m = [int(k) for k in input().split()]
    source, sink = str(1), str(n)
    g = Graph(range(1, n+1))
    for i in range(m):
        a, b, w = [k for k in input().split()]
        w = int(w)
        c = '%s+%s' % (a, b)
        g.update_edge(a, c, w)
        g.update_edge(c, b, w)
        g.update_edge(b, a, w)
    max_flow = g.max_flow(source, sink)
    if max_flow == 0:
        print('Case %d: impossible' % t)
    else:
        print('Case %d: %d' % (t, max_flow))