Graph Algorithms Laravel Package

Getting Started

Minimal Steps

1. Install the package and dependency:

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

2. Create a graph using nexus-scholar/graph-core:

   use NexusScholar\GraphCore\Graph;
   $graph = new Graph();
   $graph->addNode('node1');
   $graph->addNode('node2');
   $graph->addEdge('node1', 'node2', ['weight' => 5]);
   

3. Run a basic algorithm (e.g., PageRank):

   use Mbsoft\Graph\Algorithms\Centrality\PageRank;
   $pagerank = new PageRank();
   $scores = $pagerank->compute($graph);
   

First Use Case: Citation Network Analysis

// Load a citation graph (e.g., from a database or CSV)
$citationGraph = buildCitationGraphFromData();

// Compute author influence using PageRank
$pagerank = new PageRank(dampingFactor: 0.85);
$influenceScores = $pagerank->compute($citationGraph);

// Find shortest path between two papers (e.g., for "citation lineage")
$dijkstra = new Dijkstra();
$path = $dijkstra->find($citationGraph, 'paperA', 'paperB');

Implementation Patterns

Core Workflow: Algorithm Execution

1. Graph Preparation:

   • Use nexus-scholar/graph-core to build your graph (nodes/edges with attributes).
   • For large graphs, consider pre-indexing nodes for performance:

     $indexMap = new \Mbsoft\Graph\Algorithms\IndexMap($graph);
     $algorithmGraph = new \Mbsoft\Graph\Algorithms\AlgorithmGraph($graph, $indexMap);
     

2. Algorithm Execution:

   • Centrality: Compute node importance (e.g., PageRank for citation influence).

     $pagerank = new PageRank(maxIterations: 50);
     $scores = $pagerank->compute($graph);
     

   • Pathfinding: Find optimal routes (e.g., shortest citation path).

     $astar = new AStar(
         heuristicCallback: fn ($from, $to) => haversineDistance($from, $to),
     );
     $path = $astar->find($graph, 'start', 'end');
     

   • Components: Analyze graph structure (e.g., strongly connected components for fraud detection).

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

3. Result Handling:

   • Use typed value objects (e.g., PathResult, MstResult) for structured data.
   • Example: Extract nodes and cost from a path:

     if ($path instanceof PathResult) {
         $nodes = $path->nodes;
         $cost = $path->cost;
     }
     

Integration with Laravel

1. Service Container Binding:

   $this->app->bind(MultiPathFinder::class, function ($app) {
       return new MultiPathFinder(
           new AStar(heuristicCallback: $app['heuristic.callback']),
           new Dijkstra()
       );
   });
   

2. Job Queues for Heavy Computations:

   use Mbsoft\Graph\Algorithms\Centrality\PageRank;
   use Illuminate\Bus\Queueable;
   
   class ComputeInfluence implements ShouldQueue
   {
       use Queueable;
   
       public function handle() {
           $pagerank = new PageRank();
           $scores = $pagerank->compute($this->graph);
           $this->storeScores($scores);
       }
   }
   

3. API Responses:

   return response()->json([
       'path' => $path->nodes,
       'cost' => $path->cost,
       'nodes_visited' => count($path->nodes),
   ]);
   

Customization Patterns

1. Custom Weights for Pathfinding:

   $dijkstra = new Dijkstra(
       weightExtractor: fn ($attrs) => $attrs['custom_weight'] ?? 1.0
   );
   

2. Heuristic Functions for A*:

   $heuristic = fn ($from, $to) => sqrt(
       ($from['x'] - $to['x']) ** 2 + ($from['y'] - $to['y']) ** 2
   );
   $astar = new AStar($heuristic);
   

3. Post-Processing Results:

   $components = (new StronglyConnected())->findComponents($graph);
   $largestComponent = collect($components)->max(fn ($c) => count($c));
   

Gotchas and Tips

Pitfalls

1. Negative Weights:

   • Dijkstra throws an exception if negative weights are detected. Use Bellman-Ford for such cases.
   • Fix: Validate weights before execution:

     $edges = $graph->getEdges();
     foreach ($edges as $edge) {
         if ($edge['weight'] < 0) {
             throw new \InvalidArgumentException("Negative weights not allowed for Dijkstra.");
         }
     }
     

2. Disconnected Graphs:

   • Algorithms like MST or topological sort may return null or empty results.
   • Fix: Handle gracefully:

     $mst = (new MinimumSpanningTree())->compute($graph);
     if ($mst === null) {
         return response()->json(['error' => 'Graph is disconnected'], 400);
     }
     

3. Performance with Large Graphs:

   • The AlgorithmGraph proxy improves speed but requires O(n) memory for indexing.
   • Tip: Cache the IndexMap and AlgorithmGraph if running repeated operations:

     $indexMap = new IndexMap($graph);
     $algorithmGraph = new AlgorithmGraph($graph, $indexMap);
     // Reuse $algorithmGraph for multiple algorithm runs
     

4. String Node IDs:

   • The package assumes string node IDs. For numeric IDs, create a custom IndexMap or pre-process data.

5. Floating-Point Precision:

   • PageRank and other iterative algorithms may suffer from precision issues.
   • Tip: Adjust tolerance and maxIterations:

     $pagerank = new PageRank(tolerance: 1e-8, maxIterations: 200);
     

Debugging Tips

1. Log Intermediate States:

   $pagerank = new PageRank();
   $pagerank->setLogger($this->logger); // If supported
   $scores = $pagerank->compute($graph);
   

2. Visualize Graphs: Use graph-core's export methods to generate DOT files for debugging:

   $graph->toDot()->saveToFile('graph.dot');
   

3. Test with Fixtures: The package includes Pest fixtures. Reuse them for local testing:

   use Mbsoft\Graph\Algorithms\Tests\Fixtures\SampleGraph;
   $graph = SampleGraph::create();
   

Extension Points

1. Custom Algorithms: Implement interfaces like CentralityAlgorithmInterface to add new algorithms:

   class MyCentrality implements CentralityAlgorithmInterface {
       public function compute(GraphInterface $graph): array {
           // Custom logic
       }
   }
   

2. Graph Adapters: Create adapters to bridge graph-core with other graph libraries (e.g., jenssegers/agent):

   class LaravelGraphAdapter implements GraphInterface {
       // Delegate to Laravel's graph storage
   }
   

3. Event Hooks: Extend algorithms by overriding methods (e.g., add logging in AStar::find()).

Configuration Quirks

1. Default Parameters:

   • PageRank uses a damping factor of 0.85 by default (standard for web graphs).
   • Adjust for citation networks (e.g., 0.95 for higher "teleportation" probability).

2. Edge Attributes:

   • Pathfinding algorithms expect weights in edge attributes. Use null or 1.0 for unweighted edges:

     $graph->addEdge('a', 'b', ['weight' => null]); // Treated as unweighted
     

3. Cycle Detection:

   • Topological sort throws an exception on cycles. Catch it to handle gracefully:

     try {
         $order = (new TopologicalSort())->sort($graph);
     } catch (CycleDetectedException $e) {
         $order = null;
     }
     

Performance Optimization

1. Reuse AlgorithmGraph: Convert the graph to AlgorithmGraph once and reuse it:

   $indexMap = new IndexMap($graph);
   $algorithmGraph = new AlgorithmGraph($graph, $indexMap);
   
   $pager