FlowTest.java

Go to the documentation of this file.

// Copyright 2010-2022 Google LLC
// 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;
 
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNotNull;
 
import com.google.ortools.Loader;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
 
public final class FlowTest {
  @BeforeEach
  public void setUp() {
    Loader.loadNativeLibraries();
  }
 
  @Test
  public void testMinCostFlow() {
    final int numSources = 4;
    final int numTargets = 4;
    final int[][] costs = {
        {90, 75, 75, 80}, {35, 85, 55, 65}, {125, 95, 90, 105}, {45, 110, 95, 115}};
    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]);
    }
  }
}