基於圖結構實現地鐵乘坐線路查詢
- 2019 年 10 月 8 日
- 筆記
基於圖結構實現地鐵乘坐線路查詢
- github-python演算法和flaskapp部分：repo
- github-android部分：repo
- flaskapp介面文檔：傳送門
- 深度了解Dijkstra優化演算法：傳送門
- personblog:github_page or csdnblog
問題描述
編寫一個程式實現地鐵最短乘坐（站）線路查詢，輸入為起始站名和目的站名，輸出為從起始站到目的站的最短乘坐站換乘線路。
1.採用Dijkstra演算法實現，使用優先隊列對性能進行了優化；
2.如果兩站間存在多條最短路徑，則輸出其中的一條即可；
-
本次項目實現採用了flask作為後端提供介面服務，使用androidApp進行get請求獲得數據，顯示在Textview中
設計需求
- 確定儲存地鐵站文件的格式文件 （已確認使用json格式和文本格式）
- 確定讀取地鐵站數據的方式 （使用python的file打開命令）
- 確定獲取兩站點最小站點數的演算法方式
- 進行外表封裝
- 進行輸出格式的確定
- 性能測試
-
最後結果檢查
數據存儲格式
stationline.txt文本為存儲的地圖數據文本，格式如下圖所示：
- 使用0與1來分別表示是否需要換乘
地鐵線路條數 線路x 線路x站數 站名1 是否需要換乘 站名2 是否需要換乘 ... - 數據示例
2 20 曹庄 0 卞興 0 芥園西道 0 咸陽路 0 長虹公園 1 廣開四馬路 0 西南角 1 鼓樓 0 東南角 0 建國道 0 天津站 1 遠洋國際中心 0 順馳橋 0 靖江路 1 翠阜新村 0 嶼東城 0 登州路 0 國山路 0數據文本讀取程式碼
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)- 列印結果
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,.....}- 獲得點與點之間的最短路徑:
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演算法具體分析
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 部分
# 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中具體使用的函數分析
# 確定出發點和最後的站點 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_NUMflask app的分析：
- flask具體作用類似與springboot，是python後端的一個框架，對新手及其友好，而json包則是用來處理json輸出格式的一個工具
- 具體詳情查看flask官方中文文檔
# 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已經部署在伺服器上，返回資訊，請求方式等具體請查看介面文檔：傳送門
Android部分
- 編譯器使用AS進行開發
- 使用友好的流線式布局進行開發
- 布局程式碼如下:
<?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中的應該顯示的值
- 格式如下
<?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>- 程式碼控制：
.... 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的包
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); } }); }