-
Notifications
You must be signed in to change notification settings - Fork 3
/
tree_sampling_tools.py
190 lines (151 loc) · 6.77 KB
/
tree_sampling_tools.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
180
181
182
183
184
185
186
187
188
189
# -*- coding: utf-8 -*-
"""
Created on Wed Jul 4 11:43:31 2018
@author: MGGG
"""
#####For creating a spanning tree
import networkx as nx
import random
from equi_partition_tools import equi_split, almost_equi_split, check_delta_equi_split
from projection_tools import remove_edges_map
from walk_tools import propose_step, propose_Broder_step
from Broder_Wilson_algorithms import random_spanning_tree_wilson, random_spanning_tree
#################
'''
'''
def random_equi_partitions(graph, num_partitions, num_blocks, algorithm = "Wilson"):
'''
Here is the code that makes equi partitions.
:graph:
:num_partitions:
:num_blocks: Number of blocks in each partition
'''
found_partitions = []
counter = 0
while len(found_partitions) < num_partitions:
counter += 1
if algorithm == "Broder":
tree = random_spanning_tree(graph)
if algorithm == "Wilson":
tree = random_spanning_tree_wilson(graph)
edge_list = equi_split(tree, num_blocks)
#edge_list will return None if there is no equi_split
if edge_list != None:
found_partitions.append(remove_edges_map(graph, tree, edge_list))
print(len(found_partitions), "waiting time:", counter)
counter = 0
#keeps track of how many trees it went through to find the one
#that could be equi split
return found_partitions
def random_equi_partition_fast(graph, log2_num_blocks):
'''This is a divide and conquer algorithm that speeds up the search
for an equipartition...
The way it works is that it find a tree that equi-splits graph into two
subgraphs, and then repeats this procedure on each subgraph until we have
the desired number of blocks in the subgraph.
'''
blocks = random_equi_partitions(graph, 1, 2)[0]
while len(blocks) < 2**log2_num_blocks:
subgraph_splits = []
for subgraph in blocks:
subgraph_splits += random_equi_partitions(subgraph, 1, 2)[0]
blocks = subgraph_splits
return blocks
def random_equi_partitions_fast(graph, num_partitions, log2_num_blocks):
'''This calls random_equi_partition_fast until you have num_partitions
partitions
'''
found_partitions = []
while len(found_partitions) < num_partitions:
found_partitions.append(random_equi_partition_fast(graph, log2_num_blocks))
return found_partitions
############ Almost equi-partitions:
def random_almost_equi_partitions(graph, num_partitions, num_blocks, delta):
'''This produces a delta almost equi partition... it keeps looping until it finds
the required amounts
'''
found_partitions = []
counter = 0
while len(found_partitions) < num_partitions:
counter += 1
tree = random_spanning_tree_wilson(graph)
edge_list = almost_equi_split(tree, num_blocks, delta)
#If the almost equi split was not a delta split, then it returns none...
if edge_list != None:
blocks = remove_edges_map(graph, tree, edge_list)
found_partitions.append(blocks)
print(len(found_partitions), "waiting time:", counter)
counter = 0
return found_partitions
##
def random_almost_equi_partition_fast(graph, log2_num_blocks, delta):
'''Divide and conquer approach to finding almost equi-partitions.
Similar idea to random_equi_partition_fast
'''
blocks = random_equi_partitions(graph, 1, 2)[0]
while len(blocks) < 2**log2_num_blocks:
subgraph_splits = []
for subgraph in blocks:
subgraph_splits += random_almost_equi_partitions(subgraph, 1, 2, delta)[0]
blocks = subgraph_splits
return blocks
def random_almost_equi_partitions_fast(graph, num_partitions, log2_num_blocks, delta):
'''This builds up almost-equi partitions, it called random_almost_equi_partitoins_fast
which does a divide and consquer to build up partitions...
'''
found_partitions = []
while len(found_partitions) < num_partitions:
found_partitions.append(random_almost_equi_partition_fast(graph, log2_num_blocks, delta))
return found_partitions
############ Almost equi-partitions using sampling, then MH on trees
'''To be filled in -- this will draw a random spanning tree, and check if it can be
almost equi split (delta can be set to be zero...)
[Aside: You can clean up the code by putting delta =0 to be equi-partitions...]
then it will run a the tree walk, updated the labels dynamically, until it gets to a tree
that can be equi split...
'''
def random_almost_equi_partitions_with_walk(graph, num_partitions, num_blocks, delta, step = "Basis", jump_size = 50):
'''This produces a delta almost equi partition... it keeps looping until it finds
the required amounts
'''
# print("am here")
# print(step)
found_partitions = []
counter = 0
tree = random_spanning_tree_wilson(graph)
while len(found_partitions) < num_partitions:
counter += 1
if step == "Basis":
for i in range(jump_size):
tree, edge_to_remove, edge_to_add = propose_step(graph, tree)
if step == "Broder":
for i in range(jump_size):
tree, edge_to_remove, edge_to_add = propose_Broder_step(graph, tree)
edge_list = almost_equi_split(tree, num_blocks, delta)
#If the almost equi split was not a delta split, then it returns none...
if edge_list != None:
blocks = remove_edges_map(graph, tree, edge_list)
found_partitions.append(blocks)
print(len(found_partitions), "waiting time:", counter)
counter = 0
return found_partitions
##
def random_almost_equi_partition_fast_with_walk(graph, log2_num_blocks, delta, step, jump_size = 50):
'''Divide and conquer approach to finding almost equi-partitions.
Similar idea to random_equi_partition_fast
'''
blocks = random_almost_equi_partitions_with_walk(graph, 1, 2, delta, step, jump_size)[0]
while len(blocks) < 2**log2_num_blocks:
subgraph_splits = []
for subgraph in blocks:
subgraph_splits += random_almost_equi_partitions_with_walk(subgraph, 1, 2, delta, step, jump_size)[0]
blocks = subgraph_splits
return blocks
def random_almost_equi_partitions_fast_with_walk(graph, num_partitions, log2_num_blocks, delta, step = "Basis", jump_size = 50):
'''This builds up almost-equi partitions, it called random_almost_equi_partitoins_fast
which does a divide and consquer to build up partitions...
'''
found_partitions = []
while len(found_partitions) < num_partitions:
found_partitions.append(random_almost_equi_partition_fast_with_walk(graph, log2_num_blocks, delta, step, jump_size = 50))
return found_partitions