This is my first question here as I've usually found helpful answers by searching previous posts. I cannot find any that relate to my particular problem this time. I need to complete a branch and bound function in Python (it's for a Coursera course), and I cannot figure out how to keep the algorithm going after it finds the first cycle. I would appreciate any hints or guidance you can give. This is the most frustrated I've been with a programing assignment - and I've been taking Coursera courses for 2 years.
Most of the code has been given to us, and my portion is near the end. The graph is undirected and complete.
`# This function computes a lower bound on the length of Hamiltonian cycles starting with vertices in the list sub_cycle.
def lower_bound(g, sub_cycle):
# The weight of the current path.
current_weight = sum([g[sub_cycle[i]][sub_cycle[i + 1]]['weight'] for i in range(len(sub_cycle) - 1)])
# For convenience we create a new graph which only contains vertices not used by g.
unused = [v for v in g.nodes() if v not in sub_cycle]
h = g.subgraph(unused)
# Compute the weight of a minimum spanning tree.
t = list(nx.minimum_spanning_edges(h))
mst_weight = sum([h.get_edge_data(e[0], e[1])['weight'] for e in t])
# If the current sub_cycle is "trivial" (i.e., it contains no vertices or all vertices), then our lower bound is
# just the sum of the weight of a minimum spanning tree and the current weight.
if len(sub_cycle) == 0 or len(sub_cycle) == g.number_of_nodes():
return mst_weight + current_weight
# If the current sub_cycle is not trivial, then we can also add the weight of two edges connecting the vertices
# from sub_cycle and the remaining part of the graph.
# s is the first vertex of the sub_cycle
s = sub_cycle[0]
# t is the last vertex of the sub_cycle
t = sub_cycle[-1]
# The minimum weight of an edge connecting a vertex from outside of sub_sycle to s.
min_to_s_weight = min([g[v][s]['weight'] for v in g.nodes() if v not in sub_cycle])
# The minimum weight of an edge connecting the vertex t to a vertex from outside of sub_cycle.
min_from_t_weight = min([g[t][v]['weight'] for v in g.nodes() if v not in sub_cycle])
# Any cycle which starts with sub_cycle must be of length:
# the weight of the edges from sub_cycle +
# the minimum weight of an edge connecting sub_cycle and the remaining vertices +
# the minimum weight of a spanning tree on the remaining vertices +
# the minimum weight of an edge connecting the remaining vertices to sub_cycle.
return current_weight + min_from_t_weight + mst_weight + min_to_s_weight
# The branch and bound procedure takes
# 1. a graph g;
# 2. the current sub_cycle, i.e. several first vertices of cycle under consideration.
# Initially sub_cycle is empty;
# 3. currently best solution current_min, so that we don't even consider paths of greater weight.
# Initially the min weight is infinite
def branch_and_bound(g, sub_cycle=None, current_min=float("inf")):
used_nodes = list()
# If the current path is empty, then we can safely assume that it starts with the vertex 0.
if sub_cycle is None:
sub_cycle = [0]
# If we already have all vertices in the cycle, then we just compute the weight of this cycle and return it.
if len(sub_cycle) == g.number_of_nodes():
weight = sum([g[sub_cycle[i]][sub_cycle[i + 1]]['weight'] for i in range(len(sub_cycle) - 1)])
weight = weight + g[sub_cycle[-1]][sub_cycle[0]]['weight']
return weight
# Now we look at all nodes which aren't yet used in sub_cycle.
unused_nodes = list()
for v in g.nodes():
if v not in sub_cycle:
unused_nodes.append((g[sub_cycle[-1]][v]['weight'], v))
# We sort them by the distance from the "current node" -- the last node in sub_cycle.
unused_nodes = sorted(unused_nodes)
for (d, v) in unused_nodes:
assert v not in sub_cycle
extended_subcycle = list(sub_cycle)
extended_subcycle.append(v)
# For each unused vertex, we check if there is any chance to find a shorter cycle if we add it now.
if lower_bound(g, extended_subcycle) < current_min:
**# THIS IS WHERE WE ARE TO ADD OUR PORTION OF THE CODE.
# If there is such a chance, we add the vertex to the current cycle, and proceed recursively.
# If we found a short cycle, then we update the current_min value**.
if len(extended_subcycle) == g.number_of_nodes():
current_min = sum([g[extended_subcycle[i]][extended_subcycle[i + 1]]['weight'] for i in range(len(extended_subcycle) - 1)])
current_min = current_min + g[extended_subcycle[-1]][extended_subcycle[0]]['weight']
sub_cycle.append(v)
return branch_and_bound(g, sub_cycle, current_min)
# The procedure returns the shortest cycle length.
return current_min`
The optimal cycle should be [0,4,2,1,5,3] with a weight of 695.8588106976. No matter what I try, I keep getting [0,1,2,4,3,5] with a weight of 769.1010673076235.
I believe I'm missing an ELSE: statement; and I've tried a few; but the code was never evaluated. I confirmed this by adding print('else'); but it never printed so I removed the code.
I wish I could enumerate all of the other things I've tried; but I've been revising and re-running this code for two-three days now - so I can't recall specific details.
Here is the input I'm using. They are coordinates that are passed to a function that creates a graph. I've included it below.
coordinates3 = [(199, 59), (152, 117), (68, 87), (281, 161), (11, 53), (254, 227)]
def get_graph(coordinates):
g = nx.Graph()
n = len(coordinates)
for i in range(n):
for j in range(i + 1):
g.add_edge(i, j, weight=dist(coordinates[i][0], coordinates[i][1], coordinates[j][0], coordinates[j][1]))
return g
Edited to add: I'm leaving this question here in case it gets answered and someone else has this same issue. I have unenrolled from the class...my first one due to frustration at an assignment. It's been 5 days, and I've worked on it more than 3 hours each day with no improvement.
