使用graphp可以快速枚举两个节点之间的所有路径吗？

Question

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?

Answer 1

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.