[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/minimum_spanning_tree.go b/vendor/github.com/gyuho/goraph/minimum_spanning_tree.go
new file mode 100644
index 0000000..a86e279
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/minimum_spanning_tree.go
@@ -0,0 +1,287 @@
+package goraph
+
+import (
+ "container/heap"
+ "math"
+ "sort"
+)
+
+// Kruskal finds the minimum spanning tree with disjoint-set data structure.
+// (http://en.wikipedia.org/wiki/Kruskal%27s_algorithm)
+//
+// 0. Kruskal(G)
+// 1.
+// 2. A = ∅
+// 3.
+// 4. for each vertex v in G:
+// 5. MakeDisjointSet(v)
+// 6.
+// 7. edges = get all edges
+// 8. sort edges in ascending order of weight
+// 9.
+// 10. for each edge (u, v) in edges:
+// 11. if FindSet(u) ≠ FindSet(v):
+// 12. A = A ∪ {(u, v)}
+// 13. Union(u, v)
+// 14.
+// 15. return A
+//
+func Kruskal(g Graph) (map[Edge]struct{}, error) {
+
+ // A = ∅
+ A := make(map[Edge]struct{})
+
+ // disjointSet maps a member Node to a represent.
+ // (https://en.wikipedia.org/wiki/Disjoint-set_data_structure)
+ forests := NewForests()
+
+ // for each vertex v in G:
+ for _, nd := range g.GetNodes() {
+ // MakeDisjointSet(v)
+ MakeDisjointSet(forests, nd.String())
+ }
+
+ // edges = get all edges
+ edges := []Edge{}
+ foundEdge := make(map[string]struct{})
+ for id1, nd1 := range g.GetNodes() {
+ tm, err := g.GetTargets(id1)
+ if err != nil {
+ return nil, err
+ }
+ for id2, nd2 := range tm {
+ weight, err := g.GetWeight(id1, id2)
+ if err != nil {
+ return nil, err
+ }
+ edge := NewEdge(nd1, nd2, weight)
+ if _, ok := foundEdge[edge.String()]; !ok {
+ edges = append(edges, edge)
+ foundEdge[edge.String()] = struct{}{}
+ }
+ }
+
+ sm, err := g.GetSources(id1)
+ if err != nil {
+ return nil, err
+ }
+ for id3, nd3 := range sm {
+ weight, err := g.GetWeight(id3, id1)
+ if err != nil {
+ return nil, err
+ }
+ edge := NewEdge(nd3, nd1, weight)
+ if _, ok := foundEdge[edge.String()]; !ok {
+ edges = append(edges, edge)
+ foundEdge[edge.String()] = struct{}{}
+ }
+ }
+ }
+
+ // sort edges in ascending order of weight
+ sort.Sort(EdgeSlice(edges))
+
+ // for each edge (u, v) in edges:
+ for _, edge := range edges {
+ // if FindSet(u) ≠ FindSet(v):
+ if FindSet(forests, edge.Source().String()).represent != FindSet(forests, edge.Target().String()).represent {
+
+ // A = A ∪ {(u, v)}
+ A[edge] = struct{}{}
+
+ // Union(u, v)
+ // overwrite v's represent with u's represent
+ Union(forests, FindSet(forests, edge.Source().String()), FindSet(forests, edge.Target().String()))
+ }
+ }
+
+ return A, nil
+}
+
+// Prim finds the minimum spanning tree with min-heap (priority queue).
+// (http://en.wikipedia.org/wiki/Prim%27s_algorithm)
+//
+// 0. Prim(G, source)
+// 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.
+// 14. while Q is not empty:
+// 15.
+// 16. u = Q.extract_min()
+// 17.
+// 18. for each adjacent vertex v of u:
+// 19.
+// 21. if v ∈ Q and distance[v] > weight(u, v):
+// 22. distance[v] = weight(u, v)
+// 23. prev[v] = u
+// 24. Q.decrease_priority(v, weight(u, v))
+// 25.
+// 26.
+// 27. return tree from prev
+//
+func Prim(g Graph, src ID) (map[Edge]struct{}, error) {
+
+ // let Q be a priority queue
+ minHeap := &nodeDistanceHeap{}
+
+ // distance[source] = 0
+ distance := make(map[ID]float64)
+ distance[src] = 0.0
+
+ // for each vertex v in G:
+ for id := range g.GetNodes() {
+
+ // if v ≠ src:
+ if id != src {
+ // 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)
+ uID := u.id
+
+ // for each adjacent vertex v of u:
+ tm, err := g.GetTargets(uID)
+ if err != nil {
+ return nil, err
+ }
+ for vID := range tm {
+
+ isExist := false
+ for _, one := range *minHeap {
+ if vID == one.id {
+ isExist = true
+ break
+ }
+ }
+
+ // weight(u, v)
+ weight, err := g.GetWeight(uID, vID)
+ if err != nil {
+ return nil, err
+ }
+
+ // if v ∈ Q and distance[v] > weight(u, v):
+ if isExist && distance[vID] > weight {
+
+ // distance[v] = weight(u, v)
+ distance[vID] = weight
+
+ // prev[v] = u
+ prev[vID] = uID
+
+ // Q.decrease_priority(v, weight(u, v))
+ minHeap.updateDistance(vID, weight)
+ heap.Init(minHeap)
+ }
+ }
+
+ sm, err := g.GetSources(uID)
+ if err != nil {
+ return nil, err
+ }
+ vID := uID
+ for uID := range sm {
+
+ isExist := false
+ for _, one := range *minHeap {
+ if vID == one.id {
+ isExist = true
+ break
+ }
+ }
+
+ // weight(u, v)
+ weight, err := g.GetWeight(uID, vID)
+ if err != nil {
+ return nil, err
+ }
+
+ // if v ∈ Q and distance[v] > weight(u, v):
+ if isExist && distance[vID] > weight {
+
+ // distance[v] = weight(u, v)
+ distance[vID] = weight
+
+ // prev[v] = u
+ prev[vID] = uID
+
+ // Q.decrease_priority(v, weight(u, v))
+ minHeap.updateDistance(vID, weight)
+ heap.Init(minHeap)
+ }
+ }
+ }
+
+ tree := make(map[Edge]struct{})
+ for k, v := range prev {
+ weight, err := g.GetWeight(v, k)
+ if err != nil {
+ return nil, err
+ }
+ tree[NewEdge(g.GetNode(v), g.GetNode(k), weight)] = struct{}{}
+ }
+ return tree, nil
+}
+
+type nodeDistance struct {
+ id ID
+ distance float64
+}
+
+// container.Heap's Interface needs sort.Interface, Push, Pop to be implemented
+
+// nodeDistanceHeap is a min-heap of nodeDistances.
+type nodeDistanceHeap []nodeDistance
+
+func (h nodeDistanceHeap) Len() int { return len(h) }
+func (h nodeDistanceHeap) Less(i, j int) bool { return h[i].distance < h[j].distance } // Min-Heap
+func (h nodeDistanceHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
+
+func (h *nodeDistanceHeap) Push(x interface{}) {
+ *h = append(*h, x.(nodeDistance))
+}
+
+func (h *nodeDistanceHeap) Pop() interface{} {
+ heapSize := len(*h)
+ lastNode := (*h)[heapSize-1]
+ *h = (*h)[0 : heapSize-1]
+ return lastNode
+}
+
+func (h *nodeDistanceHeap) updateDistance(id ID, val float64) {
+ for i := 0; i < len(*h); i++ {
+ if (*h)[i].id == id {
+ (*h)[i].distance = val
+ break
+ }
+ }
+}