Using Graphp (the PHP library) is there a quick and easy way to enumerate all unique, loop-free paths between two nodes, or do i need to create an algorithm object to accomplish this?
Well, i took a stab at writing a quick and dirty recursive function rather than try and implement a graphp algorithm object... I need to do some testing and make sure its spitting back the data in the correct format, and its completely inefficient but I would appreciate some feedback as to better ways to get to where I want:
function Recursive_Find_Paths($GRAPH, $NODE, $DEST, $PATH = array(), $VISITED )
{
$PATHS = array();
array_push( $VISITED,$NODE->getId() ); // Add this node to the list of visited to prevent loops
if ( $NODE->getId() == $DEST->getId() ) { return array($PATH); } // SUCCESS! We found a path to the destination!
foreach ($NODE->getVerticesEdgeTo() as $NEXTNODE)
{
if ( in_array($NEXTNODE->getId(),$VISITED) ) { continue; } // SKIP nodes if we have already visited them!
$NEXTPATH = $PATH; $A = $NODE->getId(); $B = $NEXTNODE->getId();
$NEXTPATH["{$A}->{$B}"] = 0.9;
$MOREPATHS = Recursive_Find_Paths($GRAPH, $NEXTNODE, $DEST, $NEXTPATH, $VISITED);
if ( count($MOREPATHS) ) { $PATHS = array_merge($PATHS,$MOREPATHS); }
}
return $PATHS; // Return the recursively calculated list of paths...
}
It is returning what I am looking for (I chose an associative array so that I could later stick some Edge detail information with regard to each leg of the path)
Assuming a simple square with 4 Vertices 1->2, 1->3, 2->4, 3->4 I get this output:
Array
(
[0] => Array
(
[1->2] => 0.9
[2->4] => 0.9
)
[1] => Array
(
[1->3] => 0.9
[3->4] => 0.9
)
)
So I will keep playing with the code and see if i can come up with any better solutions. Thanks.