actived / graphphp
A PHP graph theory package.
Requires
- php: >=8.0
Requires (Dev)
- phpunit/phpunit: ^10.3
README
A PHP graph theory package that provides structures and algorithms for working with graphs.
Installation
You can install the package via Composer:
composer require actived/graphphp
Features
Graph
The Graph
class provides the foundation for working with undirected graphs in PHP. It includes methods for manipulating nodes, edges, and retrieving various properties of the graph.
Creating a Graph
use GraphPHP\Graph\Graph; use GraphPHP\Node\Node; use GraphPHP\Edge\Edge; $graph = new Graph();
Adding Nodes
$nodeA = new Node('A'); $graph->addNode($nodeA);
Adding Edges
$nodeB = new Node('B'); $edge = new Edge($nodeA, $nodeB); $graph->addEdge($edge);
Removing Nodes and Edges
Nodes and edges can be removed from the graph:
$graph->removeNode($nodeA); $graph->removeEdge($edge);
Neighbors
Retrieve the neighbors of a given node:
$neighbors = $graph->getNeighbors($nodeB);
Adjacency Matrix
Get the adjacency matrix of the graph:
$matrix = $graph->getAdjacencyMatrix();
Checking for Cycles
Determine if the graph contains a cycle:
if ($graph->hasCycle()) { echo "The graph has a cycle."; } else { echo "The graph does not have a cycle."; }
Transitive Closure
Compute the transitive closure of the graph using the Floyd-Warshall algorithm:
$closure = $graph->transitiveClosure();
Shortest Path
Compute the shortest path between two nodes using Dijkstra's algorithm:
$pathInfo = $graph->shortestPathDijkstra($nodeA, $nodeC); echo "Shortest path: " . implode(' -> ', $pathInfo['path']); echo "Cost: " . $pathInfo['cost'];
String Representation
To get a string representation of the graph:
echo $graph;
Note: The Graph class assumes an undirected graph. For directed graphs, refer to the DiGraph class documentation.
DiGraph (Directed Graph)
The DiGraph
class extends the base Graph
class and represents a directed graph. This means all edges in this graph have a direction, going from a source node to a target node.
Creating a Directed Graph
use GraphPHP\Graph\DiGraph; use GraphPHP\Node\Node; use GraphPHP\Edge\DirectedEdge; $diGraph = new DiGraph();
Adding Directed Edges
Only directed edges can be added to a directed graph:
$nodeA = new Node('A'); $nodeB = new Node('B'); $directedEdge = new DirectedEdge($nodeA, $nodeB); $diGraph->addEdge($directedEdge);
Outgoing Neighbors
Retrieve the outgoing neighbors of a given node:
$outgoingNeighbors = $diGraph->getNeighbors($nodeA);
Predecessors
Retrieve the predecessors (nodes with directed edges pointing to the given node) of a node:
$predecessors = $diGraph->getPredecessors($nodeB);
Bellman-Ford Shortest Path
Compute the shortest path between two nodes using the Bellman-Ford algorithm:
$pathInfo = $diGraph->shortestPathBellmanFord($nodeA, $nodeC); echo "Shortest path: " . implode(' -> ', $pathInfo['path']); echo "Cost: " . $pathInfo['cost'];
Checking for Cycles in Directed Graphs
Determine if the directed graph contains a cycle:
if ($diGraph->hasCycle()) { echo "The directed graph has a cycle."; } else { echo "The directed graph does not have a cycle."; }
Adjacency Matrix for Directed Graphs
Get the adjacency matrix of the directed graph:
$matrix = $diGraph->getAdjacencyMatrix();
Note: The DiGraph class is specific to directed graphs. If you need an undirected graph, refer to the base Graph class documentation.
Directed Acyclic Graphs (DAG)
Create and manipulate directed acyclic graphs.
use GraphPHP\Graph\DAG; use GraphPHP\Node\Node; use GraphPHP\Edge\DirectedEdge; $graph = new DAG(); $nodeA = new Node('A'); $nodeB = new Node('B'); $nodeC = new Node('C'); $graph->addNode($nodeA) ->addNode($nodeB) ->addNode($nodeC) ->addEdge(new DirectedEdge($nodeA, $nodeB, 4)) ->addEdge(new DirectedEdge($nodeB, $nodeC, -6)) ->addEdge(new DirectedEdge($nodeA, $nodeC, 2));
Transitive Reduction
Perform transitive reduction on a DAG.
$graph->transitiveReduction(); echo $graph; // Visual representation of the graph
Topological Sort
Get a topological ordering of the nodes in a DAG.
$order = $graph->topologicalSort(); print_r($order);
Roadmap
- Testing: Implement comprehensive tests for the current functionalities.
- Trees: Introduce tree graph structures.
- Directed Trees: Extend the tree structures to support directed trees.
- Binary Trees: Implement binary tree structures and related algorithms.
Contributing
If you have suggestions or improvements, feel free to submit a pull request or open an issue on the GitHub repository.
License
This package is open-sourced software licensed under the MIT license.