| 1 | package main
|
| 2 |
|
| 3 | import (
|
| 4 | "gonum.org/v1/gonum/floats"
|
| 5 | "gonum.org/v1/gonum/graph"
|
| 6 | "gonum.org/v1/gonum/graph/path"
|
| 7 | "gonum.org/v1/gonum/graph/simple"
|
| 8 | )
|
| 9 |
|
| 10 | // Weighter evaluates the weight of a route
|
| 11 | // based on some criteria
|
| 12 | type Weighter func(Route) float64
|
| 13 |
|
| 14 | // ByDistance sets the weight of a route based on the
|
| 15 | // distance between two airports.
|
| 16 | func ByDistance() Weighter {
|
| 17 | return func(r Route) float64 {
|
| 18 | return GetDistance(r.from, r.to)
|
| 19 | }
|
| 20 | }
|
| 21 |
|
| 22 | func Load(airports AirportMap, routes []Route, weighters ...Weighter) graph.Graph {
|
| 23 | g := simple.NewWeightedDirectedGraph(0.0, 0.0)
|
| 24 | for _, airport := range airports {
|
| 25 | g.AddNode(airport)
|
| 26 | }
|
| 27 | for _, route := range routes {
|
| 28 | var values []float64
|
| 29 | for _, weighter := range weighters {
|
| 30 | values = append(values, weighter(route))
|
| 31 | }
|
| 32 | g.SetWeightedEdge(SetWeight(route, floats.Sum(values)))
|
| 33 | }
|
| 34 | return g
|
| 35 | }
|
| 36 |
|
| 37 | func Find(start, end Airport, g graph.Graph) Itinerary {
|
| 38 | shortest := path.DijkstraFrom(start, g)
|
| 39 | path, weight := shortest.To(end.ID())
|
| 40 | var airports []Airport
|
| 41 | for _, p := range path {
|
| 42 | airports = append(airports, p.(Airport))
|
| 43 | }
|
| 44 | return Itinerary{stops: airports, weight: weight}
|
| 45 | }
|