Source code for titan_pylib.algorithm.random.random_tree

 1from titan_pylib.data_structures.heap.deletable_min_heap import DeletableMinHeap
 2import enum
 3from typing import Optional
 4import random
 5
 6

[docs]
 7class RandomTreeType(enum.Enum):
 8    """``RandomTree`` で木の形を指定するときに使用する列挙型クラスです。"""
 9
10    random = enum.auto()
11    path = enum.auto()
12    star = enum.auto()

13
14

[docs]
15class RandomTree:
16

[docs]
17    @classmethod
18    def build(
19        cls,
20        n: int,
21        typ: RandomTreeType = RandomTreeType.random,
22        seed: Optional[int] = None,
23    ) -> list[tuple[int, int]]:
24        """ランダムな木を生成し、辺を返します。
25        :math:`O(n \\log{n})` です。
26
27        Args:
28            n (int): 頂点の数です。
29            typ (RandomTreeType, optional): 木の形です。 Defaults to RandomTreeType.random。
30            seed (Optional[int], optional): seed値です。 Defaults to None。
31
32        Returns:
33            list[tuple[int, int]]: 辺のリストです。辺のインデックスは 0-indexed です。
34        """
35        cls.rand = random.Random(seed)
36        edges = None
37        if typ == RandomTreeType.random:
38            edges = cls._build_random(n)
39        elif typ == RandomTreeType.path:
40            edges = cls._build_path(n)
41        elif typ == RandomTreeType.star:
42            edges = cls._build_star(n)
43        assert (
44            edges is not None
45        ), f"{cls.__class__.__name__}.build({typ}), typ is not defined."
46        cls.rand.shuffle(edges)
47        return edges

48
49    @classmethod
50    def _build_star(cls, n: int) -> list[tuple[int, int]]:
51        center = cls.rand.randrange(0, n)
52        edges = []
53        for i in range(n):
54            if i == center:
55                continue
56            if cls.rand.random() < 0.5:
57                edges.append((center, i))
58            else:
59                edges.append((i, center))
60        return edges
61
62    @classmethod
63    def _build_path(cls, n: int) -> list[tuple[int, int]]:
64        p = list(range(n))
65        cls.rand.shuffle(p)
66        edges = [
67            (p[i], p[i + 1]) if cls.rand.random() < 0.5 else (p[i + 1], p[i])
68            for i in range(n - 1)
69        ]
70        return edges
71
72    @classmethod
73    def _build_random(cls, n: int) -> list[tuple[int, int]]:
74        edges = []
75        D = [1] * n
76        A = [0] * (n - 2)
77        for i in range(n - 2):
78            v = cls.rand.randrange(0, n)
79            D[v] += 1
80            A[i] = v
81        avl: DeletableMinHeap[tuple[int, int]] = DeletableMinHeap(
82            (D[i], i) for i in range(n)
83        )
84        for a in A:
85            d, v = avl.pop_min()
86            assert d == 1
87            edges.append((v, a))
88            D[v] -= 1
89            avl.remove((D[a], a))
90            D[a] -= 1
91            if D[a] >= 1:
92                avl.push((D[a], a))
93        u = D.index(1)
94        D[u] -= 1
95        v = D.index(1)
96        D[v] -= 1
97        edges.append((u, v))
98        return edges