"Fossies" - the Fresh Open Source Software Archive 
Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/dir.go" (28 May 2021, 14722 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 // dir.go has methods specific to directed graphs, types Directed and
7 // LabeledDirected.
8 //
9 // Methods on Directed are first, with exported methods alphabetized.
10
11 import "errors"
12
13 // DAGMaxLenPath finds a maximum length path in a directed acyclic graph.
14 //
15 // Argument ordering must be a topological ordering of g.
16 func (g Directed) DAGMaxLenPath(ordering []NI) (path []NI) {
17 // dynamic programming. visit nodes in reverse order. for each, compute
18 // longest path as one plus longest of 'to' nodes.
19 // Visits each arc once. O(m).
20 //
21 // Similar code in label.go
22 var n NI
23 mlp := make([][]NI, len(g.AdjacencyList)) // index by node number
24 for i := len(ordering) - 1; i >= 0; i-- {
25 fr := ordering[i] // node number
26 to := g.AdjacencyList[fr]
27 if len(to) == 0 {
28 continue
29 }
30 mt := to[0]
31 for _, to := range to[1:] {
32 if len(mlp[to]) > len(mlp[mt]) {
33 mt = to
34 }
35 }
36 p := append([]NI{mt}, mlp[mt]...)
37 mlp[fr] = p
38 if len(p) > len(path) {
39 n = fr
40 path = p
41 }
42 }
43 return append([]NI{n}, path...)
44 }
45
46 // EulerianCycle finds an Eulerian cycle in a directed multigraph.
47 //
48 // * If g has no nodes, result is nil, nil.
49 //
50 // * If g is Eulerian, result is an Eulerian cycle with err = nil.
51 // The cycle result is a list of nodes, where the first and last
52 // nodes are the same.
53 //
54 // * Otherwise, result is nil, error
55 //
56 // Internally, EulerianCycle copies the entire graph g.
57 // See EulerianCycleD for a more space efficient version.
58 func (g Directed) EulerianCycle() ([]NI, error) {
59 c, m := g.Copy()
60 return c.EulerianCycleD(m)
61 }
62
63 // EulerianCycleD finds an Eulerian cycle in a directed multigraph.
64 //
65 // EulerianCycleD is destructive on its receiver g. See EulerianCycle for
66 // a non-destructive version.
67 //
68 // Argument ma must be the correct arc size, or number of arcs in g.
69 //
70 // * If g has no nodes, result is nil, nil.
71 //
72 // * If g is Eulerian, result is an Eulerian cycle with err = nil.
73 // The cycle result is a list of nodes, where the first and last
74 // nodes are the same.
75 //
76 // * Otherwise, result is nil, error
77 func (g Directed) EulerianCycleD(ma int) ([]NI, error) {
78 if len(g.AdjacencyList) == 0 {
79 return nil, nil
80 }
81 e := newEulerian(g.AdjacencyList, ma)
82 for e.s >= 0 {
83 v := e.top() // v is node that starts cycle
84 e.push()
85 // if Eulerian, we'll always come back to starting node
86 if e.top() != v {
87 return nil, errors.New("not balanced")
88 }
89 e.keep()
90 }
91 if !e.uv.Zero() {
92 return nil, errors.New("not strongly connected")
93 }
94 return e.p, nil
95 }
96
97 // EulerianPath finds an Eulerian path in a directed multigraph.
98 //
99 // * If g has no nodes, result is nil, nil.
100 //
101 // * If g has an Eulerian path, result is an Eulerian path with err = nil.
102 // The path result is a list of nodes, where the first node is start.
103 //
104 // * Otherwise, result is nil, error
105 //
106 // Internally, EulerianPath copies the entire graph g.
107 // See EulerianPathD for a more space efficient version.
108 func (g Directed) EulerianPath() ([]NI, error) {
109 ind := g.InDegree()
110 var start NI
111 for n, to := range g.AdjacencyList {
112 if len(to) > ind[n] {
113 start = NI(n)
114 break
115 }
116 }
117 c, m := g.Copy()
118 return c.EulerianPathD(m, start)
119 }
120
121 // EulerianPathD finds an Eulerian path in a directed multigraph.
122 //
123 // EulerianPathD is destructive on its receiver g. See EulerianPath for
124 // a non-destructive version.
125 //
126 // Argument ma must be the correct arc size, or number of arcs in g.
127 // Argument start must be a valid start node for the path.
128 //
129 // * If g has no nodes, result is nil, nil.
130 //
131 // * If g has an Eulerian path, result is an Eulerian path with err = nil.
132 // The path result is a list of nodes, where the first node is start.
133 //
134 // * Otherwise, result is nil, error
135 func (g Directed) EulerianPathD(ma int, start NI) ([]NI, error) {
136 if len(g.AdjacencyList) == 0 {
137 return nil, nil
138 }
139 e := newEulerian(g.AdjacencyList, ma)
140 e.p[0] = start
141 // unlike EulerianCycle, the first path doesn't have be a cycle.
142 e.push()
143 e.keep()
144 for e.s >= 0 {
145 start = e.top()
146 e.push()
147 // paths after the first must be cycles though
148 // (as long as there are nodes on the stack)
149 if e.top() != start {
150 return nil, errors.New("no Eulerian path")
151 }
152 e.keep()
153 }
154 if !e.uv.Zero() {
155 return nil, errors.New("no Eulerian path")
156 }
157 return e.p, nil
158 }
159
160 // starting at the node on the top of the stack, follow arcs until stuck.
161 // mark nodes visited, push nodes on stack, remove arcs from g.
162 func (e *eulerian) push() {
163 for u := e.top(); ; {
164 e.uv.SetBit(u, 0) // reset unvisited bit
165 arcs := e.g[u]
166 if len(arcs) == 0 {
167 return // stuck
168 }
169 w := arcs[0] // follow first arc
170 e.s++ // push followed node on stack
171 e.p[e.s] = w
172 e.g[u] = arcs[1:] // consume arc
173 u = w
174 }
175 }
176
177 // like push, but for for undirected graphs.
178 func (e *eulerian) pushUndir() {
179 for u := e.top(); ; {
180 e.uv.SetBit(u, 0)
181 arcs := e.g[u]
182 if len(arcs) == 0 {
183 return
184 }
185 w := arcs[0]
186 e.s++
187 e.p[e.s] = w
188 e.g[u] = arcs[1:] // consume arc
189 // here is the only difference, consume reciprocal arc as well:
190 a2 := e.g[w]
191 for x, rx := range a2 {
192 if rx == u { // here it is
193 last := len(a2) - 1
194 a2[x] = a2[last] // someone else gets the seat
195 e.g[w] = a2[:last] // and it's gone.
196 break
197 }
198 }
199 u = w
200 }
201 }
202
203 // starting with the node on top of the stack, move nodes with no arcs.
204 func (e *eulerian) keep() {
205 for e.s >= 0 {
206 n := e.top()
207 if len(e.g[n]) > 0 {
208 break
209 }
210 e.p[e.m] = n
211 e.s--
212 e.m--
213 }
214 }
215
216 type eulerian struct {
217 g AdjacencyList // working copy of graph, it gets consumed
218 m int // number of arcs in g, updated as g is consumed
219 uv Bits // unvisited
220 // low end of p is stack of unfinished nodes
221 // high end is finished path
222 p []NI // stack + path
223 s int // stack pointer
224 }
225
226 func (e *eulerian) top() NI {
227 return e.p[e.s]
228 }
229
230 func newEulerian(g AdjacencyList, m int) *eulerian {
231 e := &eulerian{
232 g: g,
233 m: m,
234 p: make([]NI, m+1),
235 }
236 e.uv.SetAll(len(g))
237 return e
238 }
239
240 // MaximalNonBranchingPaths finds all paths in a directed graph that are
241 // "maximal" and "non-branching".
242 //
243 // A non-branching path is one where path nodes other than the first and last
244 // have exactly one arc leading to the node and one arc leading from the node,
245 // thus there is no possibility to branch away to a different path.
246 //
247 // A maximal non-branching path cannot be extended to a longer non-branching
248 // path by including another node at either end.
249 //
250 // In the case of a cyclic non-branching path, the first and last elements
251 // of the path will be the same node, indicating an isolated cycle.
252 //
253 // The method calls the emit argument for each path or isolated cycle in g,
254 // as long as emit returns true. If emit returns false,
255 // MaximalNonBranchingPaths returns immediately.
256 func (g Directed) MaximalNonBranchingPaths(emit func([]NI) bool) {
257 ind := g.InDegree()
258 var uv Bits
259 uv.SetAll(len(g.AdjacencyList))
260 for v, vTo := range g.AdjacencyList {
261 if !(ind[v] == 1 && len(vTo) == 1) {
262 for _, w := range vTo {
263 n := []NI{NI(v), w}
264 uv.SetBit(NI(v), 0)
265 uv.SetBit(w, 0)
266 wTo := g.AdjacencyList[w]
267 for ind[w] == 1 && len(wTo) == 1 {
268 u := wTo[0]
269 n = append(n, u)
270 uv.SetBit(u, 0)
271 w = u
272 wTo = g.AdjacencyList[w]
273 }
274 if !emit(n) { // n is a path
275 return
276 }
277 }
278 }
279 }
280 // use uv.From rather than uv.Iterate.
281 // Iterate doesn't work here because we're modifying uv
282 for b := uv.From(0); b >= 0; b = uv.From(b + 1) {
283 v := NI(b)
284 n := []NI{v}
285 for w := v; ; {
286 w = g.AdjacencyList[w][0]
287 uv.SetBit(w, 0)
288 n = append(n, w)
289 if w == v {
290 break
291 }
292 }
293 if !emit(n) { // n is an isolated cycle
294 return
295 }
296 }
297 }
298
299 // Undirected returns copy of g augmented as needed to make it undirected.
300 func (g Directed) Undirected() Undirected {
301 c, _ := g.AdjacencyList.Copy() // start with a copy
302 rw := make(AdjacencyList, len(g.AdjacencyList)) // "reciprocals wanted"
303 for fr, to := range g.AdjacencyList {
304 arc: // for each arc in g
305 for _, to := range to {
306 if to == NI(fr) {
307 continue // loop
308 }
309 // search wanted arcs
310 wf := rw[fr]
311 for i, w := range wf {
312 if w == to { // found, remove
313 last := len(wf) - 1
314 wf[i] = wf[last]
315 rw[fr] = wf[:last]
316 continue arc
317 }
318 }
319 // arc not found, add to reciprocal to wanted list
320 rw[to] = append(rw[to], NI(fr))
321 }
322 }
323 // add missing reciprocals
324 for fr, to := range rw {
325 c[fr] = append(c[fr], to...)
326 }
327 return Undirected{c}
328 }
329
330 // StronglyConnectedComponents identifies strongly connected components
331 // in a directed graph.
332 //
333 // Algorithm by David J. Pearce, from "An Improved Algorithm for Finding the
334 // Strongly Connected Components of a Directed Graph". It is algorithm 3,
335 // PEA_FIND_SCC2 in
336 // http://homepages.mcs.vuw.ac.nz/~djp/files/P05.pdf, accessed 22 Feb 2015.
337 //
338 // Returned is a list of components, each component is a list of nodes.
339 /*
340 func (g Directed) StronglyConnectedComponents() []int {
341 rindex := make([]int, len(g))
342 S := []int{}
343 index := 1
344 c := len(g) - 1
345 visit := func(v int) {
346 root := true
347 rindex[v] = index
348 index++
349 for _, w := range g[v] {
350 if rindex[w] == 0 {
351 visit(w)
352 }
353 if rindex[w] < rindex[v] {
354 rindex[v] = rindex[w]
355 root = false
356 }
357 }
358 if root {
359 index--
360 for top := len(S) - 1; top >= 0 && rindex[v] <= rindex[top]; top-- {
361 w = rindex[top]
362 S = S[:top]
363 rindex[w] = c
364 index--
365 }
366 rindex[v] = c
367 c--
368 } else {
369 S = append(S, v)
370 }
371 }
372 for v := range g {
373 if rindex[v] == 0 {
374 visit(v)
375 }
376 }
377 return rindex
378 }
379 */
380
381 // Transpose constructs a new adjacency list with all arcs reversed.
382 //
383 // For every arc from->to of g, the result will have an arc to->from.
384 // Transpose also counts arcs as it traverses and returns ma the number of arcs
385 // in g (equal to the number of arcs in the result.)
386 func (g Directed) Transpose() (t Directed, ma int) {
387 ta := make(AdjacencyList, len(g.AdjacencyList))
388 for n, nbs := range g.AdjacencyList {
389 for _, nb := range nbs {
390 ta[nb] = append(ta[nb], NI(n))
391 ma++
392 }
393 }
394 return Directed{ta}, ma
395 }
396
397 // DAGMaxLenPath finds a maximum length path in a directed acyclic graph.
398 //
399 // Length here means number of nodes or arcs, not a sum of arc weights.
400 //
401 // Argument ordering must be a topological ordering of g.
402 //
403 // Returned is a node beginning a maximum length path, and a path of arcs
404 // starting from that node.
405 func (g LabeledDirected) DAGMaxLenPath(ordering []NI) (n NI, path []Half) {
406 // dynamic programming. visit nodes in reverse order. for each, compute
407 // longest path as one plus longest of 'to' nodes.
408 // Visits each arc once. Time complexity O(m).
409 //
410 // Similar code in dir.go.
411 mlp := make([][]Half, len(g.LabeledAdjacencyList)) // index by node number
412 for i := len(ordering) - 1; i >= 0; i-- {
413 fr := ordering[i] // node number
414 to := g.LabeledAdjacencyList[fr]
415 if len(to) == 0 {
416 continue
417 }
418 mt := to[0]
419 for _, to := range to[1:] {
420 if len(mlp[to.To]) > len(mlp[mt.To]) {
421 mt = to
422 }
423 }
424 p := append([]Half{mt}, mlp[mt.To]...)
425 mlp[fr] = p
426 if len(p) > len(path) {
427 n = fr
428 path = p
429 }
430 }
431 return
432 }
433
434 // FromListLabels transposes a labeled graph into a FromList and associated
435 // list of labels.
436 //
437 // Receiver g should be connected as a tree or forest. Specifically no node
438 // can have multiple incoming arcs. If any node n in g has multiple incoming
439 // arcs, the method returns (nil, nil, n) where n is a node with multiple
440 // incoming arcs.
441 //
442 // Otherwise (normally) the method populates the From members in a
443 // FromList.Path, populates a slice of labels, and returns the FromList,
444 // labels, and -1.
445 //
446 // Other members of the FromList are left as zero values.
447 // Use FromList.RecalcLen and FromList.RecalcLeaves as needed.
448 func (g LabeledDirected) FromListLabels() (*FromList, []LI, NI) {
449 labels := make([]LI, len(g.LabeledAdjacencyList))
450 paths := make([]PathEnd, len(g.LabeledAdjacencyList))
451 for i := range paths {
452 paths[i].From = -1
453 }
454 for fr, to := range g.LabeledAdjacencyList {
455 for _, to := range to {
456 if paths[to.To].From >= 0 {
457 return nil, nil, to.To
458 }
459 paths[to.To].From = NI(fr)
460 labels[to.To] = to.Label
461 }
462 }
463 return &FromList{Paths: paths}, labels, -1
464 }
465
466 // Transpose constructs a new adjacency list that is the transpose of g.
467 //
468 // For every arc from->to of g, the result will have an arc to->from.
469 // Transpose also counts arcs as it traverses and returns ma the number of
470 // arcs in g (equal to the number of arcs in the result.)
471 func (g LabeledDirected) Transpose() (t LabeledDirected, ma int) {
472 ta := make(LabeledAdjacencyList, len(g.LabeledAdjacencyList))
473 for n, nbs := range g.LabeledAdjacencyList {
474 for _, nb := range nbs {
475 ta[nb.To] = append(ta[nb.To], Half{To: NI(n), Label: nb.Label})
476 ma++
477 }
478 }
479 return LabeledDirected{ta}, ma
480 }
481
482 // Undirected returns a new undirected graph derived from g, augmented as
483 // needed to make it undirected, with reciprocal arcs having matching labels.
484 func (g LabeledDirected) Undirected() LabeledUndirected {
485 c, _ := g.LabeledAdjacencyList.Copy() // start with a copy
486 // "reciprocals wanted"
487 rw := make(LabeledAdjacencyList, len(g.LabeledAdjacencyList))
488 for fr, to := range g.LabeledAdjacencyList {
489 arc: // for each arc in g
490 for _, to := range to {
491 if to.To == NI(fr) {
492 continue // arc is a loop
493 }
494 // search wanted arcs
495 wf := rw[fr]
496 for i, w := range wf {
497 if w == to { // found, remove
498 last := len(wf) - 1
499 wf[i] = wf[last]
500 rw[fr] = wf[:last]
501 continue arc
502 }
503 }
504 // arc not found, add to reciprocal to wanted list
505 rw[to.To] = append(rw[to.To], Half{To: NI(fr), Label: to.Label})
506 }
507 }
508 // add missing reciprocals
509 for fr, to := range rw {
510 c[fr] = append(c[fr], to...)
511 }
512 return LabeledUndirected{c}
513 }
514
515 // Unlabeled constructs the unlabeled directed graph corresponding to g.
516 func (g LabeledDirected) Unlabeled() Directed {
517 return Directed{g.LabeledAdjacencyList.Unlabeled()}
518 }
519
520 // UnlabeledTranspose constructs a new adjacency list that is the unlabeled
521 // transpose of g.
522 //
523 // For every arc from->to of g, the result will have an arc to->from.
524 // Transpose also counts arcs as it traverses and returns ma, the number of
525 // arcs in g (equal to the number of arcs in the result.)
526 //
527 // It is equivalent to g.Unlabeled().Transpose() but constructs the result
528 // directly.
529 func (g LabeledDirected) UnlabeledTranspose() (t Directed, ma int) {
530 ta := make(AdjacencyList, len(g.LabeledAdjacencyList))
531 for n, nbs := range g.LabeledAdjacencyList {
532 for _, nb := range nbs {
533 ta[nb.To] = append(ta[nb.To], NI(n))
534 ma++
535 }
536 }
537 return Directed{ta}, ma
538 }