(key_list, idx_list, factor)
| 80 | return ret % n |
| 81 | |
| 82 | def generate_graph(key_list, idx_list, factor): |
| 83 | n = int(len(key_list) * factor + 1) |
| 84 | failed = True |
| 85 | while not is_prime(n): |
| 86 | n += 1 |
| 87 | print("*** 'n' selected: " + str(n)) |
| 88 | print("*** Start iterating...") |
| 89 | iter_cnt = 0 |
| 90 | while failed: |
| 91 | iter_cnt += 1 |
| 92 | print("trying iterating, step %d..." % iter_cnt) |
| 93 | # generate random table |
| 94 | T1 = [random.randint(1, 255) for i in range(0, len(idx_list))] |
| 95 | T2 = [random.randint(1, 255) for i in range(0, len(idx_list))] |
| 96 | # generate empty graph |
| 97 | adj_matrix = [list() for i in range(0, n)] |
| 98 | uniset = union_set(n) |
| 99 | # calcu each key |
| 100 | index = 0 |
| 101 | failed = False |
| 102 | for key in key_list: |
| 103 | hash1 = keyhash(key, T1, idx_list, n) |
| 104 | hash2 = keyhash(key, T2, idx_list, n) |
| 105 | # connect hash1 and hash2 |
| 106 | if uniset.is_connected(hash1, hash2): |
| 107 | failed = True |
| 108 | break |
| 109 | uniset.connect(hash1, hash2) |
| 110 | # make edge |
| 111 | edge = { "hash1" : hash1, "hash2" : hash2, "key" : key, "value" : index } |
| 112 | adj_matrix[hash1].append(edge) |
| 113 | adj_matrix[hash2].append(edge) |
| 114 | index += 1 |
| 115 | print("*** Graph generated") |
| 116 | return T1, T2, adj_matrix |
| 117 | |
| 118 | def find_func_g(adj_matrix, m): |
| 119 | g = [0 for i in range(0, len(adj_matrix))] |
no test coverage detected