A PHP graph theory package that provides structures and algorithms for working with graphs.
You can install the package via Composer:
composer require actived/graphphp
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.
use GraphPHP\Graph\Graph;
use GraphPHP\Node\Node;
use GraphPHP\Edge\Edge;
$graph = new Graph();
$nodeA = new Node('A');
$graph->addNode($nodeA);
$nodeB = new Node('B');
$edge = new Edge($nodeA, $nodeB);
$graph->addEdge($edge);
Nodes and edges can be removed from the graph:
$graph->removeNode($nodeA);
$graph->removeEdge($edge);
Retrieve the neighbors of a given node:
$neighbors = $graph->getNeighbors($nodeB);
Get the adjacency matrix of the graph:
$matrix = $graph->getAdjacencyMatrix();
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.";
}
Compute the transitive closure of the graph using the Floyd-Warshall algorithm:
$closure = $graph->transitiveClosure();
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'];
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.
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.
use GraphPHP\Graph\DiGraph;
use GraphPHP\Node\Node;
use GraphPHP\Edge\DirectedEdge;
$diGraph = new DiGraph();
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);
Retrieve the outgoing neighbors of a given node:
$outgoingNeighbors = $diGraph->getNeighbors($nodeA);
Retrieve the predecessors (nodes with directed edges pointing to the given node) of a node:
$predecessors = $diGraph->getPredecessors($nodeB);
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'];
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.";
}
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.
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));
Perform transitive reduction on a DAG.
$graph->transitiveReduction();
echo $graph; // Visual representation of the graph
Get a topological ordering of the nodes in a DAG.
$order = $graph->topologicalSort();
print_r($order);
- 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.
If you have suggestions or improvements, feel free to submit a pull request or open an issue on the GitHub repository.
This package is open-sourced software licensed under the MIT license.