基于图结构实现地铁乘坐线路查询

发表于

基于图结构实现地铁乘坐线路查询

问题描述

编写一个程序实现地铁最短乘坐（站）线路查询，输入为起始站名和目的站名，输出为从起始站到目的站的最短乘坐站换乘线路。

1.采用Dijkstra算法实现，使用优先队列对性能进行了优化；
2.如果两站间存在多条最短路径，则输出其中的一条即可；

  • 本次项目实现采用了flask作为后端提供接口服务，使用androidApp进行get请求获得数据，显示在Textview中

    设计需求

  • 确定储存地铁站文件的格式文件 （已确认使用json格式和文本格式）
  • 确定读取地铁站数据的方式 （使用python的file打开命令）
  • 确定获取两站点最小站点数的算法方式
  • 进行外表封装
  • 进行输出格式的确定
  • 性能测试
  • 最后结果检查

数据存储格式

stationline.txt文本为存储的地图数据文本，格式如下图所示：

  • 使用0与1来分别表示是否需要换乘
1
2
3
4
5
地铁线路条数
线路x 线路x站数
站名1 是否需要换乘
站名2 是否需要换乘
...
  • 数据示例
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    2 20
    曹庄 0 
    卞兴 0
    芥园西道 0
    咸阳路 0
    长虹公园 1
    广开四马路 0
    西南角 1
    鼓楼 0
    东南角 0
    建国道 0
    天津站 1
    远洋国际中心 0
    顺驰桥 0
    靖江路 1
    翠阜新村 0
    屿东城 0
    登州路 0
    国山路 0

数据文本读取代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
with open(os.path.join(os.path.abspath('..'), "station/stationLine.txt"), "r") as f:
    TOTAL = f.readline()
    for line in f.readlines():
        if line != '\n':
            line = line.rstrip('\n')
            line = line.split(' ')
            if line[0] in LINEDATA:
                linei = line[0]
                continue
            line[1] = linei
            line0 = line[0]

            intline = int(line[1])
            if intline not in data.keys():
                data[intline] = []
                data[intline].append(line0)
            else:
                data[intline].append(line0)
            if line0 not in datanum.keys():
                datanum[line0] = [intline]
            else:
                datanum[line0].append(intline)

  • 打印结果

    1
    2
    3
    4
    5
    stationline {"1": ["刘园", "西横堤", "果酒厂", "本溪路", "勤俭道", "洪湖里", "西站", "西北角", ..]}

    linesdata {"刘园": [1], "西横堤": [1], "果酒厂": [1], "本溪路": [1], "勤俭道": [1], "洪湖里": [1], "西站": [1, 6], "西北角": [1], "西南角": [1, 2], "二纬路": [1], "海光寺": [1], "鞍山道": [1], "营口道": [1, 3], "小白楼": [1], "下瓦房": [1, 5],....}

    station_num {"刘园": 0, "西横堤": 1, "果酒厂": 2, "本溪路": 3, "勤俭道": 4, "洪湖里": 5, "西站": 6, "西北角": 7, "西南角": 8, "二纬路": 9, "海光寺": 10, "鞍山道": 11, "营口道": 12, "小白楼": 13, "下瓦房": 14,.....}

  • 获得点与点之间的最短路径:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def find_shortest_path(graph, start, end, path=[]):
    # 查找最短路径
    path = path + [start]
    if start == end:
        return path
    if not start in graph.keys():
        return None
    shortest = None
    for node in graph[start]:
        if node not in path:
            newpath = find_shortest_path(graph, node, end, path)
            if newpath:
                if not shortest or len(newpath) < len(shortest):
                    shortest = newpath
    return shortest

def find_all_paths(graph, start, end, path):
    # 查找所有的路径
    path = path + [start]
    if start == end:
        return [path]
    if not start in graph.keys():
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths
    
pathss = {}
for i in range(I):
    for j in range(I):
        if RouteGraph.get_edge(i, j) == 1:
            start = STATIO[i]
            end = STATIO[j]
            if i not in pathss.keys():
                pathss[i] = [j]
            else:
                pathss[i].append(j)
# pathss是记录每个站点接触的站点list
# print(pathss)

  • dijkstra算法具体分析

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    def dijkstra_shortest_pathS(graph, v0, endpos):
        vnum = 0
        for i in pathss.keys():
            vnum += 1
            
        assert 0 <= v0 < vnum
        # 长为vnum的表记录路径
        paths = [None] * vnum
        count = 0
        
        cands = PrioQueue([(0, v0, v0)])
        while count < vnum and not cands.is_empty():
            plen, u, vmin = cands.dequeue()  
            if paths[vmin]:  
                continue
            paths[vmin] = (u, plen)  
            # print(u, plen)
            for v in graph[vmin]:  
                if not paths[v]:  
                    cands.enqueue((plen + 1, vmin, v))
            count += 1
        return paths

  • stationController 部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# encoding=utf-8
import os
import json

from stationplan import computefshortestpath
from stationplan import getInfo


def getShort(start, end):
    stationnum, s = computefshortestpath(start, end)
    return stationnum, s


def getInfoStation():
    stationnumlist, stationlist = getInfo()
    return stationnumlist, stationlist


if __name__ == "__main__":
    a, b = getInfoStation()
    print(type(a))
    print(type(b))
  • stationController中具体使用的函数分析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 确定出发点和最后的站点
def computefshortestpath(startpos, endpos):
    s1 = STATION_NUM[startpos]
    e1 = STATION_NUM[endpos]
    # print(s1,e1)
    paths = dijkstra_shortest_pathS(pathss, s1, e1)
    # print(paths)
    b = []
    p = paths[e1][0]
    # print(paths[e1])
    b.append(STATIO[p])
    while True:
        p1 = paths[p][0]
        p = p1
        b.append(STATIO[p])
        if p == s1:
            break
    b.reverse()
    if s1 != e1:
        b.append(STATIO[e1])
    stationnumo = len(b)

    s = ""
    s += b[0]
    for i in range(1, len(b) - 1):
        a1 = set(datanum[b[i - 1]])
        b1 = set(datanum[b[i + 1]])
        c1 = set(datanum[b[i]])
        # 如果没有交集，说明不是同一条路,对当前站点前后站点进行分析，如果两个站点属于
        # 的站点线号没有发生重叠，说明当前线路在该站点没有进行换乘
        if not len(a1 & b1):
            if len(datanum[b[i + 1]]) != 0:
                s += "-" + str((list(set(datanum[b[i]]) & b1)[0])) + "号线"
            s += "-" + b[i]
        else:
            s += "-" + b[i]
    s += "-" + b[len(b) - 1]
    return stationnumo, s

def getInfo():
    return data, STATION_NUM

flask app的分析：

  • flask具体作用类似与springboot，是python后端的一个框架，对新手及其友好，而json包则是用来处理json输出格式的一个工具
  • 具体详情查看flask官方中文文档
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# encoding=utf-8
from flask import Flask, request
from stationController import getShort
from stationController import getInfoStation
import json

app = Flask(__name__)

@app.route('/getStationInfo', methods=['GET'])
def getStationInfo():
    num = request.args["num"]
    num = int(num)
    data, stationlist = getInfoStation()
    if not num:
        result = {
            "code": 500,
            "msg": "the service make a mistake -.-"
        }
    else:
        strmsg = data[num]
        print(strmsg)
        result = {
            "code": 0,
            "msg": strmsg
        }
    return json.dumps(result)


@app.route('/getShortestPath', methods=['GET'])
def getShortestPath():
    start = request.args['start']
    end = request.args['end']
    data, stationlist = getInfoStation()
    print(start not in stationlist.keys() and end not in stationlist.keys)
    if (not start or not end) or (start not in stationlist.keys() or end not in stationlist.keys()):
        result = {
            "code": 501,
            "msg": "please input the correct start and end station -.-"
        }
    else:
        stationnum, strmsg = getShort(start, end)
        result = {
            "code": 0,
            "msg": strmsg,
            "stationnum": stationnum
        }

    return json.dumps(result)


if __name__ == '__main__':
    app.run(host="0.0.0.0", port=80)
  • flask具体demo已经部署在服务器上，返回信息，请求方式等具体请查看接口文档：传送门

安卓部分

  • 编译器使用AS进行开发
  • 使用友好的流线式布局进行开发
  • 布局代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
<?xml version="1.0" encoding="utf-8"?>

<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="10dp"
    android:paddingLeft="10dp"
    android:paddingRight="10dp"
    android:paddingTop="30dp"
    android:orientation="vertical"
    tools:context=".MainActivity" >

    <TextView
        android:id="@+id/textView1"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:text="请选择站点线路起点线" />

    <LinearLayout
        android:layout_width="match_parent"
        android:layout_height="141dp"
        android:layout_gravity="center"
        android:orientation="vertical">

        <Spinner
            android:id="@+id/spinner1"
            android:layout_width="match_parent"
            android:layout_height="50dp" />

        <Spinner
            android:id="@+id/spinner2"
            android:layout_width="match_parent"
            android:layout_height="50dp"
            android:layout_marginTop="20dp" />
    </LinearLayout>

    <TextView
        android:id="@+id/textView2"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:text="请选择站点线路终点线" />

    <LinearLayout
        android:layout_width="match_parent"
        android:layout_height="141dp"
        android:layout_gravity="center"
        android:orientation="vertical">

        <Spinner
            android:id="@+id/spinner3"
            android:layout_width="match_parent"
            android:layout_height="50dp" />

        <Spinner
            android:id="@+id/spinner4"
            android:layout_width="match_parent"
            android:layout_height="50dp"
            android:layout_marginTop="20dp"

            />
    </LinearLayout>
    <Button
        android:id="@+id/searchButton"
        android:layout_width="match_parent"
        android:layout_height="40dp"
        android:text="搜索最短路线">
    </Button>

    <TextView
        android:id="@+id/showShortestPath"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:text="">
    </TextView>
</LinearLayout>

  • 对与spinner（下拉框的集联操作使用xml进行了储存）

  • 当选中相应的station值时进行选择第二个spinner中的应该显示的值

  • 格式如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    <?xml version="1.0" encoding="utf-8"?>
        <resources>
            <string-array name="station">
                <item>-站点线路-</item>
                <item>1</item>
                <item>2</item>
                <item>3</item>
                <item>5</item>
                <item>6</item>
                <item>9</item>
             </string-array>
             <string-array name="station1">
                 <item>-站点-</item>
                 <item>刘园</item>
                 <item>西横堤</item>
                 <item>果酒厂</item>
                 <item>本溪路</item>
                 <item>勤俭道</item>
                 <item>洪湖里</item>
                 <item>西站</item>
                 <item>西北角</item>
                 <item>西南角</item>
                 <item>二纬路</item>
                 <item>海光寺</item>
                 <item>鞍山道</item>
                 <item>营口道</item>
                 <item>小白楼</item>
                 <item>下瓦房</item>
                 <item>南楼</item>
                 <item>土城</item>
                 <item>陈塘庄</item>
                 <item>复兴门</item>
                 <item>华山里</item>
                 <item>财经大学</item>
                 <item>双林</item>
                 <item>李楼</item>
             </string-array>
       			......
         </resources>

  • 代码控制：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
if (pro.equals("1")) {
     cityAdapter = ArrayAdapter.createFromResource(
             MainActivity.this, R.array.station1,
             android.R.layout.simple_spinner_dropdown_item);
     sr4.setAdapter(cityAdapter);
     sr4.setOnItemSelectedListener(new AdapterView.OnItemSelectedListener() {
         @Override
         public void onItemSelected(AdapterView<?> parent, View view, int position, long id) {

             String strstation = MainActivity.this.getResources().getStringArray(R.array.station1)[position];
             sr4Val = strstation;
         }

         @Override
         public void onNothingSelected(AdapterView<?> parent) {

         }

     });
} 
.....
  • demo图
    在这里插入图片描述
  • 使用okhttps获得json数据，get方式
  • 相应的as添加jar包方式：
  • 打开路径：file->project Structure->Depndences->app->+号 搜索相应的包即可
  • 博主用的是 okhttp:2.7.5的包

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public void SendGetRequest(final String url,final String startpos,final  String endpos){

        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    OkHttpClient client = new OkHttpClient();//创建OkHttpClient对象
                    Request request = new Request.Builder()
                            .url("http://139.9.90.185/getShortestPath?start="+startpos+"&end="+endpos)//请求接口。如果需要传参拼接到接口后面。
                            .build();//创建Request 对象
                    Response response = null;
                    response = client.newCall(request).execute();//得到Response 对象
                    if (response.isSuccessful()) {
                        Log.d("kwwl","response.code()=="+response.code());
                        Log.d("kwwl","response.message()=="+response.message());
//                        Log.d("kwwl","res=="+response.body().string());
                        String resdata = response.body().string();
                        System.out.println(resdata);

                        //此时的代码执行在子线程，修改UI的操作请使用handler跳转到UI线程。
                            JSONObject jsonObject = new JSONObject(resdata);
                            String code = (jsonObject.getString("code"));
                            if(Integer.parseInt(code)==0) {
                                String resultpath = (jsonObject.getString("msg"));
                                String resultnum = (jsonObject.getString("stationnum"));
                                show("站点数:" + resultnum + "\n" + "站点最短路径:" + resultpath);
                                Toast.makeText(MainActivity.this,"正在搜索中,请稍后",Toast.LENGTH_SHORT).show();
                            }else{
                                String msg = (jsonObject.getString("msg"));
                                show("提示信息:"+msg);
                                Toast.makeText(MainActivity.this,"提示信息:"+msg,Toast.LENGTH_SHORT).show();
                            }
//                            System.out.println(result);
                    }else{
                        show("请求出错,请选择正确的站点请求");
                        Toast.makeText(MainActivity.this,"请求出错,请选择正确的站点请求",Toast.LENGTH_SHORT).show();
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }).start();


    }
 //显示在下方的TextView中
    private void show(final String result) {
        runOnUiThread(new Runnable() {
            @Override
            public void run() {
                textShowPaths.setText(result);
            }
        });
    }