2021-05-03 12:11:39 +02:00
|
|
|
#!/usr/bin/env python3
|
2025-01-10 11:35:44 +01:00
|
|
|
# Copyright 2010-2025 Google LLC
|
2011-03-16 15:32:09 +00:00
|
|
|
# Licensed under the Apache License, Version 2.0 (the "License");
|
|
|
|
|
# you may not use this file except in compliance with the License.
|
|
|
|
|
# You may obtain a copy of the License at
|
|
|
|
|
#
|
|
|
|
|
# http://www.apache.org/licenses/LICENSE-2.0
|
|
|
|
|
#
|
|
|
|
|
# Unless required by applicable law or agreed to in writing, software
|
|
|
|
|
# distributed under the License is distributed on an "AS IS" BASIS,
|
|
|
|
|
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
|
|
|
# See the License for the specific language governing permissions and
|
|
|
|
|
# limitations under the License.
|
2023-07-01 06:06:53 +02:00
|
|
|
|
2013-06-11 14:51:51 +00:00
|
|
|
"""MaxFlow and MinCostFlow examples."""
|
2011-03-16 15:32:09 +00:00
|
|
|
|
2023-01-29 21:20:58 +01:00
|
|
|
from typing import Sequence
|
2020-11-18 10:50:14 +01:00
|
|
|
from absl import app
|
2022-03-31 18:21:20 +02:00
|
|
|
from ortools.graph.python import max_flow
|
|
|
|
|
from ortools.graph.python import min_cost_flow
|
2011-03-16 15:32:09 +00:00
|
|
|
|
2013-06-11 14:51:51 +00:00
|
|
|
|
2023-01-29 21:20:58 +01:00
|
|
|
def max_flow_api():
|
2018-11-11 09:39:59 +01:00
|
|
|
"""MaxFlow simple interface example."""
|
2023-07-01 06:06:53 +02:00
|
|
|
print("MaxFlow on a simple network.")
|
2018-11-11 09:39:59 +01:00
|
|
|
tails = [0, 0, 0, 0, 1, 2, 3, 3, 4]
|
|
|
|
|
heads = [1, 2, 3, 4, 3, 4, 4, 5, 5]
|
|
|
|
|
capacities = [5, 8, 5, 3, 4, 5, 6, 6, 4]
|
|
|
|
|
expected_total_flow = 10
|
2022-03-31 18:21:20 +02:00
|
|
|
smf = max_flow.SimpleMaxFlow()
|
2018-11-11 09:39:59 +01:00
|
|
|
for i in range(0, len(tails)):
|
2022-03-31 18:21:20 +02:00
|
|
|
smf.add_arc_with_capacity(tails[i], heads[i], capacities[i])
|
|
|
|
|
if smf.solve(0, 5) == smf.OPTIMAL:
|
2023-07-01 06:06:53 +02:00
|
|
|
print("Total flow", smf.optimal_flow(), "/", expected_total_flow)
|
2022-03-31 18:21:20 +02:00
|
|
|
for i in range(smf.num_arcs()):
|
2023-07-01 06:06:53 +02:00
|
|
|
print(
|
|
|
|
|
"From source %d to target %d: %d / %d"
|
|
|
|
|
% (smf.tail(i), smf.head(i), smf.flow(i), smf.capacity(i))
|
|
|
|
|
)
|
|
|
|
|
print("Source side min-cut:", smf.get_source_side_min_cut())
|
|
|
|
|
print("Sink side min-cut:", smf.get_sink_side_min_cut())
|
2018-11-11 09:39:59 +01:00
|
|
|
else:
|
2023-07-01 06:06:53 +02:00
|
|
|
print("There was an issue with the max flow input.")
|
2011-03-16 15:32:09 +00:00
|
|
|
|
|
|
|
|
|
2023-01-29 21:20:58 +01:00
|
|
|
def min_cost_flow_api():
|
2018-11-11 09:39:59 +01:00
|
|
|
"""MinCostFlow simple interface example.
|
2013-06-11 14:51:51 +00:00
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
Note that this example is actually a linear sum assignment example and will
|
|
|
|
|
be more efficiently solved with the pywrapgraph.LinearSumAssignment class.
|
|
|
|
|
"""
|
|
|
|
|
print("MinCostFlow on 4x4 matrix.")
|
2018-11-11 09:39:59 +01:00
|
|
|
num_sources = 4
|
|
|
|
|
num_targets = 4
|
2025-07-23 17:38:49 +02:00
|
|
|
costs = [
|
|
|
|
|
[90, 75, 75, 80],
|
|
|
|
|
[35, 85, 55, 65],
|
|
|
|
|
[125, 95, 90, 105],
|
|
|
|
|
[45, 110, 95, 115],
|
|
|
|
|
]
|
2018-11-11 09:39:59 +01:00
|
|
|
expected_cost = 275
|
2022-03-31 18:21:20 +02:00
|
|
|
smcf = min_cost_flow.SimpleMinCostFlow()
|
2018-11-11 09:39:59 +01:00
|
|
|
for source in range(0, num_sources):
|
|
|
|
|
for target in range(0, num_targets):
|
2023-07-01 06:06:53 +02:00
|
|
|
smcf.add_arc_with_capacity_and_unit_cost(
|
|
|
|
|
source, num_sources + target, 1, costs[source][target]
|
|
|
|
|
)
|
2018-11-11 09:39:59 +01:00
|
|
|
for node in range(0, num_sources):
|
2022-03-31 18:21:20 +02:00
|
|
|
smcf.set_node_supply(node, 1)
|
|
|
|
|
smcf.set_node_supply(num_sources + node, -1)
|
|
|
|
|
status = smcf.solve()
|
|
|
|
|
if status == smcf.OPTIMAL:
|
2023-07-01 06:06:53 +02:00
|
|
|
print("Total flow", smcf.optimal_cost(), "/", expected_cost)
|
2022-03-31 18:21:20 +02:00
|
|
|
for i in range(0, smcf.num_arcs()):
|
|
|
|
|
if smcf.flow(i) > 0:
|
2023-07-01 06:06:53 +02:00
|
|
|
print(
|
|
|
|
|
"From source %d to target %d: cost %d"
|
|
|
|
|
% (smcf.tail(i), smcf.head(i) - num_sources, smcf.unit_cost(i))
|
|
|
|
|
)
|
2018-11-11 09:39:59 +01:00
|
|
|
else:
|
2023-07-01 06:06:53 +02:00
|
|
|
print("There was an issue with the min cost flow input.")
|
2011-03-16 15:32:09 +00:00
|
|
|
|
|
|
|
|
|
2023-01-29 21:20:58 +01:00
|
|
|
def main(argv: Sequence[str]) -> None:
|
|
|
|
|
if len(argv) > 1:
|
2023-07-01 06:06:53 +02:00
|
|
|
raise app.UsageError("Too many command-line arguments.")
|
2023-01-29 21:20:58 +01:00
|
|
|
max_flow_api()
|
|
|
|
|
min_cost_flow_api()
|
2011-03-16 15:32:09 +00:00
|
|
|
|
|
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
if __name__ == "__main__":
|
2020-11-18 10:50:14 +01:00
|
|
|
app.run(main)
|
