README

GraPHP 是用 PHP 编写的数学图和网络库。

开发版本：这个分支包含即将推出的 1.0 版本的代码。对于当前稳定版 0.9 的代码，请查看 0.9.x 分支。

即将推出的 1.0 版本将是此包的发展方向。但是，我们仍将积极支持 0.9.x，以帮助尚未升级到最新版本的用户。有关详细信息，请参阅 安装说明。

目录

• 快速入门示例
• 功能
• 组件
  • 图绘制
  • 常见算法
• 安装
• 测试
• 贡献
• 许可

快速入门示例

安装后，让我们初始化一个示例图

<?php

require __DIR__ . '/vendor/autoload.php';

$graph = new Graphp\Graph\Graph();

// create some cities
$rome = $graph->createVertex(array('name' => 'Rome'));
$madrid = $graph->createVertex(array('name' => 'Madrid'));
$cologne = $graph->createVertex(array('name' => 'Cologne'));

// build some roads
$graph->createEdgeDirected($cologne, $madrid);
$graph->createEdgeDirected($madrid, $rome);
// create loop
$graph->createEdgeDirected($rome, $rome);

让我们看看哪个城市（顶点）有一条通往罗马的路（即指向顶点的边）

foreach ($rome->getVerticesEdgeFrom() as $vertex) {
    echo $vertex->getAttribute('name') . ' leads to Rome' . PHP_EOL;
    // result: Madrid and Rome itself lead to Rome
}

功能

这个库围绕 数学图论（即它不是一个用于绘制 函数图的 图表库）的概念构建。本质上，图是由任意数量的 连接 组成的 节点 集合。在图论中，顶点（顶点的复数）是这些 节点 的抽象表示，而 连接 则表示为 边。边可以是无向的（“双向”）或有向的（“单向”，即二向边、弧）。

根据边的构建方式，整个图可以是无向的，也可以是有向图（即有向图）或混合图。边也可以形成 环（即从顶点 A 指向顶点 A 的边）。此外，也支持从顶点 A 到顶点 B 的 多重边（即平行边），实际上形成一个 多重图（即伪图）。当然，也支持任何组合。虽然许多作者试图区分这些核心概念，但这个库努力不对你的图施加任何人为的限制或假设。

组件

这个库提供了用于处理图、其顶点、边和属性的核心数据结构。

在这些结构之上构建了几个官方组件，以提供常用的功能。这种架构允许这些组件独立使用，并且仅在需要时使用。

以下是部分突出显示的组件列表。所有官方组件的列表可以在 graphp 项目 中找到。

图绘制

这个库旨在支持图形图像的可视化，包括将它们嵌入到网页中，从CLI应用程序中打开图像，以及将它们导出为PNG、JPEG或SVG等文件格式（以及其他许多格式）。因为图绘制是一个复杂的领域，所以实际的图形布局留给优秀的GraphViz "图形可视化软件"来处理，我们仅提供一些方便的API与GraphViz接口。

有关更多详细信息，请参阅graphp/graphviz。

常见算法

除了图形绘制之外，最常见的事情之一是运行算法来解决常见的图形问题。因此，这个库被用作实现许多常用图形算法的基础。

• 搜索
  • 深度优先搜索（DFS）
  • 广度优先搜索（BFS）
• 最短路径
  • Dijkstra算法
  • Moore-Bellman-Ford（MBF）算法
  • 计算跳数（简单BFS）
• 最小生成树（MST）
  • Kruskal算法
  • Prim算法
• 旅行商问题（TSP）
  • 穷举算法
  • 最小生成树启发式（TSP MST启发式）
  • 最近邻启发式（NN启发式）
• 最大流
  • Edmonds-Karp算法
• 最小费用流（MCF）
  • 循环消除
  • 连续最短路径
• 最大匹配
  • 流算法

有关更多详细信息，请参阅graphp/algorithms。

安装

推荐使用Composer来安装此库。您是Composer新手吗？

一旦发布，此项目将遵循SemVer。目前，这将安装最新开发版本。

composer require graphp/graph:^1@dev

有关版本升级的详细信息，请参阅CHANGELOG。

该项目旨在在任何平台上运行，因此不要求任何PHP扩展，并支持从PHP 5.3到当前PHP 8+的运行。强烈建议使用此项目所支持的最新PHP版本。

您可能还想安装一些附加组件。所有官方组件的列表可以在graphp项目中找到。

测试

此库使用PHPUnit进行广泛的测试套件。要运行测试套件，您首先需要克隆此存储库，然后通过Composer安装所有依赖项。

composer install

要运行测试套件，请转到项目根目录并运行

vendor/bin/phpunit

贡献

此库附带了一个广泛的测试套件，并经常在实际环境中进行测试和使用。尽管如此，此库仍被视为测试版软件，其API可能发生变化。变更日志列出了发布之间更新的所有相关信息。

如果您遇到任何问题，请随时与我们联系，提交错误报告，甚至最好提供补丁/拉取请求和/或单元测试以重现您的问题。

除了直接处理代码外，任何额外的文档、对readme的添加或甚至修复简单的错误都是受欢迎的。

欢迎任何反馈和/或贡献！

在irc.freenode.net上查看#graphp频道。

许可

此项目在宽松的MIT许可证下发布。

你知道吗？我提供定制开发服务，并发行赞助发布和贡献的发票。请联系我（@clue）了解详情。