pgr_nodeNetwork

[cvvergara]

The discussion of pgr_nodeNetwork for version 2.2 I would be nice a complete revision of pgr_nodeNetwork

Related Issues: #330 pgr_nodeNetwork, add where clause #280 pgr_nodeNetwork does not correctly split line segments #240 Couple of bugs after pgr_nodeNetwork applying #214 pgr_nodenetwork is creating 'LINESTRING EMPTY' records #172 small improvement suggestion for pgr_nodenetwork function in 2.0 RC #140 Add support for passing bigint as ids and returning them #423 switched id and geom in notice by pgr_nodeNetwork #540 ’pgr_nodeNetwork' sub_id starts from other number rather than 1 #623 Orthogonal lines to road network are not noded with pgr_nodeNetwork

[cvvergara]

@robe2 I'll add you as the assigned person. you might want to read all the related issues. (I'll assign you there also, except for #140 which is for all pgr_functions)

[cvvergara]

@robe2 I created the following branch for you to work on pgr_nodeNetwork nodeNetwork-dev-2.2

If anyone else want to work on pgr_nodeNetwork in your forks, please make the pull requests to nodeNetwork-dev-2.2

[cvvergara]

While developing: change this to your own mail https://github.com/pgRouting/pgrouting/blob/nodeNetwork-dev-2.2/.travis.yml#L18

[cvvergara]

Forgot, to keep track of the different hashes for the versioning, read and follow the instructions: https://github.com/pgRouting/pgrouting/blob/nodeNetwork-dev-2.2/tools/pre-commit

[yobiSource]

How about to replace pgr_nodeNetwork with PostGIS-Topology? That should solve all the Issues.

• native PostGIS
• WHERE clause possible
• editable and with (materialized) views automatic refreshing
  • add/delete edges does not require a completely new run of pgr_nodeNetwork
• ready for other uses with PostGIS-Topo

With Sample Data and without pgr_createTopology:

CREATE EXTENSION postgis_topology;
SELECT CreateTopology('route_topo', find_srid('public', 'edge_table', 'the_geom'));
SELECT AddTopoGeometryColumn('route_topo', 'public', 'edge_table', 'topogeom', 'LINE');
UPDATE edge_table SET topogeom = toTopoGeom(the_geom, 'route_topo', 1);

CREATE OR REPLACE VIEW public.v_edge_table_noded AS 
 SELECT e.edge_id,
    r.id,
    r.dir,
    r.source,
    r.target,
    r.cost,
    r.reverse_cost,
    e.start_node,
    e.end_node,
    e.geom
   FROM route_topo.edge e,
    route_topo.relation rel,
    edge_table r
  WHERE e.edge_id = rel.element_id AND rel.topogeo_id = (r.topogeom).id;

SELECT * FROM pgr_dijkstra(
        'SELECT edge_id AS id, start_node AS source, end_node AS target, cost, reverse_cost FROM v_edge_table_noded',
        2, 3); -- Cost not recalculated (ST_Length(geom) ), split edges are wrong

[cvvergara]

@yobiSource Interesting... I just re-read the documentation for pgr_nodeNetwork Also all the steps mentioned in the documentation are in this pgr_nodeNetwork test file. So if you load the sampledata and then run that code, you'll get the same results as in the documentation. And this tests are executed each time we modify something, to make sure the functionality remains the same. I can see you haven't updated your fork: https://github.com/yobiSource/pgrouting

This branch is 1 commit ahead, 646 commits behind pgRouting:master. 

I am working on some documentation for developers: http://docs.pgrouting.org/developers-doc/installation.html

The branch where you can work is nodeNet-dev-2.2 Modify src/common/sql/pgrouting_node_network.sql and run the tests mentioned on that documentation.

[cvvergara]

A monologue: When I used non OSM data when I did my map:

• I used pgr_nodeNetwork
• Some of the fixes I made.
• I wrote that extensive documentation, because I think of it as a "one time use function"
  • After getting the data, the data has to be prepared for your application needs.
  • So it helps to prepare the data. that its why it generates a new table, because not everything will be nodded.
    • overpass
    • bridges
    • underpass
• I remember it took a long time to process the data so the
  • #330 would be a nice feature, then one can add a BBOX and just node the troubled areas.
  • The troubled areas can be detected because its a dead end that is within the tolerance.
  • The dead ends can be detected in the vertices table because pgr_analyzeGraph fills: chk, cnt, e_in, e_out columns.

The process of testing pgr_nodeNetwork was with a lot of trial and error using analysing/fixing my non osm data.

[cvvergara]

@yobiSource If you want to try, first add the where clause to the existing pgr_nodeNetwork. More or less follow the code of pgr_analyzeGraph to do that. That will give you the hang of how we work on code contributions.

[woodbri]

@yobiSource postgis topology might be a good alternative for some people that need to node there data. How about adding a wiki page with your example of how to do that.

My concern would be performance. It would be interesting to see how it performs against our existing code (but I think there are/were some open bugs against our code). it might be interesting to plot the performance of noding 10, 100, 1K, 10K, 100K, 1M, 10M edge networks against pgr_nodenetwork() versus postgis_topology. The Tiger data for the US is about 20M, OSM data for Germany is in the 5-10M edges IIRC. Noding small networks is never a problem, it is always dealing with the larger sized ones where the performance problems shows up.

I would also be interested in how you would solve the overpass/underpass intersections.

[cvvergara]

I would do:

• pgr_AnalizeGraph
• detect in the vertices table the vertices that are dead end using the results left in the vertices table.
• Suppose vertex 3256is a dead end
• if it had the rows_where clause:

SELECT  pgr_nodeNetwork('edge_table', 0.001,
     rows_where:='the_geom &&
      (SELECT st_buffer(the_geom,0.05) 
           FROM edge_table WHERE source = 3256 or target = 3256)');

• I doubt it will work 10M edges
• So the rows_where clause is important to improve the performance.

I don't want to process 10M edges where I know where the problem is by using pgr_analyseGraph

[yobiSource]

I'm still working on the basics and check for correctness, thus no update in my fork

Everything processed with UPDATE edge_table SET topogeom = toTopoGeom(the_geom, 'route_topo', 1); are noded, including bridges, etc. If I understand the PG-Topo docs correctly, each intersection needs a node. Remove overpass/underpass from the network is not an option, they must be routable.

I just replace the split overpass/underpass with the original non-split:

SELECT e.edge_id,
    r.id,
    r.dir,
    r.source,
    r.target,
    r.cost,
    r.reverse_cost,
    e.start_node,
    e.end_node,
    e.geom,
    ST_Length(e.geom) As length
   FROM route_topo.edge e,
    route_topo.relation rel,
    edge_table r
  WHERE e.edge_id = rel.element_id AND rel.topogeo_id = (r.topogeom).id AND id <> 18 and id <> 13
  UNION
  SELECT (GetTopoGeomElementArray(topogeom))[1][1] AS edge_id, id, dir, source, target, cost, reverse_cost,
    GetNodeByPoint('route_topo',ST_StartPoint(the_geom), 0) AS start_node,
    GetNodeByPoint('route_topo',ST_EndPoint(the_geom), 0) AS end_node,
    the_geom AS geom, ST_Length(the_geom) As length
   FROM public.edge_table WHERE id = 18 or id = 13

The UPDATE is definitely slower but replaced pgr_nodeNetwork() and pgr_createTopology(). I'll test it with my 900K edges OSM data and run some tests. But first need some sleep.

[cvvergara]

for the overpass, underpass: the rows_where would be longer,

• suppose that my edges_table has a column: bridge and bridges are not to be nodded:

rows_where:='(bridge = false) and (the_geom &&
      (SELECT st_buffer(the_geom,0.05) 
           FROM edge_table WHERE source = 3256 or target = 3256))'

[cvvergara]

@yobiSource if you see the documentation pgr_nodeNetwork needs pre and post processing

The topology functions help to make routable networks, depending on the problem.

pgr_nodeNetwork helps to build routable data. For example: pgr_dijkstra: id, source, target, cost, [reverse_cost] is the routable data, there is no need of geometry of any kind

And depending on the problem we would make decisions on what is routable and what is not:

For example:

• If I am making an application to route cars (find shortest path for cars maybe based on length and speed): I don't want that dead end street to be nodded with the main road (the side walk in this case is wide, but in some cases its 1m wide, I just forgot where I saw it)
• If I am making an application to route telephone lines (find the shortest path in terms of length) I want that dead end street to be nodded.

[robe2]

@yobiSource which version of postgis_topology are you using? @strk converted the toTopoGeom and some other functions to be native C code. I think there are some kinks to be worked out, but I think the PostGIS 2.2 should be in general much faster than prior versions. @strk correct me if I misspoke.

[yobiSource]

@robe2 PostgreSQL 9.4.5, postgis_topology 2.1.8

@woodbri some information about the performance: https://lists.osgeo.org/pipermail/postgis-devel/2014-January/024085.html https://trac.osgeo.org/postgis/ticket/3321 http://de.slideshare.net/laopsahl/foss4-g-topologyjuly162015

my OSM data:

HINWEIS:  pgr_nodeNetwork('t_r_osm_ways',0.01,'geom','gid','test1')
HINWEIS:    Splitted Edges: 162965
HINWEIS:   Untouched Edges: 735687
HINWEIS:       Total original Edges: 898652
HINWEIS:   Edges generated: 998078
HINWEIS:   Untouched Edges: 735687
HINWEIS:         Total New segments: 1733765
Gesamtlaufzeit der Abfrage: 488111 ms.

SELECT  pgr_createTopology('t_r_osm_ways_test1',0.01,'geom','id','source','target');
Gesamtlaufzeit der Abfrage: 2099337 ms.

[cvvergara]

@yobiSource There is the issue #330 of allowing working with views. I don't think we can create columns on a view.

[yobiSource]

@cvvergara the source table is not changed by pgr_nodeNetwork but tested for indices. So when the source is a view Index test must be skipped.

The test with my OSM data run into an error (i think). Accordingly I can not provide runtimes, for now.

I will for now create the WHERE clause for pgr_nodeNetwork. (looks easier)

[cvvergara]

@yobiSource Yes, start with easy thing, but use git, so that you get the hang of it.

[yobiSource]

First commit: yobiSource/pgrouting@00ba37eaac87382d549dcb70e5f9a2e429513264

Refers the 'where' to the entire output or just to the nodefunction, or both (switch)? Currently everything is outputted and 'where' is noded.

[cvvergara]

Can you add here: https://github.com/yobiSource/pgrouting/blob/nodeNet-dev-2.2/.travis.yml#L22 a line with:

• nodeNet-dev-2.2

[yobiSource]

finished

I've added 2 optional parameters: WHERE and a switch if the entire table (including unnoded) should be created

This results in 3 ways.

1. the normal as before (all noded)
2. Only the passed where
3. the passed where + unnoded rest (like bridge)

Fixed in this version: #423

[cvvergara]

@yobiSource First I'll give you an explanation about rows_where (note, this is focused on dead ends, but care must be taken when edges intersect but you don't want a node because it is a bridge)

Rows_where is to work on a particular set of rows on the edge_table. That way, if someone has the whole world in the table, and is making an application for a particular city/town/country. And its going to find/fix problems. He can do use pgr_AnalyzeGraph (has a rows_where)

with location_bbox as 
(select boundary_geom as the_geom from city_boundaries where city = 12345 )
pgr_analyzeGraph( <other_parameters>  rows_where:=' the_geom && location_bbox.the_geom')

Then based on the results, he can inspect that the dead end is actually a dead end street. if the dead_end is not a dead_end street then he can fix the area around that point, using pgr_nodeNetwork. This is a proposed query with rows_where:

with location_bbox as
(select st_buffer(wrong_point....) as the_geom from ... )
select pgr_nodeNetwork( <other_parameters>  rows_where:=' the_geom && location_bbox.the_geom')

After that he can include the fixes in the original table. V2.1 uses all edges in edge_table that means if the are he is looking at is 1 Km² he has to process the whole world. V2.2 proposal is be able to use all edges in edge_table OR a particular set of edges defined by rows_where. That way he can only process the 1 Km² area of his interest

Now its your turn: A little explanation about the parameters, and your thoughts around them:

 node_where text DEFAULT ''::text, outall boolean DEFAULT false)

[yobiSource]

It's late so only a brief explanation.

My test examples with Sample Data:

SELECT pgr_nodeNetwork('edge_table', 0.01, 'id', 'the_geom', 'test1'); works the same as before total 20 edges

SELECT pgr_nodeNetwork('edge_table', 0.01, 'id', 'the_geom', 'test2', 'id<18', true); node_where is used to Filter the area every normal WHERE statement on edge_table is possible for example "the_geom && 'BOX(572126 5671279,1258837 6154972)'::box2d"

outall=true ensures that the filter only acts on the function for splitting the edges but not on the output of all data

for my test with the sample data and sql above: edge id 18 is not split but output as it is in the new table there is nothing else to split so total 18 edges

SELECT pgr_nodeNetwork('edge_table', 0.01, 'id', 'the_geom', 'test3', 'id<18'); as before but (outall=false) "where_node" is copied to "where_rows" and filters the created table

for my test with the sample data and sql above: edge id 18 will completely filtered and the new created table has only 17 edges

[cvvergara]

@yobiSource so nodes_where is what Its called rows_where in other functions?

[yobiSource]

Yes nodes_where for what is split rows_where for output

outall=false copies nodes_where to rows_where

The name I just need to distinguish between the two variables, can also be renamed. But both filtering rows in the end. (intersecting edges nodes_where and nonintersecting edges rows_where)

[cvvergara]

@yobiSource I see that the new parameters are optional, but I get this: https://travis-ci.org/pgRouting/pgrouting/jobs/91277542#L2024

I wonder if you ran in your computer, form the root of the repository: tools/test-runner.pl

Anyway I'll merge and @robe2 and me can have a look.

[yobiSource]

fixed forgot COMMENT ON FUNCTION pgr_nodeNetwork

Sorry I dont rebuild pgRouting I only create the functions with CREATE OR REPLACE FUNCTION ...

[cvvergara]

@yobiSource You dont need to rebuild, If you have a travis account (I don't think so I didnt find it), when you push, travis makes the builds. If you dont have, then after you push go to the site and make a pull request and travis will start a build that you can see , for example here, https://github.com/pgRouting/pgrouting/pull/429 clink on details link continuous-integration/travis-ci/pr — The Travis CI build is in progress

[cvvergara]

@robe2 when you have time can you check which of the issues mentioned in https://github.com/pgRouting/pgrouting/issues/419#issue-113713680 can be closed with the work you made on nodeNetwork? Thanks

[cvvergara]

This function needs a complete rewrite