, (*1)
fisharebest/algorithm
General purpose algorithms in PHP, (*2)
- Dijkstra
- Myers’ diff
- Connected/unconnected components of a graph
Installation
Install using composer., (*3)
composer require fisharebest/algorithm
Dijkstra
Dijkstra's algorithm finds the
shortest path(s) between two nodes in a weighted, directed graph., (*4)
Graphs are specified as an array of edges, each with a cost. The example below is
an undirected graph (i.e. if D→E is 9, then E→D is also 9.), because it is easy to
understand and easy to draw. However, the algorithm works equally well for directed
graphs, where links can be one-way only or have different costs in each direction., (*5)
D---9---E
/ \ \
14 2 6
/ \ \
A---9---B--11--C
\ / /
7 10 /
\ / /
F-----15 G
Sample code for the above graph., (*6)
``` php
$graph = array(
'A' => array('B' => 9, 'D' => 14, 'F' => 7),
'B' => array('A' => 9, 'C' => 11, 'D' => 2, 'F' => 10),
'C' => array('B' => 11, 'E' => 6, 'F' => 15),
'D' => array('A' => 14, 'B' => 2, 'E' => 9),
'E' => array('C' => 6, 'D' => 9),
'F' => array('A' => 7, 'B' => 10, 'C' => 15),
'G' => array(),
);, (*7)
$algorithm = new \Fisharebest\Algorithm\Dijkstra($graph);, (*8)
// There can be zero, one or more shortest (i.e. same total cost) paths., (*9)
// No shortest path.
$path = $algorithm->shortestPaths('A', 'G'); // array(), (*10)
// Exactly one shortest path.
$path = $algorithm->shortestPaths('A', 'E'); // array(array('A', 'B', 'D', 'E')), (*11)
// Multiple solutions with the same shortest path.
$path = $algorithm->shortestPaths('E', 'F'); // array(array('E', 'D', 'B', 'F'), array('E', 'C', 'F')), (*12)
// To find next-shortest paths, exclude one or more intermediate nodes from the shortest path.
$path = $algorithm->shortestPaths('A', 'E'); // array(array('A', 'B', 'D', 'E'))
$path = $algorithm->shortestPaths('A', 'E', array('B')); // array(array('A', 'B', 'D', 'E'))
$path = $algorithm->shortestPaths('A', 'E', array('D')); // array(array('A', 'B', 'C', 'E'))
$path = $algorithm->shortestPaths('A', 'E', array('B', 'D')); // array(array('A', 'F', 'C', 'E')), (*13)
## Myers’ diff
Find the difference between two sequences of tokens (characters, words, lines, etc.) using
“[An O(ND) Difference Algorithm and Its Variations](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927)”
by Eugene W. Myers.
The output can be interpreted as either:
* A series of instructions to transform the first sequence into the second sequence.
* A list of matches (tokens that appear in both sequences) and mismatches (tokens that appear in
just one sequence).
``` php
$x = array('a', 'b', 'c', 'a', 'b', 'b', 'a');
$y = array('c', 'b', 'a', 'b', 'a', 'c');
$algorithm = new MyersDiff;
$diff = $algorithm->calculate($x, $y);
// array(
// array('a', MyersDiff::DELETE), i.e. 'a' occurs only in $x
// array('b', MyersDiff::DELETE), i.e. 'b' occurs only in $x
// array('c', MyersDiff::KEEP), i.e. 'c' occurs both $x and $y
// array('b', MyersDiff::INSERT), i.e. 'b' occurs only in $y
// array('a', MyersDiff::KEEP), i.e. 'a' occurs in both $x and $y
// array('b', MyersDiff::KEEP), i.e. 'b' occurs in both $x and $y
// array('b', MyersDiff::DELETE), i.e. 'b' occurs only in $x
// array('a', MyersDiff::KEEP), i.e. 'a' occurs in both $x and $y
// array('c', MyersDiff::INSERT), i.e. 'c' occurs only in $y
// );
Connected components
A depth-first search of a graph to find isolated groups of nodes., (*14)
D E
/ \ \
/ \ \
A-----B C
\ /
\ /
F
Sample code for the above graph, (*15)
$graph = array(
'A' => array('B' => 1, 'D' => 1, 'F' => 1),
'B' => array('A' => 1, 'D' => 1, 'F' => 1),
'C' => array('E' => 1),
'D' => array('A' => 1, 'B' => 1),
'E' => array('C' => 1),
'F' => array('A' => 1, 'B' => 1),
);
$algorithm = new \Fisharebest\Algorithm\ConnectedComponent($graph);
$components = $algorithm->findConnectedComponents());
// array(
// 1 => array('A', 'B', 'D', 'F'),
// 2 => array('C', 'E'),
// );
Wallogit.com
