8000 Add k-shortest-path by antejavor · Pull Request #435 · memgraph/mage · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Add k-shortest-path #435

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Draft
wants to merge 12 commits into
base: main
Choose a base branch
from
Draft

Add k-shortest-path #435

wants to merge 12 commits into from

Conversation

antejavor
Copy link
Contributor
@antejavor antejavor commented Dec 18, 2023 •
edited
Loading

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:

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

Pull request type

  • Bugfix
  • 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

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

gitbuda
gitbuda reviewed Jan 2, 2024
View reviewed changes
@sonarqubecloud SonarQubeCloud
Copy link

Quality Gate Passed 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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@gitbuda gitbuda gitbuda left review comments

At least 1 approving review is required to merge this pull request.

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@antejavor @gitbuda @MarkoBarisic
0