greedy_links_directed.py 2.36 KB
Newer Older
Thomas Fenz's avatar
Thomas Fenz committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
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