def max_flow(edges, source, sink):
"""Returns the maximum flow that can be routed from source to sink.
Uses the push-relabel algorithm (also known as pre-flow push) to push
flow to nodes, then divert any excess flow at the nodes to 'downhill'
(lower labeled) nodes until the flow reaches sink.
Args:
edges: A list of directed edge tuples of the form
(start, end, capacity), where start and end both represent nodes,
and capacity represents the maximum capacity that can pass through
this edge at once.
start and end may be strings or numbers, and capacity must be a
number.
source, sink: Node names identifying the start (source) and end (sink)
nodes of the paths. May be numbers or strings.
If both names are not included in edges, the maximum flow will be 0.
Returns:
A floating point number indicating the maximum flow that can be routed
from source to sink through edges.
"""
flow, labels, outgoing_edges, incoming_edges = _initialize(edges, source)
# Start with the nodes that are adjacent to source, since they can get flow
excess_nodes = [edge[1] for edge in outgoing_edges[source]]
while len(excess_nodes) > 0:
current = excess_nodes.pop()
pushed = _push(
outgoing_edges[current], incoming_edges[current], labels, flow)
if not (pushed or _relabel(outgoing_edges[current], labels)):
# Try next node if nothing could be pushed or relabeled
continue
# Only check nodes with outgoing edges
excess_nodes = [node for node in outgoing_edges if _excess(
flow, outgoing_edges[node], incoming_edges[node]) > 0]
# Use fsum for precision in case capacities are floats
return math.fsum(flow[x] for x in incoming_edges[sink])
评论列表
文章目录
