Version:

Network Graphs & Solvers REST Tutorial (DC)

The following guide provides step-by-step instructions to get started with using the Network Graphs & Solvers in Kinetica. This guide demonstrates some key graph concepts as well as how to create and solve a graph using the Kinetica REST API. Note that this tutorial primarily uses GAdmin to ingest necessary data and to run the REST commands.

Prerequisites

Data File

The tutorial makes use of the dc_roads 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.

Key Information and Concepts

After the data file has been ingested into Kinetica, you should learn about the dataset and how it relates to the Network Graphs Solvers.

Data

The dc_roads dataset is a modified OpenStreetMap (OSM) dataset. Because OSM datasets are open source, they are not necessarily the most accurate representation of a city's road network. For the purposes of this example however, the dataset will be perfect for conveying the core concepts of creating and solving graphs. The dataset used in this example is analogous to most road network datasets you could find in that it includes columns for the type of road, the name of the road, the max speed, whether the road is a bridge or tunnel, a WKT linestring for its geographic location, a unique ID integer for the road, and much more.

The graph used in the example is created with three columns from the dc_roads dataset:

  • wkt -- a WKT linestring composed of points that make up various streets, roads, highways, alleyways, and footpaths throughout Washington, D.C.
  • oneway -- an integer column that conveys information about the directionality of the road, with forward meaning the direction in which the way is drawn in OSM and backward being the opposite direction:
    • 0 -- a forward one-way road
    • 1 -- a two-way road
    • 2 -- a backward one-way road
  • weight -- a "cost" to travelling the associated road. In this example, weight is reflected as the length of the WKT linestring (in meters) divided by the speed of the overall road type. The road type is derived from the fclass column in the dataset. The speed limits assigned for each road type:
    • For motorways, it is assumed the speed limit is 50 miles per hour (88513.9 meters per hour)
    • For primary, secondary, and tertiary roads, it is assumed the speed limit is 25 miles per hour (40233.6 meters per hour)
    • For alleyways, it is assumed the speed limit is 15 miles per hour (24140.2 meters per hour)
    • For all other roads, it is assumed the speed limit is 25 miles per hour (40233.6 meters per hour)

Tip

Consult the OSM wiki for more information on the Washington, D.C., map.

Graph Concepts

A graph typically comprises Nodes, Edges, Weights, Restrictions but only requires edges and weights. The graph created in this tutorial only uses edges and weights.

In this particular example, edges are logically mapped to sections of roadways and footpaths throughout the Washington, D.C., area. Each edge corresponds to a consecutive pair of points from each of the source LINESTRINGs, so a LINESTRING containing n points will have n-1 edges. Because the source graph is not created with nodes, implicit nodes are assigned at either end of each edge after graph creation.

For example, Feature ID 19456 is a two-way road behind the White House, part of the larger "Pennsylvania Avenue Northwest" road. Selecting Feature ID 19456 from the dc_roads table reveals the following WKT linestring (the end of the linestring was removed for clarity):

LINESTRING (-77.035127 38.8987825, -77.0353806 38.898782, -77.0356898 38.8987813, -77.0364333 38.8987798, ...)

As noted above, each consecutive pair of coordinates will correspond to an edge in the graph, e.g.:

  • Edge A - LINESTRING(-77.035127 38.8987825, -77.0353806 38.898782)
  • Edge B - LINESTRING(-77.0353806 38.898782, -77.0356898 38.8987813)
  • Edge C - LINESTRING(-77.0356898 38.8987813, -77.0364333 38.8987798)

Tip

After graph creation, you can view each edge's details, including its respective WKT linestring, using WMS and clicking an edge:

../../_images/edge_wms.png

Each coordinate pair composing an edge is an implicit node:

../../_images/edge_wms_nodes.png

Weights in this graph, as mentioned previously, are an abstract cost for travelling any roadway or footpath in the Washington, D.C., area. Weights are particularly important when solving a graph. There are two solver types presented in the tutorial below:

  • shortest_path -- Find the shortest path between two points on a graph
  • multiple_routing -- Find the quickest route between a source point and many destination points; also known as travelling salesman

Because there are no explicit nodes in the tutorial graph, source and destination point(s) must be selected from any of the edges comprising the Washington, D.C., road network. Otherwise, the graph will not be able to traverse to the point and will result in a null solution.

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:

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

Create Graph

One graph is used for both solve graph examples later in the tutorial: dc_roads_graph, a graph based on the aforementioned dc_roads dataset. The dc_roads_graph 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 WKT column of the dc_roads table (EDGE_WKTLINE). Each road segment's directionality is derived from the oneway column of the dc_roads table (EDGE_DIRECTION).
  • The weights are represented using the cost to travel the segment found in the weight column of the dc_roads table (WEIGHTS_VALUESPECIFIED). The weights are matched to the edges using the same WKT column as edges (WEIGHTS_EDGE_WKTLINE) and the same oneway column as the edge direction (WEIGHTS_EDGE_DIRECTION).
  • It has no inherent restrictions for any of the nodes or edges in the graph
  • It will be replaced with this instance of the graph if a graph of the same name exists (recreate)

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_roads_graph",
      "directed_graph": true,
      "nodes": [],
      "edges": [
        "dc_roads.WKT AS EDGE_WKTLINE",
        "dc_roads.oneway AS EDGE_DIRECTION"
      ],
      "weights": [
        "dc_roads.WKT AS WEIGHTS_EDGE_WKTLINE",
        "dc_roads.oneway AS WEIGHTS_EDGE_DIRECTION",
        "dc_roads.weight AS WEIGHTS_VALUESPECIFIED"
      ],
      "restrictions": [],
      "options": {
        "recreate": "true",
        "enable_graph_draw": "true",
        "graph_table": "dc_roads_graph_table"
      }
    }
    
  3. Click Send Request

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

------------------------------------------------------------
Thu Oct 03 2019 11:20:45 GMT-0400 (Eastern Daylight Time)
------------------------------------------------------------
Endpoint: /create/graph
Time: 3449
Request: {
    "graph_name": "dc_roads_graph",
    "directed_graph": true,
    "nodes": [],
    "edges": [
        "dc_roads.WKT AS EDGE_WKTLINE",
        "dc_roads.oneway AS EDGE_DIRECTION"
    ],
    "weights": [
        "dc_roads.WKT AS WEIGHTS_EDGE_WKTLINE",
        "dc_roads.oneway AS WEIGHTS_EDGE_DIRECTION",
        "dc_roads.weight AS WEIGHTS_VALUESPECIFIED"
    ],
    "restrictions": [],
    "options": {
        "recreate": "true",
        "enable_graph_draw": "true",
        "graph_table": "dc_roads_graph_table"
    }
}
Response: {
    "num_nodes": 123019,
    "num_edges": 145186,
    "edges_ids": [],
    "info": {
        "status": "OK"
    }
}

Solve the Graph (Shortest Path)

The following scenario has been designed to illustrate a shortest path solution:

You work near the White House, and after you get off work, you'd like to attend a baseball game at the nearby ball park. What's the shortest path you could take to get to the ball park?

Important

The source and destination points were selected from endpoints of edges within the graph. The easiest way to review the points that make up an edge is using the WMS tool on the graph table (dc_roads_graph_table).

Source / Destination Source Destination
WKT POINT(-77.0353806 38.898782) POINT(-77.0058078 38.8746344)
Location Description The corner of Madison Place Northwest and Pennsylvania Avenue Northwest The corner of N Street Southeast and Southeast 1st street
WMS Location ../../_images/dc_roads_sp_source.png ../../_images/dc_roads_sp_dest.png

To generate the solution:

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

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

    {
      "graph_name": "dc_roads_graph",
      "weights_on_edges": [],
      "restrictions": [],
      "solver_type": "shortest_path",
      "source_nodes": ["POINT(-77.0353806 38.898782)"],
      "destination_nodes": ["POINT(-77.0058078 38.8746344)"],
      "solution_table": "dc_roads_graph_solved_shortest_path",
      "options": {}
    }
    

    Note

    Because the tutorial graph was created using WKT linestrings, the /solve/graph call provides the source and destination points as WKT points. The source and destination node ID fields are left as 0.

  3. Click Send Request

The solution output to WMS:

../../_images/dc_roads_graph_solved_shortest_path.png

Solve the Graph (Multiple Routing)

The following scenario has been designed to illustrate a multiple routing solution:

You're taking the subway to Union Station and would like to see some of the most iconic monuments and buildings in Washington, D.C. before returning back to Union Station. Starting from Union Station, what's the quickest route between each stop before returning back to Union Station?

Important

The source and destination points were selected from endpoints of edges within the graph. The easiest way to review the points that make up an edge is using the WMS tool on the graph table (dc_roads_graph_table).

Source / Destination Source Destination Destination Destination Destination
WKT POINT(-77.00561399999999 38.8966211) POINT(-77.0394895 38.8889164) POINT(-77.0358775 38.8798738) POINT(-77.0503923 38.890192) POINT(-77.01215809999999 38.8905465)
Location Description Union Station Near the Washington Monument Near the Jefferson Memorial Near the Lincoln Memorial Near Capitol Hill
WMS Location ../../_images/dc_roads_mr_source.png ../../_images/dc_roads_mr_dest_wm.png ../../_images/dc_roads_mr_dest_jm.png ../../_images/dc_roads_mr_dest_lm.png ../../_images/dc_roads_mr_dest_ch.png

To generate the solution:

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

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

    {
      "graph_name": "dc_roads_graph",
      "weights_on_edges": [],
      "restrictions": [],
      "solver_type": "multiple_routing",
      "source_nodes": ["POINT(-77.00561399999999 38.8966211)"],
      "destination_nodes": [
        "POINT(-77.0394895 38.8889164)",
        "POINT(-77.0358775 38.8798738)",
        "POINT(-77.0503923 38.890192)",
        "POINT(-77.01215809999999 38.8905465)"
      ],
      "solution_table": "dc_roads_graph_solved_multiple_routing",
      "options": {}
    }
    

    Note

    Because the tutorial graph was created using WKT linestrings, the /solve/graph call provides the source and destination points as WKT points. The source and destination node ID fields are left as 0.

  3. Click Send Request

The solution output to WMS:

../../_images/dc_roads_graph_solved_multiple_routing.png

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 graphs_rest.sh and the JSON files are in the same directory; then switch to that directory and do the following:

./graphs_rest.sh <kinetica-host>