Back to Repositories

Testing Bipartite Graph Detection Algorithm in williamfiset/Algorithms

This test suite validates the BipartiteGraphCheckAdjacencyList implementation, focusing on verifying bipartite graph properties across different graph structures. The tests ensure correct identification of bipartite and non-bipartite graphs using adjacency list representation.

Test Coverage Overview

The test suite provides comprehensive coverage of bipartite graph verification scenarios:

Single node self-loop cases
Basic two-node graph validation
Triangle graph detection
Disjoint graph components
Square graph configurations
Complex edge case scenarios

Implementation Analysis

The testing approach utilizes JUnit 5 framework with systematic graph construction and verification. Each test case builds specific graph structures using Utils helper methods, followed by bipartite property assertion using Truth assertions framework.

The implementation employs @BeforeEach setup and isolated test methods for clear separation of concerns.

Technical Details

Testing infrastructure includes:

JUnit Jupiter test framework
Google Truth assertion library
Custom Utils class for graph construction
Adjacency list representation
Graph utility methods for edge management

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Isolated test cases with clear purpose
Systematic test setup and teardown
Comprehensive edge case coverage
Clear test naming conventions
Efficient use of utility methods
Consistent assertion patterns

williamfiset/algorithms

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

            
package com.williamfiset.algorithms.graphtheory.networkflow;

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

import com.williamfiset.algorithms.utils.graphutils.Utils;
import java.util.*;
import org.junit.jupiter.api.*;

public class BipartiteGraphCheckAdjacencyListTest {

  private List<List<Integer>> graph;
  private BipartiteGraphCheckAdjacencyList solver;

  @BeforeEach
  public void setUp() {}

  @Test
  public void testSingleton() {
    int n = 1;
    graph = Utils.createEmptyAdjacencyList(n);
    solver = new BipartiteGraphCheckAdjacencyList(graph);
    Utils.addUndirectedEdge(graph, 0, 0);
    assertThat(solver.isBipartite()).isFalse();
  }

  @Test
  public void testTwoNodeGraph() {
    int n = 2;
    graph = Utils.createEmptyAdjacencyList(n);
    solver = new BipartiteGraphCheckAdjacencyList(graph);
    Utils.addUndirectedEdge(graph, 0, 1);
    assertThat(solver.isBipartite()).isTrue();
  }

  @Test
  public void testTriangleGraph() {
    int n = 3;
    graph = Utils.createEmptyAdjacencyList(n);
    solver = new BipartiteGraphCheckAdjacencyList(graph);
    Utils.addUndirectedEdge(graph, 0, 1);
    Utils.addUndirectedEdge(graph, 1, 2);
    Utils.addUndirectedEdge(graph, 2, 0);
    assertThat(solver.isBipartite()).isFalse();
  }

  @Test
  public void testDisjointBipartiteGraphComponents() {
    int n = 4;
    graph = Utils.createEmptyAdjacencyList(n);
    solver = new BipartiteGraphCheckAdjacencyList(graph);
    Utils.addUndirectedEdge(graph, 0, 1);
    Utils.addUndirectedEdge(graph, 2, 3);
    assertThat(solver.isBipartite()).isFalse();
  }

  @Test
  public void testSquareBipartiteGraph() {
    int n = 4;
    graph = Utils.createEmptyAdjacencyList(n);
    solver = new BipartiteGraphCheckAdjacencyList(graph);
    Utils.addUndirectedEdge(graph, 0, 1);
    Utils.addUndirectedEdge(graph, 1, 2);
    Utils.addUndirectedEdge(graph, 2, 3);
    Utils.addUndirectedEdge(graph, 3, 0);
    assertThat(solver.isBipartite()).isTrue();
  }

  @Test
  public void testSquareBipartiteGraphWithAdditionalEdge() {
    int n = 4;
    graph = Utils.createEmptyAdjacencyList(n);
    solver = new BipartiteGraphCheckAdjacencyList(graph);
    Utils.addUndirectedEdge(graph, 0, 1);
    Utils.addUndirectedEdge(graph, 1, 2);
    Utils.addUndirectedEdge(graph, 0, 2);
    Utils.addUndirectedEdge(graph, 2, 3);
    Utils.addUndirectedEdge(graph, 3, 0);
    assertThat(solver.isBipartite()).isFalse();
  }
}