Skip to content
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.

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

Program hangs with a large (>2200) edge set #42

Open
GeneL opened this issue Jun 6, 2024 · 2 comments
Open

Program hangs with a large (>2200) edge set #42

GeneL opened this issue Jun 6, 2024 · 2 comments

Comments

@GeneL
Copy link

GeneL commented Jun 6, 2024

Your library works great for me when I use a set of edges with under 2200 records. When I try it with a larger set of edges the application hangs.. Is there a way to configure the app for a larger data set? Is there a different commands or function calls to use a larger data set?
Thank you in advance.

Below is my source code:

let mut input_graph = InputGraph::new();
let json = read_json_file("disc.json".to_string());
let mut cnt = 1;
for l1 in json.unwrap().len() {
if cnt < 2200 {
println!(" s: {:?} t: {:?}", l1["source"].as_u64().unwrap(), l1["target"].as_u64().unwrap());
input_graph.add_edge(l1["source"].as_u64().unwrap() as NodeId, l1["target"].as_u64().unwrap() as NodeId, 12);
}
cnt += 1;
}
input_graph.freeze();
let fast_graph = fast_paths::prepare(&input_graph);
let shortest_path = fast_paths::calc_path(&fast_graph, 388, 99);
println!("{:?}", shortest_path.clone().unwrap());

@GeneL
Copy link
Author

GeneL commented Jun 7, 2024

CORRECTION!
The program did not freeze, it just took much longer to execute.
This is the timing I got on Windows 10:

Elapsed time to load edges 2199 : 1.55ms
Elapsed time to freeze: 2.00ms
Elapsed time to prepare: 235.42ms
Elapsed time to get path: 235.87ms
ShortestPath { source: 388, target: 99, weight: 72, nodes: [388, 392, 428, 879, 888, 889, 99] }

Elapsed time to load edges 2499 : 1.59ms
Elapsed time to freeze: 2.07ms
Elapsed time to prepare: 3.52s
Elapsed time to get path: 3.52s
ShortestPath { source: 388, target: 99, weight: 72, nodes: [388, 392, 428, 879, 888, 889, 99] }

Elapsed time to load edges 2999 : 1.58ms
Elapsed time to freeze: 2.10ms
Elapsed time to prepare: 50.74s
Elapsed time to get path: 50.74s
ShortestPath { source: 388, target: 99, weight: 36, nodes: [388, 392, 393, 99] }

Elapsed time to load edges 3499 : 1.62ms
Elapsed time to freeze: 2.22ms
Elapsed time to prepare: 274.39s
Elapsed time to get path: 274.39s
ShortestPath { source: 388, target: 99, weight: 36, nodes: [388, 387, 398, 99] }

Elapsed time to load edges 3540 : 1.59ms
Elapsed time to freeze: 2.13ms
Elapsed time to prepare: 267.99s
Elapsed time to get path: 267.99s
ShortestPath { source: 388, target: 99, weight: 36, nodes: [388, 387, 393, 99] }

Is this normal to see such a time difference with addition of a few hundred edges?
Are there ways to speed the preparation up?

@dabreegster
Copy link
Contributor

During preparation, the library emits progress updates via log. If you install something like https://crates.io/crates/env_logger in your app, then you'll see them -- it can be helpful, but also maybe too verbose

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants