README

一个提供结构和算法以在PHP中操作图的PHP图论包。

安装

您可以通过Composer安装此包

composer require actived/graphphp

特性

图

Graph类为在PHP中操作无向图提供了基础。它包括操作节点、边以及获取图的各种属性的方法。

创建图

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

删除节点和边

可以从图中删除节点和边

$graph->removeNode($nodeA);
$graph->removeEdge($edge);

邻居

检索给定节点的邻居

$neighbors = $graph->getNeighbors($nodeB);

邻接矩阵

获取图的邻接矩阵

$matrix = $graph->getAdjacencyMatrix();

检查循环

确定图是否包含循环

if ($graph->hasCycle()) {
    echo "The graph has a cycle.";
} else {
    echo "The graph does not have a cycle.";
}

传递闭包

使用Floyd-Warshall算法计算图的传递闭包

$closure = $graph->transitiveClosure();

最短路径

使用Dijkstra算法计算两个节点之间的最短路径

$pathInfo = $graph->shortestPathDijkstra($nodeA, $nodeC);
echo "Shortest path: " . implode(' -> ', $pathInfo['path']);
echo "Cost: " . $pathInfo['cost'];

字符串表示

获取图的字符串表示

echo $graph;

注意：Graph类假定是无向图。对于有向图，请参考DiGraph类的文档。

DiGraph（有向图）

DiGraph类扩展了基本Graph类，表示有向图。这意味着该图中的所有边都有方向，从源节点指向目标节点。

创建有向图

use GraphPHP\Graph\DiGraph;
use GraphPHP\Node\Node;
use GraphPHP\Edge\DirectedEdge;

$diGraph = new DiGraph();

添加有向边

只能向有向图中添加有向边

$nodeA = new Node('A');
$nodeB = new Node('B');
$directedEdge = new DirectedEdge($nodeA, $nodeB);
$diGraph->addEdge($directedEdge);

出邻接

检索给定节点的出邻接

$outgoingNeighbors = $diGraph->getNeighbors($nodeA);

前驱

检索指向给定节点的有向边的节点（前驱节点）

$predecessors = $diGraph->getPredecessors($nodeB);

Bellman-Ford最短路径

使用Bellman-Ford算法计算两个节点之间的最短路径

$pathInfo = $diGraph->shortestPathBellmanFord($nodeA, $nodeC);
echo "Shortest path: " . implode(' -> ', $pathInfo['path']);
echo "Cost: " . $pathInfo['cost'];

检查有向图中的循环

确定有向图是否包含循环

if ($diGraph->hasCycle()) {
    echo "The directed graph has a cycle.";
} else {
    echo "The directed graph does not have a cycle.";
}

有向图的邻接矩阵

获取有向图的邻接矩阵

$matrix = $diGraph->getAdjacencyMatrix();

注意：DiGraph类仅针对有向图。如果您需要无向图，请参考基本Graph类的文档。

有向无环图（DAG）

创建和操作有向无环图。

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

传递约简

对DAG执行传递约简。

$graph->transitiveReduction();
echo $graph; // Visual representation of the graph

拓扑排序

获取DAG中节点的拓扑排序。

$order = $graph->topologicalSort();
print_r($order);

路线图

• 测试：实现当前功能的全面测试。
• 树：引入树图结构。
• 有向树：扩展树结构以支持有向树。
• 二叉树：实现二叉树结构和相关算法。

贡献

如果您有建议或改进，请随时提交pull request或在GitHub仓库中打开issue。

许可协议

此软件包是开源软件，根据MIT许可协议授权。