概要
昨晩、首都圏鉄道網のForce-Graph（ネットワーク図）を作ったので、これで経路探査を試してみました。
また、ページをGithub.ioで公開しました。
- 【Github.io】https://termat.github.io/tokyo-challenge-test_01/
- 【リポジトリ】https://github.com/termat/tokyo-challenge-test_01
始点と終点の駅を選択し、実行するとグラフの下に探索された経路が表示され、通過駅のノードが青に変更されます。
ソースコード
前回作成したrailway.jsonから駅と駅の接続状況を以下の様な表に整理し、始点（Ａ）から終点（Ｂ）までの経路を再帰で探査しています。
なお、距離や運賃等のコストは考慮せずに経路を探査しています。
<!DOCTYPE html>
<html>
<head>
<title>tokyo-challenge-test</title>
<link href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-ggOyR0iXCbMQv3Xipma34MD+dH/1fQ784/j6cY/iJTQUOhcWr7x9JvoRxT2MZw1T" crossorigin="anonymous">
<script src="https://code.jquery.com/jquery-3.4.1.min.js" integrity="sha256-CSXorXvZcTkaix6Yvo6HppcZGetbYMGWSFlBw8HfCJo=" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/5.9.2/d3.min.js"></script>
<script src="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/js/bootstrap.min.js" integrity="sha384-JjSmVgyd0p3pXB1rRibZUAYoIIy6OrQ6VrjIEaFf/nJGzIxFDsf4x0xIM+B07jRM" crossorigin="anonymous"></script>
</head>
<body>
<div class="container-fluid" style="width:600px;margin-left:30px;">
<div class="row">
<div class="col">
<div class="form-group">
<label for="select1">起 点</label>
<select id="select1" class="form-control">
</select>
</div>
</div>
<div class="col">
<div class="form-group">
<label for="select2">終 点</label>
<select id="select2" class="form-control">
</select>
</div>
</div>
<div class="col">
<button type="button" class="btn btn-primary" style="margin-top:30px;width:180px;" onclick="travers();">実 行</button>
</div>
</div>
</div>
<div>
<svg></svg>
</div>
<div id="result" style="margin-left:10px;"></div>
<script type="text/javascript">
let width = 1200;
let height = 750;
let baseMap;
const loadData = () => {
d3.json("railway.json").then(function(json) {
baseMap=createBaseTable(json);
createMap(json);
});
};
const createMap=(json)=>{
const rail=json.raillines;
const station=json.stations;
let nodes=[];
let links=[];
let check={};
let idv=0;
for(let i=0;i<rail.length;i++){
let sts=rail[i].stations;
let tmp=[];
for(let j=0;j<sts.length;j++){
if(!check[sts[j]]){
let p={id:idv++,label:station[sts[j]].name_ja,val:1};
tmp.push(p);
nodes.push(p);
check[sts[j]]=p;
$("#select1").append("<option>"+station[sts[j]].name_ja+"</option>");
$("#select2").append("<option>"+station[sts[j]].name_ja+"</option>");
}else{
check[sts[j]].val=check[sts[j]].val+1;
tmp.push(check[sts[j]]);
}
}
for(let i=1;i<tmp.length;i++){
let l={source:tmp[i-1].id,target:tmp[i].id};
links.push(l);
}
}
const svg = d3.select("svg").attr("width",width).attr("height",height);
const link = d3.select("svg")
.selectAll("line")
.data(links)
.enter()
.append("line")
.attr("stroke-width", 1)
.attr("stroke", "#ccc");
const node = d3.select("svg")
.selectAll("g")
.data(nodes)
.enter()
.append("circle")
.attr("r",function(d){return d.val*5;})
.attr("fill", "orange")
.call(d3.drag()
.on("start", dragstarted)
.on("drag", dragged)
.on("end", dragended));
const label = d3.select("svg")
.selectAll("g")
.data(nodes)
.enter()
.append("text")
.attr("text-anchor", "middle")
.attr("dominant-baseline", "middle")
.style("fill", "steelblue")
.style("font-size", "9px")
.text(function(d){return d.label;});
const simulation = d3.forceSimulation()
.force("link", d3.forceLink())
.force("center", d3.forceCenter(600, 450))
.force("charge", d3.forceManyBody().strength(-8))
.force("x", d3.forceX().strength(0.05).x(width / 2))
.force("y", d3.forceY().strength(0.05).y(height / 2));
simulation.nodes(nodes).on("tick", ticked);
simulation.force("link").links(links);
function ticked() {
link.attr("x1", function(d) { return d.source.x; })
.attr("y1", function(d) { return d.source.y; })
.attr("x2", function(d) { return d.target.x; })
.attr("y2", function(d) { return d.target.y; });
node.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; });
label.attr("x", function(d) { return d.x; })
.attr("y", function(d) { return d.y; });
}
function dragstarted(d) {
if(!d3.event.active) simulation.alphaTarget(0.3).restart();
d.fx = d.x;
d.fy = d.y;
}
function dragged(d) {
d.fx = d3.event.x;
d.fy = d3.event.y;
}
function dragended(d) {
if(!d3.event.active) simulation.alphaTarget(0);
d.fx = null;
d.fy = null;
}
const zoom = d3.zoom()
.scaleExtent([1/4,4])
.on('zoom', function(){
node.attr("transform", d3.event.transform);
link.attr("transform", d3.event.transform);
label.attr("transform", d3.event.transform);
});
svg.call(zoom);
}
function netTravaerse(data){
let stack=[];
let array=[];
stack.push(0);
traverse(data,0,stack,array);
return array;
}
function traverse(data,mark,stack,array){
for(let i=mark+1;i<data.length;i++){
if(data[mark][i]>=1){
stack.push(i);
traverse(data,i,stack,array);
if(stack.includes(data.length-1)){
array.push(Array.from(stack));
}
stack.pop();
}
}
}
function createBaseTable(json){
let table={};
let lines=json.raillines;
for(let i=0;i<lines.length;i++){
let st=lines[i].stations;
for(let j=0;j<st.length;j++){
if(!table[st[j]])table[st[j]]={};
}
for(let j=1;j<st.length;j++){
table[st[j-1]][st[j]]=1;
table[st[j]][st[j-1]]=1;
}
}
return table;
}
function createTravaseTable(baseTable,start,end){
let n=Object.keys(baseTable).length;
let table=new Array(n);
for(let i=0;i<n;i++){
table[i]=new Array(n).fill(0);
}
let map={};
let station=new Array(n);
let it=1;
for(let key in baseTable){
if(key==start){
map[key]=0;
station[0]=key;
}else if(key==end){
map[key]=n-1;
station[n-1]=key;
}else{
map[key]=it;
station[it++]=key;
}
}
it=0;
for(let key in baseTable){
let ll=baseTable[key];
for(let key2 in ll){
table[it][map[key2]]=ll[key2];
}
it++;
}
return {'station':station,'table':table};
}
function travers(){
$("#result").empty();
const st=$("#select1").val();
const ed=$("#select2").val();
if(st==ed)return;
let net=createTravaseTable(baseMap,st,ed);
let station=net.station;
let trip=netTravaerse(net.table);
if(trip.length==0){
alert("経路が見つかりませんでした。");
d3.selectAll("circle").style("fill","orange");
}else{
let tmp=[];
let mark={};
for(let i=0;i<trip.length;i++){
let t=[];
for(let j=0;j<trip[i].length;j++){
let ii=trip[i][j];
t.push(station[ii]);
mark[station[ii]]=1;
if(j==0){
$("#result").append(station[ii]);
}else{
$("#result").append("->"+station[ii]);
}
}
tmp.push(t);
$("#result").append("<br />");
}
d3.selectAll("circle").style("fill",function(d){
if(mark[d.label]==1){
return "blue"
}else{
return "orange"
}
});
}
}
loadData();
</script>
</body>
</html>
最後に
本当はノード（駅）だけではなく、リンク（経路）の色や太さも変えるべきなのですが、思い付きで作っていることもあり、今回は割愛しました。