gdrive-2.1.1.tar.gz: .../graph/fromlist.go

"Fossies" - the Fresh Open Source Software Archive

Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/fromlist.go" (28 May 2021, 11916 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 // FromList represents a rooted tree (or forest) where each node is associated 7 // with a half arc identifying an arc "from" another node. 8 // 9 // Other terms for this data structure include "parent list", 10 // "predecessor list", "in-tree", "inverse arborescence", and 11 // "spaghetti stack." 12 // 13 // The Paths member represents the tree structure. Leaves and MaxLen are 14 // not always needed. Where Leaves is used it serves as a bitmap where 15 // Leaves.Bit(n) == 1 for each leaf n of the tree. Where MaxLen is used it is 16 // provided primarily as a convenience for functions that might want to 17 // anticipate the maximum path length that would be encountered traversing 18 // the tree. 19 // 20 // Various graph search methods use a FromList to returns search results. 21 // For a start node of a search, From will be -1 and Len will be 1. For other 22 // nodes reached by the search, From represents a half arc in a path back to 23 // start and Len represents the number of nodes in the path. For nodes not 24 // reached by the search, From will be -1 and Len will be 0. 25 // 26 // A single FromList can also represent a forest. In this case paths from 27 // all leaves do not return to a single root node, but multiple root nodes. 28 // 29 // While a FromList generally encodes a tree or forest, it is technically 30 // possible to encode a cyclic graph. A number of FromList methods require 31 // the receiver to be acyclic. Graph methods documented to return a tree or 32 // forest will never return a cyclic FromList. In other cases however, 33 // where a FromList is not known to by cyclic, the Cyclic method can be 34 // useful to validate the acyclic property. 35 type FromList struct { 36 Paths []PathEnd // tree representation 37 Leaves Bits // leaves of tree 38 MaxLen int // length of longest path, max of all PathEnd.Len values 39 } 40 41 // PathEnd associates a half arc and a path length. 42 // 43 // A PathEnd list is an element type of FromList. 44 type PathEnd struct { 45 From NI // a "from" half arc, the node the arc comes from 46 Len int // number of nodes in path from start 47 } 48 49 // NewFromList creates a FromList object of given order. 50 // 51 // The Paths member is allocated to length n but there is no other 52 // initialization. 53 func NewFromList(n int) FromList { 54 return FromList{Paths: make([]PathEnd, n)} 55 } 56 57 // BoundsOk validates the "from" values in the list. 58 // 59 // Negative values are allowed as they indicate root nodes. 60 // 61 // BoundsOk returns true when all from values are less than len(t). 62 // Otherwise it returns false and a node with a from value >= len(t). 63 func (f FromList) BoundsOk() (ok bool, n NI) { 64 for n, e := range f.Paths { 65 if int(e.From) >= len(f.Paths) { 66 return false, NI(n) 67 } 68 } 69 return true, -1 70 } 71 72 // CommonStart returns the common start node of minimal paths to a and b. 73 // 74 // It returns -1 if a and b cannot be traced back to a common node. 75 // 76 // The method relies on populated PathEnd.Len members. Use RecalcLen if 77 // the Len members are not known to be present and correct. 78 func (f FromList) CommonStart(a, b NI) NI { 79 p := f.Paths 80 if p[a].Len < p[b].Len { 81 a, b = b, a 82 } 83 for bl := p[b].Len; p[a].Len > bl; { 84 a = p[a].From 85 if a < 0 { 86 return -1 87 } 88 } 89 for a != b { 90 a = p[a].From 91 if a < 0 { 92 return -1 93 } 94 b = p[b].From 95 } 96 return a 97 } 98 99 // Cyclic determines if f contains a cycle, a non-empty path from a node 100 // back to itself. 101 // 102 // Cyclic returns true if g contains at least one cycle. It also returns 103 // an example of a node involved in a cycle. 104 // 105 // Cyclic returns (false, -1) in the normal case where f is acyclic. 106 // Note that the bool is not an "ok" return. A cyclic FromList is usually 107 // not okay. 108 func (f FromList) Cyclic() (cyclic bool, n NI) { 109 var vis Bits 110 p := f.Paths 111 for i := range p { 112 var path Bits 113 for n := NI(i); vis.Bit(n) == 0; { 114 vis.SetBit(n, 1) 115 path.SetBit(n, 1) 116 if n = p[n].From; n < 0 { 117 break 118 } 119 if path.Bit(n) == 1 { 120 return true, n 121 } 122 } 123 } 124 return false, -1 125 } 126 127 // IsolatedNodeBits returns a bitmap of isolated nodes in receiver graph f. 128 // 129 // An isolated node is one with no arcs going to or from it. 130 func (f FromList) IsolatedNodes() (iso Bits) { 131 p := f.Paths 132 iso.SetAll(len(p)) 133 for n, e := range p { 134 if e.From >= 0 { 135 iso.SetBit(NI(n), 0) 136 iso.SetBit(e.From, 0) 137 } 138 } 139 return 140 } 141 142 // PathTo decodes a FromList, recovering a single path. 143 // 144 // The path is returned as a list of nodes where the first element will be 145 // a root node and the last element will be the specified end node. 146 // 147 // Only the Paths member of the receiver is used. Other members of the 148 // FromList do not need to be valid, however the MaxLen member can be useful 149 // for allocating argument p. 150 // 151 // Argument p can provide the result slice. If p has capacity for the result 152 // it will be used, otherwise a new slice is created for the result. 153 // 154 // See also function PathTo. 155 func (f FromList) PathTo(end NI, p []NI) []NI { 156 return PathTo(f.Paths, end, p) 157 } 158 159 // PathTo decodes a single path from a PathEnd list. 160 // 161 // A PathEnd list is the main data representation in a FromList. See FromList. 162 // 163 // PathTo returns a list of nodes where the first element will be 164 // a root node and the last element will be the specified end node. 165 // 166 // Argument p can provide the result slice. If p has capacity for the result 167 // it will be used, otherwise a new slice is created for the result. 168 // 169 // See also method FromList.PathTo. 170 func PathTo(paths []PathEnd, end NI, p []NI) []NI { 171 n := paths[end].Len 172 if n == 0 { 173 return nil 174 } 175 if cap(p) >= n { 176 p = p[:n] 177 } else { 178 p = make([]NI, n) 179 } 180 for { 181 n-- 182 p[n] = end 183 if n == 0 { 184 return p 185 } 186 end = paths[end].From 187 } 188 } 189 190 // Preorder traverses f calling Visitor v in preorder. 191 // 192 // Nodes are visited in order such that for any node n with from node fr, 193 // fr is visited before n. Where f represents a tree, the visit ordering 194 // corresponds to a preordering, or depth first traversal of the tree. 195 // Where f represents a forest, the preorderings of the trees can be 196 // intermingled. 197 // 198 // Leaves must be set correctly first. Use RecalcLeaves if leaves are not 199 // known to be set correctly. FromList f cannot be cyclic. 200 // 201 // Traversal continues while v returns true. It terminates if v returns false. 202 // Preorder returns true if it completes without v returning false. Preorder 203 // returns false if traversal is terminated by v returning false. 204 func (f FromList) Preorder(v OkNodeVisitor) bool { 205 p := f.Paths 206 var done Bits 207 var df func(NI) bool 208 df = func(n NI) bool { 209 done.SetBit(n, 1) 210 if fr := p[n].From; fr >= 0 && done.Bit(fr) == 0 { 211 df(fr) 212 } 213 return v(n) 214 } 215 for n := range f.Paths { 216 p[n].Len = 0 217 } 218 return f.Leaves.Iterate(func(n NI) bool { 219 return df(n) 220 }) 221 } 222 223 // RecalcLeaves recomputes the Leaves member of f. 224 func (f *FromList) RecalcLeaves() { 225 p := f.Paths 226 lv := &f.Leaves 227 lv.SetAll(len(p)) 228 for n := range f.Paths { 229 if fr := p[n].From; fr >= 0 { 230 lv.SetBit(fr, 0) 231 } 232 } 233 } 234 235 // RecalcLen recomputes Len for each path end, and recomputes MaxLen. 236 // 237 // RecalcLen relies on the Leaves member being valid. If it is not known 238 // to be valid, call RecalcLeaves before calling RecalcLen. 239 func (f *FromList) RecalcLen() { 240 p := f.Paths 241 var setLen func(NI) int 242 setLen = func(n NI) int { 243 switch { 244 case p[n].Len > 0: 245 return p[n].Len 246 case p[n].From < 0: 247 p[n].Len = 1 248 return 1 249 } 250 l := 1 + setLen(p[n].From) 251 p[n].Len = l 252 return l 253 } 254 for n := range f.Paths { 255 p[n].Len = 0 256 } 257 f.MaxLen = 0 258 f.Leaves.Iterate(func(n NI) bool { 259 if l := setLen(NI(n)); l > f.MaxLen { 260 f.MaxLen = l 261 } 262 return true 263 }) 264 } 265 266 // ReRoot reorients the tree containing n to make n the root node. 267 // 268 // It keeps the tree connected by "reversing" the path from n to the old root. 269 // 270 // After ReRoot, the Leaves and Len members are invalid. 271 // Call RecalcLeaves or RecalcLen as needed. 272 func (f *FromList) ReRoot(n NI) { 273 p := f.Paths 274 fr := p[n].From 275 if fr < 0 { 276 return 277 } 278 p[n].From = -1 279 for { 280 ff := p[fr].From 281 p[fr].From = n 282 if ff < 0 { 283 return 284 } 285 n = fr 286 fr = ff 287 } 288 } 289 290 // Root finds the root of a node in a FromList. 291 func (f FromList) Root(n NI) NI { 292 for p := f.Paths; ; { 293 fr := p[n].From 294 if fr < 0 { 295 return n 296 } 297 n = fr 298 } 299 } 300 301 // Transpose constructs the directed graph corresponding to FromList f 302 // but with arcs in the opposite direction. That is, from roots toward leaves. 303 // 304 // The method relies only on the From member of f.Paths. Other members of 305 // the FromList are not used. 306 // 307 // See FromList.TransposeRoots for a version that also accumulates and returns 308 // information about the roots. 309 func (f FromList) Transpose() Directed { 310 g := make(AdjacencyList, len(f.Paths)) 311 for n, p := range f.Paths { 312 if p.From == -1 { 313 continue 314 } 315 g[p.From] = append(g[p.From], NI(n)) 316 } 317 return Directed{g} 318 } 319 320 // TransposeLabeled constructs the directed labeled graph corresponding 321 // to FromList f but with arcs in the opposite direction. That is, from 322 // roots toward leaves. 323 // 324 // The argument labels can be nil. In this case labels are generated matching 325 // the path indexes. This corresponds to the "to", or child node. 326 // 327 // If labels is non-nil, it must be the same length as f.Paths and is used 328 // to look up label numbers by the path index. 329 // 330 // The method relies only on the From member of f.Paths. Other members of 331 // the FromList are not used. 332 // 333 // See FromList.TransposeLabeledRoots for a version that also accumulates 334 // and returns information about the roots. 335 func (f FromList) TransposeLabeled(labels []LI) LabeledDirected { 336 g := make(LabeledAdjacencyList, len(f.Paths)) 337 for n, p := range f.Paths { 338 if p.From == -1 { 339 continue 340 } 341 l := LI(n) 342 if labels != nil { 343 l = labels[n] 344 } 345 g[p.From] = append(g[p.From], Half{NI(n), l}) 346 } 347 return LabeledDirected{g} 348 } 349 350 // TransposeLabeledRoots constructs the labeled directed graph corresponding 351 // to FromList f but with arcs in the opposite direction. That is, from 352 // roots toward leaves. 353 // 354 // TransposeLabeledRoots also returns a count of roots of the resulting forest 355 // and a bitmap of the roots. 356 // 357 // The argument labels can be nil. In this case labels are generated matching 358 // the path indexes. This corresponds to the "to", or child node. 359 // 360 // If labels is non-nil, it must be the same length as t.Paths and is used 361 // to look up label numbers by the path index. 362 // 363 // The method relies only on the From member of f.Paths. Other members of 364 // the FromList are not used. 365 // 366 // See FromList.TransposeLabeled for a simpler verstion that returns the 367 // forest only. 368 func (f FromList) TransposeLabeledRoots(labels []LI) (forest LabeledDirected, nRoots int, roots Bits) { 369 p := f.Paths 370 nRoots = len(p) 371 roots.SetAll(len(p)) 372 g := make(LabeledAdjacencyList, len(p)) 373 for i, p := range f.Paths { 374 if p.From == -1 { 375 continue 376 } 377 l := LI(i) 378 if labels != nil { 379 l = labels[i] 380 } 381 n := NI(i) 382 g[p.From] = append(g[p.From], Half{n, l}) 383 if roots.Bit(n) == 1 { 384 roots.SetBit(n, 0) 385 nRoots-- 386 } 387 } 388 return LabeledDirected{g}, nRoots, roots 389 } 390 391 // TransposeRoots constructs the directed graph corresponding to FromList f 392 // but with arcs in the opposite direction. That is, from roots toward leaves. 393 // 394 // TransposeRoots also returns a count of roots of the resulting forest and 395 // a bitmap of the roots. 396 // 397 // The method relies only on the From member of f.Paths. Other members of 398 // the FromList are not used. 399 // 400 // See FromList.Transpose for a simpler verstion that returns the forest only. 401 func (f FromList) TransposeRoots() (forest Directed, nRoots int, roots Bits) { 402 p := f.Paths 403 nRoots = len(p) 404 roots.SetAll(len(p)) 405 g := make(AdjacencyList, len(p)) 406 for i, e := range p { 407 if e.From == -1 { 408 continue 409 } 410 n := NI(i) 411 g[e.From] = append(g[e.From], n) 412 if roots.Bit(n) == 1 { 413 roots.SetBit(n, 0) 414 nRoots-- 415 } 416 } 417 return Directed{g}, nRoots, roots 418 }