GSoC'22: Detailed signature of the new function pgr_hawickCircuits to be added in pgRouting

[nitishchauhan0022]

Name of the function:

pgr_hawickCircuits( ): This algorithm solves the problem of detecting and enumerating circuits in graphs.It is capable of circuit enumeration in graphs with directed-arcs, multiple-arcs and self-arcs with a memory efficient and high-performance im-plementation. It is an extension of Johnson's Algorithm of finding all the elementary circuits of a directed graph. Detecting and enumerating circuits in graphs is of fundamental importance for analyzing graphs.

Main characteristics of the function:

• The algorithm implementation works for directed graph.
• The graph can be either weighted or unweighted.
• It enumerates the circuits in the linear order of vertex.
• Returns the distinct circuits present in the graph.
• It has a time complexity of O((V+E)(C+1)) where c = No. of Circuits

Variants:

• pgr_hawickCircuits()

pgr_hawickCirucits(Edges SQL)
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Parameters:

Parameter	Type	Description
Edges SQL	TEXT	Inner SQL query, as described below.

Inner Query:

Edges SQL: It should be an SQL query which should return a set of rows with the following columns:

Column	Type	Default	Description
id	ANY-INTEGER		Identifier of the edge
source	ANY-INTEGER		Identifier of the first end point vertex of the edge
target	ANY-INTEGER		Identifier of the second end point vertex of the edge
cost	ANY-NUMERICAL | | Weight of the edge (source, target). When negative: edge (source, target) does not exist on the graph.
reverse_cost	ANY-NUMERICAL | -1 | Weight of the edge (target, source). When negative: edge (target, source) does not exist on the graph.

Where: ANY-INTEGER = SMALLINT, INTEGER, BIGINT ANY-NUMERICAL = SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns:

Returns SET OF (seq, node)

Column	Type	Description
seq	INTEGER | Sequential value starting from 1
path_id	INTEGER | Id of the circuit starting from 1
path_seq	INTEGER | Relative postion in the path. Has value 0 for beginning of the path
start_vid	BIGINT	Identifier of the starting vertex of the circuit.
end_vid	BIGINT	Identifier of the ending vertex of the circuit.
node	BIGINT	Identifier of the node in the path from a vid to next vid.
edge	BIGINT | Identifier of the edge used to go from node to the next node in the path sequence. -1 for the last node of the path.
cost	FLOAT | Cost to traverse from node using edge to the next node in the path sequence.
agg_cost	FLOAT | Aggregate cost from start_v to node.