September 2023 – Sagebrush Trails

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&lt;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.py

The 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.)