Algorithms Laravel Package

Getting Started

graphp/algorithms is a library, not a framework: it operates on graph objects built with graphp/graph (pulled in transitively). Install both explicitly so you control versions:

composer require graphp/graph graphp/algorithms

Then check two things before writing code:

1. composer show graphp/algorithms — the latest release is from Feb 2020, so confirm the resolved graphp/graph version and PHP constraint against your runtime (PHP 8.1+ usually works but is not declared).
2. The README's shortest-path example and src/ShortestPath/ — it's the fastest way to see the constructor/result conventions every other algorithm follows.

First use case: weighted shortest path

Build a graph, put costs on the weight edge attribute, and ask Dijkstra for distances and routes:

<?php
require 'vendor/autoload.php';

use Graphp\Graph\Graph;
use Graphp\Algorithms\ShortestPath\Dijkstra;

$graph = new Graph();
$home  = $graph->createVertex('home');
$shop  = $graph->createVertex('shop');
$work  = $graph->createVertex('work');

$graph->createEdgeDirected($home, $shop)->setAttribute('weight', 2);
$graph->createEdgeDirected($shop, $work)->setAttribute('weight', 3);
$graph->createEdgeDirected($home, $work)->setAttribute('weight', 10);

$dijkstra = new Dijkstra($graph);

$distance = $dijkstra->getDistanceTo($work); // 5.0
$path     = $dijkstra->getPathTo($work);     // Edge[] home->shop, shop->work

foreach ($path as $edge) {
    echo $edge->getVertexStart()->getId(), ' -> ', $edge->getVertexEnd()->getId(), PHP_EOL;
}

From there, the same new Algorithm($graph) shape applies to MinimumSpanningTree\Kruskal/Prim, ConnectedComponents, TopologicalSort, Bipartitep, DetectNegativeCycle, and the Tree\*/Loop/Complete helpers.

Implementation Patterns

Build once, query many

Algorithm objects compute and cache maps internally (Dijkstra's distance/path maps, for example). Build the graph in a factory, construct the algorithm object, then serve many queries from it:

$dijkstra = new Dijkstra($graph);
$distances = $dijkstra->getDistanceMap(); // all reachable vertices in one pass

Use getDistanceMap() for "nearest X" screens and only call getPathTo() when you actually need to render a route. This avoids re-running the search per row in a table.

Pick the algorithm by weight semantics

Kruskal::getTree() and Prim::getTree() return a new graph, not an array — iterate its edges to render a network plan or to feed a second algorithm.

Wrap it in a domain service

The graph is a computation artifact, not your persistence layer. Keep a [id => domain object] map alongside the nodes, and expose intent-level methods:

final class RoutePlanner
{
    private Dijkstra $dijkstra;
    private array $nodes = []; // id => Stop

    public function __construct(iterable $stops, iterable $legs) {
        $graph = new Graph();
        foreach ($stops as $stop) {
            $this->nodes[$stop->id] = $stop;
            $graph->createVertex($stop->id);
        }
        foreach ($legs as $leg) {
            $graph->createEdgeDirected(
                $graph->getVertex($leg->from),
                $graph->getVertex($leg->to)
            )->setAttribute('weight', $leg->minutes);
        }
        $this->dijkstra = new Dijkstra($graph);
    }

    public function minutes(string $from, string $to): ?float {
        $d = $this->dijkstra->getDistanceTo($this->dijkstra->getGraph()->getVertex($to));
        return is_finite($d) ? $d : null;
    }
}

Pipeline patterns that pay off

• Cluster first, then route: run ConnectedComponents::getComponents(), and skip expensive shortest-path work for vertices in different components.
• Dependency ordering: TopologicalSort::getVertices() for job/migration ordering; feed the result straight into a batch loop.
• Feasibility checks: Bipartitep::getBipartition() for two-sided matching and scheduling; Loop::hasLoop() and Tree\Undirected::isTree() as cheap guards before tree-only logic.
• Debugging visually: graphp/graphviz (optional) can render any Graph, including the MST returned by getTree() — invaluable when an algorithm "gives the wrong answer."

Gotchas and Tips

• Weights live in the weight attribute. Set it with setAttribute('weight', $n); algorithms read it through the graph's edge API. If you omit it, the default is treated as 1 — a silent source of wrong-but-plausible results. Assert weights are numeric at ingestion.
• Dijkstra and negative weights don't mix. It won't warn you meaningfully; it will produce suboptimal paths. Validate weight >= 0 up front or switch to Bellman-Ford.
• Unreachable targets return INF (a float), which poisons arithmetic into NAN. Always gate with is_finite($distance) before formatting or comparing.
• getPathTo() may return null/empty for disconnected vertices. Guard the call site; don't assume an array you can foreach.
• Vertex identity is by getId(). Duplicate or null IDs collapse nodes in algorithm maps. Assign stable, unique IDs from your domain keys — never rely on auto-generated ordering.
• Algorithms cache. Mutating the graph after constructing new Dijkstra($graph) leaves you with stale results. Treat the graph as immutable per algorithm instance, or rebuild both together.
• Directed vs. undirected matters. Use createEdgeUndirected() only for genuinely symmetric costs; Dijkstra follows edge direction, so a one-way createEdgeDirected() will not be traversable backwards.
• Self-loops and multigraphs can distort Loop, spanning-tree, and path results. De-duplicate parallel edges (keep the cheapest) before running algorithms.
• Cycle handling in TopologicalSort is not forgiving — expect an exception or an incomplete/false result on cyclic input. Test with a deliberately cyclic fixture so you know which behavior your version gives.
• Bipartitep is spelled without the final "e" in the class name. Autocomplete will not save you.
• Complexity is real. FloydWarshall is O(V³) and materializes a full matrix — fine for hundreds of vertices, not thousands. For large sparse graphs, run Dijkstra from each source you care about instead.
• Maintenance signal: no release since February 2020. Pin the version, add an integration test that exercises your main algorithm against a known fixture, and be prepared to fork or vendor if PHP compatibility breaks. The algorithms themselves are small and self-contained, which makes patching tractable.
• Extension point: all algorithms share the base graph/dual-graph abstractions under Graphp\Algorithms\. Subclass there if you need a custom traversal, rather than reimplementing Dijkstra from scratch.