Geek Hiking – Page 7 – Sagebrush Trails

Trails and Graph Theory 7: Apply Tools

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

Trails and Graph Theory 6: Utilities

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

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.