(distance_matrix, pi = None, root = 0)
| 257 | return edges, float(cost) |
| 258 | |
| 259 | def _minimum_one_tree(distance_matrix, pi = None, root = 0): |
| 260 | n = distance_matrix.shape[0] |
| 261 | if pi is None: |
| 262 | pi = np.zeros(n) |
| 263 | weighted = distance_matrix + pi.reshape((n, 1)) + pi.reshape((1, n)) |
| 264 | |
| 265 | nodes = [i for i in range(0, n) if i != root] |
| 266 | mst_edges, mst_cost = _mst_prim(weighted, nodes) |
| 267 | |
| 268 | root_edges = sorted([(weighted[root, j], root, j) for j in nodes], key = lambda x: x[0]) |
| 269 | e1 = (root_edges[0][1], root_edges[0][2]) |
| 270 | e2 = (root_edges[1][1], root_edges[1][2]) |
| 271 | |
| 272 | edges = mst_edges + [e1, e2] |
| 273 | weighted_cost = mst_cost + root_edges[0][0] + root_edges[1][0] |
| 274 | |
| 275 | degree = np.zeros(n, dtype = int) |
| 276 | for i, j in edges: |
| 277 | degree[i] = degree[i] + 1 |
| 278 | degree[j] = degree[j] + 1 |
| 279 | |
| 280 | lower_bound = weighted_cost - 2.0 * np.sum(pi) |
| 281 | return edges, degree, float(weighted_cost), float(lower_bound), weighted |
| 282 | |
| 283 | def _subgradient_potentials(distance_matrix, root = 0, ascent_iterations = 100): |
| 284 | n = distance_matrix.shape[0] |
no test coverage detected