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:8 months ago
Show doc for...
Tokens:
Raw
### Install mbsoft/graph-algorithms using Composer

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

This command installs the mbsoft/graph-algorithms library using Composer, the dependency manager for PHP. Ensure Composer is installed and accessible in your environment.

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

--------------------------------

### Heuristic Functions for A*

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Demonstrates the implementation of various heuristic functions for the A* pathfinding algorithm. Examples include Manhattan distance for grid-based pathfinding, Euclidean distance for coordinate-based graphs, and a zero heuristic which makes A* behave like Dijkstra's algorithm.

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

```

--------------------------------

### PageRank Convergence Control

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Shows how to control the convergence of the PageRank algorithm by adjusting parameters like `maxIterations` and `tolerance`. Examples include configurations for fast convergence in real-time applications and high precision for research, as well as exploring different damping factors.

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

```

--------------------------------

### Find Shortest Paths using Dijkstra and A* in PHP

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Implements shortest pathfinding algorithms. Dijkstra's algorithm guarantees the shortest path, while A* uses a heuristic function (like Manhattan distance) for potentially faster results. Both methods take the graph, start node, and destination node as input, returning a path object with nodes and cost, or null if no path exists. Requires `Mbsoft\Graph\Algorithms\Pathfinding\Dijkstra` and `Mbsoft\Graph\Algorithms\Pathfinding\AStar`.

```php
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');
```

--------------------------------

### Perform Graph Traversal with BFS and DFS in PHP

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Provides implementations for Breadth-First Search (BFS) and Depth-First Search (DFS) graph traversal algorithms. BFS explores level by level using a queue, while DFS explores as deeply as possible using recursion or an explicit stack to prevent stack overflow. Both methods take a graph and a starting node, returning an ordered list of visited nodes. Requires `Mbsoft\Graph\Algorithms\Traversal\Bfs` and `Mbsoft\Graph\Algorithms\Traversal\Dfs`.

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

--------------------------------

### Contribute to the Project

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Steps for contributing to the graph-algorithms project, including forking the repository, creating feature branches, running tests and static analysis, and submitting a Pull Request.

```bash
git checkout -b feature/amazing-algorithm
composer test
composer stan
git push origin feature/amazing-algorithm
```

--------------------------------

### Run Test Suite with Pest

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Executes the project's test suite using the Pest testing framework. This command is essential for verifying the correctness of implemented algorithms and ensuring code quality.

```bash
composer test
```

--------------------------------

### Run Performance Benchmarks

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Executes performance benchmarks to measure the efficiency of graph algorithms. This is useful for understanding the library's performance characteristics under various conditions.

```bash
composer bench
```

--------------------------------

### Run Static Analysis with PHPStan

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Performs static code analysis using PHPStan to detect potential errors and improve code quality. This step helps in identifying bugs before runtime.

```bash
composer stan
```

--------------------------------

### Error Handling in Graph Algorithms

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Demonstrates robust error handling for common issues encountered in graph algorithms. This includes handling negative weights in Dijkstra's algorithm, detecting cycles in topological sort, managing disconnected graphs for MST computation, and identifying unreachable nodes during pathfinding.

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

```

--------------------------------

### Error Handling in Graph Algorithms (PHP)

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Illustrates comprehensive error handling in the graph algorithms library using specific exceptions for various failure modes. It covers handling negative weights in Dijkstra's algorithm, cycles in topological sort, invalid graph types for SCC, and disconnected graphs for Prim's algorithm.

```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";
}

```

--------------------------------

### A* Pathfinding with Heuristics in PHP

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Implements the A* pathfinding algorithm, which uses a heuristic function to estimate the distance to the goal for faster pathfinding. It can fall back to Dijkstra's behavior if no heuristic is provided. Supports custom heuristic callbacks, such as Manhattan or Euclidean distance.

```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));
    }
);

```

--------------------------------

### Custom Edge Weight Extraction for Dijkstra

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Illustrates how to customize Dijkstra's algorithm by providing specific callback functions to extract edge weights based on different attributes like 'travel_time' or 'distance'. It also shows dynamic weight calculation considering node properties such as elevation.

```php
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;
    }
);

```

--------------------------------

### Minimum Spanning Tree (Prim's Algorithm)

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Calculates the Minimum Spanning Tree (MST) for a connected, undirected, weighted graph using Prim's algorithm with a binary heap. It returns an object containing the total weight and edges of the MST, or null if the graph is disconnected. The time complexity is O(E log V). It supports custom weight extraction via a callback.

```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 using Peeling Algorithm

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Computes the k-core decomposition of a graph. 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. This implementation uses the peeling algorithm.

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

```

--------------------------------

### Find Strongly Connected Components (SCC) in PHP

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Implements Tarjan's algorithm to efficiently find strongly connected components (SCCs) in a directed graph. An SCC is a subgraph where every node is reachable from every other node within that subgraph. The algorithm takes a graph object and returns an array of arrays, where each inner array represents an SCC. Requires `Mbsoft\Graph\Algorithms\Components\StronglyConnected`.

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

--------------------------------

### Find Strongly Connected Components (Tarjan's Algorithm)

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Identifies all strongly connected components in a directed graph using Tarjan's single-pass algorithm. It requires a directed graph as input and has a time complexity of O(V + E). The output is an array of components, where each component is an array of node identifiers.

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

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Provides a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before v. It uses Kahn's algorithm and includes cycle detection, throwing a `CycleDetectedException` if the graph is not a DAG. The output is an array of node identifiers in topological order.

```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";
}
```

--------------------------------

### Depth-First Search (DFS) Traversal in PHP

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Implements an iterative Depth-First Search (DFS) traversal using a stack to avoid recursion depth limits. It explores as far as possible along each branch before backtracking. Time complexity is 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

```

--------------------------------

### Breadth-First Search (BFS) Traversal in PHP

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Performs a Breadth-First Search (BFS) traversal on a graph, visiting nodes level by level. It uses a queue to manage nodes to visit and returns the order in which nodes are visited. Time complexity is 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: []

```

--------------------------------

### Bellman-Ford Algorithm for Shortest Paths in PHP

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Implements the Bellman-Ford algorithm to find the shortest path from a single source to all other nodes in a weighted graph. It can handle negative edge weights and detect negative cycles. The time complexity is O(V*E).

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

```

--------------------------------

### Find Shortest Path using Dijkstra's Algorithm in PHP

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Implements Dijkstra's algorithm to find the shortest path between two nodes in a graph with non-negative edge weights. It returns a PathResult object containing the path nodes and total cost, or null if no path exists. It supports custom weight extraction via a callback.

```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";
}

```

--------------------------------

### Compute PageRank Centrality Scores in PHP

Source: https://github.com/mbsoft31/graph-algorithms/blob/main/README.md

Calculates PageRank centrality scores for nodes in a graph using configurable damping factor, maximum iterations, and tolerance for convergence. It takes a graph object as input and returns an associative array of scores, which can then be sorted by importance. Requires the `Mbsoft\Graph\Algorithms\Centrality\PageRank` class.

```php
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";
}
```

--------------------------------

### MstResult Value Object for MST Algorithms (PHP)

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Demonstrates the usage of the MstResult value object, which is returned by MST algorithms like Prim's. It holds the tree edges and the total weight of the Minimum Spanning Tree. The object is immutable and provides methods to access edge count and iterate through edges.

```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']);
}

```

--------------------------------

### PathResult Value Object for Pathfinding Algorithms

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

An immutable result object returned by pathfinding algorithms like Dijkstra, A*, and BellmanFord. It contains the path nodes and total cost, providing 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

```

--------------------------------

### Compute PageRank Centrality in PHP

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Calculates PageRank centrality scores for nodes in a directed graph. It uses an iterative power method with configurable parameters like damping factor, maximum iterations, and convergence tolerance. The output is a map of node names to their importance scores, normalized to 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

```

--------------------------------

### Calculate Degree Centrality in PHP

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Computes the in-degree, out-degree, or total degree centrality for each node in a graph. The calculation can be optionally normalized by dividing by the maximum possible degree (N-1). The time complexity is 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]);
}

```

--------------------------------

### Adamic-Adar Link Prediction

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

A link prediction algorithm that 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);
}

```

--------------------------------

### Common Neighbors Link Prediction

Source: https://context7.com/mbsoft31/graph-algorithms/llms.txt

Predicts potential links between nodes based on the number of common neighbors they share. Higher scores indicate a stronger likelihood of a connection forming. This is 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";
}

```
Tokens:
Raw