"Fossies" - the Fresh Open Source Software Archive 
Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/undir_RO.go" (28 May 2021, 16624 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 // undir_RO.go is code generated from undir_cg.go by directives in graph.go.
7 // Editing undir_cg.go is okay. It is the code generation source.
8 // DO NOT EDIT undir_RO.go.
9 // The RO means read only and it is upper case RO to slow you down a bit
10 // in case you start to edit the file.
11
12 // Bipartite determines if a connected component of an undirected graph
13 // is bipartite, a component where nodes can be partitioned into two sets
14 // such that every edge in the component goes from one set to the other.
15 //
16 // Argument n can be any representative node of the component.
17 //
18 // If the component is bipartite, Bipartite returns true and a two-coloring
19 // of the component. Each color set is returned as a bitmap. If the component
20 // is not bipartite, Bipartite returns false and a representative odd cycle.
21 //
22 // There are equivalent labeled and unlabeled versions of this method.
23 func (g Undirected) Bipartite(n NI) (b bool, c1, c2 Bits, oc []NI) {
24 b = true
25 var open bool
26 var df func(n NI, c1, c2 *Bits)
27 df = func(n NI, c1, c2 *Bits) {
28 c1.SetBit(n, 1)
29 for _, nb := range g.AdjacencyList[n] {
30 if c1.Bit(nb) == 1 {
31 b = false
32 oc = []NI{nb, n}
33 open = true
34 return
35 }
36 if c2.Bit(nb) == 1 {
37 continue
38 }
39 df(nb, c2, c1)
40 if b {
41 continue
42 }
43 switch {
44 case !open:
45 case n == oc[0]:
46 open = false
47 default:
48 oc = append(oc, n)
49 }
50 return
51 }
52 }
53 df(n, &c1, &c2)
54 if b {
55 return b, c1, c2, nil
56 }
57 return b, Bits{}, Bits{}, oc
58 }
59
60 // BronKerbosch1 finds maximal cliques in an undirected graph.
61 //
62 // The graph must not contain parallel edges or loops.
63 //
64 // See https://en.wikipedia.org/wiki/Clique_(graph_theory) and
65 // https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background.
66 //
67 // This method implements the BronKerbosch1 algorithm of WP; that is,
68 // the original algorithm without improvements.
69 //
70 // The method calls the emit argument for each maximal clique in g, as long
71 // as emit returns true. If emit returns false, BronKerbosch1 returns
72 // immediately.
73 //
74 // There are equivalent labeled and unlabeled versions of this method.
75 //
76 // See also more sophisticated variants BronKerbosch2 and BronKerbosch3.
77 func (g Undirected) BronKerbosch1(emit func([]NI) bool) {
78 a := g.AdjacencyList
79 var f func(R, P, X *Bits) bool
80 f = func(R, P, X *Bits) bool {
81 switch {
82 case !P.Zero():
83 var r2, p2, x2 Bits
84 pf := func(n NI) bool {
85 r2.Set(*R)
86 r2.SetBit(n, 1)
87 p2.Clear()
88 x2.Clear()
89 for _, to := range a[n] {
90 if P.Bit(to) == 1 {
91 p2.SetBit(to, 1)
92 }
93 if X.Bit(to) == 1 {
94 x2.SetBit(to, 1)
95 }
96 }
97 if !f(&r2, &p2, &x2) {
98 return false
99 }
100 P.SetBit(n, 0)
101 X.SetBit(n, 1)
102 return true
103 }
104 if !P.Iterate(pf) {
105 return false
106 }
107 case X.Zero():
108 return emit(R.Slice())
109 }
110 return true
111 }
112 var R, P, X Bits
113 P.SetAll(len(a))
114 f(&R, &P, &X)
115 }
116
117 // BKPivotMaxDegree is a strategy for BronKerbosch methods.
118 //
119 // To use it, take the method value (see golang.org/ref/spec#Method_values)
120 // and pass it as the argument to BronKerbosch2 or 3.
121 //
122 // The strategy is to pick the node from P or X with the maximum degree
123 // (number of edges) in g. Note this is a shortcut from evaluating degrees
124 // in P.
125 //
126 // There are equivalent labeled and unlabeled versions of this method.
127 func (g Undirected) BKPivotMaxDegree(P, X *Bits) (p NI) {
128 // choose pivot u as highest degree node from P or X
129 a := g.AdjacencyList
130 maxDeg := -1
131 P.Iterate(func(n NI) bool { // scan P
132 if d := len(a[n]); d > maxDeg {
133 p = n
134 maxDeg = d
135 }
136 return true
137 })
138 X.Iterate(func(n NI) bool { // scan X
139 if d := len(a[n]); d > maxDeg {
140 p = n
141 maxDeg = d
142 }
143 return true
144 })
145 return
146 }
147
148 // BKPivotMinP is a strategy for BronKerbosch methods.
149 //
150 // To use it, take the method value (see golang.org/ref/spec#Method_values)
151 // and pass it as the argument to BronKerbosch2 or 3.
152 //
153 // The strategy is to simply pick the first node in P.
154 //
155 // There are equivalent labeled and unlabeled versions of this method.
156 func (g Undirected) BKPivotMinP(P, X *Bits) NI {
157 return P.From(0)
158 }
159
160 // BronKerbosch2 finds maximal cliques in an undirected graph.
161 //
162 // The graph must not contain parallel edges or loops.
163 //
164 // See https://en.wikipedia.org/wiki/Clique_(graph_theory) and
165 // https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background.
166 //
167 // This method implements the BronKerbosch2 algorithm of WP; that is,
168 // the original algorithm plus pivoting.
169 //
170 // The argument is a pivot function that must return a node of P or X.
171 // P is guaranteed to contain at least one node. X is not.
172 // For example see BKPivotMaxDegree.
173 //
174 // The method calls the emit argument for each maximal clique in g, as long
175 // as emit returns true. If emit returns false, BronKerbosch1 returns
176 // immediately.
177 //
178 // There are equivalent labeled and unlabeled versions of this method.
179 //
180 // See also simpler variant BronKerbosch1 and more sophisticated variant
181 // BronKerbosch3.
182 func (g Undirected) BronKerbosch2(pivot func(P, X *Bits) NI, emit func([]NI) bool) {
183 a := g.AdjacencyList
184 var f func(R, P, X *Bits) bool
185 f = func(R, P, X *Bits) bool {
186 switch {
187 case !P.Zero():
188 var r2, p2, x2, pnu Bits
189 // compute P \ N(u). next 5 lines are only difference from BK1
190 pnu.Set(*P)
191 for _, to := range a[pivot(P, X)] {
192 pnu.SetBit(to, 0)
193 }
194 // remaining code like BK1
195 pf := func(n NI) bool {
196 r2.Set(*R)
197 r2.SetBit(n, 1)
198 p2.Clear()
199 x2.Clear()
200 for _, to := range a[n] {
201 if P.Bit(to) == 1 {
202 p2.SetBit(to, 1)
203 }
204 if X.Bit(to) == 1 {
205 x2.SetBit(to, 1)
206 }
207 }
208 if !f(&r2, &p2, &x2) {
209 return false
210 }
211 P.SetBit(n, 0)
212 X.SetBit(n, 1)
213 return true
214 }
215 if !pnu.Iterate(pf) {
216 return false
217 }
218 case X.Zero():
219 return emit(R.Slice())
220 }
221 return true
222 }
223 var R, P, X Bits
224 P.SetAll(len(a))
225 f(&R, &P, &X)
226 }
227
228 // BronKerbosch3 finds maximal cliques in an undirected graph.
229 //
230 // The graph must not contain parallel edges or loops.
231 //
232 // See https://en.wikipedia.org/wiki/Clique_(graph_theory) and
233 // https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background.
234 //
235 // This method implements the BronKerbosch3 algorithm of WP; that is,
236 // the original algorithm with pivoting and degeneracy ordering.
237 //
238 // The argument is a pivot function that must return a node of P or X.
239 // P is guaranteed to contain at least one node. X is not.
240 // For example see BKPivotMaxDegree.
241 //
242 // The method calls the emit argument for each maximal clique in g, as long
243 // as emit returns true. If emit returns false, BronKerbosch1 returns
244 // immediately.
245 //
246 // There are equivalent labeled and unlabeled versions of this method.
247 //
248 // See also simpler variants BronKerbosch1 and BronKerbosch2.
249 func (g Undirected) BronKerbosch3(pivot func(P, X *Bits) NI, emit func([]NI) bool) {
250 a := g.AdjacencyList
251 var f func(R, P, X *Bits) bool
252 f = func(R, P, X *Bits) bool {
253 switch {
254 case !P.Zero():
255 var r2, p2, x2, pnu Bits
256 // compute P \ N(u). next lines are only difference from BK1
257 pnu.Set(*P)
258 for _, to := range a[pivot(P, X)] {
259 pnu.SetBit(to, 0)
260 }
261 // remaining code like BK2
262 pf := func(n NI) bool {
263 r2.Set(*R)
264 r2.SetBit(n, 1)
265 p2.Clear()
266 x2.Clear()
267 for _, to := range a[n] {
268 if P.Bit(to) == 1 {
269 p2.SetBit(to, 1)
270 }
271 if X.Bit(to) == 1 {
272 x2.SetBit(to, 1)
273 }
274 }
275 if !f(&r2, &p2, &x2) {
276 return false
277 }
278 P.SetBit(n, 0)
279 X.SetBit(n, 1)
280 return true
281 }
282 if !pnu.Iterate(pf) {
283 return false
284 }
285 case X.Zero():
286 return emit(R.Slice())
287 }
288 return true
289 }
290 var R, P, X Bits
291 P.SetAll(len(a))
292 // code above same as BK2
293 // code below new to BK3
294 _, ord, _ := g.Degeneracy()
295 var p2, x2 Bits
296 for _, n := range ord {
297 R.SetBit(n, 1)
298 p2.Clear()
299 x2.Clear()
300 for _, to := range a[n] {
301 if P.Bit(to) == 1 {
302 p2.SetBit(to, 1)
303 }
304 if X.Bit(to) == 1 {
305 x2.SetBit(to, 1)
306 }
307 }
308 if !f(&R, &p2, &x2) {
309 return
310 }
311 R.SetBit(n, 0)
312 P.SetBit(n, 0)
313 X.SetBit(n, 1)
314 }
315 }
316
317 // ConnectedComponentBits returns a function that iterates over connected
318 // components of g, returning a member bitmap for each.
319 //
320 // Each call of the returned function returns the order (number of nodes)
321 // and bits of a connected component. The returned function returns zeros
322 // after returning all connected components.
323 //
324 // There are equivalent labeled and unlabeled versions of this method.
325 //
326 // See also ConnectedComponentReps, which has lighter weight return values.
327 func (g Undirected) ConnectedComponentBits() func() (order int, bits Bits) {
328 a := g.AdjacencyList
329 var vg Bits // nodes visited in graph
330 var vc *Bits // nodes visited in current component
331 var nc int
332 var df func(NI)
333 df = func(n NI) {
334 vg.SetBit(n, 1)
335 vc.SetBit(n, 1)
336 nc++
337 for _, nb := range a[n] {
338 if vg.Bit(nb) == 0 {
339 df(nb)
340 }
341 }
342 return
343 }
344 var n NI
345 return func() (o int, bits Bits) {
346 for ; n < NI(len(a)); n++ {
347 if vg.Bit(n) == 0 {
348 vc = &bits
349 nc = 0
350 df(n)
351 return nc, bits
352 }
353 }
354 return
355 }
356 }
357
358 // ConnectedComponentLists returns a function that iterates over connected
359 // components of g, returning the member list of each.
360 //
361 // Each call of the returned function returns a node list of a connected
362 // component. The returned function returns nil after returning all connected
363 // components.
364 //
365 // There are equivalent labeled and unlabeled versions of this method.
366 //
367 // See also ConnectedComponentReps, which has lighter weight return values.
368 func (g Undirected) ConnectedComponentLists() func() []NI {
369 a := g.AdjacencyList
370 var vg Bits // nodes visited in graph
371 var m []NI // members of current component
372 var df func(NI)
373 df = func(n NI) {
374 vg.SetBit(n, 1)
375 m = append(m, n)
376 for _, nb := range a[n] {
377 if vg.Bit(nb) == 0 {
378 df(nb)
379 }
380 }
381 return
382 }
383 var n NI
384 return func() []NI {
385 for ; n < NI(len(a)); n++ {
386 if vg.Bit(n) == 0 {
387 m = nil
388 df(n)
389 return m
390 }
391 }
392 return nil
393 }
394 }
395
396 // ConnectedComponentReps returns a representative node from each connected
397 // component of g.
398 //
399 // Returned is a slice with a single representative node from each connected
400 // component and also a parallel slice with the order, or number of nodes,
401 // in the corresponding component.
402 //
403 // This is fairly minimal information describing connected components.
404 // From a representative node, other nodes in the component can be reached
405 // by depth first traversal for example.
406 //
407 // There are equivalent labeled and unlabeled versions of this method.
408 //
409 // See also ConnectedComponentBits and ConnectedComponentLists which can
410 // collect component members in a single traversal, and IsConnected which
411 // is an even simpler boolean test.
412 func (g Undirected) ConnectedComponentReps() (reps []NI, orders []int) {
413 a := g.AdjacencyList
414 var c Bits
415 var o int
416 var df func(NI)
417 df = func(n NI) {
418 c.SetBit(n, 1)
419 o++
420 for _, nb := range a[n] {
421 if c.Bit(nb) == 0 {
422 df(nb)
423 }
424 }
425 return
426 }
427 for n := range a {
428 if c.Bit(NI(n)) == 0 {
429 reps = append(reps, NI(n))
430 o = 0
431 df(NI(n))
432 orders = append(orders, o)
433 }
434 }
435 return
436 }
437
438 // Copy makes a deep copy of g.
439 // Copy also computes the arc size ma, the number of arcs.
440 //
441 // There are equivalent labeled and unlabeled versions of this method.
442 func (g Undirected) Copy() (c Undirected, ma int) {
443 l, s := g.AdjacencyList.Copy()
444 return Undirected{l}, s
445 }
446
447 // Degeneracy computes k-degeneracy, vertex ordering and k-cores.
448 //
449 // See Wikipedia https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)
450 //
451 // There are equivalent labeled and unlabeled versions of this method.
452 func (g Undirected) Degeneracy() (k int, ordering []NI, cores []int) {
453 a := g.AdjacencyList
454 // WP algorithm
455 ordering = make([]NI, len(a))
456 var L Bits
457 d := make([]int, len(a))
458 var D [][]NI
459 for v, nb := range a {
460 dv := len(nb)
461 d[v] = dv
462 for len(D) <= dv {
463 D = append(D, nil)
464 }
465 D[dv] = append(D[dv], NI(v))
466 }
467 for ox := range a {
468 // find a non-empty D
469 i := 0
470 for len(D[i]) == 0 {
471 i++
472 }
473 // k is max(i, k)
474 if i > k {
475 for len(cores) <= i {
476 cores = append(cores, 0)
477 }
478 cores[k] = ox
479 k = i
480 }
481 // select from D[i]
482 Di := D[i]
483 last := len(Di) - 1
484 v := Di[last]
485 // Add v to ordering, remove from Di
486 ordering[ox] = v
487 L.SetBit(v, 1)
488 D[i] = Di[:last]
489 // move neighbors
490 for _, nb := range a[v] {
491 if L.Bit(nb) == 1 {
492 continue
493 }
494 dn := d[nb] // old number of neighbors of nb
495 Ddn := D[dn] // nb is in this list
496 // remove it from the list
497 for wx, w := range Ddn {
498 if w == nb {
499 last := len(Ddn) - 1
500 Ddn[wx], Ddn[last] = Ddn[last], Ddn[wx]
501 D[dn] = Ddn[:last]
502 }
503 }
504 dn-- // new number of neighbors
505 d[nb] = dn
506 // re--add it to it's new list
507 D[dn] = append(D[dn], nb)
508 }
509 }
510 cores[k] = len(ordering)
511 return
512 }
513
514 // Degree for undirected graphs, returns the degree of a node.
515 //
516 // The degree of a node in an undirected graph is the number of incident
517 // edges, where loops count twice.
518 //
519 // If g is known to be loop-free, the result is simply equivalent to len(g[n]).
520 // See handshaking lemma example at AdjacencyList.ArcSize.
521 //
522 // There are equivalent labeled and unlabeled versions of this method.
523 func (g Undirected) Degree(n NI) int {
524 to := g.AdjacencyList[n]
525 d := len(to) // just "out" degree,
526 for _, to := range to {
527 if to == n {
528 d++ // except loops count twice
529 }
530 }
531 return d
532 }
533
534 // FromList constructs a FromList representing the tree reachable from
535 // the given root.
536 //
537 // The connected component containing root should represent a simple graph,
538 // connected as a tree.
539 //
540 // For nodes connected as a tree, the Path member of the returned FromList
541 // will be populated with both From and Len values. The MaxLen member will be
542 // set but Leaves will be left a zero value. Return value cycle will be -1.
543 //
544 // If the connected component containing root is not connected as a tree,
545 // a cycle will be detected. The returned FromList will be a zero value and
546 // return value cycle will be a node involved in the cycle.
547 //
548 // Loops and parallel edges will be detected as cycles, however only in the
549 // connected component containing root. If g is not fully connected, nodes
550 // not reachable from root will have PathEnd values of {From: -1, Len: 0}.
551 //
552 // There are equivalent labeled and unlabeled versions of this method.
553 func (g Undirected) FromList(root NI) (f FromList, cycle NI) {
554 p := make([]PathEnd, len(g.AdjacencyList))
555 for i := range p {
556 p[i].From = -1
557 }
558 ml := 0
559 var df func(NI, NI) bool
560 df = func(fr, n NI) bool {
561 l := p[n].Len + 1
562 for _, to := range g.AdjacencyList[n] {
563 if to == fr {
564 continue
565 }
566 if p[to].Len > 0 {
567 cycle = to
568 return false
569 }
570 p[to] = PathEnd{From: n, Len: l}
571 if l > ml {
572 ml = l
573 }
574 if !df(n, to) {
575 return false
576 }
577 }
578 return true
579 }
580 p[root].Len = 1
581 if !df(-1, root) {
582 return
583 }
584 return FromList{Paths: p, MaxLen: ml}, -1
585 }
586
587 // IsConnected tests if an undirected graph is a single connected component.
588 //
589 // There are equivalent labeled and unlabeled versions of this method.
590 //
591 // See also ConnectedComponentReps for a method returning more information.
592 func (g Undirected) IsConnected() bool {
593 a := g.AdjacencyList
594 if len(a) == 0 {
595 return true
596 }
597 var b Bits
598 b.SetAll(len(a))
599 var df func(NI)
600 df = func(n NI) {
601 b.SetBit(n, 0)
602 for _, to := range a[n] {
603 if b.Bit(to) == 1 {
604 df(to)
605 }
606 }
607 }
608 df(0)
609 return b.Zero()
610 }
611
612 // IsTree identifies trees in undirected graphs.
613 //
614 // Return value isTree is true if the connected component reachable from root
615 // is a tree. Further, return value allTree is true if the entire graph g is
616 // connected.
617 //
618 // There are equivalent labeled and unlabeled versions of this method.
619 func (g Undirected) IsTree(root NI) (isTree, allTree bool) {
620 a := g.AdjacencyList
621 var v Bits
622 v.SetAll(len(a))
623 var df func(NI, NI) bool
624 df = func(fr, n NI) bool {
625 if v.Bit(n) == 0 {
626 return false
627 }
628 v.SetBit(n, 0)
629 for _, to := range a[n] {
630 if to != fr && !df(n, to) {
631 return false
632 }
633 }
634 return true
635 }
636 v.SetBit(root, 0)
637 for _, to := range a[root] {
638 if !df(root, to) {
639 return false, false
640 }
641 }
642 return true, v.Zero()
643 }
644
645 // Size returns the number of edges in g.
646 //
647 // See also ArcSize and HasLoop.
648 func (g Undirected) Size() int {
649 m2 := 0
650 for fr, to := range g.AdjacencyList {
651 m2 += len(to)
652 for _, to := range to {
653 if to == NI(fr) {
654 m2++
655 }
656 }
657 }
658 return m2 / 2
659 }