"Fossies" - the Fresh Open Source Software Archive 
Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/mst.go" (28 May 2021, 6668 Bytes) of package /linux/misc/gdrive-2.1.1.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Go source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
1 // Copyright 2014 Sonia Keys
2 // License MIT: http://opensource.org/licenses/MIT
3
4 package graph
5
6 import (
7 "container/heap"
8 "sort"
9 )
10
11 type dsElement struct {
12 from NI
13 rank int
14 }
15
16 type disjointSet struct {
17 set []dsElement
18 }
19
20 func newDisjointSet(n int) disjointSet {
21 set := make([]dsElement, n)
22 for i := range set {
23 set[i].from = -1
24 }
25 return disjointSet{set}
26 }
27
28 // return true if disjoint trees were combined.
29 // false if x and y were already in the same tree.
30 func (ds disjointSet) union(x, y NI) bool {
31 xr := ds.find(x)
32 yr := ds.find(y)
33 if xr == yr {
34 return false
35 }
36 switch xe, ye := &ds.set[xr], &ds.set[yr]; {
37 case xe.rank < ye.rank:
38 xe.from = yr
39 case xe.rank == ye.rank:
40 xe.rank++
41 fallthrough
42 default:
43 ye.from = xr
44 }
45 return true
46 }
47
48 func (ds disjointSet) find(n NI) NI {
49 // fast paths for n == root or from root.
50 // no updates need in these cases.
51 s := ds.set
52 fr := s[n].from
53 if fr < 0 { // n is root
54 return n
55 }
56 n, fr = fr, s[fr].from
57 if fr < 0 { // n is from root
58 return n
59 }
60 // otherwise updates needed.
61 // two iterative passes (rather than recursion or stack)
62 // pass 1: find root
63 r := fr
64 for {
65 f := s[r].from
66 if f < 0 {
67 break
68 }
69 r = f
70 }
71 // pass 2: update froms
72 for {
73 s[n].from = r
74 if fr == r {
75 return r
76 }
77 n = fr
78 fr = s[n].from
79 }
80 }
81
82 // Kruskal implements Kruskal's algorithm for constructing a minimum spanning
83 // forest on an undirected graph.
84 //
85 // While the input graph is interpreted as undirected, the receiver edge list
86 // does not actually need to contain reciprocal arcs. A property of the
87 // algorithm is that arc direction is ignored. Thus only a single arc out of
88 // a reciprocal pair must be present in the edge list. Reciprocal arcs (and
89 // parallel arcs) are allowed though, and do not affect the result.
90 //
91 // The forest is returned as an undirected graph.
92 //
93 // Also returned is a total distance for the returned forest.
94 //
95 // The edge list of the receiver is sorted as a side effect of this method.
96 // See KruskalSorted for a version that relies on the edge list being already
97 // sorted.
98 func (l WeightedEdgeList) Kruskal() (g LabeledUndirected, dist float64) {
99 sort.Sort(l)
100 return l.KruskalSorted()
101 }
102
103 // KruskalSorted implements Kruskal's algorithm for constructing a minimum
104 // spanning tree on an undirected graph.
105 //
106 // While the input graph is interpreted as undirected, the receiver edge list
107 // does not actually need to contain reciprocal arcs. A property of the
108 // algorithm is that arc direction is ignored. Thus only a single arc out of
109 // a reciprocal pair must be present in the edge list. Reciprocal arcs (and
110 // parallel arcs) are allowed though, and do not affect the result.
111 //
112 // When called, the edge list of the receiver must be already sorted by weight.
113 // See Kruskal for a version that accepts an unsorted edge list.
114 //
115 // The forest is returned as an undirected graph.
116 //
117 // Also returned is a total distance for the returned forest.
118 func (l WeightedEdgeList) KruskalSorted() (g LabeledUndirected, dist float64) {
119 ds := newDisjointSet(l.Order)
120 g.LabeledAdjacencyList = make(LabeledAdjacencyList, l.Order)
121 for _, e := range l.Edges {
122 if ds.union(e.N1, e.N2) {
123 g.AddEdge(Edge{e.N1, e.N2}, e.LI)
124 dist += l.WeightFunc(e.LI)
125 }
126 }
127 return
128 }
129
130 // Prim implements the JarnÃk-Prim-Dijkstra algorithm for constructing
131 // a minimum spanning tree on an undirected graph.
132 //
133 // Prim computes a minimal spanning tree on the connected component containing
134 // the given start node. The tree is returned in FromList f. Argument f
135 // cannot be a nil pointer although it can point to a zero value FromList.
136 //
137 // If the passed FromList.Paths has the len of g though, it will be reused.
138 // In the case of a graph with multiple connected components, this allows a
139 // spanning forest to be accumulated by calling Prim successively on
140 // representative nodes of the components. In this case if leaves for
141 // individual trees are of interest, pass a non-nil zero-value for the argument
142 // componentLeaves and it will be populated with leaves for the single tree
143 // spanned by the call.
144 //
145 // If argument labels is non-nil, it must have the same length as g and will
146 // be populated with labels corresponding to the edges of the tree.
147 //
148 // Returned are the number of nodes spanned for the single tree (which will be
149 // the order of the connected component) and the total spanned distance for the
150 // single tree.
151 func (g LabeledUndirected) Prim(start NI, w WeightFunc, f *FromList, labels []LI, componentLeaves *Bits) (numSpanned int, dist float64) {
152 al := g.LabeledAdjacencyList
153 if len(f.Paths) != len(al) {
154 *f = NewFromList(len(al))
155 }
156 b := make([]prNode, len(al)) // "best"
157 for n := range b {
158 b[n].nx = NI(n)
159 b[n].fx = -1
160 }
161 rp := f.Paths
162 var frontier prHeap
163 rp[start] = PathEnd{From: -1, Len: 1}
164 numSpanned = 1
165 fLeaves := &f.Leaves
166 fLeaves.SetBit(start, 1)
167 if componentLeaves != nil {
168 componentLeaves.SetBit(start, 1)
169 }
170 for a := start; ; {
171 for _, nb := range al[a] {
172 if rp[nb.To].Len > 0 {
173 continue // already in MST, no action
174 }
175 switch bp := &b[nb.To]; {
176 case bp.fx == -1: // new node for frontier
177 bp.from = fromHalf{From: a, Label: nb.Label}
178 bp.wt = w(nb.Label)
179 heap.Push(&frontier, bp)
180 case w(nb.Label) < bp.wt: // better arc
181 bp.from = fromHalf{From: a, Label: nb.Label}
182 bp.wt = w(nb.Label)
183 heap.Fix(&frontier, bp.fx)
184 }
185 }
186 if len(frontier) == 0 {
187 break // done
188 }
189 bp := heap.Pop(&frontier).(*prNode)
190 a = bp.nx
191 rp[a].Len = rp[bp.from.From].Len + 1
192 rp[a].From = bp.from.From
193 if len(labels) != 0 {
194 labels[a] = bp.from.Label
195 }
196 dist += bp.wt
197 fLeaves.SetBit(bp.from.From, 0)
198 fLeaves.SetBit(a, 1)
199 if componentLeaves != nil {
200 componentLeaves.SetBit(bp.from.From, 0)
201 componentLeaves.SetBit(a, 1)
202 }
203 numSpanned++
204 }
205 return
206 }
207
208 // fromHalf is a half arc, representing a labeled arc and the "neighbor" node
209 // that the arc originates from.
210 //
211 // (This used to be exported when there was a LabeledFromList. Currently
212 // unexported now that it seems to have much more limited use.)
213 type fromHalf struct {
214 From NI
215 Label LI
216 }
217
218 type prNode struct {
219 nx NI
220 from fromHalf
221 wt float64 // p.Weight(from.Label)
222 fx int
223 }
224
225 type prHeap []*prNode
226
227 func (h prHeap) Len() int { return len(h) }
228 func (h prHeap) Less(i, j int) bool { return h[i].wt < h[j].wt }
229 func (h prHeap) Swap(i, j int) {
230 h[i], h[j] = h[j], h[i]
231 h[i].fx = i
232 h[j].fx = j
233 }
234 func (p *prHeap) Push(x interface{}) {
235 nd := x.(*prNode)
236 nd.fx = len(*p)
237 *p = append(*p, nd)
238 }
239 func (p *prHeap) Pop() interface{} {
240 r := *p
241 last := len(r) - 1
242 *p = r[:last]
243 return r[last]
244 }