README

graph-algorithms is a PHP package of graph algorithms built on nexus-scholar/graph-core. It provides centrality, pathfinding, traversal, component analysis, topological ordering, and minimum-spanning-tree algorithms through typed, reusable APIs.

Role In Nexus Scholar

This package is the algorithm layer for Nexus Scholar citation-network analysis. graph-core owns graph storage and export primitives; graph-algorithms owns reusable graph computations; nexus-scholar/core applies those capabilities to scholarly workflows such as citation graphs, co-citation analysis, bibliographic coupling, snowballing, and review exports.

The package is generic enough to use outside research tooling, but its main public value is showing that Nexus Scholar's graph work is package-quality PHP, not only application code.

Features

• PageRank and degree centrality.
• Dijkstra and A* pathfinding.
• Breadth-first and depth-first traversal.
• Strongly connected components using Tarjan's algorithm.
• Topological sort with cycle detection.
• Minimum spanning tree support.
• Integer-indexed AlgorithmGraph proxy for efficient algorithm execution.
• Typed value objects such as PathResult and MstResult.
• Pest test coverage and canonical fixtures.

Requirements

• PHP 8.2+
• nexus-scholar/graph-core ^1.0

Installation

composer require nexus-scholar/graph-algorithms

Quick Start

PageRank

use Mbsoft\Graph\Algorithms\Centrality\PageRank;

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

$scores = $pagerank->compute($graph);
arsort($scores);

Shortest Path

use Mbsoft\Graph\Algorithms\Pathfinding\Dijkstra;

$dijkstra = new Dijkstra();
$path = $dijkstra->find($graph, 'start', 'destination');

if ($path !== null) {
    $nodes = $path->nodes;
    $cost = $path->cost;
}

A* With A Heuristic

use Mbsoft\Graph\Algorithms\Pathfinding\AStar;

$astar = new AStar(
    heuristicCallback: fn (string $from, string $to): float => manhattanDistance($from, $to),
);

$path = $astar->find($graph, 'start', 'destination');

Traversal

use Mbsoft\Graph\Algorithms\Traversal\Bfs;
use Mbsoft\Graph\Algorithms\Traversal\Dfs;

$bfsOrder = (new Bfs())->traverse($graph, 'startNode');
$dfsOrder = (new Dfs())->traverse($graph, 'startNode');

Strongly Connected Components

use Mbsoft\Graph\Algorithms\Components\StronglyConnected;

$components = (new StronglyConnected())->findComponents($graph);

Custom Weights

Pathfinding algorithms can read weights from arbitrary edge attributes:

use Mbsoft\Graph\Algorithms\Pathfinding\Dijkstra;

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

Error Handling

Algorithms expose failure states through typed returns or meaningful exceptions depending on the operation:

• Dijkstra rejects negative weights.
• Topological sort reports cycles.
• Minimum spanning tree returns no result for disconnected graphs.
• Pathfinding returns null when no path exists.

Architecture

• AlgorithmGraph: optimized integer-indexed graph proxy used during algorithm execution.
• IndexMap: bidirectional string-to-integer mapping.
• CentralityAlgorithmInterface: centrality algorithm contract.
• PathfindingAlgorithmInterface: pathfinding contract returning PathResult.
• TraversalAlgorithmInterface: traversal contract.
• PathResult: immutable shortest-path result.
• MstResult: minimum-spanning-tree result.

Testing

composer test
composer stan
composer bench

Use Cases

• Citation-network analysis.
• Scholarly influence and discovery graphs.
• Dependency resolution and build ordering.
• Workflow orchestration.
• Route planning and logistics.
• Infrastructure and network analysis.
• Game pathfinding and level connectivity.

See Also

• nexus-scholar/graph-core - core graph data structures, attributes, subgraph views, and exports.
• nexus-scholar/core - Nexus Scholar workflow engine that applies graph packages to scholarly review workflows.
• nexus-scholar/scholar-graph - legacy scholarly graph prototype that preceded the current graph packages.

License

This library is open-sourced software licensed under the MIT license.