Update pgr_createTopology documentation

[kimonkrenz]

Problem
pgr_createTopology has a long processing time when dealing with large networks. An alternative constitutes the use of the pgr_extractVertices function as pointed out by @Tim in issue:2087 and tested in issue:2255. This option is not directly obvious in the documentation, as the process is explained in the unobviously named function pgr_extractVertices without mentioning the functionality in the documentation Description.

#Improvement
I suggest to make this functionality clear to the user by copying example 2 from the documentation of pgr_extractVertices to the documentation of pgr_createTopology. This will highlight to users dealing with large networks that pgr_extractVertices is an alternative option to create the topology when processing time is of concern.

Alternatives
An alternative would be to reference example 2 in the documentation under Description of pgr_createTopology, e.g., "For an alternative way to create a network topology see pgr_extractVertices." and add to the Description of pgr_extractVertices that this function can also be used to create a network topology.

[cvvergara]

@kimonkrenz
@TimMcCauley
I started the work on this issue:
https://docs.pgrouting.org/dev/en/pgr_extractVertices.html#create-a-routing-topology
Please read, I expect your comments about it.
Is it clear, am I missing something? etc.

[kimonkrenz]

Hi @cvvergara, this looks clear and good to me. Two small remarks, and one question:

1. It would be helpful to add to the description that "pgr_extractVertices is an alternative option to create a routing topology."

2. It might be worth to highlight that the edge_table needs to have the columns 'id, source, target, x1, y1, x2, y2' in place in order to populate it with routing topology. Not sure if this is stated somewhere else in the documentation or if you believe this is necessary, otherwise ignore. E.g.:

ALTER TABLE edge_table ALTER COLUMN id TYPE bigint USING id::bigint;
ALTER TABLE edge_table ADD COLUMN IF NOT EXISTS source integer;
ALTER TABLE edge_table ADD COLUMN IF NOT EXISTS target integer;
ALTER TABLE edge_table ADD COLUMN IF NOT EXISTS x1 double precision;
ALTER TABLE edge_table ADD COLUMN IF NOT EXISTS y1 double precision;
ALTER TABLE edge_table ADD COLUMN IF NOT EXISTS x2 double precision;
ALTER TABLE edge_table ADD COLUMN IF NOT EXISTS y2 double precision;

3. When creating the vertices_table is the 'ORDER BY id' a necesssary step, or what is the benefit of ordering the table here?

[cvvergara]

Reminder for me:
Change from

WITH
out_going AS (
  SELECT id AS vid, unnest(out_edges) AS eid, x, y
  FROM vertices_table
)
UPDATE edge_table
SET source = vid, x1 = x, y1 = y
FROM out_going WHERE id = eid;

To

UPDATE edges AS e
SET source = v.id, x1 = x, y1 = y
FROM vertices AS v
WHERE ST_startPoint(e.geom) = v.geom;

• change for source
• change for target

[cvvergara]

@kimonkrenz

About geometries

Actually, to use pgRouting it does not need any geometry at all. see here
Having said that, when the data is related to geometries:

• x1, x2, y1, y2 are needed by some functions but they can be easily obtained using ST_X, ST_y, ST_startPoint, ST_endPoint for example x1 = ST_X(ST_startPoint(geom))
  • If the project use of aStar & bdAstar (where they are used)
    • having those values saved on the database or calculated on the fly will depend on the project'ss DB design: storage vs CPU
    • Since PostgresSQL 12 there is GENERATED ALWAYS

CREATE TABLE mexicomap (
    ...,
    geom geometry,
    x1 FLOAT GENERATED ALWAYS AS (ST_X(ST_startPoint(geom))) STORED,
    ....
);

About some other similar consequences

pgr_extractVertices was created as step 0 to deprecate pgr_createTopology But could not continue work on that because the use of it and comments were really needed to move forward.

The 3.4/4.0 under the covers objective is to deprecate:

• pgr_createTopology: Basically pgr_extractVertices was created to deprecate this first function
  pgr_createVerticesTable, it so happens that with pgr_extractVertices this function can be deprecated
• pgr_analyzeGraph
• Something similar will happen to
  pgr_AnalyzeOneWay If my memory does not fails me this was created thinking on data from "Tiger" (whatever that is, the name is the one that was curios for me, that is why I remember the name) So this is a "specialized" function, aka only the people that know what tiger is might be using it, and a specialized function can not belong to a library.
  pgr_nodeNetwork a "one functions does it all" design. And because of that design so many issues

As you can see on the documentation of pgr_extractVertices If the user needs something special, the code can be grabbed from the NOTICE and the user can make adjustments as needed because of the project's requirements or the quality of data.
So something similar (a function or set of functions with or without "dryrun" flag) will happen (or not) to be able to deprecate those functions (see pgr_degree as part of the "pgr_analyzeGraph will be deprecated" process)

And of course osm2pgRouting needs to be checked/adjusted so that the deprecated functions are not used and has all the basic needed columns to run any pgRouting function.

tasks

• Put "About the geometries" section of this issue somewhere in the documentation.
• ORDER BY on the inner query
  • does it change the topology of the graph?
    • if not then remove it.
    • if yes, be clear that we are using it in the documentation because all queries on the documentation are tested vs the same topology in order for the results to remain the same an all queries.
• "Normally" data comes from sources where there is no fromhere2pgRouting software
  • Have a section to show how to add the necessary columns & complete the routing topology

[TimMcCauley]

@kimonkrenz @TimMcCauley I started the work on this issue: https://docs.pgrouting.org/dev/en/pgr_extractVertices.html#create-a-routing-topology Please read, I expect your comments about it. Is it clear, am I missing something? etc.

It looks good. It may be very handy to highlight that one might want to contract the graph afterwards? While extractVertices will consider degree >=2 nodes as a vertex, createTopology will only add a vertex at a decision point of degree >=3. This is very cool as it will reduce the search space. What do you think @cvvergara @kimonkrenz ?

[cvvergara]

I am working this PR:
#2311
it is work in progress, this is the main file I am working on right now:
https://github.com/cvvergara/pgrouting/blob/issue-2308/doc/src/pgRouting-concepts.rst

@TimMcCauley
As this is a new function:
https://docs.pgrouting.org/dev/en/pgr_degree.html
That degree is the one you are talking about?

If I understand correctly

• too many degree = 1: a dead end contraction
• too many degree = 2; do a linear contraction
  Contracting data depends on the final application needs, the size of the data. but pgr_degree can help make a decision

SELECT * FROM pgr_degree(
  $$SELECT id FROM edges$$,
  $$SELECT id, in_edges, out_edges
    FROM pgr_extractVertices('SELECT id, geom FROM edges')$$);
 id | degree
----+--------
  1 |      1
  2 |      1
  3 |      2
  4 |      1
  5 |      1
  6 |      3
  7 |      4
  8 |      3
  9 |      1
 10 |      3
 11 |      4
 12 |      3
 13 |      1
 14 |      1
 15 |      2
 16 |      3
 17 |      2
(17 rows)

task

• incorporate use pgr_degree to help on decision of contraction process.

[TimMcCauley]

Cool function @cvvergara - what I mean is that createTopology takes care of not respecting degree 2 nodes while extractVertices does not. I.e. while extractVertices is much more performant, it will add vertices that are not really required. So removing them in a subsequent step with contraction makes sense to me. It could be highlighted in the docs if you think this is worth while.

[cvvergara]

Not yet finished, but #2311 covers more one documenting the "not use of pgr_createTopology" et all functions.
I still need to work on the last task.
But I will do on a different PR.