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
|
2012-02-20 12:09:28 +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
|
|
|
|
2012-02-20 12:09:28 +00:00
|
|
|
"""Test linear sum assignment on a 4x4 matrix.
|
|
|
|
|
|
2025-07-23 17:38:49 +02:00
|
|
|
Example taken from:
|
|
|
|
|
http://www.ee.oulu.fi/~mpa/matreng/eem1_2-1.htm with kCost[0][1]
|
|
|
|
|
modified so the optimum solution is unique.
|
2012-02-20 12:09:28 +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 linear_sum_assignment
|
2012-02-20 12:09:28 +00:00
|
|
|
|
|
|
|
|
|
2023-01-29 21:20:58 +01:00
|
|
|
def run_assignment_on_4x4_matrix():
|
2020-11-18 10:50:14 +01:00
|
|
|
"""Test linear sum assignment on a 4x4 matrix."""
|
2018-11-11 09:39:59 +01:00
|
|
|
num_sources = 4
|
|
|
|
|
num_targets = 4
|
2025-07-23 17:38:49 +02:00
|
|
|
cost = [
|
|
|
|
|
[90, 76, 75, 80],
|
|
|
|
|
[35, 85, 55, 65],
|
|
|
|
|
[125, 95, 90, 105],
|
|
|
|
|
[45, 110, 95, 115],
|
|
|
|
|
]
|
2018-11-11 09:39:59 +01:00
|
|
|
expected_cost = cost[0][3] + cost[1][2] + cost[2][1] + cost[3][0]
|
|
|
|
|
|
2022-03-31 18:21:20 +02:00
|
|
|
assignment = linear_sum_assignment.SimpleLinearSumAssignment()
|
2018-11-11 09:39:59 +01:00
|
|
|
for source in range(0, num_sources):
|
|
|
|
|
for target in range(0, num_targets):
|
2022-03-31 18:21:20 +02:00
|
|
|
assignment.add_arc_with_cost(source, target, cost[source][target])
|
2018-11-11 09:39:59 +01:00
|
|
|
|
2022-03-31 18:21:20 +02:00
|
|
|
solve_status = assignment.solve()
|
2018-11-11 09:39:59 +01:00
|
|
|
if solve_status == assignment.OPTIMAL:
|
2023-07-01 06:06:53 +02:00
|
|
|
print("Successful solve.")
|
|
|
|
|
print("Total cost", assignment.optimal_cost(), "/", expected_cost)
|
2022-03-31 18:21:20 +02:00
|
|
|
for i in range(0, assignment.num_nodes()):
|
2023-07-01 06:06:53 +02:00
|
|
|
print(
|
|
|
|
|
"Left node %d assigned to right node %d with cost %d."
|
|
|
|
|
% (i, assignment.right_mate(i), assignment.assignment_cost(i))
|
|
|
|
|
)
|
2018-11-11 09:39:59 +01:00
|
|
|
elif solve_status == assignment.INFEASIBLE:
|
2023-07-01 06:06:53 +02:00
|
|
|
print("No perfect matching exists.")
|
2018-11-11 09:39:59 +01:00
|
|
|
elif solve_status == assignment.POSSIBLE_OVERFLOW:
|
2023-07-01 06:06:53 +02:00
|
|
|
print("Some input costs are too large and may cause an integer overflow.")
|
2012-02-20 12:09:28 +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
|
|
|
run_assignment_on_4x4_matrix()
|
2012-02-20 12:09:28 +00:00
|
|
|
|
2018-06-11 11:51:18 +02:00
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
if __name__ == "__main__":
|
2020-11-18 10:50:14 +01:00
|
|
|
app.run(main)
|
