Category: Geek Hiking

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

Continue reading “Trails and Graph Theory 4 : Import Maps”

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.

Continue reading “Trails and Graph Theory 3: NetworkX”

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”