Topological Sort
(Topological_Sort.py)

View this file on GitHub
Last update: 2025-03-14 00:26:13+09:00

Outline

有向グラフ $D = (V, A)$ に対して, $V$ 上の全順序関係 $\leq$ が $D$ のトポロジカルソートであるとは, 以下を満たすことである.

任意の $u, v \in V~(u \neq v)$ に対して, $\overrightarrow{uv} \in A$ ならば, $u \leq v$ である.

位数 $N$, サイズ $M$ の有向グラフ $D$ に対して, $D$ のトポロジカルソートの存在判定及び構築を $O(N + M)$ 時間で行う.

Theory

有向グラフ $D = (V, A)$ に対して, 以下が同値になる.

(a) $D$ のトポロジカルソートが存在する.
(b) $D$ において, サイクルが存在しない.

これを証明する.

Proof

(a) ならば (b)

対偶を証明する. $D$ 上の有向サイクルを $v_1 v_2 \dots v_k$ ($k$ 個の頂点は全て相異なる) とする.

$\leq$ を $D$ 上の Topological Sort とする. ここで, サイクルの対称性により,

\[v_1 = \min_{\leq}(v_1, v_2, \dots, v_k)\]

であるとしても一般性を失わない.

すると, $\overrightarrow{v_k v_1} \in A$ となるが, $\leq$ が Topological Sort より $v_k \leq v_1$ である.

一方で, $v_1$ の定め方より, $v_1 \leq v_k$ である.

$\leq$ が全順序であるので, $v_1 = v_k$ となる.

しかし, $v_1, \dots, v_k$ が相異なる $k$ 個の頂点であることに矛盾する.

よって, $D$ に Topological Sort は存在しない.

(b) ならば (a)

DAG $D$ の位数 $n$ に関する数学的帰納法で示す.

$1$ 頂点のときは任意の順序がトポロジカルソートになる.

$(n-1)$ 頂点の任意の DAG が Topological Sort を持つと仮定する. $D$ が $n$ 頂点の DAG とする.

$D$ は DAG なので, 入近傍が存在しない頂点 $x \in V$ が存在する. $D$ から頂点 $x$ を除いた $D$ の部分グラフ $D’ := D - x$ は $D$ が DAG であるから, $D’$ も DAG である.

$D’$ の位数が $(n-1)$ であるので, 数学的帰納法の仮定により, $D’$ の Topological Sort $\leq’$ が存在する.

この $\leq’$ を用いて, $V$ 上の関係 $\leq$ を次のようにして定義する. ただし, $u,v \in V$ とする.

\[u \leq v :\iff (u = x) \lor (u,v \neq x \land u \leq' v)\]

すると, この $\leq$ は $D$ 上の Topological Sort になる. 実際, $\overrightarrow{uv} \in A~(u \neq v)$ に対して,

$u = x$ のときは, $\leq$ の定義により $u \leq v$ である.
$v = x$ とはなり得ない. これは $x$ が $D$ 上で入近傍が存在しない頂点として取ってきており, $u \neq v$ であることから従う.
$u,v \neq x$ のときは, $u \leq’ v$ より $u \leq v$ となる.

この同値性における「(b) ならば (a)」の証明を利用することによって, Topological Sort の判定と構築を行うことができる.

Code

class Topological_Sort:
    __slots__=("__arc", "__rev", "__reflexive", "__is_DAG", "__order")

    def __init__(self, N: int, reflexive: bool = False):
        """ N 頂点からなる有向空グラフを生成する.

        Args:
            N (int): 頂点数
            reflexive (bool, optional): True にすると, 自己ループの追加を認める. Defaults to False.
        """

        self.__arc=[[] for _ in  range(N)]
        self.__rev=[[] for _ in range(N)]
        self.__reflexive=reflexive

    @property
    def N(self):
        return len(self.__arc)

    @property
    def reflexive(self):
        return self.__reflexive

    def add_arc(self, source: int, target: int):
        """ source から target への弧を追加する.

        Args:
            source (int): 始点
            target (int): 終点
        """

        # 自己ループを認めない場合の source == target のときは棄却する.
        if source == target and (not self.reflexive):
            return

        self.__arc[source].append(target)
        self.__rev[target].append(source)

    def add_vertex(self) -> int:
        """ 1 頂点追加

        Returns:
            int: 追加された頂点の頂点番号
        """

        self.__arc.append([])
        self.__rev.append([])
        return self.N - 1

    def add_arc_multiple(self, sources: list[int], targets: list[int]) -> int:
        """ 任意の s in sources, t in targets に対して, s から t への弧を作成する (仮想的に 1 頂点を追加する).

        Args:
            sources (list[int]): 始点のリスト
            targets (list[int]): 終点のリスト

        Returns:
            int: 超頂点として追加された頂点の番号
        """

        # 方針
        # (1) 超頂点 x を追加する.
        # (2) 任意の s in sources に対して, 弧 sx を追加する.
        # (3) 任意の t in targets に対して, 弧 xt を追加する.
        # このようにすることで, 追加する弧の数を |sources| x |targets| から |sources| + |targets| に落とせる.

        x = self.add_vertex()
        for s in sources:
            self.add_arc(s, x)

        for t in targets:
            self.add_arc(x, t)

    def calculate(self):
        """ DAG に関する計算を行う.
        """

        in_deg = [len(self.__rev[x]) for x in range(self.N)]
        order = []
        stack = [x for x in range(self.N) if in_deg[x] == 0]

        while stack:
            x = stack.pop()
            order.append(x)

            for y in self.__arc[x]:
                in_deg[y] -= 1
                if in_deg[y] == 0:
                    stack.append(y)

        if len(order) == self.N:
            self.__is_DAG = True
            self.__order = order
        else:
            self.__is_DAG = False
            self.__order = None

    @property
    def is_DAG(self):
        return self.__is_DAG

    @property
    def order(self):
        return self.__order

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Topological Sort (Topological_Sort.py)