"""
Max-flow Min-Cut
Often it is the case that a corporation, group, or individual would like to know how much "stuff" they can
send from point A to point B using some intermediate network. The intermediate network might be highways,
pipes, or mine shafts. The Max-flow min-cut theorem says the maximum flow that can be sent from point A
to point B via the intermediate network is equal to the capacity of the smallest cut.
A cut is defined as splitting the vertices of a graph into two sets S and T. An edge which crosses the cut
(connects a vertex in S to a vertex in T or vice versa) is called a cut edge. Furthermore, when talking
about flows in networks, we say that nodes which generate or produce flow are sources, and nodes which
consume or end flows are sinks. In the intro paragraph above, the source and sink would be point A and
point B respectfully.
We are interested in the "min-cut". In a flow network, all edges have a capacity. The min-cut is the cut
in which there is minimal capacity across cut edges. Futhermore, the cut edges we are considering for the
min-cut must be going out of S and into T, where S contains all sources, and T contains all sinks. Thus,
the min-cut is the cut in which when summing all cut edges from S to T, it is the minimum sum in the graph.
Given this definition, there could be multiple min-cuts in a network. The algorithm below just finds one
min-cut. Furthermore, in order to work with flows, a directed graph is needed. In order to learn more
and get concrete definitions of everything mentioned here, please see the following Wikipedia article:
http://en.wikipedia.org/wiki/Max_flow_min_cut_theorem
AUTHORS:
-- Scott Clifford (2008-05-21): initial version
-- Jerin Schneider (2008-05-21): initial version
"""
#*****************************************************************************
# Copyright (C) 2008 - 2009
# Scott J. Clifford and Jerin R. Schneider
#
#
# Distributed under the terms of the GNU General Public License (GPL)
# http://www.gnu.org/licenses/
#*****************************************************************************
def max_flow_min_cut(self, network_original, sourceList, sinkList, augmentingPathAlgorithm=0):
"""
This function computes and returns the maximum flow and min-cut across a given network.
INPUT:
network -- the given Graph for which we compute the max flow and min-cut of.
sourceList -- a List of vertices from which flow is generated.
sinkList -- a List of vertices which mark the endpoints of flow.
augmentingPathAlgorithm -- an integer which defines the search algorithm to use when finding augmenting paths.
OUTPUT:
tuple -- first entry is the max flow as an integer, and the second entry is the min-cut as a tuple containing two lists, each representing a group of vertices on their respective sides of the cut.
EXAMPLES: TODO
This example illustrates ...
sage: A = ModuliSpace()
sage: A.point(2,3)
xxx
We now ...
sage: B = A.point(5,6)
sage: xxx
It is an error to ...
sage: C = A.point('x',7)
Traceback (most recent call last):
...
TypeError: unable to convert x (=r) to an integer
NOTES:
Preconditions:
1) Source and sink lists must be non-empty.
2) All edges must have a capacity label.
3) All capacity labels must be integers greater than or equal to zero.
4) The source and sink lists must be disjoint sets.
5) The network given must be directed.
6) The augmented path algorithm provided is supported.
7) The vertices in the source and sink lists exist in the network provided.
If any of these preconditions are not met, an exception will be raised.
Supported Augmented Path Algorithms and their parameter integer form:
- Depth First Search: 0 # default
- Breadth First Search: 1 # not implemented yet
- Priority First Search: 2 # not implemented yet
AUTHORS:
- Scott Clifford (2008-05-16)
- Jerin Schneider (2008-05-16)
"""
## copy the network handed to us since we will be modifying it
network = network_original.copy()
## ensure the provided network is a directed graph
if not isinstance(network, DiGraph):
raise TypeError, "The provided network argument is not a directed graph."
## ensure given source list and sink list are of type 'list'
if not isinstance(sourceList, list):
raise TypeError, "The provided sourceList argument is not a list."
if not isinstance(sinkList, list):
raise TypeError, "The provided sinkList argument is not a list."
## ensure source list and sink list contains at least one entry
if len(sourceList) < 1:
raise ValueError, "The provided source list contains no entries."
if len(sinkList) < 1:
raise ValueError, "The provided sink list contains no entries."
## ensure the provided source list and sink list are dijoint sets
if set([]) != set(sourceList).intersection(set(sinkList)):
raise ValueError, "There must be no vertex which is defined as a source and sink."
## ensure the provide network has a positive integer capacity label for each edge in the network
# furthermore, if an edge is present between two nodes, we construct a back edge with zero residual
# capacity if a back edge is not already present
for e in network.edges():
if not (isinstance(e[2], Integer) and e[2] >= 0):
raise TypeError, "The following edge does not have a positive integer capacity: " + str(e)
if not network.has_edge(e[1], e[0]):
network.add_edge(e[1], e[0], 0)
## declare a list of the supported augmented path algorithms
supportedAugmentedPathAlgorithms = ['DFS']
## ensure the augmentingPathAlgorithm argument provided is supported
if not (0 <= augmentingPathAlgorithm < len(supportedAugmentedPathAlgorithms)):
raise ValueError, "The augmenting path algorithm provided is unsupported."
## ensure that the source and sink list vertices are actually present in the network given
for v in sourceList:
if not network.has_vertex(v):
raise ValueError, "The source list contains a vertex which is not present in the given network: " + str(v)
for v in sinkList:
if not network.has_vertex(v):
raise ValueError, "The sink list contains a vertex which is not present in the given network: " + str(v)
## declare and initialize variables
max_flow = 0 # the max flow value we return
min_cut_s = [] # the list containing the min-cut vertices on side S
min_cut_t = [] # the list containing the min-cut vertices on side T
source_vertex = 9999999 # the master source vertex
sink_vertex = 0 # the master sink vertex
## add the master source vertex to the network
# create a unique vertex name for the master source
for v in network.vertices():
if isinstance(v, Integer) and v >= source_vertex:
source_vertex = v + 1
# for each source the user supplied, we create a forward and back edge between our master source and
# the user source nodes. the forward edges have infinite capacity (denoted by -1), and the back edges
# have residual capacity zero to start.
for v in sourceList:
network.add_edge(source_vertex, v, -1)
network.add_edge(v, source_vertex, 0)
## add the master sink vertex to the network
sink_vertex = source_vertex + 1 # we computed a unique source vertex, so a unique sink would be source + 1
# for each sink the user supplied, add analogous edges as above for the sources, but this time for the sink(s)
for v in sinkList:
network.add_edge(v, sink_vertex, -1)
network.add_edge(sink_vertex, v, 0)
## ford-fulkerson algorithm
# find an augmented path in the network
path = max_flow_min_cut_find_augmented_path(network, source_vertex, sink_vertex, augmentingPathAlgorithm)
while len(path) != 0: # as long as we found an augmented path, proceed with the following
# determine the bottleneck capacity along the augmented path
# initialize min to be the residual capacity out of the user's source vertex
minimum_capacity_on_path = network.edge_label(path[1], path[2])
# for every pair of nodes along the path, check to see if there is a smaller residual capacity
for i in range(2,len(path) - 1):
temp = network.edge_label(path[i], path[i+1])
if temp < minimum_capacity_on_path and temp != -1:
minimum_capacity_on_path = temp
# for each pair of nodes along the augmented path, update their forward and backward edges using the bottleneck just found
for i in range(0, len(path) - 1):
# we restrict changes to our master source forward edge using this if statement
if network.edge_label(path[i], path[i + 1]) != -1:
# forward edge's residual capacity is decreased by the flow we are sending along the augmented path
network.set_edge_label(path[i], path[i + 1], network.edge_label(path[i], path[i + 1]) - minimum_capacity_on_path)
# backward edge's residual capacity is increased by the flow we are sending along the augmented path
network.set_edge_label(path[i + 1], path[i], network.edge_label(path[i + 1], path[i]) + minimum_capacity_on_path)
# once the updates to the old augmented path are complete, we find a new augmented path in the residual graph
path = max_flow_min_cut_find_augmented_path(network, source_vertex, sink_vertex, augmentingPathAlgorithm)
# we could not find anymore augmented paths, so set the max flow we are going to return as the flow out of our master source
for v in network.neighbors(source_vertex):
max_flow += network.edge_label(v, source_vertex)
# find and set the min-cut on side S so we can return it along with the max flow value
min_cut_s = max_flow_min_cut_find_min_cut(network, source_vertex)
# use the set of all vertices and side S of the min-cut to find side T
min_cut_t = network.vertices() # side T starts out as the set of all vertices in the network
for v in min_cut_s: # for every vertex on side S of the min-cut
min_cut_t.remove(v) # delete the vertex from side T
# we need to remove our master source and sink since they are not part of the user's network
min_cut_t.remove(source_vertex)
min_cut_t.remove(sink_vertex)
return (max_flow, (min_cut_s, min_cut_t))
## used for finding the minimum capacity along a path of vertices given to us
#def max_flow_min_cut_min(network, path):
# # initialize min to be the residual capacity out of the user's source vertex
# min = network.edge_label(path[1], path[2])
# # for every pair of nodes along the path, check to see if there is a smaller residual capacity
# for i in range(2,len(path) - 1):
# temp = network.edge_label(path[i], path[i+1])
# if temp < min and temp != -1:
# min = temp
# return min
## Implementations for Finding Augmented Paths
def max_flow_min_cut_find_augmented_path(network, source, sink, algorithm):
"""
This function finds an augmented path from the source to the sink in the given network
using the algorithm specified.
INPUT:
network -- the given Graph for which we find an augmented path over.
source -- the vertex our augmented path starts from.
sink -- the vertex our augmented path ends at.
source -- the algorithm to use when finding an augmented path.
OUTPUT:
list -- the list of vertices along the augmented path in order from source to sink.
EXAMPLES: TODO
This example illustrates ...
sage: A = ModuliSpace()
sage: A.point(2,3)
xxx
We now ...
sage: B = A.point(5,6)
sage: xxx
It is an error to ...
sage: C = A.point('x',7)
Traceback (most recent call last):
...
TypeError: unable to convert x (=r) to an integer
NOTES:
Supported Augmented Path Algorithms and their parameter integer form:
- Depth First Search: 0 # default
- Breadth First Search: 1 # not implemented yet
- Priority First Search: 2 # not implemented yet
AUTHORS:
- Scott Clifford (2008-05-16)
- Jerin Schneider (2008-05-16)
"""
if algorithm == 0: # use DFS implementation
path = [source] # add the master source to the path by default
visited = {source:1} # mark the master source as been visited
while len(path) != 0: # while there are still nodes to explore, proceed with the following
newPathFound = 0 # zero indicates we have explored a branch fully and need to backtrack
for e in network.edges_incident(path[-1]):
# if the node has not been visited and either there is residual capacity or the capacity is infinity, proceed
if not visited.has_key(e[1]) and (e[2] > 0 or e[2] == -1):
path.append(e[1])
newPathFound = 1 # we found another node to explore
visited.update({e[1]:1}) # mark the node just found as visited
break
# if we did not find a new path, then we backtrack on our path
if not newPathFound:
path.pop()
# else, if the node we just added to our path is the sink, we are done finding our augmented path
elif path[-1] == sink:
return path
return path
elif algorithm == 1: # use BFS implementation
raise NotImplementedError, "The BFS augmented path finding algorithm has not been implemented yet."
elif algorithm == 2: # use PFS implementation
raise NotImplementedError, "The PFS augmented path finding algorithm has not been implemented yet."
## Find Min-Cut Set
def max_flow_min_cut_find_min_cut(graph, source):
"""
This function takes a graph and finds all reachable vertices from the source supplied.
INPUT:
graph -- the given Graph for which we find the reachable vertices from the source.
source -- the vertex we find the reachable vertices from.
OUTPUT:
list -- the list of vertices which are reachable from the source vertex.
EXAMPLES: TODO
This example illustrates ...
sage: A = ModuliSpace()
sage: A.point(2,3)
xxx
We now ...
sage: B = A.point(5,6)
sage: xxx
It is an error to ...
sage: C = A.point('x',7)
Traceback (most recent call last):
...
TypeError: unable to convert x (=r) to an integer
NOTES:
AUTHORS:
- Scott Clifford (2008-05-16)
- Jerin Schneider (2008-05-16)
"""
cut = [] # the set of all reachable vertices from the handed in source
stack = [source] # used for backtracking via DFS
visited = {source:1}
while len(stack) != 0:
newPathFound = 0
for e in graph.edges_incident(stack[-1]):
# if the node has not been visited and either there is residual capacity or the capacity is infinity, proceed
if not visited.has_key(e[1]) and (e[2] > 0 or e[2] == -1):
cut.append(e[1])
stack.append(e[1])
newPathFound = 1 # we found another node to explore
visited.update({e[1]:1}) # mark the node just found as visited
break
# if we did not find a new path, then we backtrack on our path
if not newPathFound:
stack.pop()
return cut