-
Notifications
You must be signed in to change notification settings - Fork 3
/
main.py
179 lines (136 loc) · 6.71 KB
/
main.py
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
# -*- coding: utf-8 -*-
"""
Created on Fri Jul 6 17:32:53 2018
@author: MGGG
"""
from walk_tools import equi_shadow_walk
import networkx as nx
from tree_sampling_tools import random_equi_partitions, random_spanning_tree, random_spanning_tree_wilson, random_equi_partitions_fast, random_almost_equi_partitions_fast, random_almost_equi_partitions, random_almost_equi_partitions_with_walk, random_almost_equi_partitions_fast_with_walk
from equi_partition_tools import check_delta_equi_split
from visualization_tools import visualize_partition, visualize_partition_with_populations
import numpy as np
def explore_random(graph, num_maps, num_blocks, pictures = False, divide_and_conquer = False, equi = False, with_walk = True, delta = .1):
'''This samples random equi-partitoins according to natural likelihood
:fast: The divide and conquer strategy. Currently unclear what distirbution this gives.
:pictures: whether to display pictures of the found plan
:num_maps: number of maps to produce
:num_blocks: number of blocks in each map
:pictures: whether to display a picture at the end
:divide_and_conquer: whether to use a divide and conquer algorithm... currently
input muts by a power of 2
:equi: Whether to hard constraint to same sized partitions
:delta: the tolerance with which to accept partitions that are not equal sized.
'''
'''easy fixes:
1. Replace equi with delta = 0
2.
'''
if with_walk == True:
step = "Broder"
jump_size = 1
tree_partitions = random_almost_equi_partitions_with_walk(graph, 1, num_blocks, delta, step, jump_size)
if with_walk == False:
# Checking partition parameter selections
if equi and divide_and_conquer:
log2_num_blocks = np.log2(num_blocks)
if int(log2_num_blocks) != log2_num_blocks:
print("Must be power of 2 number of blocks")
return
tree_partitions = random_equi_partitions_fast(graph, num_maps, log2_num_blocks)
elif equi and not divide_and_conquer:
tree_partitions = random_equi_partitions(graph, num_maps, num_blocks)
elif not equi and divide_and_conquer:
log2_num_blocks = np.log2(num_blocks)
if int(log2_num_blocks) != log2_num_blocks:
print("Must be power of 2 number of blocks")
return
tree_partitions = random_almost_equi_partitions_fast(graph, num_maps, log2_num_blocks, delta)
elif not equi and not divide_and_conquer:
tree_partitions = random_almost_equi_partitions(graph, num_maps, num_blocks, delta)
# Visualizations
if pictures == True:
for partition in tree_partitions:
visualize_partition(graph, partition)
print("Node sizes", [len(x) for x in partition])
print("Population", [total_pop(x) for x in partition])
return tree_partitions
def total_pop(graph):
return np.sum( [graph.nodes[x]["POP10"] for x in graph.nodes()] )
def explore_walk(graph_size, num_blocks):
'''
This does tree walk to sample equi-partitions
'''
graph = nx.grid_graph( [graph_size, graph_size])
tree = random_spanning_tree(graph)
tree_partitions = equi_shadow_walk(graph, tree, 3, num_blocks)
return tree_partitions
def test(graph_size, num_blocks, delta):
graph = nx.grid_graph([graph_size, graph_size])
tree_partitions = random_almost_equi_partitions_with_walk(graph, 1, num_blocks, delta)
for partition in tree_partitions:
visualize_partition(graph, partition)
print([len(x) for x in partition])
def test_fast_with_walk(graph_size, num_blocks, delta, step = "Basis", jump_size = 50):
graph = nx.grid_graph([graph_size, graph_size])
for vertex in graph:
graph.nodes[vertex]["geopos"] = vertex
graph.nodes[vertex]["POP10"] = 1
tree_partitions = random_almost_equi_partitions_fast_with_walk(graph, 1, num_blocks, delta, step, jump_size)
for partition in tree_partitions:
visualize_partition(graph, partition)
print([len(x) for x in partition])
graph = nx.grid_graph([800,800])
for vertex in graph:
graph.nodes[vertex]["geopos"] = vertex
graph.nodes[vertex]["POP10"] = 1
explore_random(graph, 1, 2, pictures=True, divide_and_conquer=False)
graph = nx.grid_graph([1200,1200])
for vertex in graph:
graph.nodes[vertex]["geopos"] = vertex
graph.nodes[vertex]["POP10"] = 1
explore_random(graph, 1, 2, pictures=True, divide_and_conquer=False)
#tree_1 = random_spanning_tree(graph)
#tree_2 = random_spanning_tree_wilson(graph)
#test_fast_with_walk(120, 2, 0.01, "Broder", 1000)
'''
Observations:
1. When doing divide and conquer with walk, you don't need ot redraw a new tree
at each stage, instead... just copy them over and have them start walking...
2. When updating with Broder walk, we should update the weights dynamically...
3. Another option is
Start a Broder walk, and build a forward tree... then after you've covered a certain
percentage of nodes, switch to Wilsons...
.... A compromise might be : sample a tree, and then do the Broder walk until you get an
equi partitoin, or an almost equipartition...
'''
'''
TODO:
1. Update labels dynamically --- for Broder walk anyway
2. Try a mixture of Broder and Wilson for generating the original walk.
3. NOTE -- If possible, I want to stick to a process which is guaranteed to sample uniformly form trees
... so doing the walk until we get a tree that can be equisplit is preferable...
4.
'''
'''
Propose step is so slow!! It shouldn't be this slow!
Also I'm calling label_weights much more often than I should be... we should update
then dynamically when doing the tree walk...
'''
#The efficiency of this can depend on a lot whether you land near somewhere thats an
#equipartition... maybe can be faster if we do the label updating in a smart way.
#parts = explore_random(40,1,2, pictures = True, divide_and_conquer = True, equi = False, graph_type = "grid", delta = .2)
#parts = explore_random(120,1,12, pictures = True, divide_and_conquer = False, equi = False, delta = .1)
#check_delta_equi_split([len(x) for x in parts[0]], .01)
#explore_walk(8,4)
#
#parts = explore_random(10,1,3, pictures = True, divide_and_conquer = False, equi = False, graph_type = "dodeca")
'''
Todo: intead of hard equi partitions, expand it to delta equi... and
get all delta equi partitions... is this going to slow down the check step?
Add a score function --
1. Draw a random tree
2. Add node weights
3. Draw random edges until you get one that lives within delta of ok (hard or soft...)
4. Accept it.
"Turtles on turtles..." but may work well.
'''