Shortest Path Panic #1117
Description
Information
- rustworkx version: 0.14.1
- Python version: 3.10
- Rust version: I only installed the package via pip.
- Operating system: 22.04
What is the current behavior?
I see a panic when running rustworkx.dijkstra_shortest_paths and rustworkx.dijkstra_shortest_path_lengths on a graph produced by PyGraph.subgraph. The subgraphs are quite small, hundreds of nodes while the main graph is 100k nodes.
Running on the larger graph seems to work fine. I think it may be due to the fact that the node ids remain the same as the one in the original graph, but they might be accessed in a way that goes out of bounds in the subgraph?
What is the expected behavior?
Steps to reproduce the problem
Pseudocode:
networkx_graph = ...
rustworkx_graph = rustworkx.networkx_converter(networkx_graph)
nodes = ...
subgraph = rustworkx_graph.subgraph(nodes)
distances = rustworkx.dijkstra_shortest_paths(subgraph, start_node, as_undirected=True)
The error occurs on
according to what is outputted.thread '<unnamed>' panicked at /project/rustworkx-core/src/distancemap.rs:52:13:
index out of bounds: the len is 44 but the index is 56
stack backtrace:
0: 0x7fb1c2fbba43 - std::backtrace_rs::backtrace::libunwind::trace::hbee8a7973eeb6c93
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/../../backtrace/src/backtrace/libunwind.rs:104:5
1: 0x7fb1c2fbba43 - std::backtrace_rs::backtrace::trace_unsynchronized::hc8ac75eea3aa6899
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
2: 0x7fb1c2fbba43 - std::sys_common::backtrace::_print_fmt::hc7f3e3b5298b1083
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:68:5
3: 0x7fb1c2fbba43 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::hbb235daedd7c6190
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:44:22
4: 0x7fb1c2f52ff0 - core::fmt::rt::Argument::fmt::h76c38a80d925a410
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/fmt/rt.rs:142:9
5: 0x7fb1c2f52ff0 - core::fmt::write::h3ed6aeaa977c8e45
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/fmt/mod.rs:1120:17
6: 0x7fb1c2f904a2 - std::io::Write::write_fmt::h78b18af5775fedb5
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/io/mod.rs:1810:15
7: 0x7fb1c2fbd47e - std::sys_common::backtrace::_print::h5d645a07e0fcfdbb
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:47:5
8: 0x7fb1c2fbd47e - std::sys_common::backtrace::print::h85035a511aafe7a8
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:34:9
9: 0x7fb1c2fbcc00 - std::panicking::default_hook::{{closure}}::hcce8cea212785a25
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:272:22
10: 0x7fb1c2fbddcc - std::panicking::default_hook::hf5fcb0f213fe709a
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:292:9
11: 0x7fb1c2fbddcc - std::panicking::rust_panic_with_hook::h095fccf1dc9379ee
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:779:13
12: 0x7fb1c2fbd7d0 - std::panicking::begin_panic_handler::{{closure}}::h032ba12139b353db
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:657:13
13: 0x7fb1c2fbd726 - std::sys_common::backtrace::__rust_end_short_backtrace::h9259bc2ff8fd0f76
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:171:18
14: 0x7fb1c2fbd71f - rust_begin_unwind
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:645:5
15: 0x7fb1c2d10284 - core::panicking::panic_fmt::h784f20a50eaab275
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/panicking.rs:72:14
16: 0x7fb1c2d10381 - core::panicking::panic_bounds_check::h8331054858f0bf20
at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/panicking.rs:208:5
17: 0x7fb1c2f0ca7a - rustworkx::shortest_path::digraph_dijkstra_shortest_paths::ha7dce4b91e598024
18: 0x7fb1c2f0d482 - rustworkx::shortest_path::_::__pyfunction_digraph_dijkstra_shortest_paths::hd33b5947a3fd21ae
19: 0x7fb1c2d6845a - pyo3::impl_::trampoline::trampoline::hbc7ae91ab10773cc
20: 0x7fb1c2f0d0d0 - rustworkx::shortest_path::_::<impl rustworkx::shortest_path::digraph_dijkstra_shortest_paths::MakeDef>::DEF::trampoline::hb057ea6b3e3fe3b4
21: 0x555d328182a3 - cfunction_vectorcall_FASTCALL_KEYWORDS
at /usr/local/src/conda/python-3.10.12/Objects/methodobject.c:446:24
22: 0x555d3282ce8c - PyVectorcall_Call
at /usr/local/src/conda/python-3.10.12/Objects/call.c:267:24
23: 0x555d3282ce8c - _PyObject_Call
at /usr/local/src/conda/python-3.10.12/Objects/call.c:290:16
24: 0x555d3282ce8c - PyObject_Call
at /usr/local/src/conda/python-3.10.12/Objects/call.c:317:12
25: 0x555d3281634b - do_call_core
at /usr/local/src/conda/python-3.10.12/Python/ceval.c:5917:9
26: 0x555d3281634b - _PyEval_EvalFrameDefault
at /usr/local/src/conda/python-3.10.12/Python/ceval.c:4277:22
27: 0x555d3282099c - _PyEval_EvalFrame
at /usr/local/src/conda/python-3.10.12/Include/internal/pycore_ceval.h:46:12
28: 0x555d3282099c - _PyEval_Vector
at /usr/local/src/conda/python-3.10.12/Python/ceval.c:5067:24
29: 0x555d3282099c - _PyFunction_Vectorcall
at /usr/local/src/conda/python-3.10.12/Objects/call.c:342:16
30: 0x555d328118fa - _PyObject_VectorcallTstate
at /usr/local/src/conda/python-3.10.12/Include/cpython/abstract.h:114:11
31: 0x555d328118fa - PyObject_Vectorcall
at /usr/local/src/conda/python-3.10.12/Include/cpython/abstract.h:123:12
32: 0x555d328118fa - call_function
at /usr/local/src/conda/python-3.10.12/Python/ceval.c:5893:13
33: 0x555d328118fa - _PyEval_EvalFrameDefault
at /usr/local/src/conda/python-3.10.12/Python/ceval.c:4231:19
34: 0x555d3282099c - _PyEval_EvalFrame
at /usr/local/src/conda/python-3.10.12/Include/internal/pycore_ceval.h:46:12
35: 0x555d3282099c - _PyEval_Vector
at /usr/local/src/conda/python-3.10.12/Python/ceval.c:5067:24
36: 0x555d3282099c - _PyFunction_Vectorcall
at /usr/local/src/conda/python-3.10.12/Objects/call.c:342:16
37: 0x555d32815142 - _PyObject_VectorcallTstate
at /usr/local/src/conda/python-3.10.12/Include/cpython/abstract.h:114:11
38: 0x555d32815142 - PyObject_Vectorcall
at /usr/local/src/conda/python-3.10.12/Include/cpython/abstract.h:123:12
39: 0x555d32815142 - call_function
at /usr/local/src/conda/python-3.10.12/Python/ceval.c:5893:13
40: 0x555d32815142 - _PyEval_EvalFrameDefault
at /usr/local/src/conda/python-3.10.12/Python/ceval.c:4181:23
41: 0x555d328b3f90 - _PyEval_EvalFrame
at /usr/local/src/conda/python-3.10.12/Include/internal/pycore_ceval.h:46:12
42: 0x555d328b3f90 - _PyEval_Vector
at /usr/local/src/conda/python-3.10.12/Python/ceval.c:5067:24
43: 0x555d328b3ed7 - PyEval_EvalCode
at /usr/local/src/conda/python-3.10.12/Python/ceval.c:1134:12
44: 0x555d328e442a - run_eval_code_obj
at /usr/local/src/conda/python-3.10.12/Python/pythonrun.c:1291:9
45: 0x555d328df833 - run_mod
at /usr/local/src/conda/python-3.10.12/Python/pythonrun.c:1312:19
46: 0x555d327766cd - pyrun_file
at /usr/local/src/conda/python-3.10.12/Python/pythonrun.c:1208:15
47: 0x555d328d9d1e - _PyRun_SimpleFileObject
at /usr/local/src/conda/python-3.10.12/Python/pythonrun.c:456:13
48: 0x555d328d98b4 - _PyRun_AnyFileObject
at /usr/local/src/conda/python-3.10.12/Python/pythonrun.c:90:15
49: 0x555d328d6aab - pymain_run_file_obj
at /usr/local/src/conda/python-3.10.12/Modules/main.c:357:15
50: 0x555d328d6aab - pymain_run_file
at /usr/local/src/conda/python-3.10.12/Modules/main.c:376:15
51: 0x555d328d6aab - pymain_run_python
at /usr/local/src/conda/python-3.10.12/Modules/main.c:591:21
52: 0x555d328d6aab - Py_RunMain
at /usr/local/src/conda/python-3.10.12/Modules/main.c:670:5
53: 0x555d328a7527 - Py_BytesMain
at /usr/local/src/conda/python-3.10.12/Modules/main.c:1090:12
54: 0x7fb31ea09d90 - __libc_start_call_main
at ./csu/../sysdeps/nptl/libc_start_call_main.h:58:16
55: 0x7fb31ea09e40 - __libc_start_main_impl
at ./csu/../csu/libc-start.c:392:3
56: 0x555d328a7421 - <unknown>
Traceback (most recent call last):
File "/home/gridsan/rdeng/gt/main_ogb.py", line 49, in <module>
sampler.get_sampled_edge_idxs_rust(nx_graph, rx_graph, num_random_walks, random_walk_length, NUM_HEADS, train_idxs)
File "/home/gridsan/rdeng/gt/sampler.py", line 31, in get_sampled_edge_idxs_rust
distances = rustworkx.dijkstra_shortest_paths(subgraph, start_node, as_undirected=True)
File "/state/partition1/llgrid/pkg/anaconda/python-LLM-2023b/lib/python3.10/functools.py", line 889, in wrapper
return dispatch(args[0].__class__)(*args, **kw)
pyo3_runtime.PanicException: index out of bounds: the len is 44 but the index is 56