Loop elimination in a weighted, directed graph

LoopEliminator.php

<?php

namespace App\Graph;

use Ds\{Set, Stack};

class LoopEliminatior {

    const INFINITE = 1000000000;

    // Simple array based graph representation $graph['alice']['bob'] = 40
    // First index is the person who owes the value to the person in the second index 
    // So in our example Alice owes Bob 40
    protected $graph = [];

    public function __construct($graph) 
    {
        $this->graph = $graph;
    }

    protected function getAdjacentEdges($v) 
    {
        return array_keys(
            // Do not return those edges which are already reduced to 0 weight ...
            array_filter($this->graph[$v], fn($w) => $w !== 0)
        );
    }
    
    // Define a function to find a cycle in the graph using depth-first search
    protected function findCycle($start): array 
    {

        // Initialize a stack to store the vertices to visit
        $stack = new Stack();
        $stack->push($start);

        // Initialize a set to store the visited vertices
        $visited = new Set();

        // Initialize a dictionary to store the parent of each vertex
        $parent = [];

        // Loop until the stack is empty
        while (!$stack->isEmpty()) {

            // Pop a vertex from the stack
            $v = $stack->pop();

            // Mark it as visited
            $visited->add($v);

            // Loop through its neighbors
            foreach ($this->getAdjacentEdges($v) as $u) {
                // If the neighbor is the start vertex, we have found a cycle
                if ($u === $start) {
                    // Initialize a list to store the cycle
                    $cycle = [];
    
                    // Trace back the path from v to start using the parent dictionary
                    while ($v !== $start) {
                        // Add the edge (v, parent[v]) to the cycle
                        $cycle[] = [$v, $parent[$v]];
    
                        // Move to the parent vertex
                        $v = $parent[$v];
                    }

                    // Complete the cycle with adding the 'last' edge to it ... ugly
                    $cycle[] = [$v, $cycle[0][0]];
    
                    // Return the cycle
                    return $cycle;
    
                // If the neighbor is not visited, push it to the stack and update its parent
                } elseif (!$visited->contains($u)) {
                    $stack->push($u);
                    $parent[$u] = $v;
                }
            }

        }

        // If no cycle is found, return an empty array ...
        return [];

    }

    protected function minWeight(array $cycle = []): int 
    {

        return array_reduce($cycle, function ($carry, $edge) {
            list($v, $u) = $edge;
            return $this->graph[$u][$v] < $carry
                ? $this->graph[$u][$v]
                : $carry;
        }, self::INFINITE);

    }

    public function getGraph(): array 
    {
        return $this->graph;
    }

    // Define a function to cancel a cycle by subtracting the minimum weight from all edges in the cycle
    protected function cancelCycle($cycle) 
    {
        
        // Find the minimum weight of the cycle
        $min_weight = $this->minWeight($cycle);
        
        // Loop through the edges in the cycle
        foreach ($cycle as list($v, $u)) {
            // Subtract the minimum weight from the edge weight
            $this->graph[$u][$v] -= $min_weight;
        }
        
    }
    
    // Define a function to reduce the number of payments using the algorithm
    public function reducePayments(): self 
    {

        // Get the first vertex in the graph
        $vertices = array_keys($this->graph);
        $firstVertex = reset($vertices);

        // Loop until there are no more cycles in the graph
        while ($cycle = $this->findCycle($firstVertex)) {
            // Cancel the cycle
            $this->cancelCycle($cycle);
        }

        return $this;

    }

}