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的新手吗？了解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可能会更改。更改日志changelog列出了发布之间更新的所有相关信息。

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

除了直接与代码工作外，任何额外的文档、对readme的补充或甚至修复简单的错误都同样受到欢迎。

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

请访问irc.freenode.net上的#graphp。

许可证

本项目采用宽松的MIT许可。

你知道我提供定制开发服务和为发行和贡献发放发票的服务吗？请联系我（@clue）获取详细信息。