Graph Algorithms Laravel Package

Getting Started

Install the package via Composer (composer require mbsoft/graph-algorithms) and ensure mbsoft/graph-core ^1.0 is also present. Start with simple use cases like computing PageRank centrality or finding shortest paths using Dijkstra—both are demonstrated in the README with clear, minimal setup. Begin by constructing a graph using the mbsoft/graph-core package (the library’s only dependency), then instantiate an algorithm class (e.g., PageRank, Dijkstra) and call its compute() or find() method directly. No heavy configuration is required upfront—algorithms default to sensible values (e.g., damping factor 0.85 for PageRank), making prototyping quick and intuitive.

Implementation Patterns

Leverage the library’s strategy-based design by passing callbacks for custom weight extraction or heuristics (e.g., lambda functions to compute travel time or Euclidean distance). Use AlgorithmGraph implicitly—no manual conversion needed, but understand that algorithms internally convert your graph once for high-performance operations. Common patterns include:

• Hybrid pathfinding: Use AStar with a heuristic in grid-based games, fallback to Dijkstra when needed, and handle null paths via null checks or try/catch for unreachable targets.
• Error handling by algorithm type: Catch CycleDetectedException for topological sorts, handle null returns from Prim for disconnected graphs, and validate edge weights before running Dijkstra.
• Streaming/iterative analysis: Run multiple centrality/traversal passes incrementally (e.g., batch PageRank updates per region), exploiting the proxy’s reuse of internal integer mappings.
• Composition: Chain algorithms—e.g., use StronglyConnected to decompose a graph into SCCs, then apply TopologicalSort to the condensation DAG.

Gotchas and Tips

• Negative weights break Dijkstra silently unless validated: Always catch InvalidArgumentException or pre-check weights; fallback to Bellman-Ford (outside this package) if needed.
• MST returns null, not an exception, for disconnected graphs: Explicitly check for null before accessing totalWeight—this avoids unexpected Error exceptions.
• Heuristic consistency matters for A*: If your heuristic overestimates actual cost, A* may return suboptimal paths. Use monotonic heuristics (e.g., Euclidean, Manhattan) for correctness.
• Graph structure is key: Algorithms accept any GraphInterface, but performance relies on the internal AlgorithmGraph conversion. Avoid frequent graph recreations—reuse the base graph or batch operations.
• Memory vs. speed tradeoffs: BFS uses SplQueue (O(1) enqueue/dequeue) and DFS is iterative (prevents stack overflow), but large graphs may still strain memory—consider chunking for huge networks.
• Extension points: You can subclass algorithms to override defaults (e.g., custom convergence logging in PageRank) or implement new algorithms per the existing interfaces (PathfindingAlgorithmInterface, etc.).
• No built-in graph I/O: You’ll need external tools to load graphs (e.g., JSON, CSV), but the library assumes node IDs are strings and edge attributes are arrays—ensure your graph data aligns.