import networkx as nx import heuristics_helper_directed as helper def __greedy_links(G, nx_static, optical_topology, D, nN, nR): obj_function_list = [] links = [] temp_static = nx_static.copy() temp_G = G.copy() current_obj_fct_value = -1 for (s, i, j) in optical_topology: links += [(i, j)] for k in range(len(links)): for (i, j) in links: if nx.shortest_path_length(temp_static, i, j, "weight") > nx.shortest_path_length(temp_G, i, j, "weight"): temp_static = helper.update_graph(temp_G, temp_static, nx.shortest_path(G, i, j, "weight"), False, optical_topology, nN, nR) obj_function_list += [helper.get_objective(temp_static, D)] else: obj_function_list += [helper.get_objective(temp_static, D)] temp_static = nx_static.copy() temp_G = G.copy() min_distance = min(obj_function_list) if min_distance == current_obj_fct_value: return nx_static else: current_obj_fct_value = min_distance min_index = obj_function_list.index(min_distance) (start, end) = links[min_index] if nx.shortest_path_length(nx_static, start, end, "weight") > nx.shortest_path_length(G, start, end, "weight"): helper.update_graph(G, nx_static, nx.shortest_path(G, start, end, "weight"), True, optical_topology, nN, nR) obj_function_list = [] links.remove((start, end)) return nx_static def solve(s, o, D): ex = None nx_full_topology = nx.MultiDiGraph() # represents all currently possible edges nx_static_topology = nx.MultiDiGraph() # represents static edges and matching made all_arcs_ij = set([(i, j) for _, i, j in o]) all_arcs_ij.update(s) nN = int(max(max(i, j) for i, j in all_arcs_ij) + 1) nR = int(max(R for R, _, _ in o) + 1) for i, j in s: nx_static_topology.add_edge(i, j, weight=s[(i, j)]) nx_full_topology.add_edge(i, j, key=0, weight=s[(i, j)]) for r, i, j in o: nx_full_topology.add_edge(i, j, key=r + 1, weight=o[(r, i, j)]) try: solution = helper.get_objective( __greedy_links(nx_full_topology.copy(), nx_static_topology.copy(), o, D, nN, nR), D) except ex as Exception: return False, str(ex), "" return True, "", solution