[VOL-1386] This commit add "dep" as the package management tool
for voltha-go.
Change-Id: I52bc4911dd00a441756ec7c30f46d45091f3f90e
diff --git a/vendor/github.com/gyuho/goraph/shortest_path.go b/vendor/github.com/gyuho/goraph/shortest_path.go
new file mode 100644
index 0000000..e6f405c
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/shortest_path.go
@@ -0,0 +1,348 @@
+package goraph
+
+import (
+ "container/heap"
+ "fmt"
+ "math"
+)
+
+// Dijkstra returns the shortest path using Dijkstra
+// algorithm with a min-priority queue. This algorithm
+// does not work with negative weight edges.
+// (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
+//
+// 0. Dijkstra(G, source, target)
+// 1.
+// 2. let Q be a priority queue
+// 3. distance[source] = 0
+// 4.
+// 5. for each vertex v in G:
+// 6.
+// 7. if v ≠ source:
+// 8. distance[v] = ∞
+// 9. prev[v] = undefined
+// 10.
+// 11. Q.add_with_priority(v, distance[v])
+// 12.
+// 13. while Q is not empty:
+// 14.
+// 15. u = Q.extract_min()
+// 16. if u == target:
+// 17. break
+// 18.
+// 19. for each child vertex v of u:
+// 20.
+// 21. alt = distance[u] + weight(u, v)
+// 22. if distance[v] > alt:
+// 23. distance[v] = alt
+// 24. prev[v] = u
+// 25. Q.decrease_priority(v, alt)
+// 26.
+// 27. reheapify(Q)
+// 28.
+// 29.
+// 30. path = []
+// 31. u = target
+// 32. while prev[u] is defined:
+// 33. path.push_front(u)
+// 34. u = prev[u]
+// 35.
+// 36. return path, prev
+//
+func Dijkstra(g Graph, source, target ID) ([]ID, map[ID]float64, error) {
+ // let Q be a priority queue
+ minHeap := &nodeDistanceHeap{}
+
+ // distance[source] = 0
+ distance := make(map[ID]float64)
+ distance[source] = 0.0
+
+ // for each vertex v in G:
+ for id := range g.GetNodes() {
+ // if v ≠ source:
+ if id != source {
+ // distance[v] = ∞
+ distance[id] = math.MaxFloat64
+
+ // prev[v] = undefined
+ // prev[v] = ""
+ }
+
+ // Q.add_with_priority(v, distance[v])
+ nds := nodeDistance{}
+ nds.id = id
+ nds.distance = distance[id]
+
+ heap.Push(minHeap, nds)
+ }
+
+ heap.Init(minHeap)
+ prev := make(map[ID]ID)
+
+ // while Q is not empty:
+ for minHeap.Len() != 0 {
+
+ // u = Q.extract_min()
+ u := heap.Pop(minHeap).(nodeDistance)
+
+ // if u == target:
+ if u.id == target {
+ break
+ }
+
+ // for each child vertex v of u:
+ cmap, err := g.GetTargets(u.id)
+ if err != nil {
+ return nil, nil, err
+ }
+ for v := range cmap {
+
+ // alt = distance[u] + weight(u, v)
+ weight, err := g.GetWeight(u.id, v)
+ if err != nil {
+ return nil, nil, err
+ }
+ alt := distance[u.id] + weight
+
+ // if distance[v] > alt:
+ if distance[v] > alt {
+
+ // distance[v] = alt
+ distance[v] = alt
+
+ // prev[v] = u
+ prev[v] = u.id
+
+ // Q.decrease_priority(v, alt)
+ minHeap.updateDistance(v, alt)
+ }
+ }
+ heap.Init(minHeap)
+ }
+
+ // path = []
+ path := []ID{}
+
+ // u = target
+ u := target
+
+ // while prev[u] is defined:
+ for {
+ if _, ok := prev[u]; !ok {
+ break
+ }
+ // path.push_front(u)
+ temp := make([]ID, len(path)+1)
+ temp[0] = u
+ copy(temp[1:], path)
+ path = temp
+
+ // u = prev[u]
+ u = prev[u]
+ }
+
+ // add the source
+ temp := make([]ID, len(path)+1)
+ temp[0] = source
+ copy(temp[1:], path)
+ path = temp
+
+ return path, distance, nil
+}
+
+// BellmanFord returns the shortest path using Bellman-Ford algorithm
+// This algorithm works with negative weight edges.
+// Time complexity is O(|V||E|).
+// (http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf)
+// It returns error when there is a negative-weight cycle.
+// A negatively-weighted cycle adds up to infinite negative-weight.
+//
+// 0. BellmanFord(G, source, target)
+// 1.
+// 2. distance[source] = 0
+// 3.
+// 4. for each vertex v in G:
+// 5.
+// 6. if v ≠ source:
+// 7. distance[v] = ∞
+// 8. prev[v] = undefined
+// 9.
+// 10.
+// 11. for 1 to |V|-1:
+// 12.
+// 13. for every edge (u, v):
+// 14.
+// 15. alt = distance[u] + weight(u, v)
+// 16. if distance[v] > alt:
+// 17. distance[v] = alt
+// 18. prev[v] = u
+// 19.
+// 20.
+// 21. for every edge (u, v):
+// 22.
+// 23. alt = distance[u] + weight(u, v)
+// 24. if distance[v] > alt:
+// 25. there is a negative-weight cycle
+// 26.
+// 27.
+// 28. path = []
+// 29. u = target
+// 30. while prev[u] is defined:
+// 31. path.push_front(u)
+// 32. u = prev[u]
+// 33.
+// 34. return path, prev
+//
+func BellmanFord(g Graph, source, target ID) ([]ID, map[ID]float64, error) {
+ // distance[source] = 0
+ distance := make(map[ID]float64)
+ distance[source] = 0.0
+
+ // for each vertex v in G:
+ for id := range g.GetNodes() {
+
+ // if v ≠ source:
+ if id != source {
+ // distance[v] = ∞
+ distance[id] = math.MaxFloat64
+
+ // prev[v] = undefined
+ // prev[v] = ""
+ }
+ }
+
+ prev := make(map[ID]ID)
+
+ // for 1 to |V|-1:
+ for i := 1; i <= g.GetNodeCount()-1; i++ {
+
+ // for every edge (u, v):
+ for id := range g.GetNodes() {
+
+ cmap, err := g.GetTargets(id)
+ if err != nil {
+ return nil, nil, err
+ }
+ u := id
+ for v := range cmap {
+ // edge (u, v)
+ weight, err := g.GetWeight(u, v)
+ if err != nil {
+ return nil, nil, err
+ }
+
+ // alt = distance[u] + weight(u, v)
+ alt := distance[u] + weight
+
+ // if distance[v] > alt:
+ if distance[v] > alt {
+ // distance[v] = alt
+ distance[v] = alt
+
+ // prev[v] = u
+ prev[v] = u
+ }
+ }
+
+ pmap, err := g.GetSources(id)
+ if err != nil {
+ return nil, nil, err
+ }
+ v := id
+ for u := range pmap {
+ // edge (u, v)
+ weight, err := g.GetWeight(u, v)
+ if err != nil {
+ return nil, nil, err
+ }
+
+ // alt = distance[u] + weight(u, v)
+ alt := distance[u] + weight
+
+ // if distance[v] > alt:
+ if distance[v] > alt {
+ // distance[v] = alt
+ distance[v] = alt
+
+ // prev[v] = u
+ prev[v] = u
+ }
+ }
+ }
+ }
+
+ // for every edge (u, v):
+ for id := range g.GetNodes() {
+
+ cmap, err := g.GetTargets(id)
+ if err != nil {
+ return nil, nil, err
+ }
+ u := id
+ for v := range cmap {
+ // edge (u, v)
+ weight, err := g.GetWeight(u, v)
+ if err != nil {
+ return nil, nil, err
+ }
+
+ // alt = distance[u] + weight(u, v)
+ alt := distance[u] + weight
+
+ // if distance[v] > alt:
+ if distance[v] > alt {
+ return nil, nil, fmt.Errorf("there is a negative-weight cycle: %v", g)
+ }
+ }
+
+ pmap, err := g.GetSources(id)
+ if err != nil {
+ return nil, nil, err
+ }
+ v := id
+ for u := range pmap {
+ // edge (u, v)
+ weight, err := g.GetWeight(u, v)
+ if err != nil {
+ return nil, nil, err
+ }
+
+ // alt = distance[u] + weight(u, v)
+ alt := distance[u] + weight
+
+ // if distance[v] > alt:
+ if distance[v] > alt {
+ return nil, nil, fmt.Errorf("there is a negative-weight cycle: %v", g)
+ }
+ }
+ }
+
+ // path = []
+ path := []ID{}
+
+ // u = target
+ u := target
+
+ // while prev[u] is defined:
+ for {
+ if _, ok := prev[u]; !ok {
+ break
+ }
+ // path.push_front(u)
+ temp := make([]ID, len(path)+1)
+ temp[0] = u
+ copy(temp[1:], path)
+ path = temp
+
+ // u = prev[u]
+ u = prev[u]
+ }
+
+ // add the source
+ temp := make([]ID, len(path)+1)
+ temp[0] = source
+ copy(temp[1:], path)
+ path = temp
+
+ return path, distance, nil
+}