Graph Algorithms Laravel Package

Getting Started

Install and confirm what you actually got.

composer require nexus-scholar/graph-algorithms

Two things to check immediately, because the package was renamed at v1.2.0:

1. The Composer name is nexus-scholar/graph-algorithms. If your codebase (or a transitive dep) requires mbsoft31/graph-algorithms, the replace bridge satisfies it — but only when the nexus-scholar package is the one installed. Don't end up with both.
2. The PHP namespace is still Mbsoft\Graph\Algorithms\*. Every use statement in the README uses Mbsoft\…, not NexusScholar\…. This is not a typo.

You also inherit nexus-scholar/graph-core ^1.0 as a hard dependency. That package owns the graph storage model (string node IDs, array edge attributes, a GraphInterface). graph-algorithms only computes over it. There is no Laravel service provider, no config file, no facade — these are plain, instantiable PHP objects.

Where to look first. Read these four things before writing anything:

• CentralityAlgorithmInterface, PathfindingAlgorithmInterface, TraversalAlgorithmInterface — these define the contracts you'll mock in tests.
• PathResult and MstResult — immutable value objects. PathResult gives you ->nodes and ->cost. They're trivially json_encode-able into an API response.
• AlgorithmGraph and IndexMap — the integer-indexed proxy used during execution. Knowing this exists is what explains the performance profile you'll measure later.
• graph-core's GraphInterface builder — because constructing the graph is 80% of your integration work and 0% of this package's surface area.

First use case: PageRank on data you already have. The lowest-friction entry point is centrality, because it needs no start node and no weights — just a directed graph. If you have a follows, cites, depends_on, or references table, you have a graph.

use Mbsoft\Graph\Algorithms\Centrality\PageRank;

$pagerank = new PageRank(dampingFactor: 0.85, maxIterations: 100, tolerance: 1e-6);

$scores = $pagerank->compute($graph);   // ['node-id' => 0.0421, ...]
arsort($scores);

Ship that as an Artisan command or a queued job, eyeball the top 20 against your own intuition about the data, and only then wire it into a UI. That's a half-day spike, not a sprint.

Implementation Patterns

Pattern 1 — An adapter service, not scattered graph building. You will build the same graph-from-Eloquent in three places unless you centralize it. Keep graph construction out of your controllers and away from the algorithms.

namespace App\Graph;

use App\Models\Citation;
use App\Models\Paper;

class CitationGraphBuilder
{
    public function build(): \Mbsoft\Graph\Core\GraphInterface
    {
        $graph = /* graph-core builder for a directed graph */;

        Paper::query()->select('id')->cursor()->each(
            fn ($paper) => $graph->addNode((string) $paper->id)
        );

        Citation::query()->select('citing_id', 'cited_id', 'weight')->cursor()->each(
            fn ($c) => $graph->addEdge(
                (string) $c->citing_id,
                (string) $c->cited_id,
                ['weight' => (float) $c->weight],
            )
        );

        return $graph;
    }
}

Cast IDs to string explicitly. The node model is string-keyed; an int from Eloquent that silently becomes "12" in one code path and 12 in another produces "no path found" bugs that take an hour to find.

Pattern 2 — Bind algorithm classes in a service provider, configured from config/. These are stateless, cheap-to-construct value objects. Bind them as singletons with your tuned parameters so every caller gets consistent behavior instead of each developer picking a damping factor.

// AppServiceProvider::register()
$this->app->singleton(PageRank::class, fn () => new PageRank(
    dampingFactor: config('graph.pagerank.damping', 0.85),
    maxIterations:  config('graph.pagerank.max_iterations', 100),
    tolerance:      config('graph.pagerank.tolerance', 1e-6),
));

Pattern 3 — Run heavy algorithms in a queue job, cache the result. PageRank over 10k+ nodes with 100 iterations is not request-cycle work. Tarjan SCC and topological sort are linear and usually fine inline; PageRank is the one to watch. Also: AlgorithmGraph builds an integer-indexed proxy on every compute() call. If you call PageRank, then Dijkstra, then SCC in the same request, you pay that conversion each time.

class RecomputeInfluence implements ShouldQueue
{
    public function handle(PageRank $pagerank, CitationGraphBuilder $builder): void
    {
        $scores = $pagerank->compute($builder->build());
        arsort($scores);

        Cache::put('graph:pagerank', $scores, now()->addHours(24));
        InfluenceSnapshot::create(['scores' => $scores, 'computed_at' => now()]);
    }
}

Schedule it nightly. Store the raw array — it's the cheapest thing to render, diff, and chart.

Pattern 4 — Custom weight callbacks are how you make pathfinding yours. The default edge weight won't match your domain. Both Dijkstra and A* accept a callback with the signature (array $attrs, string $from, string $to): float.

$cheapest = new Dijkstra(
    fn (array $attrs, string $from, string $to): float =>
        $attrs['cost'] ?? $attrs['weight'] ?? 1.0,
);

$path = $cheapest->find($graph, $startId, $endId);

if ($path === null) {
    // genuinely no route — a normal outcome, not an exception
    return null;
}

return ['nodes' => $path->nodes, 'cost' => $path->cost];

Pattern 5 — Topological sort is your dependency/ordering primitive. This is the sleeper feature. Build pipelines, prerequisite chains, migration ordering, "which tasks must run first," and — critically — circular dependency detection, which is a user-facing error message most apps handle badly.

$sorted = (new TopologicalSort())->sort($graph);   // reports cycles

Detect the cycle, surface it as a domain exception with the offending node IDs, and render it. This alone justifies the dependency if you have any DAG-shaped domain.

Pattern 6 — Tarjan SCC for clustering and circularity. Strongly connected components give you mutually-reinforcing citation rings, duplicate-record clusters, or circular depends_on groups. findComponents() returns arrays of node IDs; anything with count() > 1 in a directed graph is a cycle.

$components = (new StronglyConnected())->findComponents($graph);
$cycles = array_filter($components, fn ($c) => count($c) > 1);

Pattern 7 — Mock the interfaces in tests, assert on the value objects. This is where the typed contracts pay off. In a feature test, you don't want to run real PageRank — you want to assert the controller renders scores correctly.

$this->mock(PageRank::class, fn ($m) => $m
    ->shouldReceive('compute')
    ->andReturn(['paper-1' => 0.6, 'paper-2' => 0.4]));

Keep a handful of real, tiny, hand-verified fixtures (the package ships canonical ones) so you have one test proving the algorithm itself runs end-to-end through your adapter. Everything above that level should be mocked.

Pattern 8 — Expose results through a Resource, not raw arrays. PathResult and MstResult are immutable and map cleanly to JSON. Wrap them in an ApiResource so you have one place to change the shape when you add fields:

return [
    'path'  => $path->nodes,
    'cost'  => round($path->cost, 4),
    'steps' => count($path->nodes) - 1,
];

Gotchas and Tips

The rename is the sharpest edge. Composer name nexus-scholar/graph-algorithms, PHP namespace Mbsoft\Graph\Algorithms, original package mbsoft31/graph-algorithms bridged via replace. Pin the exact version in composer.json, and put a one-line comment next to the require explaining the rename. Anyone who later runs composer require mbsoft31/graph-algorithms out of habit will either get a different package or a confusing resolution. Also: IDE auto-import and every tutorial you find online will use the old name.

Treat this as a pilot, not core infrastructure. One star, zero dependents, single maintainer, a recent rename, and a graph-core transitive dependency. The codebase is readable in an afternoon — read it. Plan for the possibility that you own a fork. Concretely: pin the version, keep your integration behind the App\Graph\* adapter layer so swapping implementations is a one-file change, and don't let PathResult leak into your domain models.

Benchmark AlgorithmGraph at your real sizes before committing. The README says "high-performance"; no benchmarks are published. Measure on 10k and 100k nodes. The integer-indexed proxy is a deliberate design choice — it trades a conversion pass for faster inner loops — but whether that wins depends on graph shape and how often you rebuild. Cache built graphs where you can.

Failure modes are split between null and exceptions, and you must handle both:

The negative-weight throw is the one that bites: an attribute like weight: -1 (a credit, a discount, a reversed cost) will explode only for some inputs. Validate weights at the adapter boundary, not at the algorithm call.

A* heuristics must be admissible. If your heuristicCallback overestimates the true remaining cost, A* returns a path that isn't optimal — silently. If you don't have a genuine admissible heuristic (geometric distance over coordinates, typically), use Dijkstra. A* with a bad heuristic is worse than no heuristic.

PageRank tuning is data-dependent. dampingFactor: 0.85, maxIterations: 100, tolerance: 1e-6 are defaults, not truth. On a sparse graph you may not converge in 100 iterations; on a dense one you're burning CPU. Check whether your scores stabilize when you double maxIterations — if the ranking reshuffles, your numbers aren't converged and you shouldn't ship them to users. Also confirm how dangling nodes (no outbound edges) are handled in the source before you trust the output; it's the classic PageRank correctness trap.

graph-core is a real architectural commitment. Adopting this package means standardizing on string node IDs, array edge attributes, and GraphInterface throughout your graph code. If you already have a graph model — a custom node class, non-array attributes, UUIDs with namespaces — the adapter is real work and erodes the buy case. Audit the transitive dependency before it touches anything revenue-critical.

The package computes; it does not persist, serialize, or render. There is no Eloquent integration, no migration, no storage, no visualization. Caching, snapshot tables, chart data, and API shape are entirely yours. Budget for that — it's usually more code than the algorithm call itself.

Extension points you actually have: the three algorithm interfaces (for swapping implementations or faking in tests), the weight and heuristic callbacks (for injecting domain logic), and AlgorithmGraph (for pre-building a proxy you reuse across multiple algorithm runs). There is no plugin registry — extending means implementing the interface and binding your class.

Build-vs-buy, honestly. A single BFS is ~40 lines; don't take a dependency for it. The case is real at two or more algorithm families in the next two quarters. The genuinely hard-to-hand-roll pieces are PageRank convergence and Tarjan SCC — those are where hand-rolled code accumulates subtle, expensive bugs. If those two are on your roadmap, this package earns its place. If you only need reachability, write the 40 lines.