path: introduce an optimisation for function DijkstraFrom (proposal)

[juroland]

This commit is a first proposal to reduce unnecessary work due to the use of duplicated nodes in the priority queue. Better alternatives could be discussed. What do you think about this ?

If the distance is greater than the value stored in this distance node, then there already exist a better path to reach this node k. Indeed, the priority queue might contain several distanceNode for the same node k (each time it is updated), because this version of the Dijkstra algorithm does not use a decrease-key operation. Therefore, these distanceNodes should be discarded. Otherwise, the adjacent vertices of k could be traversed more than once in the for loop.

[juroland]

Yes, in this case, it is better to wait for more reviews.

I could rephrase my solution as a way to skip outdated distanceNodes from the priority queue. Another point is that the condition mid.dist < path.dist[k] should never be satisfied, because the value of path.dist[k] is updated when the corresponding distanceNode is pushed to the priority queue in the next for loop and that path.dist for the start vertex is initialized to 0 in newShortestFrom unlike the pseudo-code in the technical report.

[kortschak]

OK, thanks @vladimir-ch.

@juroland would you please add the comment noting the deviation from the paper and then this is OK to merge.

[kortschak]

Here are some actual data on the impact.

Using the following instrumentation:

diff --git a/path/dijkstra_test.go b/path/dijkstra_test.go
index 931a141..244aeda 100644
--- a/path/dijkstra_test.go
+++ b/path/dijkstra_test.go
@@ -5,17 +5,77 @@
 package path

 import (
+       "fmt"
        "math"
+       "os"
        "reflect"
        "sort"
        "testing"
+       "text/tabwriter"

        "github.com/gonum/graph"
        "github.com/gonum/graph/internal/ordered"
        "github.com/gonum/graph/path/internal/testgraphs"
+       "github.com/gonum/graph/simple"
 )

+type undirectNodeCount struct {
+       graph.Node
+       g *counterUndirected
+}
+
+func (n undirectNodeCount) ID() int {
+       n.g.nc++
+       return n.Node.ID()
+}
+
+type counterUndirected struct {
+       name string
+       *simple.UndirectedGraph
+
+       nc, fc, fn int
+}
+
+func (g *counterUndirected) From(n graph.Node) []graph.Node {
+       to := g.UndirectedGraph.From(n)
+       g.fc++
+       g.fn += len(to)
+       for i, n := range to {
+               to[i] = undirectNodeCount{Node: n, g: g}
+       }
+       return to
+}
+
+type directNodeCount struct {
+       graph.Node
+       g *counterDirected
+}
+
+func (n directNodeCount) ID() int {
+       n.g.nc++
+       return n.Node.ID()
+}
+
+type counterDirected struct {
+       name string
+       *simple.DirectedGraph
+
+       nc, fc, fn int
+}
+
+func (g *counterDirected) From(n graph.Node) []graph.Node {
+       to := g.DirectedGraph.From(n)
+       g.fc++
+       g.fn += len(to)
+       for i, n := range to {
+               to[i] = directNodeCount{Node: n, g: g}
+       }
+       return to
+}
+
 func TestDijkstraFrom(t *testing.T) {
+       tw := tabwriter.NewWriter(os.Stdout, 0, 8, 2, ' ', 0)
+       fmt.Fprintln(tw, "Test\tFrom calls\tFrom nodes returned\tNode ID calls")
        for _, test := range testgraphs.ShortestPathTests {
                g := test.Graph()
                for _, e := range test.Edges {
@@ -31,7 +91,24 @@ func TestDijkstraFrom(t *testing.T) {
                        defer func() {
                                panicked = recover() != nil
                        }()
-                       pt = DijkstraFrom(test.Query.From(), g.(graph.Graph))
+                       var cg graph.Graph
+                       switch g := g.(type) {
+                       case *simple.UndirectedGraph:
+                               cg = &counterUndirected{name: test.Name, UndirectedGraph: g}
+                       case *simple.DirectedGraph:
+                               cg = &counterDirected{name: test.Name, DirectedGraph: g}
+                       case graph.Graph:
+                               cg = g
+                       default:
+                               panic("not a graph")
+                       }
+                       pt = DijkstraFrom(test.Query.From(), cg)
+                       switch g := cg.(type) {
+                       case *counterUndirected:
+                               fmt.Fprintf(tw, "%s\t% 6d\t% 12d\t% 8d\n", g.name, g.fc, g.fn, g.nc)
+                       case *counterDirected:
+                               fmt.Fprintf(tw, "%s\t% 6d\t% 12d\t% 8d\n", g.name, g.fc, g.fn, g.nc)
+                       }
                }()
                if panicked || test.HasNegativeWeight {
                        if !test.HasNegativeWeight {
@@ -79,6 +156,7 @@ func TestDijkstraFrom(t *testing.T) {
                                test.Name, np, weight)
                }
        }
+       tw.Flush()
 }

 func TestDijkstraAllPaths(t *testing.T) {

Before optimisation:

Test                                                       From calls  From nodes returned  Node ID calls
empty directed                                                  0                 0                0
empty undirected                                                0                 0                0
one edge directed                                               2                 1                6
one edge self directed                                          2                 1                6
one edge undirected                                             2                 2                9
two paths directed                                              3                 3               15
two paths undirected                                            3                 6               24
confounding paths directed                                      7                 9               46
confounding paths undirected                                    7                19               76
confounding paths directed 2-step                               8                10               53
confounding paths undirected 2-step                             8                21               86
zero-weight cycle directed                                      6                 6               37
zero-weight cycle^2 directed                                    7                 8               47
zero-weight cycle^2 confounding directed                        7                 9               50
zero-weight cycle^3 directed                                    8                10               57
zero-weight 3·cycle^2 confounding directed                      8                13               66
zero-weight reversed 3·cycle^2 confounding directed             8                13               63
zero-weight |V|·cycle^(n/|V|) directed                        105               204             1026
zero-weight n·cycle directed                                  105               204             1027
zero-weight bi-directional tree with single exit directed      21                37              190

After optimisation:

Test                                                       From calls  From nodes returned  Node ID calls
empty directed                                                  0                 0                0
empty undirected                                                0                 0                0
one edge directed                                               2                 1                6
one edge self directed                                          2                 1                6
one edge undirected                                             2                 2                9
two paths directed                                              3                 3               15
two paths undirected                                            3                 6               24
confounding paths directed                                      6                 8               40
confounding paths undirected                                    6                16               64
confounding paths directed 2-step                               7                 9               47
confounding paths undirected 2-step                             7                18               74
zero-weight cycle directed                                      6                 6               37
zero-weight cycle^2 directed                                    7                 8               47
zero-weight cycle^2 confounding directed                        7                 9               50
zero-weight cycle^3 directed                                    8                10               57
zero-weight 3·cycle^2 confounding directed                      8                13               66
zero-weight reversed 3·cycle^2 confounding directed             8                13               63
zero-weight |V|·cycle^(n/|V|) directed                        105               204             1026
zero-weight n·cycle directed                                  105               204             1027
zero-weight bi-directional tree with single exit directed      21                37              190

[kortschak]

Thank you.