[FEATURE REQUEST] Add Push–Relabel (Relabel-to-Front variant) max-flow to graph package

[SamXop123]

What would you like to Propose?

What would you like to Propose?

• [type] New implementation
• [name] Push–Relabel (Relabel-to-Front variant, array-based)
• [problem statement]
  • Given a directed graph with non-negative capacities and vertices source and sink, compute the maximum flow using the Push–Relabel method.
• [why]
  • Complements existing max-flow algorithms (EdmondsKarp, Dinic) with a different approach that is competitive in practice.
  • Enables parity testing across multiple max-flow implementations.

Issue details

Issue details:

• [algorithm]

  • Push–Relabel with preflow initialization.
  • Repeatedly discharge active vertices by pushing along admissible edges; relabel when no admissible edges remain.
  • Queue-based activation: when a vertex’s excess becomes positive (and is neither source nor sink), it becomes active.
  • Array-based residual graph; adjacency-matrix capacities.

• [API]

  • int PushRelabel.maxFlow(int[][] capacity, int source, int sink)
    • capacity[u][v] >= 0, square matrix.
    • Returns max-flow value.

• [files to add/update]

  • src/main/java/com/thealgorithms/graph/PushRelabel.java
  • src/test/java/com/thealgorithms/graph/PushRelabelTest.java
  • DIRECTORY.md → add index entry under graph/.

• [validation]

  • Check matrix is square and non-null.
  • Non-negative capacities.
  • Valid source, sink indices.

• [complexity]

  • Worst-case O(V^3) for the array-based variant.

• [tests]

  • CLRS canonical network: expected flow = 23.
  • Disconnected network: flow = 0.
  • source == sink: flow = 0.
  • Parity on random small graphs vs EdmondsKarp and Dinic.

• [style/quality gates]

  • Javadoc with brief description, input contract, complexity, and reference link.
  • Pass mvn verify (Checkstyle, PMD, SpotBugs).
  • clang-format with --style=file.

• [references]

  • CLRS (Introduction to Algorithms) Push–Relabel.
  • Wikipedia: Push–Relabel maximum flow algorithm.

Additional Information

Additional Information:

• [rationale] Adds a widely taught algorithm to complement the repository’s flow toolkit and supports comparative testing.
• [future enhancements]
  • Adjacency-list version with heuristics (e.g., gap heuristic, global relabeling).
  • Relabel-to-front list-based optimization.
• [compatibility]
  • Mirrors the API style of EdmondsKarp.maxFlow(...) and Dinic.maxFlow(...) for consistency.

Reference links

Push–Relabel (Wikipedia): https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm
Dinic (for context): https://en.wikipedia.org/wiki/Dinic%27s_algorithm
Edmonds–Karp (for context): https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm