Detecting a cycle, within a path, when having bidirectional edges in SAP HANA Graph

[ajmaradiaga]

In this blog post, I show how you can detect if there is a cycle within a path returned by the K-shortest paths function in Graph script, why would you want to do this and how to handle it.

To create an edge in SAP HANA Graph, we define a relationship from a source vertex (S) to a target vertex (T). This will look like S -> T. There are scenarios where a connection from T to S is necessary as well. Even though it is not possible to define the edge previously created as bidirectional, it is possible to achieve this by creating an edge from T -> S. In essence, simulating a bidirectional edge.

Why do we need a bidirectional edge?

When mapping integration relationships we might need a bidirectional edge. We can have systems that integration with each other, sending/receiving data between them. For example, SAP Cloud Integration is able to create objects in SAP Ariba via the REST API. Also, SAP Cloud Integration is able to retrieve objects from SAP Ariba via the REST API. The creation/retrieval relationship is bidirectional.

Having bidirectional edges introduces a problem when retrieving the k_shortest_paths in a graph. Different from when using the shortest_path function, it is not possible to specify a direction when calling the k_shortest_paths function. Meaning that the k_shortest_path can return a path that include the first path from REST API -> SAP Cloud Integration and the next edge Cloud Integration going back to REST API, this creates a cycle and it might not be a desirable, depending on the scenario you are trying to solve.

How can I check if there is a cycle in a path and handle it?

When iterating through the edges in a path, there is a cycle if the vertices of a new edge have already been visited. In GraphScript, we can use a Multiset to keep track of the nodes included in the path and by checking if both vertices are included in the multiset, we know that there is a cycle.

A multiset is an unordered container, and there is no ordinal position to reference individual elements of a multiset. Furthermore, it is also possible to declare a nested multiset i.e. a container with an unordered collection of multisets.

The code below shows how a multiset is used to keep track of the vertices and only include in the out parameter (o_paths) the paths that have no cycles.

CREATE OR REPLACE PROCEDURE "MY_GRAPH_PROC"(

    IN i_startNode NVARCHAR(100),         -- the ID of the start node

    IN i_endNode NVARCHAR(100),         -- the ID of the end node

    IN i_k INT,         -- the ID of the end node

    IN direction NVARCHAR(10) DEFAULT 'ANY',

    OUT o_nodes "TT_NODES",

    OUT o_edges "TT_EDGES",

    OUT edge_attr NVARCHAR(5000),

    OUT o_paths "PATHS"

    )

LANGUAGE GRAPH READS SQL DATA AS

BEGIN



	GRAPH g = Graph("SCHEMA", "GRAPH");

	VERTEX v_s = Vertex(:g, :i_startNode);

	VERTEX v_t = Vertex(:g, :i_endNode);



        -------------------

        -- Shortest Path --

        -------------------

	WeightedPath<BIGINT> p = Shortest_Path(:g, :v_s, :v_t, :direction);

	

	SEQUENCE<VERTEX> sv = VERTICES(:p);

	SEQUENCE<EDGE> se = EDGES(:p);

	

	o_nodes = SELECT :v."ID", :v."NAME" FOREACH v IN Vertices(:p);

	

	FOREACH ed in EDGES(:p) WITH ORDINALITY AS edge_order {

		o_edges."EDGE_ORDER"[:edge_order] = :edge_order;

		o_edges."EDGE_KEY"[:edge_order] = :ed."ID";

        o_edges."SOURCE"[:edge_order] = :ed.NODE_SRC_ID;

        o_edges."RELATION"[:edge_order] = :ed.TYPE_ID;

        o_edges."TARGET"[:edge_order] = :ed.NODE_TGT_ID;

	}



    -- running top k shortest paths

    SEQUENCE<WeightedPath<BIGINT>> s_paths = K_Shortest_Paths(

        :g, :v_s, :v_t, :i_k);

    

    BIGINT number_of_paths = 0L;

    

    -- project result paths into a table

    BIGINT currentResultRow = 1L;

    

    FOREACH result_path IN (:s_paths) WITH ORDINALITY AS path_id {

    	MULTISET<NVARCHAR> nodes_in_path;

    	BOOLEAN cycle_in_path = FALSE;

    	

    	-- Check if there is a cycle in the path

    	FOREACH p_edge in EDGES(:result_path) {

    	

    		if(IS_EMPTY(:nodes_in_path)) {

    			-- Will enter only in the first iteration

    			nodes_in_path = {:p_edge.NODE_SRC_ID, :p_edge.NODE_TGT_ID};

    		} else {

    			

	    		if (:p_edge.NODE_SRC_ID in :nodes_in_path and :p_edge.NODE_TGT_ID  in :nodes_in_path){

	    			-- Both vertices are already in the multiset

	    			cycle_in_path = TRUE;

	    		}

		    	else { 

		    		-- Only add the target vertex

		    		nodes_in_path = :nodes_in_path UNION ALL {:p_edge.NODE_TGT_ID};

	    		}

    		}

    	}

    	

    	-- Add path to result set if there is no cycle

    	if (:cycle_in_path == FALSE){

	    	number_of_paths = :number_of_paths + 1L;

	        FOREACH path_edge in EDGES(:result_path) WITH ORDINALITY AS edge_order {

	            o_paths."PATH_ID"[:currentResultRow] = INTEGER(:path_id);

	            o_paths."PATH_LENGTH"[:currentResultRow] = Length(:result_path);

	            o_paths."PATH_WEIGHT"[:currentResultRow] = Weight(:result_path);

	            o_paths."EDGE_ID"[:currentResultRow] = :path_edge."ID";

	            o_paths."EDGE_ORDER"[:currentResultRow] = INTEGER(:edge_order);

	            edge_attr = :edge_attr  ||  :path_edge.NODE_SRC_ID || '-' || :path_edge."TYPE_ID" || '-' || :path_edge.NODE_TGT_ID || '. ';

	            currentResultRow = :currentResultRow + 1L;

	        }

        }

    }



END;

And there you go... I've covered how we can have "bidirectional edges" in SAP HANA graph, when they might be useful, a problem that might come up when using k_shortest_paths and how this can be handled if needed.

Note: The GraphScript cheat sheet (https://help.sap.com/viewer/11afa2e60a5f4192a381df30f94863f9/2021_01_QRC/en-US/53f791d0d2ce47918591a...) was very helpful when figuring out how to manipulate the different graph objects.