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