Source code for titan_pylib.algorithm.random.random_graph

 1import enum
 2from typing import Optional
 3import random
 4
 5

[docs]
 6class RandomGraphType(enum.Enum):
 7    random = enum.auto()
 8    cycle = enum.auto()

 9
10

[docs]
11class RandomGraph:
12

[docs]
13    @classmethod
14    def build(
15        cls,
16        n: int,
17        m: int,
18        typ: RandomGraphType = RandomGraphType.random,
19        seed: Optional[int] = None,
20    ) -> list[tuple[int, int]]:
21        cls.rand = random.Random(seed)
22        if typ == RandomGraphType.random:
23            return cls._build_random(n, m)
24        if typ == RandomGraphType.cycle:
25            return cls._build_cycle(n, m)
26        raise ValueError(typ)

27
28    @classmethod
29    def _build_cycle(cls, n: int, m: int) -> list[tuple[int, int]]:
30        assert m == n
31        cycle = list(range(n))
32        cls.rand.shuffle(cycle)
33        cycle.append(cycle[-1])
34        edges = [None] * n
35        for i in range(n):
36            u, v = cycle[i], cycle[i + 1]
37            if cls.rand.random() < 0.5:
38                edges[i] = (v, u)
39            else:
40                edges[i] = (u, v)
41        cls.rand.shuffle(edges)
42        assert len(edges) == m
43        return edges
44
45    @classmethod
46    def _build_random(cls, n: int, m: int) -> list[tuple[int, int]]:
47        assert m <= n * (n - 1) // 2
48        edges = set()
49        while len(edges) < m:
50            u = cls.rand.randrange(0, n)
51            v = cls.rand.randrange(0, n)
52            while u == v:
53                v = cls.rand.randrange(0, n)
54            if u > v:
55                u, v = v, u
56            edges.add((u, v))
57        edges = list(edges)
58        for i in range(m):
59            u, v = edges[i]
60            if cls.rand.random() < 0.5:
61                edges[i] = (v, u)
62        cls.rand.shuffle(edges)
63        assert len(edges) == m
64        return edges