"Fossies" - the Fresh Open Source Software Archive 
Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/adj_cg.go" (28 May 2021, 11069 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 // adj_RO.go is code generated from adj_cg.go by directives in graph.go.
7 // Editing adj_cg.go is okay.
8 // DO NOT EDIT adj_RO.go. The RO is for Read Only.
9
10 import (
11 "math/rand"
12 "time"
13 )
14
15 // ArcSize returns the number of arcs in g.
16 //
17 // Note that for an undirected graph without loops, the number of undirected
18 // edges -- the traditional meaning of graph size -- will be ArcSize()/2.
19 // On the other hand, if g is an undirected graph that has or may have loops,
20 // g.ArcSize()/2 is not a meaningful quantity.
21 //
22 // There are equivalent labeled and unlabeled versions of this method.
23 func (g LabeledAdjacencyList) ArcSize() int {
24 m := 0
25 for _, to := range g {
26 m += len(to)
27 }
28 return m
29 }
30
31 // BoundsOk validates that all arcs in g stay within the slice bounds of g.
32 //
33 // BoundsOk returns true when no arcs point outside the bounds of g.
34 // Otherwise it returns false and an example arc that points outside of g.
35 //
36 // Most methods of this package assume the BoundsOk condition and may
37 // panic when they encounter an arc pointing outside of the graph. This
38 // function can be used to validate a graph when the BoundsOk condition
39 // is unknown.
40 //
41 // There are equivalent labeled and unlabeled versions of this method.
42 func (g LabeledAdjacencyList) BoundsOk() (ok bool, fr NI, to Half) {
43 for fr, to := range g {
44 for _, to := range to {
45 if to.To < 0 || to.To >= NI(len(g)) {
46 return false, NI(fr), to
47 }
48 }
49 }
50 return true, -1, to
51 }
52
53 // BreadthFirst traverses a directed or undirected graph in breadth first order.
54 //
55 // Argument start is the start node for the traversal. If r is nil, nodes are
56 // visited in deterministic order. If a random number generator is supplied,
57 // nodes at each level are visited in random order.
58 //
59 // Argument f can be nil if you have no interest in the FromList path result.
60 // If FromList f is non-nil, the method populates f.Paths and sets f.MaxLen.
61 // It does not set f.Leaves. For convenience argument f can be a zero value
62 // FromList. If f.Paths is nil, the FromList is initialized first. If f.Paths
63 // is non-nil however, the FromList is used as is. The method uses a value of
64 // PathEnd.Len == 0 to indentify unvisited nodes. Existing non-zero values
65 // will limit the traversal.
66 //
67 // Traversal calls the visitor function v for each node starting with node
68 // start. If v returns true, traversal continues. If v returns false, the
69 // traversal terminates immediately. PathEnd Len and From values are updated
70 // before calling the visitor function.
71 //
72 // On return f.Paths and f.MaxLen are set but not f.Leaves.
73 //
74 // Returned is the number of nodes visited and ok = true if the traversal
75 // ran to completion or ok = false if it was terminated by the visitor
76 // function returning false.
77 //
78 // There are equivalent labeled and unlabeled versions of this method.
79 func (g LabeledAdjacencyList) BreadthFirst(start NI, r *rand.Rand, f *FromList, v OkNodeVisitor) (visited int, ok bool) {
80 switch {
81 case f == nil:
82 e := NewFromList(len(g))
83 f = &e
84 case f.Paths == nil:
85 *f = NewFromList(len(g))
86 }
87 rp := f.Paths
88 // the frontier consists of nodes all at the same level
89 frontier := []NI{start}
90 level := 1
91 // assign path when node is put on frontier,
92 rp[start] = PathEnd{Len: level, From: -1}
93 for {
94 f.MaxLen = level
95 level++
96 var next []NI
97 if r == nil {
98 for _, n := range frontier {
99 visited++
100 if !v(n) { // visit nodes as they come off frontier
101 return
102 }
103 for _, nb := range g[n] {
104 if rp[nb.To].Len == 0 {
105 next = append(next, nb.To)
106 rp[nb.To] = PathEnd{From: n, Len: level}
107 }
108 }
109 }
110 } else { // take nodes off frontier at random
111 for _, i := range r.Perm(len(frontier)) {
112 n := frontier[i]
113 // remainder of block same as above
114 visited++
115 if !v(n) {
116 return
117 }
118 for _, nb := range g[n] {
119 if rp[nb.To].Len == 0 {
120 next = append(next, nb.To)
121 rp[nb.To] = PathEnd{From: n, Len: level}
122 }
123 }
124 }
125 }
126 if len(next) == 0 {
127 break
128 }
129 frontier = next
130 }
131 return visited, true
132 }
133
134 // BreadthFirstPath finds a single path from start to end with a minimum
135 // number of nodes.
136 //
137 // Returned is the path as list of nodes.
138 // The result is nil if no path was found.
139 //
140 // There are equivalent labeled and unlabeled versions of this method.
141 func (g LabeledAdjacencyList) BreadthFirstPath(start, end NI) []NI {
142 var f FromList
143 g.BreadthFirst(start, nil, &f, func(n NI) bool { return n != end })
144 return f.PathTo(end, nil)
145 }
146
147 // Copy makes a deep copy of g.
148 // Copy also computes the arc size ma, the number of arcs.
149 //
150 // There are equivalent labeled and unlabeled versions of this method.
151 func (g LabeledAdjacencyList) Copy() (c LabeledAdjacencyList, ma int) {
152 c = make(LabeledAdjacencyList, len(g))
153 for n, to := range g {
154 c[n] = append([]Half{}, to...)
155 ma += len(to)
156 }
157 return
158 }
159
160 // DepthFirst traverses a graph depth first.
161 //
162 // As it traverses it calls visitor function v for each node. If v returns
163 // false at any point, the traversal is terminated immediately and DepthFirst
164 // returns false. Otherwise DepthFirst returns true.
165 //
166 // DepthFirst uses argument bm is used as a bitmap to guide the traversal.
167 // For a complete traversal, bm should be 0 initially. During the
168 // traversal, bits are set corresponding to each node visited.
169 // The bit is set before calling the visitor function.
170 //
171 // Argument bm can be nil if you have no need for it.
172 // In this case a bitmap is created internally for one-time use.
173 //
174 // Alternatively v can be nil. In this case traversal still proceeds and
175 // updates the bitmap, which can be a useful result.
176 // DepthFirst always returns true in this case.
177 //
178 // It makes no sense for both bm and v to be nil. In this case DepthFirst
179 // returns false immediately.
180 //
181 // There are equivalent labeled and unlabeled versions of this method.
182 func (g LabeledAdjacencyList) DepthFirst(start NI, bm *Bits, v OkNodeVisitor) (ok bool) {
183 if bm == nil {
184 if v == nil {
185 return false
186 }
187 bm = &Bits{}
188 }
189 var df func(n NI) bool
190 df = func(n NI) bool {
191 if bm.Bit(n) == 1 {
192 return true
193 }
194 bm.SetBit(n, 1)
195 if v != nil && !v(n) {
196 return false
197 }
198 for _, nb := range g[n] {
199 if !df(nb.To) {
200 return false
201 }
202 }
203 return true
204 }
205 return df(start)
206 }
207
208 // DepthFirstRandom traverses a graph depth first, but following arcs in
209 // random order among arcs from a single node.
210 //
211 // If Rand r is nil, the method creates a new source and generator for
212 // one-time use.
213 //
214 // Usage is otherwise like the DepthFirst method. See DepthFirst.
215 //
216 // There are equivalent labeled and unlabeled versions of this method.
217 func (g LabeledAdjacencyList) DepthFirstRandom(start NI, bm *Bits, v OkNodeVisitor, r *rand.Rand) (ok bool) {
218 if bm == nil {
219 if v == nil {
220 return false
221 }
222 bm = &Bits{}
223 }
224 if r == nil {
225 r = rand.New(rand.NewSource(time.Now().UnixNano()))
226 }
227 var df func(n NI) bool
228 df = func(n NI) bool {
229 if bm.Bit(n) == 1 {
230 return true
231 }
232 bm.SetBit(n, 1)
233 if v != nil && !v(n) {
234 return false
235 }
236 to := g[n]
237 for _, i := range r.Perm(len(to)) {
238 if !df(to[i].To) {
239 return false
240 }
241 }
242 return true
243 }
244 return df(start)
245 }
246
247 // HasArc returns true if g has any arc from node fr to node to.
248 //
249 // Also returned is the index within the slice of arcs from node fr.
250 // If no arc from fr to to is present, HasArc returns false, -1.
251 //
252 // There are equivalent labeled and unlabeled versions of this method.
253 func (g LabeledAdjacencyList) HasArc(fr, to NI) (bool, int) {
254 for x, h := range g[fr] {
255 if h.To == to {
256 return true, x
257 }
258 }
259 return false, -1
260 }
261
262 // HasLoop identifies if a graph contains a loop, an arc that leads from a
263 // a node back to the same node.
264 //
265 // If the graph has a loop, the result is an example node that has a loop.
266 //
267 // If g contains a loop, the method returns true and an example of a node
268 // with a loop. If there are no loops in g, the method returns false, -1.
269 //
270 // There are equivalent labeled and unlabeled versions of this method.
271 func (g LabeledAdjacencyList) HasLoop() (bool, NI) {
272 for fr, to := range g {
273 for _, to := range to {
274 if NI(fr) == to.To {
275 return true, to.To
276 }
277 }
278 }
279 return false, -1
280 }
281
282 // HasParallelMap identifies if a graph contains parallel arcs, multiple arcs
283 // that lead from a node to the same node.
284 //
285 // If the graph has parallel arcs, the method returns true and
286 // results fr and to represent an example where there are parallel arcs
287 // from node fr to node to.
288 //
289 // If there are no parallel arcs, the method returns false, -1 -1.
290 //
291 // Multiple loops on a node count as parallel arcs.
292 //
293 // "Map" in the method name indicates that a Go map is used to detect parallel
294 // arcs. Compared to method HasParallelSort, this gives better asymtotic
295 // performance for large dense graphs but may have increased overhead for
296 // small or sparse graphs.
297 //
298 // There are equivalent labeled and unlabeled versions of this method.
299 func (g LabeledAdjacencyList) HasParallelMap() (has bool, fr, to NI) {
300 for n, to := range g {
301 if len(to) == 0 {
302 continue
303 }
304 m := map[NI]struct{}{}
305 for _, to := range to {
306 if _, ok := m[to.To]; ok {
307 return true, NI(n), to.To
308 }
309 m[to.To] = struct{}{}
310 }
311 }
312 return false, -1, -1
313 }
314
315 // IsSimple checks for loops and parallel arcs.
316 //
317 // A graph is "simple" if it has no loops or parallel arcs.
318 //
319 // IsSimple returns true, -1 for simple graphs. If a loop or parallel arc is
320 // found, simple returns false and a node that represents a counterexample
321 // to the graph being simple.
322 //
323 // See also separate methods HasLoop and HasParallel.
324 //
325 // There are equivalent labeled and unlabeled versions of this method.
326 func (g LabeledAdjacencyList) IsSimple() (ok bool, n NI) {
327 if lp, n := g.HasLoop(); lp {
328 return false, n
329 }
330 if pa, n, _ := g.HasParallelSort(); pa {
331 return false, n
332 }
333 return true, -1
334 }
335
336 // IsolatedNodes returns a bitmap of isolated nodes in receiver graph g.
337 //
338 // An isolated node is one with no arcs going to or from it.
339 //
340 // There are equivalent labeled and unlabeled versions of this method.
341 func (g LabeledAdjacencyList) IsolatedNodes() (i Bits) {
342 i.SetAll(len(g))
343 for fr, to := range g {
344 if len(to) > 0 {
345 i.SetBit(NI(fr), 0)
346 for _, to := range to {
347 i.SetBit(to.To, 0)
348 }
349 }
350 }
351 return
352 }
353
354 /*
355 MaxmimalClique finds a maximal clique containing the node n.
356
357 Not sure this is good for anything. It produces a single maximal clique
358 but there can be multiple maximal cliques containing a given node.
359 This algorithm just returns one of them, not even necessarily the
360 largest one.
361
362 func (g LabeledAdjacencyList) MaximalClique(n int) []int {
363 c := []int{n}
364 var m bitset.BitSet
365 m.Set(uint(n))
366 for fr, to := range g {
367 if fr == n {
368 continue
369 }
370 if len(to) < len(c) {
371 continue
372 }
373 f := 0
374 for _, to := range to {
375 if m.Test(uint(to.To)) {
376 f++
377 if f == len(c) {
378 c = append(c, to.To)
379 m.Set(uint(to.To))
380 break
381 }
382 }
383 }
384 }
385 return c
386 }
387 */