📈

有向グラフの閉ループ確認に、深さ優先探索を使う(JS)

2025/01/18に公開

使いたい

こうしてZennで記事を書くのは初めてだ。書き味は良い。

経緯

作り途中のサービスで、グラフの正しい閉ループを検出する必要があった。グラフはノードと向きを持つリンクからなる。ノードのうち二つはスタートとゴールであって、ほかはなんの性質も持たせない。

グラフの表現方法

ノードの表現

これは単純な文字列として表現する。スタートならstart 、ゴールならgoal。他は番号を振るだけだ。

リンクの表現

以下のように宣言する。

  let groupedRoutes = {
    start: [1, 2, 3],
    1: [4],
    2: [4],
    3: [5],
    4: ["goal"],
    5: ["goal"],
    goal: ["start"],
  };

オブジェクトとして表現する。ノードの固有IDをオブジェクトのキーとし、値はそのオブジェクトを始点でどこに向いてリンクが貼られているかを表す。上記の場合はスタートから1,2,3へリンクがつながっていることがわかる。

正しい閉ループ/異常なルートの定義

ここでは正しい閉ループを以下のように定義した。
「スタートからゴールまで辿ることができ、なおかつゴールからスタートへ戻れるルートのこと」

異常なルートとはそれ以外のルートである。例えば以下のケースだ。

  • スタートから辿れない
  • スタートから辿ることができるが、終点がゴールにつながっていない
  • スタートから辿ることができるが、途中でスタート以外の閉ループをつくっている

メソッドの構想

異常なルートを検出させるためのメソッドを考える。深さ優先探索を再帰を用いて実装するというのは頭にあった。おおまかな処理の流れを書く。

  1. 初期設定
  2. 現在地から行けるルートをリストアップ
  3. リストアップしたルートに対してfor文を回す
  4. ルートは訪問済みか/ 訪問済みなら5 訪問済みでないなら6
  5. そのルートを通る/訪問済みにする/2を実行(再帰)
  6. for文おわり

最終的なコード

function findInvalidRoutesSetByDFS(groupedRoutes, startNode, goalNode) {
  const visitedRoutes = [];
  let InvalidRoutes = new Set();
  let validRoutes = new Set();

  // すべてのルートを配列として保管
  let keys = Object.keys(groupedRoutes);
  let allRoutes = [];
  keys.forEach((key) => {
    groupedRoutes[key].forEach((el) => {
      allRoutes.push(`${key}->${el}`);
    });
  });
  function dfs(node, startNode, path) {
    if (path.includes(startNode) && node == startNode) {
      path.length = 0;
      return;
    } else {
      path.push(node);
    }

    const neighbors = groupedRoutes[node] || [];
    let routeKey;
    let routesConvertFromPath = [];
    for (const neighbor of neighbors) {
      routeKey = `${node}->${neighbor}`;
      if (!visitedRoutes.includes(routeKey)) {
        visitedRoutes.push(routeKey);
        dfs(neighbor, startNode, path);
      }
      // path -> routeに変換
      routesConvertFromPath = [];
      path.slice(1).forEach((el, i) => {
        routesConvertFromPath.push(`${path[i]}->${el}`);
      });

      if (neighbor == startNode && node == goalNode) {
        routesConvertFromPath.push(`${path.at(-1)}->${startNode}`);
        routesConvertFromPath.forEach((el) => {
          validRoutes.add(el);
        });
      }
    }
    path.pop();
  }

  dfs(startNode, startNode, []);

  const allRoutesSet = new Set(allRoutes);
  InvalidRoutes = allRoutesSet.difference(validRoutes);
  return InvalidRoutes;
}

コードの解説

初期設定

  const visitedRoutes = [];
  let InvalidRoutes = new Set();
  let validRoutes = new Set();

  // すべてのルートを配列として保管
  let keys = Object.keys(groupedRoutes);
  let allRoutes = [];
  keys.forEach((key) => {
    groupedRoutes[key].forEach((el) => {
      allRoutes.push(`${key}->${el}`);
    });
  });

これは初期設定にあたる。訪問済みのルートと正常ルート、異常ルートを宣言する。「すべてのルートを配列として保管」はルートの集まりを["start->1","1->3","3->4"...] のような形に変換させる。

深さ優先探索

function dfs(node, startNode, path) {...}

深さ優先探索のメソッドである。wikiだと訪問済みノードで考えているが、今回はルートを全て回りたい。訪問済みルートに変えて実装している。

path はスタートから閉ループを確認するまでに訪問したルートが順次入っていく。

 path = ["start->1","1->2","2->goal"] 

といった具合だ。

    if (path.includes(startNode) && node == startNode) {
      path.length = 0;
      return;
    } else {
      path.push(node);
    }

path にスタートノードが2回含まれた場合は正しい閉ループが確認できたことになる。path.length = 0; とすることで、path 自体をリセットしている。こういう書き方をしないとpath = [] にならない。

Setオブジェクト

ルートの集合としてSetオブジェクトを使っている。これは値の集合であるが、重複した値を入れることはできない。数学の集合のイメージだ。配列とは違い、中に入っている要素の順序は不定だが、集合同士の和や差や積の操作ができる。

今回の実装では都合が良かった。登場したすべてのルートの集合から正常なルートの集合の差を求めれば、異常なルートの集合が得られる。

終わり

文章を書くのは疲れるが、理解度は深まる。今後も続けたい。

Discussion