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.

Sign up for GitHub

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

graph/path: Improve performance of YenKShortestPaths #2004

Merged
merged 3 commits into from
Jan 14, 2025
Merged

graph/path: Improve performance of YenKShortestPaths #2004

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
7649851
graph/path: add single-pair shortest path variant
BarrensZeppelin Nov 27, 2024
f112007
graph/path: re-use test setup for `DijkstraFromTo` tests
BarrensZeppelin Dec 2, 2024
01905dd
Update graph/path/dijkstra.go
BarrensZeppelin Jan 14, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
27 changes: 26 additions & 1 deletion graph/path/dijkstra.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -20,8 +20,30 @@ import (
//
// The time complexity of DijkstraFrom is O(|E|.log|V|).
func DijkstraFrom(u graph.Node, g traverse.Graph) Shortest {
return dijkstraFrom(u, nil, g)
}

// DijkstraFromTo returns a shortest path from u to t in the graph g. The
// result is equivalent to DijkstraFrom(u, g).To(t.ID()), but DijkstraFromTo
// can be more efficient, as it can terminate early if t is reached. If the
// graph does not implement Weighted, UniformCost is used. DijkstraFromTo will
// panic if g has a u-reachable negative edge weight that is discovered before
// reaching t.
//
// The time complexity of DijkstraFromTo is O(|E|.log|V|).
func DijkstraFromTo(u, t graph.Node, g traverse.Graph) (path []graph.Node, weight float64) {
// An implementation of Bidirectional Dijkstra's algorithm could be even
// more efficient, but it requires a transposed (or undirected) graph.
if t == nil {
panic("dijkstra: nil target node")
}
return dijkstraFrom(u, t, g).To(t.ID())
}

func dijkstraFrom(u, t graph.Node, g traverse.Graph) Shortest {
var path Shortest
if h, ok := g.(graph.Graph); ok {
// Use the incremental version when a target is provided.
if h, ok := g.(graph.Graph); t == nil && ok {
if h.Node(u.ID()) == nil {
return Shortest{from: u}
}
Expand Down Expand Up @@ -58,6 +80,9 @@ func DijkstraFrom(u graph.Node, g traverse.Graph) Shortest {
continue
}
mnid := mid.node.ID()
if t != nil && mnid == t.ID() {
break
}
to := g.From(mnid)
for to.Next() {
v := to.Node()
Expand Down
12 changes: 7 additions & 5 deletions graph/path/dijkstra_test.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -27,9 +27,11 @@ func TestDijkstraFrom(t *testing.T) {
for _, tg := range []struct {
typ string
g traverse.Graph
t graph.Node
}{
{"complete", g.(graph.Graph)},
{"incremental", incremental{g.(graph.Weighted)}},
{"complete", g.(graph.Graph), nil},
{"incremental", incremental{g.(graph.Weighted)}, nil},
{"single-destination", g.(graph.Graph), test.Query.To()},
} {
var (
pt Shortest
Expand All @@ -40,13 +42,13 @@ func TestDijkstraFrom(t *testing.T) {
defer func() {
panicked = recover() != nil
}()
pt = DijkstraFrom(test.Query.From(), tg.g)
pt = dijkstraFrom(test.Query.From(), tg.t, tg.g)
}()
if panicked || test.HasNegativeWeight {
if !test.HasNegativeWeight {
t.Errorf("%q %s: unexpected panic", test.Name, tg.typ)
}
if !panicked {
if !panicked && tg.t == nil {
t.Errorf("%q %s: expected panic for negative edge weight", test.Name, tg.typ)
}
continue
Expand All @@ -62,7 +64,7 @@ func TestDijkstraFrom(t *testing.T) {
test.Name, tg.typ, weight, test.Weight)
}
if weight := pt.WeightTo(test.Query.To().ID()); weight != test.Weight {
t.Errorf("%q %s: unexpected weight from Weight: got:%f want:%f",
t.Errorf("%q %s: unexpected weight from WeightTo: got:%f want:%f",
test.Name, tg.typ, weight, test.Weight)
}

Expand Down
4 changes: 2 additions & 2 deletions graph/path/yen_ksp.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -33,7 +33,7 @@ func YenKShortestPaths(g graph.Graph, k int, cost float64, s, t graph.Node) [][]
yk.weight = UniformCost(g)
}

shortest, weight := DijkstraFrom(s, yk).To(t.ID())
shortest, weight := DijkstraFromTo(s, t, yk)
cost += weight // Set cost to absolute cost limit.
switch len(shortest) {
case 0:
Expand Down Expand Up @@ -73,7 +73,7 @@ func YenKShortestPaths(g graph.Graph, k int, cost float64, s, t graph.Node) [][]
yk.removeNode(u.ID())
}

spath, weight := DijkstraFrom(spur, yk).To(t.ID())
spath, weight := DijkstraFromTo(spur, t, yk)
if weight > cost || math.IsInf(weight, 1) {
continue
}
Expand Down
Loading