931 miles that go nowhere, versus 2,761 that offer escape from either end.
For bikes at least, not that routing for other modes would change the figure much. Fun/disturbing fact of the day! Impress your friends with your amazing and mathematically informed knowledge of Cincinnati geography!
I talked about this geography of connectivity thing a little bit already, but since that post, I’ve switched to a better dead-end-finding algorithm. Where before I was looking for tree-like structures by recursing on nodes with only one edge, I’m now able to detect all nodes which could be removed from the graph‘s largest biconnected subcomponent by the elimination of just one edge. Or those which are already detached, of course.
In layman’s terms, this answers the question: “Where should we put no-exit signs?” Or for the purpose of defending our titular statement: “what portion of streets, measured by their length, would be behind such signs?”
Here is the PHP script I wrote to implement the algorithm. It connects to a PostgreSQL DB, and looks at a specified edge table with source and target fields. (These source and target fields are the IDs of the nodes on either end of the edges.) You can create an edge table, as I did, using OSM data processed with osm2po. Since I was routing for bikes, I excluded highways and most trunk roads. I also excluded dangling service roads from the measurement.
As the script runs through the graph, every time it isolates a subcomponent, it inserts the nodes of that subcomponent into a temporary table, along with a unique ID value for the component. Once all the nodes are in there(technically, they’re all part of some subcomponent), a GROUP BY statement gives us the ID of the biggest component. This component is the main street network itself. All edges that touch any node that is NOT part of this largest component are identified as dead-ending.
Before altogether too long, I’ll get around to doing some more interesting analysis and regional comparisons and mapping and stuff. But for now, I’m off to Europe with my little netbook, which is, to my honest delight, too puny for serious GIS.
I wonder what percentage of streets in the City of Cincinnati are dead-ends?
22%, roughly.