Geek Hiking – Page 7 – Sagebrush Trails

Trails and Graph Theory 5: Algorithms

First off, I am no expert in Graph Theory, or of mathematics, or even computer science, so what follows may be completely and totally wrong, the Dunning-Kruger effect writ large. This is just me trying to get a reasonable approximation to the question posed in the first post in this series:

What is the longest continuous route on existing trails in the Gila National Forest, that does not repeat any segment (but intersections are OK)?

And what is the longest continuous loop?

The longest path problem is known to be computationally hard, and even getting a reasonable upper bound of compute time for unweighted cyclic undirected graphs is difficult. The computation time is likely to be excessive for an exact solution for our size graph, so let us settle for approximations. After all, as long as a long distance hiker has at least a 600 mile trip, that is long enough for a reasonable adventure, and if the journey could have been 20% longer with a faster computer, we beg the hiker to forgive us.

Start by considering the Chinese Postman Problem: A postman needs to visit every street (edge) in a town (graph) at least once to deliver mail. What is the minimum distance to be traveled in a circuit, allowing some streets to be walked more than once?

Find the shorted closed loop on an undirected weighted graph that visits every edge at least once.

Let us call a node with an odd number of edges an odd node. If we pair up each odd node with another odd node, and then duplicate the edges between those pairs of nodes, then all nodes have an even number of edges, and we get a Euler graph, and an Euler circuit. Iterate over all those possible pairings to find the pairing (matching) with minimum total distance.

Now let us modify the Chinese Postman Problem to iterate over all pairings as before, but to look for a matching that results in a maximum distance. And because we do not want to repeat any trail segment, instead of duplicating edges between pairs of odd nodes, let us delete edges between odd nodes. (We may have more than one path between a pair of odd nodes, but perhaps we can choose the shortest path as a first-approximation). And another wrinkle, since we are deleting edges, we should be looking at edge connectivity as well as distance when deciding what edges to delete. Removing an edge might delete a large chunk of the graph.

Trails and Graph Theory 4 : Import Maps

We will use the OSMnx library to import trails from OpenStreetMap to our graph. Installing the library typically requires more than the Python pip utility– use conda, and follow on-line guides– pretty much black magic to me. The folium library is used to display our maps with graphs.

import osmnx as ox
import networkx as nx
import folium

ox.settings.log_console=True
ox.settings.use_cache=True

Let us import a trail network.

# location where you want to find your route
place = 'Gila National Forest, New Mexico, United States'

We will create a custom filter to only import trails. If we use the default network_type=’walk’ we also get dirt forest roads. Also, make retain_all=True instead of the default, or we will discard disconnected subgraphs, such as the entire Aldo Leopold Wilderness!

cf = '["highway"~"path|footway"]'

graph = ox.graph_from_place(place,
   simplify=True,retain_all=True,custom_filter=cf)

len = ox.stats.edge_length_total(graph) #in meters
len = len * 0.0006213712
print(f'total length {len:.2f} miles') 

     total length 2839.50 miles

(The total length of trails might be inflated by a factor of 2, because graph is a multidigraph, so edges are doubled.)

Trails and Graph Theory 3: NetworkX

Let us create a small imaginary trail graph in Python with NetworkX, and play around with plotting and paths. Suppose we have a graph with nodes from 0 to 15:

import networkx as nx
import matplotlib.pyplot as plt

G=nx.Graph()

edges=[(0,1,1),(1,2,1),(2,3,1),(3,4,1),(4,5,1),(5,6,1),(6,7,1),
       (8,3,2),(9,4,1),(9,5,1),(10,7,2),
       (8,9,2),(9,10,2),
       (8,11,2),(12,10,2),
       (11,12,2),(12,13,2),(13,7,2),
       (11,14,2),(14,15,4),(15,13,1)]
G.add_weighted_edges_from(edges)

The tuple (8,11,2) means an edge goes from node 8 to node 11, with weight 2.

Now we specify where the nodes are located.

#pos=nx.spring_layout(G) does not give satisfactory results.
# Draw node positions the hard way.

pos=[(0,4),(1,4),(2,4),(3,4),(4,4),(5,4),(6,4),(7,4),
     (1,3),(3,3),(5,3),
     (3,2),(6,2),(8,2),
     (4,1),(7,1)]

We are almost ready to draw the network. Since we want to draw weights for the edges, we have an extra step.

options = {
    "font_size": 16,
    "node_size": 1000,
    "node_color": "white",
    "edgecolors": "black",
    "linewidths": 5,
    "width": 5,
}
nx.draw_networkx(G, pos,**options)

labels = {e: G.edges[e]['weight'] for e in G.edges}
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_color="red")
plt.show()

And here is our result.

Think how we can convert this into a Euler graph, so all nodes have an even number of edges. We can try a Networkx library function, but should not expect it will do what we want, because it will create a multigraph, with more than one edge between nodes.