Add k-shortest-path

[antejavor]

Description

Implementation of a K-shortest path algorithm based on Yen K Shortest path implementation.

Correctness test so far:

MATCH (n) DETACH DELETE n; 
CREATE CONSTRAINT ON (n:Node) ASSERT n.id IS UNIQUE;
CREATE (:Node {id:1});
CREATE (:Node {id:2});
CREATE (:Node {id:3});
CREATE (:Node {id:4});
CREATE (:Node {id:5});
MATCH (n1:Node {id:1}), (n2:Node{id:2}) CREATE (n1)-[:REL {weight:1}]->(n2);
MATCH (n1:Node {id:1}), (n2:Node{id:3}) CREATE (n1)-[:REL {weight:4}]->(n2);
MATCH (n1:Node {id:1}), (n2:Node{id:4}) CREATE (n1)-[:REL {weight:4}]->(n2);
MATCH (n1:Node {id:2}), (n2:Node{id:3}) CREATE (n1)-[:REL {weight:1}]->(n2);
MATCH (n1:Node {id:3}), (n2:Node{id:4}) CREATE (n1)-[:REL {weight:2}]->(n2);
MATCH (n1:Node {id:3}), (n2:Node{id:5}) CREATE (n1)-[:REL {weight:2}]->(n2);
MATCH (n1:Node {id:4}), (n2:Node{id:5}) CREATE (n1)-[:REL {weight:2}]->(n2);
MATCH (n1:Node {id:1}), (n2:Node{id:5}) CREATE (n1)-[:REL {weight:3}]->(n2);

MATCH (startNode:Node{id:1}) 
WITH startNode
MATCH (endNode:Node{id:5})
WITH startNode, endNode
CALL shortest_path.k_weighted_shortest_paths(startNode, endNode, 5) YIELD paths RETURN paths
// CALL shortest_path.k_weighted_shortest_paths(startNode, endNode, 5, "weight") YIELD paths RETURN paths

Results:

(id: 171, :Node, properties: {id: 1})
(id: 175, :Node, properties: {id: 5})
Path: 3.000000

(id: 171, :Node, properties: {id: 1})
(id: 172, :Node, properties: {id: 2})
(id: 173, :Node, properties: {id: 3})
(id: 175, :Node, properties: {id: 5})
 Path: 4.000000

(id: 171, :Node, properties: {id: 1})
(id: 173, :Node, properties: {id: 3})
 (id: 175, :Node, properties: {id: 5})
 Path: 6.000000

 (id: 171, :Node, properties: {id: 1})
(id: 174, :Node, properties: {id: 4})
 (id: 175, :Node, properties: {id: 5})
 Path: 6.000000

(id: 171, :Node, properties: {id: 1})
 (id: 172, :Node, properties: {id: 2})
 (id: 173, :Node, properties: {id: 3})
 (id: 174, :Node, properties: {id: 4})
 (id: 175, :Node, properties: {id: 5})
 Path: 6.000000

TODO:

• [x] Return paths (not just nodes and weights)
• [ ] Test more scale
• [x] Test e2e

Pull request type

• [ ] Bugfix
• [x] Algorithm/Module
• [ ] Feature
• [ ] Code style update (formatting, renaming)
• [ ] Refactoring (no functional changes, no api changes)
• [ ] Build related changes
• [ ] Documentation content changes
• [ ] Other (please describe):

######################################

Reviewer checklist (the reviewer checks this part)

Module/Algorithm

• [ ] Core algorithm/module implementation
• [ ] Query module implementation
• [ ] Unit tests
• [ ] End-to-end tests
• [ ] Code documentation
• [ ] README short description
• [ ] Documentation on memgraph/docs
• [ ] Update GQLALchemy signatures in query builder using query module signature generator

######################################

[sonarcloud[bot]]

Quality Gate passed

The SonarCloud Quality Gate passed, but some issues were introduced.

4 New issues
0 Security Hotspots
No data about Coverage
0.0% Duplication on New Code

See analysis details on SonarCloud