Mbsoft Graph Algorithms (mbsoft31/graph-algorithms)

Mbsoft Graph Algorithms

https://github.com/mbsoft31/graph-algorithms
Admin
A high-performance PHP library providing efficient implementations of essential graph algorithms...

Tokens:12,560
Snippets:79
Trust Score:5.9
Update:1 month ago
Show doc for...
Context Summary (auto-generated)
Raw
# mbsoft/graph-algorithms

A high-performance PHP library providing efficient implementations of standard graph algorithms. Built for PHP 8.2+ with strict typing, this library offers production-ready solutions for centrality analysis, pathfinding, traversal, component detection, topological ordering, minimum spanning trees, and link prediction with clean APIs and comprehensive error handling.

The library uses an optimized `AlgorithmGraph` proxy pattern that converts any `GraphInterface` to integer-indexed representations for O(1) adjacency operations. It depends only on `mbsoft/graph-core` and provides extensive algorithm coverage including PageRank, Dijkstra, A*, BFS, DFS, Tarjan's SCC, Kahn's topological sort, Prim's MST, and several link prediction algorithms.

## Installation

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

## PageRank Centrality

Computes the PageRank centrality scores for all nodes in a graph using iterative power method with configurable damping factor, maximum iterations, and convergence tolerance. Handles dangling nodes (nodes with no outgoing edges) and returns normalized scores that sum to 1.

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

// Create a directed graph
$graph = new Graph(directed: true);
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addNode('D');
$graph->addEdge('A', 'B');
$graph->addEdge('A', 'C');
$graph->addEdge('B', 'C');
$graph->addEdge('C', 'A');
$graph->addEdge('D', 'C');

// Configure PageRank parameters
$pagerank = new PageRank(
    dampingFactor: 0.85,    // Probability of following a link (vs random jump)
    maxIterations: 100,     // Maximum iterations before stopping
    tolerance: 1e-6         // Convergence threshold (L1 norm)
);

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

foreach ($scores as $node => $importance) {
    echo sprintf("Node %s: %.4f\n", $node, $importance);
}
// Output:
// Node C: 0.3908
// Node A: 0.2470
// Node B: 0.2085
// Node D: 0.1537
```

## Degree Centrality

Calculates in-degree, out-degree, or total degree centrality for each node in a graph. Supports optional normalization by dividing by the maximum possible degree (N-1). Time complexity O(V + E).

```php
use Mbsoft\Graph\Algorithms\Centrality\DegreeCentrality;
use Mbsoft\Graph\Domain\Graph;

$graph = new Graph(directed: true);
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addEdge('A', 'B');
$graph->addEdge('A', 'C');
$graph->addEdge('B', 'C');

// In-degree: count of incoming edges
$inDegree = new DegreeCentrality(DegreeCentrality::IN_DEGREE);
$inScores = $inDegree->compute($graph);
// ['A' => 0, 'B' => 1, 'C' => 2]

// Out-degree: count of outgoing edges
$outDegree = new DegreeCentrality(DegreeCentrality::OUT_DEGREE);
$outScores = $outDegree->compute($graph);
// ['A' => 2, 'B' => 1, 'C' => 0]

// Total degree with normalization
$totalDegree = new DegreeCentrality(
    mode: DegreeCentrality::TOTAL_DEGREE,
    normalized: true
);
$normalizedScores = $totalDegree->compute($graph);

foreach ($inScores as $node => $score) {
    echo sprintf("Node %s: in=%d, out=%d\n",
        $node, $inScores[$node], $outScores[$node]);
}
```

## Dijkstra's Shortest Path

Finds the shortest path between two nodes using Dijkstra's algorithm with a priority queue. Requires non-negative edge weights. Returns a `PathResult` object containing the path nodes and total cost, or null if no path exists.

```php
use Mbsoft\Graph\Algorithms\Pathfinding\Dijkstra;
use Mbsoft\Graph\Domain\Graph;

$graph = new Graph(directed: true);
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addNode('D');
$graph->addEdge('A', 'B', ['weight' => 2.0]);
$graph->addEdge('A', 'C', ['weight' => 5.0]);
$graph->addEdge('B', 'C', ['weight' => 1.0]);
$graph->addEdge('B', 'D', ['weight' => 4.0]);
$graph->addEdge('C', 'D', ['weight' => 1.0]);

// Default weight extraction from 'weight' attribute
$dijkstra = new Dijkstra();
$path = $dijkstra->find($graph, 'A', 'D');

if ($path !== null) {
    echo "Path: " . implode(' -> ', $path->nodes) . "\n";  // A -> B -> C -> D
    echo "Cost: " . $path->cost . "\n";                     // 4.0
    echo "Edges: " . $path->edgeCount() . "\n";             // 3
}

// Custom weight extraction callback
$customDijkstra = new Dijkstra(
    weightCallback: fn(array $attrs, string $from, string $to): float =>
        $attrs['travel_time'] ?? 1.0
);

// Handle unreachable nodes
$unreachable = $dijkstra->find($graph, 'D', 'A');
if ($unreachable === null) {
    echo "No path exists from D to A\n";
}
```

## A* Pathfinding

A* algorithm with heuristic function for faster goal-directed pathfinding. The heuristic estimates the distance from any node to the goal. Falls back to Dijkstra behavior when no heuristic is provided.

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

$graph = new Graph(directed: false);
// Grid-based graph with coordinates as node IDs
foreach (['0,0', '0,1', '1,0', '1,1', '2,0', '2,1'] as $node) {
    $graph->addNode($node);
}
$graph->addEdge('0,0', '0,1', ['weight' => 1.0]);
$graph->addEdge('0,0', '1,0', ['weight' => 1.0]);
$graph->addEdge('0,1', '1,1', ['weight' => 1.0]);
$graph->addEdge('1,0', '1,1', ['weight' => 1.0]);
$graph->addEdge('1,0', '2,0', ['weight' => 1.0]);
$graph->addEdge('1,1', '2,1', ['weight' => 1.0]);
$graph->addEdge('2,0', '2,1', ['weight' => 1.0]);

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

$path = $astar->find($graph, '0,0', '2,1');

if ($path !== null) {
    echo "A* Path: " . implode(' -> ', $path->nodes) . "\n";
    echo "Cost: " . $path->cost . "\n";
}

// Euclidean distance heuristic for coordinate graphs
$euclideanAStar = new AStar(
    heuristicCallback: function (string $from, string $to): float {
        [$x1, $y1] = explode(',', $from);
        [$x2, $y2] = explode(',', $to);
        return sqrt(pow((int)$x2 - (int)$x1, 2) + pow((int)$y2 - (int)$y1, 2));
    }
);
```

## Bellman-Ford Algorithm

Single-source shortest path algorithm that handles negative edge weights and detects negative cycles. Time complexity O(V*E), slower than Dijkstra but more versatile.

```php
use Mbsoft\Graph\Algorithms\Pathfinding\BellmanFord;
use Mbsoft\Graph\Domain\Graph;
use InvalidArgumentException;

$graph = new Graph(directed: true);
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addEdge('A', 'B', ['weight' => 4.0]);
$graph->addEdge('A', 'C', ['weight' => 2.0]);
$graph->addEdge('C', 'B', ['weight' => -1.0]);  // Negative weight OK

$bellmanFord = new BellmanFord();
$path = $bellmanFord->find($graph, 'A', 'B');

if ($path !== null) {
    echo "Path cost: " . $path->cost . "\n";  // 1.0 (via C)
}

// Negative cycle detection
try {
    $cyclicGraph = new Graph(directed: true);
    $cyclicGraph->addNode('X');
    $cyclicGraph->addNode('Y');
    $cyclicGraph->addEdge('X', 'Y', ['weight' => -2.0]);
    $cyclicGraph->addEdge('Y', 'X', ['weight' => -1.0]);

    $bellmanFord->find($cyclicGraph, 'X', 'Y');
} catch (InvalidArgumentException $e) {
    echo "Error: " . $e->getMessage() . "\n";  // Graph contains negative cycle
}
```

## Breadth-First Search (BFS)

Level-by-level graph traversal using a queue. Returns nodes in the order they are visited, exploring all neighbors at the current depth before moving to the next level. Time complexity O(V + E).

```php
use Mbsoft\Graph\Algorithms\Traversal\Bfs;
use Mbsoft\Graph\Domain\Graph;

$graph = new Graph(directed: true);
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addNode('D');
$graph->addNode('E');
$graph->addEdge('A', 'B');
$graph->addEdge('A', 'C');
$graph->addEdge('B', 'D');
$graph->addEdge('C', 'D');
$graph->addEdge('D', 'E');

$bfs = new Bfs();
$order = $bfs->traverse($graph, 'A');

echo "BFS Order: " . implode(' -> ', $order) . "\n";
// Output: A -> B -> C -> D -> E

// Traversal from different starting points
foreach (['B', 'C', 'D'] as $start) {
    $result = $bfs->traverse($graph, $start);
    echo "From $start: " . implode(' -> ', $result) . "\n";
}

// Non-existent node returns empty array
$empty = $bfs->traverse($graph, 'Z');
// Returns: []
```

## Depth-First Search (DFS)

Iterative depth-first traversal using a stack to prevent recursion depth limits. Explores as far as possible along each branch before backtracking. Time complexity O(V + E).

```php
use Mbsoft\Graph\Algorithms\Traversal\Dfs;
use Mbsoft\Graph\Domain\Graph;

$graph = new Graph(directed: true);
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addNode('D');
$graph->addNode('E');
$graph->addEdge('A', 'B');
$graph->addEdge('A', 'C');
$graph->addEdge('B', 'D');
$graph->addEdge('C', 'E');

$dfs = new Dfs();
$order = $dfs->traverse($graph, 'A');

echo "DFS Order: " . implode(' -> ', $order) . "\n";
// Output: A -> B -> D -> C -> E (explores depth-first)

// Compare BFS vs DFS
use Mbsoft\Graph\Algorithms\Traversal\Bfs;
$bfs = new Bfs();

echo "BFS: " . implode(' -> ', $bfs->traverse($graph, 'A')) . "\n";  // A -> B -> C -> D -> E
echo "DFS: " . implode(' -> ', $dfs->traverse($graph, 'A')) . "\n";  // A -> B -> D -> C -> E
```

## Strongly Connected Components (Tarjan's Algorithm)

Finds all strongly connected components in a directed graph using Tarjan's single-pass algorithm. A strongly connected component is a maximal set of vertices where every vertex is reachable from every other vertex. Time complexity O(V + E).

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

$graph = new Graph(directed: true);
// Create a graph with multiple SCCs
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addNode('D');
$graph->addNode('E');
// SCC 1: A <-> B <-> C (cycle)
$graph->addEdge('A', 'B');
$graph->addEdge('B', 'C');
$graph->addEdge('C', 'A');
// SCC 2: D <-> E (cycle)
$graph->addEdge('D', 'E');
$graph->addEdge('E', 'D');
// Connection between SCCs (one-way)
$graph->addEdge('C', 'D');

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

echo "Found " . count($components) . " strongly connected components:\n";
foreach ($components as $i => $component) {
    echo sprintf("  Component %d: [%s]\n", $i + 1, implode(', ', $component));
}
// Output:
// Found 2 strongly connected components:
//   Component 1: [D, E]
//   Component 2: [A, B, C]

// Throws InvalidArgumentException for undirected graphs
try {
    $undirected = new Graph(directed: false);
    $scc->findComponents($undirected);
} catch (\InvalidArgumentException $e) {
    echo $e->getMessage();  // Strongly connected components require a directed graph
}
```

## Topological Sort (Kahn's Algorithm)

Returns a linear ordering of vertices such that for every directed edge (u, v), vertex u comes before v. Uses Kahn's algorithm with cycle detection. Requires a directed acyclic graph (DAG).

```php
use Mbsoft\Graph\Algorithms\Topological\TopologicalSort;
use Mbsoft\Graph\Algorithms\Topological\CycleDetectedException;
use Mbsoft\Graph\Domain\Graph;

// Dependency graph (task dependencies)
$graph = new Graph(directed: true);
$graph->addNode('install');
$graph->addNode('configure');
$graph->addNode('build');
$graph->addNode('test');
$graph->addNode('deploy');
$graph->addEdge('install', 'configure');
$graph->addEdge('configure', 'build');
$graph->addEdge('build', 'test');
$graph->addEdge('test', 'deploy');
$graph->addEdge('install', 'build');  // Alternative path

$topo = new TopologicalSort();
$order = $topo->sort($graph);

echo "Execution order: " . implode(' -> ', $order) . "\n";
// Output: install -> configure -> build -> test -> deploy

// Cycle detection
try {
    $cyclicGraph = new Graph(directed: true);
    $cyclicGraph->addNode('A');
    $cyclicGraph->addNode('B');
    $cyclicGraph->addNode('C');
    $cyclicGraph->addEdge('A', 'B');
    $cyclicGraph->addEdge('B', 'C');
    $cyclicGraph->addEdge('C', 'A');  // Creates cycle

    $topo->sort($cyclicGraph);
} catch (CycleDetectedException $e) {
    echo "Cannot sort: Graph contains cycles!\n";
}
```

## Minimum Spanning Tree (Prim's Algorithm)

Finds the minimum spanning tree of a connected, undirected, weighted graph using Prim's algorithm with a binary heap. Returns null if the graph is disconnected. Time complexity O(E log V).

```php
use Mbsoft\Graph\Algorithms\Mst\Prim;
use Mbsoft\Graph\Domain\Graph;

$graph = new Graph(directed: false);
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addNode('D');
$graph->addEdge('A', 'B', ['weight' => 2.0]);
$graph->addEdge('A', 'C', ['weight' => 3.0]);
$graph->addEdge('B', 'C', ['weight' => 1.0]);
$graph->addEdge('B', 'D', ['weight' => 4.0]);
$graph->addEdge('C', 'D', ['weight' => 2.0]);

$prim = new Prim();
$mst = $prim->findMst($graph);

if ($mst !== null) {
    echo "MST total weight: " . $mst->totalWeight . "\n";  // 5.0
    echo "MST edges:\n";
    foreach ($mst->edges as $edge) {
        echo sprintf("  %s -- %s (weight: %.1f)\n",
            $edge['from'], $edge['to'], $edge['weight']);
    }
    echo "Edge count: " . $mst->edgeCount() . "\n";  // 3 (N-1 edges)
}

// Custom weight extraction
$customPrim = new Prim(
    weightCallback: fn(array $attrs): float => $attrs['distance'] ?? 1.0
);

// Disconnected graph returns null
$disconnected = new Graph(directed: false);
$disconnected->addNode('X');
$disconnected->addNode('Y');  // No edge between X and Y
$result = $prim->findMst($disconnected);
// Returns: null
```

## K-Core Decomposition

Computes the k-core decomposition of a graph using the peeling algorithm. The core number of a vertex is the largest k such that the vertex exists in a subgraph where all vertices have at least k neighbors.

```php
use Mbsoft\Graph\Algorithms\Decomposition\KCore;
use Mbsoft\Graph\Domain\Graph;

$graph = new Graph(directed: false);
// Create a graph with varying connectivity
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addNode('D');
$graph->addNode('E');
// Dense core: A-B-C-D all connected
$graph->addEdge('A', 'B');
$graph->addEdge('A', 'C');
$graph->addEdge('A', 'D');
$graph->addEdge('B', 'C');
$graph->addEdge('B', 'D');
$graph->addEdge('C', 'D');
// Peripheral node E connected only to A
$graph->addEdge('A', 'E');

$kcore = new KCore();
$coreNumbers = $kcore->compute($graph);

foreach ($coreNumbers as $node => $coreNumber) {
    echo sprintf("Node %s: core number = %d\n", $node, $coreNumber);
}
// Output:
// Node E: core number = 1  (only 1 neighbor)
// Node A: core number = 3  (part of 3-core with B,C,D)
// Node B: core number = 3
// Node C: core number = 3
// Node D: core number = 3

// Filter nodes by minimum core number
$core2Plus = array_filter($coreNumbers, fn($k) => $k >= 2);
```

## Common Neighbors Link Prediction

Predicts potential links between nodes based on the number of common neighbors they share. Higher scores indicate a stronger likelihood of a connection forming. Useful for social network friend suggestions.

```php
use Mbsoft\Graph\Algorithms\LinkPrediction\CommonNeighbors;
use Mbsoft\Graph\Domain\Graph;

$graph = new Graph(directed: false);
$graph->addNode('Alice');
$graph->addNode('Bob');
$graph->addNode('Carol');
$graph->addNode('Dave');
$graph->addNode('Eve');
// Social network connections
$graph->addEdge('Alice', 'Bob');
$graph->addEdge('Alice', 'Carol');
$graph->addEdge('Bob', 'Carol');
$graph->addEdge('Bob', 'Dave');
$graph->addEdge('Carol', 'Dave');
// Eve is isolated from Dave

$cn = new CommonNeighbors();

// Score between two specific nodes
$score = $cn->score($graph, 'Alice', 'Dave');
echo "Alice-Dave common neighbors: $score\n";  // 2 (Bob and Carol)

// Top-k recommendations from a node
$recommendations = $cn->scoresFrom($graph, 'Eve', k: 10);
foreach ($recommendations as $node => $score) {
    echo "Recommend $node to Eve (score: $score)\n";
}
```

## Adamic-Adar Link Prediction

Similar to Common Neighbors but weights shared neighbors by their rarity (1/log(degree)). Neighbors with fewer connections contribute more to the score, capturing the intuition that a shared rare friend is more significant than a shared popular one.

```php
use Mbsoft\Graph\Algorithms\LinkPrediction\AdamicAdar;
use Mbsoft\Graph\Domain\Graph;

$graph = new Graph(directed: false);
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addNode('D');
$graph->addNode('Hub');  // High-degree hub node
// Hub connects to everyone
$graph->addEdge('Hub', 'A');
$graph->addEdge('Hub', 'B');
$graph->addEdge('Hub', 'C');
$graph->addEdge('Hub', 'D');
// C is a rare shared neighbor between A and B
$graph->addEdge('A', 'C');
$graph->addEdge('B', 'C');

$aa = new AdamicAdar();

// Adamic-Adar weights C higher than Hub because C has fewer connections
$score = $aa->score($graph, 'A', 'B');
echo sprintf("A-B Adamic-Adar score: %.4f\n", $score);

// Get top recommendations
$recommendations = $aa->scoresFrom($graph, 'D', k: 5);
foreach ($recommendations as $node => $score) {
    echo sprintf("Recommend %s to D (AA score: %.4f)\n", $node, $score);
}
```

## PathResult Value Object

Immutable result object returned by pathfinding algorithms containing the path nodes and total cost. Provides utility methods for path analysis.

```php
use Mbsoft\Graph\Algorithms\Pathfinding\PathResult;

// PathResult is returned by Dijkstra, A*, and BellmanFord
$path = new PathResult(
    nodes: ['A', 'B', 'C', 'D'],
    cost: 5.5
);

echo "Nodes: " . implode(' -> ', $path->nodes) . "\n";  // A -> B -> C -> D
echo "Total cost: " . $path->cost . "\n";               // 5.5
echo "Path length: " . $path->length() . "\n";          // 4 nodes
echo "Edge count: " . $path->edgeCount() . "\n";        // 3 edges
echo "Start node: " . $path->start() . "\n";            // A
echo "End node: " . $path->end() . "\n";                // D
echo "Is valid: " . ($path->isValid() ? 'yes' : 'no') . "\n";  // yes
```

## MstResult Value Object

Immutable result object returned by MST algorithms containing the tree edges and total weight.

```php
use Mbsoft\Graph\Algorithms\Mst\MstResult;

// MstResult is returned by Prim's algorithm
$mst = new MstResult(
    edges: [
        ['from' => 'A', 'to' => 'B', 'weight' => 2.0],
        ['from' => 'B', 'to' => 'C', 'weight' => 1.0],
        ['from' => 'C', 'to' => 'D', 'weight' => 3.0],
    ],
    totalWeight: 6.0
);

echo "Total MST weight: " . $mst->totalWeight . "\n";  // 6.0
echo "Number of edges: " . $mst->edgeCount() . "\n";   // 3

foreach ($mst->edges as $edge) {
    echo sprintf("%s -- %s (%.1f)\n",
        $edge['from'], $edge['to'], $edge['weight']);
}
```

## Error Handling

The library provides comprehensive error handling with specific exceptions for different failure modes including negative weights, cycles, and invalid graph types.

```php
use Mbsoft\Graph\Algorithms\Pathfinding\Dijkstra;
use Mbsoft\Graph\Algorithms\Topological\TopologicalSort;
use Mbsoft\Graph\Algorithms\Topological\CycleDetectedException;
use Mbsoft\Graph\Algorithms\Components\StronglyConnected;
use Mbsoft\Graph\Algorithms\Mst\Prim;
use Mbsoft\Graph\Domain\Graph;
use InvalidArgumentException;

// Dijkstra: negative weights throw InvalidArgumentException
try {
    $graph = new Graph(directed: true);
    $graph->addNode('A');
    $graph->addNode('B');
    $graph->addEdge('A', 'B', ['weight' => -1.0]);

    $dijkstra = new Dijkstra();
    $dijkstra->find($graph, 'A', 'B');
} catch (InvalidArgumentException $e) {
    echo "Dijkstra error: " . $e->getMessage() . "\n";
    // Use Bellman-Ford for negative weights instead
}

// TopologicalSort: cycles throw CycleDetectedException
try {
    $cyclic = new Graph(directed: true);
    $cyclic->addNode('A');
    $cyclic->addNode('B');
    $cyclic->addEdge('A', 'B');
    $cyclic->addEdge('B', 'A');

    $topo = new TopologicalSort();
    $topo->sort($cyclic);
} catch (CycleDetectedException $e) {
    echo "Cannot sort: graph has cycles\n";
}

// SCC: requires directed graph
try {
    $undirected = new Graph(directed: false);
    $scc = new StronglyConnected();
    $scc->findComponents($undirected);
} catch (InvalidArgumentException $e) {
    echo "SCC error: " . $e->getMessage() . "\n";
}

// Prim: requires undirected graph, returns null for disconnected
$prim = new Prim();
$disconnected = new Graph(directed: false);
$disconnected->addNode('A');
$disconnected->addNode('B');  // No edge
$result = $prim->findMst($disconnected);
if ($result === null) {
    echo "Graph is not connected\n";
}
```

## Summary

This library excels in network analysis scenarios including social network centrality analysis, influence propagation modeling, and community detection. It's ideal for route planning applications such as GPS navigation, logistics optimization, and game AI pathfinding. The dependency resolution algorithms support package managers, build systems, and task scheduling workflows. Web analytics use cases include PageRank-based ranking and link analysis.

Integration follows a consistent pattern: instantiate algorithm classes with optional configuration, call the primary method (`compute`, `find`, `traverse`, `sort`, `findComponents`, `findMst`), and handle the typed return value. All algorithms accept any implementation of `GraphInterface` from the `mbsoft/graph-core` package, enabling seamless integration with existing graph structures. The library uses immutable value objects for results, ensuring thread-safe usage in concurrent applications.