PHPackages                             nexus-scholar/graph-algorithms - PHPackages - PHPackages  [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register)

1. [Directory](/)
2. /
3. [Utility & Helpers](/categories/utility)
4. /
5. nexus-scholar/graph-algorithms

ActiveLibrary[Utility & Helpers](/categories/utility)

nexus-scholar/graph-algorithms
==============================

A high-performance library of standard graph algorithms for PHP.

v1.2.0(2w ago)0196↑267.3%MITPHPPHP ^8.2CI passing

Since Sep 26Pushed 1w agoCompare

[ Source](https://github.com/nexus-scholar/graph-algorithms)[ Packagist](https://packagist.org/packages/nexus-scholar/graph-algorithms)[ Docs](https://github.com/nexus-scholar/graph-algorithms)[ RSS](/packages/nexus-scholar-graph-algorithms/feed)WikiDiscussions main Synced 1w ago

READMEChangelog (3)Dependencies (5)Versions (4)Used By (0)

nexus-scholar/graph-algorithms
==============================

[](#nexus-scholargraph-algorithms)

[![PHP Version](https://camo.githubusercontent.com/962aced9b09d89716dbebf186ff899754a096ff1068b6b7988675c2d9fab9331/68747470733a2f2f696d672e736869656c64732e696f2f62616467652f7068702d253545382e322d626c75652e737667)](https://php.net)[![License](https://camo.githubusercontent.com/074b89bca64d3edc93a1db6c7e3b1636b874540ba91d66367c0e5e354c56d0ea/68747470733a2f2f696d672e736869656c64732e696f2f62616467652f6c6963656e73652d4d49542d627269676874677265656e2e737667)](LICENSE)[![Latest Version on Packagist](https://camo.githubusercontent.com/374308624b3801b6e36da1f28fac035acc034159e07508c8b6bbef4fe52221f3/68747470733a2f2f696d672e736869656c64732e696f2f7061636b61676973742f762f6e657875732d7363686f6c61722f67726170682d616c676f726974686d732e7376673f7374796c653d666c61742d737175617265)](https://packagist.org/packages/nexus-scholar/graph-algorithms)[![GitHub Tests Action Status](https://camo.githubusercontent.com/184a5fd0244e651073774ad6758b1fee831bdda5459530fe1aa0936f164c4295/68747470733a2f2f696d672e736869656c64732e696f2f6769746875622f616374696f6e732f776f726b666c6f772f7374617475732f6e657875732d7363686f6c61722f67726170682d616c676f726974686d732f63692e796d6c3f6272616e63683d6d61696e267374796c653d666c61742d737175617265)](https://github.com/nexus-scholar/graph-algorithms/actions)[![Total Downloads](https://camo.githubusercontent.com/25e9d7f43354800fce44f4b15c81c0314f79e311324c43105e61e5b4d42286a7/68747470733a2f2f696d672e736869656c64732e696f2f7061636b61676973742f64742f6e657875732d7363686f6c61722f67726170682d616c676f726974686d732e7376673f7374796c653d666c61742d737175617265)](https://packagist.org/packages/nexus-scholar/graph-algorithms)

`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
---------------------

[](#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
--------

[](#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
------------

[](#requirements)

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

Installation
------------

[](#installation)

```
composer require nexus-scholar/graph-algorithms
```

Quick Start
-----------

[](#quick-start)

### PageRank

[](#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

[](#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

[](#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

[](#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

[](#strongly-connected-components)

```
use Mbsoft\Graph\Algorithms\Components\StronglyConnected;

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

Custom Weights
--------------

[](#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
--------------

[](#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
------------

[](#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
-------

[](#testing)

```
composer test
composer stan
composer bench
```

Use Cases
---------

[](#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
--------

[](#see-also)

- [nexus-scholar/graph-core](https://github.com/nexus-scholar/graph-core) - core graph data structures, attributes, subgraph views, and exports.
- [nexus-scholar/core](https://github.com/nexus-scholar/core) - Nexus Scholar workflow engine that applies graph packages to scholarly review workflows.
- [nexus-scholar/scholar-graph](https://github.com/nexus-scholar/scholar-graph) - legacy scholarly graph prototype that preceded the current graph packages.

License
-------

[](#license)

This library is open-sourced software licensed under the [MIT license](LICENSE).

###  Health Score

45

—

FairBetter than 91% of packages

Maintenance97

Actively maintained with recent releases

Popularity16

Limited adoption so far

Community8

Small or concentrated contributor base

Maturity50

Maturing project, gaining track record

 Bus Factor1

Top contributor holds 50% of commits — single point of failure

How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window.

**Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores.

**Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement.

**Maturity (30%)** — Project age, version count, PHP version support, and release stability.

###  Release Activity

Cadence

Every ~119 days

Total

3

Last Release

18d ago

### Community

Maintainers

![](https://www.gravatar.com/avatar/2d86d4859cd0f7e935dc056ca1155f5842ac8c590ebe8481d3051feb339885d7?d=identicon)[nexus-scholar](/maintainers/nexus-scholar)

---

Top Contributors

[![mbsoft31](https://avatars.githubusercontent.com/u/14237661?v=4)](https://github.com/mbsoft31 "mbsoft31 (12 commits)")[![nexus-scholar](https://avatars.githubusercontent.com/u/233639653?v=4)](https://github.com/nexus-scholar "nexus-scholar (12 commits)")

---

Tags

networkgraphalgorithmsPagerankpathfindingcentrality

###  Code Quality

TestsPest

Static AnalysisPHPStan

Code StyleLaravel Pint

Type Coverage Yes

### Embed Badge

![Health badge](/badges/nexus-scholar-graph-algorithms/health.svg)

```
[![Health](https://phpackages.com/badges/nexus-scholar-graph-algorithms/health.svg)](https://phpackages.com/packages/nexus-scholar-graph-algorithms)
```

###  Alternatives

[clue/graph

GraPHP is the mathematical graph/network library written in PHP.

7144.4M43](/packages/clue-graph)[novus/nvd3

A reusable charting library written in d3.js

7.2k212.6k2](/packages/novus-nvd3)[graphp/graph

GraPHP is the mathematical graph/network library written in PHP.

714305.2k4](/packages/graphp-graph)[mlocati/ip-lib

Handle IPv4, IPv6 addresses and ranges

3127.0M58](/packages/mlocati-ip-lib)[s1lentium/iptools

PHP Library for manipulating network addresses (IPv4 and IPv6)

2326.5M27](/packages/s1lentium-iptools)[amenadiel/jpgraph

Composer Friendly, full refactor of JpGraph, library to make graphs and charts

1532.3M7](/packages/amenadiel-jpgraph)

PHPackages © 2026

[Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)