## "Fossies" - the Fresh Open Source Software Archive ### Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/adj_RO.go" (28 May 2021, 10916 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
3
4 package graph
5
6 // adj_RO.go is code generated from adj_cg.go by directives in graph.go.
7 // Editing adj_cg.go is okay.
8 // DO NOT EDIT adj_RO.go.  The RO is for Read Only.
9
10 import (
11     "math/rand"
12     "time"
13 )
14
15 // ArcSize returns the number of arcs in g.
16 //
17 // Note that for an undirected graph without loops, the number of undirected
18 // edges -- the traditional meaning of graph size -- will be ArcSize()/2.
19 // On the other hand, if g is an undirected graph that has or may have loops,
20 // g.ArcSize()/2 is not a meaningful quantity.
21 //
22 // There are equivalent labeled and unlabeled versions of this method.
23 func (g AdjacencyList) ArcSize() int hlOpen(23,1);{
24     m := 0
25     for _, to := range g hlOpen(25,2);{
26         m += len(to)
27     hlClose(2, 27);}
28     return m
29 hlClose(1, 29);}
30
31 // BoundsOk validates that all arcs in g stay within the slice bounds of g.
32 //
33 // BoundsOk returns true when no arcs point outside the bounds of g.
34 // Otherwise it returns false and an example arc that points outside of g.
35 //
36 // Most methods of this package assume the BoundsOk condition and may
37 // panic when they encounter an arc pointing outside of the graph.  This
38 // function can be used to validate a graph when the BoundsOk condition
39 // is unknown.
40 //
41 // There are equivalent labeled and unlabeled versions of this method.
42 func (g AdjacencyList) BoundsOk() (ok bool, fr NI, to NI) hlOpen(42,1);{
43     for fr, to := range g hlOpen(43,2);{
44         for _, to := range to hlOpen(44,3);{
45             if to < 0 || to >= NI(len(g)) hlOpen(45,4);{
46                 return false, NI(fr), to
47             hlClose(6, 47);}
48         hlClose(5, 48);}
49     hlClose(4, 49);}
50     return true, -1, to
51 hlClose(3, 51);}
52
53 // BreadthFirst traverses a directed or undirected graph in breadth first order.
54 //
55 // Argument start is the start node for the traversal.  If r is nil, nodes are
56 // visited in deterministic order.  If a random number generator is supplied,
57 // nodes at each level are visited in random order.
58 //
59 // Argument f can be nil if you have no interest in the FromList path result.
60 // If FromList f is non-nil, the method populates f.Paths and sets f.MaxLen.
61 // It does not set f.Leaves.  For convenience argument f can be a zero value
62 // FromList.  If f.Paths is nil, the FromList is initialized first.  If f.Paths
63 // is non-nil however, the FromList is  used as is.  The method uses a value of
64 // PathEnd.Len == 0 to indentify unvisited nodes.  Existing non-zero values
65 // will limit the traversal.
66 //
67 // Traversal calls the visitor function v for each node starting with node
68 // start.  If v returns true, traversal continues.  If v returns false, the
69 // traversal terminates immediately.  PathEnd Len and From values are updated
70 // before calling the visitor function.
71 //
72 // On return f.Paths and f.MaxLen are set but not f.Leaves.
73 //
74 // Returned is the number of nodes visited and ok = true if the traversal
75 // ran to completion or ok = false if it was terminated by the visitor
76 // function returning false.
77 //
78 // There are equivalent labeled and unlabeled versions of this method.
79 func (g AdjacencyList) BreadthFirst(start NI, r *rand.Rand, f *FromList, v OkNodeVisitor) (visited int, ok bool) hlOpen(79,1);{
80     switch hlOpen(80,2);{
81     case f == nil:
82         e := NewFromList(len(g))
83         f = &e
84     case f.Paths == nil:
85         *f = NewFromList(len(g))
86     hlClose(8, 86);}
87     rp := f.Paths
88     // the frontier consists of nodes all at the same level
89     frontier := []NIhlOpen(89,2);{starthlClose(9, 89);}
90     level := 1
91     // assign path when node is put on frontier,
92     rp[start] = PathEndhlOpen(92,2);{Len: level, From: -1hlClose(10, 92);}
93     for hlOpen(93,2);{
94         f.MaxLen = level
95         level++
96         var next []NI
97         if r == nil hlOpen(97,3);{
98             for _, n := range frontier hlOpen(98,4);{
99                 visited++
100                 if !v(n) hlOpen(100,5);{ // visit nodes as they come off frontier
101                     return
102                 hlClose(14, 102);}
103                 for _, nb := range g[n] hlOpen(103,5);{
104                     if rp[nb].Len == 0 hlOpen(104,6);{
105                         next = append(next, nb)
106                         rp[nb] = PathEndhlOpen(106,7);{From: n, Len: levelhlClose(17, 106);}
107                     hlClose(16, 107);}
108                 hlClose(15, 108);}
109             hlClose(13, 109);}
110         hlClose(12, 110);} else hlOpen(110,3);{ // take nodes off frontier at random
111             for _, i := range r.Perm(len(frontier)) hlOpen(111,4);{
112                 n := frontier[i]
113                 // remainder of block same as above
114                 visited++
115                 if !v(n) hlOpen(115,5);{
116                     return
117                 hlClose(20, 117);}
118                 for _, nb := range g[n] hlOpen(118,5);{
119                     if rp[nb].Len == 0 hlOpen(119,6);{
120                         next = append(next, nb)
121                         rp[nb] = PathEndhlOpen(121,7);{From: n, Len: levelhlClose(23, 121);}
122                     hlClose(22, 122);}
123                 hlClose(21, 123);}
124             hlClose(19, 124);}
125         hlClose(18, 125);}
126         if len(next) == 0 hlOpen(126,3);{
127             break
128         hlClose(24, 128);}
129         frontier = next
130     hlClose(11, 130);}
131     return visited, true
132 hlClose(7, 132);}
133
134 // BreadthFirstPath finds a single path from start to end with a minimum
135 // number of nodes.
136 //
137 // Returned is the path as list of nodes.
138 // The result is nil if no path was found.
139 //
140 // There are equivalent labeled and unlabeled versions of this method.
142     var f FromList
143     g.BreadthFirst(start, nil, &f, func(n NI) bool hlOpen(143,2);{ return n != end hlClose(26, 143);})
144     return f.PathTo(end, nil)
145 hlClose(25, 145);}
146
147 // Copy makes a deep copy of g.
148 // Copy also computes the arc size ma, the number of arcs.
149 //
150 // There are equivalent labeled and unlabeled versions of this method.
153     for n, to := range g hlOpen(153,2);{
154         c[n] = append([]NIhlOpen(154,3);{hlClose(29, 154);}, to...)
155         ma += len(to)
156     hlClose(28, 156);}
157     return
158 hlClose(27, 158);}
159
160 // DepthFirst traverses a graph depth first.
161 //
162 // As it traverses it calls visitor function v for each node.  If v returns
163 // false at any point, the traversal is terminated immediately and DepthFirst
164 // returns false.  Otherwise DepthFirst returns true.
165 //
166 // DepthFirst uses argument bm is used as a bitmap to guide the traversal.
167 // For a complete traversal, bm should be 0 initially.  During the
168 // traversal, bits are set corresponding to each node visited.
169 // The bit is set before calling the visitor function.
170 //
171 // Argument bm can be nil if you have no need for it.
172 // In this case a bitmap is created internally for one-time use.
173 //
174 // Alternatively v can be nil.  In this case traversal still proceeds and
175 // updates the bitmap, which can be a useful result.
176 // DepthFirst always returns true in this case.
177 //
178 // It makes no sense for both bm and v to be nil.  In this case DepthFirst
179 // returns false immediately.
180 //
181 // There are equivalent labeled and unlabeled versions of this method.
182 func (g AdjacencyList) DepthFirst(start NI, bm *Bits, v OkNodeVisitor) (ok bool) hlOpen(182,1);{
183     if bm == nil hlOpen(183,2);{
184         if v == nil hlOpen(184,3);{
185             return false
186         hlClose(32, 186);}
187         bm = &BitshlOpen(187,3);{hlClose(33, 187);}
188     hlClose(31, 188);}
189     var df func(n NI) bool
190     df = func(n NI) bool hlOpen(190,2);{
191         if bm.Bit(n) == 1 hlOpen(191,3);{
192             return true
193         hlClose(35, 193);}
194         bm.SetBit(n, 1)
195         if v != nil && !v(n) hlOpen(195,3);{
196             return false
197         hlClose(36, 197);}
198         for _, nb := range g[n] hlOpen(198,3);{
199             if !df(nb) hlOpen(199,4);{
200                 return false
201             hlClose(38, 201);}
202         hlClose(37, 202);}
203         return true
204     hlClose(34, 204);}
205     return df(start)
206 hlClose(30, 206);}
207
208 // DepthFirstRandom traverses a graph depth first, but following arcs in
209 // random order among arcs from a single node.
210 //
211 // If Rand r is nil, the method creates a new source and generator for
212 // one-time use.
213 //
214 // Usage is otherwise like the DepthFirst method.  See DepthFirst.
215 //
216 // There are equivalent labeled and unlabeled versions of this method.
217 func (g AdjacencyList) DepthFirstRandom(start NI, bm *Bits, v OkNodeVisitor, r *rand.Rand) (ok bool) hlOpen(217,1);{
218     if bm == nil hlOpen(218,2);{
219         if v == nil hlOpen(219,3);{
220             return false
221         hlClose(41, 221);}
222         bm = &BitshlOpen(222,3);{hlClose(42, 222);}
223     hlClose(40, 223);}
224     if r == nil hlOpen(224,2);{
225         r = rand.New(rand.NewSource(time.Now().UnixNano()))
226     hlClose(43, 226);}
227     var df func(n NI) bool
228     df = func(n NI) bool hlOpen(228,2);{
229         if bm.Bit(n) == 1 hlOpen(229,3);{
230             return true
231         hlClose(45, 231);}
232         bm.SetBit(n, 1)
233         if v != nil && !v(n) hlOpen(233,3);{
234             return false
235         hlClose(46, 235);}
236         to := g[n]
237         for _, i := range r.Perm(len(to)) hlOpen(237,3);{
238             if !df(to[i]) hlOpen(238,4);{
239                 return false
240             hlClose(48, 240);}
241         hlClose(47, 241);}
242         return true
243     hlClose(44, 243);}
244     return df(start)
245 hlClose(39, 245);}
246
247 // HasArc returns true if g has any arc from node fr to node to.
248 //
249 // Also returned is the index within the slice of arcs from node fr.
250 // If no arc from fr to to is present, HasArc returns false, -1.
251 //
252 // There are equivalent labeled and unlabeled versions of this method.
253 func (g AdjacencyList) HasArc(fr, to NI) (bool, int) hlOpen(253,1);{
254     for x, h := range g[fr] hlOpen(254,2);{
255         if h == to hlOpen(255,3);{
256             return true, x
257         hlClose(51, 257);}
258     hlClose(50, 258);}
259     return false, -1
260 hlClose(49, 260);}
261
262 // HasLoop identifies if a graph contains a loop, an arc that leads from a
263 // a node back to the same node.
264 //
265 // If the graph has a loop, the result is an example node that has a loop.
266 //
267 // If g contains a loop, the method returns true and an example of a node
268 // with a loop.  If there are no loops in g, the method returns false, -1.
269 //
270 // There are equivalent labeled and unlabeled versions of this method.
271 func (g AdjacencyList) HasLoop() (bool, NI) hlOpen(271,1);{
272     for fr, to := range g hlOpen(272,2);{
273         for _, to := range to hlOpen(273,3);{
274             if NI(fr) == to hlOpen(274,4);{
275                 return true, to
276             hlClose(55, 276);}
277         hlClose(54, 277);}
278     hlClose(53, 278);}
279     return false, -1
280 hlClose(52, 280);}
281
282 // HasParallelMap identifies if a graph contains parallel arcs, multiple arcs
283 // that lead from a node to the same node.
284 //
285 // If the graph has parallel arcs, the method returns true and
286 // results fr and to represent an example where there are parallel arcs
287 // from node fr to node to.
288 //
289 // If there are no parallel arcs, the method returns false, -1 -1.
290 //
291 // Multiple loops on a node count as parallel arcs.
292 //
293 // "Map" in the method name indicates that a Go map is used to detect parallel
294 // arcs.  Compared to method HasParallelSort, this gives better asymtotic
295 // performance for large dense graphs but may have increased overhead for
296 // small or sparse graphs.
297 //
298 // There are equivalent labeled and unlabeled versions of this method.
299 func (g AdjacencyList) HasParallelMap() (has bool, fr, to NI) hlOpen(299,1);{
300     for n, to := range g hlOpen(300,2);{
301         if len(to) == 0 hlOpen(301,3);{
302             continue
303         hlClose(58, 303);}
304         m := map[NI]structhlOpen(304,3);{hlClose(59, 304);}hlOpen(304,3);{hlClose(60, 304);}
305         for _, to := range to hlOpen(305,3);{
306             if _, ok := m[to]; ok hlOpen(306,4);{
307                 return true, NI(n), to
308             hlClose(62, 308);}
309             m[to] = structhlOpen(309,4);{hlClose(63, 309);}hlOpen(309,4);{hlClose(64, 309);}
310         hlClose(61, 310);}
311     hlClose(57, 311);}
312     return false, -1, -1
313 hlClose(56, 313);}
314
315 // IsSimple checks for loops and parallel arcs.
316 //
317 // A graph is "simple" if it has no loops or parallel arcs.
318 //
319 // IsSimple returns true, -1 for simple graphs.  If a loop or parallel arc is
320 // found, simple returns false and a node that represents a counterexample
321 // to the graph being simple.
322 //
324 //
325 // There are equivalent labeled and unlabeled versions of this method.
326 func (g AdjacencyList) IsSimple() (ok bool, n NI) hlOpen(326,1);{
327     if lp, n := g.HasLoop(); lp hlOpen(327,2);{
328         return false, n
329     hlClose(66, 329);}
330     if pa, n, _ := g.HasParallelSort(); pa hlOpen(330,2);{
331         return false, n
332     hlClose(67, 332);}
333     return true, -1
334 hlClose(65, 334);}
335
336 // IsolatedNodes returns a bitmap of isolated nodes in receiver graph g.
337 //
338 // An isolated node is one with no arcs going to or from it.
339 //
340 // There are equivalent labeled and unlabeled versions of this method.
341 func (g AdjacencyList) IsolatedNodes() (i Bits) hlOpen(341,1);{
342     i.SetAll(len(g))
343     for fr, to := range g hlOpen(343,2);{
344         if len(to) > 0 hlOpen(344,3);{
345             i.SetBit(NI(fr), 0)
346             for _, to := range to hlOpen(346,4);{
347                 i.SetBit(to, 0)
348             hlClose(71, 348);}
349         hlClose(70, 349);}
350     hlClose(69, 350);}
351     return
352 hlClose(68, 352);}
353
354 /*
355 MaxmimalClique finds a maximal clique containing the node n.
356
357 Not sure this is good for anything.  It produces a single maximal clique
358 but there can be multiple maximal cliques containing a given node.
359 This algorithm just returns one of them, not even necessarily the
360 largest one.
361
362 func (g LabeledAdjacencyList) MaximalClique(n int) []int {
363     c := []int{n}
364     var m bitset.BitSet
365     m.Set(uint(n))
366     for fr, to := range g {
367         if fr == n {
368             continue
369         }
370         if len(to) < len(c) {
371             continue
372         }
373         f := 0
374         for _, to := range to {
375             if m.Test(uint(to.To)) {
376                 f++
377                 if f == len(c) {
378                     c = append(c, to.To)
379                     m.Set(uint(to.To))
380                     break
381                 }
382             }
383         }
384     }
385     return c
386 }
387 */
```