For simplifying and deleting degree-4 vertices

[kkdd]

Contributing guidelines

• [X] I understand the contributing guidelines

Documentation

• [X] My proposal is not addressed by the documentation or examples

Existing issues

• [X] Nothing similar appears in an existing issue

What problem does your feature proposal solve?

Hello, For simplifying MultiDiGraph in osmnx, I think that degree-4 vertices should be deleted only when originating from two-way ways.

What is your proposed solution?

See above.

What alternatives have you considered?

For alternative solution, convert OSM two-way ways to MultiGraph, delete degree-2 vertices, convert it to MultiDiGraph, and merge into the MultiDiGraph of one-way ways.

Additional context

https://github.com/kkdd/GraphFromOSM/blob/master/js/simplify-graph.js

[gboeing]

Thanks for your suggestion. Are you referring to rule 3? Can you provide more details and the "why" of your logic, and some real world examples of what would be modeled better?

[kkdd]

Thank you for your reply. Yes, I have slight suspicion about part of the simplification rule 3. OSM road network could be modeled by a mixed multigraph. So I think the rule should be:

• delete degree-2 nodes and concatenate connecting ways if
  • the both of ways are two-way (--*--), or
  • the both of ways are one-way with the propagating direction (→*→), that is, the node is connected to one inward and one outward ways,
• except for the case of isolated loops (and cycle graphs).

I'm however afraid that the above would not be easily realized based on networkx. And my source code, simplify-graph.js, is not recommended for you because it isn't based on networkx but on MatveiT/GraphFromOSM.

[gboeing]

Could you share a specific OSM node or two that OSMnx currently simplifies incorrectly and how your proposal's result would differ?

[kkdd]

Your are interested in the existence of the specific examples in point derived from actual osm data. I'm interested in the theoretical basis of rule 3, on the other hand.

Long-time patience would be required to find these rare examples, but I'm now pursuing the methodology for finding them.

[gboeing]

Your are interested in the existence of the specific examples in point derived from actual osm data. I'm interested in the theoretical basis of rule 3, on the other hand.

Actually, I am failing to understand the theoretical basis of your proposed problem. I'm requesting specific examples to demonstrate both the current problem and the proposed solution.

You said:

I think that degree-4 vertices should be deleted only when originating from two-way ways.

But why? Like I said in my first comment: can you provide the "why" of your logic? And, importantly, how does this relate to current OSMnx behavior?

You also said:

OSM road network could be modeled by a mixed multigraph

There are no mixed graphs in NetworkX. These are MultiDiGraphs, so node degree $k = k{in} + k{out}$. Hence the logic of rule 3 is that a node is not an endpoint if it has exactly 2 neighbors and is either degree-2 (i.e., it has 2 incident one-way edges that unidirectionally link it to its 2 neighbors) or degree-4 (i.e., it has 4 incident one-way edges that bidirectionally link it to its 2 neighbors). This is the current behavior. But as far as I can tell, this is what you proposed in the bullet points where you said "So I think the rule should be."

All that said: I'm always open to improving these algorithms if we can make a more faithful graph model. If you do see an opportunity for improvement, please identify/demonstrate the current problem, and why/how the proposed solution resolves it.

[kkdd]

I will introduce the artifact example of an OSM road network below, where junctions are depicted by blue circles and distinct oneway roads are depicted by orange lines.

I think that any junctions should not be deleted during simplification in this example because these junctions exist and these roads are distinct. Would you have any disagreement with it?

[gboeing]

Yes, I would disagree. Here's a simple NetworkX model of your graph drawing:

import networkx as nx
import osmnx as ox
G = nx.MultiDiGraph()
G.add_nodes_from([1, 2, 3, 4, 5, 6], x=0, y=0)
G.add_edges_from([(1, 2), (2, 3), (3, 2), (3, 4), (4, 3), (4, 5), (5, 4), (5, 6)])
print(len(G.nodes), len(G.edges))

We have 6 nodes and 8 directed edges. So what's the desired simplification here?

Nodes 1 and 6 should remain, because they are degree-1 endpoints. Nodes 2 and 5 should remain, because they are transition points between one-way and two-way traffic. Nodes 3 and 4 should be removed to create simplified reciprocal edges between nodes 2 and 5 directly, because nodes 3 and 4 are not junctions of distinct roads. They are interstitial geometric vertices along the road between nodes 2 and 5.

Gs = ox.simplification.simplify_graph(G)
print(len(Gs.nodes), len(Gs.edges))
print(Gs.nodes)
print(Gs.edges(keys=False))

Which prints:

4 4
[1, 2, 5, 6]
[(1, 2), (2, 5), (5, 6), (5, 2)]

As expected. But, let's say hypothetically that nodes 3 and 4 are actually junctions of distinct roads. In other words, in this hypothetical street network, nodes 3 and 4 each represent "elbow" intersections of two different named streets, each of which terminates at the node in question. In that case, you could retain them (i.e., simplification would change nothing in this graph) by simplifying in non-strict mode. From the docs:

Use the node_attrs_include or edge_attrs_differ parameters to relax simplification strictness. For example, edge_attrs_differ=[“osmid”] will retain every node whose incident edges have different OSM IDs. This lets you keep nodes at elbow two-way intersections (but be aware that sometimes individual blocks have multiple OSM IDs within them too). You could also use this parameter to retain nodes where sidewalks or bike lanes begin/end in the middle of a block. Or for example, node_attrs_include=[“highway”] will retain every node with a “highway” attribute (regardless of its value), even if it does not represent a street junction.

[kkdd]

Thank you for your detail description. The OSM data of this artifact example just describes that node-3 (and node-4, similarly) has two inward and two outward distinct oneway roads, and this means it is a junction, as shown below. Why did you consider it isn't by default? Do you recommend using the non-strict mode in the simplification for oneway roads unless any other information is obtained?

[gboeing]

example just describes that node-3 (and node-4, similarly) has two inward and two outward distinct oneway roads, and this means it is a junction

But it doesn't "just" show that: in addition to how many incident edges node 3 has, your drawing also showed how many adjacent neighbors (predecessors and successors) it has. That is, in your first drawing, node 3 has only 2 neighbors, and is linked to each by one inbound edge and one outbound edge apiece.

Why did you consider it isn't by default?

The combination of neighbors + configuration of incident edges determines whether it's a junction or not. In your first drawing, node 3 is not a junction because of that combination: it merely serves to link node 2 to node 4 rather than represent a junction of multiple different streets.

In your second drawing, it is a junction and OSMnx would not remove it in simplification. Here, node 3 has 4 neighbors and is linked to each by a single directed edge. In other words: the topology of node 3's neighborhood differs between your first and second drawings. Thus, it is not a junction in drawing 1, but it is in drawing 2, and hence you get different simplification outcomes.

Do you recommend using the non-strict mode in the simplification for oneway roads unless any other information is obtained?

You can relax simplification strictness to produce any fine-tuned simplification outcome you desire. Those function parameters offer the user nearly infinite flexibility.

[kkdd]

Thank you for your description. This OSM data example describes that you can travel also along the oneway route passing nodes 1, 2, 3, and 2 in this order, because no turn restriction is provided on node-3. Would you delete node-3?

On the travel in this road network, you can choose the directions of turn at node-3, and this ensures it is a junction. I would have considered that you have substantially added and used a kind of assumption, which makes node-3 not being a junction. Is this consideration agreeable to you?

[gboeing]

In a model, the components have to represent something. In an OSMnx street network model, as the documentation explains, the nodes represent intersections (of 2+ streets) and dead-ends, and the edges represent the street segments that link them. This is the modeling choice (i.e., assumption) of this modeling tool, but it is a standard one.

I would have considered that you have substantially added and used a kind of assumption, which makes node-3 not being a junction.

All models are formal simplifications of reality that including a set of assumptions. In OSMnx, one assumption is that definition of what nodes and edges represent. This is inherent to modeling. The (brief) explanation follows below.

On the travel in this road network, you can choose the directions of turn at node-3, and this ensures it is a junction.

No. That's not how streets work and that's not how OSMnx models them. On many streets, drivers could make a u-turn at any time. On all pedestrian paths, pedestrians can make a u-turn at any time. That doesn't mean they contain infinitely many junctions, nor does it mean we should model them as such. Conversely, if node 3 offers a unique or intentional turnaround point along a street segment, it should be tagged as such on OSM (and you can easily thus retain it in non-strict simplification mode).

In an unsimplified graph, you can make a u-turn at every geometric line vertex of a bidirectional street, as you wish to do here. If you wish to retain that behavior, just don't simplify your graph. The simplify_graph function makes an OSMnx model parsimonious for several benefits. First, parsimonious graphs better represent reality in terms of how we typically think about the street network in the practice of urban design and transport engineering: nodes are intersections/dead-ends and edges are street segments. Second, they offer more accurate network statistics (e.g., intersection counts, densities, block lengths, etc all depend on such parsimony). Third, they offer much fast algorithmic completion, as most graph algorithms scale with the node count.

[kkdd]

Thank you for your detailed explanation. Could you provide the too conceptual and mathematical option in the graph simplification of OSMnx? To explain additionally, it would allow to select the directions of turn at the nodes 3 and 4 on the network of directional ways, where any u-turns would be prohibited, shown in the following, exaggeratedly.

I consider that the graph simplification, deleting degree-2 vertices, is justified by that it is an equivalent conversion under usual conditions, even though it isn't pure-mathematically.

I agree with you on that u-turns seem to be allowed at any positions on the bidirectional ways which don't have any restrictive OSM tags.

[gboeing]

Could you provide the too conceptual and mathematical option in the graph simplification of OSMnx?

I'm not sure what this means. But if you're interested in how to configure the simplify_graph function in OSMnx, it is detailed in the documentation's user reference and the OSMnx examples gallery repo.

I'm going to close this issue as this isn't a change we'll be making to the package. But if you do have a "how-to" or usage question, please ask it at the user community on StackOverflow per the contributing guidelines.

[kkdd]

Thank you for your explanation. I consider that OSMnx seems to be specialized for city streets, not for universal ways.