I want to connect eulerian cycles into longer ones without exceed a value.
So, I have this eulerian cycles and their length in a list. The maximal length of a cycle can be for example 500. The length of all cycles added up is 6176.778566350282. By connecting them cleverly together there could be probably only 13 or 14 cycles. But I don't really know how I could do that. I tried to just add one cycle to another but there I got 21 cycles out. The problem is that if you have a cycle of these numbers for example: [8, 21, 9, 22, 8, 23, 9, 24, 8] and you want to integrate this cycle [10, 11, 12, 10] it will not work because in the first cycle there is no edge of the number 10. I just started then a new cycle with this numbers [10, 11, 12, 10] and saved [8, 21, 9, 22, 8, 23, 9, 24, 8] as one of the 21 result cycles. But with this method I don't really get a good result. What would be a cleverer way to solve this problem?
This is an example how the list of the short eulerian cycles looks like:
[([0, 1, 2, 0], 36.36630772776802), ([0, 3, 1, 4, 0], 93.83277865587606), ([0, 5, 1, 6, 0], 45.79353710664728), ([0, 7, 1, 8, 0], 49.60782827778143), ([0, 9, 1, 10, 0], 73.2674533926481), ([0, 11, 1, 12, 0], 75.52124688926921), ([0, 13, 1, 14, 0], 57.88021234723078), ([0, 15, 1, 16, 0], 62.21469065955568), ([0, 17, 1, 18, 0], 81.43809748917617), ([0, 19, 1, 20, 0], 98.88867905572438), ([0, 21, 1, 22, 0], 95.3596513800762), ([0, 23, 1, 24, 0], 116.15359042770964), ([2, 3, 4, 2], 49.106297391220245), ([2, 5, 3, 6, 2], 71.5422470782724), ([2, 7, 3, 8, 2], 50.237654764168), ([2, 9, 3, 10, 2], 71.36355688043689), ([2, 11, 3, 12, 2], 44.474596239420634), ([2, 13, 3, 14, 2], 103.42527218232905), ([2, 15, 3, 16, 2], 65.92444557445982), ([2, 17, 3, 18, 2], 83.30561323888043), ([2, 19, 3, 20, 2], 144.20150278029047), ([2, 21, 3, 22, 2], 131.70030082856), ([2, 23, 3, 24, 2], 141.63032737825358), ([4, 5, 6, 4], 42.10300780814433), ([4, 7, 5, 8, 4], 88.13162862262575), ([4, 9, 5, 10, 4], 29.40312423743285), ([4,
11, 5, 12, 4], 35.06685249446684), ([4, 13, 5, 14, 4], 83.54113932583394), ([4, 15, 5, 16, 4], 57.669814210895076), ([4, 17, 5, 18, 4], 85.16088821443248), ([4, 19, 5, 20, 4], 115.83839679838714), ([4, 21, 5, 22, 4], 96.32509817470469), ([4, 23, 5, 24, 4], 95.72504474795447), ([6, 7, 8, 6], 39.680511478789455), ([6, 9, 7, 10, 6], 78.55998969220359), ([6, 11, 7, 12, 6], 75.38181527864062), ([6, 13, 7, 14, 6], 65.59514045044449), ([6, 15, 7, 16, 6], 64.00893982862813), ([6, 17, 7, 18, 6], 82.99423226082924), ([6, 19, 7, 20, 6], 107.80803412093549), ([6, 21, 7, 22, 6], 104.34384551877056), ([6, 23, 7, 24, 6], 125.5684717784), ([8, 9, 10, 8], 52.130784276071026), ([8, 11, 9, 12, 8], 60.084249983353345), ([8, 13, 9, 14,
8], 80.8264707041123), ([8, 15, 9, 16, 8], 56.067658306081576), ([8, 17, 9, 18, 8], 87.79739969269264), ([8, 19, 9, 20, 8], 115.04095207094785),
([8, 21, 9, 22, 8], 100.28892183336735), ([8, 23, 9, 24, 8], 107.98171312085222), ([10, 11, 12, 10], 18.073592581964586), ([10, 13, 11, 14, 10],
86.59048377734861), ([10, 15, 11, 16, 10], 53.62896051047471), ([10, 17, 11, 18, 10], 79.42707393175432), ([10, 19, 11, 20, 10], 121.75438335508098), ([10, 21, 11, 22, 10], 103.13320830479722), ([10, 23, 11, 24, 10], 104.67092453129686), ([12, 13, 14, 12], 65.01056040398879), ([12, 15, 13, 16, 12], 73.92038351218434), ([12, 17, 13, 18, 12], 75.85986620162797), ([12, 19, 13, 20, 12], 99.9668143111241), ([12, 21, 13, 22, 12], 97.01425784207544), ([12, 23, 13, 24, 12], 113.28618776429398), ([14, 15, 16, 14], 53.12806382231952), ([14, 17, 15, 18, 14], 83.32318283097464), ([14,
19, 15, 20, 14], 59.489711796339975), ([14, 21, 15, 22, 14], 49.93204117686305), ([14, 23, 15, 24, 14], 59.39628730132421), ([16, 17, 18, 16], 76.30230372794964), ([16, 19, 17, 20, 16], 151.38369644764225), ([16, 21, 17, 22, 16], 137.27131752575687), ([16, 23, 17, 24, 16], 146.11467181532439), ([18, 19, 20, 18], 28.731124011957917), ([18, 21, 19, 22, 18], 51.78367537918862), ([18, 23, 19, 24, 18], 86.45013419422762), ([20, 21, 22,
20], 39.010097887844154), ([20, 23, 21, 24, 20], 63.48159687540681), ([22, 23, 24, 22], 22.283951753399037)]
CodePudding user response：
I designed an elaborate branch-and-price scheme and then realized that it probably wouldn’t work well. Here’s a much simpler local search that achieves 14 cycles on your sample input.
from collections import defaultdict
from itertools import combinations
import random
# pip3 install networkx if necessary.
import networkx as nx
# The input consists of the variables maximum_length and cycles.
maximum_length = 500
cycles = [
([0, 1, 2, 0], 36.36630772776802),
([0, 3, 1, 4, 0], 93.83277865587606),
([0, 5, 1, 6, 0], 45.79353710664728),
([0, 7, 1, 8, 0], 49.60782827778143),
([0, 9, 1, 10, 0], 73.2674533926481),
([0, 11, 1, 12, 0], 75.52124688926921),
([0, 13, 1, 14, 0], 57.88021234723078),
([0, 15, 1, 16, 0], 62.21469065955568),
([0, 17, 1, 18, 0], 81.43809748917617),
([0, 19, 1, 20, 0], 98.88867905572438),
([0, 21, 1, 22, 0], 95.3596513800762),
([0, 23, 1, 24, 0], 116.15359042770964),
([2, 3, 4, 2], 49.106297391220245),
([2, 5, 3, 6, 2], 71.5422470782724),
([2, 7, 3, 8, 2], 50.237654764168),
([2, 9, 3, 10, 2], 71.36355688043689),
([2, 11, 3, 12, 2], 44.474596239420634),
([2, 13, 3, 14, 2], 103.42527218232905),
([2, 15, 3, 16, 2], 65.92444557445982),
([2, 17, 3, 18, 2], 83.30561323888043),
([2, 19, 3, 20, 2], 144.20150278029047),
([2, 21, 3, 22, 2], 131.70030082856),
([2, 23, 3, 24, 2], 141.63032737825358),
([4, 5, 6, 4], 42.10300780814433),
([4, 7, 5, 8, 4], 88.13162862262575),
([4, 9, 5, 10, 4], 29.40312423743285),
([4, 11, 5, 12, 4], 35.06685249446684),
([4, 13, 5, 14, 4], 83.54113932583394),
([4, 15, 5, 16, 4], 57.669814210895076),
([4, 17, 5, 18, 4], 85.16088821443248),
([4, 19, 5, 20, 4], 115.83839679838714),
([4, 21, 5, 22, 4], 96.32509817470469),
([4, 23, 5, 24, 4], 95.72504474795447),
([6, 7, 8, 6], 39.680511478789455),
([6, 9, 7, 10, 6], 78.55998969220359),
([6, 11, 7, 12, 6], 75.38181527864062),
([6, 13, 7, 14, 6], 65.59514045044449),
([6, 15, 7, 16, 6], 64.00893982862813),
([6, 17, 7, 18, 6], 82.99423226082924),
([6, 19, 7, 20, 6], 107.80803412093549),
([6, 21, 7, 22, 6], 104.34384551877056),
([6, 23, 7, 24, 6], 125.5684717784),
([8, 9, 10, 8], 52.130784276071026),
([8, 11, 9, 12, 8], 60.084249983353345),
([8, 13, 9, 14, 8], 80.8264707041123),
([8, 15, 9, 16, 8], 56.067658306081576),
([8, 17, 9, 18, 8], 87.79739969269264),
([8, 19, 9, 20, 8], 115.04095207094785),
([8, 21, 9, 22, 8], 100.28892183336735),
([8, 23, 9, 24, 8], 107.98171312085222),
([10, 11, 12, 10], 18.073592581964586),
([10, 13, 11, 14, 10], 86.59048377734861),
([10, 15, 11, 16, 10], 53.62896051047471),
([10, 17, 11, 18, 10], 79.42707393175432),
([10, 19, 11, 20, 10], 121.75438335508098),
([10, 21, 11, 22, 10], 103.13320830479722),
([10, 23, 11, 24, 10], 104.67092453129686),
([12, 13, 14, 12], 65.01056040398879),
([12, 15, 13, 16, 12], 73.92038351218434),
([12, 17, 13, 18, 12], 75.85986620162797),
([12, 19, 13, 20, 12], 99.9668143111241),
([12, 21, 13, 22, 12], 97.01425784207544),
([12, 23, 13, 24, 12], 113.28618776429398),
([14, 15, 16, 14], 53.12806382231952),
([14, 17, 15, 18, 14], 83.32318283097464),
([14, 19, 15, 20, 14], 59.489711796339975),
([14, 21, 15, 22, 14], 49.93204117686305),
([14, 23, 15, 24, 14], 59.39628730132421),
([16, 17, 18, 16], 76.30230372794964),
([16, 19, 17, 20, 16], 151.38369644764225),
([16, 21, 17, 22, 16], 137.27131752575687),
([16, 23, 17, 24, 16], 146.11467181532439),
([18, 19, 20, 18], 28.731124011957917),
([18, 21, 19, 22, 18], 51.78367537918862),
([18, 23, 19, 24, 18], 86.45013419422762),
([20, 21, 22, 20], 39.010097887844154),
([20, 23, 21, 24, 20], 63.48159687540681),
([22, 23, 24, 22], 22.283951753399037),
]
for cycle, length in cycles:
assert cycle[0] == cycle[-1]
assert 0 <= length <= maximum_length
# Two cycles can be merged if and only if there exists a vertex that they have
# in common. Compute the graph where each cycle is a node and each pair of
# cycles that can be merged is an edge. A set of cycles can be merged if and
# only if the total length does not exceed the maximum and the corresponding set
# of nodes induces a connected subgraph.
inverted_index = defaultdict(list)
for i, (cycle, length) in enumerate(cycles):
for v in set(cycle):
inverted_index[v].append(i)
cycle_graph = nx.Graph()
for i, (cycle, length) in enumerate(cycles):
cycle_graph.add_node(i, length=length)
for posting_list in inverted_index.values():
for e in combinations(posting_list, 2):
cycle_graph.add_edge(*e)
lengths = [round(length * 2**40) / 2**40 for (cycle, length) in cycles]
# We want to find the smallest partition of cycles into mergeable parts. This
# code implements a greedy local search. Initialize the partition where every
# cycle is in its own part. For some number of steps, move one cycle to another
# part, respecting the connectivity constraint.
def make_part_graph(part):
part_graph = cycle_graph.subgraph(part)
return nx.Graph(
part_graph,
can_move=set(part_graph.nodes()) - set(nx.articulation_points(part_graph)),
length=sum(lengths[i] for i in part_graph.nodes()),
)
def merge_cycles(indexes):
g = nx.DiGraph()
for i in indexes:
cycle, length = cycles[i]
for j in range(1, len(cycle)):
g.add_edge(cycle[j - 1], cycle[j])
cycle = []
for u, v in nx.eulerian_circuit(g):
if not cycle:
cycle.append(u)
cycle.append(v)
return cycle, sum(lengths[i] for i in indexes)
labels = list(range(len(cycles)))
cycle_subgraphs = {i: make_part_graph({i}) for i in range(len(cycles))}
for step in range(10000):
moves = []
for tail, cycle_subgraph in cycle_subgraphs.items():
for i in cycle_subgraph.graph["can_move"]:
for j in cycle_graph.neighbors(i):
head = labels[j]
if (
head != tail
and cycle_subgraphs[head].graph["length"] lengths[i]
<= maximum_length
):
moves.append((i, tail, head))
i, tail, head = random.choice(moves)
labels[i] = head
cycle_subgraphs[tail] = make_part_graph(set(cycle_subgraphs[tail].nodes()) - {i})
cycle_subgraphs[head] = make_part_graph(set(cycle_subgraphs[head].nodes()) | {i})
for cycle_subgraph in cycle_subgraphs.values():
part = sorted(cycle_subgraph.nodes())
if not part:
continue
print(*merge_cycles(part))
Output:
[0, 23, 11, 24, 8, 23, 9, 3, 10, 2, 9, 24, 10, 23, 1, 24, 0, 21, 1, 22, 0] 495.5294363403709
[0, 19, 17, 20, 16, 19, 22, 18, 21, 3, 22, 2, 21, 19, 1, 20, 0, 5, 1, 6, 0] 479.5498888177626
[6, 23, 17, 24, 16, 10, 15, 11, 14, 10, 13, 11, 16, 23, 7, 24, 6] 411.90258788154733
[0, 9, 22, 8, 21, 9, 18, 16, 17, 18, 8, 17, 9, 16, 8, 15, 9, 12, 8, 6, 7, 8, 11, 9, 1, 10, 0] 493.488498414883
[2, 5, 3, 6, 19, 9, 10, 8, 9, 20, 23, 21, 24, 20, 8, 19, 7, 20, 6, 2] 410.00361442163285
[0, 7, 22, 6, 21, 7, 16, 12, 15, 20, 14, 19, 11, 20, 10, 19, 15, 13, 16, 6, 15, 7, 1, 8, 0] 473.1250922887857
[0, 13, 1, 14, 0, 11, 22, 10, 21, 11, 5, 12, 4, 11, 3, 12, 2, 11, 1, 12, 0, 1, 2, 0] 352.442424002953
[0, 3, 1, 4, 23, 15, 24, 14, 23, 5, 24, 4, 7, 5, 8, 4, 0] 337.0857393277802
[4, 21, 13, 7, 14, 8, 13, 9, 14, 6, 13, 22, 23, 24, 22, 20, 21, 22, 12, 21, 5, 22, 4, 9, 5, 10, 4] 430.458141050015
[2, 23, 3, 24, 2, 13, 3, 14, 2, 7, 12, 6, 11, 7, 10, 6, 4, 5, 6, 9, 7, 3, 8, 2] 491.33806710373847
[0, 15, 22, 14, 21, 15, 5, 20, 12, 10, 11, 12, 19, 13, 20, 4, 19, 5, 16, 4, 15, 1, 16, 0] 403.69534973878945
[0, 17, 22, 16, 21, 17, 11, 18, 19, 3, 20, 2, 19, 20, 18, 10, 17, 1, 18, 0] 471.0691157389365
[2, 15, 16, 14, 4, 13, 24, 18, 23, 19, 24, 12, 23, 13, 5, 14, 15, 3, 16, 2, 3, 4, 2] 451.43626807235523
[2, 17, 15, 18, 14, 12, 13, 14, 17, 13, 18, 12, 17, 7, 18, 6, 17, 5, 18, 4, 17, 3, 18, 2] 475.65434315073435