(distance_matrix, root = 0, ascent_iterations = 100)
| 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] |
| 285 | pi = np.zeros(n, dtype = float) |
| 286 | |
| 287 | edges, degree, weighted_cost, lb, weighted = _minimum_one_tree(distance_matrix, pi = pi, root = root) |
| 288 | best_pi = pi.copy() |
| 289 | best_edges = edges |
| 290 | best_degree = degree.copy() |
| 291 | best_lb = lb |
| 292 | |
| 293 | positive_distances = distance_matrix[distance_matrix > 0] |
| 294 | scale = float(np.mean(positive_distances)) if positive_distances.size > 0 else 1.0 |
| 295 | |
| 296 | total_iterations = max(0, int(ascent_iterations)) |
| 297 | if total_iterations == 0: |
| 298 | return best_pi, best_edges, best_degree, best_lb |
| 299 | |
| 300 | period = max(4, total_iterations // 4) |
| 301 | step_scale = scale |
| 302 | prev_g = np.zeros(n, dtype = float) |
| 303 | t = 0 |
| 304 | |
| 305 | while t < total_iterations: |
| 306 | for _ in range(period): |
| 307 | if t >= total_iterations: |
| 308 | break |
| 309 | edges, degree, weighted_cost, lb, weighted = _minimum_one_tree(distance_matrix, pi = pi, root = root) |
| 310 | if lb > best_lb + 1e-12: |
| 311 | best_lb = lb |
| 312 | best_pi = pi.copy() |
| 313 | best_edges = edges |
| 314 | best_degree = degree.copy() |
| 315 | |
| 316 | g = (degree - 2).astype(float) |
| 317 | norm = float(np.dot(g, g)) |
| 318 | if norm <= 1e-12: |
| 319 | best_pi = pi.copy() |
| 320 | best_edges = edges |
| 321 | best_degree = degree.copy() |
| 322 | best_lb = lb |
| 323 | return best_pi, best_edges, best_degree, best_lb |
| 324 | |
| 325 | beta = 0.3 if t > 0 else 0.0 |
| 326 | direction = g + beta * (g - prev_g) |
| 327 | dir_norm = float(np.dot(direction, direction)) |
| 328 | if dir_norm <= 1e-12: |
| 329 | direction = g |
| 330 | dir_norm = norm |
| 331 | |
| 332 | step = step_scale / np.sqrt(dir_norm) |
| 333 | pi = pi + step * direction |
| 334 | pi = pi - np.mean(pi) |
| 335 | prev_g = g |
| 336 | t = t + 1 |
| 337 | |
| 338 | step_scale = 0.5 * step_scale |
| 339 | period = max(2, period // 2) |
| 340 |
no test coverage detected