"Fossies" - the Fresh Open Source Software Archive

Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/mst.go" (28 May 2021, 6668 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 import (
    7     "container/heap"
    8     "sort"
    9 )
   10 
   11 type dsElement struct {
   12     from NI
   13     rank int
   14 }
   15 
   16 type disjointSet struct {
   17     set []dsElement
   18 }
   19 
   20 func newDisjointSet(n int) disjointSet {
   21     set := make([]dsElement, n)
   22     for i := range set {
   23         set[i].from = -1
   24     }
   25     return disjointSet{set}
   26 }
   27 
   28 // return true if disjoint trees were combined.
   29 // false if x and y were already in the same tree.
   30 func (ds disjointSet) union(x, y NI) bool {
   31     xr := ds.find(x)
   32     yr := ds.find(y)
   33     if xr == yr {
   34         return false
   35     }
   36     switch xe, ye := &ds.set[xr], &ds.set[yr]; {
   37     case xe.rank < ye.rank:
   38         xe.from = yr
   39     case xe.rank == ye.rank:
   40         xe.rank++
   41         fallthrough
   42     default:
   43         ye.from = xr
   44     }
   45     return true
   46 }
   47 
   48 func (ds disjointSet) find(n NI) NI {
   49     // fast paths for n == root or from root.
   50     // no updates need in these cases.
   51     s := ds.set
   52     fr := s[n].from
   53     if fr < 0 { // n is root
   54         return n
   55     }
   56     n, fr = fr, s[fr].from
   57     if fr < 0 { // n is from root
   58         return n
   59     }
   60     // otherwise updates needed.
   61     // two iterative passes (rather than recursion or stack)
   62     // pass 1: find root
   63     r := fr
   64     for {
   65         f := s[r].from
   66         if f < 0 {
   67             break
   68         }
   69         r = f
   70     }
   71     // pass 2: update froms
   72     for {
   73         s[n].from = r
   74         if fr == r {
   75             return r
   76         }
   77         n = fr
   78         fr = s[n].from
   79     }
   80 }
   81 
   82 // Kruskal implements Kruskal's algorithm for constructing a minimum spanning
   83 // forest on an undirected graph.
   84 //
   85 // While the input graph is interpreted as undirected, the receiver edge list
   86 // does not actually need to contain reciprocal arcs.  A property of the
   87 // algorithm is that arc direction is ignored.  Thus only a single arc out of
   88 // a reciprocal pair must be present in the edge list.  Reciprocal arcs (and
   89 // parallel arcs) are allowed though, and do not affect the result.
   90 //
   91 // The forest is returned as an undirected graph.
   92 //
   93 // Also returned is a total distance for the returned forest.
   94 //
   95 // The edge list of the receiver is sorted as a side effect of this method.
   96 // See KruskalSorted for a version that relies on the edge list being already
   97 // sorted.
   98 func (l WeightedEdgeList) Kruskal() (g LabeledUndirected, dist float64) {
   99     sort.Sort(l)
  100     return l.KruskalSorted()
  101 }
  102 
  103 // KruskalSorted implements Kruskal's algorithm for constructing a minimum
  104 // spanning tree on an undirected graph.
  105 //
  106 // While the input graph is interpreted as undirected, the receiver edge list
  107 // does not actually need to contain reciprocal arcs.  A property of the
  108 // algorithm is that arc direction is ignored.  Thus only a single arc out of
  109 // a reciprocal pair must be present in the edge list.  Reciprocal arcs (and
  110 // parallel arcs) are allowed though, and do not affect the result.
  111 //
  112 // When called, the edge list of the receiver must be already sorted by weight.
  113 // See Kruskal for a version that accepts an unsorted edge list.
  114 //
  115 // The forest is returned as an undirected graph.
  116 //
  117 // Also returned is a total distance for the returned forest.
  118 func (l WeightedEdgeList) KruskalSorted() (g LabeledUndirected, dist float64) {
  119     ds := newDisjointSet(l.Order)
  120     g.LabeledAdjacencyList = make(LabeledAdjacencyList, l.Order)
  121     for _, e := range l.Edges {
  122         if ds.union(e.N1, e.N2) {
  123             g.AddEdge(Edge{e.N1, e.N2}, e.LI)
  124             dist += l.WeightFunc(e.LI)
  125         }
  126     }
  127     return
  128 }
  129 
  130 // Prim implements the Jarník-Prim-Dijkstra algorithm for constructing
  131 // a minimum spanning tree on an undirected graph.
  132 //
  133 // Prim computes a minimal spanning tree on the connected component containing
  134 // the given start node.  The tree is returned in FromList f.  Argument f
  135 // cannot be a nil pointer although it can point to a zero value FromList.
  136 //
  137 // If the passed FromList.Paths has the len of g though, it will be reused.
  138 // In the case of a graph with multiple connected components, this allows a
  139 // spanning forest to be accumulated by calling Prim successively on
  140 // representative nodes of the components.  In this case if leaves for
  141 // individual trees are of interest, pass a non-nil zero-value for the argument
  142 // componentLeaves and it will be populated with leaves for the single tree
  143 // spanned by the call.
  144 //
  145 // If argument labels is non-nil, it must have the same length as g and will
  146 // be populated with labels corresponding to the edges of the tree.
  147 //
  148 // Returned are the number of nodes spanned for the single tree (which will be
  149 // the order of the connected component) and the total spanned distance for the
  150 // single tree.
  151 func (g LabeledUndirected) Prim(start NI, w WeightFunc, f *FromList, labels []LI, componentLeaves *Bits) (numSpanned int, dist float64) {
  152     al := g.LabeledAdjacencyList
  153     if len(f.Paths) != len(al) {
  154         *f = NewFromList(len(al))
  155     }
  156     b := make([]prNode, len(al)) // "best"
  157     for n := range b {
  158         b[n].nx = NI(n)
  159         b[n].fx = -1
  160     }
  161     rp := f.Paths
  162     var frontier prHeap
  163     rp[start] = PathEnd{From: -1, Len: 1}
  164     numSpanned = 1
  165     fLeaves := &f.Leaves
  166     fLeaves.SetBit(start, 1)
  167     if componentLeaves != nil {
  168         componentLeaves.SetBit(start, 1)
  169     }
  170     for a := start; ; {
  171         for _, nb := range al[a] {
  172             if rp[nb.To].Len > 0 {
  173                 continue // already in MST, no action
  174             }
  175             switch bp := &b[nb.To]; {
  176             case bp.fx == -1: // new node for frontier
  177                 bp.from = fromHalf{From: a, Label: nb.Label}
  178                 bp.wt = w(nb.Label)
  179                 heap.Push(&frontier, bp)
  180             case w(nb.Label) < bp.wt: // better arc
  181                 bp.from = fromHalf{From: a, Label: nb.Label}
  182                 bp.wt = w(nb.Label)
  183                 heap.Fix(&frontier, bp.fx)
  184             }
  185         }
  186         if len(frontier) == 0 {
  187             break // done
  188         }
  189         bp := heap.Pop(&frontier).(*prNode)
  190         a = bp.nx
  191         rp[a].Len = rp[bp.from.From].Len + 1
  192         rp[a].From = bp.from.From
  193         if len(labels) != 0 {
  194             labels[a] = bp.from.Label
  195         }
  196         dist += bp.wt
  197         fLeaves.SetBit(bp.from.From, 0)
  198         fLeaves.SetBit(a, 1)
  199         if componentLeaves != nil {
  200             componentLeaves.SetBit(bp.from.From, 0)
  201             componentLeaves.SetBit(a, 1)
  202         }
  203         numSpanned++
  204     }
  205     return
  206 }
  207 
  208 // fromHalf is a half arc, representing a labeled arc and the "neighbor" node
  209 // that the arc originates from.
  210 //
  211 // (This used to be exported when there was a LabeledFromList.  Currently
  212 // unexported now that it seems to have much more limited use.)
  213 type fromHalf struct {
  214     From  NI
  215     Label LI
  216 }
  217 
  218 type prNode struct {
  219     nx   NI
  220     from fromHalf
  221     wt   float64 // p.Weight(from.Label)
  222     fx   int
  223 }
  224 
  225 type prHeap []*prNode
  226 
  227 func (h prHeap) Len() int           { return len(h) }
  228 func (h prHeap) Less(i, j int) bool { return h[i].wt < h[j].wt }
  229 func (h prHeap) Swap(i, j int) {
  230     h[i], h[j] = h[j], h[i]
  231     h[i].fx = i
  232     h[j].fx = j
  233 }
  234 func (p *prHeap) Push(x interface{}) {
  235     nd := x.(*prNode)
  236     nd.fx = len(*p)
  237     *p = append(*p, nd)
  238 }
  239 func (p *prHeap) Pop() interface{} {
  240     r := *p
  241     last := len(r) - 1
  242     *p = r[:last]
  243     return r[last]
  244 }