petgraph icon indicating copy to clipboard operation
petgraph copied to clipboard

Update source/target API

Open pnevyk opened this issue 6 years ago • 0 comments

Summary

Add functions update_source and update_target (names is a topic for discussion) on graph structures, each accepting an edge index and node index (new endpoint). It would allow to change endpoints of an edge in-place while keeping graph's indices stable.

Motivation

One can achieve this goal by removing the edge and adding it back with a different endpoint. But in my opinion, having these functions available would bring these little improvements in usability:

  • Modifying the endpoint in-place keeps indices in the graph stable. For the "remove + add" workaround this is not true. This is actually the reason why I "need" this. I think it enables some use cases.
  • If we consider updating endpoints of an edge as a common operation, providing the user with a direct API without any workarounds looks nice to me. The "remove + add" workaround requires also boilerplate like getting the edge's endpoint which user wants to keep the same, etc.
  • In-place modification should also bring some performance improvements, although benchmarks would be necessary to measure the impact.

Details

I would add the following functions to all (if it makes sense) graph structures:

// edge, new_endpoint -> old_endpoint
pub fn update_target(&mut self, e: EdgeIndex<Ix>, n: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>;
pub fn update_source(&mut self, e: EdgeIndex<Ix>, n: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>;

I already have an implementation for Graph struct with some tests. I am willing to implement it for other structs as well.

By the way, there is a short discussion about such API in #103

Let me know what you think!

pnevyk avatar Feb 19 '20 16:02 pnevyk