Version:

Table Of Contents

  1. Docs
  2. Features
  3. Network Graphs & Solvers
  4. Network Graphs & Solvers Examples
  5. Fitting Road Network Data to a Graph Tutorial (DC)

Fitting Road Network Data to a Graph Tutorial (DC)

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:

  1. In-line Expressions -- calculating weights using inline expressions and forcing the graph server to divide complex WKT LINESTRINGs during the /create/graph operation
  2. Expansion -- using iteration to divide complex WKT LINESTRINGs and projections to calculate weights prior to the /create/graph operation

Prerequisites

Data File

The tutorial makes use of the dc_shape dataset, which can be ingested from the data file mentioned above. To ingest the file using GAdmin:

  1. Navigate to GAdmin and login (http://<kinetica-host>:8080/)
  2. In the top menu, click Data ‣ Import
  3. In the top right corner, click Advanced CSV Import
  4. Click Select File and select the data file from your local directory
  5. Leave the default options and values for the rest of Step 1 and Step 2
  6. Under Step 3: Confirm, click Import CSV

The file will be validated and records will be inserted.

Using the REST API

As mentioned above, running the following examples requires access to a REST client or a terminal. GAdmin contains a REST client (Query ‣ API) into which you can copy and paste JSON, so there's no need to download a third-party REST client. If opting to run the tutorial via a terminal, the tutorial script and cURL package are required. See Tutorial via Terminal for more information.

Tutorial via REST Client

This tutorial uses the GAdmin API Tool to create and solve the graph, but any REST client will work. To access the API tool in GAdmin:

  1. Navigate to GAdmin and login (http://<kinetica-host>:8080/)
  2. In the top menu, click Query ‣ API
  3. Under Request Mode, select JSON

Fit Using Inline Expressions

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 calculates weight as distance inline and is based on the aforementioned dc_shape dataset. The dc_shape_inline graph is created 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 (EDGE_WKTLINE); the graph server will automatically divide each complex LINESTRING into simple edges. The edge's directionality is derived from the direction column of the dc_shape table (EDGE_DIRECTION).
  • The 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 (WEIGHTS_VALUESPECIFIED). The weights are matched to the edges using the same shape column as edges (WEIGHTS_EDGE_WKTLINE) and the same direction column as the edge direction (WEIGHTS_EDGE_DIRECTION).
  • 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 will be merged together (merge_tolerance)
    • The resulting graph's information will be placed into a table (graph_table) and an EDGE_WKTLINE column will be included so the graph can be visualized (enable_graph_draw)

To create the graph:

  1. In the API Tool, select /create/graph from the Endpoint drop-down menu

  2. Copy the following JSON into the Request Mode text box:

    {
  "graph_name": "dc_shape_inline",
  "directed_graph": true,
  "nodes": [],
  "edges": [
    "dc_shape.shape AS EDGE_WKTLINE",
    "dc_shape.direction AS EDGE_DIRECTION"
  ],
  "weights": [
    "dc_shape.shape AS WEIGHTS_EDGE_WKTLINE",
    "dc_shape.direction AS WEIGHTS_EDGE_DIRECTION",
    "ST_Length(dc_shape.shape,1)/(ST_NPOINTS(dc_shape.shape)-1) AS WEIGHTS_VALUESPECIFIED"
  ],
  "restrictions": [],
  "options": {
    "merge_tolerance": "0.00001",
    "recreate": "true",
    "enable_graph_draw": "true",
    "graph_table": "dc_graph_inline_table"
  }
}

  3. Click Send Request

The response field on the right-hand side of the page will be populated with the server response:

------------------------------------------------------------
Wed Jan 15 2020 18:04:02 GMT-0500 (Eastern Standard Time)
------------------------------------------------------------
Endpoint: /create/graph
Time: 15650
Request: {
    "graph_name": "dc_shape_inline",
    "directed_graph": true,
    "nodes": [],
    "edges": [
        "dc_shape.shape AS EDGE_WKTLINE",
        "dc_shape.direction AS EDGE_DIRECTION"
    ],
    "weights": [
        "dc_shape.shape AS WEIGHTS_EDGE_WKTLINE",
        "dc_shape.direction AS WEIGHTS_EDGE_DIRECTION",
        "ST_Length(dc_shape.shape,1)/(ST_NPOINTS(dc_shape.shape)-1) AS WEIGHTS_VALUESPECIFIED"
    ],
    "restrictions": [],
    "options": {
        "merge_tolerance": "0.00001",
        "recreate": "true",
        "enable_graph_draw": "true",
        "graph_table": "dc_graph_inline_table"
    }
}
Response: {
    "num_nodes": 446491,
    "num_edges": 491462,
    "edges_ids": [],
    "info": {
        "status": "OK"
    }
}

Fit Using Expansion

Fitting road network data to a graph using expansion is more complex than using inline expressions but performs most of the calculations using the database instead of the graph server, making for a more efficient process. 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 start iteration, first the complex LINESTRINGs are divided into single edges by joining the dc_shape table and the ITER table in the /create/jointable endpoint, which is setup in this example with the following characteristics:

  • The existing dc_shape table will be joined to the ITER virtual table (table_names) and the results will be placed in a new dc_shape_expanded_lines view (join_table_name)
  • The direction and link_id columns will be copied from the dc_shape table to assist in graph creation later. A new WKT LINESTRING will be constructed from each consecutive pair of points in the source LINESTRINGs contained in the shape column from dc_shape (column_names)
  • An iteration expression to direct that each record’s WKT LINESTRING be iterated over, for each line segment contained in the overall LINESTRING (expressions)

To perform the expansion:

  1. In the API Tool, select /create/jointable from the Endpoint drop-down menu

  2. Copy the following JSON into the Request Mode text box:

    {
  "join_table_name": "dc_shape_expanded_lines",
  "table_names": [
    "dc_shape",
    "ITER"
  ],
  "column_names": [
    "dc_shape.direction as direction",
    "dc_shape.link_id as link_id",
    "st_makeLine(st_pointN(dc_shape.shape, ITER.i + 1), st_pointN(dc_shape.shape, ITER.i + 2)) as shape"
  ],
  "expressions": [
    "ITER.i < ST_NumPoints(dc_shape.shape)-1"
  ],
  "options": {}
}

  3. Click Send Request

The response field on the right-hand side of the page will be populated with the server response:

------------------------------------------------------------
Wed Jan 15 2020 18:06:02 GMT-0500 (Eastern Standard Time)
------------------------------------------------------------
Endpoint: /create/jointable
Time: 76
Request: {
    "join_table_name": "dc_shape_expanded_lines",
    "table_names": [
        "dc_shape",
        "ITER"
    ],
    "column_names": [
        "dc_shape.direction as direction",
        "dc_shape.link_id as link_id",
        "st_makeLine(st_pointN(dc_shape.shape, ITER.i + 1), st_pointN(dc_shape.shape, ITER.i + 2)) as shape"
    ],
    "expressions": [
        "ITER.i < ST_NumPoints(dc_shape.shape)-1"
    ],
    "options": {}
}
Response: {
    "join_table_name": "dc_shape_expanded_lines",
    "count": 491470,
    "info": {}
}

Next, a projection is used to eliminate the nullable property introduced with the join (since graphs cannot be created from columns with the nullable property) and to calculate the weight as distance:

  • The projection is created from the new join view (table_name)
  • The results of the projection are placed in a new table (projection_name)
  • The link_id and direction columns are copied from the join view as they are; the shape column has the nullable property that must be removed first before copying. The shape column is then used to calculate the distance while also removing the nullable property (column_names)
  • The projection is persisted (persist)

To create the projection:

  1. In the API Tool, select /create/projection from the Endpoint drop-down menu

  2. Copy the following JSON into the Request Mode text box:

    {
  "table_name": "dc_shape_expanded_lines",
  "projection_name": "dc_shape_expanded_with_distance",
  "column_names": [
    "link_id",
    "direction",
    "remove_nullable(shape) as shape",
    "remove_nullable(ST_Length(shape,1)) as distance"
  ],
  "options": {
    "persist": "true"
  }
}

  3. Click Send Request

The response field on the right-hand side of the page will be populated with the server response:

------------------------------------------------------------
Wed Jan 15 2020 18:07:04 GMT-0500 (Eastern Standard Time)
------------------------------------------------------------
Endpoint: /create/projection
Time: 4031
Request: {
    "table_name": "dc_shape_expanded_lines",
    "projection_name": "dc_shape_expanded_with_distance",
    "column_names": [
        "link_id",
        "direction",
        "remove_nullable(shape) as shape",
        "remove_nullable(ST_Length(shape,1)) as distance"
    ],
    "options": {
        "persist": "true"
    }
}
Response: {
    "projection_name": "dc_shape_expanded_with_distance",
    "info": {
        "is_replicated": "false",
        "reshard_count": "0",
        "retain_chunks": "false"
    }
}

Last, the dc_shape_iteration graph is created directly from the dc_shape_single_distance projection with no extra calculations necessary. The graph is created 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_expanded_with_distance table (EDGE_WKTLINE). The edge's directionality is derived from the direction column of the dc_shape_expanded_with_distance table (EDGE_DIRECTION). The link_id is provided as an easy way to link to the associated weights (EDGE_ID).
  • The weights are matched to the edges using the same link_id column (WEIGHTS_EDGE_ID) and the distance calculated earlier is used as the weight (WEIGHTS_VALUESPECIFIED).
  • 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 will be merged together (merge_tolerance)
    • The resulting graph's information will be placed into a table (graph_table) and an EDGE_WKTLINE column will be included so the graph can be visualized (enable_graph_draw)

To create the graph:

  1. In the API Tool, select /create/graph from the Endpoint drop-down menu

  2. Copy the following JSON into the Request Mode text box:

    {
  "graph_name": "dc_shape_expansion",
  "directed_graph": true,
  "nodes": [],
  "edges": [
    "dc_shape_expanded_with_distance.link_id AS EDGE_ID",
    "dc_shape_expanded_with_distance.shape AS EDGE_WKTLINE",
    "dc_shape_expanded_with_distance.direction AS EDGE_DIRECTION"
  ],
  "weights": [
    "dc_shape_expanded_with_distance.link_id AS WEIGHTS_EDGE_ID",
    "dc_shape_expanded_with_distance.distance AS WEIGHTS_VALUESPECIFIED"
  ],
  "restrictions": [],
  "options": {
    "merge_tolerance": "0.00001",
    "recreate": "true",
    "enable_graph_draw": "true",
    "graph_table": "dc_graph_expansion_table"
  }
}

  3. Click Send Request

The response field on the right-hand side of the page will be populated with the server response:

------------------------------------------------------------
Wed Jan 15 2020 18:09:30 GMT-0500 (Eastern Standard Time)
------------------------------------------------------------
Endpoint: /create/graph
Time: 16064
Request: {
    "graph_name": "dc_shape_expansion",
    "directed_graph": true,
    "nodes": [],
    "edges": [
        "dc_shape_expanded_with_distance.link_id AS EDGE_ID",
        "dc_shape_expanded_with_distance.shape AS EDGE_WKTLINE",
        "dc_shape_expanded_with_distance.direction AS EDGE_DIRECTION"
    ],
    "weights": [
        "dc_shape_expanded_with_distance.link_id AS WEIGHTS_EDGE_ID",
        "dc_shape_expanded_with_distance.distance AS WEIGHTS_VALUESPECIFIED"
    ],
    "restrictions": [],
    "options": {
        "merge_tolerance": "0.00001",
        "recreate": "true",
        "enable_graph_draw": "true",
        "graph_table": "dc_graph_expansion_table"
    }
}
Response: {
    "num_nodes": 446491,
    "num_edges": 491457,
    "edges_ids": [],
    "info": {
        "status": "OK"
    }
}

Tutorial via Terminal

Included below is the complete tutorial containing all the above requests and the necessary JSON files:

To run the complete sample, ensure the fit_data.sh and the JSON files are in the same directory; then switch to that directory and do the following:

./fit_data.sh <kinetica-host>
© Copyright 2020, Kinetica. Created using Sphinx.