## root / fiddle / heuristic-betweenness-centrality / centrality_biconnected.py @ 82c7c698

History | View | Annotate | Download (16.2 KB)

1 | 8e44cb4f | Quynh PX Nguyen | ```
# Implement the section IV in Puzis 2012 paper
``` |
---|---|---|---|

2 | 82c7c698 | Quynh PX Nguyen | ```
# straight_lineent the section IV in Puzis 2012 paper
``` |

3 | 8e44cb4f | Quynh PX Nguyen | ```
# Heuristic Betweenness Centrality - Partitioning to Bi-connected Components
``` |

4 | |||

5 | 181e7c50 | Quynh PX Nguyen | import os |

6 | 739fe075 | Quynh PX Nguyen | import sys |

7 | 3c6ce57c | Quynh PX Nguyen | import pprint |

8 | 181e7c50 | Quynh PX Nguyen | import networkx as nx |

9 | import betweenness_centrality as centrality |
||

10 | 8e44cb4f | Quynh PX Nguyen | import utility |

11 | 181e7c50 | Quynh PX Nguyen | from pdb import set_trace as debugger |

12 | |||

13 | MAIN_CODE_DIR = os.environ.get('MAIN_CODE_DIR', '') |
||

14 | |||

15 | |||

16 | class HeuristicBetweennessCentrality(): |
||

17 | def __init__(self, subgraphs, bicomponents, cutpoints, num_vertices, link_weight, traffic_matrix): |
||

18 | ```
self.subgraphs = subgraphs
``` |
||

19 | ```
self.bicomponents = bicomponents
``` |
||

20 | ```
self.cutpoints = cutpoints
``` |
||

21 | ```
self.num_vertices = num_vertices
``` |
||

22 | ```
self.link_weight = link_weight
``` |
||

23 | ```
self.traffic_matrix = traffic_matrix
``` |
||

24 | |||

25 | self.bc_components = list() |
||

26 | ```
self.calculate_bc_non_cutpoint()
``` |
||

27 | ```
self.calculate_bc_cutpoint()
``` |
||

28 | |||

29 | self.bc = dict() |
||

30 | ```
self.finalize()
``` |
||

31 | |||

32 | def calculate_bc_non_cutpoint(self): |
||

33 | 3c6ce57c | Quynh PX Nguyen | ```
"""BC for non cutpoint
``` |

34 | 181e7c50 | Quynh PX Nguyen | ```
"""
``` |

35 | for i, subgraphs in enumerate(self.subgraphs): |
||

36 | ```
traffic_matrix = self.traffic_matrix[i]
``` |
||

37 | 3c6ce57c | Quynh PX Nguyen | results = centrality.weight_betweenness_centrality(subgraphs, traffic_matrix) |

38 | 181e7c50 | Quynh PX Nguyen | ```
self.bc_components.append(results)
``` |

39 | |||

40 | def calculate_bc_cutpoint(self): |
||

41 | self.bc_cutpoints = dict() |
||

42 | |||

43 | ```
bc_inter = dict()
``` |
||

44 | for v in self.cutpoints: |
||

45 | ```
inter = 0
``` |
||

46 | for i, comp in enumerate(self.bicomponents): |
||

47 | if v in comp: |
||

48 | ```
inter += self.link_weight.get_link_weight(i, v
``` |
||

49 | ```
) * self.link_weight.get_reverse_link_weight(i, v)
``` |
||

50 | bc_inter[v] = inter |
||

51 | |||

52 | print 'XXXX bc_components = %s' % self.bc_components |
||

53 | print 'XXXX inter = %s' % bc_inter |
||

54 | |||

55 | for v in self.cutpoints: |
||

56 | ```
bc_locally = 0
``` |
||

57 | for i, comp in enumerate(self.bicomponents): |
||

58 | if v in comp: |
||

59 | ```
bc_locally += self.bc_components[i][v]
``` |
||

60 | 3c6ce57c | Quynh PX Nguyen | ```
# self.bc_cutpoints[v] = bc_locally - bc_inter[v]
``` |

61 | ```
# TODO: do not minus the bc_inter
``` |
||

62 | ```
self.bc_cutpoints[v] = bc_locally
``` |
||

63 | 181e7c50 | Quynh PX Nguyen | |

64 | def finalize(self): |
||

65 | ```
# Add the bc for non cutpoint vertices
``` |
||

66 | for bc_component in self.bc_components: |
||

67 | for key, value in bc_component.iteritems(): |
||

68 | if key not in self.bc: |
||

69 | ```
self.bc[key] = value
``` |
||

70 | |||

71 | ```
# Add the bc for cutpoint vertices
``` |
||

72 | for key, value in self.bc_cutpoints.iteritems(): |
||

73 | ```
self.bc[key] = value
``` |
||

74 | |||

75 | 3c6ce57c | Quynh PX Nguyen | print '*** betweenness = %s' % self.bc |

76 | 181e7c50 | Quynh PX Nguyen | ```
# Rescale the bc according to the original graph
``` |

77 | 3c6ce57c | Quynh PX Nguyen | factor = 1.0 / ((self.num_vertices - 1) * (self.num_vertices - 2)) |

78 | 82c7c698 | Quynh PX Nguyen | ```
# TODO: check the scaling factor, how much should it be?
``` |

79 | 3c6ce57c | Quynh PX Nguyen | ```
# factor = 2.0 / (self.num_vertices*self.num_vertices - 3 * self.num_vertices + 2)
``` |

80 | 181e7c50 | Quynh PX Nguyen | for key, value in self.bc.iteritems(): |

81 | ```
self.bc[key] = value * factor
``` |
||

82 | |||

83 | def write(self, file_suffix=''): |
||

84 | ```
filepath = '/output/heuristic_%s.csv' % file_suffix
``` |
||

85 | with open(MAIN_CODE_DIR + filepath, 'w') as output: |
||

86 | for node, centrality in self.bc.iteritems(): |
||

87 | ```
output.write('%s, %s\n' % (node, centrality))
``` |
||

88 | |||

89 | def __str__(self): |
||

90 | return str(self.bc) |
||

91 | |||

92 | |||

93 | class TrafficMatrix(): |
||

94 | def __init__(self, bicomponents, cutpoints, link_weight): |
||

95 | ```
self.bicomponents = bicomponents
``` |
||

96 | ```
self.cutpoints = cutpoints
``` |
||

97 | self.num_components = len(bicomponents) |
||

98 | ```
self.link_weight = link_weight
``` |
||

99 | |||

100 | self.h = list() |
||

101 | ```
self.generate_empty_traffic_matrix()
``` |
||

102 | ```
self.generate_traffic_matrix()
``` |
||

103 | |||

104 | def generate_empty_traffic_matrix(self): |
||

105 | for i in range(self.num_components): |
||

106 | l = len(self.bicomponents[i]) |
||

107 | matrix = [[1 for x in range(l)] for y in range(l)] |
||

108 | ```
# update the main diagonal
``` |
||

109 | for x in range(l): |
||

110 | ```
matrix[x][x] = 0
``` |
||

111 | |||

112 | ```
self.h.append(matrix)
``` |
||

113 | |||

114 | def generate_traffic_matrix(self): |
||

115 | ```
# Update the value when one vertex is a cut-point, another vertex is not a cut-point
``` |
||

116 | for i, components in enumerate(self.bicomponents): |
||

117 | ```
normal_points = components.difference(self.cutpoints)
``` |
||

118 | ```
cutpoints = self.cutpoints.intersection(components)
``` |
||

119 | |||

120 | for cutpoint in cutpoints: |
||

121 | for normal_point in normal_points: |
||

122 | communication_intensity = self.link_weight.get_reverse_link_weight(i, cutpoint) + 1 |
||

123 | ```
self.update(i, cutpoint, normal_point, communication_intensity)
``` |
||

124 | |||

125 | ```
# Update the value when both vertices are cut-points
``` |
||

126 | for i, components in enumerate(self.bicomponents): |
||

127 | cutpoints = list(self.cutpoints.intersection(components)) |
||

128 | ```
len_cutpoints = len(cutpoints)
``` |
||

129 | if len_cutpoints > 1: |
||

130 | for k in range(len_cutpoints - 1): |
||

131 | for l in range(1, len_cutpoints): |
||

132 | 8e44cb4f | Quynh PX Nguyen | ```
if k == l:
``` |

133 | ```
continue
``` |
||

134 | 181e7c50 | Quynh PX Nguyen | communication_intensity = ( |

135 | self.link_weight.get_reverse_link_weight(i, cutpoints[k]) + 1) * ( |
||

136 | self.link_weight.get_reverse_link_weight(i, cutpoints[l]) + 1 |
||

137 | ) |
||

138 | ```
self.update(i, cutpoints[k], cutpoints[l], communication_intensity)
``` |
||

139 | |||

140 | def simple_update(self, comp_index, x_pos, y_pos, value): |
||

141 | ```
self.h[comp_index][x_pos][y_pos] = value
``` |
||

142 | ```
# to keep the symmetric property of Traffic Matrix
``` |
||

143 | ```
self.h[comp_index][y_pos][x_pos] = value
``` |
||

144 | |||

145 | def update(self, comp_index, x, y, value): |
||

146 | 82c7c698 | Quynh PX Nguyen | comp = sorted(self.bicomponents[comp_index]) |

147 | 181e7c50 | Quynh PX Nguyen | ```
try:
``` |

148 | ```
x_pos = list(comp).index(x)
``` |
||

149 | ```
y_pos = list(comp).index(y)
``` |
||

150 | ```
except:
``` |
||

151 | debugger() |
||

152 | ```
a = 2
``` |
||

153 | |||

154 | ```
self.simple_update(comp_index, x_pos, y_pos, value)
``` |
||

155 | |||

156 | def __str__(self): |
||

157 | return str(self.h) |
||

158 | |||

159 | def __getitem__(self, key): |
||

160 | return self.h[key] |
||

161 | |||

162 | |||

163 | class LinkWeight(): |
||

164 | def __init__(self, graph, bicomponents, cutpoints): |
||

165 | ```
self.num_vertices = nx.number_of_nodes(graph)
``` |
||

166 | ```
self.bicomponents = bicomponents
``` |
||

167 | self.num_components = len(bicomponents) |
||

168 | ```
self.cutpoints = cutpoints
``` |
||

169 | |||

170 | self.Dv_B = [dict() for i in range(self.num_components)] # link weight |
||

171 | 24a4abf9 | Quynh PX Nguyen | ```
self.compute_component_tree_weight()
``` |

172 | 181e7c50 | Quynh PX Nguyen | |

173 | self.reverse_Dv_B = [dict() for i in range(self.num_components)] # reverse link weight |
||

174 | ```
self.generate_reverse_link_weight()
``` |
||

175 | |||

176 | def _components_sharing_cutpoint(self, B_cutpoints, point): |
||

177 | ```
indices = list()
``` |
||

178 | for i, cp in enumerate(B_cutpoints): |
||

179 | if point in cp: |
||

180 | indices.append(i) |
||

181 | |||

182 | ```
return indices
``` |
||

183 | |||

184 | def get_link_weight(self, comp_index, point): |
||

185 | ```
Dv_B_comp = self.Dv_B[comp_index]
``` |
||

186 | |||

187 | if point in Dv_B_comp: |
||

188 | ```
return Dv_B_comp[point]
``` |
||

189 | ```
else:
``` |
||

190 | return 0 |
||

191 | |||

192 | 3c6ce57c | Quynh PX Nguyen | def set_link_weight(self, comp_index, point, value): |

193 | ```
self.Dv_B[comp_index][point] = value
``` |
||

194 | |||

195 | 181e7c50 | Quynh PX Nguyen | def get_reverse_link_weight(self, comp_index, point): |

196 | ```
reverse_Dv_B_comp = self.reverse_Dv_B[comp_index]
``` |
||

197 | |||

198 | if point in reverse_Dv_B_comp: |
||

199 | ```
return reverse_Dv_B_comp[point]
``` |
||

200 | ```
else:
``` |
||

201 | return 0 |
||

202 | |||

203 | def generate_link_weight(self): |
||

204 | ```
# How many cutpoints does this component have
``` |
||

205 | ```
B_plus_v = list()
``` |
||

206 | B_cutpoints = list() # number of cutpoints in component B |
||

207 | for comp in self.bicomponents: |
||

208 | ```
points = comp.intersection(self.cutpoints)
``` |
||

209 | B_plus_v.append(comp.difference(points)) |
||

210 | B_cutpoints.append(points) |
||

211 | |||

212 | len_B_plus_v = [len(x) for x in B_plus_v] |
||

213 | len_B_cutpoints = [len(x) for x in B_cutpoints] |
||

214 | |||

215 | ```
# Calculate the Dv_B
``` |
||

216 | |||

217 | ```
# For the leaf in the block-cut tree
``` |
||

218 | ```
level = 1
``` |
||

219 | for (i, cp) in enumerate(B_cutpoints): |
||

220 | ```
if len_B_cutpoints[i] == level:
``` |
||

221 | point = list(cp)[0] # there is only 1 element |
||

222 | ```
self.Dv_B[i][point] = len_B_plus_v[i]
``` |
||

223 | |||

224 | ```
# For other nodes in the block-cut tree
``` |
||

225 | ```
level += 1
``` |
||

226 | while level <= max(len_B_cutpoints): |
||

227 | 3c6ce57c | Quynh PX Nguyen | if level == 3: |

228 | debugger() |
||

229 | 181e7c50 | Quynh PX Nguyen | for (i, cp) in enumerate(B_cutpoints): |

230 | ```
if len_B_cutpoints[i] == level:
``` |
||

231 | |||

232 | for point in cp: |
||

233 | 3c6ce57c | Quynh PX Nguyen | ```
# 1st way
``` |

234 | 181e7c50 | Quynh PX Nguyen | ```
shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, point)
``` |

235 | shared_comp_indices.remove(i) |
||

236 | ```
weight_shared_comp = list()
``` |
||

237 | |||

238 | for index in shared_comp_indices: |
||

239 | ```
weight_shared_comp.append(self.get_link_weight(index, point))
``` |
||

240 | |||

241 | 3c6ce57c | Quynh PX Nguyen | weight = self.num_vertices - 1 - sum(weight_shared_comp) |

242 | 181e7c50 | Quynh PX Nguyen | |

243 | ```
self.Dv_B[i][point] = weight
``` |
||

244 | |||

245 | ```
level += 1
``` |
||

246 | |||

247 | def generate_reverse_link_weight(self): |
||

248 | for i, Dv_B_i in enumerate(self.Dv_B): |
||

249 | for key, value in Dv_B_i.iteritems(): |
||

250 | self.reverse_Dv_B[i][key] = self.num_vertices - 1 - self.get_link_weight(i, key) |
||

251 | |||

252 | 3c6ce57c | Quynh PX Nguyen | def compute_component_tree_weight(self): |

253 | ```
"""Follows exactly the Algorithm 1 [Puzis 2012]
``` |
||

254 | ```
"""
``` |
||

255 | B_cutpoints = list() # number of cutpoints in component B |
||

256 | for comp in self.bicomponents: |
||

257 | ```
points = comp.intersection(self.cutpoints)
``` |
||

258 | B_cutpoints.append(points) |
||

259 | |||

260 | ```
Q = self._inititalize_component_tree_weight()
``` |
||

261 | ```
while Q:
``` |
||

262 | ```
pair = Q.pop(0)
``` |
||

263 | if pair['type'] == 'component_vertex_pair': |
||

264 | B_index = pair['value'][0] |
||

265 | v = pair['value'][1] |
||

266 | size = len(self.bicomponents[B_index]) - 1; |
||

267 | all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints) |
||

268 | all_cutpoints.remove(v) |
||

269 | |||

270 | for cp in all_cutpoints: |
||

271 | if self.get_link_weight(B_index, cp) != -1: |
||

272 | 24a4abf9 | Quynh PX Nguyen | size += self.num_vertices - self.get_link_weight(B_index, cp) - 1 |

273 | 3c6ce57c | Quynh PX Nguyen | |

274 | 739fe075 | Quynh PX Nguyen | link_weight = size |

275 | ```
self._verify_link_weight(B_index, v, link_weight)
``` |
||

276 | ```
self.set_link_weight(B_index, v, link_weight)
``` |
||

277 | 3c6ce57c | Quynh PX Nguyen | |

278 | ```
# update Q
``` |
||

279 | ```
Q = self._find_unknown_weight_wrt_cutpoint(v, Q)
``` |
||

280 | |||

281 | if pair['type'] == 'vertex_component_pair': |
||

282 | 24a4abf9 | Quynh PX Nguyen | ```
size = 0
``` |

283 | 3c6ce57c | Quynh PX Nguyen | B_index = pair['value'][0] |

284 | v = pair['value'][1] |
||

285 | ```
shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v)
``` |
||

286 | shared_comp_indices.remove(B_index) |
||

287 | |||

288 | |||

289 | for i in shared_comp_indices: |
||

290 | if self.get_link_weight(i, v) != - 1: |
||

291 | ```
size += self.get_link_weight(i, v)
``` |
||

292 | |||

293 | 739fe075 | Quynh PX Nguyen | link_weight = self.num_vertices - 1 - size |

294 | ```
self._verify_link_weight(B_index, v, link_weight)
``` |
||

295 | ```
self.set_link_weight(B_index, v, link_weight)
``` |
||

296 | 3c6ce57c | Quynh PX Nguyen | |

297 | ```
# update Q
``` |
||

298 | ```
Q = self._find_unknown_weight_wrt_component(B_index, Q)
``` |
||

299 | |||

300 | 739fe075 | Quynh PX Nguyen | def _verify_link_weight(self, B_index, v, value): |

301 | ```
""" If the old_value exist in self.Dv_B, then it must be equal to new value
``` |
||

302 | ```
``` |
||

303 | ```
Otherwise, do nothing
``` |
||

304 | ```
"""
``` |
||

305 | ```
old_value = self.get_link_weight(B_index, v)
``` |
||

306 | 82c7c698 | Quynh PX Nguyen | |

307 | if old_value != -1: # -1 is unknown |
||

308 | 739fe075 | Quynh PX Nguyen | ```
if old_value != value:
``` |

309 | print "BUGS FOUND in _verify_link_weight()" |
||

310 | sys.exit() |
||

311 | |||

312 | 24a4abf9 | Quynh PX Nguyen | |

313 | 3c6ce57c | Quynh PX Nguyen | def _inititalize_component_tree_weight(self): |

314 | Q = [] |
||

315 | for i, comp in enumerate(self.bicomponents): |
||

316 | ```
current_cutpoints = self.cutpoints.intersection(comp)
``` |
||

317 | if len(current_cutpoints) == 1: |
||

318 | Q.append({ |
||

319 | 'type': 'component_vertex_pair', |
||

320 | 'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (i-th component, the cutpoint name) |
||

321 | }) |
||

322 | for cp in current_cutpoints: |
||

323 | self.set_link_weight(i, cp, -1) |
||

324 | ```
return Q
``` |
||

325 | |||

326 | def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q): |
||

327 | 24a4abf9 | Quynh PX Nguyen | ```
# Cut-point v such that the weights of all but one of its links in T are already computed.
``` |

328 | ```
num_of_uncomputed_weight = 0
``` |
||

329 | uncomputed_component_index = [] |
||

330 | |||

331 | 3c6ce57c | Quynh PX Nguyen | for i, Dv_B_comp in enumerate(self.Dv_B): |

332 | 24a4abf9 | Quynh PX Nguyen | if cutpoint in Dv_B_comp: |

333 | if Dv_B_comp[cutpoint] == -1: |
||

334 | ```
num_of_uncomputed_weight += 1
``` |
||

335 | uncomputed_component_index.append(i) |
||

336 | if num_of_uncomputed_weight == 1: |
||

337 | pair = { |
||

338 | 'type': 'vertex_component_pair', |
||

339 | ```
'value': (uncomputed_component_index.pop(), cutpoint)
``` |
||

340 | } |
||

341 | Q.append(pair) |
||

342 | ```
return Q
``` |
||

343 | |||

344 | def _find_unknown_weight_wrt_component(self, comp_index, Q): |
||

345 | ```
# Component B such that weights of all but one of its links in T are already computed.
``` |
||

346 | ```
Dv_B_comp = self.Dv_B[comp_index]
``` |
||

347 | values = Dv_B_comp.values() |
||

348 | |||

349 | ```
# Check if -1 value appear only 1 time
``` |
||

350 | ```
flag = False
``` |
||

351 | minus_one_value = [x for x in values if x == -1] |
||

352 | if len(minus_one_value) == 1: |
||

353 | 3c6ce57c | Quynh PX Nguyen | for cp, value in Dv_B_comp.iteritems(): |

354 | if value == -1: |
||

355 | pair = { |
||

356 | 24a4abf9 | Quynh PX Nguyen | 'type': 'component_vertex_pair', |

357 | ```
'value': (comp_index, cp)
``` |
||

358 | 3c6ce57c | Quynh PX Nguyen | } |

359 | Q.append(pair) |
||

360 | ```
return Q
``` |
||

361 | |||

362 | 181e7c50 | Quynh PX Nguyen | def __str__(self): |

363 | return str(self.Dv_B) |
||

364 | |||

365 | def analyse_biconnected_component(graph): |
||

366 | ```
bicomponents = list(nx.biconnected_components(graph))
``` |
||

367 | ```
print bicomponents
``` |
||

368 | print [len(x) for x in bicomponents] |
||

369 | |||

370 | 3c6ce57c | Quynh PX Nguyen | def find_heuristic_bc(filepath): |

371 | 82c7c698 | Quynh PX Nguyen | ```
filename = os.path.splitext(os.path.basename(filepath))[0]
``` |

372 | 739fe075 | Quynh PX Nguyen | |

373 | 3c6ce57c | Quynh PX Nguyen | ```
pp = pprint.PrettyPrinter(indent=4)
``` |

374 | 181e7c50 | Quynh PX Nguyen | |

375 | graph = nx.read_weighted_edgelist(filepath) |
||

376 | |||

377 | 739fe075 | Quynh PX Nguyen | if not nx.is_connected(graph): |

378 | print "Graph is not connected" |
||

379 | ```
# sys.exit()
``` |
||

380 | ```
else:
``` |
||

381 | print "Graph is connected" |
||

382 | |||

383 | 181e7c50 | Quynh PX Nguyen | ```
# Find biconnected components
``` |

384 | analyse_biconnected_component(graph) |
||

385 | |||

386 | ```
subgraphs = list(nx.biconnected_component_subgraphs(graph))
``` |
||

387 | ```
bicomponents = list(nx.biconnected_components(graph))
``` |
||

388 | ```
component_edges = list(nx.biconnected_component_edges(graph))
``` |
||

389 | ```
cutpoints = set(nx.articulation_points(graph))
``` |
||

390 | |||

391 | num_vertices = nx.number_of_nodes(graph) |
||

392 | |||

393 | lw = LinkWeight(graph, bicomponents, cutpoints) |
||

394 | 3c6ce57c | Quynh PX Nguyen | |

395 | 24a4abf9 | Quynh PX Nguyen | tm = TrafficMatrix(bicomponents, cutpoints, lw) |

396 | 181e7c50 | Quynh PX Nguyen | |

397 | 24a4abf9 | Quynh PX Nguyen | bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm) |

398 | bc.write(file_suffix) |
||

399 | 739fe075 | Quynh PX Nguyen | ```
print bc
``` |

400 | 181e7c50 | Quynh PX Nguyen | |

401 | 82c7c698 | Quynh PX Nguyen | def test_isomorphic_graphs(filepath1, filepath2): |

402 | graph1 = nx.read_weighted_edgelist(filepath1) |
||

403 | graph2 = nx.read_weighted_edgelist(filepath2) |
||

404 | print "Isomorphic = %s" % nx.is_isomorphic(graph1, graph2) |
||

405 | |||

406 | |||

407 | 3c6ce57c | Quynh PX Nguyen | if __name__ == '__main__': |

408 | 739fe075 | Quynh PX Nguyen | utility.initialize() |

409 | 82c7c698 | Quynh PX Nguyen | ```
f1 = MAIN_CODE_DIR + '/input/9_vertices_green.edges'
``` |

410 | ```
f2 = MAIN_CODE_DIR + '/input/9_vertices_blue.edges'
``` |
||

411 | test_isomorphic_graphs(f1, f2) |
||

412 | 739fe075 | Quynh PX Nguyen | |

413 | 3c6ce57c | Quynh PX Nguyen | ```
# filepath = MAIN_CODE_DIR + '/input/simple_house.edges'
``` |

414 | ```
# filepath = MAIN_CODE_DIR + '/input/simple2.edges'
``` |
||

415 | ```
# filepath = MAIN_CODE_DIR + '/input/simple.edges'
``` |
||

416 | 739fe075 | Quynh PX Nguyen | ```
# filepath = MAIN_CODE_DIR + '/input/ninux_simplified.edges'
``` |

417 | ```
# filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected.edges'
``` |
||

418 | 82c7c698 | Quynh PX Nguyen | ```
# filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected2.edges'
``` |

419 | ```
# filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected3.edges'
``` |
||

420 | ```
# filepath = MAIN_CODE_DIR + '/input/9_vertices_green.edges'
``` |
||

421 | ```
# filepath = MAIN_CODE_DIR + '/input/9_vertices_blue.edges'
``` |
||

422 | ```
# filepath = MAIN_CODE_DIR + '/input/simple_loop.edges'
``` |
||

423 | ```
# filepath = MAIN_CODE_DIR + '/input/straight_line.edges'
``` |
||

424 | 739fe075 | Quynh PX Nguyen | ```
# filepath = MAIN_CODE_DIR + '/input/ninux_connected.edges'
``` |

425 | ```
# filepath = MAIN_CODE_DIR + '/input/ninux_unweighted.edges'
``` |
||

426 | ```
# filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified.edges'
``` |
||

427 | ```
# filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified_connected.edges'
``` |
||

428 | 3c6ce57c | Quynh PX Nguyen | ```
# filepath = MAIN_CODE_DIR + '/input/simple3.edges'
``` |

429 | 24a4abf9 | Quynh PX Nguyen | ```
# filepath = MAIN_CODE_DIR + '/input/simple4.edges'
``` |

430 | 739fe075 | Quynh PX Nguyen | ```
# filepath = MAIN_CODE_DIR + '/input/simple5.edges'
``` |

431 | 82c7c698 | Quynh PX Nguyen | |

432 | ```
filepath = MAIN_CODE_DIR + '/input/ninux.edges'
``` |
||

433 | 3c6ce57c | Quynh PX Nguyen | ```
file_suffix = 'edge_list'
``` |

434 | |||

435 | 82c7c698 | Quynh PX Nguyen | ```
# Weight betweenness centrality
``` |

436 | utility.weight_betweenness_centrality(filepath, file_suffix) |
||

437 | 739fe075 | Quynh PX Nguyen | |

438 | 82c7c698 | Quynh PX Nguyen | ```
# Brandess betweenness centrality
``` |

439 | utility.brandes_betweenness_centrality(filepath, file_suffix) |
||

440 | 3c6ce57c | Quynh PX Nguyen | |

441 | 82c7c698 | Quynh PX Nguyen | ```
# Heuristic BC
``` |

442 | find_heuristic_bc(filepath) |