PHP Array Routing

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

solodesignz
Forum Newbie
Posts: 10
Joined: Thu Jan 26, 2006 7:12 pm

PHP Array Routing

Post 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?
Last edited by solodesignz on Thu Jan 26, 2006 10:30 pm, edited 1 time in total.
User avatar
raghavan20
DevNet Resident
Posts: 1451
Joined: Sat Jun 11, 2005 6:57 am
Location: London, UK
Contact:

Post 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
solodesignz
Forum Newbie
Posts: 10
Joined: Thu Jan 26, 2006 7:12 pm

Post 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...
User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

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

?>
Last edited by Jenk on Fri Jan 27, 2006 3:46 am, edited 1 time in total.
solodesignz
Forum Newbie
Posts: 10
Joined: Thu Jan 26, 2006 7:12 pm

Post by solodesignz »

=/ I dont need to sort the lines... I need to generate the $routes from the lines
solodesignz
Forum Newbie
Posts: 10
Joined: Thu Jan 26, 2006 7:12 pm

Post 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 =/
User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

Post 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)
User avatar
raghavan20
DevNet Resident
Posts: 1451
Joined: Sat Jun 11, 2005 6:57 am
Location: London, UK
Contact:

Post 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
User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

Post 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.
User avatar
raghavan20
DevNet Resident
Posts: 1451
Joined: Sat Jun 11, 2005 6:57 am
Location: London, UK
Contact:

Post 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
User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

Post 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.)
User avatar
raghavan20
DevNet Resident
Posts: 1451
Joined: Sat Jun 11, 2005 6:57 am
Location: London, UK
Contact:

Post 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.
User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

Post 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.
User avatar
raghavan20
DevNet Resident
Posts: 1451
Joined: Sat Jun 11, 2005 6:57 am
Location: London, UK
Contact:

Post 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...
User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

Post 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..
Post Reply