letournel/path-finder

Path finder algorithm

1.2.1 2017-07-23 14:59 UTC

Requires

• php: >=5.3.0

Requires (Dev)

• phpunit/phpunit: ~4.0

MIT

• Adrien Letournel

• shortest path
• dijkstra
• Graph algorithms
• travelling salesman
• astar
• floydwarshall
• nearest neighbour
• 2opt
• 3opt

README

PathFinder is a standalone library aiming to implement famous path and route finding algorithms in PHP to solve classical problems such as:

• SSP: Shortest path problem
• TSP: Travelling salesman problem

Features

• Distances: Chebyshev, Euclidean, Manhattan, Octile, Zero

• SSP solving algorithms: AStar, Dijkstra, FloydWarshall

• TSP solving algorithms: NearestNeighbour, 2Opt, 3Opt

Roadmap

• New SSP solving algorithms: Kruskal MooreBellmanFord Prim or others

• New TSP solving algorithms: Christofides, kOpt, LinKernighan or others

• Speed optimisations

• Open to suggestions and contributions

Classes

Core Classes

• Heuristic: A distance with a floating weight.
• Node: A node entity used in NodeGrid, NodeGraph, NodeMap or NodePath which is basically a couple of coordinates (x, y) or indices (i,j)
• NodeGraph: A graph is a set of vertices connected by edges. Here, vertices are nodes and any couple of them can be connected by an edge with a floating value. By default, the graph is symmetric so the edge from vertex A to vertex B and vice versa have the same value.
• NodeGrid: Simply a matrix of Nodes with coordinates (x, y) or indices (i,j) using the following pattern:

    .--------------> j (width) coord y
    | 1,1 1,2 1,3
    | 2,1 2,2 2,3
    | 3,1 ...
    |
    i (height) coord x

• NodeMap: A map or dictionary which maps a Node (as key) to an object (as value) which can be a Node, boolean, ...
• NodePath: A linked list of successive Nodes which forms a path

Algorithms Classes

• ShortestDistance\Dijkstra: Compute shortest distance with Dijkstra algorithm
• ShortestDistance\FloydWarshall: Compute shortest distance with FloydWarshall algorithm
• ShortestPath\AStar: Compute shortest path with AStar algorithm
• ShortestPath\Dijkstra: Compute shortest path with Dijkstra algorithm
• TravelingSalesman\NearestNeighbour: Compute shortest tour with NearestNeighbour algorithm
• TravelingSalesman\ThreeOpt: Improve shortest tour with ThreeOpt algorithm
• TravelingSalesman\TwoOpt: Improve shortest tour with TwoOpt algorithm

Converters Classes

• Grid\ASCIISyntax: Allow converting map with an ASCII syntax to NodeMap, NodePath, Node Objects back and forth

Distances Classes

• Chebyshev: Compute the Chebyshev distance between two nodes which is max(|dx|, |dy|)
• Euclidean: Compute the Euclidean distance between two nodes which is sqrt(|dx|^2 + |dy|^2)
• Manhattan: Compute the Manhattan distance between two nodes which is |dx| + |dy|
• Octile : Compute the Octile distance between two nodes which is (|dx| < |dy|) ? (sqrt(2) - 1) * |dx| + |dy|: (sqrt(2) - 1) * |dy| + |dx|
• Zero : Compute the null or zero distance between two nodes A and B which is always 0

Examples

ASCIISyntax for maps:

• Path: '.'
• Source: '>'
• Target: '<'
• Wall: 'X'

SSP solving:

    require __DIR__ . '/vendor/autoload.php';
    
    use Letournel\PathFinder\Algorithms;
    use Letournel\PathFinder\Converters\Grid\ASCIISyntax;
    use Letournel\PathFinder\Core;
    use Letournel\PathFinder\Distances;
    
    function solve($map, $algorithm)
    {
        $converter = new ASCIISyntax();
        $grid = $converter->convertToGrid($map);
        $matrix = $converter->convertToMatrix($map);
        $source = $converter->findAndCreateNode($matrix, ASCIISyntax::IN);
        $target = $converter->findAndCreateNode($matrix, ASCIISyntax::OUT);
        
        $algorithm->setGrid($grid);
        $starttime = microtime(true);
        $path = $algorithm->computePath($source, $target);
        $endtime = microtime(true);
        
        if($path instanceof Core\NodePath)
        {
            echo "Path found in " . floor(($endtime - $starttime) * 1000) . " ms\n";
            echo $converter->convertToSyntaxWithPath($grid, $path);
        }
        else
        {
            echo "No path found\n";
        }
    }
    
    $map =
        '                ' . "\n" .
        '.XXXXXX XXXXXXXX' . "\n" .
        ' X   XX<X  X    ' . "\n" .
        ' X X  XXX X   X ' . "\n" .
        '   X           >' . "\n" ;
    
    $distance = new Distances\Euclidean();
    $heuristic = new Core\Heuristic(new Distances\Euclidean(), 1);
    
    echo "Solving SSP with AStar:\n";
    solve($map, new Algorithms\ShortestPath\AStar($distance, $heuristic));
    echo "\n\n\n";
    
    echo "Solving SSP with Dijkstra:\n";
    solve($map, new Algorithms\ShortestPath\Dijkstra($distance));
    echo "\n\n\n";

Installation

Use composer:

{
    "require": {
        "letournel/path-finder" : "~1.0"
    }
}

Legal

Letournel/PathFinder is Copyright(c) 2015 Letournel

Code released under the MIT license