Graph Solvers with UI

End-to-End Graph Example Using the UI

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 Workbench Data Explorer and Workbook.

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 Workbench:

  1. Navigate to Workbench; see Connecting to the Kinetica Cloud Workbench.
  2. On the left side under the Data tab, click the + next to Tables & Views.
  3. Click Add New Schema input tutorial_graph as the name and click Create.
  4. In the top menu, click Import.
  5. Click File Upload.
  6. Create a new folder named graph_data and drag and drop or select the data file and click Upload.
  7. Under Step 2, leave the default options and values and click Next.
  8. Under Step 3, change Schema to tutorial_graph.
  9. Do not make any changes under Step 4.
  10. Click Import.

The file will be validated and records will be inserted.

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_shape dataset is a HERE dataset and is analogous to most road network datasets you could find in that it includes columns for the type of road, the average speed, the direction of the road, a WKT linestring for its geographic location, a unique ID integer for the road, and more. The graph used in the example is created with two columns from the dc_shape dataset:

  • shape -- a WKT linestring composed of points that make up various streets, roads, highways, alleyways, and footpaths throughout Washington, D.C.
  • direction -- 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

You'll notice later that the shape column is also part of an inline calculation for distance as weight during graph creation using the ST_LENGTH and ST_NPOINTS geospatial functions.

Graph Concepts

A graph typically comprises nodes, edges, weights, and 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, link ID 18350083 is a part of the Ward Circle roundabout, which itself is part of Massachusetts Avenue Northwest near American University. Selecting link ID 18350083 from the dc_shape table reveals the following WKT linestring (the end of the linestring was removed for clarity):

LINESTRING (-77.08544159 38.93787003, -77.08544159 38.93793869, -77.08545685 38.9380188, -77.08548737 38.9381218, ...)

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

  • Edge A - LINESTRING(-77.08544159 38.93787003, -77.08544159 38.93793869)
  • Edge B - LINESTRING(-77.08544159 38.93793869, -77.08545685 38.9380188)
  • Edge C - LINESTRING(-77.08545685 38.9380188, -77.08548737 38.9381218)

Weights in this graph, as mentioned previously, are an abstract cost (distance, time, etc.) for traveling 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 traveling 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 GUI

This tutorial is designed to be used with the Workbench Data Explorer and Workbook.

Create Schema

Before starting with graph creation, a schema, tutorial_graph_gui, will be created to contain the tables supporting graph creation & solving. To create the schema:

  1. On the left side under Data click the + next to Tables & Views.
  2. Click Add New Schema input tutorial_graph_gui as the name and click Create.

Create Graph

One graph is used for both graph solving examples in the tutorial: dc_shape_graph, a graph based on the aforementioned dc_shape dataset. To create the graph:

  1. On the left side under Data click the + next to Graphs.
  2. Input tutorial_graph_gui.dc_shape_graph for the Graph Name.
  3. Select True under Directed Graph. The graph is directed because the roads in the dataset have directionality (one-way and two-way roads)
  4. Skip selecting a configuration for Nodes. The graph will have no explicitly defined nodes because the example relies on implicit nodes attached to the defined edges.
  5. For Edges:
    1. Click the configuration drop-down menu and select EDGE_WKTLINE, EDGE_DIRECTION.
    2. Click Add.
    3. Input tutorial_graph.dc_shape.shape next to as EDGE_WKTLINE. The edges will be derived from the WKT LINESTRINGs in this column.
    4. Input tutorial_graph.dc_shape.direction next to as EDGE_DIRECTION. The edges' directionality will be derived from the integers in this column.
  6. For Weights:
    1. Click the configuration drop-down menu and select WEIGHTS_EDGE_WKTLINE, WEIGHTS_EDGE_DIRECTION, WEIGHTS_VALUE_SPECIFIED.
    2. Click Add.
    3. Input tutorial_graph.dc_shape.shape next to as WEIGHTS_EDGE_WKTLINE. This will match the weights to the edges by using the same WKTs.
    4. Input tutorial_graph.dc_shape.direction next to as WEIGHTS_EDGE_DIRECTION. This will match the weights to the edges' directionality.
    5. Input ST_Length(tutorial_graph.dc_shape.shape,1)/(ST_NPoints(tutorial_graph.dc_shape.shape)-1) next to as WEIGHTS_VALUESPECIFIED. The weights will be 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
  7. Skip selecting a configuration for Restrictions. The graph will have no restrictions on any nodes or edges.
  8. Click Next.
  9. For Options:
    1. Set the Merge Tolerance to 0.00001. This will merge nodes that are within one meter of each other.
    2. Set Recreate to True. This will recreate the graph if it already exists.
    3. Set Enable Graph Draw to True and input tutorial_graph_gui.dc_shape_graph_table for the Graph Table. This will create a table containing the graph information in addition to creating the graph.
  10. Click Create Graph.
  11. To view the graph click on tutorial_graph_gui.dc_shape_graph under Graphs in the left hand menu, and click Preview.

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 ballpark. What's the shortest path you could take to get to the ballpark?

Important

The source and destination points were selected from endpoints of edges within the graph.

  Source Destination
WKT POINT(-77.03511810000001 38.89876175) POINT(-77.00585175000001 38.87462997)
Location Description The corner of Madison Place Northwest and Pennsylvania Avenue Northwest The corner of N Street Southeast and Southeast 1st street
WMS Location ../img/tutorial_solve_sp/dc_roads_sp_source.png ../img/tutorial_solve_sp/dc_roads_sp_dest.png

To solve the graph for shortest path:

  1. On the left side of the screen, click on Workbooks.
  2. Click the + and select Add New Workbook.
  3. Name your new workbook dc_tutorial and click Create.
  4. Copy the following into the first block of your workbook:
    Solving for Shortest Path from White House to Ball Park
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    
    EXECUTE FUNCTION SOLVE_GRAPH(
        GRAPH => 'tutorial_graph_gui.dc_shape_graph',
        SOLVER_TYPE => 'SHORTEST_PATH',
        SOURCE_NODES => INPUT_TABLE(SELECT ST_GEOMFROMTEXT('POINT(-77.03511810000001 38.89876175)') AS WKTPOINT),
        DESTINATION_NODES => INPUT_TABLE(SELECT ST_GEOMFROMTEXT('POINT(-77.0058078 38.8746344)') AS WKTPOINT),
        SOLUTION_TABLE => 'tutorial_graph_gui.dc_shape_graph_solved_shortest_path',
        OPTIONS => KV_PAIRS(
            'export_solve_results' = 'true',
            'output_edge_path' = 'true'
        )
    )
    
  5. On the left hand menu under Data click on the newly created output table, dc_shape_graph_solved_shortest_path under tutorial_graph_gui.
  6. Click WMS Preview, and make sure the WKT Column is set to wktroute under Configuration.
  7. Keep everything else as is, and click Update.
  8. A WMS window will open, display the solution:
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 currently taking the subway to Union Station to visit Washington D.C. for the day. You 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.

  Source Destination Destination Destination Destination
WKT POINT(-77.00576019 38.89677811) POINT(-77.03517151 38.8898201) POINT(-77.03626251 38.88068008) POINT(-77.04974365 38.89020157) POINT(-77.01207733 38.89072037)
Location Description Union Station Near the Washington Monument Near the Jefferson Memorial Near the Lincoln Memorial Near Capitol Hill
WMS Location ../img/tutorial_solve_mr/dc_roads_mr_source.png ../img/tutorial_solve_mr/dc_roads_mr_dest_wm.png ../img/tutorial_solve_mr/dc_roads_mr_dest_jm.png ../img/tutorial_solve_mr/dc_roads_mr_dest_lm.png ../img/tutorial_solve_mr/dc_roads_mr_dest_ch.png

To solve the graph for shortest path:

  1. In the same workbook as the previous example, add a new SQL block by clicking the SQL button near the top of the screen.

  2. Copy the following into the new block:

    Solving for Quickest Path to Each Stop
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    
    EXECUTE FUNCTION SOLVE_GRAPH(
        GRAPH => 'tutorial_graph_gui.dc_shape_graph',
        SOLVER_TYPE => 'MULTIPLE_ROUTING',
        SOURCE_NODES => INPUT_TABLE(SELECT ST_GEOMFROMTEXT('POINT(-77.00576019 38.89677811)') AS WKTPOINT),
        DESTINATION_NODES => INPUT_TABLE(
            SELECT ST_GEOMFROMTEXT('POINT(-77.03517151 38.8898201)') AS WKTPOINT
            UNION
            SELECT ST_GEOMFROMTEXT('POINT(-77.03626251 38.88068008)')
            UNION
            SELECT ST_GEOMFROMTEXT('POINT(-77.04974365 38.89020157)')
            UNION
            SELECT ST_GEOMFROMTEXT('POINT(-77.01207733 38.89072037)')
        ),
        SOLUTION_TABLE => 'tutorial_graph_gui.dc_shape_graph_solved_multiple_routing',
        OPTIONS => KV_PAIRS(
            'export_solve_results' = 'true',
            'output_edge_path' = 'true'
        )
    ) 
    
  3. On the left hand menu under Data click on the newly created output table, dc_shape_graph_solved_multiple_routing, under the tutorial_graph_gui schema.

  4. Click WMS Preview, and make sure the WKT Column is set to wktroute under Configuration.

  5. Keep everything else as is, and click Update.

  6. A WMS window will open, display the solution:

dc_roads_graph_solved_multiple_routing.png