from operator import itemgetter
import random
import numpy as np
import networkx as nx
import time
from itertools import product
from utils import (
graph_cost,
graph_with_calc_edge_capacity,
create_compl_graph_from_other,
)
"""
This script generates spanning trees and iterates over the heuristic network optimization algorithms
"""
def optimal_from_prufer_sequence(input_graph, cost_function):
"""
Finds global minimum-cost graph from another graph object,
by iterating over all possible trees.
Based on the method described in the appendices of Heijenen et al 2020:
"A method for designing minimum‐cost multisource multisink network layouts"
https://doi.org/10.1002/sys.21492
Args:
input_graph: NetworkX Graph
cost_function: a cost function of the capacity
Returns:
optimal networkx Graph
cost of optimal graph
"""
graph = input_graph.copy()
#Number of nodes
n = len(list(graph))
nodes_list = graph.nodes()
#Rename nodes as integers
dict_lab = dict(zip(range(n), nodes_list))
graph = nx.convert_node_labels_to_integers(graph)
cost_initial = np.inf
#Generate prufer sequences of all possible trees
prufer_sequences = list(product(range(n), repeat = n-2))
#Check every possible tree for a lower cost solution
for tree in prufer_sequences:
candidate_graph = graph.copy()
candidate_graph.remove_edges_from(list(candidate_graph.edges()))
candidate_graph.add_edges_from(list(nx.from_prufer_sequence(tree).edges()))
#Relabel with original node labels
candidate_graph = nx.relabel_nodes(candidate_graph, dict_lab)
candidate_graph = graph_with_calc_edge_capacity(candidate_graph)
new_cost = graph_cost(cost_function, candidate_graph)
if new_cost < cost_initial:
incumbent_graph = candidate_graph.copy()
cost_initial = new_cost
return incumbent_graph, cost_initial
def local_search(input_graph, cost_function):
"""
Heuristic to provide minimum-cost tree from another tree,
by creating and breaking cycles in the trees before calculating cost.
Steepest-descent algorithm. Not guaranteed to provide global minima solutions.
Based on the method described in Brimberg 2003
"An oil pipeline design problem."
http://dx.doi.org/10.1287/opre.51.2.228.12786
Args:
input_graph: NetworkX Graph
cost_function: a cost function of the capacity
Returns:
optimized Networkx Graph
cost of optimized graph
"""
complete_graph = create_compl_graph_from_other(input_graph)
initial_cost = graph_cost(cost_function, input_graph)
nodes_i = list(input_graph.nodes())
#This variable serves to stop the while loop if no better solution is found
better_found = True
candidate_graph = input_graph.copy()
while better_found == True:
initial_cost = graph_cost(cost_function, candidate_graph)
better_found = False
#Potential list of cheaper trees:
results = []
#Add current best solution
results.append([initial_cost, candidate_graph.copy()])
for node_iter_i in nodes_i:
#Find all potential neighbours to node_i
nodes_ij = list(complete_graph[node_iter_i])
#Find all existing neighbours to node_i
existing_neighbours = list(candidate_graph.neighbors(node_iter_i))
#Get candiate nodes that aren't connected to node_i
for node_neighbour in existing_neighbours:
nodes_ij.remove(node_neighbour)
#Create cycle by connecting candidate nodes
for node_ij_iter in nodes_ij:
candidate_graph2 = candidate_graph.copy()
candidate_graph2.add_edge(
node_ij_iter,
node_iter_i,
weight=complete_graph[node_ij_iter][node_iter_i]["weight"],
)
edges_cycle = nx.find_cycle(candidate_graph2)
try:
edges_cycle.remove((node_ij_iter, node_iter_i))
except ValueError:
edges_cycle.remove((node_iter_i, node_ij_iter))
#Test removing each edge in the new cycle and calculate graph cost
for candidate_edge_remove in edges_cycle:
candidate_graph3 = candidate_graph2.copy()
candidate_graph3.remove_edge(*candidate_edge_remove)
candidate_graph3 = graph_with_calc_edge_capacity(candidate_graph3)
new_cost = graph_cost(cost_function, candidate_graph3)
if new_cost < initial_cost:
results.append([new_cost, candidate_graph3])
#If better solution found:
if len(results) > 1:
better_found = True
results.sort(key=lambda x: x[0])
candidate_graph = results[0][1]
#Otherwise exit whle loop (better_found is stil True) and return the incumbent solution
else:
candidate_graph = results[0][1]
return candidate_graph, graph_cost(cost_function, candidate_graph)
def delta_change(input_graph, cost_function):
"""
Heuristic to provide minimum-cost tree from another tree,
by creating and breaking cycles in the trees before calculating cost.
First-descent algorithm. Not guaranteed to provide global minima solutions.
Based on the method described by Rothfarb 1970
"Optimal Design of Offshore Natural-Gas Pipeline Systems"
https://doi.org/10.1287/opre.18.6.992
with additions (highlighted here) from Andre 2013
"Design and dimensioning of hydrogen transmission pipeline networks"
https://doi.org/10.1016/j.ejor.2013.02.036
Args:
input_graph: NetworkX Graph
cost_function: a cost function of the capacity
Returns:
optimized Networkx Graph
cost of optimized graph
"""
complete_graph = create_compl_graph_from_other(input_graph)
nodes_i = list(input_graph.nodes())
#Randomisation of node list as indicated in Andre 2013:
random.shuffle(nodes_i)
#This variable serves to stop the while loop if no better solution is found
better_found = True
candidate_graph = input_graph.copy()
while better_found == True:
better_found = False
initial_cost = graph_cost(cost_function, candidate_graph)
for node_iter_i in nodes_i:
#The following paragraph of code would correspond to an addition of Andre 2013
#In which only the closest nodes to reconnect are considered.
#The value of 5 closest nodes is set here.
#We choose not to implement this addition
#Here the weight property of the graph is simply distance
#sorted_dist = [(x[0],x[1]['weight']) for x in dict(complete_graph[node_iter_i]).items()]
#sorted_dist.sort(key=itemgetter(1))
#nodes_ij = [x[0] for x in sorted_dist][:5]
#Find all potential neighbours to node_i
nodes_ij = list(complete_graph[node_iter_i])
#Find all existing neighbours to node_i
existing_neighbours = list(candidate_graph.neighbors(node_iter_i))
#Get candiate nodes that aren't connected to node_i
for node_neighbour in existing_neighbours:
nodes_ij.remove(node_neighbour)
#Create cycle by connecting candidate nodes
for node_ij_iter in nodes_ij:
candidate_graph2 = candidate_graph.copy()
candidate_graph2.add_edge(
node_ij_iter,
node_iter_i,
weight=complete_graph[node_ij_iter][node_iter_i]["weight"],
)
edges_cycle = nx.find_cycle(candidate_graph2)
try:
edges_cycle.remove((node_ij_iter, node_iter_i))
except ValueError:
edges_cycle.remove((node_iter_i, node_ij_iter))
#Test removing each edge in the new cycle and calculate graph cost
for candidate_edge_remove in edges_cycle:
candidate_graph3 = candidate_graph2.copy()
candidate_graph3.remove_edge(*candidate_edge_remove)
candidate_graph3 = graph_with_calc_edge_capacity(candidate_graph3)
new_cost = graph_cost(cost_function, candidate_graph3)
#As soon as better solution is found break all loops and restart:
if new_cost < initial_cost:
candidate_graph = candidate_graph3.copy()
initial_cost = new_cost
better_found = True
break
if better_found == True:
break
if better_found == True:
break
return candidate_graph, graph_cost(cost_function, candidate_graph)
def delta_change_recursive_under(input_graph, cost_function,recursion_level):
complete_graph = create_compl_graph_from_other(input_graph)
nodes_i = list(input_graph.nodes())
candidate_graph = input_graph.copy()
better_found = False
initial_cost = graph_cost(cost_function, candidate_graph)
for node_iter_i in nodes_i:
#Find all potential neighbours to node_i
nodes_ij = list(complete_graph[node_iter_i])
#Get candiate nodes that aren't connected to node_i
existing_neighbours = list(candidate_graph.neighbors(node_iter_i))
for node_neighbour in existing_neighbours:
nodes_ij.remove(node_neighbour)
#Create cycle by connecting candidate nodes
for node_ij_iter in nodes_ij:
candidate_graph2 = candidate_graph.copy()
candidate_graph2.add_edge(
node_ij_iter,
node_iter_i,
weight=complete_graph[node_ij_iter][node_iter_i]["weight"],
)
edges_cycle = nx.find_cycle(candidate_graph2)
try:
edges_cycle.remove((node_ij_iter, node_iter_i))
except ValueError:
edges_cycle.remove((node_iter_i, node_ij_iter))
#Test removing each edge in the new cycle and calculate graph cost
for candidate_edge_remove in edges_cycle:
candidate_graph3 = candidate_graph2.copy()
candidate_graph3.remove_edge(*candidate_edge_remove)
candidate_graph3 = graph_with_calc_edge_capacity(candidate_graph3)
new_cost = graph_cost(cost_function, candidate_graph3)
#As soon as better solution is found break all loops and restart:
if new_cost < initial_cost:
candidate_graph = candidate_graph3.copy()
initial_cost = new_cost
better_found = True
break
if recursion_level >1:
nested_candidate,nested_cost = delta_change_recursive(candidate_graph3, cost_function,recursion_level-1)
if nested_cost < initial_cost:
candidate_graph = nested_candidate.copy()
initial_cost = nested_cost
better_found = True
break
if better_found == True:
break
if better_found == True:
break
return candidate_graph, graph_cost(cost_function, candidate_graph)
def delta_change_recursive(input_graph, cost_function,recursion_level = 2):
"""
Heuristic to provide minimum-cost tree from another tree,
by creating and breaking cycles in the trees before calculating cost.
First-descent algorithm. Not guaranteed to provide global minima solutions.
This algorithm is a recursive version of a simpler algorithm "delta_change".
In this algorithm the delta_change is performed,
and on each intermediate candidate tree, a nested delta_change is performed, and so on...
allowing jumps into the neigbourhood solution space of the recursion level in one step.
In this implementation we remove the Andre's (2013) additions the delta_change algorithm (and references to them),
although including them (notably only taking closest candidate nodes) could reduce calculation time.
Note that calcaulation time becomes usually becomes impratical for input recusion levels above 3 and node numbers above 10.
Args:
input_graph: NetworkX Graph
cost_function: a cost function of the capacity
Returns:
optimized Networkx Graph
cost of optimized graph
"""
complete_graph = create_compl_graph_from_other(input_graph)
nodes_i = list(input_graph.nodes())
#Randomisation of node list as indicated in Andre 2013:
random.shuffle(nodes_i)
#This variable serves to stop the while loop if no better solution is found
better_found = True
candidate_graph = input_graph.copy()
while better_found == True:
better_found = False
initial_cost = graph_cost(cost_function, candidate_graph)
for node_iter_i in nodes_i:
#if node_iter
#Find all potential neighbours to node_i
nodes_ij = list(complete_graph[node_iter_i])
#Get candiate nodes that aren't connected to node_i
existing_neighbours = list(candidate_graph.neighbors(node_iter_i))
for node_neighbour in existing_neighbours:
nodes_ij.remove(node_neighbour)
#Create cycle by connecting candidate nodes
for node_ij_iter in nodes_ij:
candidate_graph2 = candidate_graph.copy()
candidate_graph2.add_edge(
node_ij_iter,
node_iter_i,
weight=complete_graph[node_ij_iter][node_iter_i]["weight"],
)
edges_cycle = nx.find_cycle(candidate_graph2)
try:
edges_cycle.remove((node_ij_iter, node_iter_i))
except ValueError:
edges_cycle.remove((node_iter_i, node_ij_iter))
#Test removing each edge in the new cycle and calculate graph cost
for candidate_edge_remove in edges_cycle:
candidate_graph3 = candidate_graph2.copy()
candidate_graph3.remove_edge(*candidate_edge_remove)
candidate_graph3 = graph_with_calc_edge_capacity(candidate_graph3)
new_cost = graph_cost(cost_function, candidate_graph3)
#As soon as better solution is found break all loops and restart:
if new_cost < initial_cost:
candidate_graph = candidate_graph3.copy()
initial_cost = new_cost
better_found = True
break
if recursion_level >1:
nested_candidate,nested_cost = delta_change_recursive_under(candidate_graph3, cost_function,recursion_level-1)
if nested_cost < initial_cost:
candidate_graph = nested_candidate.copy()
initial_cost = nested_cost
better_found = True
break
if better_found == True:
break
if better_found == True:
break
return candidate_graph, graph_cost(cost_function, candidate_graph)
def edge_turn(input_graph, cost_function):
"""
Heuristic to provide minimum-cost tree from another tree,
by breaking the tree in two,
and reconnecting the two connected components elswehere in the trees before calculating cost.
Steepest-descent algorithm. Not guaranteed to provide global minima solutions.
Based on the edge-turn method described in Heijenen et al 2019:
"A method for designing minimum‐cost multisource multisink network layouts"
https://doi.org/10.1002/sys.21492
Args:
input_graph: NetworkX Graph
cost_function: a cost function of the capacity
Returns:
optimized Networkx Graph
cost of optimized graph
"""
#This variable serves to stop the while loop if no better solution is found
better_found = True
candidate_graph = input_graph.copy()
while better_found == True:
better_found = False
initial_cost = graph_cost(cost_function, candidate_graph)
#Potential list of cheaper trees:
results = []
#Add current best solution
results.append([initial_cost, candidate_graph.copy()])
#Test removing edges and reconnecting elswehere
for edge in candidate_graph.edges:
candidate_graph2 = candidate_graph.copy()
candidate_graph2.remove_edge(*edge)
#For each removed edge, all nodes of either connected component are re-attached to the node in the oher connected compoenent from the removed edge
# the following codeblock in then repeated only twice in the for loop: once for each connected component
#Iterates over both connected components:
for component in list(nx.connected_components(candidate_graph2)):
connected = list(component)
#Finding the terminal in the removed edge that is not in the connected component considered
if edge[0] not in connected:
term = edge[0]
else:
term = edge[1]
for comp in connected:
candidate_graph_test = candidate_graph2.copy()
candidate_graph_test.add_edge(term, comp)
candidate_graph_test = graph_with_calc_edge_capacity(candidate_graph_test)
new_cost = graph_cost(cost_function, candidate_graph_test)
if new_cost < initial_cost:
results.append([new_cost, candidate_graph_test])
#If better solution found:
if len(results) > 1:
better_found = True
results.sort(key=lambda x: x[0])
candidate_graph = results[0][1]
#Otherwise exit whle loop (check is stil True) and return the incumbent solution
else:
candidate_graph = results[0][1]
input_graph = candidate_graph.copy()
return input_graph, graph_cost(cost_function, input_graph)
def edge_turn_recursive_under(input_graph, cost_function,recursion_level):
#This variable serves to stop the while loop if no better solution is found
candidate_graph = input_graph.copy()
better_found = False
initial_cost = graph_cost(cost_function, candidate_graph)
#Potential list of cheaper trees:
results = []
#Add current best solution
results.append([initial_cost, candidate_graph.copy()])
#Iterates over the edges to remove
for edge in candidate_graph.edges:
candidate_graph2 = candidate_graph.copy()
candidate_graph2 = graph_with_calc_edge_capacity(candidate_graph2)
candidate_graph2.remove_edge(*edge)
#For each removed edge, all nodes of either connected component are re-attached
#to the node in the oher connected compoenent from the removed edge.
#The following codeblock in then repeated only twice in the for loop: once for each connected component
#Iterates over both connected components:
for component in list(nx.connected_components(candidate_graph2)):
connected = list(component)
#Finding the terminal in the removed edge that is not in the connected component considered
if edge[0] not in connected:
term = edge[0]
else:
term = edge[1]
for comp in connected:
candidate_graph_test = candidate_graph2.copy()
candidate_graph_test.add_edge(term, comp)
candidate_graph_test = graph_with_calc_edge_capacity(candidate_graph_test)
new_cost = graph_cost(cost_function, candidate_graph_test)
if new_cost < initial_cost:
results.append([new_cost, candidate_graph_test])
if recursion_level >1:
nested_candidate,nested_cost = edge_turn_recursive_under(candidate_graph_test, cost_function,recursion_level-1)
if nested_cost < initial_cost:
results.append([nested_cost, nested_candidate])
#If better solution found:
if len(results) > 1:
better_found = True
results.sort(key=lambda x: x[0])
candidate_graph = results[0][1]
#Otherwise return the incumbent solution
else:
candidate_graph = results[0][1]
input_graph = candidate_graph.copy()
return input_graph, graph_cost(cost_function, input_graph)
def edge_turn_recursive(input_graph, cost_function,recursion_level = 2):
"""
Heuristic to provide minimum-cost tree from another tree,
by creating and breaking cycles in the trees before calculating cost.
Steepest-descent algorithm. Not guaranteed to provide global minima solutions.
This algorithm is a recursive version of a simpler algorithm "edge_turn".
In this algorithm the edge turn algorithm is performed,
and on each intermediate candidate tree, a nested turn algorithm is performed, and so on...
allowing jumps into the neigbourhood solution space of the recursion level in one step
In our implementation, the steepest descent applies to both the initial
and to the nested edge turn algorithm, and the chosen best tree is chosen
over all the initial and nested edge turns.
Args:
input_graph: NetworkX Graph
cost_function: a cost function of the capacity
Returns:
optimized Networkx Graph
cost of optimized graph
"""
#This variable serves to stop the while loop if no better solution is found
better_found = True
candidate_graph = input_graph.copy()
while better_found == True:
better_found = False
initial_cost = graph_cost(cost_function, candidate_graph)
#Potential list of cheaper trees:
results = []
#Add current best solution
results.append([initial_cost, candidate_graph.copy()])
#Iterates over the edges to remove
for edge in candidate_graph.edges:
candidate_graph2 = candidate_graph.copy()
candidate_graph2 = graph_with_calc_edge_capacity(candidate_graph2)
candidate_graph2.remove_edge(*edge)
#For each removed edge, all nodes of either connected component are re-attached
#to the node in the oher connected compoenent from the removed edge.
#The following codeblock in then repeated only twice in the for loop: once for each connected component
#Iterates over both connected components:
for component in list(nx.connected_components(candidate_graph2)):
connected = list(component)
#Finding the terminal in the removed edge that is not in the connected component considered
if edge[0] not in connected:
term = edge[0]
else:
term = edge[1]
for comp in connected:
candidate_graph_test = candidate_graph2.copy()
candidate_graph_test.add_edge(term, comp)
candidate_graph_test = graph_with_calc_edge_capacity(candidate_graph_test)
new_cost = graph_cost(cost_function, candidate_graph_test)
if new_cost < initial_cost:
results.append([new_cost, candidate_graph_test])
if recursion_level >1:
nested_candidate,nested_cost = edge_turn_recursive_under(candidate_graph_test, cost_function,recursion_level-1)
if nested_cost < initial_cost:
results.append([nested_cost, nested_candidate])
#If better solution found:
if len(results) > 1:
better_found = True
results.sort(key=lambda x: x[0])
candidate_graph = results[0][1]
#Otherwise exit whle loop (better_found is stil False) and return the incumbent solution
else:
candidate_graph = results[0][1]
input_graph = candidate_graph.copy()
return input_graph, graph_cost(cost_function, input_graph)
def vns(input_graph, cost_function):
"""
Metaheuristic to provide minimum-cost tree from another tree,
by exploring higher-cost solutions as ways out of local minima.
Makes jumps to neighbourhoods by creating and breaking
cycles a given number of times before performing local_search on the
cheapest found tree in the new optimization space.
This algorithm is based on the description for VNS given by
Brimberg in 2003:
"An oil pipeline design problem."
http://dx.doi.org/10.1287/opre.51.2.228.12786
The two parameters "k_max" and "time_stopped" are fixed here at values of 5 and 10 times
the time required for an initial local_search on the graph, as set by Brimberg.
These parameters correspond to the kmax and stopping criterion as described by Brimberg.
Args:
input_graph: NetworkX Graph
cost_function: a cost function of the capacity
Returns:
optimized Networkx Graph
cost of optimized graph
"""
#Initiate initial solution from local_search
start = time.time()
candidate_graph, cost_orig = local_search(input_graph, cost_function)
end = time.time()
local_search_time = end - start
#Set stoppping and kmax parameters
k_max = 5
time_stopped = 10*local_search_time
complete_graph = create_compl_graph_from_other(input_graph)
nodes_i = list(candidate_graph.nodes())
#Initiate stopping timer and neighbourhood distance
continue_k = False
start_full = time.time()
#While stopping criterion not reached
while time.time() - start_full < time_stopped:
#Start k at 1 and increase as long as kmax not reached
if continue_k == False:
k = 1
if continue_k == True:
k = k + 1
candidate_graph2 = candidate_graph.copy()
nodes_done = []
#Modify create and break a cycle in initial graph k times
for dummy in range(k):
works = True
#This while loop ensures that the node pairs to connect
#are not the same as old ones
while works == True:
nodes_i_it = nodes_i.copy()
node1_rand = random.choice(nodes_i_it)
existing_neighbours = list(candidate_graph.neighbors(node1_rand))
for node_neighbour in existing_neighbours:
nodes_i_it.remove(node_neighbour)
node2_rand = random.choice(nodes_i_it)
while (
node2_rand == node1_rand
or set([node1_rand, node2_rand]) in nodes_done
):
node2_rand = random.choice(nodes_i_it)
if node2_rand == node1_rand and [node2_rand] == nodes_i_it:
works = False
break
if works == False:
works = True
continue
#If new node pair is valid, connect them to create a cycle
candidate_graph2.add_edge(
node1_rand,
node2_rand,
weight=complete_graph[node1_rand][node2_rand]["weight"],
)
edges_cycle = nx.find_cycle(candidate_graph2)
#Dont allow the algorithm to remove the newly created edge
try:
edges_cycle.remove((node1_rand, node2_rand))
except ValueError:
edges_cycle.remove((node2_rand, node1_rand))
pot_graphs = []
#Find and keep the cheapest graph from the new cycle
for candidate_edge_remove in edges_cycle:
candidate_graph3 = candidate_graph2.copy()
candidate_graph3.remove_edge(*candidate_edge_remove)
candidate_graph3 = graph_with_calc_edge_capacity(candidate_graph3)
new_cost = graph_cost(cost_function, candidate_graph3)
pot_graphs.append((new_cost, candidate_graph3))
pot_graphs.sort(key=lambda x: x[0])
candidate_graph2 = pot_graphs[0][1]
nodes_done.append(set([node1_rand, node2_rand]))
works = False
#Do local search on the graph moved out of local minimum k times
candidate_graph_end, new_cost = local_search(candidate_graph2, cost_function)
#If a better solution found set as the incumbent solution and reinitialize k to 1
if new_cost < cost_orig:
candidate_graph = candidate_graph_end.copy()
continue_k = False
cost_orig = new_cost
#Else explore further away from incumbent solution
if k + 1 >= k_max:
continue_k = False
return candidate_graph, cost_orig
def tabu(input_graph, cost_function):
"""
Metaheuristic to provide minimum-cost tree from another tree,
by exploring higher-cost solutions as ways out of local minima.
Makes jumps to different solutions using by creating and breaking
cycles, and pursuing potentially higher-cost solutions in hope of finding
a lower minimum in the wider optimization space.
Once a transformation is made the reverse transformation is not allowed and
is added to the Tabu list.
This algorithm is based on the description for Tabu search given by
Brimberg in 2003:
"An oil pipeline design problem."
http://dx.doi.org/10.1287/opre.51.2.228.12786
The parameter "stopped" is fixed here at a value of 10.
This parameter corresponds to the stopping criterion as described by Brimberg.
Args:
s_ref: NetworkX Graph
func: a cost function of the capacity
Returns:
optimized Networkx Graph
cost of optimized graph .
"""
start = time.time()
#Initiate initial solution from local_search
best_graph, best_cost = local_search(input_graph, cost_function)
end = time.time()
local_time = end - start
#Set stopping parameter
time_stopped = 10*local_time
length_tabu = 7
candidate_graph = best_graph.copy()
#Complete graph for edges to add
complete_graph = create_compl_graph_from_other(candidate_graph)
#Initial Tabu list and stopping timer
tabu_list = []
start_full = time.time()
while time.time() - start_full < time_stopped:
sets_complete = [set(x) for x in complete_graph.edges()]
sets_candidate = [set(x) for x in candidate_graph.edges()]
#Potential edges to add
edges_not_there = [tuple(x) for x in sets_complete if x not in sets_candidate]
#Initiate potential solutions list
results = []
#Iterate over neighbourhood
for edge_test in edges_not_there:
candidate_graph2 = candidate_graph.copy()
candidate_graph2.add_edge(
edge_test[0],
edge_test[1],
weight=complete_graph[edge_test[0]][edge_test[1]]["weight"],)
edges_cycle = nx.find_cycle(candidate_graph2)
#Dont allow the algorithm to remove the newly created edge
try:
edges_cycle.remove((edge_test[0], edge_test[1]))
except ValueError:
edges_cycle.remove((edge_test[1], edge_test[0]))
#Break cycle and add solutions
for edge_rem in edges_cycle:
#Don't add solutions from Tabu list
if (set(edge_test),set(edge_rem)) in tabu_list or (set(edge_rem),set(edge_test)) in tabu_list:
continue
candidate_graph3 = candidate_graph2.copy()
candidate_graph3.remove_edge(*edge_rem)
candidate_graph3 = graph_with_calc_edge_capacity(candidate_graph3)
new_cost = graph_cost(cost_function, candidate_graph3)
results.append([new_cost, candidate_graph3, edge_test, edge_rem])
#Choose current "exploratory" solution as best from neighbourhood
results.sort(key=lambda x: x[0])
candidate_graph = results[0][1].copy()
#Add the transformation to Tabu list
if len(tabu_list) 2]
#Iterating over initial high valency nodes
for cand in candidates_high_valency:
sorted_dist = [
(x[0], x[1]["weight"]) for x in dict(complete_graph[cand[0]]).items()
]
#Find closest neighbours to transfer edges to (here closest 4)
sorted_dist.sort(key=itemgetter(1))
nodes_ij = [x[0] for x in sorted_dist][:4]
#Iterating over nodes to transfer edges to
for node_ij in nodes_ij:
candidate_graph2 = candidate_graph.copy()
#Edges to transfer
edges = list(candidate_graph2[cand[0]])
for to_reconnect in edges:
if to_reconnect != node_ij:
candidate_graph2.add_edge(node_ij, to_reconnect)
candidate_graph2.remove_edge(cand[0], to_reconnect)
#After edges removal, if node is not connected, reconnect to candidate
if len(list(candidate_graph2[cand[0]])) == 0:
candidate_graph2.add_edge(nodes_ij[0], cand[0])
#Break cycle (if found) and add solutions
try:
edges_cycle = nx.find_cycle(candidate_graph2)
for candidate_edge_remove in edges_cycle:
candidate_graph3 = candidate_graph2.copy()
candidate_graph3.remove_edge(*candidate_edge_remove)
candidate_graph3 = graph_with_calc_edge_capacity(candidate_graph3)
#Local Search is the lower-level heuristic
candidate_graph4, new_cost = local_search(candidate_graph3, cost_function)
results.append([new_cost, candidate_graph4])
except nx.exception.NetworkXNoCycle:
candidate_graph2 = graph_with_calc_edge_capacity(candidate_graph2)
candidate_graph3, new_cost = local_search(candidate_graph2, cost_function)
results.append([new_cost, candidate_graph3])
results.sort(key=lambda x: x[0])
if results[0][0] < orig_cost:
orig_cost = results[0][0]
candidate_graph = results[0][1].copy()
better_found = True
return candidate_graph, orig_cost
def high_valency_shuffle_edge_turn(input_graph, cost_function):
"""
Metaheuristic to provide minimum-cost tree from another tree,
by switching high valency nodes with neighbours.
After a local minimum is achieved with a lower-level heuristic,
high valency nodes are identified and their edes are transferered to
a nearby node. Cycles are broken in case any are created.
The lower-level heuristic used here is the edge-turn algorithm.
This metaheuristic algorithm is original work,
currently under review for publication.
Args:
input_graph: NetworkX Graph
cost_function: a cost function of the capacity
Returns:
optimized Networkx Graph
cost of optimized graph .
"""
#Initiate initial solution from edge_turn
candidate_graph, orig_cost = edge_turn(input_graph, cost_function)
#Complete graph is used to identify closest nodes for node shuffle
complete_graph = create_compl_graph_from_other(input_graph)
better_found = True
while better_found == True:
better_found = False
#Initiate results list
results = []
results.append([orig_cost, candidate_graph])
#Find high valency (here chosen as <2) nodes
candidates = [(x[0], x[1]) for x in list(candidate_graph.degree) if x[1] > 2]
#Iterating over initial high valency nodes
for cand in candidates:
sorted_dist = [
(x[0], x[1]["weight"]) for x in dict(complete_graph[cand[0]]).items()
]
#Find closest neighbours to transfer edges to (here closest 4)
sorted_dist.sort(key=itemgetter(1))
nodes_ij = [x[0] for x in sorted_dist][:4]
#Iterating over nodes to transfer edges to
for node_ij in nodes_ij:
candidate_graph2 = candidate_graph.copy()
#Edges to transfer
edges = list(candidate_graph2[cand[0]])
for to_reconnect in edges:
if to_reconnect != node_ij:
candidate_graph2.add_edge(node_ij, to_reconnect)
candidate_graph2.remove_edge(cand[0], to_reconnect)
#After edges removal, if node is not connected, reconnect to candidate
if len(list(candidate_graph2[cand[0]])) == 0:
candidate_graph2.add_edge(nodes_ij[0], cand[0])
#Break cycle (if found) and add solutions
try:
edges_cycle = nx.find_cycle(candidate_graph2)
for candidate_edge_remove in edges_cycle:
candidate_graph3 = candidate_graph2.copy()
candidate_graph3.remove_edge(*candidate_edge_remove)
candidate_graph3 = graph_with_calc_edge_capacity(candidate_graph3)
#The Edge turn algorithm is the lower-level heuristic
candidate_graph4, new_cost = edge_turn(candidate_graph3, cost_function)
results.append([new_cost, candidate_graph4])
except nx.exception.NetworkXNoCycle:
candidate_graph2 = graph_with_calc_edge_capacity(candidate_graph2)
candidate_graph3, new_cost = edge_turn(candidate_graph2, cost_function)
results.append([new_cost, candidate_graph3])
results.sort(key=lambda x: x[0])
if results[0][0] < orig_cost:
orig_cost = results[0][0]
candidate_graph = results[0][1].copy()
better_found = True
return candidate_graph, orig_cost
def high_valency_shuffle_delta_change(input_graph, cost_function):
"""
Metaheuristic to provide minimum-cost tree from another tree,
by switching high valency nodes with neighbours.
After a local minimum is achieved with a lower-level heuristic,
high valency nodes are identified and their edes are transferered to
a nearby node. Cycles are broken in case any are created.
The lower-level heuristic used here is the delta change algorithm.
This metaheuristic algorithm is original work,
currently under review for publication.
Args:
input_graph: NetworkX Graph
cost_function: a cost function of the capacity
Returns:
optimized Networkx Graph
cost of optimized graph .
"""
#Initiate initial solution from delta_change
candidate_graph, orig_cost = delta_change(input_graph, cost_function)
#Complete graph is used to identify closest nodes for node shuffle
complete_graph = create_compl_graph_from_other(input_graph)
better_found = True
while better_found == True:
better_found = False
#Initiate results list
results = []
results.append([orig_cost, candidate_graph])
#Find high valency (here chosen as >2) nodes
candidates = [(x[0], x[1]) for x in list(candidate_graph.degree) if x[1] > 2]
#Iterating over initial high valency nodes
for cand in candidates:
sorted_dist = [
(x[0], x[1]["weight"]) for x in dict(complete_graph[cand[0]]).items()
]
#Find closest neighbours to transfer edges to (here closest 4)
sorted_dist.sort(key=itemgetter(1))
nodes_ij = [x[0] for x in sorted_dist][:4]
#Iterating over nodes to transfer edges to
for node_ij in nodes_ij:
candidate_graph2 = candidate_graph.copy()
#Edges to transfer
edges = list(candidate_graph2[cand[0]])
for to_reconnect in edges:
if to_reconnect != node_ij:
candidate_graph2.add_edge(node_ij, to_reconnect)
candidate_graph2.remove_edge(cand[0], to_reconnect)
#After edges removal, if node is not connected, reconnect to candidate
if len(list(candidate_graph2[cand[0]])) == 0:
candidate_graph2.add_edge(nodes_ij[0], cand[0])
#Break cycle (if found) and add solutions
try:
edges_cycle = nx.find_cycle(candidate_graph2)
for candidate_edge_remove in edges_cycle:
candidate_graph3 = candidate_graph2.copy()
candidate_graph3.remove_edge(*candidate_edge_remove)
candidate_graph3 = graph_with_calc_edge_capacity(candidate_graph3)
#The delta change algorithm is the lower-level heuristic
candidate_graph4, new_cost = delta_change(candidate_graph3, cost_function)
results.append([new_cost, candidate_graph4])
except nx.exception.NetworkXNoCycle:
candidate_graph2 = graph_with_calc_edge_capacity(candidate_graph2)
candidate_graph3, new_cost = delta_change(candidate_graph2, cost_function)
results.append([new_cost, candidate_graph3])
results.sort(key=lambda x: x[0])
if results[0][0] < orig_cost:
orig_cost = results[0][0]
candidate_graph = results[0][1].copy()
better_found = True
return candidate_graph, orig_cost