This repository has been archived by the owner on Oct 22, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 11
/
mincut.jl
30 lines (29 loc) · 1.51 KB
/
mincut.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
"""
mincut(flow_graph::lg.IsDirected, source::Integer, target::Integer, capacity_matrix::AbstractMatrix, algorithm::AbstractFlowAlgorithm)
Compute the min-cut between `source` and `target` for the given graph.
First computes the maxflow using `algorithm` and then builds the partition of the residual graph
Returns a triplet `(part1, part2, flow)` with the partition containing the source, the partition containing the target (the rest) and the min-cut(max-flow) value
"""
function mincut(
flow_graph::lg.DiGraph, # the input graph
source::Integer, # the source vertex
target::Integer, # the target vertex
capacity_matrix::AbstractMatrix, # edge flow capacities
algorithm::AbstractFlowAlgorithm # keyword argument for algorithm
)
flow, flow_matrix = maximum_flow(flow_graph, source, target, capacity_matrix, algorithm)
residual_matrix = spzeros(lg.nv(flow_graph),lg.nv(flow_graph))
for edge in lg.edges(flow_graph)
residual_matrix[edge.src,edge.dst] = max(0.0, capacity_matrix[edge.src,edge.dst] - flow_matrix[edge.src,edge.dst])
end
part1 = typeof(source)[]
queue = [source]
while !isempty(queue)
node = pop!(queue)
push!(part1, node)
dests = [dst for dst in 1:lg.nv(flow_graph) if residual_matrix[node,dst]>0.0 && dst ∉ part1]
append!(queue, dests)
end
part2 = [node for node in 1:lg.nv(flow_graph) if node ∉ part1]
return (part1, part2, flow)
end