2024年1月18日木曜日

functional graphの閉路の情報を得る

問題: 関数$f: \{0, 1, ..., N-1\} \rightarrow \{0, 1, ..., N-1\}$が与えられる。$f$によって定まるfunctional graph上の閉路の情報を$O(N)$で得たい。具体的には、次の配列を作りたい:

  • $\operatorname {cycle}[v] :=$ 閉路上の頂点で$v$に最も近いもの。より形式的には、$f^k(v)$が閉路に含まれるような最小の非負整数$k$に関する$f^k(v)$。
  • $\operatorname{length}[v] := v$が閉路に含まれるならその閉路の長さ。そうでないなら$v$から$\operatorname{cycle}[v]$までの距離。

以下はグラフと求めたい値の例。頂点番号 (cycleの値, lengthの値)という表記になっている。

flowchart TD
	0["0 (3, 3)"]
	1["1 (3, 2)"]
	2["2 (3, 1)"]
	3["3 (3, 4)"]
	4["4 (4, 4)"]
	5["5 (5, 4)"]
	6["6 (6, 4)"]
	7["7 (3, 4)"]
	8["8 (3, 3)"]
	9["9 (10, 1)"]
	10["10 (10, 2)"]
	11["11 (11, 2)"]
	12["12 (6, 1)"]
	13["13 (6, 2)"]
	14["14 (14, 1)"]
	0 --> 1
	1 --> 2
	2 --> 3
	3 --> 4
	4 --> 5
	5 --> 6
	6 --> 3
	7 --> 8
	8 --> 1
	9 --> 10
	10 --> 11
	11 --> 10
	12 --> 6
	13 --> 12
	14 --> 14

アルゴリズム

長さ$N$の配列$\mathrm{tmp}, \mathrm{length}, \mathrm{cycle}$を初期化する。$\mathrm{tmp}$は$-1$で埋め、$\mathrm{length}, \mathrm{cycle}$は$0$で埋める。

頂点$r = 0, 1, ..., N-1$について、それぞれ未訪問($\mathrm{tmp}[r] = -1$)であれば$r$に関するイテレーションを開始する。

1回のイテレーションにおいては、$v \leftarrow r$を始点にして$v \leftarrow f(v)$を繰り返してグラフを辿っていく。この際、$r$から$v$までの距離$d$を保持して、$\mathrm{tmp}[v] \leftarrow d$と記録していく。以前に訪れた頂点($\mathrm{tmp}[v] \neq -1$)を再訪したところでストップするが、このとき、$v$がこのイテレーションで初めて訪問した頂点である($\mathrm{length}[v] = 0$)か、以前のイテレーションで訪問した頂点かで必要な処理が異なる。

$v$がこのイテレーションで初めて訪問した頂点であれば新しい閉路を発見したことになるので、閉路の長さ($d - \mathrm{tmp}[v]$)に従って、閉路をもう一周しながら$\mathrm{length}$と$\mathrm{cycle}$を埋める。さらに、始点$r$から閉路に達するまでの頂点についても$\mathrm{length}$と$\mathrm{cycle}$を埋める。

$v$が以前のイテレーションで訪問した頂点の場合、始点$r$から辿って$\mathrm{cycle}$を$\mathrm{cycle}[v]$で埋めていく。$\mathrm{length}$については、$v$が閉路中の頂点($v = \mathrm{cycle}[v]$)であれば$\mathrm{tmp}[v]$を採用し、$v$が閉路外の頂点であれば$\mathrm{tmp}[v]+\mathrm{length}[v]$を採用して始点から埋めていく。

どの頂点についても高々2回しか$f$を適用しないので$O(N)$。

以下はPythonの実装例:

def get_cycle_info(f: list[int]) -> tuple[list[int], list[int]]:
    """{0, 1, ..., N-1}上の写像fを入力として2つのリストcycle, lengthを返す

    cycle[v] := 閉路に含まれるような最初のf(f(...f(v)...))
    length[v] := vが閉路上の頂点の場合は閉路の長さ、そうでない場合はvから閉路までの距離
    """
    n = len(f)
    tmp = [-1] * n
    cycle = [0] * n
    length = [0] * n
    for start in range(n):
        v = start
        dist = 0
        while tmp[v] == -1:
            tmp[v] = dist
            v = f[v]
            dist += 1
        if length[v] == 0:
            u = start
            path_length = tmp[v]
            for i in range(path_length):
                cycle[u] = v
                length[u] = path_length - i
                u = f[u]
            cycle_length = dist - tmp[v]
            for _ in range(cycle_length):
                cycle[v] = v
                length[v] = cycle_length
                v = f[v]
        else:
            u = start
            path_length = dist if v == cycle[v] else dist + length[v]
            for i in range(dist):
                cycle[u] = cycle[v]
                length[u] = path_length - i
                u = f[u]
    return cycle, length

cycle, length = get_cycle_info([1, 2, 3, 4, 5, 6, 3, 8, 1, 10, 11, 10, 6, 12, 14])
assert cycle == [3, 3, 3, 3, 4, 5, 6, 3, 3, 10, 10, 11, 6, 6, 14]
assert length == [3, 2, 1, 4, 4, 4, 4, 4, 3, 1, 2, 2, 1, 2, 1]

cycle, length = get_cycle_info([1, 2, 2])
assert cycle == [2, 2, 2]
assert length == [2, 1, 1]

cycle, length = get_cycle_info([])
assert cycle == []
assert length == []

たぶん基本的な問題だけど書いてある文献が見つからなかったのでメモ。

投稿者