In our last episode we added random “noise” to the length values of each segment of our trail graph, and for each iteration of random values we did our normal routine to make an Euler graph, and therefore find a long hiking loop without repeating any trail sections:
- networkx.algorithms.min_weight_matching() on the fuzzed length odd-nodes graph
- Delete trail segments between matched nodes to make an all-even node graph
- Restore 4-nodes that we saved previously
- Take the largest subgraph, since deleting bits of trails may create disconnected islands
- If the graph is Eulerian, see if the total length is larger than anything we have tried before (using the actual length values, not the fuzzed lengths).
With our fuzzing routine, we increased our best try at an Euler graph from an initial solution of 154 miles to a respectable 228 miles after 200 or so iterations.
Now, let us alter our approach, doing a technique I am calling “gradient fuzz”. We fuzz our original graph like before, but if the resulting solution is the longest, we save the fuzzed graph as our next input, and fuzz the fuzzed graph instead of fuzzing our original graph.
In other words, if we find a better solution, try to improve that solution instead of continuing to try to improve the original input.
The code needs only minor changes.
def fuzz_min_weight_matching(Q):
T = nx.Graph()
for u, v, d in Q.edges(data=True):
len = d['length']
len = len * (1 + random.random())
T.add_edge(u,v,length=len)
return T, nx.min_weight_matching(T,weight='length')
max_fuzzed_Graph = None
while j<1000:
if max_fuzzed_Graph == None:
fuzzed_Graph, matching =
fuzz_min_weight_matching(K)
else:
fuzzed_Graph, matching =
fuzz_min_weight_matching(max_fuzzed_Graph)
j+=1
T = K.copy()
T.remove_edges_from(matching)
restore_4node_graph(T,fix_4_list)
nodes = max(nx.connected_components(T), key=len)
T2 = nx.subgraph(T, nodes).copy()
if nx.is_eulerian(T2):
all_matchings.append(matching)
print('found eulerian on fuzz attempt ', j)
index = len(all_matchings)-1
print('length of successful matching: ', len(matching))
print('matching ', index, ' is eulerian')
report(T2,'matching ' + str(index))
length = graph_length(T2)
save_png(T2,max_T2,bounds,index)
if length > max_length:
max_length = length
max_T2 = T2.copy()
max_fuzzed_Graph = fuzzed_Graph.copy()
Results after 1000 iterations:
...
current max length: 270
found eulerian on fuzz attempt 9999
length of successful matching: 68
matching 834 is eulerian
65 nodes matching 834
66 edges matching 834
total length 189.19 miles matching 834
number of odd intersections matching 834 : 0
number of even intersections matching 834 : 65
number of 2-way intersections matching 834 : 64
number of trailhead/terminus matching 834 : 0
current max length: 270
found eulerian on fuzz attempt 1000
length of successful matching: 68
matching 835 is eulerian
65 nodes matching 835
66 edges matching 835
total length 161.67 miles matching 835
number of odd intersections matching 835 : 0
number of even intersections matching 835 : 65
number of 2-way intersections matching 835 : 64
number of trailhead/terminus matching 835 : 0
current max length: 270
1:33:15
finished finding some possible matchings
max length = 270.4589642970273 miles
1:33:16
finished script max_trail3e.pyThe color schemes chosen for the output graphs have been tweaked from the last article to be a bit easier to follow. (I am still having trouble finding a good combinations of colors and styles, as the current graph and maximum graph often overlap for much of their length.)
We have improved the maximum known circuit length from 228 to 270 miles, with modest effort.
Download source code here.