PHPackages                             mbsoft31/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. mbsoft31/graph-algorithms

ActiveLibrary

mbsoft31/graph-algorithms
=========================

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

v1.0.0(7mo ago)027↓100%1MITPHPPHP ^8.2CI passing

Since Sep 26Pushed 7mo agoCompare

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

READMEChangelog (1)Dependencies (4)Versions (2)Used By (1)

mbsoft/graph-algorithms
=======================

[](#mbsoftgraph-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/1936fb4b7233d6068abd96d94677d5ba1989d50d3e08d23afa4895b27c0880b8/68747470733a2f2f696d672e736869656c64732e696f2f7061636b61676973742f762f6d62736f667433312f67726170682d616c676f726974686d732e7376673f7374796c653d666c61742d737175617265)](https://packagist.org/packages/mbsoft/graph-algorithms)[![GitHub Tests Action Status](https://camo.githubusercontent.com/2ee5141da12a68514d13f34c3f4bd9e0a199ec59b1694b341b9b380d7d7c73ea/68747470733a2f2f696d672e736869656c64732e696f2f6769746875622f616374696f6e732f776f726b666c6f772f7374617475732f6d62736f667433312f67726170682d616c676f726974686d732f63692e796d6c3f6272616e63683d6d61696e267374796c653d666c61742d737175617265)](https://github.com/mbsoft31/graph-algorithms/actions)[![Total Downloads](https://camo.githubusercontent.com/3f0e8ecaf1211170e903558973047afa165761884d6952a9d3879fbd7ae88858/68747470733a2f2f696d672e736869656c64732e696f2f7061636b61676973742f64742f6d62736f667433312f67726170682d616c676f726974686d732e7376673f7374796c653d666c61742d737175617265)](https://packagist.org/packages/mbsoft31/graph-algorithms)

A high-performance library of standard graph algorithms for PHP. This library provides efficient implementations of essential graph algorithms with clean APIs, comprehensive error handling, and performance optimizations for production use.

✨ Features
----------

[](#-features)

- ⚡ **High Performance**: Integer-indexed `AlgorithmGraph` proxy for O(1) adjacency operations
- 🎯 **Comprehensive Coverage**: Centrality, pathfinding, traversal, components, ordering, and MST algorithms
- 📊 **Centrality Analysis**: PageRank with damping and convergence, degree centrality with normalization
- 🛣️ **Smart Pathfinding**: Dijkstra and A\* with heuristic support and negative weight detection
- 🔍 **Graph Traversal**: BFS with `SplQueue` and iterative DFS to prevent stack overflow
- 🔗 **Component Analysis**: Tarjan's single-pass strongly connected components algorithm
- 📋 **Topological Ordering**: Kahn's algorithm with cycle detection and meaningful exceptions
- 🌲 **Minimum Spanning Tree**: Prim's algorithm with connectivity validation
- 🔒 **Type-Safe**: Leverages PHP 8.2+ features with strict typing and comprehensive contracts
- ✅ **Production Ready**: Extensive test coverage with canonical fixtures and edge case handling
- 🚀 **Zero External Dependencies**: Only depends on `mbsoft/graph-core`

📋 Requirements
--------------

[](#-requirements)

- PHP 8.2 or higher
- mbsoft/graph-core ^1.0

📦 Installation
--------------

[](#-installation)

Install via Composer:

```
composer require mbsoft/graph-algorithms
```

Here are the code snippets for each Quick Start and Advanced Features section:

🚀 Quick Start
-------------

[](#-quick-start)

### PageRank Centrality

[](#pagerank-centrality)

```
use Mbsoft\Graph\Algorithms\Centrality\PageRank;

// Create PageRank with custom parameters
$pagerank = new PageRank(
    dampingFactor: 0.85,    // Link-following probability
    maxIterations: 100,     // Maximum iterations
    tolerance: 1e-6         // Convergence threshold
);

// Compute centrality scores
$scores = $pagerank->compute($graph);
arsort($scores); // Sort by importance

// Results: ['nodeA' => 0.343, 'nodeB' => 0.289, 'nodeC' => 0.368]
foreach ($scores as $node => $importance) {
    echo "Node {$node}: " . round($importance, 3) . "\n";
}
```

### Shortest Path Finding

[](#shortest-path-finding)

```
use Mbsoft\Graph\Algorithms\Pathfinding\Dijkstra;
use Mbsoft\Graph\Algorithms\Pathfinding\AStar;

// Dijkstra's algorithm for guaranteed shortest path
$dijkstra = new Dijkstra();
$path = $dijkstra->find($graph, 'start', 'destination');

if ($path) {
    echo "Path: " . implode(' → ', $path->nodes) . "\n";
    echo "Total cost: " . $path->cost . "\n";
    echo "Hops: " . $path->edgeCount() . "\n";
}

// A* with heuristic for faster pathfinding
$astar = new AStar(
    heuristicCallback: fn($from, $to) => manhattanDistance($from, $to)
);
$fasterPath = $astar->find($graph, 'start', 'destination');
```

### Graph Traversal

[](#graph-traversal)

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

// Breadth-first search (level by level)
$bfs = new Bfs();
$bfsOrder = $bfs->traverse($graph, 'startNode');
echo "BFS: " . implode(' → ', $bfsOrder) . "\n";

// Depth-first search (go deep first)
$dfs = new Dfs();
$dfsOrder = $dfs->traverse($graph, 'startNode');
echo "DFS: " . implode(' → ', $dfsOrder) . "\n";

// Example output:
// BFS: A → B → C → D → E → F (breadth-first)
// DFS: A → B → D → F → C → E (depth-first)
```

### Component Analysis

[](#component-analysis)

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

// Find strongly connected components using Tarjan's algorithm
$scc = new StronglyConnected();
$components = $scc->findComponents($graph);

echo "Found " . count($components) . " strongly connected components:\n";
foreach ($components as $i => $component) {
    echo "Component " . ($i + 1) . ": [" . implode(', ', $component) . "]\n";
}

// Example output:
// Component 1: [A, B, C]
        $attrs['distance'] ?? 1.0
);

// Dynamic weight calculation based on node properties
$dynamicWeights = new Dijkstra(
    function(array $attrs, string $from, string $to) use ($graph): float {
        $fromElevation = $graph->nodeAttrs($from)['elevation'] ?? 0;
        $toElevation = $graph->nodeAttrs($to)['elevation'] ?? 0;
        $baseDistance = $attrs['distance'] ?? 1.0;

        // Add penalty for uphill movement
        $elevationPenalty = max(0, $toElevation - $fromElevation) * 0.1;
        return $baseDistance + $elevationPenalty;
    }
);
```

### Heuristic Functions

[](#heuristic-functions)

```
use Mbsoft\Graph\Algorithms\Pathfinding\AStar;

// Manhattan distance heuristic for grid-based pathfinding
$gridPathfinder = new AStar(
    heuristicCallback: function(string $from, string $to): float {
        [$x1, $y1] = explode(',', $from);
        [$x2, $y2] = explode(',', $to);
        return abs($x2 - $x1) + abs($y2 - $y1);
    }
);

// Euclidean distance for coordinate-based graphs
$coordinatePathfinder = new AStar(
    heuristicCallback: function(string $from, string $to) use ($coordinates): float {
        $fromCoord = $coordinates[$from];
        $toCoord = $coordinates[$to];
        return sqrt(
            pow($toCoord['x'] - $fromCoord['x'], 2) +
            pow($toCoord['y'] - $fromCoord['y'], 2)
        );
    }
);

// Zero heuristic (equivalent to Dijkstra)
$dijkstraEquivalent = new AStar(); // Default heuristic returns 0.0
```

### Convergence Control

[](#convergence-control)

```
use Mbsoft\Graph\Algorithms\Centrality\PageRank;

// Fast convergence for real-time applications
$fastPageRank = new PageRank(
    dampingFactor: 0.85,
    maxIterations: 50,      // Fewer iterations
    tolerance: 0.01         // Less precision, faster results
);

// High precision for research/analysis
$precisePageRank = new PageRank(
    dampingFactor: 0.85,
    maxIterations: 1000,    // More iterations allowed
    tolerance: 1e-8         // Higher precision
);

// Monitor convergence
$scores = $precisePageRank->compute($graph);
echo "PageRank converged with high precision\n";

// Different damping factors for different behaviors
$surfingPageRank = new PageRank(dampingFactor: 0.85); // Traditional web surfing
$explorationPageRank = new PageRank(dampingFactor: 0.5); // More random exploration
```

### Error Handling

[](#error-handling)

```
use Mbsoft\Graph\Algorithms\Pathfinding\Dijkstra;
use Mbsoft\Graph\Algorithms\Topological\TopologicalSort;
use Mbsoft\Graph\Algorithms\Topological\CycleDetectedException;
use Mbsoft\Graph\Algorithms\Mst\Prim;

// Handle negative weights in Dijkstra
try {
    $dijkstra = new Dijkstra();
    $path = $dijkstra->find($graphWithNegativeWeights, 'A', 'B');
} catch (InvalidArgumentException $e) {
    echo "Error: " . $e->getMessage() . "\n";
    echo "Use Bellman-Ford algorithm for negative weights\n";
}

// Handle cycles in topological sort
try {
    $topo = new TopologicalSort();
    $order = $topo->sort($cyclicGraph);
    echo "Valid ordering: " . implode(' → ', $order) . "\n";
} catch (CycleDetectedException $e) {
    echo "Cannot sort: Graph contains cycles!\n";
    // Alternative: Use strongly connected components to identify cycles
}

// Handle disconnected graphs in MST
$prim = new Prim();
$mst = $prim->findMst($disconnectedGraph);

if ($mst === null) {
    echo "Cannot create MST: Graph is not connected\n";
    echo "Consider finding MST for each connected component separately\n";
} else {
    echo "MST total weight: " . $mst->totalWeight . "\n";
}

// Handle unreachable nodes in pathfinding
$path = $dijkstra->find($graph, 'island1', 'island2');
if ($path === null) {
    echo "No path exists between the nodes\n";
    // Alternative: Check connected components first
}
```

These code snippets demonstrate practical usage patterns for each feature, showing both basic usage and real-world scenarios with proper error handling and parameter configuration.

🏗️ Architecture
---------------

[](#️-architecture)

### Core Strategy

[](#core-strategy)

**AlgorithmGraph Proxy Pattern**: All algorithms convert any `GraphInterface` to an optimized integer-indexed representation once, then perform all operations on fast adjacency lists.

### Interfaces

[](#interfaces)

- **`CentralityAlgorithmInterface`**: Common interface for centrality calculations
- **`PathfindingAlgorithmInterface`**: Standard pathfinding contract with `PathResult` return type
- **`TraversalAlgorithmInterface`**: Graph traversal operations

### Value Objects

[](#value-objects)

- **`PathResult`**: Immutable path representation with nodes, cost, and utility methods
- **`MstResult`**: MST result with edges, total weight, and connectivity information

### Performance Classes

[](#performance-classes)

- **`AlgorithmGraph`**: Internal proxy for integer-indexed graph operations
- **`IndexMap`**: Bidirectional string-to-integer mapping for node ID management

🧪 Testing
---------

[](#-testing)

Run the test suite with Pest:

```
composer test
```

Run static analysis with PHPStan:

```
composer stan
```

Run performance benchmarks:

```
composer bench
```

🎯 Use Cases
-----------

[](#-use-cases)

This library excels in:

- **Network Analysis**: Social network centrality, influence propagation, community detection
- **Route Planning**: GPS navigation, logistics optimization, shortest path queries
- **Dependency Resolution**: Package managers, build systems, task scheduling
- **Web Analytics**: PageRank-based ranking, link analysis, authority computation
- **Game Development**: Pathfinding AI, level connectivity, optimal route calculation
- **Data Pipeline**: Topological sorting for ETL processes, workflow orchestration
- **Infrastructure Planning**: Network design, minimal spanning trees, connectivity analysis

⚡ Performance Considerations
----------------------------

[](#-performance-considerations)

The library is optimized for high-performance graph processing:

### Integer-Indexed Operations

[](#integer-indexed-operations)

**AlgorithmGraph Conversion**: One-time O(V + E) conversion to integer indices enables O(1) adjacency lookups throughout algorithm execution.

### Efficient Data Structures

[](#efficient-data-structures)

- **BFS**: Uses `SplQueue` for FIFO operations without array shifting overhead
- **DFS**: Iterative implementation with `SplStack` prevents recursion depth limits
- **Dijkstra/A**\*: Handles stale priority queue entries without expensive decrease-key operations
- **Tarjan SCC**: Single-pass algorithm with optimal time complexity

### Memory Optimization

[](#memory-optimization)

**Lazy Predecessor Building**: Only constructs reverse adjacency lists when algorithms require them, saving memory for algorithms that only need forward traversal.

### Cache-Friendly Design

[](#cache-friendly-design)

**Parallel Adjacency Lists**: Neighbor and weight arrays stored in aligned structures for CPU cache efficiency.

### Benchmarks

[](#benchmarks)

Performance on a 1,000-node graph (100 iterations):

- PageRank convergence: ~5ms
- Dijkstra pathfinding: ~2ms
- BFS traversal: ~1ms
- Tarjan SCC: ~3ms

📚 Example Applications
----------------------

[](#-example-applications)

### Social Network Analysis

[](#social-network-analysis)

Identify influential users with PageRank, find shortest connection paths, and detect tightly-knit communities using strongly connected components.

### Supply Chain Optimization

[](#supply-chain-optimization)

Model supplier networks as graphs, find optimal routing with Dijkstra, ensure connectivity with MST algorithms, and identify critical dependencies.

### Web Crawling and SEO

[](#web-crawling-and-seo)

Implement PageRank for page authority, use BFS for site structure analysis, and apply topological sorting for sitemap generation.

### Game AI Pathfinding

[](#game-ai-pathfinding)

Integrate A\* with custom heuristics for character movement, use BFS for area exploration, and apply DFS for maze solving.

🤝 Contributing
--------------

[](#-contributing)

Contributions are welcome! Please feel free to submit a Pull Request.

1. Fork the repository
2. Create your feature branch (`git checkout -b feature/amazing-algorithm`)
3. Ensure tests pass (`composer test`)
4. Verify static analysis (`composer stan`)
5. Push to the branch (`git push origin feature/amazing-algorithm`)
6. Open a Pull Request

### Adding New Algorithms

[](#adding-new-algorithms)

Follow the established patterns:

- Create algorithm in appropriate category directory
- Implement relevant interface contract
- Use `AlgorithmGraph` proxy for performance
- Include comprehensive tests with fixtures
- Document time/space complexity

📝 License
---------

[](#-license)

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

🙏 Acknowledgments
-----------------

[](#-acknowledgments)

- Algorithm implementations inspired by CLRS "Introduction to Algorithms"
- Performance patterns from NetworkX (Python) and JGraphT (Java)
- Built with modern PHP 8.2+ features and best practices
- Tested with Pest PHP testing framework

📮 Support
---------

[](#-support)

For bugs and feature requests, please use the [GitHub issues page](https://github.com/mbsoft/graph-algorithms/issues).

For algorithm-specific questions or performance optimization discussions, include graph characteristics (node count, edge density, directedness) in your issue description.

🔗 See Also
----------

[](#-see-also)

- [mbsoft/graph-core](https://github.com/mbsoft/graph-core) - Core graph package that implement entities and exports to many graph plotting libraries formats.

###  Health Score

34

—

LowBetter than 77% of packages

Maintenance67

Regular maintenance activity

Popularity8

Limited adoption so far

Community8

Small or concentrated contributor base

Maturity47

Maturing project, gaining track record

 Bus Factor1

Top contributor holds 100% 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

Unknown

Total

1

Last Release

225d ago

### Community

Maintainers

![](https://www.gravatar.com/avatar/288f14daea877ea6b5b49d25bf1647f75eab2870b3e143e2a35b17a0666f1bd8?d=identicon)[mbsoft](/maintainers/mbsoft)

---

Top Contributors

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

###  Code Quality

TestsPest

Static AnalysisPHPStan

Type Coverage Yes

### Embed Badge

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

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

PHPackages © 2026

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