Stat_Project/perculation.py at main · Mabbai/Stat_Project · GitHub

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
import random as rn

import networkx as nx
import matplotlib.pyplot as plt


GRAPH_SIZE = 1000
EDGE_PROB = 0.501


def EXIST_EDGE(p):
  return rn.random() < p

def generate_graph():
  G = {}
  n = GRAPH_SIZE
  for i in range(0,n+1):
    for j in range(0,n+1):
      G[f'{i},{j}'] = []
  for i in range(0,n+1):
    for j in range(0,n+1,2):
      if i & 1: # i modulo 2 = 1
        j += 1
      if j == n+1:
        continue
      Domestic_Edges = []

      if EXIST_EDGE(EDGE_PROB) and j+1 <= n:
        Domestic_Edges.append(f'{i},{j+1}')

        G[f'{i},{j+1}'].append(f'{i},{j}')

      if EXIST_EDGE(EDGE_PROB) and i+1 <= n:
        Domestic_Edges.append(f'{i+1},{j}')

        G[f'{i+1},{j}'].append(f'{i},{j}')
      if EXIST_EDGE(EDGE_PROB) and i-1 >= 0:
        Domestic_Edges.append(f'{i-1},{j}')

        G[f'{i-1},{j}'].append(f'{i},{j}')

      if EXIST_EDGE(EDGE_PROB) and j-1 >= 0:
        Domestic_Edges.append(f'{i},{j-1}')

        G[f'{i},{j-1}'].append(f'{i},{j}')

      G[f'{i},{j}'] = Domestic_Edges
  return G


G = generate_graph()
#print(f'{G} \n')

def draw_graph_from_dict(grid) -> None:
  G = nx.Graph()
  for node, neighbors in grid.items():
    G.add_node(node)
    for neighbor in neighbors:
      G.add_edge(node, neighbor)

  pos = {node: tuple(map(int,node.split(','))) for node in G.nodes}
  nx.draw(G, pos, with_labels=True, node_size=100,
          node_color='lightgreen', font_size=4)
  plt.gca().invert_yaxis()
  plt.show()


searched_starts = set()

def iterate_frontier(start):
  old_frontier = set()
  frontier = {start}
  while frontier:
    leafs = set()
    for node in frontier:
      acc = grow_leafs(node, frontier | old_frontier)
      if acc == 'W':
        print('W')
        return 'W'
      leafs = leafs | acc

    print(leafs)
    old_frontier = frontier
    frontier = leafs


def grow_leafs(node, past_nodes):
  leafs = set()
  for n in G[node]:
    if not n in past_nodes | leafs:
      x_val = int(n.split(',')[0])
      if x_val == GRAPH_SIZE:
        return 'W'

      if x_val == 0:
        searched_starts.add(n)
      leafs.add(n)

  return leafs

i=0
RESULT = 'L'
while i <= GRAPH_SIZE and RESULT != 'W':
  node = f'0,{i}'
  if not node in searched_starts:
    RESULT = iterate_frontier(node)
  i += 1

#draw_graph_from_dict(G) //don't run it for large graphs 15<