README

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

⚡ 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

PHP 8.2 or higher
mbsoft/graph-core ^1.0

📦 Installation

Install via Composer:

composer require mbsoft/graph-algorithms

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

🚀 Quick Start

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

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

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

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]  <- These nodes can all reach each other
// Component 2: [D]        <- Isolated node
// Component 3: [E, F]     <- Another strongly connected pair

🔍 Advanced Features

Custom Weight Extraction

use Mbsoft\Graph\Algorithms\Pathfinding\Dijkstra;

// Extract weights from different edge attributes
$timeOptimized = new Dijkstra(
    fn(array $attrs, string $from, string $to): float => 
        $attrs['travel_time'] ?? 1.0
);

$distanceOptimized = new Dijkstra(
    fn(array $attrs, string $from, string $to): float => 
        $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

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

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

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

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

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

Value Objects

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

Performance Classes

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

🧪 Testing

Run the test suite with Pest:

composer test

Run static analysis with PHPStan:

composer stan

Run performance benchmarks:

composer bench

🎯 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

The library is optimized for high-performance graph processing:

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

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

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

Cache-Friendly Design

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

Benchmarks

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

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

📚 Example Applications

Social Network Analysis

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

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

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

Game AI Pathfinding

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

🤝 Contributing

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

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

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

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

🙏 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

For bugs and feature requests, please use the GitHub issues page.

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

🔗 See Also

mbsoft/graph-core - Core graph package that implement entities and exports to many graph plotting libraries formats.

mbsoft31 / graph-algorithms

Maintainers

Details