Randomized iteration order for `PyGraph.neighbors`

[adamglos92]

Information

• rustworkx version: 0.17.1
• Python version: 3.12.11
• Rust version: (I believe it is not installed as I'm only using python version)
• Operating system: Linux aarch64 (devcontainer in macOS arm64)

What is the current behavior?

For a fixed graph I'm getting neighbors in random order.

What is the expected behavior?

Arbitrary, but fixed order

Judging on implementation, set is the problem (but I'm no Rust expert)

    pub fn neighbors(&self, node: usize) -> NodeIndices {
        NodeIndices {
            nodes: self
                .graph
                .neighbors(NodeIndex::new(node))
                .map(|node| node.index())
                .collect::<HashSet<usize>>()
                .drain()
                .collect(),
        }
    }

Steps to reproduce the problem

import rustworkx.generators as gen

for _ in range(3):
    g = gen.path_graph(5)
    print(g.neighbors(2))

[IvanIsCoding]

That is correct. Currently, the behaviour would be analogous to a set data structure in Python. Although we return NodeIndices.

We can possibly use indexmap::IndexSet to return a deterministic result that preserves insertion order. I’ll need to confirm that petgraph is detereministic first, of course.

In the meantime, sorted(g.neighbors(node)) is the most reliable solution. Node indices are integers, so you can always sort them if you need determinism.