README

一个适配器，使 Graphp 与 Pathfinder 兼容。

安装

使用 composer require stratadox/graphp-finder 安装

功能

此 Graphp 适配器旨在尊重 Graphp 哲学，支持有向和无向图，以及单图和多图。

上述功能大致对应于 Pathfinder 所说的 网络。除了网络之外，Pathfinder 还可以操作它所称为的 环境：附着有笛卡尔坐标的图。

使用环境而不是网络的优势在于，可以通过使用 启发式算法 来优化搜索算法，这是 Pathfinder 的 A* 实现 使用的技术。

此适配器可以用来将 Graphp 图转换为环境或网络。为了实现兼容性，环境适配器利用了 Graphp 的 attributes 概念。

Graphp 中的属性是键值对；环境适配器需要至少存在键 x 和 y，当可用时也使用 z。

示例

无 GraphpFinder 的环境

使用 Pathfinder 模块的标准方式看起来大致如此

<?php
use Stratadox\Pathfinder\DynamicPathfinder;
use Stratadox\Pathfinder\Graph\At;
use Stratadox\Pathfinder\Graph\Builder\GraphEnvironment;
use Stratadox\Pathfinder\Graph\Builder\WithEdge;

$environment = GraphEnvironment::create()
    ->withLocation('A', At::position(0, 0), WithEdge::to('B', 5)->andTo('C', 8))
    ->withLocation('B', At::position(0, 1), WithEdge::to('D', 9)->andTo('A', 1))
    ->withLocation('C', At::position(1, 0), WithEdge::to('D', 4)->andTo('A', 1))
    ->withLocation('D', At::position(1, 1), WithEdge::to('B', 3)->andTo('C', 9))
    ->make();

$shortestPath = DynamicPathfinder::operatingIn($environment);

assert(['A', 'C', 'D'] === $shortestPath->between('A', 'D'));
assert(['D', 'B', 'A'] === $shortestPath->between('D', 'A'));

assert([
    'B' => ['A', 'B'],
    'C' => ['A', 'C'],
    'D' => ['A', 'C', 'D'],
] === $shortestPath->from('A'));

使用 GraphpFinder 的网络

如果你正在使用 Graphp 图，你可以使用此适配器来使它们兼容

<?php
use Fhaculty\Graph\Graph;
use Stratadox\GraphpFinder\AdaptedNetwork;
use Stratadox\Pathfinder\DynamicPathfinder;

// The same network as in the previous example, now represented as Graphp

$graph = new Graph();
$a = $graph->createVertex('A');
$b = $graph->createVertex('B');
$c = $graph->createVertex('C');
$d = $graph->createVertex('D');

$a->createEdgeTo($b)->setWeight(5);
$a->createEdgeTo($c)->setWeight(8);
$b->createEdgeTo($d)->setWeight(9);
$b->createEdgeTo($a)->setWeight(1);
$c->createEdgeTo($d)->setWeight(4);
$c->createEdgeTo($a)->setWeight(1);
$d->createEdgeTo($b)->setWeight(3);
$d->createEdgeTo($c)->setWeight(9);

$shortestPath = DynamicPathfinder::operatingIn(AdaptedNetwork::from($graph));

assert(['A', 'C', 'D'] === $shortestPath->between('A', 'D'));
assert(['D', 'B', 'A'] === $shortestPath->between('D', 'A'));

assert([
    'B' => ['A', 'B'],
    'C' => ['A', 'C'],
    'D' => ['A', 'C', 'D'],
] === $shortestPath->from('A'));

使用 GraphpFinder 的环境

您可以使用属性来定义坐标，从而提高在图中找到最短路径（s）的速度

<?php
use Fhaculty\Graph\Graph;
use Stratadox\GraphpFinder\AdaptedEnvironment;
use Stratadox\Pathfinder\DynamicPathfinder;

// The same environment as in the previous example, now represented as Graphp

$graph = new Graph();
$a = $graph->createVertex('A');
$a->setAttribute('x', 0);
$a->setAttribute('y', 0);
$b = $graph->createVertex('B');
$b->setAttribute('x', 0);
$b->setAttribute('y', 1);
$c = $graph->createVertex('C');
$c->setAttribute('x', 1);
$c->setAttribute('y', 0);
$d = $graph->createVertex('D');
$d->setAttribute('x', 1);
$d->setAttribute('y', 1);

$a->createEdgeTo($b)->setWeight(5);
$a->createEdgeTo($c)->setWeight(8);
$b->createEdgeTo($d)->setWeight(9);
$b->createEdgeTo($a)->setWeight(1);
$c->createEdgeTo($d)->setWeight(4);
$c->createEdgeTo($a)->setWeight(1);
$d->createEdgeTo($b)->setWeight(3);
$d->createEdgeTo($c)->setWeight(9);


$shortestPath = DynamicPathfinder::operatingIn(AdaptedEnvironment::from($graph));

assert(['A', 'C', 'D'] === $shortestPath->between('A', 'D'));
assert(['D', 'B', 'A'] === $shortestPath->between('D', 'A'));

assert([
    'B' => ['A', 'B'],
    'C' => ['A', 'C'],
    'D' => ['A', 'C', 'D'],
] === $shortestPath->from('A'));

这些后者的例子看起来代码更多，但这只是因为与 Pathfinder 模块附带的各种 图形构建器 相比，创建 Graphp 图要更冗长一些。

当你已经有了 Graphp 图时，使用 AdaptedEnvironment::from($graph) 比创建和维护整个图的额外副本以便路径查找要短、快且不麻烦。

使用 GraphpFinder 的 3D 环境

同样支持三维坐标

<?php
use Fhaculty\Graph\Graph;
use Stratadox\GraphpFinder\AdaptedEnvironment;
use Stratadox\Pathfinder\Distance\Euclidean;
use Stratadox\Pathfinder\DynamicPathfinder;
use Stratadox\Pathfinder\Estimate\Estimate;

$graph = new Graph();
$a = $graph->createVertex('A');
$a->setAttribute('x', 0);
$a->setAttribute('y', 0);
$a->setAttribute('z', 0);
$b = $graph->createVertex('B');
$b->setAttribute('x', 2);
$b->setAttribute('y', 5);
$b->setAttribute('z', 4);
$c = $graph->createVertex('C');
$c->setAttribute('x', 8);
$c->setAttribute('y', -1);
$c->setAttribute('z', 0.5);
$d = $graph->createVertex('D');
$d->setAttribute('x', 9);
$d->setAttribute('y', 5);
$d->setAttribute('z', 1);

$a->createEdge($b)->setWeight(6);
$a->createEdge($c)->setWeight(8);
$b->createEdge($d)->setWeight(9);
$c->createEdge($d)->setWeight(4);

$shortestPath = DynamicPathfinder::withHeuristic(
    Estimate::costAs(
        Euclidean::inDimensions(3), 
        AdaptedEnvironment::from3D($graph)
    )
);

assert(['A', 'C', 'D'] === $shortestPath->between('A', 'D'));