README

GraphDS是什么？为什么创建它？

GraphDS是PHP中图数据结构的面向对象、轻量级实现。

在我的一个项目中，我需要一个在PHP中表示图的方法。现有的所有解决方案都不适合我，所以我决定从头开始编写自己的图库。项目中原有的实现包含用于图遍历和图重构的额外函数，但这些函数是特定于我的项目的。

GraphDS的此版本最初是我的原始实现的简化版本，但现在已发展成为一个独立的项目。它利用面向对象实践，允许按需加载算法，使GraphDS既快速又可扩展，同时保持轻量级。

GraphDS至少需要PHP版本5.3。从PHP 5.4开始可以运行单元测试。尽管试图保持与较旧PHP版本的兼容性，但仅对最后3个主要PHP版本进行官方单元测试。

如何安装

简单地要求Composer包。在你的项目目录中运行

composer require algb12/graph-ds

它有什么用？

图在许多方面都有用，从交通到社交网络。在这方面，GraphDS使在PHP中处理图变得更加容易。

请查看SampleApp_RoadPlanner目录中的RoadPlanner示例应用程序，以找到GraphDS的原始应用。RoadPlanner应用程序使用Dijkstra算法、多路径Dijkstra算法和Floyd-Warshall算法计算两个城市之间的最短道路。计算出的路径在源地图上以视觉方式表示。要使用你自己的地图测试GraphDS，请查看src/data中的roads.json文件，你可以在其中添加你自己的地图/"国家"。

基本语法

GraphDS具有用于创建无向图和有向图的顶点和边的函数。用户无需担心创建哪种类型的边/顶点，因为这都是在相关类下抽象出来的。

以下是对GraphDS使用的简要介绍

有向图和无向图

在图论中，有两种主要的图类型。一方面，有有向图。有向图中的顶点通过单向边连接。将有向图的边想象为单向车道——你可以从任何顶点开始，但只能沿着边的方向性跟随到相邻顶点。

另一方面，有无向图。它们允许你从任何顶点到达任何邻居，因为在无向图中，没有祖先和后代的概念。将无向图的边想象为双向的道路，交通在两个方向上。顶点通过无方向的边相互连接。

以下是如何初始化有向图的示例

<?php

$g = new DirectedGraph();

请注意，图是一个对象，任何顶点和边都包含在这个对象中。

以类似的方式，可以通过在DirectedGraph对象的位置创建UndirectedGraph对象来初始化无向图。

转置图

有向图的转置图是指所有边(u, v)变为(v, u)，其中u和v是有向边连接的顶点。

要获取有向图$g的转置作为DirectedGraph对象，请调用

$g->getTranspose()

这可能对需要图转置的算法很有用，现在GraphDS提供了一个方法来实现它。

顶点

在任何图中，所有顶点都可以通过$g->vertices数组访问，其中$g是图对象的实例。因此，要访问顶点A，语法将是$g->vertices['A']。

添加和删除顶点

可以使用$g->addVertex('v')和$g->removeVertex('v')方法添加和删除顶点，其中v是要添加/删除的顶点的名称。

获取和设置顶点的值

要获取顶点的值，可以调用$g->vertices['v']->getValue()。要设置顶点的值，可以调用$g->vertices['v']->setValue(value)，其中value可以是任何可存储的数据类型。

获取顶点的邻居

通过使用$g->vertices['v']->getNeighbors()可以获取无向图中顶点的邻居。

在有向图中，$g->vertices['v']->getInNeighbors()返回一个由入边连接的所有顶点的数组，而$g->vertices['v']->getOutNeighbors()返回一个由当前顶点发出的所有顶点连接的数组的数组。$g->vertices['v']->getNeighbors()返回一个包含两个子数组in和out的数组，分别代表入边和出边的顶点。

入度和出度

顶点的入度和出度分别表示与顶点连接的入边和出边的数量。

入度和出度仅适用于有向图，因为无向图不能有入边或出边。

可以使用$g->vertices['v']->getIndegree()和$g->vertices['v']->getOutdegree()轻松确定顶点的入度和出度。

断言顶点相邻

在任何图中，可以通过调用$g->vertices['A']->adjacent('B')断言顶点B与A相邻。如果顶点相邻，则返回true，否则返回false。请注意，在有向图中，使用adjacent方法时，无论是有入边还是有出边，都将考虑顶点相邻。

在有向图中，可以使用$g->vertices['A']->inAdjacent('B')和$g->vertices['A']->outAdjacent('B')分别断言内向和向外相邻。

边

边是连接顶点的对象。请注意，在GraphDS中，边作为与顶点分离的对象存储，这意味着它们是独立存在的。管理图内边与顶点之间关系的GraphDS核心负责管理这些关系。

可以通过$g->edge('A', 'B')轻松访问边，其中A和B是连接的顶点。请注意，在无向图中，$g->edge('A', 'B')和$g->edge('B', 'A')是等价的，而在有向图中，它们代表两个不同的边。

实边和虚边

在GraphDS中，边作为对象存储，每个对象都占用内存空间。为了减少空间占用，从版本1.0.3开始引入了edge函数，它返回实边和“虚”边。

实边是实际的DirectedEdge或UndirectedEdge对象，而虚边不是实际的边对象，而是edge函数返回边('A', 'B')的结果，即使请求的是('B', 'A')。虚边可以像实边一样修改。虚边不是有向图的组成部分，因为每个有向边都是唯一的。

这是期望的行为，因为在无向图中，边('A', 'B')与('B', 'A')是等价的。虚边还消除了无向图中边重复的问题，因此也减少了GraphDS占用的内存。

添加和删除边

要添加一条边，只需调用 $g->addEdge('A', 'B', 'value')，其中 A 和 B 是图中需要通过此边连接的顶点，而 value 是边的可选值。此值可以用作边的权重。边的默认值为 null。

注意，在无向图中，这将返回“虚拟”边 ('B', 'A')，即使请求的是 ('A', 'B')。

可以通过 $g->removeEdge('A', 'B') 删除边。由于虚拟边的特性，这将在无向图中删除两条边，即真实边 ('A', 'B') 和虚拟边 ('B', 'A')，但在有向图中只删除真实边。在无向图中，边删除是无序的，这意味着无论提供的是真实边还是虚拟边，都会删除正确的边。

获取和设置边的值

要获取边的值，可以调用 $g->edge('A', 'B')->getValue()。要设置边的值，可以调用 $g->edge('A', 'B')->setValue(value)，其中 value 可以是任何可存储的数据类型。

算法

从版本 1.0.1 开始，GraphDS 支持算法。GraphDS 中的算法命名空间为 GraphDS\Algo。

在 GraphDS 中，算法被视为修改图的独立对象。它们接受图并在其上工作，但不会影响图的核心功能。

这就是 GraphDS 精简和优化的原因，因为算法只有在需要时才加载到内存中，因为它们不是图对象的固有部分。

运行算法

任何算法首先必须被 PHP “使用”，例如 use GraphDS\Algo\Algorithm
在相关的图（$g）上创建算法的新实例，例如 $a = new Algorithm($g)
现在可以使用 $a->run(args) 运行算法，其中 args 是算法特定的参数
使用 $a->get(args) 获取算法的结果，其中 args 是算法特定的参数

“运行和获取”语句简化了算法的使用，因为这是算法应该拥有的唯一两个公开暴露的方法。从现在起，文档将仅引用这些方法。

编写 GraphDS 算法

为了简化算法的编写，PHP 的标准 PHP 库（SPL）提供了有用的辅助类，例如

SplQueue：FIFO 队列的实现
SplStack：LIFO 栈的实现

这些类极大地简化了算法的编写，例如深度优先搜索（DFS）和广度优先搜索（BFS），这些算法可以在算法所在的目录中找到。

以下概述了 GraphDS 算法的基本结构。为了简洁起见，省略了文档块，尽管推荐为算法正确编写文档

<?php
namespace GraphDS\Algo;

use GraphDS\Graph\Graph;
use GraphDS\Graph\DirectedGraph;
use GraphDS\Graph\UndirectedGraph;
use InvalidArgumentException;

// Class defining an algorithm named "Algorithm"
class Algorithm
{
    // Reference to the graph
    public $graph;

    // Any global variables...

    // Constructor accepts a GraphDS graph and validates it
    public function __construct($graph)
    {
        if (!($graph instanceof DirectedGraph) && !($graph instanceof UndirectedGraph)) {
            throw new InvalidArgumentException(
                "Algorithm requires a directed or undirected graph"
            );
        }
    }

    // Running the algorithm
    public function run(args)
    {
        code...
    }

    // Getting the results of the algorithm
    public function get(args)
    {
        code...
    }

    // Any private helper methods...
}

再次用文字概述上述内容

检查图是否确实是图并使用它，否则抛出 InvalidArgumentException
run(args) 执行算法，其中 args 是参数
get(args) 获取算法的结果，其中 args 是参数

请注意，处理结果变量的方式是灵活的，因为不同的算法可能需要从代码的不同部分访问它。

广度优先搜索（BFS）

BFS，一种路径遍历算法，在类 GraphDS\Algo\BFS 中。它访问图中的每个顶点，并沿着图的广度前进。因此，它按层逐层访问图中的每个顶点。

$bfs->run(root) 接受 root 作为必选参数，这是 BFS 的起始顶点的名称
$bfs->get() 不接受任何参数。它返回一个数组，$arr，包含 3 个子数组
- $arr['discovered']（按 BFS 顺序发现的顶点）
- $arr['dist']（每个顶点到根顶点的距离，以跳数计）
- $arr['parent']（使用 BFS 时每个顶点的父顶点）

深度优先搜索（DFS）

DFS，一种路径遍历算法，位于类 GraphDS\Algo\DFS 中。它访问图中的每个顶点，并沿着图的深度进行搜索。因此，它访问图中的每个顶点，并且只有当所有顶点的后代都已在其完全深度上访问过时，才会从一个顶点移动到另一个顶点。

$dfs->run(root) 接受 root 作为必选参数，这是 DFS 的起始顶点的名称
$dfs->get() 不接受任何参数。它返回一个数组，arr，包含 3 个子数组
- $arr['discovered']（按 DFS 顺序发现的顶点）
- $arr['dist']（每个顶点到根顶点的距离，以跳数计）
- $arr['parent']（使用 DFS 时每个顶点的父顶点）

Dijkstra 算法求最短路径

Dijkstra 算法求最短路径算法在类 GraphDS\Algo\Dijkstra 中。它找到顶点与所有其他顶点之间的最短路径。

$dijkstra->run(start) 接受 start 作为必选参数，这是 Dijkstra 应该开始的顶点的名称
$dijkstra->get(dest) 接受 dest 作为必选参数，这是应返回最短路径的目标顶点的名称。它返回一个包含 2 个子数组的数组，arr
- $arr['path']（从 start 到 dest 的最短路径）
- $arr['dist']（每个顶点到根顶点的最短距离，以边权重计）

多路径 Dijkstra 算法求最短路径

与单路径版本不同，多路径 Dijkstra 算法求最短路径算法找到顶点与所有其他顶点之间的所有最短路径。它位于类 GraphDS\Algo\DijkstraMulti 中。

$dijkstra_mult->run(start) 接受 start 作为必选参数，这是多路径 Dijkstra 应该开始的顶点的名称
$dijkstra_mult->get(dest) 接受 dest 作为必选参数，这是应计算所有最短路径的目标顶点。它返回一个包含 2 个子数组的数组，$arr
- $arr['paths']（从 $start 到 $dest 的所有最短路径的数组）
- $arr['dist']（每个顶点到根顶点的最短距离，以边权重计）

Floyd-Warshall 算法

Floyd-Warshall 算法计算图中每个顶点之间的最短路径。它位于类 GraphDS\Algo\FloydWarshall 中。

$fw->run() 不接受任何参数，只是简单地对图上的算法进行运行
$fw->get(startVertex, destVertex) 接受 startVertex 和 destVertex 作为必选参数，分别是起始顶点和目标顶点，应在这两个顶点之间计算最短路径。它返回一个包含子数组的数组 arr
- $arr['path']（从 start 到 dest 的最短路径）
- $arr['dist']（目标顶点到起始顶点的最短距离，以边权重计）

Yen 算法

Yen 算法在图中计算单源 K 短路径环路径。它位于类 GraphDS\Algo\Yen 中。

$yen->run(start, dest, k) 接受 start 作为必选参数，这是 Yen 应该开始的顶点的名称。接受 dest 作为必选参数，这是应返回最短 K 路径的目标顶点的名称。接受 k 作为可选参数，默认为 3，这是要返回的最大路径数。
$yen->get() 不接受任何参数。它返回一个已排序的数组 arr，包含子数组
- $arr[i]['path']（从 start 到顶点 dest 的路径）
- $arr[i]['dist']（目标顶点到起始顶点的距离，以边权重为单位）

持久性

GraphDS 具有使用流行的 GraphML 格式导出和导入图的功能。注意，为了正确地执行图持久性，应在服务器上设置正确的读写权限，这超出了本 README 的范围。

GraphML 文件的示例有 graphUndirected.graphml 和 graphDirected.graphml，这两个文件都位于本存储库中。

导出图

要将图导出到 GraphML 文件，请使用 GraphDS\Persistence\ExportGraph 类，并运行 $e = new ExportGraph($g)，其中 $e 是图导出对象，$g 是一个图。$graphml = $e->getGraphML() 将 $graphml 设置为图的 GraphML 标记，$e->saveToFile($graphml, 'graph.graphml') 将此标记写入文件 graph.graphml。

导入图

要从 GraphML 文件导入图，请使用 GraphDS\Persistence\ImportGraph 类，并运行 $i = new ImportGraph()，其中 $i 是图导入对象。$g = $i->fromGraphML('graph.graphml') 将 $g 设置为文件 graph.graphml 中由 GraphML 标记表示的 GraphDS 图对象。

对象 $g 现在是常规的 GraphDS，从 graph.graphml 文件中的 GraphML 标记重建。

测试

该应用可以在使用 docker 的 php 7.2 环境中本地测试。

使用以下命令构建 docker 容器。
```
docker build -t docker-graph-ds .
```
使用以下命令在 docker 容器中运行 php 单元测试。
```
docker run --rm docker-graph-ds "./vendor/bin/phpunit"
```

关于错误和/或建议

如果 GraphDS 中发现任何错误，请通过 GitHub 联系我或发送电子邮件至： algb12.19@gmail.com。同样适用于任何建议。

尽管进行了彻底的单元测试，但错误不可避免地会出现，所以如果出现任何问题，请务必在 GitHub 上提出！目前支持 PHP 5.3 及以上版本，尽管建议至少使用 PHP 5.6。

algb12 / graph-ds

维护者

详细信息