Page 1 of 2

PHP Array Routing

Posted: Thu Jan 26, 2006 7:13 pm
by solodesignz
Hey,

I am having a hard time trying to figure this out....

I have a list of arrays in this format:

Code: Select all

$line[0] = array(1, 2, 3, 4, 5);
$line[1] = array(6, 7, 9, 2, ;
$line[2] = array(2, 8, 9, 3, 13);
I need to generate a list of all available routes from point A to point B, for example:

Code: Select all

$start = 1;
$finish = 13;

// routes   -------I need help generating this!
$route[0] = array(1, 2, 8, 9, 13);
$route[1] = array(1, 2, 3, 13);
$route[2] = array(1, 2, 8, 9, 3, 13);
See how there are three possible routes with the given data? $route[1] being the smallest.
I need this pretty dynamic, having the ability to scale to alot of different routes, then I would return the one w/ the smallest number of stations (the numbers)

I just cant seem to figure out how to get code this to run through the array and generate thr routes.

Can anyone help me?

Posted: Thu Jan 26, 2006 7:54 pm
by raghavan20
Try this and post if you come across exceptions. For this example, it should print Route 2 which is route[2] as longest path and print Route 3 which is route[3] as shortest path.

Code: Select all

<?php

$start = 1; 
$finish = 13; 

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

$totalRoutes = count($route);
$length = array();

for ($i = 0; $i < $totalRoutes; $i++) {
	if (($startIndex = array_search($start, $route[$i])) >= 0 && ($endIndex = array_search($finish, $route[$i])) >= 0){
		$length[] = abs($endIndex - $startIndex);
	}
}


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";

?>
EDIT: complex example...where I put 1 after 13 in array....since I use abs() this works properly

Code: Select all

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

output (Remember value refer to array indexes):
Longest Route: 2
Shortest Route: 4

Posted: Thu Jan 26, 2006 10:03 pm
by solodesignz
Thank you...

great example for when I have the routes... but I need to generate the routes from the $lines, that is the part I cannot figure out...

Posted: Fri Jan 27, 2006 3:39 am
by Jenk
Try..

Code: Select all

<?php

$lines = array( /* lines data here, in multidimensional array.. */);
$routes = array();

$c = count($lines);

for ($i = 0; $i < $c; $i++) {
    if ((array_search($a, $lines[$i]) !== false) && (array_search($b, $lines[$i]) !== false)) {
        $routes[] = $lines[$i];
}

//$lines now contains all $routes that contain $a and $b;

?>

Posted: Fri Jan 27, 2006 3:42 am
by solodesignz
=/ I dont need to sort the lines... I need to generate the $routes from the lines

Posted: Fri Jan 27, 2006 3:42 am
by solodesignz
Ok... bascially I have a list of 50 stations, they reside on about 7 lines

Some stations belong on multiple lines, so this process needs to find routes from station A to station B.

The routes may need to jump onto new lines to reach their final destination.

$line[0] = array(1, 2, 3, 4, 5 );
Would be one line, with the various station Ids that are located on that line...

$line[1] = array(6, 7, 9, 2, 8 );
Would be another line with various station Ids... see how both have station 2, that means that these lines intersect at station 2

I hope this helps =/

Posted: Fri Jan 27, 2006 3:48 am
by Jenk
see my edit.

btw, none of the examples provided sort the arrays. raghavan20's example find the longest and shortest routes (something you will probably find useful...) and my example finds all routes which have both $a and $b in it. (Which is what your require, going by the initial request)

:)


Now then.. for the line changing .. I won't be able to assist until I get home tonight as I do not have access to a PHP parser here, so I can't test I'm afraid. But the solution would be a recursive function to loop through the arrays, and self submit a new starting station id (to the one the passenger must change at)

Posted: Fri Jan 27, 2006 5:47 am
by raghavan20

Code: Select all

<pre>
<?php

$start = 1; 
$finish = 13; 

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

$totalRoutes = count($route);
$length = array();

for ($i = 0; $i < $totalRoutes; $i++) {
	if (($startIndex = array_search($start, $route[$i])) >= 0 && ($endIndex = array_search($finish, $route[$i])) >= 0){
		$length[] = abs($endIndex - $startIndex);
	}
}

print_r($route);

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>
Output:

Code: Select all

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

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

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

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

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

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

)
Route - 0: 1->2->8->9->13Route - 1: 1->2->3->13Route - 2: 1->2->8->9->3->13Route - 3: 1->2->13Route - 4: 1->13Route - 5: 1->8->4->23->3->13Longest Route: 2Shortest Route: 4

Posted: Fri Jan 27, 2006 6:01 am
by Jenk
raghavan20 - what he wants is a journey planner for trains/buses, i.e. user enters departure station and destination, then the system outputs which trains/buses the passenger will need to get and where to change.

Posted: Fri Jan 27, 2006 6:37 am
by raghavan20
Jenk wrote:raghavan20 - what he wants is a journey planner for trains/buses, i.e. user enters departure station and destination, then the system outputs which trains/buses the passenger will need to get and where to change.
Let's say that you want to reach 13 from 1. I am listing all paths starting from shortest to longest to reach destination. Arrows represent the stations/points in between start and destination. There was a small problem in the above code...use this tested code...

Code: Select all

<pre>
<?php

$start = 1; 
$finish = 13; 

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

$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>
Output:

Code: Select all

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

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

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

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

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

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

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

)
Array
(
    [4] => 1
    [3] => 2
    [1] => 3
    [0] => 4
    [6] => 5
    [2] => 5
)
Routes are ordered by their length: 
Route numbers refer to array indexes.
Arrows represent the path to be taken to reach destination from start
Route - 4: 1->13
Route - 3: 1->2->13
Route - 1: 1->5->3->13
Route - 0: 1->2->8->9->13
Route - 6: 1->8->4->23->3->13
Route - 2: 1->2->8->9->3->13

Longest Route: 6
Shortest Route: 4

Posted: Fri Jan 27, 2006 6:48 am
by Jenk
But the routes are not predefined, only the lines.

He needs to be able to generate a system that will say "To get from A to B, you will need to jump on Line1 at station x, then transfer at station y, transfer again at station z, then you will reach your destination B.)

Posted: Fri Jan 27, 2006 6:55 am
by raghavan20
Jenk wrote:But the routes are not predefined, only the lines.

He needs to be able to generate a system that will say "To get from A to B, you will need to jump on Line1 at station x, then transfer at station y, transfer again at station z, then you will reach your destination B.)
Let's assume that you want to go from Birmingham to Manchester. There are routes/trains available from London, Milton Keynes, Oxford, Coventry to Manchester. So, the passenger can take any of the routes and these are predefined. The values in the route array, define the stations in the entire route (something like TUBE lines, say piccadily line). We start with finding routes from all available routes in UK that have Birmingham and Manchester stations in their route. So we first look for existance of these two stations, then sort the routes by shortest path and we draw the route from Birmingham to Manchester with arrows marks indicating stations in between them. This is the best way so far I could think of and you have to develop relevant inputs according to this strategy. The output generated from the code I have provided, explains the same.

Posted: Fri Jan 27, 2006 7:00 am
by Jenk
But what happens if the quickest route has only one of the stations in? This is what I am referring to.

Simple way to explain:

Train1 goes from A to B, to C.

Train2 goes from C to B, to D.

Passenger wants to go from A to D.

Posted: Fri Jan 27, 2006 7:04 am
by raghavan20
Jenk wrote:But what happens if the quickest route has only one of the stations in? This is what I am referring to.

Simple way to explain:

Train1 goes from A to B, to C.

Train2 goes from C to B, to D.

Passenger wants to go from A to D.
you could have given me this example a lot earlier:wink: ...now I have to think ...this is a bit complex...so what i gave was only for people taking direct trains....i will think of the logic for the new problem...

Posted: Fri Jan 27, 2006 7:08 am
by Jenk
This is why I referred to a recursive function that breaks up the route into smaller routes, I can't test any of my logic out yet (no parser here) so it'll have to wait till I get home, but I have got in my head some logic for finding atleast a 1 change route.

multiple changes pose a bigger challenge..