## "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/old/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
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 //
38 func Euclidean(nNodes, nArcs int, affinity float64, patience int, r *rand.Rand) (g Directed, pos []structhlOpen(38,1);{ X, Y float64 hlClose(1, 38);}, err error) hlOpen(38,1);{
39     a := make(AdjacencyList, nNodes) // graph
40     // generate random positions
41     if r == nil hlOpen(41,2);{
42         r = rand.New(rand.NewSource(time.Now().UnixNano()))
43     hlClose(3, 43);}
44     pos = make([]structhlOpen(44,2);{ X, Y float64 hlClose(4, 44);}, nNodes)
45     for i := range pos hlOpen(45,2);{
46         pos[i].X = r.Float64()
47         pos[i].Y = r.Float64()
48     hlClose(5, 48);}
49     // arcs
50     var tooFar, dup int
51 arc:
52     for i := 0; i < nArcs; hlOpen(52,2);{
53         if tooFar == nArcs*patience hlOpen(53,3);{
55             return
56         hlClose(7, 56);}
57         if dup == nArcs*patience hlOpen(57,3);{
58             err = errors.New("overcrowding")
59             return
60         hlClose(8, 60);}
61         n1 := NI(r.Intn(nNodes))
62         var n2 NI
63         for hlOpen(63,3);{
64             n2 = NI(r.Intn(nNodes))
65             if n2 != n1 hlOpen(65,4);{ // no graph loops
66                 break
67             hlClose(10, 67);}
68         hlClose(9, 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() hlOpen(72,3);{ // favor near nodes
73             tooFar++
74             continue
75         hlClose(11, 75);}
76         for _, nb := range a[n1] hlOpen(76,3);{
77             if nb == n2 hlOpen(77,4);{ // no parallel arcs
78                 dup++
79                 continue arc
80             hlClose(13, 80);}
81         hlClose(12, 81);}
82         a[n1] = append(a[n1], n2)
83         i++
84     hlClose(6, 84);}
85     g = DirectedhlOpen(85,2);{ahlClose(14, 85);}
86     return
87 hlClose(2, 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 []structhlOpen(96,1);{ X, Y float64 hlClose(15, 96);}, wt []float64, err error) hlOpen(96,1);{
97     a := make(LabeledAdjacencyList, nNodes) // graph
98     wt = make([]float64, nArcs)             // arc weights
99     // generate random positions
100     if r == nil hlOpen(100,2);{
101         r = rand.New(rand.NewSource(time.Now().UnixNano()))
102     hlClose(17, 102);}
103     pos = make([]structhlOpen(103,2);{ X, Y float64 hlClose(18, 103);}, nNodes)
104     for i := range pos hlOpen(104,2);{
105         pos[i].X = r.Float64()
106         pos[i].Y = r.Float64()
107     hlClose(19, 107);}
108     // arcs
109     var tooFar, dup int
110 arc:
111     for i := 0; i < nArcs; hlOpen(111,2);{
112         if tooFar == nArcs*patience hlOpen(112,3);{
114             return
115         hlClose(21, 115);}
116         if dup == nArcs*patience hlOpen(116,3);{
117             err = errors.New("overcrowding")
118             return
119         hlClose(22, 119);}
120         n1 := NI(r.Intn(nNodes))
121         var n2 NI
122         for hlOpen(122,3);{
123             n2 = NI(r.Intn(nNodes))
124             if n2 != n1 hlOpen(124,4);{ // no graph loops
125                 break
126             hlClose(24, 126);}
127         hlClose(23, 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() hlOpen(131,3);{ // favor near nodes
132             tooFar++
133             continue
134         hlClose(25, 134);}
135         for _, nb := range a[n1] hlOpen(135,3);{
136             if nb.To == n2 hlOpen(136,4);{ // no parallel arcs
137                 dup++
138                 continue arc
139             hlClose(27, 139);}
140         hlClose(26, 140);}
141         wt[i] = dist
142         a[n1] = append(a[n1], HalfhlOpen(142,3);{n2, LI(i)hlClose(28, 142);})
143         i++
144     hlClose(20, 144);}
145     g = LabeledDirectedhlOpen(145,2);{ahlClose(29, 145);}
146     return
147 hlClose(16, 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 //
163 func Geometric(nNodes int, radius float64, r *rand.Rand) (g Undirected, pos []structhlOpen(163,1);{ X, Y float64 hlClose(30, 163);}, m int) hlOpen(163,1);{
164     // Expected degree is approximately nπr².
166     if r == nil hlOpen(166,2);{
167         r = rand.New(rand.NewSource(time.Now().UnixNano()))
168     hlClose(32, 168);}
169     pos = make([]structhlOpen(169,2);{ X, Y float64 hlClose(33, 169);}, nNodes)
170     for i := range pos hlOpen(170,2);{
171         pos[i].X = r.Float64()
172         pos[i].Y = r.Float64()
173     hlClose(34, 173);}
174     for u, up := range pos hlOpen(174,2);{
175         for v := u + 1; v < len(pos); v++ hlOpen(175,3);{
176             vp := pos[v]
177             if math.Hypot(up.X-vp.X, up.Y-vp.Y) < radius hlOpen(177,4);{
178                 a[u] = append(a[u], NI(v))
179                 a[v] = append(a[v], NI(u))
180                 m++
181             hlClose(37, 181);}
182         hlClose(36, 182);}
183     hlClose(35, 183);}
184     g = UndirectedhlOpen(184,2);{ahlClose(38, 184);}
185     return
186 hlClose(31, 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 []structhlOpen(196,1);{ X, Y float64 hlClose(39, 196);}, wt []float64) hlOpen(196,1);{
198     if r == nil hlOpen(198,2);{
199         r = rand.New(rand.NewSource(time.Now().UnixNano()))
200     hlClose(41, 200);}
201     pos = make([]structhlOpen(201,2);{ X, Y float64 hlClose(42, 201);}, nNodes)
202     for i := range pos hlOpen(202,2);{
203         pos[i].X = r.Float64()
204         pos[i].Y = r.Float64()
205     hlClose(43, 205);}
206     for u, up := range pos hlOpen(206,2);{
207         for v := u + 1; v < len(pos); v++ hlOpen(207,3);{
208             vp := pos[v]
209             if w := math.Hypot(up.X-vp.X, up.Y-vp.Y); w < radius hlOpen(209,4);{
210                 a[u] = append(a[u], HalfhlOpen(210,5);{NI(v), LI(len(wt))hlClose(47, 210);})
211                 a[v] = append(a[v], HalfhlOpen(211,5);{NI(u), LI(len(wt))hlClose(48, 211);})
212                 wt = append(wt, w)
213             hlClose(46, 213);}
214         hlClose(45, 214);}
215     hlClose(44, 215);}
216     g = LabeledUndirectedhlOpen(216,2);{ahlClose(49, 216);}
217     return
218 hlClose(40, 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) hlOpen(232,1);{
233     a, m := kronecker(scale, arcFactor, true, r)
234     return DirectedhlOpen(234,2);{ahlClose(51, 234);}, m
235 hlClose(50, 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) hlOpen(250,1);{
251     al, s := kronecker(scale, edgeFactor, false, r)
252     return UndirectedhlOpen(252,2);{alhlClose(53, 252);}, s
253 hlClose(52, 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) hlOpen(260,1);{
261     if r == nil hlOpen(261,2);{
262         r = rand.New(rand.NewSource(time.Now().UnixNano()))
263     hlClose(55, 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 hlOpen(273,2);{
274         var i, j NI
275         for b := NI(1); b < N; b <<= 1 hlOpen(275,3);{
276             if r.Float64() > ab hlOpen(276,4);{
277                 i |= b
278                 if r.Float64() > cNorm hlOpen(278,5);{
279                     j |= b
280                 hlClose(59, 280);}
281             hlClose(58, 281);} else if r.Float64() > aNorm hlOpen(281,4);{
282                 j |= b
283             hlClose(60, 283);}
284         hlClose(57, 284);}
285         if bm.Bit(i) == 0 hlOpen(285,3);{
286             bm.SetBit(i, 1)
287             nNodes++
288         hlClose(61, 288);}
289         if bm.Bit(j) == 0 hlOpen(289,3);{
290             bm.SetBit(j, 1)
291             nNodes++
292         hlClose(62, 292);}
293         r := r.Intn(k + 1) // shuffle edges as they are generated
294         ij[k] = ij[r]
295         ij[r] = [2]NIhlOpen(295,3);{i, jhlClose(63, 295);}
296     hlClose(56, 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 hlOpen(300,2);{
301         if bm.Bit(NI(i)) == 1 hlOpen(301,3);{
302             rn[i] = NI(p[px]) // fill lookup table
303             px++
304         hlClose(65, 304);}
305     hlClose(64, 305);}
307 ij:
308     for _, e := range ij hlOpen(308,2);{
309         if e[0] == e[1] hlOpen(309,3);{
310             continue // skip loops
311         hlClose(67, 311);}
312         ri, rj := rn[e[0]], rn[e[1]]
313         for _, nb := range g[ri] hlOpen(313,3);{
314             if nb == rj hlOpen(314,4);{
315                 continue ij // skip parallel edges
316             hlClose(69, 316);}
317         hlClose(68, 317);}
318         g[ri] = append(g[ri], rj)
319         mma++
320         if !dir hlOpen(320,3);{
321             g[rj] = append(g[rj], ri)
322         hlClose(70, 322);}
323     hlClose(66, 323);}
324     return
325 hlClose(54, 325);}
```