Closed magnushiie closed 2 years ago
Thanks for PR, we'll take a deep look for sure.
First look (just opened diff
from mobile phone):
I'd suggest to not change signature of
func (graph *Graph) shortestPath(source, target int64) (float64, []int64) {
to
func (graph *Graph) shortestPath(sources, targets []vertexAlternativeInternal) (float64, []int64) {
Since you've added
func (graph *Graph) ShortestPathWithAlternatives(sources, targets []VertexAlternative)
I guess it would be better to have
func (graph *Graph) shortestPathWithAlternatives(sources, targets []vertexAlternativeInternal) (float64, []int64) {
and keep classic(-ish?) function untouched
Thanks for PR, we'll take a deep look for sure.
First look (just opened
diff
from mobile phone):I'd suggest to not change signature of
func (graph *Graph) shortestPath(source, target int64) (float64, []int64) {
to
func (graph *Graph) shortestPath(sources, targets []vertexAlternativeInternal) (float64, []int64) {
Since you've added
func (graph *Graph) ShortestPathWithAlternatives(sources, targets []VertexAlternative)
I guess it would be better to have
func (graph *Graph) shortestPathWithAlternatives(sources, targets []vertexAlternativeInternal) (float64, []int64) {
and keep classic(-ish?) function untouched
Do I understand correctly that you would like to copy the whole content of shortestPath
to shortestPathWithAlternatives
although it's only the initialization code that changes? Or would you prefer keeping the initialization code separate and refactoring the actual algorithm into a separate method?
It seems to me that terms distinction is good (breaking DRY principle though). I see that there are changes only before this line (initialization code) and straightforward copying forward/backward propagation code could bloat overall code base a lot.... So
Or would you prefer keeping the initialization code separate and refactoring the actual algorithm into a separate method?
could be best choice here (from my POV)
// some initialization code
// ...
// NEED TO WRAP SOMEHOW THIS PIECE OF CODE to call from both `shortestPath` and `shortestPathWithAlternatives`
for forwQ.Len() != 0 || backwQ.Len() != 0 {
// forward/backward propagation
}
//...
// exit fn
I've now changed it so the core algorithm is common but initialization code is separate. I've also rearranged the code a bit to make the diffs smaller. I hope this works for you.
With the latest commit I refactored the common initialization code also into a separate method. Let me know which one you prefer.
Merged
Good job on initial penalty
technique. We find it useful for our own tasks too
This change allows specifying multiple source and destination nodes. If source and/or target are not exactly on the graph nodes, this allows passing multiple close-by nodes with associated distance to them.