PHP
MySQL
jQuery

PHPで駅をモデルにした最短経路問題を解く(2/4 SQL編)


あらすじ

前回書いた考え方をもとに最短経路問題もとい駅探もどきを作っていく。

先に成果物のビューをお見せします。

成果物 ⇦最終的にはこれを目指します。


今回の目的

前回示した工程のうち、以下のものを行なっていきます。

1.止まる電車と所属する路線idを持った駅テーブルを作る。

2.一本道になるルートをカンマで区切ったルートテーブルを作る。

3.駅テーブル~ルートテーブル間の中間テーブルを作り、ルートに応じた駅情報を抽出できるようにする。

4.ビューを作り、1~3のテーブルをphp内のSQLを駆使し必要なデータを抽出する、順番が逆になる駅があればUnionでひっくり返したものを引っ付ける。

隣接行列の元になるデータをSQLで引っ張ってくるところまで行きたいと思います。


テーブルを作ろう

まずは駅情報がなければ始まらないので駅テーブルを作っていきましょう。駅に必要な情報は並んでる駅順のID、どの路線にいるかがわかる路線ID、どの電車が止まるかの識別用のカラムです。idは駅順が望ましいです。泉岳寺から横浜方面にidを振り、枝に着いたら枝方向に振っていきます。枝の橋まで来たら分岐駅の続きから振っていきます。

(例)京急蒲田(分岐)⇨羽田空港国内線(枝終わり)⇨雑色

駅テーブル

列名
データ型
用途

name
varchar
駅名

rail_id
int
路線テーブルのid

local
tinyint
普通電車の有無

a_express
tinyint
急行電車の有無

l_express
tinyint
特急電車の有無

kl_express
tinyint
快特電車の有無

ak_express
tinyint
エアポート快特電車の有無

次に二駅を通るルートから駅情報を丸ごと引っ張るためにもう二つテーブルを用意します。

路線テーブル(駅-ルートの中間テーブル)

列名
データ型
用途

id
int

route_id
int

rails.png

ルートテーブル

列名
データ型
用途

belongs
varchar
1,2のようにカンマ区切られた複数の路線番号

ルート.png

路線テーブルとルートテーブルの見方ですがまずこの絵をみてください。



ルートは前回話した通り、一本道になるパターンをです。1番(泉岳寺〜京急蒲田)経由で一本道になるルートは[1,2],[1,3,4]、[1,3,5,6]、[1,3,5,7,8]、[1,3,5,7,9]の5つのパターンです。2番から、4番から、・・・と見ていくと計15本あります。それをカンマで区切って表現したのがルートテーブルです。SQLはカンマを区切りとして認識できる方法があるので、例えばbelongsカラムで「1と3を含む」を検索条件にすることができます。

路線テーブルは路線idと関係するルートを示したものです。1番は5つのルートに関係があるので5個データ作っています。なお枝の中継駅に関しては10,11,12,13のユニークな値を入れ、京急蒲田なら1,2,3三つの路線全てに関わるパターンを入力しています。

この三つのテーブルを合わせれば、一個のルートが分かれば必要な駅の情報は丸ごと引っ張ることができます。


フォームを作ろう

駅テーブルを作ったことで駅名を引っ張り出せるようになったので、簡単に検索用のビューを作っていきましょう。


index.php

<?php

//駅名一覧
try{
$pdo = new PDO("mysql:host=localhost; dbname=kktrain;charset=utf8","sample", "sample");
$sql = 'SELECT name FROM stations ';
$stmt = $pdo->prepare($sql);
$stmt->execute();
}catch (PDOException $e) {
print('接続失敗:' . $e->getMessage());
die();
}
while($result = $stmt->fetch(PDO::FETCH_ASSOC)){
$stations[] = $result;
}

//セレクトボックス作成ファンクション
function selectstation($name ,$stations){
$i = 1;
echo '<select name="' . $name . '">';
echo '<option disabled selected>選択してください</option>';
foreach($stations as $station){
foreach($station as $data){
echo '<option value="' . $i++ . '">'.$data.'</option>';
}
}
echo '</select>';
}
?>
<h4>乗り換え検索<h4>
<form action="" method="Post">
<h4>出発駅<h4>
<?php selectstation('d_station',$stations) ?>
<h4>到着駅<h4>
<?php selectstation('a_station',$stations) ?>
<input id="button" type="submit" value="検索" name="send">
</form>

<h4>結果<h4>
<div class="result"></div>


これで 乗り換え検索から結果までのビューは出来上がるはずです。まだ結果は出せませんのでしばらくご辛抱ください。

image.png

今回はPOSTを非同期通信で自分に投げて結果を表示する動きにしたので、ajaxを使用します。


sample.js

$(function(){

var appendhtml = "";
$(document).on('click','#button',function(){
event.preventDefault();
$.ajax({
url:"index.php",
data: {
d_station: $("select[name='d_station']").val(),
a_station: $("select[name='a_station']").val(),
send: $("input[name='send']").val(),
},
//json形式
dataType: 'json',
type: "POST"
}).done(function(response) {
$('.routes').remove();
var appendhtml;
console.log(response);
var station_name;
appendhtml = '<div class="routes">' + response + '</div>';
$('.result').append(appendhtml)
}).fail(function() {
alert("通信エラー");
});
});

});


戻り値が正常であれば、resultクラスのなかに結果を表示することができます。


ajax処理の注意事項

ajaxを使う場合は、もう一度このフォームのphpファイルを上から読む挙動になるようなので、初期の処理と、ajaxの処理を分けないといけません。何が起こるかというとフォームのHTMLの記述まで戻り値にしてしまいます。欲しい情報だけecho等で出すようにして、exitで終了すればOKです。


sample.php

session_start();

$result = "";
if(isset($_POST["send"]) && isset($_POST["d_station"] ) && isset($_POST["a_station"])){
//ajax用の処理
echo json_encode($result);
exit;
}else{
//初期の処理
//駅名一覧
}
//セレクトボックス作成ファンクション
//HTML


小話「POSTに持たせる情報」

僕「さてここからSQL書いて欲しい駅情報を抽出したいとこだけど、今のテーブルの形だと二つの駅idと二つの路線idがあれば抽出できるか、路線idもフォームで投げれるようにしようかな。」

先輩「それはよくないな。」

僕「というと?」

先輩「フォームに持たせる情報を増やすということは、悪意を持ったユーザーが手を出せる幅が広がることに繋がるよ、ブラウザで検証画面出すだけでもいじれてしまうからね。」

僕「セキュリティ上問題があるから、フォームのデータは最小限にしてphp内で処理しろってことですね。それだとSQLがかなり複雑になりそうですね。」

先輩「フォームの情報で足りないのが路線idであれば、先にSQLでそれだけ抽出して別にSQLを書けばいいよね。誰もSQL使っていいのは一回だけとは言ってないよ。」

僕「・・・なるほど、それもそうですね。(納得)」

POSTの情報は必要最低限にしよう。


SQLで駅情報を抽出しよう

POSTで二つの駅idは手に入れたので、ここから路線idをSQLで抽出しましょう。もし同じ駅を選んだ場合は警告だけ出して終了することをお忘れなく。


index.php

session_start();

$result = "";
if(isset($_POST["send"]) && isset($_POST["d_station"] ) && isset($_POST["a_station"])){
//ajax用の処理
if ($_POST["d_station"] !== $_POST["a_station"] ){
header("Content-Type: application/json; charset=UTF-8");//json形式で出力するときは必須
// 路線IDを抽出する
$d_station = get_rail($_POST["d_station"]);
$a_station = get_rail($_POST["a_station"]);

//中継の駅が選択された場合 本線の路線として路線idを振る。
$d_station["rail_id"] = $d_station["rail_id"] > 9? relay($d_station["rail_id"]) : $d_station["rail_id"];
$a_station["rail_id"] = $a_station["rail_id"] > 9? relay($a_station["rail_id"]) : $a_station["rail_id"];
try{
$pdo = new PDO("mysql:host=localhost; dbname=kktrain;charset=utf8","sample", "sample");
// 二駅に関係するルートIDを抽出する
$sql = "SELECT id,MIN(belongs) FROM `routes` WHERE FIND_IN_SET(" . $d_station["rail_id"] . ", `belongs`) and FIND_IN_SET(". $a_station["rail_id"] .", `belongs`)";
$stmt2 = $pdo->prepare($sql);
$stmt2->execute();
}catch (PDOException $e) {
print('接続失敗:' . $e->getMessage());
die();
}
while($result = $stmt2->fetch(PDO::FETCH_ASSOC)){
$route = $result;
}
}else{
echo json_encode("お前はもう到着している!");
exit;
}
}else{
//初期の処理
//駅名一覧
}
//セレクトボックス作成ファンクション
//路線id抽出ファンクション
function get_rail($input){
try{
$pdo = new PDO("mysql:host=localhost; dbname=kktrain;charset=utf8","sample", "sample");
$sql = 'SELECT id,rail_id FROM stations WHERE id in( '. $input . ')';
$stmt = $pdo->prepare($sql);
$stmt->execute();
}catch (PDOException $e) {
print('接続失敗:' . $e->getMessage());
die();
}
while($result = $stmt->fetch(PDO::FETCH_ASSOC)){
$stations = $result;
}
return $stations;
}
//中継駅が選択された時の路線id設定ファンクション
function relay($i){
switch ($i) {
case 10:
return 1;
break;
case 11:
return 3;
break;
case 12:
return 5;
break;
case 13:
return 7;
break;
}
}
//HTML


where句で[FIND_IN_SET]を使うと、カンマをデータ区切りとして認識した検索を使うことができます。


sample.php

    FIND_IN_SET(" . $d_station["rail_id"] . ", `belongs`)


中継駅を選択した時が少し特殊な動きになります。10~13という振り方をしたのでそのままだとルートidの検索に使えません。本線の路線として振り直します。

この処理で使うべきルートは確定したので、通り道の駅情報を一気に抽出します。


index.php

session_start();

$result = "";
if(isset($_POST["send"]) && isset($_POST["d_station"] ) && isset($_POST["a_station"])){
//ajax用の処理
if ($_POST["d_station"] !== $_POST["a_station"] ){
// 路線IDを抽出する
//中継の駅が選択された場合 本線の路線として路線idを振る。
// 二駅に関係するルートIDを抽出する
try{
$pdo = new PDO("mysql:host=localhost; dbname=kktrain;charset=utf8","sample", "sample");
// 対象駅を抽出する
//さらに並び替えが必要か判別する ①枝から下へ向かうとき ②下から上の枝に向かうとき つまり上側の枝の順番をひっくり返す。
if ($d_station["rail_id"]%2==0 && $d_station["rail_id"] < $a_station["rail_id"]){
$sql = "(" . "SELECT `stations`.* , 1 AS row FROM `stations`WHERE rail_id =" . $d_station["rail_id"] . " order by id DESC LIMIT 20000". ")UNION all(" . "SELECT`stations`.* , 2 AS row FROM `stations`, `routes`, `rails` WHERE `stations`.`rail_id` = `rails`.id and `rails`.route_id = `routes`.id and `routes`.id =". $route["id"] . " and `stations`.`rail_id`<> ". $d_station["rail_id"] ." order by id LIMIT 20000" . ")";
} else if($a_station["rail_id"]%2==0 && $d_station["rail_id"] > $a_station["rail_id"]){
$sql = "(" . "SELECT `stations`.* , 1 AS row FROM `stations`WHERE rail_id =" . $a_station["rail_id"] . " order by id DESC LIMIT 20000". ")UNION all(" . "SELECT`stations`.* , 2 AS row FROM `stations`, `routes`, `rails` WHERE `stations`.`rail_id` = `rails`.id and `rails`.route_id = `routes`.id and `routes`.id =". $route["id"] . " and `stations`.`rail_id`<> ". $a_station["rail_id"] ." order by id LIMIT 20000" . ")";
} else{
$sql = "SELECT`stations`.* FROM `stations`, `routes`, `rails` WHERE `stations`.`rail_id` = `rails`.id and `rails`.route_id = `routes`.id and `routes`.id =" . $route["id"] ;
}
$stmt3 = $pdo->prepare($sql);
$stmt3->execute();
}catch (PDOException $e) {
print('接続失敗:' . $e->getMessage());
die();
}
while($result = $stmt3->fetch(PDO::FETCH_ASSOC)){
$allstations[] = $result;
}
}else{
echo json_encode("お前はもう到着している!");
exit;
}
}else{
//初期の処理
//駅名一覧
}
//セレクトボックス作成ファンクション
//路線id抽出ファンクション
//中継駅が選択された時の路線id設定ファンクション
//HTML

SQLが複雑なのはルートによっては枝の順番をひっくり返さないとおかしくなるケースが存在するからです。その場合はunionでひっくり返した枝を引っ付けます。

長くなりましたが、これで最低限必要なデータは出揃いました。

泉岳寺と仲木戸を選んだ際の駅情報は下記の通りです。

情報.png

次回はこのデータから不要なデータを削りつつ、隣接行列に加工していこうと思います。

隣接行列編に続く