Find all paths

[jumbo]

Hi guys

 

i'm trying to find all the paths from a starting node to an ending node in a network (refer to the attached pic)

 

what im doing is that i'm populating an array ($arr) with the connections that each node has with its neighbours.

 

then in  the function pathx, i'm trying to recursively find all paths that lead from a given starting node to a given ending node.

 

now 3 essential assumptions should be made in the algorithm that guarantee a right output:

 

1- don't forward to an incoming node (that is, if the path is 1 - 0 - 2, i cannot go back to 0 from 2)

2- dont forward to a node already in the sequence (that is, 1 - 0 - 2, i cannot go from 2 back to 1 because it's already there)

3- if u get to a node where the only next possible node is already in the sequence, dismiss that path (example: 0 - 1 - 3 - 4 - 5 - 2 ==> then from 2 u can only go to 0 or 1, which are already in the sequence... then the mistake was 5- 2, then from 5 u gotta find another path)

 

 

the code i've written so far returns promissing results, but i couldnt figure out how to implement the previous 3 essential points... my main problem is how to store and process the sequence during recursion (dynamically append new nodes or dismiss the entire sequence, or compare the new node to previous nodes in the sequence)

 

to see the results, comment the echo"arr[".$start."][".$i."]"; line (which shows how the recursion proceeds) and uncomment the other echos...

 

any help would be highly appreciated...

 

thanx

 

 

<?
$arr = array(0 => array(0=>1,1=>2));
$arr[1] = array(0=>0,1=>2,2=>3,3=>7);
$arr[2] = array(0=>0,1=>1,2=>5);
$arr[3] = array(0=>1,1=>4);
$arr[4] = array(0=>3,1=>5);
$arr[5] = array(0=>2,1=>6);
$arr[6] = array(0=>5,1=>7);
$arr[7] = array(0=>1,1=>6);


function pathx($arr, $prev, $start, $end)
{


 foreach ($arr[$start] as $i => $value)
{

 echo"arr[".$start."][".$i."]";


// echo $start.' - ';
 if ($arr[$start][$i] == $end)
 {
 echo $end;
//	 echo"<br>";
 }
 else 
 if ($arr[$start][$i] == $prev){echo" | ";}
 else
 {
	pathx($arr, $start, $arr[$start][$i], $end);
//	echo $arr[$start][$i].' - ';


}


}


}

?>

 

[attachment deleted by admin]

[jumbo]

the array actually looks like this

 

[attachment deleted by admin]

[jumbo]

no one has any answer?

[bobbinsbro]

working on it...

[bobbinsbro]

here you go:

<?php
$arr = array(0 => array(0=>1,1=>2));
$arr[1] = array(0=>0,1=>2,2=>3,3=>7);
$arr[2] = array(0=>0,1=>1,2=>5);
$arr[3] = array(0=>1,1=>4);
$arr[4] = array(0=>3,1=>5);
$arr[5] = array(0=>2,1=>6);
$arr[6] = array(0=>5,1=>7);
$arr[7] = array(0=>1,1=>6);


$solution = array(); //this array hold the valid path
$badResults = array(); //this array holds bad paths

//encase both arrays so i can return both arrays at once.
//$returnArray[0] = $solutions
//$returnArray[1] = $badResults
$returnArray = array($solution, $badResults);
$startPoint = 2; //obvious
$endPoint = 4; //ibvious

echo "the result is:<br>";

$result = findPath($arr, $startPoint, $endPoint, $returnArray); //call funtion
if (end($result[0]) == $endPoint){ //if endPoint exists in $solution, path was found. show path.
	print_r($result[0]);
}
else{ //else path was not found. display error.
	echo "No path found";
}

function findPath($inputArr, $startPoint, $endPoint, $returnArray){

	$returnArray[0][] = $startPoint; //save current point into the $solution array

	//if the endpoint is accessible, solution found = end the function successfuly.
	if (array_search($endPoint, $inputArr[$startPoint])){ 
		$returnArray[0][] = $endPoint;
		return $returnArray;
	}
	else{ //else, loop through all accessible connections
		foreach($inputArr[$startPoint] as $key => $value){
			//safty check - make sure we didn't find the endpoint already.
			//for some reason, this check is necessary for the succes of the function, so don't remove it.
			if (array_search($endPoint, $returnArray[0])){
				return $returnArray;
			}
			//if point was already used, save it as a badPoint (inaccessible)
			else if (array_search($value, $returnArray[0]) !== FALSE){
				//only save if not already saved as bad point. no need to clutter the array with duplications.
				if ((array_search($value, $returnArray[1])) === FALSE){
					$returnArray[1][] = $value;
				}
				continue;
			}
			//if this is a bad point, skip it and do nothing.
			else if (array_search($value, $returnArray[1])){
				continue;
			}
			//else, call recourse from this point to the endpoint, passing the updated $returnArray.
			else {
				$returnArray = findPath($inputArr, $value, $endPoint, $returnArray);
			}
		}
	}		
	return $returnArray; //return results. contains both $solutions and $badResults
}
?>

 

i tested this with a few different start/end points, with successful results.

 

please note that i did not use backtracking to find the optimal result. this just finds a result.

 

i tried to document everything to make it as easy as possible to understand, but if you have any questions about how it works, please ask.

 

there is one bit that i added for a good reason, but can no longer remember what that reason was. i tried to remove that bit of code, but that messed up the results, so i'm sure the reason was a good one. don't remove this bit, even though i have no idea why it's needed . in the documentation i mention which bit this is.

 

Edit - forgot to mention:

do not, under any circumstances, turn the "==="/"!==" into "=="/"!=". since array_search returns the key of the found value, the returned value can sometimes be 0, which is considered false if "=="/"!=" are used, which will mess up the results.

[jumbo]

thanx dude

 

ur code does return a valid result, which is great...

 

actually i need all possible paths between 2 endpoints... so im trying to work around ur code and see i can make that possible...

 

meanwhile any other input from anyone is most welcome!

 

thanx again

[bobbinsbro]

oh. whoops... didn't notice that... i'll see if i can figure it out.

[bobbinsbro]

since the function i gave you walk the input array by order of the sub-arrays contained within, getting many results may be easiest by running a loop in the global scope that re-orders the input-array and calls the function multiple times, once for each order. but you'd have to figure out how to make sure every new order is unique, which would probably be a new kind of pain in the rear-end...  :-\

[jumbo]

i see what u mean...

 

but im trying to do this differently... like having a new array each time i find a new possible path...

[jumbo]

NOTE: in the code, just call the function pathx like:

 

pathx($arr, 5, 5, 1, $parr, $x); //find all paths from 5 to 1, with 5 being supposedly the previous node for itself