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
In-line Expressions -- calculating weights using inline
expressions and forcing the graph
server to divide complex WKT LINESTRINGs during the graph creation
Expansion -- using iteration to divide
complex WKT LINESTRINGs and, using a subquery, calculate weights prior to the
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, tutorial_graph_fit_data, will
be created to contain the tables supporting graph creation & solving. To create
On the left side under the Data tab, click the
+ next to Tables & Views and then click
Add New Schema.
Enter input tutorial_graph_fit_data as the Name, and
To create the graph, in Workbench:
On the left side of the screen, click on Workbooks.
Click the + and select
Add New Workbook.
Name your new workbook Fitting Data and click Create.
Copy the following CREATE GRAPH statement into the first
block of your workbook:
This creates the dc_shape_inline graph with the following characteristics:
It is DIRECTED because the roads in the graph
have directionality (one-way and two-way roads).
It has no explicitly defined nodes, because the
example relies on implicit nodes attached to the defined edges.
The EDGES are derived from WKT LINESTRINGs in the
shape column of the dc_shape table (AS WKTLINE); the graph
server will automatically divide each complex LINESTRING into simple edges.
Each edge's directionality is derived from the direction column of the
dc_shape table (AS DIRECTION), and each edge will be assigned
an ID that is the link_id column of the dc_shape table
The edge weights are represented as distance,
which is calculated as the length of the entire shape column's LINESTRING
(in meters) divided by the number of points in the LINESTRING minus 1
It has no inherent restrictions for any of
the nodes or edges in the graph.
It utilizes the following OPTIONS:
It will be replaced with this instance of the graph if a graph of the same
name exists (recreate).
If nodes are within 0.00001 degrees (1 meter) of each other, they are
merged together (merge_tolerance).
The resulting graph's information is placed into a table
(enable_graph_draw/graph_table) and an EDGE_WKTLINE column is
included so the graph can be visualized.
To view the created graph:
Click on dc_shape_inline under Graphs
in the left hand menu, and click Preview.
Click Update to use the default map settings.
Fit Using Expansion
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
Create Expansion Table
To accomplish this, first create the expansion table, in Workbench:
If not already viewing the Fitting Data workbook, click
Explore at the top of the screen, and then click the
Fitting Data workbook.
Click the run icon to create the expanded data table.
This CREATE TABLE...AS statement performs several actions
necessary to expand the edges and prepare the data for use by the graph creation
First the complex LINESTRINGs are divided into single edges via a subquery:
The existing dc_shape table is joined to the ITER virtual table, where
each WKT LINESTRING is iterated through to extract line segments.
A new WKT LINESTRING is constructed (ST_MakeLine) from each consecutive
pair of points in the source LINESTRING (dc_shape.shape) column.
The direction and link_id columns are extracted from the dc_shape
table to assist in graph creation later.
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.
The results of the query are placed in a new table
The link_id and direction columns are passed through as they are.
The shape column has its nullability removed (REMOVE_NULLABLE).
The shape column is used to calculate a distance column (distance),
and nullability is removed from that column as well.
Create Graph from Expansion Table
Finally, the dc_shape_expansion graph is created directly from the
dc_shape_expandedtable with no extra calculations necessary. The graph
is created with the same characteristics as before, with the following changes:
The edges are derived from the line segments expanded from the original WKT
LINESTRINGs in the shape column of the dc_shape_expanded table
The weights are pulled directly from the distance column of the
dc_shape_expanded table (WEIGHT_VALUESPECIFIED), pre-calculated