2025-01-10 11:33:35 +01:00
|
|
|
// Copyright 2010-2025 Google LLC
|
2021-08-31 11:58:46 +02: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.
|
|
|
|
|
|
|
|
|
|
package com.google.ortools.graph;
|
|
|
|
|
|
2026-01-28 17:42:53 +01:00
|
|
|
import static org.junit.jupiter.api.Assertions.assertEquals;
|
|
|
|
|
import static org.junit.jupiter.api.Assertions.assertNotNull;
|
2021-08-31 11:58:46 +02:00
|
|
|
|
|
|
|
|
import com.google.ortools.Loader;
|
2026-01-28 17:42:53 +01:00
|
|
|
import org.junit.jupiter.api.BeforeEach;
|
|
|
|
|
import org.junit.jupiter.api.Test;
|
2021-08-31 11:58:46 +02:00
|
|
|
|
|
|
|
|
/** Test the Min/Max Flow solver java interface. */
|
|
|
|
|
public final class FlowTest {
|
2026-01-28 17:42:53 +01:00
|
|
|
@BeforeEach
|
2021-08-31 11:58:46 +02:00
|
|
|
public void setUp() {
|
|
|
|
|
Loader.loadNativeLibraries();
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Test
|
|
|
|
|
public void testMinCostFlow() {
|
|
|
|
|
final int numSources = 4;
|
|
|
|
|
final int numTargets = 4;
|
2022-02-16 16:19:26 +01:00
|
|
|
final int[][] costs = {
|
|
|
|
|
{90, 75, 75, 80}, {35, 85, 55, 65}, {125, 95, 90, 105}, {45, 110, 95, 115}};
|
2021-08-31 11:58:46 +02:00
|
|
|
final int expectedCost = 275;
|
|
|
|
|
final MinCostFlow minCostFlow = new MinCostFlow();
|
|
|
|
|
assertNotNull(minCostFlow);
|
|
|
|
|
for (int source = 0; source < numSources; ++source) {
|
|
|
|
|
for (int target = 0; target < numTargets; ++target) {
|
|
|
|
|
minCostFlow.addArcWithCapacityAndUnitCost(
|
|
|
|
|
source, numSources + target, 1, costs[source][target]);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
for (int source = 0; source < numSources; ++source) {
|
|
|
|
|
minCostFlow.setNodeSupply(source, 1);
|
|
|
|
|
}
|
|
|
|
|
for (int target = 0; target < numTargets; ++target) {
|
|
|
|
|
minCostFlow.setNodeSupply(numSources + target, -1);
|
|
|
|
|
}
|
|
|
|
|
final MinCostFlowBase.Status solveStatus = minCostFlow.solve();
|
|
|
|
|
assertEquals(solveStatus, MinCostFlow.Status.OPTIMAL);
|
|
|
|
|
final long totalFlowCost = minCostFlow.getOptimalCost();
|
|
|
|
|
assertEquals(expectedCost, totalFlowCost);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Test
|
|
|
|
|
public void testMaxFlow() {
|
|
|
|
|
final int numNodes = 6;
|
|
|
|
|
final int numArcs = 9;
|
|
|
|
|
final int[] tails = {0, 0, 0, 0, 1, 2, 3, 3, 4};
|
|
|
|
|
final int[] heads = {1, 2, 3, 4, 3, 4, 4, 5, 5};
|
|
|
|
|
final int[] capacities = {5, 8, 2, 0, 4, 5, 6, 0, 4};
|
|
|
|
|
final int[] expectedFlows = {4, 4, 2, 0, 4, 4, 0, 6, 4};
|
|
|
|
|
final int expectedTotalFlow = 10;
|
|
|
|
|
final MaxFlow maxFlow = new MaxFlow();
|
|
|
|
|
assertNotNull(maxFlow);
|
|
|
|
|
for (int i = 0; i < numArcs; ++i) {
|
|
|
|
|
maxFlow.addArcWithCapacity(tails[i], heads[i], capacities[i]);
|
|
|
|
|
}
|
|
|
|
|
maxFlow.setArcCapacity(7, 6);
|
|
|
|
|
final MaxFlow.Status solveStatus = maxFlow.solve(/*source=*/0, /*sink=*/numNodes - 1);
|
|
|
|
|
assertEquals(solveStatus, MaxFlow.Status.OPTIMAL);
|
|
|
|
|
final long totalFlow = maxFlow.getOptimalFlow();
|
|
|
|
|
assertEquals(expectedTotalFlow, totalFlow);
|
|
|
|
|
for (int i = 0; i < numArcs; ++i) {
|
|
|
|
|
assertEquals(maxFlow.getFlow(i), expectedFlows[i]);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
