Repository: gboeing/osmnx

Issue:
Fix duplicate edges in save_graph_osm()
When I originally wrote this function, I didn't realize that the edges dataframe generated by `ox.graph_to_gdfs()` will contain multiple rows with the same `osmid` for any way that is associate with more than two nodes. As such, save_graph_osm() will generate XML like
```
<way id="123456789"/>
  <nd ref="1"/>
  <nd ref="2"/>
  <tag k="highway" v="residential"/>
</way>
<way id="123456789"/>
  <nd ref="2"/>
  <nd ref="3"/>
 <tag k="highway" v="residential"/>
</way>
<way id="123456789"/>
  <nd ref="3"/>
  <nd ref="4"/>
  <tag k="highway" v="residential"/> 
</way>
```
instead of 
```
<way id="123456789"/>
  <nd ref="1"/>
  <nd ref="2"/>
  <nd ref="3"/>
  <nd ref="4"/>
  <tag k="highway" v="residential"/>
</way>
```
The XML will still validate, as was documented in the original PR, but it doesn't technically conform to the OSM XML design schema, nor is it the most efficient way of storing the data. Furthermore I'm just not sure what this might do for any downstream processes (e.g. routers) that make use of this re-formatted file. 

In practice, this should be a straightforward fix, edit [this](https://github.com/gboeing/osmnx/blob/master/osmnx/save_load.py#L217-L224) chunk of code to check whether or not the tree already contains an edge with that id and if so just add the new nodes to it rather than creating a whole new way. However, according to the OSM wiki, OSM XML requires that the `<nd/>` tags be listed "in the correct order" (see the last sentence [here](https://wiki.openstreetmap.org/wiki/Way#Street_as_a_vector), and I'm unsure if its possible to infer that order from the order in which the duplicate `osmid` ways appear in the edges table.. 

So, my questions are two-fold:
1. Is this a big enough problem to worry about fixing?
2. If so, is it possible to recover the correct node order from either the edges table or the original NetworkX graph object?

Discussion:

Patch:
diff --git a/osmnx/core.py b/osmnx/core.py
index d9588335..9c844d4a 100644
--- a/osmnx/core.py
+++ b/osmnx/core.py
@@ -807,8 +807,11 @@ def add_path(G, data, one_way):
     del data['nodes']
 
     # set the oneway attribute to the passed-in value, to make it consistent
-    # True/False values
-    data['oneway'] = one_way
+    # True/False values, but only do this if you aren't forcing all edges to
+    # oneway with the all_oneway setting. With the all_oneway setting, you
+    # likely still want to preserve the original OSM oneway attribute.
+    if not settings.all_oneway:
+        data['oneway'] = one_way
 
     # zip together the path nodes so you get tuples like (0,1), (1,2), (2,3)
     # and so on
@@ -846,9 +849,11 @@ def add_paths(G, paths, bidirectional=False):
 
     for data in paths.values():
 
+        if settings.all_oneway is True:
+            add_path(G, data, one_way=True)
         # if this path is tagged as one-way and if it is not a walking network,
         # then we'll add the path in one direction only
-        if ('oneway' in data and data['oneway'] in osm_oneway_values) and not bidirectional:
+        elif ('oneway' in data and data['oneway'] in osm_oneway_values) and not bidirectional:
             if data['oneway'] == '-1':
                 # paths with a one-way value of -1 are one-way, but in the
                 # reverse direction of the nodes' order, see osm documentation
diff --git a/osmnx/save_load.py b/osmnx/save_load.py
index c12b3373..ac09de0d 100644
--- a/osmnx/save_load.py
+++ b/osmnx/save_load.py
@@ -19,7 +19,7 @@ from shapely import wkt
 from xml.etree import ElementTree as etree
 
 from . import settings
-from .utils import make_str, log
+from .utils import make_str, log, get_unique_nodes_ordered_from_way
 
 
 def save_gdf_shapefile(gdf, filename=None, folder=None):
@@ -147,7 +147,7 @@ def save_graph_osm(G, node_tags=settings.osm_xml_node_tags,
                    node_attrs=settings.osm_xml_node_attrs,
                    edge_tags=settings.osm_xml_way_tags,
                    edge_attrs=settings.osm_xml_way_attrs,
-                   oneway=True, filename='graph.osm',
+                   oneway=False, filename='graph.osm',
                    folder=None):
     """
     Save a graph as an OSM XML formatted file. NOTE: for very large
@@ -169,11 +169,12 @@ def save_graph_osm(G, node_tags=settings.osm_xml_node_tags,
     if folder is None:
         folder = settings.data_folder
 
+    # get undirected graph so we don't generate duplicate nodes and
     # create a copy to convert all the node/edge attribute values to string
-    G_save = G.copy()
+    H = get_undirected(G).copy()
 
     gdf_nodes, gdf_edges = graph_to_gdfs(
-        G_save, node_geometry=False, fill_edge_geometry=False)
+        H, node_geometry=False, fill_edge_geometry=False)
 
     # rename columns per osm specification
     gdf_nodes.rename(
@@ -197,13 +198,15 @@ def save_graph_osm(G, node_tags=settings.osm_xml_node_tags,
 
     # misc. string replacements to meet OSM XML spec
     if 'oneway' in edges.columns:
-        edges.loc[:, 'oneway'] = oneway
+
+        # fill blank oneway tags with default (False)
+        edges.loc[pd.isnull(edges['oneway']), 'oneway'] = oneway
         edges.loc[:, 'oneway'] = edges['oneway'].astype(str)
         edges.loc[:, 'oneway'] = edges['oneway'].str.replace(
             'False', 'no').replace('True', 'yes')
 
     # initialize XML tree with an OSM root element
-    root = etree.Element('osm')
+    root = etree.Element('osm', attrib={'version': '1', 'generator': 'OSMnx'})
 
     # append nodes to the XML tree
     for i, row in nodes.iterrows():
@@ -214,14 +217,23 @@ def save_graph_osm(G, node_tags=settings.osm_xml_node_tags,
                 node, 'tag', attrib={'k': tag, 'v': row[tag]})
 
     # append edges to the XML tree
-    for i, row in edges.iterrows():
+    for e in edges.id.unique():
+        all_way_edges = edges[edges['id'] == e]
+        first = all_way_edges.iloc[0]
         edge = etree.SubElement(
-            root, 'way', attrib=row[edge_attrs].dropna().to_dict())
-        etree.SubElement(edge, 'nd', attrib={'ref': row['u']})
-        etree.SubElement(edge, 'nd', attrib={'ref': row['v']})
+            root, 'way', attrib=first[edge_attrs].dropna().to_dict())
+
+        if len(all_way_edges) == 1:
+            etree.SubElement(edge, 'nd', attrib={'ref': first['u']})
+            etree.SubElement(edge, 'nd', attrib={'ref': first['v']})
+        else:
+            ordered_nodes = get_unique_nodes_ordered_from_way(all_way_edges)
+            for node in ordered_nodes:
+                etree.SubElement(edge, 'nd', attrib={'ref': node})
+
         for tag in edge_tags:
             etree.SubElement(
-                edge, 'tag', attrib={'k': tag, 'v': row[tag]})
+                edge, 'tag', attrib={'k': tag, 'v': first[tag]})
 
     et = etree.ElementTree(root)
 
@@ -230,8 +242,8 @@ def save_graph_osm(G, node_tags=settings.osm_xml_node_tags,
 
     et.write(os.path.join(folder, filename))
 
-    log('Saved graph "{}" to disk as OSM at "{}" in {:,.2f} seconds'.format(
-        G_save.name, os.path.join(folder, filename), time.time() - start_time))
+    log('Saved graph to disk as OSM at "{}" in {:,.2f} seconds'.format(
+        os.path.join(folder, filename), time.time() - start_time))
 
 
 def save_graphml(G, filename='graph.graphml', folder=None, gephi=False):
diff --git a/osmnx/settings.py b/osmnx/settings.py
index 9f1d7d6c..d4aeb01c 100644
--- a/osmnx/settings.py
+++ b/osmnx/settings.py
@@ -52,6 +52,10 @@ default_access = '["access"!~"private"]'
 # The network types for which a bidirectional graph will be created
 bidirectional_network_types = ['walk']
 
+# all one-way mode to maintain original OSM node order
+# when constructing graphs specifically to save to .osm xml file
+all_oneway = False
+
 # default CRS to set when creating graphs
 default_crs = '+proj=longlat +ellps=WGS84 +datum=WGS84 +no_defs'
 
diff --git a/osmnx/utils.py b/osmnx/utils.py
index 27b7e16d..fbe8dd15 100644
--- a/osmnx/utils.py
+++ b/osmnx/utils.py
@@ -80,7 +80,8 @@ def config(data_folder=settings.data_folder,
            default_accept_language=settings.default_accept_language,
            nominatim_endpoint=settings.nominatim_endpoint,
            nominatim_key=settings.nominatim_key,
-           overpass_endpoint=settings.overpass_endpoint):
+           overpass_endpoint=settings.overpass_endpoint,
+           all_oneway=settings.all_oneway):
     """
     Configure osmnx by setting the default global vars to desired values.
 
@@ -125,6 +126,9 @@ def config(data_folder=settings.data_folder,
         your API key, if you are using an endpoint that requires one
     overpass_endpoint : string
         which API endpoint to use for overpass queries
+    all_oneway : boolean
+        if True, forces all paths to be loaded as oneway ways, preserving
+        the original order of nodes stored in the OSM way XML.
 
     Returns
     -------
@@ -158,6 +162,7 @@ def config(data_folder=settings.data_folder,
     settings.nominatim_endpoint = nominatim_endpoint
     settings.nominatim_key = nominatim_key
     settings.overpass_endpoint = overpass_endpoint
+    settings.all_oneway = all_oneway
 
     # if logging is turned on, log that we are configured
     if settings.log_file or settings.log_console:
@@ -331,3 +336,89 @@ def get_logger(level=None, name=None, filename=None):
         logger.handler_set = True
 
     return logger
+
+
+def get_unique_nodes_ordered_from_way(way_edges_df):
+    """
+    Function to recover the original order of nodes from a dataframe
+    of edges associated with a single OSM way.
+
+    Parameters
+    ----------
+    way_edges_df : pandas.DataFrame()
+        Dataframe containing columns 'u' and 'v' corresponding to
+        origin/desitination nodes.
+
+    Returns
+    -------
+    unique_ordered_nodes : list
+        An ordered list of unique node IDs
+
+    NOTE: If the edges do not all connect (e.g. [(1, 2), (2,3),
+    (10, 11), (11, 12), (12, 13)]), then this method will return
+    only those nodes associated with the FIRST chunk of connected
+    edges, even if subsequent connected chunks are contain more
+    total nodes. I don't believe that we would ever encounter this
+    kind of disconnected structure of nodes within a given way,
+    but as best I could tell it is not explicitly forbidden in the
+    OSM XML design schema. As such, I had to safeguard against it
+    to ensure this method wouldn't get stuck in the while loop if
+    encountered a disconnected structure. I'm using a print
+    statement right now to tell the user whether or not any nodes
+    have been dropped and how many.
+    """
+    all_nodes = list(way_edges_df['u'].values) + \
+        list(way_edges_df['v'].values)
+    num_unique_nodes = len(np.unique(all_nodes))
+    node_pairs = list(way_edges_df[['u', 'v']].values)
+    unique_ordered_nodes = []
+    recycled = []
+
+    while len(node_pairs) > 0:
+
+        pair = node_pairs.pop(0)
+        start = pair[0]
+        end = pair[1]
+        the_rest = [element for p in node_pairs for element in p]
+
+        # first pair
+        if len(unique_ordered_nodes) == 0:
+
+            # if there are subsequent pairs to match on
+            if start in the_rest or end in the_rest:
+                unique_ordered_nodes = list(pair)
+            continue
+
+        # if both nodes are already in the list, we don't need them
+        if (start in unique_ordered_nodes) and (end in unique_ordered_nodes):
+            continue
+
+        # if start node is in the list, add the end node to the right of it
+        if start in unique_ordered_nodes:
+            start_idx = unique_ordered_nodes.index(start)
+            end_idx = start_idx + 1
+            unique_ordered_nodes[end_idx:end_idx] = [end]
+
+        # if end node is in the list, add the start node to the left of it
+        elif end in unique_ordered_nodes:
+            end_idx = unique_ordered_nodes.index(end)
+            start_idx = end_idx
+            unique_ordered_nodes[start_idx:start_idx] = [start]
+
+        else:
+            # if we've already processed this pair and there is still no way
+            # to match it in the list, then we're done
+            if list(pair) in recycled:
+                break
+
+            # if there's no match in the list but there's a match in the
+            # remaining pairs to be processed, recycle it to process again
+            elif start in the_rest or end in the_rest:
+                node_pairs.append(pair)
+                recycled.append(list(pair))
+
+    if len(unique_ordered_nodes) < num_unique_nodes:
+        print('Recovered order for {0} of {1} nodes'.format(
+            len(unique_ordered_nodes), num_unique_nodes))
+
+    return unique_ordered_nodes


Test patch:
diff --git a/tests/test_osmnx.py b/tests/test_osmnx.py
index 271f91fb..030b24d9 100644
--- a/tests/test_osmnx.py
+++ b/tests/test_osmnx.py
@@ -5,6 +5,7 @@
 ################################################################################
 
 import matplotlib as mpl
+import pandas as pd
 import warnings
 
 mpl.use('Agg')  # use agg backend so you don't need a display on travis-ci
@@ -438,6 +439,14 @@ def test_osm_xml_output():
     ox.save_graph_osm(G)
 
 
+def test_ordered_nodes_from_way():
+    df = pd.DataFrame({
+        'u': [54, 2, 5, 3, 10, 19, 20],
+        'v': [76, 3, 8, 10, 5, 20, 15]})
+    ordered_nodes = ox.get_unique_nodes_ordered_from_way(df)
+    assert ordered_nodes == [2, 3, 10, 5, 8]
+
+
 def test_overpass():
     import pytest