Back to Repositories

Testing Network Flow Algorithm Implementation in williamfiset/Algorithms

This test suite validates the implementation of minimum cost maximum flow algorithms in graph theory, focusing on network flow solvers and negative cycle detection. The tests ensure correct flow calculations and cost optimizations in network graphs.

Test Coverage Overview

The test suite provides comprehensive coverage of network flow algorithms with specific focus on minimum cost maximum flow calculations. Key test scenarios include:

Negative cycle detection and handling
Flow capacity constraints verification
Cost optimization validation
Multiple solver implementation testing

Implementation Analysis

The testing approach utilizes JUnit 5 framework with a modular design pattern for testing multiple solver implementations. The suite implements a base solver class with specialized implementations for different algorithms, particularly focusing on Johnson’s algorithm for min-cost max-flow problems.

Technical Details

Testing infrastructure includes:

JUnit Jupiter test framework
Google Truth assertion library
Custom NetworkFlowSolverBase implementation
BeforeEach setup for solver initialization
Parameterized edge addition testing

Best Practices Demonstrated

The test suite exemplifies several testing best practices including:

Modular test setup with clear separation of concerns
Consistent test initialization patterns
Reusable test utilities and helper methods
Clear assertion methods for verification
Comprehensive edge case handling

williamfiset/algorithms

src/test/java/com/williamfiset/algorithms/graphtheory/networkflow/MinCostMaxFlowTests.java

            
package com.williamfiset.algorithms.graphtheory.networkflow;

import static com.google.common.truth.Truth.assertThat;

import java.util.*;
import org.junit.jupiter.api.*;

public class MinCostMaxFlowTests {

  List<NetworkFlowSolverBase> solvers;

  @BeforeEach
  public void setUp() {
    solvers = new ArrayList<>();
  }

  void createAllSolvers(int n, int s, int t) {
    // TODO(issue/67): Fix Bellman Ford mincost maxflow
    // solvers.add(new MinCostMaxFlowWithBellmanFord(n, s, t));
    solvers.add(new MinCostMaxFlowJohnsons(n, s, t));
  }

  void addEdge(int f, int t, int cap, int cost) {
    for (NetworkFlowSolverBase solver : solvers) {
      solver.addEdge(f, t, cap, cost);
    }
  }

  void assertFlowAndCost(long flow, long cost) {
    for (NetworkFlowSolverBase solver : solvers) {
      assertThat(solver.getMaxFlow()).isEqualTo(flow);
      assertThat(solver.getMinCost()).isEqualTo(cost);
    }
  }

  @Test
  public void testNegativeCycle1() {
    int n = 5, s = n - 1, t = n - 2;
    createAllSolvers(n, s, t);

    addEdge(s, 0, 100, 0);
    addEdge(1, t, 100, 0);

    // Triangle cycle
    addEdge(0, 1, 10, -1);
    addEdge(1, 2, 10, -1);
    addEdge(2, 0, 10, -1);

    assertFlowAndCost(10, -10);
  }
}