Graph Laravel Package

Getting Started

composer require clue/graph

The first surprise: the package is clue/graph, but every class lives under the Fhaculty\Graph namespace (it is a maintained fork of fhaculty/graph). Import Fhaculty\Graph\Graph, not Clue\Graph\Graph.

Minimal working example:

use Fhaculty\Graph\Graph;

$graph = new Graph();

$build  = $graph->createVertex('build');
$deploy = $graph->createVertex('deploy');

$edge = $build->createEdgeTo($deploy);   // directed build -> deploy
$edge->setWeight(10);
$edge->setAttribute('type', 'depends-on');

$graph->getVertex('deploy')
      ->setAttribute('label', 'Production deploy');

foreach ($graph->getVertices() as $vertex) {
    echo $vertex->getId(), PHP_EOL;
}

Where to look first:

• src/Graph.php — vertex/edge factories, whole-graph lookups (getVertex, hasVertex, getVertices, getEdges).
• src/Vertex.php — neighbor and edge accessors (getEdges, getEdgesOut, getEdgesIn, getVerticesEdgeTo, getVerticesEdgeFrom) plus setAttribute.
• src/Edge/Directed.php and src/Edge/Undirected.php — direction semantics, getWeight/setWeight.
• src/Set/Vertices.php and src/Set/Edges.php — the collection objects returned everywhere.
• src/Algorithm/ — Dijkstra, BFS/DFS, TopologicalSort, ConnectedComponents, spanning trees, max-flow. This is the real reason to use the package over hand-rolled arrays.

First use case to reach for: modeling a dependency or routing problem where you need shortest path, reachability, cycle detection, or topological ordering — not a general-purpose ORM.

Implementation Patterns

Decide directed vs. undirected before you write code. Mixing them later is painful.

// Directed
$graph->createEdgeDirected($a, $b);
$a->createEdgeTo($b);

// Undirected
$graph->createEdgeUndirected($a, $b);
$a->createEdge($b);

Prefer the explicit createEdgeDirected/createEdgeUndirected on Graph for clarity; the Vertex helpers are convenient inside loops.

Map domain IDs directly to vertex IDs. The graph's internal index is keyed by vertex ID, so using database IDs or slugs makes lookups O(1) and avoids a parallel map:

private function vertex(Graph $graph, int $id): Vertex
{
    return $graph->hasVertex($id)
        ? $graph->getVertex($id)
        : $graph->createVertex($id);
}

$graph = new Graph();
foreach ($tasks as $task) {
    $v = $this->vertex($graph, $task->id);
    $v->setAttribute('task', $task);       // or just store scalar fields
}
foreach ($dependencies as $dep) {
    $this->vertex($graph, $dep->task_id)
         ->createEdgeTo($this->vertex($graph, $dep->depends_on_id));
}

Use weights for cost, attributes for everything else. getWeight() defaults to 1, which makes unweighted shortest-path work "for free". Attributes are a loose key/value bag — use them for labels, colors, external IDs, but keep the graph shape itself in vertices and edges.

Algorithms are standalone objects. Instantiate with either the whole graph or a start vertex (check each constructor), then query:

use Fhaculty\Graph\Algorithm\ShortestPath\Dijkstra;
use Fhaculty\Graph\Algorithm\ShortestPath\BFS;
use Fhaculty\Graph\Algorithm\Search\BFS as SearchBFS;
use Fhaculty\Graph\Algorithm\TopologicalSort;

$dijkstra = new Dijkstra($graph);            // or new Dijkstra($startVertex)
$distance = $dijkstra->getDistance($target);
$edges    = $dijkstra->getPath($target);     // traversable path

$order = (new TopologicalSort($graph))->getVertices();

For unweighted graphs, BFS is cheaper than Dijkstra; for "can I reach X" questions, Search\BFS/Search\DFS with a start vertex gives you the visited set.

Wrap it in a small service, not a model. Graphs are transient computation artifacts. A GraphBuilder that takes Eloquent collections and returns a Graph, plus a GraphAnalyzer that runs algorithms, keeps the library out of your domain layer:

$this->app->bind(GraphBuilder::class, fn () => new GraphBuilder());

Cache or queue expensive builds. Rebuilding a graph per request is fine for hundreds of nodes, wasteful for thousands. Build it in a job and persist the derived answer (shortest path, ordering, component map), not the graph itself.

Export deliberately. There is no built-in serializer. For APIs, do $graph->getVertices()->getIds() plus an edge list of [startId, endId, weight]. For visualization, emit Graphviz DOT yourself (or use clue/graph-composer if you're specifically visualizing Composer packages).

Gotchas and Tips

• Namespace mismatch is the #1 onboarding friction. clue/graph ships Fhaculty\Graph\*. IDE autocomplete on Clue\Graph will find nothing.
• Low maintenance, last release 2021. Pin the constraint, run it against your target PHP version in CI, and treat upgrade risk as low-but-not-zero. Don't expect typed properties, enums, or modern static analysis support.
• getVertex() / getEdge() throw OutOfBoundsException on miss. Always guard with hasVertex() / hasEdge() in ingestion code.
• Duplicate IDs are not forgiving. createVertex() with an ID that already exists will not silently return the existing vertex; use the hasVertex() pattern above.
• getWeight() never returns null. It returns 1 when unset, so you can't distinguish "default" from "explicitly 1" — store your own attribute if that matters.
• Dijkstra assumes non-negative weights. Negative weights will produce wrong results, not an error. Validate on ingestion.
• Directional accessors are subtle on undirected edges. Undirected edges appear in both getEdgesOut() and getEdgesIn(); getEdges() returns everything. Use getEdgesOut() for "what can I go to" only if your graph is genuinely directed.
• Collections are objects, not arrays. Vertices and Edges support count(), iteration, getVector(), getIds(), and getVertexFirst(); don't pass them to array_map/array_filter directly.
• Attributes are untyped and unvalidated. Do not stash Eloquent models in them if you ever plan to serialize(), cache, or hand the graph to a queue — store IDs and rehydrate.
• Performance is "textbook", not tuned. Algorithms are clean implementations with straightforward data structures. Thousands of nodes are fine; millions are not. For hot paths, pre-index adjacency in a plain array and only use the graph classes for the algorithm itself.
• Extension points are limited. Graph, Vertex, and Edge factory methods return the base classes; subclassing to inject custom types is fragile. Prefer composition (a builder + analyzer service) over inheritance.
• Debugging tip: when an algorithm returns something unexpected, dump the shape first — $graph->getVertices()->getIds() and, per vertex, $v->getEdgesOut()->count() — most bugs are ingestion bugs (missing vertices, reversed edges), not algorithm bugs.