"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/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 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 }