FilesExpand file tree

 Write-for-current-Python

/

markov_chain.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

83 lines (61 loc) · 2.02 KB

 Write-for-current-Python

/

markov_chain.py

Copy path

Top

File metadata and controls

• Code
• Blame

83 lines (61 loc) · 2.02 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

from __future__ import annotations

from collections import Counter

from random import random

class MarkovChainGraphUndirectedUnweighted:

"""

Undirected Unweighted Graph for running Markov Chain Algorithm

"""

def __init__(self):

self.connections = {}

def add_node(self, node: str) -> None:

self.connections[node] = {}

def add_transition_probability(

self, node1: str, node2: str, probability: float

) -> None:

if node1 not in self.connections:

self.add_node(node1)

if node2 not in self.connections:

self.add_node(node2)

self.connections[node1][node2] = probability

def get_nodes(self) -> list[str]:

return list(self.connections)

def transition(self, node: str) -> str:

current_probability = 0

random_value = random()

for dest in self.connections[node]:

current_probability += self.connections[node][dest]

if current_probability > random_value:

return dest

def get_transitions(

start: str, transitions: list[tuple[str, str, float]], steps: int

) -> dict[str, int]:

"""

Running Markov Chain algorithm and calculating the number of times each node is

visited

>>> transitions = [

... ('a', 'a', 0.9),

... ('a', 'b', 0.075),

... ('a', 'c', 0.025),

... ('b', 'a', 0.15),

... ('b', 'b', 0.8),

... ('b', 'c', 0.05),

... ('c', 'a', 0.25),

... ('c', 'b', 0.25),

... ('c', 'c', 0.5)

... ]

>>> result = get_transitions('a', transitions, 5000)

>>> result['a'] > result['b'] > result['c']

True

"""

graph = MarkovChainGraphUndirectedUnweighted()

for node1, node2, probability in transitions:

graph.add_transition_probability(node1, node2, probability)

visited = Counter(graph.get_nodes())

node = start

for _ in range(steps):

node = graph.transition(node)

visited[node] += 1

return visited

if __name__ == "__main__":

import doctest

doctest.testmod()