Use a double linked list for free nodes in stable_graph #415
Conversation
ABorgna
force-pushed
the
fix-extend_with_edges
branch
2 times, most recently
from
7a1054f
to
8fd81ba
Compare
Fixes a crash ocurring in stable_graph::extend_with_edges. The double linked list lets us fill any vacant node directly without having to add the previous free nodes in the list.
ABorgna
force-pushed
the
fix-extend_with_edges
branch
from
8fd81ba
to
da13938
Compare
|
hmm, if you don't mind the order in which nodes are reused possibly changing, you can use a singly-linked free list with constant-time insertion and removal: // using pointers instead of node indexes for easier writing
struct Node {
next: Option<Box<Node>>,
}
struct FreeList {
head: Option<Box<Node>>,
}
impl FreeList {
fn add_free_node(&mut self, node: Box<Node>) {
node.next = self.head.take();
self.head = Some(node);
}
fn remove_free_node(&mut self) -> Option<Box<Node>> {
let mut node = self.head.take()?;
self.head = node.next.take();
Some(node)
}
} |
|
Yes, but the problem is that Consider the test example: let mut gr = StableGraph::<_, _>::default();
let a = gr.add_node("a");
let b = gr.add_node("b");
let c = gr.add_node("c");
let _d = gr.add_node("d");
gr.remove_node(a);
gr.remove_node(b);
gr.remove_node(c);
gr.extend_with_edges(vec![(0, 3, ())]);Before calling the last method, the graph has a single node with index 3 and a free_node list That is where you have to do the O(n) singly linked list node removal, or use a doubly linked list. |
Ah, so you need the doubly-linked list since you're removing arbitrary nodes from the middle of the list. makes sense! |
|
Hi everyone @ABorgna @programmerjake @saolof @jkeljo @mtreinish @pnevyk @sebk @XVilka @jrraymond @jmcomets @waywardmonkeys @TheZalli Petgraph has seen an increase in activity and that's really nice. Long ago I created it. I'm sorry that I haven't been able to keep up with maintaining or managing releases. We've had maintainers step up and that has been great, and I think we need to talk about that again. We already have an organization but the designated maintainers (including me) don't seem to have so much time, which is a shame. This PR looks really good and clicking merge would be easy, but petgraph needs a little bit more: maintainers and making releases (there is no point in merging things if they don't eventually end up in a nice, working release). Petgraph needs ownership, not just someone that wants to help 🙂, that's what I see at least. I wouldn't mind signing up new maintainers, if @XVilka agrees. Thanks for reading. |
|
I'd be happy to sign up as a maintainer. |
|
I'm currently busy finishing my phd thesis so I can graduate, but I'd be happy to sign up as a maintainer as soon as that's done (i.e. I should have loads of free time in June). |
|
I really like this library and use it in my projects often, so I'd happily accept to become a maintainer. I might not always be regularly consistent with the time I spent on programming work, but I think I could do work and design for this library at times, even on bigger things. I don't have any organization experience about managing libraries like these, but if someone made a list of work I could work on that. |
|
That's great. We need to hear from @XVilka before continuing. I'll stress that I want this library to grow past me, and I don't want to be a speedbump for it (I'm a grumpy maintainer 🙂). If we can we should plan out if the next release is breaking or non-breaking, get unreleased changes released and then integrate new changes and get those released too. |
|
Of course I agree and would be happy to see more people here! Sorry for my
absence lately, but I am really short on time.
…On Wed, Apr 21, 2021, 05:33 bluss ***@***.***> wrote:
That's great. We need to hear from @XVilka <https://github.com/XVilka>
before continuing. I'll stress that I want this library to grow past me,
and I don't want to be a speedbump for it (I'm a grumpy maintainer 🙂).
If we can we should plan out if the next release is breaking or
non-breaking, get unreleased changes released and then integrate new
changes and get those released too.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#415 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AABRT7IV5TM2MUYZGK3GJG3TJXXKXANCNFSM43G5X35A>
.
|
|
This is what I had in mind for the next milestone: https://github.com/petgraph/petgraph/milestone/4 |
|
Great! I've invited @ABorgna and @TheZalli. I'm around but I don't intend to "assert ownership" for lack of a better word. I can't really plan and execute releases for petgraph right now -- so it should be open for maintainers that want to, to do that. I won't click merge here -- I encourage maintainers to work together and also feel personally empowered. Let me know who needs release (crates.io) powers or other upgraded powers. We can keep in mind that there is a petgraph organization and a petgraph repo - where you choose to spend time or care about is of course voluntary, it's just another level of managing access and I'm not really that good at it. If you need to contact me there is contact info in my profile (scarce) and I'm on #rust-sci:matrix.org and sometimes in the rust discords. |
|
Thank you! I'll start tackling the issue queue, and maybe later we can discuss what should go into the next release. @TheZalli do you want to check and merge my PR ? |
This is the first time I'm checking a PR, but looking over the commit I didn't see anything wrong. It's passed all checks and even the benchmark showed no big slowdown so I'll merge it. |
|
Thanks! You can of course ask me, if you want to have input on something 🙂 |
Fixes a crash occurring in `stable_graph::extend_with_edges`. The double linked list lets us fill any vacant node directly without having to add the previous free nodes in the list.
Fixes a crash occurring in `stable_graph::extend_with_edges`. The double linked list lets us fill any vacant node directly without having to add the previous free nodes in the list.
Fixes #412. The previous implementation of
extend_with_edgeswas copied directly fromgraphand misbehaved.In a stable graph the function may have to create nodes corresponding to previously-deleted indices.
To do that it has to remove the node from the free_node list, and doing that would have required traversing the list to find the previous node in the chain and modify the pointers.
Instead, I upgraded the free_node list to a doubly linked list using the unused "input edge" field in
node.next[1]for the backwards pointer, in addition to the existing forward pointer innode.next[0].This allows for removing nodes from the free_node list in constant time.
The drawback of this are the additional node indexing operation required each time we have to update the backwards pointer,
but I compared the benchmarks and saw no significant difference.
Benchmark comparison