templesofcode/nodes-and-edges

PHP algorithm implementations

dev-master 2020-05-06 14:25 UTC

Requires

• php: >=7.1

MIT

• TOC

• php
• algorithms

README

A php partial-port of the library described in

https://algs4.cs.princeton.edu/40graphs/

Example usage:

use TemplesOfCode\NodesAndEdges\BFS\BreadthFirstPaths;
use TemplesOfCode\NodesAndEdges\UndirectedGraph;

function bfsPaths(string $file, int $sourceVertex)
{  
    // build the graph
    $graph = UndirectedGraph::fromFile($file);
    // create an instance
    $bfs = new BreadthFirstPaths($graph, $sourceVertex);
    // iterate over the set of graph vertices
    for ($vertex = 0; $vertex < $graph->getVertices(); $vertex++) {
        // is this connected to the source vertex
        if ($bfs->hasPathTo($vertex)) {
            // print to screen
            print sprintf(
                '%d to %d (%d):  ', 
                $sourceVertex, 
                $vertex,
                $bfs->distTo($vertex)
            );
            // iterate over the path
            foreach ($bfs->pathTo($vertex) as $x) {
                // check for self
                if ($x == $sourceVertex) {
                    print $x;
                } else {
                    print "-" . $x;
                }
            }
            print PHP_EOL;

        } else {
            print sprintf(
                '%d to %d (-):  not connected',
                $sourceVertex,
                $vertex
            );
        }
    }
}

See https://github.com/templesofcode/nodes-edges-commander for some additional example usage