SAP HANA, graph options – part 2

In this blog we will learn further about built-in Graph functionalities supported in SAP HANA, graph options.

To review what are graphs and how do we create graphs in SAP HANA kindly refer to SAP HANA, graph options – part 1

Below are the graph functions supported.

1. Neighbourhood Search – This function is used to get neighbouring vertices from the input vertex with a given radius.
2. Shortest Path (One-to-all) – This function, also known as Single Source Shortest path,  provides shortest path from given vertex to all vertices in the graph. The resulting shortest paths form a tree structure.
3. Shortest Path (One-to-One) – This is a variant of the Shortest Path(One-to-all) which provides shortest path between a start vertex and a target vertex.
4. Strongly Connected Components – A directed graph is strongly connected if every vertex is reachable from every other vertex.

Now, we will look at scripts for each one of the above stated functionalities.

First we define Graph.

In the below code snippet we define reference vertex, edge tables and graph workspace object.

DROP SCHEMA "GRAPHOPTION" CASCADE;
CREATE SCHEMA "GRAPHOPTION";
CREATE COLUMN TABLE "GRAPHOPTION"."NODES" (
	"ID" BIGINT PRIMARY KEY
);
CREATE COLUMN TABLE "GRAPHOPTION"."EDGES" (
	"ID" BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
	"SOURCE" BIGINT REFERENCES "GRAPHOPTION"."NODES"("ID") ON DELETE CASCADE NOT NULL,
	"TARGET" BIGINT REFERENCES "GRAPHOPTION"."NODES"("ID") ON DELETE CASCADE NOT NULL,
	"WEIGHT" DOUBLE
);
INSERT INTO "GRAPHOPTION"."NODES" VALUES (1);
INSERT INTO "GRAPHOPTION"."NODES" VALUES (2);
INSERT INTO "GRAPHOPTION"."NODES" VALUES (3);
INSERT INTO "GRAPHOPTION"."NODES" VALUES (4);
INSERT INTO "GRAPHOPTION"."NODES" VALUES (5);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (1, 2, 0.5);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (1, 3, 0.1);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (2, 3, 1.5);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (2, 4, 0.1);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (3, 4, 0.2);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (5, 4, 0.8);

CREATE GRAPH WORKSPACE "GRAPHOPTION"."GRAPHWS"
	EDGE TABLE "GRAPHOPTION"."EDGES"
		SOURCE COLUMN "SOURCE"
		TARGET COLUMN "TARGET"
		KEY COLUMN "ID"
	VERTEX TABLE "GRAPHOPTION"."NODES" 
		KEY COLUMN "ID";

Now, we will look at sample implementations of custom graph functions provided in SAP HANA, graph options mentioned above.

• Neighbourhood Search

CREATE TYPE "GRAPHOPTION"."TT_NODES_NEI" AS TABLE ("ID" BIGINT); -- Table type for getting neighbour output for target vertices ids from input source vertex.
CREATE TYPE "GRAPHOPTION"."TT_EDGES_NEI" AS TABLE ("ID" BIGINT, "SOURCE" BIGINT, "TARGET" BIGINT);- Table type for getting neighbour output for edges that form the neighburhood.
CREATE OR REPLACE PROCEDURE "GRAPHOPTION"."GS_NEIGHBORS"(
	IN i_startNode BIGINT, 		-- the ID of the start node
	IN i_min BIGINT, 			-- the minimum hop distance 
	IN i_max BIGINT, 			-- the maximum hop distance
	OUT o_nodes "GRAPHOPTION"."TT_NODES_NEI",
	OUT o_nodesCount BIGINT,
	OUT o_edges "GRAPHOPTION"."TT_EDGES_NEI"
	)
LANGUAGE GRAPH READS SQL DATA AS
BEGIN
	-- create an instance of the graph, refering to the graph workspace object
	GRAPH g = Graph("GRAPHOPTION", "GRAPHWS");
	-- create an instance of the start node
	VERTEX v_start = Vertex(:g, :i_startNode);
	-- create a multiset of all neighbor nodes of the start node
	MULTISET<Vertex> m_neighbors = Neighbors(:g, :v_start, :i_min, :i_max);
	-- project the result from the multiset
	o_nodes = SELECT :v."ID" FOREACH v IN :m_neighbors;
	o_nodesCount = COUNT(:m_neighbors);
	-- create a vertex induced subgraph to get all edges between the nodes in the neighbors multiset
	GRAPH g_sub = SubGraph(:g, :m_neighbors);
	o_edges = SELECT :e."ID", :e."SOURCE", :e."TARGET" FOREACH e IN Edges(:g_sub);
END;

CALL "GRAPHOPTION"."GS_NEIGHBORS"(i_startNode => 1, i_min => 0, i_max => 1000, o_nodes => ?, o_nodesCount => ?, o_edges => ?);

• Shortest Path One-to-All

  /*************************************/
  -- Shortest Paths One to All procedure
  CREATE TYPE "GRAPHOPTION"."TT_NODES_SPOA" AS TABLE ("ID" BIGINT, "CALCULATED_COST" DOUBLE);
  CREATE TYPE "GRAPHOPTION"."TT_EDGES_SPOA" AS TABLE ("ID" BIGINT, "SOURCE" BIGINT, "TARGET" BIGINT, "WEIGHT" DOUBLE);
  
  CREATE OR REPLACE PROCEDURE "GRAPHOPTION"."GS_SPOA"(
  	IN i_startNode BIGINT, 		-- the ID of the start node
  	OUT o_nodes "GRAPHOPTION"."TT_NODES_SPOA", 
  	OUT o_edges "GRAPHOPTION"."TT_EDGES_SPOA"
  	)
  LANGUAGE GRAPH READS SQL DATA AS
  BEGIN
  	-- create an instance of the graph, refering to the graph workspace object
  	GRAPH g = Graph("GRAPHOPTION", "GRAPHWS");
  	-- create an instance of the start node
  	VERTEX v_start = Vertex(:g, :i_startNode);
  	-- running shortest paths one to all, which returns a subgraph. The WEIGHT based path length to a node is stored in the attribute CALCULATED_COST
  	GRAPH g_spoa = SHORTEST_PATHS_ONE_TO_ALL(:g, :v_start, "CALCULATED_COST", (Edge e) => DOUBLE{ return :e."WEIGHT"; });
  	o_nodes = SELECT :v."ID", :v."CALCULATED_COST" FOREACH v IN Vertices(:g_spoa);
  	o_edges = SELECT :e."ID", :e."SOURCE", :e."TARGET", :e."WEIGHT" FOREACH e IN Edges(:g_spoa);
  END;
  
  CALL "GRAPHOPTION"."GS_SPOA"(i_startNode => 1, o_nodes => ?, o_edges => ?);​

• Shortest path One-to-One

/*************************************/
-- Shortest Path One to One procedure
CREATE TYPE "GRAPHOPTION"."TT_NODES_SPOO" AS TABLE ("ID" BIGINT);
CREATE TYPE "GRAPHOPTION"."TT_EDGES_SPOO" AS TABLE ("ID" BIGINT, "SOURCE" BIGINT, "TARGET" BIGINT);

CREATE OR REPLACE PROCEDURE "GRAPHOPTION"."GS_SPOO"(
	IN i_startNode BIGINT, 		-- the ID of the start node
	IN i_endNode BIGINT, 		-- the ID of the end node
	OUT o_path_length BIGINT,	-- the hop distance between start and end
	OUT o_path_weight DOUBLE,	-- the path weight/cost based on the WEIGHT attribute
	OUT o_nodes "GRAPHOPTION"."TT_NODES_SPOO",
	OUT o_edges "GRAPHOPTION"."TT_EDGES_SPOO"
	)
LANGUAGE GRAPH READS SQL DATA AS
BEGIN
	-- create an instance of the graph, refering to the graph workspace object
	GRAPH g = Graph("GRAPHOPTION", "GRAPHWS");
	-- create an instance of the start/end node
	VERTEX v_start = Vertex(:g, :i_startNode);
	VERTEX v_end = Vertex(:g, :i_endNode);
	-- running shortest path using the WEIGHT column as cost
	WeightedPath<DOUBLE> p = Shortest_Path(:g, :v_start, :v_end, (Edge e) => DOUBLE{ return :e."WEIGHT"; });
	-- project the results from the path
	o_path_length = LENGTH(:p);
	o_path_weight = WEIGHT(:p);
	o_nodes = SELECT :v."ID" FOREACH v IN Vertices(:p);
	o_edges = SELECT :e."ID", :e."SOURCE", :e."TARGET" FOREACH e IN Edges(:p);
END;

CALL "GRAPHOPTION"."GS_SPOO"(i_startNode => 1, i_endNode => 4, o_path_length => ?, o_path_weight => ?, o_nodes => ?, o_edges => ?);

And that’s the out-of-the-box algorithms for SAP HANA, graph options.

In the next article we will check out some custom algorithms with Graphs.