README

Gliph是一个PHP的图库。它为其他PHP应用程序提供了图构建块和数据结构。它旨在与内存中的图一起使用，而不是与图数据库（如Cayley或Neo4J）进行交互（尽管它也可以用来促进此类连接）。

Gliph旨在实现合理的接口和尽可能高性能的实现。

这确实需要了解足够多的图知识，以便知道哪种类型适用于您的用例，但我们旨在提供简化这些选择的助手。

快速入门

使用gliph很简单：选择一个图实现，然后根据需要添加边和顶点。（注意：gliph当前仅支持对象顶点，但此限制可能在未来的版本中放宽）

<?php

use Gliph\Graph\DirectedAdjacencyList;

class Vertex {
    public $val;

    public function __construct($val) {
        $this->val = $val;
    }
}

$vertices = array(
    'a' => new Vertex('a'),
    'b' => new Vertex('b'),
    'c' => new Vertex('c'),
    'd' => new Vertex('d'),
    'e' => new Vertex('e'),
    'f' => new Vertex('f'),
);

$g = new DirectedAdjacencyList();

foreach ($vertices as $vertex) {
    $g->ensureVertex($vertex);
}

$g->ensureArc($vertices['a'], $vertices['b']);
$g->ensureArc($vertices['b'], $vertices['c']);
$g->ensureArc($vertices['a'], $vertices['c']);
$g->ensureArc($vertices['d'], $vertices['a']);
$g->ensureArc($vertices['d'], $vertices['e']);

这将创建以下有向图

一旦创建了图，gliph提供了一系列的Traversable机制来在图上执行工作。这些机制非常重要，在维基百科中有更详细的介绍，但对于熟悉图论的人来说，方法命名旨在自我解释

对于有向和无向图

• Graph::vertices()
• Graph::edges()
• Graph::adjacentTo($vertex)
• Graph::incidentTo($vertex)

仅对于有向图

• Digraph::successorsOf($vertex)
• Digraph::predecessorsOf($vertex)
• Digraph::arcsFrom($vertex)
• Digraph::arcsTo($vertex)

核心概念

Gliph有几个概念组件协同工作，以创建一个连贯的库：图实现、算法和访问者。

Gliph有多个组件协同工作：图类、算法和访问者。一般来说，Gliph模仿了C++ Boost Graph Library；阅读他们的文档可以提供大量有关Gliph如何工作的见解。

图

Gliph最重要的基本出口是其各种图接口。其他组件（算法和访问者）严格依赖于接口，而不是具体实现。因此，gliph的使用者可以创建特定情况的实现，并确保它们与算法一起工作。为此，gliph提供了一些phpunit测试特性，这使得确保您的自定义图实现符合gliph接口的字母和灵魂变得简单。

Gliph的自己的实现旨在在一般情况下尽可能高效。当前的实现包括仅邻接表，有向和无向。

算法

Gliph提供了各种算法，这些算法可以在图对象上运行。这些算法通过调用定义在各种图接口中的方法（主要是迭代器）与图进行交互。如果一个图实现了特定算法所指定的接口类型提示，则该算法可以在该图上运行。但是，算法的效率将主要取决于该图实现如何高效地满足接口要求。例如，邻接表在提供图中所有边的列表方面效率不高，但在单顶点中心操作方面非常好。

Gliph的算法通常实现得相当稀疏（尤其是遍历器）——它们试图实现算法最简单、最通用的版本。它们可能不会返回任何输出，因为这部分工作留给访客（Visitors）来完成。

访客（Visitors）

大多数算法都需要提供访客对象。访客符合算法指定的接口，算法将在其执行过程中的某些选择点调用访客。这使得算法保持高度通用，而访客可以根据更具体的目的进行定制。

例如，可以使用DepthFirst访客来计算顶点可达性或生成拓扑排序列表。这些都是深度优先图遍历所能完成的任务。但是，执行这些任务的工作留给访客，这样只需要一个遍历算法，并且该算法尽可能便宜（内存和循环）。

致谢

这个库从C++ Boost Graph Library中汲取灵感，尽管在有些重要的设计哲学上有所分歧。Gliph通常遵循与gogl相同的模式，但那里的概念应用得更严格。

许可证

MIT