-
-
Notifications
You must be signed in to change notification settings - Fork 49
file structure for a function
This wiki explains the flow of control when using functions by using the pgr_dijkstra as an example.
Each algorithm can have multiple SQL functions implemented which handle one-to-one, many-to-one, etc types of queries.
These implementations are stored in sql/dijkstra/dijkstra.sql file.
These functions are further documented here: https://docs.pgrouting.org/dev/en/pgr_dijkstra.html
The above-mentioned functions further call a function named _pgr_dijkstra. These calls are visible on lines 48, 73, 98 and 124 of sql/dijkstra/dijkstra.sql.
Any function which begins with "_" symbol such as _pgr_dijkstra will be considered as an internal function which is not directly available to the users. In our example, this function is implemented in file sql/dijkstra/_dijkstra.sql.
The internal function will then call a C function which is defined in src/dijkstra/dijkstra.c. The exact function that is called by the SQL code is defined in the sql/dijkstra/_dijkstra.sql file. In our example, 'many_to_many_dijkstra' is the function name that has been set in line 51 of _dijkstra.sql file.
The 'many_to_many_dijkstra' function is implemented in src/dijkstra/dijkstra.c beginning at line 139.
The data that is sent to this function from the SQL function is of the SQL datatypes which are not compatible with C. Thus, this SQL data must be converted to C data.
The raw data is extracted using PG_GETARG_ functions such as PG_GETARG_ARRAYTYPE_P, PG_GETARG_BOOL. PG_GETARG_INT64, etc. This conversion is done on lines 164 - 170 in src/dijkstra/dijkstra.c.
One thing to note is that the array returned by PG_GETARG_ARRAYTYPE_P is a Postgres-style array and will need further processing for C to efficiently use the data.
Each C file has a static process function. This function will accept the C type data from the 'many_to_many_dijkstra' function. The function is defined on line 51 of src/dijkstra/dijkstra.c.
The function will extract the graph edges(normal and/or reverse as per the normal parameter) from Postgres-style arrays using the pgr_get_edges and pgr_get_edges_reversed functions, convert the data using pgr_get_bigIntArray function and then store them in normal C integer type arrays.
Once all the data is loaded, it calls another function, in this case: do_pgr_many_to_many_dijkstra on line 97.
The function do_pgr_many_to_many_dijkstra is defined in the header file: include/drivers/dijkstra/dijkstra_driver.h . This file will be compiled in both C and C++ programming languages.
The function body of the do_pgr_many_to_many_dijkstra is located in src/dijkstra/dijkstra_driver.cpp. The do_pgr_many_to_many_dijkstra is the function that the C code is calling.
The assertions present on lines 106 through 111 are preconditions that must be true for the function to work properly.
Algorithms can work on directed or undirected graphs or both. To handle this, the do_pgr_many_to_many_dijkstra function calls the pgr_dijkstra function with the correct type of graph (directed/undirected).
The pgr_dijkstra function defined at line 45.
It includes code such as :
sources.erase(
std::unique(sources.begin(), sources.end()),
sources.end());
which serves to remove duplicate queries in order to reduce the computational load.
Example: The query SELECT * FROM pgr_dijkstra('SELECT * FROM edge_table', ARRAY[1,1,1,1,1], ARRAY[2,2,2,2]); The function will only then calculate one path from 1 to 2, as the duplicated 1's and duplicated 2's are removed.
Then,
pgrouting::Pgr_dijkstra< G > fn_dijkstra;
auto paths = fn_dijkstra.dijkstra(
will create an instance of the Pgr_Dijkstra class, and will use that instance to calculate the paths for the queries.
The class is a template and all of its member variables and functions are defined in the C++ header file include/dijkstra/pgr_dijkstra.hpp.
This file will contain the actual implementation and logic of the algorithm to be implemented. It can also include Boost code if required.
Once the results are calculated, they need to be converted to Postgres data types. The conversion take place from line 154 onwards in src/dijkstra/dijkstra_driver.cpp. Memory handling is also performed at this step.
There are two schemas for testing:
- pgTap schema -> Analysis based.
- Test schema ->Results based.
First, the analysis is done. if the result of the function should be r1 for the data x,y,z then the test should be:
select r1 = pgr_foo(x,y,z);
The wrong way is as follows:
select pgr_foo(x,y,z);
Store the result, say in r2 and then:
select r2 = pgr_foo(x,y,z);
This is because:
From the analysis, r1 was the result, not r2. If the result is r2 then there is a bug, because from the analysis the result should be r1.
A more explicit example:
pgr_addOne(x) adds one to x. So, the analysis says pgr_addOne(10) should be 11.
So the test is made as SELECT pgr_addOne(10) = 11;.
Let the pseudocode for the function be:
CREATE FUNCTION pgr_addOne(x bigint)
if x > 0 return x + 1
else return x -1
END function
By analysis, if 1 is added to -10, the result is -9.
Then the query SELECT pgr_addOne(-10) = -9; should be true.
if SELECT pgr_addOne(-10) is executed, it gives -11 as result.
So, SELECT pgr_addOne(-10) = -9; gives false as result, so there is a bug.
If the test is based on current results, then SELECT pgr_addOne(-10) = -11; will give true results and hence the bug is not caught.
Test schema is based on current results while pgTap schema is based on the analysis.
The test schema uses the sampledata(https://docs.pgrouting.org/dev/en/sampledata.html) which is a small graph.
The test schema's main purpose is to have the queries that are used on the documentation.
The code that includes the queries in the documentation is:
.. literalinclude:: doc-pgr_dijkstra.queries
:start-after: -- q1
:end-before: -- q2
in doc/dijkstra/pgr_dijkstra.rst.
The test/dijkstra/doc-pgr_dijkstra.result file generates the doc file doc/queries/doc-pgr_dijkstra.queries which is then included in the .rst file mentioned above.