Category: Geek Hiking

My first choice for a programming language for solving our graph problem is Python, with its “batteries included” philosophy, and diversity of native data structures. Data structures such as lists, dequeues, and dictionaries seem more of an afterthought for C++ and Java. My past experience with Python is extremely limited, but I am not on deadline, and can use the brain exercise.

A quick search of graph theory libraries for Python or R turns up NetworkX. The library has built-in solvers for shortest paths, but not necessarily for the longest path we are looking for. But at least I could use their built-in data structures to create my own solver, if necessary.

(In a previous career as a chip designer decades ago, I used awk to solve graph theory problems on huge CMOS netlists because of its built-in associative memory, but let’s stick with a language known to be much more modern and readable, Python.)

An insight about bridges might make our problem easier to solve.

Seven Bridges of Königsberg

Consider these 7 bridges in the ancient city of Königsberg in Prussia. Find a walk through the city that crosses each bridge once and only once.

We transform this problem into a graph, where each of 4 land masses is a node, and each bridge is an edge.

Euler explained that, except for the beginning and end of the walk, whenever you enter a node you must leave the node. So except for the beginning and end, all nodes must have an even number of edges. In this problem, all nodes have an odd number of edges, so a solution is impossible.

Continue reading “Trails and Graph Theory 2: Bridges”

It all started with a question:

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?

Can the result be mapped and documented as a Long Trail to share with hikers?

Sagebrush

The Gila has a few trails that dead-end, so those can be eliminated, and several trails are currently in poor condition due to fire or lack of maintenance, and not reasonable to hike. Furthermore, some trails are not where they are shown on published maps. Fortunately, I know an expert on the Gila, an individual with boundless energy who is dedicated to reopening and maintaining routes. And perhaps another published long trail could be used as a motivation to go out and work on particular segments.

Finding a longest route is an optimization problem, so mathematics might be able to help. A famous problem in math is the Traveling Salesman. One version:

A salesman needs to visit all lower-48 state capitals and return to the beginning. What is the route with minimum distance?

An obverse is the Longest Path Problem

What is the longest path in a given network?

Nano Intro to Graph Theory

Continue reading “Trails and Graph Theory: Graphs”

Hiking long trails is a fine time to listen to audiobooks and podcasts. My method is to use a tiny Bluetooth earbud in one ear, a model that does not block outside noise, so I can still be aware of any sounds that indicate danger or people or nature.

My long-time favorite source for audiobooks is the public-domain recordings of LibriVox. Early in my planning stage for a long hike, I am selecting out-of-copyright literature that I should have already read if I were a more well-rounded individual who was not busy consuming the latest science fiction. In January when it is too early to do much else, I can search for and download books and experience that excitement that comes from taking those many small preparations necessary for a long trip.

If you ever read my hiking blog (or ebooks) on long trails, you will notice that I list each audiobook the day I finish it in my journal, along with a link for you to download if you might also like to experience that book.

I prefer not to purchase audiobooks from Audible.com, following my policy of not engaging with monopolies or DRM whenever practical. One recent series of speculative fiction that I do enjoy purchasing is the Martin Hench books from Cory Doctorow. First-up in my list of books to read this July on the Colorado Trail is Red Team Blues. The author has gone to great lengths to provide a way to purchase the audiobook without DRM. And the reality that the audiobook is read by Wil Wheaton– I can barely wait to start listening until I reach the trail!