Page 2 of 2

Posted: Fri Jan 27, 2006 8:41 am
by raghavan20
This allows to find routes where a connection can help reach destination from start point
for ex: this can find...
route 1: 1, 4, 10
route 2: 4, 13, 3, 6
start: 1
destination:13
this will print: 1->4>13
This basically finds one level of connection.....

Code: Select all

<pre>
<?php
error_reporting(E_ALL);

$start = 1; 
$finish = 13; 

// routes 
$route[0] = array(7, 9, 13); 
$route[1] = array(4, 5, 3, 13); 
$route[2] = array(2, 8, 9, 3); 
$route[3] = array(1, 2, 13);
$route[4] = array(3, 5, 2, 13);
$route[5] = array(7, 2, 23, 4, 8, 1);
$route[6] = array(3, 7, 2, 13, 3, 23, 4, 8, 1);


findNonDirectRoutes($start, $finish, $route);

function findNonDirectRoutes($start, $finish, $route){
	$totalRoutes = count($route);
	$length = array();
	$startMatches = array();
	$finishMatches = array();
	print_r($route);
	//find start and end stations routes matches
	for ($i = 0; $i < $totalRoutes; $i++) {
		if ((in_array($start, $route[$i]) === TRUE) xor (in_array($finish, $route[$i]) === TRUE) ){
			if (in_array($start, $route[$i]) === TRUE){
				 $startMatches[] = $i;
			}else{
				 $finishMatches[] = $i;
			}
		}
	}
	
	//DEBUG//echo "<br />Start matches:"; print_r($startMatches);
	//DEBUG//echo "<br />End matches:"; print_r($finishMatches);
	
	//find available connections
	$connectionMatches = array();
	$counter = 0;
	foreach ($startMatches as $startKey => $startRoute){
		for ($k = 0; $k < count($route[$startRoute]); $k++){
			foreach ($finishMatches as $finishKey=>$finishRoute){
				if ($startRoute != $finishRoute){//avoid comparing with same route
					for ($j = 0; $j < count($route[$finishRoute]); $j++){
						/*echo "<br/> startRoute - $k - $finishRoute - $j : {$route[$startRoute][$k]} <-> {$route[$finishRoute][$j]}";*/
						if ($route[$startRoute][$k] == $route[$finishRoute][$j] && $route[$startRoute][$k] != 	$start && $route[$finishRoute][$j] != $finish){
							$connectionMatches[$counter]["StartRoute"] = $startRoute;
							$connectionMatches[$counter]["FinishRoute"] = $finishRoute;
							$connectionMatches[$counter++]["ChangePoint"] = $route[$startRoute][$k];
						}	
					}
				}
			}	
		}
	}
	//DEBUG//echo "<br />Connection matches:"; print_r($connectionMatches);
	
	foreach($connectionMatches as $connection){
		echo "<br />Route: {$connection["StartRoute"]} -> {$connection["ChangePoint"]} -> {$connection["FinishRoute"]}";
	}

}

function findDirectRoutes($start, $finish, $route){
	$totalRoutes = count($route);
	$length = array();
	for ($i = 0; $i < $totalRoutes; $i++) {
		if ((in_array($start, $route[$i]) === TRUE) && (in_array($finish, $route[$i]) === TRUE) ){
			$length[$i] = abs(array_search($finish, $route[$i]) - array_search($start, $route[$i]));
		}
	}
	
	asort($length);
	print_r($route);
	print_r($length);
	echo "<br /><b>Routes order by their length: Route numbers refer to array indexes.<br />Arrows represent the path to 

be taken 
	
	to reach destination from start</b>";
	foreach($length as $key => $value){
		$startIndex  = array_search($start, $route[$key]) ;
		$endIndex = array_search($finish, $route[$key]);
	
		echo "<br />"."Route - $key: ";
		//DEBUG//echo "start index - $startIndex : end index = $endIndex <br />";
	
		if ($startIndex > $endIndex){ 
			for ($j = $startIndex; $j >= $endIndex; $j--){
				echo ($j != $endIndex)? $route[$key][$j]."->" : $route[$key][$j];
			}
		}else {
			
			for ($j = $startIndex; $j <= $endIndex; $j++){
				echo ($j != $endIndex)? $route[$key][$j]."->" : $route[$key][$j];
			}
		}
	}
	
	echo "<br /><br /><br /><br />";
	echo (is_array($length)) ? "Longest Route: ".array_search(max($length), $length) : "No path found"; echo "<br />";
	echo (is_array($length)) ? "Shortest Route: ".array_search(min($length), $length) : "No path found";
}
?>
</pre>

Code: Select all

Array
(
    [0] => Array
        (
            [0] => 7
            [1] => 9
            [2] => 13
        )

    [1] => Array
        (
            [0] => 4
            [1] => 5
            [2] => 3
            [3] => 13
        )

    [2] => Array
        (
            [0] => 2
            [1] => 8
            [2] => 9
            [3] => 3
        )

    [3] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 13
        )

    [4] => Array
        (
            [0] => 3
            [1] => 5
            [2] => 2
            [3] => 13
        )

    [5] => Array
        (
            [0] => 7
            [1] => 2
            [2] => 23
            [3] => 4
            [4] => 8
            [5] => 1
        )

    [6] => Array
        (
            [0] => 3
            [1] => 7
            [2] => 2
            [3] => 13
            [4] => 3
            [5] => 23
            [6] => 4
            [7] => 8
            [8] => 1
        )

)
Route: 5 -> 7 -> 0
Route: 5 -> 2 -> 4
Route: 5 -> 4 -> 1

Posted: Fri Jan 27, 2006 11:50 am
by solodesignz
Wow thanks guys for all the input, I'm hoping someone can figure this out, because I cant for the life of me =/

Ive been running some tests with array_intersect() - finds all the intersections

But haven't been able to figure anything out yet...

Posted: Fri Jan 27, 2006 12:21 pm
by solodesignz
Here is an image to maybe make this alittle easier to get the route thing
Image

So we have two lines

Code: Select all

$line[0] = array(2, 6, 3, 9, 5);
$line[1] = array(8, 4, 10, 3, 14, 11, 7);

$intersections = array_intersect($line[0], $line[1]);
So the code starts out with the $lines (Generated from database);

Then PHP needs to genereate some how all routes from Point A to Point B...

So for this example Station 8 to Station 9 would have an intersection at Station 3, and one route (Only one for this basic example) would be:

Code: Select all

$route[0] =  array(8, 4, 10, 3, 9);
Hope this helps some more

Posted: Fri Jan 27, 2006 2:26 pm
by solodesignz
Does this help any? (Post from another forum)
Is there any chance you could change the storage format to a directed graph? Most standard path finding algorithms work on directed graphs and none of this is for the faint of heart so I hope you're sure it's necessary :shifty: p

this looked like a chanllenge so I figured I'd pseudo code it for you. My array skills with php aren't strong enough to do it for you but the following logic will find all routes from a starting point to an ending point with a variable number of arrays.

Code: Select all

for(x=0; x < number of arrays; x++)
look for a starting point in array[x]

	if a start point was found
		for(y=0; y < number of arrays; y++)
		look for a ending point in array[y]

			if a start and ending point are found
			find an intersection of array[x] and array[y]

				if an intersection of array[x] and array[y] is found populate a result array
http://en.wikipedia.org/wiki/Shortest_path_problem
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Posted: Fri Jan 27, 2006 3:10 pm
by raghavan20
for basic one level of intersection, the code that I have given you should work. I do not know whether you tried it with other examples. Try your example with my code; the pseudo code is more similar to what I have done.

Posted: Fri Jan 27, 2006 3:17 pm
by solodesignz
I need it to be able to handdle multiple intersections, I guess that can be limited to maybe 4 levels deep or something if it needs to be a static number.

I tested your code out, it didnt seem to handle it correct..

say there is a function getRoute... this is what it should do:

Code: Select all

$lines[0] = array(1, 2, 3, 4, 5);
$lines[1] = array(6, 7, 9, 2, ;
$lines[2] = array(2, 8, 9, 3, 13);

print_r(getRoute($lines, 1, 13));
Should give you:

Code: Select all

/*
    prints:
    
        Array
        (
            [0] => 1
            [1] => 2
            [2] => 3
            [3] => 13
        )
*/