東京公共交通オープンデータで経路検索してみる

## 概要
昨晩、[首都圏鉄道網のForce-Graph](https://qiita.com/t-mat/items/179252f159030e3932e7)（ネットワーク図）を作ったので、これで経路探査を試してみました。
また、ページをGithub.ioで公開しました。

- 【Github.io】[https://termat.github.io/tokyo-challenge-test_01/](https://termat.github.io/tokyo-challenge-test_01/)
- 【リポジトリ】[https://github.com/termat/tokyo-challenge-test_01](https://github.com/termat/tokyo-challenge-test_01)

始点と終点の駅を選択し、実行するとグラフの下に探索された経路が表示され、通過駅のノードが青に変更されます。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/55735/2ba3502d-e465-57fe-a07e-1940444dbe67.png" width="700">

## ソースコード
[前回](https://qiita.com/t-mat/items/179252f159030e3932e7)作成したrailway.jsonから駅と駅の接続状況を以下の様な表に整理し、始点（Ａ）から終点（Ｂ）までの経路を再帰で探査しています。
なお、距離や運賃等のコストは考慮せずに経路を探査しています。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/55735/75f361dd-ffa4-e1b6-858b-e2487e9ae2ca.png" width="600">

```html
<!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>
```

## 最後に
本当はノード（駅）だけではなく、リンク（経路）の色や太さも変えるべきなのですが、思い付きで作っていることもあり、今回は割愛しました。