An implementation of graph algorithms for solving optimal cell pairing problems on colored grids, developed as part of an ENSAE programming project.

This project solves a combinatorial optimization problem: given a grid with colored and valued cells, find the optimal pairing of adjacent cells that minimizes the total cost. Cells have color constraints (some colors can only be paired with specific other colors) and values (the cost of a pair is the absolute difference of their values). The project implements and compares four different algorithmic approaches.

• Grid representation with color constraints (white, red, blue, green, black)
• Multiple solving algorithms with different optimality guarantees
• Visualization of grids and matching results
• File-based grid input format
• Comparison framework for algorithm benchmarking

├── code/
│   ├── main.py           # Entry point and algorithm comparison
│   ├── grid.py           # Grid class with color/value management
│   ├── graph.py          # Graph classes for flow algorithms
│   ├── solver.py         # Solver implementations
│   └── hongrois.py       # Hungarian algorithm wrapper
├── input/                # Test grid files (.in format)
└── tests/                # Unit tests

1. SolverGreedy: Greedy heuristic that iteratively pairs cells with minimum local cost. Fast but not optimal.

2. SolverFF (Ford-Fulkerson): Models the problem as maximum bipartite matching using max-flow. Uses BFS to find augmenting paths. Optimal for unweighted grids.

3. SolverFFBF (Ford-Fulkerson + Bellman-Ford): Extends Ford-Fulkerson with edge costs using the Busacker-Gowen algorithm. Finds minimum-cost maximum matching by using Bellman-Ford to find shortest augmenting paths.

4. SolverHongrois (Hungarian Algorithm): Classic assignment algorithm for weighted bipartite matching. Guarantees optimal solution with O(n^3) complexity.

The grid is modeled as a bipartite graph where:

• Cells at positions (i,j) where i+j is even form set U
• Cells at positions (i,j) where i+j is odd form set V
• Edges connect adjacent cells with compatible colors
• Edge weights represent pairing costs (value differences)

• White (0): Can pair with any non-black color
• Red (1): Can pair with red or blue
• Blue (2): Can pair with blue or red
• Green (3): Can only pair with green
• Black (4): Cannot be paired (forbidden cells)

• Python
• NumPy
• Matplotlib
• SciPy (for Hungarian algorithm)