[Python] How to drive every street in a given area?

I'm looking to collect 360 imagery in a given area by driving all the streets in it, trying to optimize the route (a variant of the Chinese Postman Problem - CPP).

I am trying to use this nice code, Every Street, which solves the original CPP, so I don't need to fully develop a solution. In summary, this is what the original code does:

1. 
   get all pedestrian-allowed roads in a given area out of OpenStreetMap
   
   
2. 
   apply an algorithm proposed by Edmonds, J. and Johnson, which gives the optimal solution. This algorithm is applied inside the network package, developed by same author.
   

The code works pretty fine for the original problem, but I can't adapt to my problem. There are 2 adjustments I think I need to apply in the original code:

• adjust the ways to only obtain the drivable roads (exclude pedestrian paths etc)
• make the graph directed

The code uses OSMnx package, so the first part I believe is easily solved, using the parameter network_type='drive':

org_graph = ox.graph.graph_from_place("My Area", network_type='drive', simplify=True, retain_all=True, truncate_by_edge=False, which_result=None, buffer_dist=0, clean_periphery=None, custom_filter=None)


The original code also have this line, which I removed:

graph = ox.utils_graph.get_undirected(org_graph)

It seems the graph is oriented, but in the end, the resulted GPX file still don't respect the direction of the streets. OpenStreetMap is correctly mapped, and I inserted some lines in the middle of the code to check if the graph is oriented, which it is confirmed.

Is there anything I'm missing? I also checked the network package, which seems ready to deal with a directed graph. This is a discussion he had some time ago, without solution.

You can see the original code here, and my adapted code here:

import warnings
warnings.filterwarnings("ignore")

from libs.tools import *
from libs.graph_route import plot_graph_route

import networkx as nx
import osmnx as ox
import matplotlib.pyplot as plt

from network import Network
from network.algorithms import hierholzer
ox.config(use_cache=True, log_console=True)


org_graph = ox.graph.graph_from_place("Campus do Pici, Fortaleza", network_type='drive', simplify=True, retain_all=True, truncate_by_edge=False, which_result=None, buffer_dist=0, clean_periphery=None, custom_filter=None)
fig, ax = ox.plot_graph(org_graph, node_zorder=2, node_color="k", bgcolor="w")


# The nodes you want to remove (replace with your actual node IDs) - workaround to remove some nodes in order to make the network fully reachable.
nodes_to_remove = [7804644351, 2509017600]

# Remove the nodes
org_graph.remove_nodes_from(nodes_to_remove)
fig, ax = ox.plot_graph(org_graph, node_zorder=2, node_color="k", bgcolor="w")


graph = ox.utils_graph.get_largest_component(org_graph,strongly=False)
fig, ax = ox.plot_graph(graph, node_zorder=2, node_color="k", bgcolor="w")


# Finds the odd degree nodes and minimal matching
odd_degree_nodes = get_odd_degree_nodes(graph)
pair_weights = get_shortest_distance_for_odd_degrees(graph, odd_degree_nodes)
matched_edges_with_weights = min_matching(pair_weights)


fig, ax = plt.subplots(figsize=(8, 8), facecolor='black', frameon=False)
for v, u, w in matched_edges_with_weights:
x = graph.nodes[v]["x"], graph.nodes["x"]
y = graph.nodes[v]["y"], graph.nodes["y"]
ax.plot(x, y, c='red', alpha=0.3)
ax.scatter(x, y, c='red', edgecolor="none")

fig, ax = ox.plot_graph(graph, node_zorder=2, node_color='g', bgcolor='k', ax=ax)


from libs.gpx_formatter import TEMPLATE, TRACE_POINT
from datetime import datetime
...
# List all edges of the extended graph including original edges and edges from minimal matching
single_edges = [(u, v) for u, v, k in graph.edges]
added_edges = get_shortest_paths(graph, matched_edges_with_weights)
edges = map_osmnx_edges2integers(graph, single_edges + added_edges)

# Finds the Eulerian path
network = Network(len(graph.nodes), edges, weighted=True)
eulerian_path = hierholzer(network)
converted_eulerian_path = convert_integer_path2osmnx_nodes(eulerian_path, graph.nodes())
double_edge_heap = get_double_edge_heap(org_graph)

# Finds the final path with edge IDs
final_path = convert_path(graph, converted_eulerian_path, double_edge_heap)
coordinates_path = convert_final_path_to_coordinates(org_graph, final_path)

eccentricity = nx.eccentricity(graph)
center = nx.center(graph)
center_node = graph.nodes[center[0]]

trace_points = "\n\t\t\t".join([TRACE_POINT.format(
lat=lat, lon=lon, id=i, timestamp=datetime.now().isoformat()
) for i, (lat, lon) in enumerate(coordinates_path)])

gpx_payload = TEMPLATE.format(
name="Name your everystreet route",
trace_points=trace_points,
center_lat=center_node["y"],
center_lon=center_node["x"]
)

with open("gpx_output.gpx", "w") as f:
f.write(gpx_payload)


In this last section, at network = Network(len(graph.nodes), edges, weighted=True), I also added directed=True, but then it throws an error:

ValueError Traceback (most recent call last)
Cell In[11], line 11
9 # Finds the Eulerian path
10 network = Network(len(graph.nodes), edges, directed=True, weighted=True)
---> 11 eulerian_path = hierholzer(network)
12 converted_eulerian_path = convert_integer_path2osmnx_nodes(eulerian_path, graph.nodes())
13 double_edge_heap = get_double_edge_heap(org_graph)

File ~\everystreet\network\algorithms\eulerian.py:67, in hierholzer(network, source)
64 if network.n == 0:
65 return path
---> 67 eulerian, odd_degree_nodes = is_eulerian(network)
68 if not eulerian:
69 raise NotEulerianNetwork(f"Network is not Eulerian, not all nodes are even degree: {odd_degree_nodes}")

File ~\everystreet\network\algorithms\eulerian.py:22, in is_eulerian(network)
12 """ Checks if the network is Eulerian
13
14 Args:
(...)
19 odd_degree_nodes (list): list if nodes with odd degree
20 """
21 if network.directed:
---> 22 out_degree, in_degree = network.directed_degrees()
23 odd_degree_nodes = [
24 {"node": n, "out_degree": d, "in_degree": in_degree[n]}
25 for n, d in enumerate(out_degree) if d != in_degree[n]
26 ]
27 else:

File ~\everystreet\network\network.py:146, in Network.directed_degrees(self)
135 """However, degrees_list holds info about out-degree values (or both for undirected networks), this function
136 return out-degree and in-degree for each node
137
(...)
143 after running Network.directed_degrees()!
144 """
145 out_degree = self.degrees_list
--> 146 in_coming_edges_basket = self.get_edge_basket(self.n, self.edges, reverse=True, directed=True)
148 in_degree = [len(_) for _ in in_coming_edges_basket]
149 self.in_degrees_list = in_degree

File ~\everystreet\network\network.py:69, in Network.get_edge_basket(n, edges, edge_basket, directed, reverse, weighted)
66 # Removing weights for weighted network
67 edges = [(v, u) for v, u, w in edges] if weighted else edges
---> 69 for v, u in edges:
70 if reverse and directed:
71 v, u = u, v

ValueError: too many values to unpack (expected 2)

Continue reading...