Skip to content
This repository was archived by the owner on Oct 8, 2021. It is now read-only.

Metaweight filters for shortest path routing on attributes #119

Open
FalafelGood opened this issue Jul 15, 2021 · 0 comments
Open

Metaweight filters for shortest path routing on attributes #119

FalafelGood opened this issue Jul 15, 2021 · 0 comments

Comments

@FalafelGood
Copy link

Hi, this is somewhat of a cross-post from MetaGraphsNext.jl, so please let me know if I'm being redundant / annoying.

I had this idea a couple days ago that I think would be really nice to implement. Here's a motivating example. Suppose we have
a large graph, and all the edges have the attribute :active. We want do routing on this graph, but only on the edges where :active == true. The naive implementation is to remove all the edges where :active == false, and put them back in after the path has been found, but this is not pretty nor efficient. The edges could have lots of metadata, or :active == true could be sparse within the graph, or maybe we just need to find a lot of paths. It would be much cleaner if there was a way to filter / modify weights based on attribute properties before they're sent off to a_star or whatever.

Here's my suggestion for implementing this:

  1. Add a new field to the MetaWeights struct filter::Function. This is a function that takes an edge, edge attributes, and a weightfield as arguments. By default, this function will just return the requested weight, but the user can write a custom function that will modify this weight conditional on whatever they want. In my example for instance, if :active == true, we return the normal weight, else return Inf.

  2. Modify getindex(w::MetaWeights{T,U}, u::Integer, v::Integer) such that the filter is applied before the weight is returned.

  3. Success? Now in principle all we need to do is write some nice API so the user can set filter to whatever they want and then restore it back to default when they're done.

Let me know what you all think! I'm keen to work on this further :-)

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

No branches or pull requests

1 participant