save_graph_xml fails if roundabout present

[stl-maxgardner]

Read these instructions carefully. Use the template below and fill out every section. Your issue will be automatically closed if you don't provide all of the information requested in the template, because we need this information to assist you. Before you proceed, review the contributing guidelines in the CONTRIBUTING.md file.

Please don't use the issue tracker to ask "how-to" or usage questions. If asked here, they will be closed automatically. Instead, ask "how-to" and usage questions on StackOverflow. If you installed OSMnx via conda and are experiencing installation problems, please open an issue at its feedstock instead.

Bug reports are for reporting a bug you have found in OSMnx's codebase. First search the open/closed issues and StackOverflow to see if the problem has already been noted. If it hasn't, fill in the bug reporting template below.

Completely fill out the following template.

• I have read the OSMnx contributing guidelines
• I have read the OSMnx documentation and usage examples
• I have searched the open/closed issues and StackOverflow for problems similar to mine

Problem description

• What did you do? Tried to create an osm xml file from a region containing a roundabout
• What did you expect to happen? An .osm xml file created
• And what actually happened instead? networkx.NetworkXUnfeasible error was thrown as soon as osmnx tried to perform a topological sort on a table of edges corresponding to a roundabout (https://overpass-turbo.eu/s/1vwy).

Environment information

• What operating system are you using? Ubuntu
• What Python version are you using? 3.11
• What OSMnx version are you using? 1.3.1
• How did you install OSMnx? conda-forge
• Provide a complete list of your environment's packages and their versions (for example, run conda list or pip list then paste the output between the two "details" tags below)

osmnx=1.3.1 numpy=1.24.3

Provide a complete minimal reproducible example

Your example code snippet here must be minimal so it doesn't contain extraneous code or data unrelated to your specific problem and it must be complete so we can independently run it from top to bottom by copying/pasting it into a Python interpreter. That means all imports and all variables must be defined. If you're unsure how to create a good reproducible example, read this guide. Do not post a screenshot of your code or error message: provide it as text.

import osmnx as ox
import numpy as np
overpass_date_str = '[date:"2023-04-01T00:00:00Z"]'
ox.settings.overpass_settings += overpass_date_str
ox.settings.all_oneway = True
ox.settings.bidirectional_network_types = []
g = ox.graph_from_point(
            (39.09091886432667, -84.52266036019037),
            dist=int(np.floor(1609.34 * (5.5))),
            dist_type="bbox",
            network_type="drive",
            simplify=False,
            retain_all=False,
        )
nodes, edges = ox.graph_to_gdfs(g)
way_df = edges[edges['osmid'] == 570883705]
ordered_nodes = ox.osm_xml._get_unique_nodes_ordered_from_way(way_df)

[stl-maxgardner]

Most of the time the topological sort isn't necessary because the rows are already ordered correctly. We only order them because it's not written anywhere in the OSM docs that they have to be, afaik. But if we assume the first row in the edges table is the first edge, a potential solution for the roundabout issue could look like this:

try:
    ordered_nodes = ox.osm_xml._get_unique_nodes_ordered_from_way(way_df)
except NetworkXUnfeasible:
    first_node = way_df.iloc[0]["u"]
    ordered_nodes = ox.osm_xml._get_unique_nodes_ordered_from_way(way_df.iloc[1:])
    ordered_nodes = [first_node] + ordered_nodes

[gboeing]

Interesting. Would you like to open a PR to correct this?

Most of the time the topological sort isn't necessary because the rows are already ordered correctly. We only order them because it's not written anywhere in the OSM docs that they have to be, afaik.

Can you remind me again why the rows need to be in a certain order? And what the OSM docs do say about it? That is, what exactly is expected here?

[gboeing]

Also, the NetworkX topological sort function only works on DAGs, which we should expect a real world street network to never be. Accordingly, we'd expect that unfeasible exception every time the function runs. Does it really make sense to have it in our codebase at all?

[mxndrwgrdnr]

The rows need to be in a certain order because that's how OSM defines a way:

Technically a way is an ordered list of nodes...The nodes defining the geometry of the way are enumerated in the correct order, and indicated only by reference using their unique identifier.

I honestly don't recall if I implemented the sorting logic just to conform with that definition or if I actually encountered errors without sorting.

You're right about the DAG thing, but the reason why you don't get an unfeasible exception every time is that the workflow for using save_graph_xml() requires the user to set ox.settings.all_oneway = True before loading the graph, as described in the docstring here: https://github.com/gboeing/osmnx/blob/main/osmnx/osm_xml.py#L116-L118. Maybe we can also raise an error if the user tries to run save_graph_xml() without ox.settings.all_oneway = True?

But also I won't be offended if you'd rather deprecate the method.

[gboeing]

You're right about the DAG thing, but the reason why you don't get an unfeasible exception every time is that the workflow for using save_graph_xml() requires the user to set ox.settings.all_oneway = True before loading the graph

I'm still not grasping something for some reason... The all_oneway setting really just affects the graph._add_paths function. It doesn't result in a DAG (you can still have cycles even if every street is one-way). So shouldn't that unfeasible exception still occur?

Maybe we can also raise an error if the user tries to run save_graph_xml() without ox.settings.all_oneway = True?

It currently raises a warning if this happens, so it should be obvious to the end user.

[mxndrwgrdnr]

Oh, yeah it works because the topological sort is only performed one way at a time, not on the whole graph: https://github.com/gboeing/osmnx/blob/main/osmnx/osm_xml.py#L306-L315

[gboeing]

Ah of course. That's what I was forgetting. I should have just looked back through the code more carefully.

[gboeing]

Given your potential solution earlier, would you like to open a PR?

[mxndrwgrdnr]

Yes, will do!

[gboeing]

Closed by #986

[gboeing]

See enhancements in #1135