You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
The text was updated successfully, but these errors were encountered:
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.
The text was updated successfully, but these errors were encountered: