A few utility functions were created to help solve our maximum-length trail problem. Since most of you may not be interested in the code, I will first describe what each function does, and then append the source at the end for you to skip over.
First is report(graph, description=”), which reports of the number of edges and nodes of a graph, and some basic statistics. We will use our first example graph as an example. We make a small change to start with a Multigraph instead of a Graph, and to use ‘length’ instead of ‘weight’, to be more compatible with OSMnx later.
report(G)
16 nodes
21 edges
total length 0.02 miles
number of odd intersections : 10
number of even intersections : 6
number of 2-way intersections : 5
number of trailhead/terminus : 1
The function draw(graph, title=”) displays our simple graphs, and can handle Multigraphs.
draw(G)
Trailhead/terminus points are dead-ends that cannot be included in a grand circuit, so it is computationally easier to eliminate them early, with delete_ends(graph).
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.
One possible pairing, not the optimum
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.
We will use the OSMnxlibrary 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 foliumlibrary 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.)
