Trails and Graph Theory 9: Gradient Fuzz

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())
    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)
        fuzzed_Graph, matching = fuzz_min_weight_matching(max_fuzzed_Graph)
    T = K.copy()
    nodes = max(nx.connected_components(T), key=len)
    T2 = nx.subgraph(T, nodes).copy()
    if nx.is_eulerian(T2):
        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)
        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
finished finding some possible matchings
max length =  270.4589642970273  miles
finished script

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

We have improved the maximum known circuit length from 228 to 270 miles, with modest effort.

Download source code here.

Related Posts:

Landavaso Trail 2023

About 28 volunteers celebrated National Public Lands Day by building 1.0 miles of the 3.5 mile Landavaso Trail just west of Magdalena. Socorro Trails partnered with BLM Socorro and several Magdalena volunteers, with donations from Socorro Walmart and Tumbleweeds Cafe/SCOPE.

Mike and Marty from BLM had already roughed out the trail with a custom-built drag-plow, so volunteers used McLeods and pick-mattocks to remove grass and rock and smooth out trail, in rolling grassland among scattered juniper and piƱon.

Rocky Mountain Youth Corps is expected to finish the trail next month. We look forward to hiking this trail… often!

Related Post:

Jemez Mountains Cleanup 2 2023

Six NMVFO volunteers returned to the Jemez, picking up litter along dispersed campsites along Forest Road 144, in a joint project with NMWild and the Jemez Ranger District.

I do not know of a way to make gripping photos of people using litter pickup tools. But we did find that a litter picker makes a good improvised selfie-stick…

photo credit Catlin