Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allow disabling edges for one single algo computation #158

Open
UnasZole opened this issue Feb 22, 2025 · 0 comments
Open

Allow disabling edges for one single algo computation #158

UnasZole opened this issue Feb 22, 2025 · 0 comments

Comments

@UnasZole
Copy link

Today, the API separates the definition of the graph itself (vertices and edges) from the weights, and the weighting function is passed as argument whenever we call an algorithm. 

This is great, because it allows having a single instance of a large graph in memory, and use it in several contexts.

It would be great to have a similar solution to apply "perturbations" (minor alterations) to the graph for the sake of one algo computation.

Typically, if I have a large graph representing a wide network, and I want to compute the impact of cutting a few connections (ie. Removing a few edges), today as far as I can tell the only reliable solution is to build a completely separate copy of the graph with these edges removed. 

Functionally, another way of thinking about it could be to use a weight function that sets a weight of "+infinity" to these edges, and then exclude paths with an infinite cost from the results - but it's not very efficient.

One possibility could be the extend the WeightFunction interface with a "boolean isDisabled(E)" method (with a default implementation returning false to preserve backwards compatibility with current weight functions).

And then each algo could call this method to decide if an edge can be used in the current computation.

I'm not sure how much of a performance and design impact it may have on your current algorithms though, so I'll understand if this is not desired - but if approved, it could help users of large graphs to optimise such "perturbation" use cases to avoid copies and use less memory.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant