PARIS

code & requirements

###the code https://gist.github.com/Remi-C/85b32364a1e8b33af006

depends on python functions in rc_lib:

rc_lib: https://github.com/Remi-C/PPPP_utilities

Not the 7 bridges problem

I achieved quit an advanced graph processing method using combination of pgpointcloud, postgis, pgrouting, networkx, scikit learn, postgis topology.

I put it here as example so other people using pgrouting may know that is can be used for advanced stuff, all within the database.

SO first I create a simplified network based on a lot of data from pgpointcloud. I do this using postgis functions. In blue is the network, in grey Paris building, for easier understanding.

The goal is to reduce this network so it boils down to only a simple road network. For this I compute the topological distance from any node to any other node below a geometrical distance using postgis to create the node pairs, and the cool pgr_dijkstraCost function. In the image we plot a segment for each node-node pair, and color it according to pgrouting topological distance (notice top right edges are red, because topological distance is big)

Then we use plpython , with networkx to create a graph from those segments, then we convert this graph into a distance matrix, then the distance matrix is converted to an affinity matrix, then we use spectral clustering on this matrix ! To make it short, we automatically regroup the nodes of the original network into bigger groups containing nodes topologically close to each other.

Then we rebuild a network using postgis topology

then we simplify again this network.

Voila, we go from several thousands nodes and edges to a few dozen, while retaining the original graph layout.

here is the straight skeleton code : https://gist.github.com/Remi-C/8e4f250df3175cae7db6 here are straight skeleton results: the filtering process is fairly sophisticated.

failure is due to an error of polygon simplification in my end straight_skeleton_failure

Results are quite good for such a simple (pure geometry) method