Shuffly

6/**7 * Pure breadth-first search over the friend graph. No database access: the8 * caller injects a neighbor provider, so this class can be unit-tested with an9 * in-memory graph. Produces distance-2..maxDepth candidates ranked by BFS10 * distance (closer first), then by bridge count (more mutual paths first).11 *12 * Performance guards are class constants; the constructor accepts overrides so13 * tests can trip the caps cheaply without changing production behaviour.14 */15class FriendGraphTraversal16{17    public const HARD_MAX_DEPTH = 4;18    public const MAX_VISITED_NODES = 5000;19    public const MAX_FRONTIER = 2000;2021    public function __construct(22        private int $maxVisited = self::MAX_VISITED_NODES,23        private int $maxFrontier = self::MAX_FRONTIER,24    ) {25    }2627    public function clampDepth(int $requested): int28    {29        if ($requested < 2) {30            return 2;31        }32        return min($requested, self::HARD_MAX_DEPTH);33    }3435    /**36     * @param list<string>                                          $level1Keys37     * @param callable(list<string>): array<string, list<string>>  $neighborProvider38     * @param array<string, true>                                   $excludedKeys39     *40     * @return array{41     *   candidates: list<array{userKey: string, distance: int, bridgeCount: int, bridgeKeys: list<string>}>,42     *   truncated: bool43     * }44     */45    public function run(46        string $seedKey,47        array $level1Keys,48        callable $neighborProvider,49        array $excludedKeys,50        int $maxDepth,51    ): array {52        $maxDepth = $this->clampDepth($maxDepth);5354        // distance[key] = shortest hop count from seed. seed=0, direct friends=1.55        $distance = [$seedKey => 0];56        foreach ($level1Keys as $k) {57            $distance[$k] = 1;58        }5960        /** @var array<string, array<string, true>> $bridges candidateKey => set of level-1 bridge keys */61        $bridges = [];62        $truncated = false;63        $visited = count($distance);6465        $frontier = array_values(array_unique($level1Keys));66        $d = 1;6768        while ($d < $maxDepth && $frontier !== [] && $visited < $this->maxVisited) {69            if (count($frontier) > $this->maxFrontier) {70                $frontier = array_slice($frontier, 0, $this->maxFrontier);71                $truncated = true;72            }7374            $neighbors = $neighborProvider($frontier);7576            /** @var array<string, array<string, true>> $nextLayer */77            $nextLayer = [];78            foreach ($frontier as $node) {79                // Bridges that reach $node on a shortest path. A level-1 node is80                // its own bridge; deeper nodes carry the accumulated set.81                $nodeBridges = $d === 1 ? [(string) $node => true] : ($bridges[$node] ?? []);82                foreach (($neighbors[$node] ?? []) as $nb) {83                    if (isset($distance[$nb]) && $distance[$nb] <= $d) {84                        continue; // reached earlier/at this layer — not via $node's next hop85                    }86                    if (!isset($nextLayer[$nb])) {87                        $nextLayer[$nb] = [];88                    }89                    foreach ($nodeBridges as $b => $_) {90                        $nextLayer[$nb][$b] = true; // union accumulates distinct paths91                    }92                }93            }9495            $nextFrontier = [];96            foreach ($nextLayer as $nb => $brs) {97                if (isset($distance[$nb])) {98                    continue; // committed in an earlier (shorter) layer99                }100                $distance[$nb] = $d + 1;101                $bridges[$nb] = $brs;102                $nextFrontier[] = (string) $nb;103                $visited++;104                if ($visited >= $this->maxVisited) {105                    $truncated = true;106                    break;107                }108            }109110            $frontier = $nextFrontier;111            $d++;112        }113114        $candidates = [];115        foreach ($bridges as $key => $brs) {116            if (isset($excludedKeys[$key])) {117                continue;118            }119            $bridgeKeys = array_map('strval', array_keys($brs));120            sort($bridgeKeys);121            $candidates[] = [122                'userKey' => (string) $key,123                'distance' => $distance[$key],124                'bridgeCount' => count($brs),125                'bridgeKeys' => $bridgeKeys,126            ];127        }128129        usort($candidates, static function (array $a, array $b): int {130            return [$a['distance'], -$a['bridgeCount'], $a['userKey']]131                <=> [$b['distance'], -$b['bridgeCount'], $b['userKey']];132        });133134        return ['candidates' => $candidates, 'truncated' => $truncated];135    }136}

shuffly-serverb7006f04app/Services/Recommendation/FriendGraphTraversal.phpSatır 6 – 136131 satır

/**
 * Pure breadth-first search over the friend graph. No database access: the
 * caller injects a neighbor provider, so this class can be unit-tested with an
 * in-memory graph. Produces distance-2..maxDepth candidates ranked by BFS
 * distance (closer first), then by bridge count (more mutual paths first).
 *
 * Performance guards are class constants; the constructor accepts overrides so
 * tests can trip the caps cheaply without changing production behaviour.
 */
class FriendGraphTraversal
{
    public const HARD_MAX_DEPTH = 4;
    public const MAX_VISITED_NODES = 5000;
    public const MAX_FRONTIER = 2000;

    public function __construct(
        private int $maxVisited = self::MAX_VISITED_NODES,
        private int $maxFrontier = self::MAX_FRONTIER,
    ) {
    }

    public function clampDepth(int $requested): int
    {
        if ($requested < 2) {
            return 2;
        }
        return min($requested, self::HARD_MAX_DEPTH);
    }

    /**
     * @param list<string>                                          $level1Keys
     * @param callable(list<string>): array<string, list<string>>  $neighborProvider
     * @param array<string, true>                                   $excludedKeys
     *
     * @return array{
     *   candidates: list<array{userKey: string, distance: int, bridgeCount: int, bridgeKeys: list<string>}>,
     *   truncated: bool
     * }
     */
    public function run(
        string $seedKey,
        array $level1Keys,
        callable $neighborProvider,
        array $excludedKeys,
        int $maxDepth,
    ): array {
        $maxDepth = $this->clampDepth($maxDepth);

        // distance[key] = shortest hop count from seed. seed=0, direct friends=1.
        $distance = [$seedKey => 0];
        foreach ($level1Keys as $k) {
            $distance[$k] = 1;
        }

        /** @var array<string, array<string, true>> $bridges candidateKey => set of level-1 bridge keys */
        $bridges = [];
        $truncated = false;
        $visited = count($distance);

        $frontier = array_values(array_unique($level1Keys));
        $d = 1;

        while ($d < $maxDepth && $frontier !== [] && $visited < $this->maxVisited) {
            if (count($frontier) > $this->maxFrontier) {
                $frontier = array_slice($frontier, 0, $this->maxFrontier);
                $truncated = true;
            }

            $neighbors = $neighborProvider($frontier);

            /** @var array<string, array<string, true>> $nextLayer */
            $nextLayer = [];
            foreach ($frontier as $node) {
                // Bridges that reach $node on a shortest path. A level-1 node is
                // its own bridge; deeper nodes carry the accumulated set.
                $nodeBridges = $d === 1 ? [(string) $node => true] : ($bridges[$node] ?? []);
                foreach (($neighbors[$node] ?? []) as $nb) {
                    if (isset($distance[$nb]) && $distance[$nb] <= $d) {
                        continue; // reached earlier/at this layer — not via $node's next hop
                    }
                    if (!isset($nextLayer[$nb])) {
                        $nextLayer[$nb] = [];
                    }
                    foreach ($nodeBridges as $b => $_) {
                        $nextLayer[$nb][$b] = true; // union accumulates distinct paths
                    }
                }
            }

            $nextFrontier = [];
            foreach ($nextLayer as $nb => $brs) {
                if (isset($distance[$nb])) {
                    continue; // committed in an earlier (shorter) layer
                }
                $distance[$nb] = $d + 1;
                $bridges[$nb] = $brs;
                $nextFrontier[] = (string) $nb;
                $visited++;
                if ($visited >= $this->maxVisited) {
                    $truncated = true;
                    break;
                }
            }

            $frontier = $nextFrontier;
            $d++;
        }

        $candidates = [];
        foreach ($bridges as $key => $brs) {
            if (isset($excludedKeys[$key])) {
                continue;
            }
            $bridgeKeys = array_map('strval', array_keys($brs));
            sort($bridgeKeys);
            $candidates[] = [
                'userKey' => (string) $key,
                'distance' => $distance[$key],
                'bridgeCount' => count($brs),
                'bridgeKeys' => $bridgeKeys,
            ];
        }

        usort($candidates, static function (array $a, array $b): int {
            return [$a['distance'], -$a['bridgeCount'], $a['userKey']]
                <=> [$b['distance'], -$b['bridgeCount'], $b['userKey']];
        });

        return ['candidates' => $candidates, 'truncated' => $truncated];
    }
}