Category: Geek Hiking

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

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

Download source code here.

Related Posts:

• Trails and Graph Theory: The Series

Let us take the tools we developed in the last post and apply to the much larger graph of the Gila National Forest, and see what needs debugging. We follow nearly the same steps as the previous post, so refer to that article for an explanation of why we are taking particular steps in a certain order.

One thing discovered after experimentation is that OSMnx embeds a good deal of geometry information on the attributes of graph edges and graph nodes, so my contract_twos function would need a good deal of modification to correctly join the geometries of two edges to a single edge. Instead, we will use a shortcut. OSMnx has a simplify_graph function, which eliminates all nodes of degree 2, but it can only be used once. (I pray that the maintainers of the OSMnx library might remove that restriction in later releases. ) Before, I used that function just after reading in the OpenStreetMap data, but now we will wait. The trade-off is that we start out with a graph with a huge number of nodes for our initial graphs. Our draw function that can handle OSMnx graphs has an option to show the nodes.

OSMnx version:  1.4.0
NetworkX version:  3.1

report(G)

79985  nodes  
79983  edges  
total length 1546.96 miles  
number of zero-degree nodes  : 11
number of odd intersections  : 900
number of even intersections  : 79085
number of 2-way intersections  : 79027
number of trailhead/terminus  : 489

draw(G)

If we turn on display_nodes, we see a jungle of them. The extra nodes slow down calculations, but not too much to bear. (Perhaps I need to display nodes in a higher contrast color than ‘pink’.