import sets

# Computes maximal flow in a graph
# Adam Langley <agl@imperialviolet.org> http://www.imperialviolet.org
# Creative Commons http://creativecommons.org/licenses/by-sa/2.0/

class Network(object):
	"""This class can be used to calculate the maximal flow between two points in a network/graph. A network consists of nodes and arcs (egdes) that link them. Each arc has a capacity (the maximum flow down that arc).

The iterative algorithm is described at http://carbon.cudenver.edu/~hgreenbe/glossary/notes/maxflow-FF.pdf"""
	__slots__ = ['arcs', 'backarcs', 'nodes', 'labels']

	def __init__ (self, arcs):
		"""arcs: {node : {dest : {'cap': capacity, 'flow' : 0}}}

Nodes can be any compariable type (e.g. numbers, strings etc)"""
		
		self.nodes = {}
		self.labels = {}

		self.arcs = arcs
		self.backarcs = {}

		for source in arcs:
			if not source in self.backarcs:
				self.backarcs[source] = {}
			for dest in arcs[source]:
				if not dest in self.backarcs:
					self.backarcs[dest] = {}
				self.backarcs[dest][source] = {'cap' : arcs[source][dest]['cap'], 'flow' : 0}

	def min (a, b):
		"""private function"""
		if (a == -1):
			return b
		if (b == -1):
			return a
		return min (a, b)
	min = staticmethod (min)
	
	def maxflow (self, source, sink):
		"""Return the maximum flow from the source node number, to the sink"""

		while 1:
			labels = {}
			labels[source] = ((0, 0), -1)
		
			unscanned = sets.Set ([source])
			scanned = sets.Set ()

			while 1:
				# Select any node, x, that is labeled and unscanned
				for node in unscanned:
					##print "Unscanned: " + str(node)
					# To all unlabeled succ nodes
					for outnode in self.arcs[node]:
						if (outnode in unscanned or outnode in scanned):
							continue
						arc = self.arcs[node][outnode]
						if (arc['flow'] >= arc['cap']):
							continue
						labels[outnode] = ((node, 1), Network.min (labels[node][1], arc['cap'] - arc['flow']))
						unscanned.add (outnode)
					# To all predecessor nodes
					for innode in self.backarcs[node]:
						if (innode in unscanned or innode in scanned):
							continue
						arc = self.arcs[innode][node]
						if (arc['flow'] == 0):
							continue
						labels[innode] = ((node, -1), Network.min (labels[node][1], arc['flow']))
						unscanned.add (innode)
					unscanned.remove (node)
					scanned.add (node)
	
					##print labels
					break;
				else:
					# no labels could be assigned
					# total the incomming flows to the sink
					sum = 0
					for innode in self.backarcs[sink]:
						sum += self.arcs[innode][sink]['flow']
					return sum
	
				if (sink in unscanned):
					# sink is labeled and unscanned
					break;

			# Routine B
			s = sink
			((node, sense), et) = labels[s]
			##print "et: " + str (et)
			while 1:
				if (s == source):
					break
				((node, sense), epi) = labels[s]
				# If the first part of the label is y+
				if (sense == 1):
					##print "  add " + str(node) + " " + str(s)
					self.arcs[node][s]['flow'] += et
				else:
					##print "  rm " + str(s) + " " + str(node)
					self.arcs[s][node]['flow'] -= et
				s = node
			##print self.arcs

if (__name__ == "__main__"):
	n = Network ({'s' : {'x' : {'cap' : 1, 'flow' : 1}, 'y' : {'cap' : 3, 'flow' : 0}}, 'x' : {'y' : {'cap' : 1, 'flow' : 1}, 't' : {'cap' : 3, 'flow' : 0}}, 'y' : {'x' : {'cap' : 1, 'flow' : 0}, 't' : {'cap' : 1, 'flow' : 1}}})

	print n.maxflow ('s', 't')