README

用 PHP 编写的数学图/网络库

快速入门示例

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

<?php
require_once 'vendor/autoload.php';

use \Fhaculty\Graph\Graph as Graph;

$graph = new Graph();

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

// build some roads
$cologne->createEdgeTo($madrid);
$madrid->createEdgeTo($rome);
// create loop
$rome->createEdgeTo($rome);

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

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

特性

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

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

组件

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

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

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

图绘制

此库旨在支持可视化图形图像，包括它们到网页中，从CLI应用程序中打开图像以及将它们导出为PNG、JPEG或SVG文件格式（等等）。由于图绘制是一个复杂的领域，因此图的布局留给卓越的GraphViz“图可视化软件”，我们仅提供一些方便的API与GraphViz接口。

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

常见算法

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

• 搜索
  • 深度优先搜索（DFS）
  • 广度优先搜索（BFS）
• 最短路径
  • 迪杰斯特拉算法
  • 莫尔-贝尔曼-福特算法（MBF）
  • 计算跳数（简单BFS）
• 最小生成树（MST）
  • 克鲁斯卡尔算法
  • 普里姆算法
• 旅行商问题（TSP）
  • 暴力算法
  • 最小生成树启发式算法（TSP MST启发式算法）
  • 最近邻启发式算法（NN启发式算法）
• 最大流
  • 埃德蒙兹-卡尔普算法
• 最小费用流（MCF）
  • 循环消除
  • 连续最短路径
• 最大匹配
  • 流算法

更多信息请查看graphp/algorithms。

安装

推荐通过composer安装此库。您是否是composer的新手？了解composer？

{
    "require": {
        "clue/graph": "~0.9.0"
    }
}

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

测试

此库使用phpunit进行其广泛的测试套件。您可以使用全局安装，或者当您第一次运行$ composer install时，依赖composer安装。这设置开发环境，因此您现在可以从项目根目录运行

$ php vendor/bin/phpunit

贡献

此库带有广泛的测试套件，并定期在真实世界中进行测试和使用。尽管如此，此库仍被视为测试版软件，其API可能会更改。《变更日志》列出了发行之间所有相关的更新信息。

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

除了直接与代码工作外，任何额外的文档、对readme的补充，甚至纠正简单的拼写错误也同等欢迎。

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

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

许可

在MIT许可的宽松条款下发布MIT许可证。