コンテンツにスキップ

Week 10 (2025/6/27)

今週の目的

グラフ上のノードをたどる。

今週のキーワード

  • グラフ上のウォーク（歩道）

今回はグラフの探索の準備として、隣接ノードを辿るプログラムを実装する。

課題1：グラフ上を歩く

前回実装したGraphクラスを継承し、隣接ノードを辿る以下のwalk(start, step)メソッドを備えたGraphWalkクラス定義せよ。ただし、訪問先のノードは近傍リストの先頭のノードとする。

なお、Graphクラスはdef_graph.pyモジュールのGraphクラスをインポートして用いること。

GraphWalkクラスの仕様は、以下の通りである。

GraphWalkクラス

class GraphWalk() Graphクラスのサブクラス
グラフ上のノードを辿ることができるクラス

walk(start, step)
指定されたノードから指定された数だけグラフ上のノードを辿る（ウォーク）メソッド

パラメータ

  • start: ウォークの開始ノードのID（文字列）
  • step: 辿る隣接ノードの数（整数）

次に、前回と同じkyotocitybus_line.datのデータを読み込んだGraphWalkインスタンスを用いて、ED01_1914から5ステップ分進むパスを出力せよ。なお、kyotocitybus_line.datは、「バス停ID バス停ID 京都市 路線名」のフォーマットで表されたエッジリストである。

week10_1.py
 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
# 穴埋め問題用のプログラム
from def_graph import Graph  # Graphクラスの読み込み

class GraphWalk(Graph):
    def walk(self, start, step):
        visited = [start]  # 開始地点のノードIDを訪問済みリストに追加
        parents = {start:None}  # 直前のノードとそれに接続するエッジのペア（タプル）を格納する辞書（key=訪問中ノードID、value=(直前のノードID, エッジラベル)）
        current = start  # 開始地点のノードIDを探索基点のノードに設定
        for i in range(step):  # step分、訪問を繰り返す
            if current not in self.node_list:  # 訪問中ノードが存在しなければ
                print('{}のノードがグラフ上に存在しません。'.format(current))
                return
            neighbors = self.get_neighborhood([____])  # 訪問中ノードの隣接ノードを取得
            if neighbors != []:  # 隣接ノードがあれば以下を実行
                visited.append(neighbors[0].id)  # 次の訪問先を訪問する
                parents[[____]] = ([____], neighbors[0].label)  # 訪問中ノードIDとそれに接続するエッジをparents辞書に追加
                current = [____]  # 訪問先候補を次の訪問先に決定
            else:  # 隣接ノードが無ければ終了
                print('{}から{}ステップ分進むパスはありません。'.format(start, step))
                return
        # 訪問したノードを訪問順に表示する
        path = visited[0]  # 最初に訪問したノードをpathに代入
        for v in visited[1:]:  # 訪問した順にノードを取得
            path = path + ' --[' + parents[v][1] +']--> ' + v  # 次の訪問先と辿ったエッジをpathに連結
        print(path)


if __name__ == '__main__':  # モジュールとしてインポートされるときは実行しない
    fi = open('kyotocitybus_line.dat', 'r', encoding = 'utf-8')
    bus_network = GraphWalk()
    lines = fi.readlines()
    for line in lines:
        line = line.rstrip()
        items = line.split(' ')  # 1行を半角スペースで区切ってitemsリストに代入
        bus_network.add_undirected_edge(items[0], items[1], items[3])  # 無向エッジを追加
    bus_network.walk('ED01_1914', 5)
    fi.close()

ED01_1914 --[快速202号系統]--> ED01_1936 --[快速202号系統]--> ED01_1914 --[快速202号系統]--> ED01_1936 --[快速202号系統]--> ED01_1914 --[快速202号系統]--> ED01_1936

課題2：グラフ上を巡回せずに歩く

課題1で作成したwalk(start, step)メソッドを改良し、訪問済みのノードの再訪を避ける、以下のwalk_without_loop(start, step)メソッドを定義せよ。

GraphWalkクラスのwalk_without_loopメソッドの仕様は、以下の通りである。

walk_without_loopメソッド

walk_without_loop(start, step)
指定されたノードから指定された数だけグラフ上の未訪問のノードを辿る（ウォーク）メソッド

パラメータ

  • start: ウォークの開始ノードのID（文字列）
  • step: 辿る隣接ノードの数（整数）

次に、kyotocitybus_line.datのデータを読み込んだGraphWalkインスタンスを用いて、ED01_1914からループせずに5ステップ分進むパスを出力せよ。課題1と結果が異なることに注意せよ。

ED01_1914 --[快速202号系統]--> ED01_1936 --[快速202号系統]--> ED01_1927 --[快速202号系統]--> ED01_1883 --[10号系統]--> ED01_1882 --[10号系統]--> ED01_1881

課題3：グラフ上の指定された道を歩く

課題1で作成したwalk(start, step)メソッドを改良し、指定したラベルのエッジを辿る、以下のwalk_along_route(start, step, route)メソッドを定義せよ。

GraphWalkクラスのwalk_along_routeメソッドの仕様は、以下の通りである。

walk_along_routeメソッド

walk_along_route(start, step, route)
指定されたノードから指定された数だけ、グラフ上の指定されたラベルに接続するノードを辿る（ウォーク）メソッド

パラメータ

  • start: ウォークの開始ノードのID（文字列）
  • step: 辿る隣接ノードの数（整数）
  • label: 隣接ノードに接続するエッジのラベル（文字列）

次に、kyotocitybus_line.datのデータを読み込んだGraphWalkインスタンスを用いて、ED01_1914から5ステップ分進む快速202号系統のパスを出力せよ。余力があれば、kyotocitybus_stop.datのデータも読み込み、バス停IDをバス停名に変換して表示せよ。

ED01_1914 --[快速202号系統]--> ED01_1936 --[快速202号系統]--> ED01_1927 --[快速202号系統]--> ED01_1883 --[快速202号系統]--> ED01_1930 --[快速202号系統]--> ED01_1742
Back to top