The idea is to have a method that will accept a set of unordered edges, and will return them ordered so that each edge is traversed.
The input of the function is an array of Edge instances (see src/DTO/Edge.php);
The has the same format as the input, but sorted :)
You need to have composer installed.
Once you have composer you need to run
cd /path/to/source && composer install
and then
./vendor/bin/phpunit -c .
The algorithm to order the edges is of linear complexity O(n).
The unordered edges array is scanned 4 times:
- to add metadata to each edge
- calculate the In-degree of the nodes
- select the starting point
- pick the next ordered edge
Licensed under the MIT license