"Fossies" - the Fresh Open Source Software Archive 
Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/random.go" (28 May 2021, 9415 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 2016 Sonia Keys
2 // License MIT: https://opensource.org/licenses/MIT
3
4 package graph
5
6 import (
7 "errors"
8 "math"
9 "math/rand"
10 "time"
11 )
12
13 // Euclidean generates a random simple graph on the Euclidean plane.
14 //
15 // Nodes are associated with coordinates uniformly distributed on a unit
16 // square. Arcs are added between random nodes with a bias toward connecting
17 // nearer nodes.
18 //
19 // Unfortunately the function has a few "knobs".
20 // The returned graph will have order nNodes and arc size nArcs. The affinity
21 // argument controls the bias toward connecting nearer nodes. The function
22 // selects random pairs of nodes as a candidate arc then rejects the candidate
23 // if the nodes fail an affinity test. Also parallel arcs are rejected.
24 // As more affine or denser graphs are requested, rejections increase,
25 // increasing run time. The patience argument controls the number of arc
26 // rejections allowed before the function gives up and returns an error.
27 // Note that higher affinity will require more patience and that some
28 // combinations of nNodes and nArcs cannot be achieved with any amount of
29 // patience given that the returned graph must be simple.
30 //
31 // If Rand r is nil, the method creates a new source and generator for
32 // one-time use.
33 //
34 // Returned is a directed simple graph and associated positions indexed by
35 // node number.
36 //
37 // See also LabeledEuclidean.
38 func Euclidean(nNodes, nArcs int, affinity float64, patience int, r *rand.Rand) (g Directed, pos []struct{ X, Y float64 }, err error) {
39 a := make(AdjacencyList, nNodes) // graph
40 // generate random positions
41 if r == nil {
42 r = rand.New(rand.NewSource(time.Now().UnixNano()))
43 }
44 pos = make([]struct{ X, Y float64 }, nNodes)
45 for i := range pos {
46 pos[i].X = r.Float64()
47 pos[i].Y = r.Float64()
48 }
49 // arcs
50 var tooFar, dup int
51 arc:
52 for i := 0; i < nArcs; {
53 if tooFar == nArcs*patience {
54 err = errors.New("affinity not found")
55 return
56 }
57 if dup == nArcs*patience {
58 err = errors.New("overcrowding")
59 return
60 }
61 n1 := NI(r.Intn(nNodes))
62 var n2 NI
63 for {
64 n2 = NI(r.Intn(nNodes))
65 if n2 != n1 { // no graph loops
66 break
67 }
68 }
69 c1 := &pos[n1]
70 c2 := &pos[n2]
71 dist := math.Hypot(c2.X-c1.X, c2.Y-c1.Y)
72 if dist*affinity > r.ExpFloat64() { // favor near nodes
73 tooFar++
74 continue
75 }
76 for _, nb := range a[n1] {
77 if nb == n2 { // no parallel arcs
78 dup++
79 continue arc
80 }
81 }
82 a[n1] = append(a[n1], n2)
83 i++
84 }
85 g = Directed{a}
86 return
87 }
88
89 // LabeledEuclidean generates a random simple graph on the Euclidean plane.
90 //
91 // Arc label values in the returned graph g are indexes into the return value
92 // wt. Wt is the Euclidean distance between the from and to nodes of the arc.
93 //
94 // Otherwise the function arguments and return values are the same as for
95 // function Euclidean. See Euclidean.
96 func LabeledEuclidean(nNodes, nArcs int, affinity float64, patience int, r *rand.Rand) (g LabeledDirected, pos []struct{ X, Y float64 }, wt []float64, err error) {
97 a := make(LabeledAdjacencyList, nNodes) // graph
98 wt = make([]float64, nArcs) // arc weights
99 // generate random positions
100 if r == nil {
101 r = rand.New(rand.NewSource(time.Now().UnixNano()))
102 }
103 pos = make([]struct{ X, Y float64 }, nNodes)
104 for i := range pos {
105 pos[i].X = r.Float64()
106 pos[i].Y = r.Float64()
107 }
108 // arcs
109 var tooFar, dup int
110 arc:
111 for i := 0; i < nArcs; {
112 if tooFar == nArcs*patience {
113 err = errors.New("affinity not found")
114 return
115 }
116 if dup == nArcs*patience {
117 err = errors.New("overcrowding")
118 return
119 }
120 n1 := NI(r.Intn(nNodes))
121 var n2 NI
122 for {
123 n2 = NI(r.Intn(nNodes))
124 if n2 != n1 { // no graph loops
125 break
126 }
127 }
128 c1 := &pos[n1]
129 c2 := &pos[n2]
130 dist := math.Hypot(c2.X-c1.X, c2.Y-c1.Y)
131 if dist*affinity > r.ExpFloat64() { // favor near nodes
132 tooFar++
133 continue
134 }
135 for _, nb := range a[n1] {
136 if nb.To == n2 { // no parallel arcs
137 dup++
138 continue arc
139 }
140 }
141 wt[i] = dist
142 a[n1] = append(a[n1], Half{n2, LI(i)})
143 i++
144 }
145 g = LabeledDirected{a}
146 return
147 }
148
149 // Geometric generates a random geometric graph (RGG) on the Euclidean plane.
150 //
151 // An RGG is an undirected simple graph. Nodes are associated with coordinates
152 // uniformly distributed on a unit square. Edges are added between all nodes
153 // falling within a specified distance or radius of each other.
154 //
155 // The resulting number of edges is somewhat random but asymptotically
156 // approaches m = πr²n²/2. The method accumulates and returns the actual
157 // number of edges constructed.
158 //
159 // If Rand r is nil, the method creates a new source and generator for
160 // one-time use.
161 //
162 // See also LabeledGeometric.
163 func Geometric(nNodes int, radius float64, r *rand.Rand) (g Undirected, pos []struct{ X, Y float64 }, m int) {
164 // Expected degree is approximately nπr².
165 a := make(AdjacencyList, nNodes)
166 if r == nil {
167 r = rand.New(rand.NewSource(time.Now().UnixNano()))
168 }
169 pos = make([]struct{ X, Y float64 }, nNodes)
170 for i := range pos {
171 pos[i].X = r.Float64()
172 pos[i].Y = r.Float64()
173 }
174 for u, up := range pos {
175 for v := u + 1; v < len(pos); v++ {
176 vp := pos[v]
177 if math.Hypot(up.X-vp.X, up.Y-vp.Y) < radius {
178 a[u] = append(a[u], NI(v))
179 a[v] = append(a[v], NI(u))
180 m++
181 }
182 }
183 }
184 g = Undirected{a}
185 return
186 }
187
188 // LabeledGeometric generates a random geometric graph (RGG) on the Euclidean
189 // plane.
190 //
191 // Edge label values in the returned graph g are indexes into the return value
192 // wt. Wt is the Euclidean distance between nodes of the edge. The graph
193 // size m is len(wt).
194 //
195 // See Geometric for additional description.
196 func LabeledGeometric(nNodes int, radius float64, r *rand.Rand) (g LabeledUndirected, pos []struct{ X, Y float64 }, wt []float64) {
197 a := make(LabeledAdjacencyList, nNodes)
198 if r == nil {
199 r = rand.New(rand.NewSource(time.Now().UnixNano()))
200 }
201 pos = make([]struct{ X, Y float64 }, nNodes)
202 for i := range pos {
203 pos[i].X = r.Float64()
204 pos[i].Y = r.Float64()
205 }
206 for u, up := range pos {
207 for v := u + 1; v < len(pos); v++ {
208 vp := pos[v]
209 if w := math.Hypot(up.X-vp.X, up.Y-vp.Y); w < radius {
210 a[u] = append(a[u], Half{NI(v), LI(len(wt))})
211 a[v] = append(a[v], Half{NI(u), LI(len(wt))})
212 wt = append(wt, w)
213 }
214 }
215 }
216 g = LabeledUndirected{a}
217 return
218 }
219
220 // KroneckerDirected generates a Kronecker-like random directed graph.
221 //
222 // The returned graph g is simple and has no isolated nodes but is not
223 // necessarily fully connected. The number of of nodes will be <= 2^scale,
224 // and will be near 2^scale for typical values of arcFactor, >= 2.
225 // ArcFactor * 2^scale arcs are generated, although loops and duplicate arcs
226 // are rejected.
227 //
228 // If Rand r is nil, the method creates a new source and generator for
229 // one-time use.
230 //
231 // Return value ma is the number of arcs retained in the result graph.
232 func KroneckerDirected(scale uint, arcFactor float64, r *rand.Rand) (g Directed, ma int) {
233 a, m := kronecker(scale, arcFactor, true, r)
234 return Directed{a}, m
235 }
236
237 // KroneckerUndirected generates a Kronecker-like random undirected graph.
238 //
239 // The returned graph g is simple and has no isolated nodes but is not
240 // necessarily fully connected. The number of of nodes will be <= 2^scale,
241 // and will be near 2^scale for typical values of edgeFactor, >= 2.
242 // EdgeFactor * 2^scale edges are generated, although loops and duplicate edges
243 // are rejected.
244 //
245 // If Rand r is nil, the method creates a new source and generator for
246 // one-time use.
247 //
248 // Return value m is the true number of edges--not arcs--retained in the result
249 // graph.
250 func KroneckerUndirected(scale uint, edgeFactor float64, r *rand.Rand) (g Undirected, m int) {
251 al, s := kronecker(scale, edgeFactor, false, r)
252 return Undirected{al}, s
253 }
254
255 // Styled after the Graph500 example code. Not well tested currently.
256 // Graph500 example generates undirected only. No idea if the directed variant
257 // here is meaningful or not.
258 //
259 // note mma returns arc size ma for dir=true, but returns size m for dir=false
260 func kronecker(scale uint, edgeFactor float64, dir bool, r *rand.Rand) (g AdjacencyList, mma int) {
261 if r == nil {
262 r = rand.New(rand.NewSource(time.Now().UnixNano()))
263 }
264 N := NI(1 << scale) // node extent
265 M := int(edgeFactor*float64(N) + .5) // number of arcs/edges to generate
266 a, b, c := 0.57, 0.19, 0.19 // initiator probabilities
267 ab := a + b
268 cNorm := c / (1 - ab)
269 aNorm := a / ab
270 ij := make([][2]NI, M)
271 var bm Bits
272 var nNodes int
273 for k := range ij {
274 var i, j NI
275 for b := NI(1); b < N; b <<= 1 {
276 if r.Float64() > ab {
277 i |= b
278 if r.Float64() > cNorm {
279 j |= b
280 }
281 } else if r.Float64() > aNorm {
282 j |= b
283 }
284 }
285 if bm.Bit(i) == 0 {
286 bm.SetBit(i, 1)
287 nNodes++
288 }
289 if bm.Bit(j) == 0 {
290 bm.SetBit(j, 1)
291 nNodes++
292 }
293 r := r.Intn(k + 1) // shuffle edges as they are generated
294 ij[k] = ij[r]
295 ij[r] = [2]NI{i, j}
296 }
297 p := r.Perm(nNodes) // mapping to shuffle IDs of non-isolated nodes
298 px := 0
299 rn := make([]NI, N)
300 for i := range rn {
301 if bm.Bit(NI(i)) == 1 {
302 rn[i] = NI(p[px]) // fill lookup table
303 px++
304 }
305 }
306 g = make(AdjacencyList, nNodes)
307 ij:
308 for _, e := range ij {
309 if e[0] == e[1] {
310 continue // skip loops
311 }
312 ri, rj := rn[e[0]], rn[e[1]]
313 for _, nb := range g[ri] {
314 if nb == rj {
315 continue ij // skip parallel edges
316 }
317 }
318 g[ri] = append(g[ri], rj)
319 mma++
320 if !dir {
321 g[rj] = append(g[rj], ri)
322 }
323 }
324 return
325 }