smoren/graph-tools

Graph tools

v1.0.0 2023-08-25 09:59 UTC

Requires

• php: >=7.4.0
• php-ds/php-ds: >=1.4

Requires (Dev)

• codeception/codeception: ^4.2.1
• codeception/module-asserts: ^2.0
• php-coveralls/php-coveralls: ^2.0
• phpstan/phpstan: ^1.8
• squizlabs/php_codesniffer: 3.*

Suggests

• ext-ds: *

MIT

• Smoren

• math
• graph

README

Tools for working with graphs

How to install to your project

composer require smoren/graph-tools

Unit testing

composer install
composer test-init
composer test

Usage

Working with preloaded graph repository

Basic graph

use Smoren\GraphTools\Models\Edge;
use Smoren\GraphTools\Models\Vertex;
use Smoren\GraphTools\Traverse\Traverse;
use Smoren\GraphTools\Traverse\TraverseDirect;
use Smoren\GraphTools\Traverse\TraverseReverse;
use Smoren\GraphTools\Filters\TransparentTraverseFilter;
use Smoren\GraphTools\Store\PreloadedGraphRepository;
use Smoren\GraphTools\Structs\FilterConfig;

$vertexes = [
    new Vertex(1, 1, null), // id, type, extra data
    new Vertex(2, 1, null),
    new Vertex(3, 1, null),
];
$connections = [
    new Edge(1, 1, 1, 2), // id, type, from id, to id
    new Edge(2, 1, 2, 3),
];

// Creating repository
$repo = new PreloadedGraphRepository($vertexes, $connections);

// Creating direct traverse model
$traverse = new TraverseDirect($repo);
$contexts = $traverse->generate(
    $repo->getVertexById(1),
    new TransparentTraverseFilter([FilterConfig::PREVENT_LOOP_PASS])
);

// Let's go traverse
$vertexIds = [];
foreach($contexts as $context) {
    $vertexIds[] = $context->getVertex()->getId();
}
print_r($vertexIds); // [1, 2, 3]

// Creating reverse traverse model
$traverse = new TraverseReverse($repo);
$contexts = $traverse->generate(
    $repo->getVertexById(3),
    new TransparentTraverseFilter([FilterConfig::PREVENT_LOOP_PASS])
);

// Let's go traverse
$vertexIds = [];
foreach($contexts as $context) {
    $vertexIds[] = $context->getVertex()->getId();
}
print_r($vertexIds); // [3, 2, 1]

$traverse = new Traverse($repo);

// Creating non-directed traverse model
$contexts = $traverse->generate(
    $repo->getVertexById(2),
    new TransparentTraverseFilter([FilterConfig::PREVENT_LOOP_PASS])
);

// Let's go traverse
$vertexIds = [];
$loopsCount = 0;
foreach($contexts as $context) {
    if($context->isLoop()) {
        $contexts->send(Traverse::STOP_BRANCH);
        ++$loopsCount;
    } else {
        $vertexIds[] = $context->getVertex()->getId();
    }
}
print_r($vertexIds); // [2, 3, 1]
var_dump($loopsCount); // 2

// Creating non-directed traverse model with loop prevent control
$contexts = $traverse->generate(
    $repo->getVertexById(2),
    new TransparentTraverseFilter([FilterConfig::PREVENT_LOOP_PASS, FilterConfig::PREVENT_LOOP_HANDLE])
);

// Let's go traverse
$vertexIds = [];
foreach($contexts as $context) {
    $vertexIds[] = $context->getVertex()->getId();
}
print_r($vertexIds); // [2, 3, 1]

Look for more examples in tests.