search

Qiskit / rustworkx

A high performance Python graph library implemented in Rust.
https://www.rustworkx.org
Apache License 2.0
1.03k stars 145 forks source link

Shortest Path Panic #1117

Closed ryandeng1 closed 5 months ago

ryandeng1 commented 6 months ago

Information

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 https://github.com/Qiskit/rustworkx/blob/eb896fbd88c8bd086379cd2d46b2a1f74981bc9e/rustworkx-core/src/distancemap.rs#L52 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
IvanIsCoding commented 6 months ago

The code is panicking when accessing the scores for the shortest path but the culprit is probably this: https://github.com/Qiskit/rustworkx/blob/eb896fbd88c8bd086379cd2d46b2a1f74981bc9e/rustworkx-core/src/shortest_path/dijkstra.rs#L115C28-L115C33

Maybe the subgraph does not have the current .node_bound() set? We'll investigate more and try to release a fix in 0.14.2 if possible.

IvanIsCoding commented 6 months ago

Ok I think get why you are getting a panic. The good news is there is no bug in rustworkx and that the code is working as intended. However, you will need to rewrite your code.

Here is a short snippet to reproduce the same error message you posted:

import rustworkx as rx
graph = rx.generators.generalized_petersen_graph(5, 2)
sub_nodes = [6, 7, 8, 9, 5]
subg = graph.subgraph(sub_nodes)

#  This works, subgraph generates new node indices
paths = rx.dijkstra_shortest_paths(subg, 0)

# This panics like reported
paths_fail = rx.dijkstra_shortest_paths(subg, sub_nodes[0])

Subgraph generates new node indices, hence you need to account for that in your code. You should not call shortest path functions with the old node indices.

The fix from our side will be to add a more clear error message so you get an Exception and not a panic crashing your program.

IvanIsCoding commented 5 months ago

Closed by #1134. Once the backport #1135 merges I plan to release 0.14.2