Fitting Road Network Data to a Graph
How to model a graph based on a road network dataset
Note
This documentation is for a prior release of Kinetica. For the latest documentation, click here.
How to model a graph based on a road network dataset
The following guide provides step-by-step instructions to get started with fitting existing road network data to a graph. Since edges in graphs can only be composed of two nodes, the weight (or cost to travel) for complex WKT LINESTRINGs (e.g., more than two points) that typically define road networks must be assigned consistently to the segments composing the LINESTRING, as noted under Weights. There are two methods for calculating and assigning weights to a graph with edges derived from large WKT LINESTRINGs:
The tutorial makes use of the dc_shape dataset, which can be ingested from the data file mentioned above.
To ingest the file using Workbench:
The file will be validated and records will be inserted.
Fitting road network data to a graph using inline expressions offers a simpler but less efficient approach to deriving the individual edge segments' weight. The dc_shape_inline graph that will be created will calculate weight as distance inline and is based on the aforementioned dc_shape dataset.
Before starting with graph creation, a schema, graph_c_fit_data, will be created to contain the tables supporting graph creation & solving. To create the schema:
To create the graph, in Workbench:
|
|
This creates the dc_shape_inline graph with the following characteristics:
To view the created graph:
Fitting road network data to a graph using expansion separates the creation of line segments and calculation of distance from graph creation. This increases the performance of the graph creation process, as most of the calculations are done within the database instead of the graph server. Expansion is achieved through iteration, wherein each source record with a WKT is expanded into a number of records equal to the number of edges in that corresponding WKT. For example, a single road record with a 10-segment WKT LINESTRING will become ten individual records, each containing one of the 10 segments. In this way, the weights can be pre-calculated and assigned directly to the road segments/edges, alleviating the need for the graph server to do this processing itself.
To accomplish this, first create the expansion table, in Workbench:
|
|
This CREATE TABLE ... AS statement performs several actions necessary to expand the edges and prepare the data for use by the graph creation process.
First the complex LINESTRINGs are divided into single edges via a subquery:
Next, an outer query is used to eliminate the column nullability introduced by join (since graphs cannot be created from columns with the nullable property), and also to calculate the weight as distance. Lastly, the result is saved to a table, which the graph creation will use as input.
Finally, the dc_shape_expansion graph is created directly from the dc_shape_expanded table with no extra calculations necessary. The graph is created with the same characteristics as before, with the following changes:
To create the graph:
|
|
To view the created graph: