Calculate Shortest Path Using a GRAPH Procedure
- How to define the required Table Type for the database procedure
- How to create a GRAPH procedure for shortest path calculation
- How to use anonymous blocks approach for shortest path calculation
- You have already created a Graph Workspace using the tutorial First steps with the SAP HANA Graph Engine.
- You have access to the sample graph data used in this tutorial group.
- Make sure your database instance is running before you start.
Once you have defined a Graph Workspace, you can run
openCypher(*) queries for pattern matching workload or create GRAPH procedures for network analysis. In this tutorial you will learn how to create a database procedure that uses the built-in function to calculate a shortest path between two vertices. This includes three steps:
- Define the required Table Type for database procedure
- Create a GRAPH procedure for shortest path calculation
- Run a GRAPH code using anonymous blocks
- Step 1
If you are familiar with SAP HANA database procedures using
SQLScript, you already know how to handle table-like results. A clean way to do this is defining and using TABLE TYPES. The same approach is valid for GRAPH procedures. Our
TABLE TYPE TT_SPOO_EDGESdescribes the structure of the path result. It includes the
IDof the edge and the
ORDERin which the edges are traversed.
First you need to create a
TABLE TYPEthat describes the output table of the procedure, containing
length(DOUBLE). Execute this statement:SQLCopy
CREATE TYPE "TT_SPOO_EDGES" AS TABLE ( "ID" NVARCHAR(5000), "SOURCE" BIGINT, "TARGET" BIGINT, "EDGE_ORDER" BIGINT, "length" DOUBLE) ;
- Step 2
The GRAPH procedure has a similar structure to a
The header describes input and output variables, followed by the actual code.
The code below is a graph specific programming language called GRAPH. Instead of working with relational objects and operations like tables and SQL, GRAPH procedures operate on vertices and edges.
The core of this procedure is the call of the built-in graph algorithm:
WeightedPath<BIGINT> p = Shortest_Path(:g, :v_start, :v_end, :i_direction);
In this algorithm,
gis our graph,
v_endare the start/end vertices of the path we are searching, and
i_directionindicates the direction in which edges can be traversed (OUTGOING, INCOMING, or ANY). The result is assigned to a path object p.
This is the complete statement to create the procedure. Paste it to your SQL console and run it:SQLCopy
CREATE OR REPLACE PROCEDURE "GS_SPOO"( IN i_startVertex BIGINT, -- INPUT: the ID of the start vertex IN i_endVertex BIGINT, -- INPUT: the ID of the end vertex IN i_direction VARCHAR(10), -- INPUT: the direction of the edge traversal: OUTGOING (default), INCOMING, ANY OUT o_path_length BIGINT, -- OUTPUT: the hop distance between start and end OUT o_edges "TT_SPOO_EDGES" -- OUTPUT: a table containing the edges that make up a shortest path between start and end ) LANGUAGE GRAPH READS SQL DATA AS BEGIN -- Create an instance of the graph, referring to the graph workspace object GRAPH g_all = Graph("DAT260", "LONDON_GRAPH"); -- Using the IN_SCOPE attribute created in "Exercise 3 Identify Relevant Area for Transportation Network" to narrow down the search scope GRAPH g = SubGraph(:g_all, v IN Vertices(:g_all) WHERE :v."IN_SCOPE" == 1); -- Create an instance of the start/end vertex VERTEX v_start = Vertex(:g, :i_startVertex); VERTEX v_end = Vertex(:g, :i_endVertex); -- Runnning shortest path one-to-one based hop distance, i.e. the minimum number of edges between start and end WeightedPath<BIGINT> p = Shortest_Path(:g, :v_start, :v_end, :i_direction); o_path_length = LENGTH(:p); o_edges = SELECT :e."ID", :e."SOURCE", :e."TARGET", :EDGE_ORDER, :e."length" FOREACH e IN Edges(:p) WITH ORDINALITY AS EDGE_ORDER; END;
If you remember, we have used the
IN_SCOPEattribute created in tutorial 4 to focus on the relevant area. For this we “induced” a sub-graph by filtering the complete
The database procedure is executed like any other - using a CALL statement providing the input parameters. As we have assigned the POI data to nodes in the street network (in tutorial 6), we can now lookup the
VERTEX_OSMIDfor our start and end POI’s: Canary Wharf snaps to 1433737988, and Blues Kitchen to 1794145673.SQLCopy
-- Look up VERTEX_OSMID of POI Blues kitchen SELECT VERTEX_OSMID FROM "LONDON_POI" WHERE "name" = 'Blues Kitchen' AND "osmid" = 6274057185; CALL "GS_SPOO"(i_startVertex => 1433737988, i_endVertex => 1794145673, i_direction => 'ANY', o_path_length => ?, o_edges => ?); -- or in short CALL "GS_SPOO"(1433737988, 1794145673, 'ANY', ?, ?);
The result is a set of edges/street segments that make up the path. The
EDGE_ORDERvalue identifies the sequence. The procedure also returns
O_PATH_LENGTH = 464which is the number of minimal hops it takes from Canary Wharf to Blues Kitchen.
You can see the results here:
- Step 3
Sometimes it is more convenient to generate and execute the GRAPH code dynamically without creating a procedure in the database. This approach is called “anonymous blocks”. The code below is basically the same as in the procedure above, but this time it is executed in a DO - BEGIN - END block.SQLCopy
DO ( IN i_startVertex BIGINT => 14680080, IN i_endVertex BIGINT => 7251951621, OUT o_edges TABLE("ID" NVARCHAR(5000), "SOURCE" BIGINT, "TARGET" BIGINT, "EGDE_ORDER" BIGINT, "length" DOUBLE) => ? ) LANGUAGE GRAPH BEGIN GRAPH g = Graph("LONDON_GRAPH"); VERTEX v_start = Vertex(:g, :i_startVertex); VERTEX v_end = Vertex(:g, :i_endVertex); WeightedPath<BIGINT> p = Shortest_Path(:g, :v_start, :v_end, 'ANY'); o_edges = SELECT :e."ID", :e."SOURCE", :e."TARGET", :EDGE_ORDER, :e."length" FOREACH e IN Edges(:p) WITH ORDINALITY AS EDGE_ORDER; END;
You now have created a GRAPH procedure which calculates a hop distance shortest path between start and end vertex.
In the next tutorial, learn how to use a GRAPH Procedure to calculate Shortest Paths using a more complex cost function that minimizes the time it takes to get from start to end.
- Step 4