random_graph

ソースコード

from titan_pylib.algorithm.random.random_graph import RandomGraphType
from titan_pylib.algorithm.random.random_graph import RandomGraph

view on github

展開済みコード

 1# from titan_pylib.algorithm.random.random_graph import RandomGraph
 2import enum
 3from typing import Optional
 4import random
 5
 6
 7class RandomGraphType(enum.Enum):
 8    random = enum.auto()
 9    cycle = enum.auto()
10
11
12class RandomGraph:
13
14    @classmethod
15    def build(
16        cls,
17        n: int,
18        m: int,
19        typ: RandomGraphType = RandomGraphType.random,
20        seed: Optional[int] = None,
21    ) -> list[tuple[int, int]]:
22        cls.rand = random.Random(seed)
23        if typ == RandomGraphType.random:
24            return cls._build_random(n, m)
25        if typ == RandomGraphType.cycle:
26            return cls._build_cycle(n, m)
27        raise ValueError(typ)
28
29    @classmethod
30    def _build_cycle(cls, n: int, m: int) -> list[tuple[int, int]]:
31        assert m == n
32        cycle = list(range(n))
33        cls.rand.shuffle(cycle)
34        cycle.append(cycle[-1])
35        edges = [None] * n
36        for i in range(n):
37            u, v = cycle[i], cycle[i + 1]
38            if cls.rand.random() < 0.5:
39                edges[i] = (v, u)
40            else:
41                edges[i] = (u, v)
42        cls.rand.shuffle(edges)
43        assert len(edges) == m
44        return edges
45
46    @classmethod
47    def _build_random(cls, n: int, m: int) -> list[tuple[int, int]]:
48        assert m <= n * (n - 1) // 2
49        edges = set()
50        while len(edges) < m:
51            u = cls.rand.randrange(0, n)
52            v = cls.rand.randrange(0, n)
53            while u == v:
54                v = cls.rand.randrange(0, n)
55            if u > v:
56                u, v = v, u
57            edges.add((u, v))
58        edges = list(edges)
59        for i in range(m):
60            u, v = edges[i]
61            if cls.rand.random() < 0.5:
62                edges[i] = (v, u)
63        cls.rand.shuffle(edges)
64        assert len(edges) == m
65        return edges

仕様

class RandomGraph[source]

Bases: object

classmethod build(n: int, m: int, typ: RandomGraphType = RandomGraphType.random, seed: int | None = None) → list[tuple[int, int]][source]
class RandomGraphType(*values)[source]

Bases: Enum

cycle = 2
random = 1