"Fossies" - the Fresh Open Source Software Archive 
Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/dir_cg.go" (28 May 2021, 10847 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_RO.go is code generated from dir_cg.go by directives in graph.go.
7 // Editing dir_cg.go is okay. It is the code generation source.
8 // DO NOT EDIT dir_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 // Balanced returns true if for every node in g, in-degree equals out-degree.
13 //
14 // There are equivalent labeled and unlabeled versions of this method.
15 func (g LabeledDirected) Balanced() bool {
16 for n, in := range g.InDegree() {
17 if in != len(g.LabeledAdjacencyList[n]) {
18 return false
19 }
20 }
21 return true
22 }
23
24 // Copy makes a deep copy of g.
25 // Copy also computes the arc size ma, the number of arcs.
26 //
27 // There are equivalent labeled and unlabeled versions of this method.
28 func (g LabeledDirected) Copy() (c LabeledDirected, ma int) {
29 l, s := g.LabeledAdjacencyList.Copy()
30 return LabeledDirected{l}, s
31 }
32
33 // Cyclic determines if g contains a cycle, a non-empty path from a node
34 // back to itself.
35 //
36 // Cyclic returns true if g contains at least one cycle. It also returns
37 // an example of an arc involved in a cycle.
38 // Cyclic returns false if g is acyclic.
39 //
40 // Also see Topological, which detects cycles.
41 //
42 // There are equivalent labeled and unlabeled versions of this method.
43 func (g LabeledDirected) Cyclic() (cyclic bool, fr NI, to Half) {
44 a := g.LabeledAdjacencyList
45 fr, to.To = -1, -1
46 var temp, perm Bits
47 var df func(NI)
48 df = func(n NI) {
49 switch {
50 case temp.Bit(n) == 1:
51 cyclic = true
52 return
53 case perm.Bit(n) == 1:
54 return
55 }
56 temp.SetBit(n, 1)
57 for _, nb := range a[n] {
58 df(nb.To)
59 if cyclic {
60 if fr < 0 {
61 fr, to = n, nb
62 }
63 return
64 }
65 }
66 temp.SetBit(n, 0)
67 perm.SetBit(n, 1)
68 }
69 for n := range a {
70 if perm.Bit(NI(n)) == 1 {
71 continue
72 }
73 if df(NI(n)); cyclic { // short circuit as soon as a cycle is found
74 break
75 }
76 }
77 return
78 }
79
80 // FromList transposes a labeled graph into a FromList.
81 //
82 // Receiver g should be connected as a tree or forest. Specifically no node
83 // can have multiple incoming arcs. If any node n in g has multiple incoming
84 // arcs, the method returns (nil, n) where n is a node with multiple
85 // incoming arcs.
86 //
87 // Otherwise (normally) the method populates the From members in a
88 // FromList.Path and returns the FromList and -1.
89 //
90 // Other members of the FromList are left as zero values.
91 // Use FromList.RecalcLen and FromList.RecalcLeaves as needed.
92 //
93 // Unusual cases are parallel arcs and loops. A parallel arc represents
94 // a case of multiple arcs going to some node and so will lead to a (nil, n)
95 // return, even though a graph might be considered a multigraph tree.
96 // A single loop on a node that would otherwise be a root node, though,
97 // is not a case of multiple incoming arcs and so does not force a (nil, n)
98 // result.
99 //
100 // There are equivalent labeled and unlabeled versions of this method.
101 func (g LabeledDirected) FromList() (*FromList, NI) {
102 paths := make([]PathEnd, len(g.LabeledAdjacencyList))
103 for i := range paths {
104 paths[i].From = -1
105 }
106 for fr, to := range g.LabeledAdjacencyList {
107 for _, to := range to {
108 if paths[to.To].From >= 0 {
109 return nil, to.To
110 }
111 paths[to.To].From = NI(fr)
112 }
113 }
114 return &FromList{Paths: paths}, -1
115 }
116
117 // InDegree computes the in-degree of each node in g
118 //
119 // There are equivalent labeled and unlabeled versions of this method.
120 func (g LabeledDirected) InDegree() []int {
121 ind := make([]int, len(g.LabeledAdjacencyList))
122 for _, nbs := range g.LabeledAdjacencyList {
123 for _, nb := range nbs {
124 ind[nb.To]++
125 }
126 }
127 return ind
128 }
129
130 // IsTree identifies trees in directed graphs.
131 //
132 // Return value isTree is true if the subgraph reachable from root is a tree.
133 // Further, return value allTree is true if the entire graph g is reachable
134 // from root.
135 //
136 // There are equivalent labeled and unlabeled versions of this method.
137 func (g LabeledDirected) IsTree(root NI) (isTree, allTree bool) {
138 a := g.LabeledAdjacencyList
139 var v Bits
140 v.SetAll(len(a))
141 var df func(NI) bool
142 df = func(n NI) bool {
143 if v.Bit(n) == 0 {
144 return false
145 }
146 v.SetBit(n, 0)
147 for _, to := range a[n] {
148 if !df(to.To) {
149 return false
150 }
151 }
152 return true
153 }
154 isTree = df(root)
155 return isTree, isTree && v.Zero()
156 }
157
158 // Tarjan identifies strongly connected components in a directed graph using
159 // Tarjan's algorithm.
160 //
161 // The method calls the emit argument for each component identified. Each
162 // component is a list of nodes. A property of the algorithm is that
163 // components are emitted in reverse topological order of the condensation.
164 // (See https://en.wikipedia.org/wiki/Strongly_connected_component#Definitions
165 // for description of condensation.)
166 //
167 // There are equivalent labeled and unlabeled versions of this method.
168 //
169 // See also TarjanForward and TarjanCondensation.
170 func (g LabeledDirected) Tarjan(emit func([]NI) bool) {
171 // See "Depth-first search and linear graph algorithms", Robert Tarjan,
172 // SIAM J. Comput. Vol. 1, No. 2, June 1972.
173 //
174 // Implementation here from Wikipedia pseudocode,
175 // http://en.wikipedia.org/w/index.php?title=Tarjan%27s_strongly_connected_components_algorithm&direction=prev&oldid=647184742
176 var indexed, stacked Bits
177 a := g.LabeledAdjacencyList
178 index := make([]int, len(a))
179 lowlink := make([]int, len(a))
180 x := 0
181 var S []NI
182 var sc func(NI) bool
183 sc = func(n NI) bool {
184 index[n] = x
185 indexed.SetBit(n, 1)
186 lowlink[n] = x
187 x++
188 S = append(S, n)
189 stacked.SetBit(n, 1)
190 for _, nb := range a[n] {
191 if indexed.Bit(nb.To) == 0 {
192 if !sc(nb.To) {
193 return false
194 }
195 if lowlink[nb.To] < lowlink[n] {
196 lowlink[n] = lowlink[nb.To]
197 }
198 } else if stacked.Bit(nb.To) == 1 {
199 if index[nb.To] < lowlink[n] {
200 lowlink[n] = index[nb.To]
201 }
202 }
203 }
204 if lowlink[n] == index[n] {
205 var c []NI
206 for {
207 last := len(S) - 1
208 w := S[last]
209 S = S[:last]
210 stacked.SetBit(w, 0)
211 c = append(c, w)
212 if w == n {
213 if !emit(c) {
214 return false
215 }
216 break
217 }
218 }
219 }
220 return true
221 }
222 for n := range a {
223 if indexed.Bit(NI(n)) == 0 && !sc(NI(n)) {
224 return
225 }
226 }
227 }
228
229 // TarjanForward returns strongly connected components.
230 //
231 // It returns components in the reverse order of Tarjan, for situations
232 // where a forward topological ordering is easier.
233 func (g LabeledDirected) TarjanForward() [][]NI {
234 var r [][]NI
235 g.Tarjan(func(c []NI) bool {
236 r = append(r, c)
237 return true
238 })
239 scc := make([][]NI, len(r))
240 last := len(r) - 1
241 for i, ci := range r {
242 scc[last-i] = ci
243 }
244 return scc
245 }
246
247 // TarjanCondensation returns strongly connected components and their
248 // condensation graph.
249 //
250 // Components are ordered in a forward topological ordering.
251 func (g LabeledDirected) TarjanCondensation() (scc [][]NI, cd AdjacencyList) {
252 scc = g.TarjanForward()
253 cd = make(AdjacencyList, len(scc)) // return value
254 cond := make([]NI, len(g.LabeledAdjacencyList)) // mapping from g node to cd node
255 for cn := NI(len(scc) - 1); cn >= 0; cn-- {
256 c := scc[cn]
257 for _, n := range c {
258 cond[n] = NI(cn) // map g node to cd node
259 }
260 var tos []NI // list of 'to' nodes
261 var m Bits // tos map
262 m.SetBit(cn, 1)
263 for _, n := range c {
264 for _, to := range g.LabeledAdjacencyList[n] {
265 if ct := cond[to.To]; m.Bit(ct) == 0 {
266 m.SetBit(ct, 1)
267 tos = append(tos, ct)
268 }
269 }
270 }
271 cd[cn] = tos
272 }
273 return
274 }
275
276 // Topological computes a topological ordering of a directed acyclic graph.
277 //
278 // For an acyclic graph, return value ordering is a permutation of node numbers
279 // in topologically sorted order and cycle will be nil. If the graph is found
280 // to be cyclic, ordering will be nil and cycle will be the path of a found
281 // cycle.
282 //
283 // There are equivalent labeled and unlabeled versions of this method.
284 func (g LabeledDirected) Topological() (ordering, cycle []NI) {
285 a := g.LabeledAdjacencyList
286 ordering = make([]NI, len(a))
287 i := len(ordering)
288 var temp, perm Bits
289 var cycleFound bool
290 var cycleStart NI
291 var df func(NI)
292 df = func(n NI) {
293 switch {
294 case temp.Bit(n) == 1:
295 cycleFound = true
296 cycleStart = n
297 return
298 case perm.Bit(n) == 1:
299 return
300 }
301 temp.SetBit(n, 1)
302 for _, nb := range a[n] {
303 df(nb.To)
304 if cycleFound {
305 if cycleStart >= 0 {
306 // a little hack: orderng won't be needed so repurpose the
307 // slice as cycle. this is read out in reverse order
308 // as the recursion unwinds.
309 x := len(ordering) - 1 - len(cycle)
310 ordering[x] = n
311 cycle = ordering[x:]
312 if n == cycleStart {
313 cycleStart = -1
314 }
315 }
316 return
317 }
318 }
319 temp.SetBit(n, 0)
320 perm.SetBit(n, 1)
321 i--
322 ordering[i] = n
323 }
324 for n := range a {
325 if perm.Bit(NI(n)) == 1 {
326 continue
327 }
328 df(NI(n))
329 if cycleFound {
330 return nil, cycle
331 }
332 }
333 return ordering, nil
334 }
335
336 // TopologicalKahn computes a topological ordering of a directed acyclic graph.
337 //
338 // For an acyclic graph, return value ordering is a permutation of node numbers
339 // in topologically sorted order and cycle will be nil. If the graph is found
340 // to be cyclic, ordering will be nil and cycle will be the path of a found
341 // cycle.
342 //
343 // This function is based on the algorithm by Arthur Kahn and requires the
344 // transpose of g be passed as the argument.
345 //
346 // There are equivalent labeled and unlabeled versions of this method.
347 func (g LabeledDirected) TopologicalKahn(tr Directed) (ordering, cycle []NI) {
348 // code follows Wikipedia pseudocode.
349 var L, S []NI
350 // rem for "remaining edges," this function makes a local copy of the
351 // in-degrees and consumes that instead of consuming an input.
352 rem := make([]int, len(g.LabeledAdjacencyList))
353 for n, fr := range tr.AdjacencyList {
354 if len(fr) == 0 {
355 // accumulate "set of all nodes with no incoming edges"
356 S = append(S, NI(n))
357 } else {
358 // initialize rem from in-degree
359 rem[n] = len(fr)
360 }
361 }
362 for len(S) > 0 {
363 last := len(S) - 1 // "remove a node n from S"
364 n := S[last]
365 S = S[:last]
366 L = append(L, n) // "add n to tail of L"
367 for _, m := range g.LabeledAdjacencyList[n] {
368 // WP pseudo code reads "for each node m..." but it means for each
369 // node m *remaining in the graph.* We consume rem rather than
370 // the graph, so "remaining in the graph" for us means rem[m] > 0.
371 if rem[m.To] > 0 {
372 rem[m.To]-- // "remove edge from the graph"
373 if rem[m.To] == 0 { // if "m has no other incoming edges"
374 S = append(S, m.To) // "insert m into S"
375 }
376 }
377 }
378 }
379 // "If graph has edges," for us means a value in rem is > 0.
380 for c, in := range rem {
381 if in > 0 {
382 // recover cyclic nodes
383 for _, nb := range g.LabeledAdjacencyList[c] {
384 if rem[nb.To] > 0 {
385 cycle = append(cycle, NI(c))
386 break
387 }
388 }
389 }
390 }
391 if len(cycle) > 0 {
392 return nil, cycle
393 }
394 return L, nil
395 }