## "Fossies" - the Fresh Open Source Software Archive ### Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/undir.go" (28 May 2021, 8669 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
3
4 package graph
5
6 // undir.go has methods specific to undirected graphs, Undirected and
7 // LabeledUndirected.
8
9 import "errors"
10
12 //
13 // It can be useful for constructing undirected graphs.
14 //
15 // When n1 and n2 are distinct, it adds the arc n1->n2 and the reciprocal
16 // n2->n1.  When n1 and n2 are the same, it adds a single arc loop.
17 //
18 // The pointer receiver allows the method to expand the graph as needed
19 // to include the values n1 and n2.  If n1 or n2 happen to be greater than
20 // len(*p) the method does not panic, but simply expands the graph.
21 func (p *Undirected) AddEdge(n1, n2 NI) hlOpen(21,1);{
23
24     // determine max of the two end points
25     max := n1
26     if n2 > max hlOpen(26,2);{
27         max = n2
28     hlClose(2, 28);}
29     // expand graph if needed, to include both
31     if int(max) >= len(g) hlOpen(31,2);{
35     hlClose(3, 35);}
36     // create one half-arc,
37     g[n1] = append(g[n1], n2)
38     // and except for loops, create the reciprocal
39     if n1 != n2 hlOpen(39,2);{
40         g[n2] = append(g[n2], n1)
41     hlClose(4, 41);}
42 hlClose(1, 42);}
43
44 // EulerianCycleD for undirected graphs is a bit of an experiment.
45 //
46 // It is about the same as the directed version, but modified for an undirected
47 // multigraph.
48 //
49 // Parameter m in this case must be the size of the undirected graph -- the
50 // number of edges.  Use Undirected.Size if the size is unknown.
51 //
52 // It works, but contains an extra loop that I think spoils the time
53 // complexity.  Probably still pretty fast in practice, but a different
54 // graph representation might be better.
55 func (g Undirected) EulerianCycleD(m int) ([]NI, error) hlOpen(55,1);{
56     if len(g.AdjacencyList) == 0 hlOpen(56,2);{
57         return nil, nil
58     hlClose(6, 58);}
60     for e.s >= 0 hlOpen(60,2);{
61         v := e.top()
62         e.pushUndir() // call modified method
63         if e.top() != v hlOpen(63,3);{
64             return nil, errors.New("not balanced")
65         hlClose(8, 65);}
66         e.keep()
67     hlClose(7, 67);}
68     if !e.uv.Zero() hlOpen(68,2);{
69         return nil, errors.New("not strongly connected")
70     hlClose(9, 70);}
71     return e.p, nil
72 hlClose(5, 72);}
73
74 // TarjanBiconnectedComponents decomposes a graph into maximal biconnected
75 // components, components for which if any node were removed the component
76 // would remain connected.
77 //
78 // The receiver g must be a simple graph.  The method calls the emit argument
79 // for each component identified, as long as emit returns true.  If emit
80 // returns false, TarjanBiconnectedComponents returns immediately.
81 //
83 func (g Undirected) TarjanBiconnectedComponents(emit func([]Edge) bool) hlOpen(83,1);{
84     // Implemented closely to pseudocode in "Depth-first search and linear
85     // graph algorithms", Robert Tarjan, SIAM J. Comput. Vol. 1, No. 2,
86     // June 1972.
87     //
89     // His "adjacency list" is an element of a graph.AdjacencyList, also
90     // termed a "to-list", "neighbor list", or "child list."
93     var stack []Edge
94     var i int
95     var biconnect func(NI, NI) bool
96     biconnect = func(v, u NI) bool hlOpen(96,2);{
97         i++
98         number[v] = i
99         lowpt[v] = i
100         for _, w := range g.AdjacencyList[v] hlOpen(100,3);{
101             if number[w] == 0 hlOpen(101,4);{
102                 stack = append(stack, EdgehlOpen(102,5);{v, whlClose(14, 102);})
103                 if !biconnect(w, v) hlOpen(103,5);{
104                     return false
105                 hlClose(15, 105);}
106                 if lowpt[w] < lowpt[v] hlOpen(106,5);{
107                     lowpt[v] = lowpt[w]
108                 hlClose(16, 108);}
109                 if lowpt[w] >= number[v] hlOpen(109,5);{
110                     var bcc []Edge
111                     top := len(stack) - 1
112                     for number[stack[top].N1] >= number[w] hlOpen(112,6);{
113                         bcc = append(bcc, stack[top])
114                         stack = stack[:top]
115                         top--
116                     hlClose(18, 116);}
117                     bcc = append(bcc, stack[top])
118                     stack = stack[:top]
119                     top--
120                     if !emit(bcc) hlOpen(120,6);{
121                         return false
122                     hlClose(19, 122);}
123                 hlClose(17, 123);}
124             hlClose(13, 124);} else if number[w] < number[v] && w != u hlOpen(124,4);{
125                 stack = append(stack, EdgehlOpen(125,5);{v, whlClose(21, 125);})
126                 if number[w] < lowpt[v] hlOpen(126,5);{
127                     lowpt[v] = number[w]
128                 hlClose(22, 128);}
129             hlClose(20, 129);}
130         hlClose(12, 130);}
131         return true
132     hlClose(11, 132);}
133     for w := range g.AdjacencyList hlOpen(133,2);{
134         if number[w] == 0 && !biconnect(NI(w), 0) hlOpen(134,3);{
135             return
136         hlClose(24, 136);}
137     hlClose(23, 137);}
138 hlClose(10, 138);}
139
140 /* half-baked.  Read the 72 paper.  Maybe revisit at some point.
141 type BiconnectedComponents struct {
143     Start  int
144     Cuts   big.Int // bitmap of node cuts
145     From   []int   // from-tree
146     Leaves []int   // leaves of from-tree
147 }
148
149 func NewBiconnectedComponents(g Undirected) *BiconnectedComponents {
150     return &BiconnectedComponents{
151         Graph: g,
152         From:  make([]int, len(g)),
153     }
154 }
155
156 func (b *BiconnectedComponents) Find(start int) {
157     g := b.Graph
158     depth := make([]int, len(g))
159     low := make([]int, len(g))
160     // reset from any previous run
161     b.Cuts.SetInt64(0)
162     bf := b.From
163     for n := range bf {
164         bf[n] = -1
165     }
166     b.Leaves = b.Leaves[:0]
167     d := 1 // depth. d > 0 means visited
168     depth[start] = d
169     low[start] = d
170     d++
171     var df func(int, int)
172     df = func(from, n int) {
173         bf[n] = from
174         depth[n] = d
175         dn := d
176         l := d
177         d++
178         cut := false
179         leaf := true
180         for _, nb := range g[n] {
181             if depth[nb] == 0 {
182                 leaf = false
183                 df(n, nb)
184                 if low[nb] < l {
185                     l = low[nb]
186                 }
187                 if low[nb] >= dn {
188                     cut = true
189                 }
190             } else if nb != from && depth[nb] < l {
191                 l = depth[nb]
192             }
193         }
194         low[n] = l
195         if cut {
196             b.Cuts.SetBit(&b.Cuts, n, 1)
197         }
198         if leaf {
199             b.Leaves = append(b.Leaves, n)
200         }
201         d--
202     }
203     nbs := g[start]
204     if len(nbs) == 0 {
205         return
206     }
207     df(start, nbs)
208     var rc uint
209     for _, nb := range nbs[1:] {
210         if depth[nb] == 0 {
211             rc = 1
212             df(start, nb)
213         }
214     }
215     b.Cuts.SetBit(&b.Cuts, start, rc)
216     return
217 }
218 */
219
221 //
222 // It can be useful for constructing undirected graphs.
223 //
224 // When n1 and n2 are distinct, it adds the arc n1->n2 and the reciprocal
225 // n2->n1.  When n1 and n2 are the same, it adds a single arc loop.
226 //
227 // If the edge already exists in *p, a parallel edge is added.
228 //
229 // The pointer receiver allows the method to expand the graph as needed
230 // to include the values n1 and n2.  If n1 or n2 happen to be greater than
231 // len(*p) the method does not panic, but simply expands the graph.
232 func (p *LabeledUndirected) AddEdge(e Edge, l LI) hlOpen(232,1);{
234
235     // determine max of the two end points
236     max := e.N1
237     if e.N2 > max hlOpen(237,2);{
238         max = e.N2
239     hlClose(26, 239);}
240     // expand graph if needed, to include both
242     if max >= NI(len(g)) hlOpen(242,2);{
246     hlClose(27, 246);}
247     // create one half-arc,
248     g[e.N1] = append(g[e.N1], HalfhlOpen(248,2);{To: e.N2, Label: lhlClose(28, 248);})
249     // and except for loops, create the reciprocal
250     if e.N1 != e.N2 hlOpen(250,2);{
251         g[e.N2] = append(g[e.N2], HalfhlOpen(251,3);{To: e.N1, Label: lhlClose(30, 251);})
252     hlClose(29, 252);}
253 hlClose(25, 253);}
254
255 // TarjanBiconnectedComponents decomposes a graph into maximal biconnected
256 // components, components for which if any node were removed the component
257 // would remain connected.
258 //
259 // The receiver g must be a simple graph.  The method calls the emit argument
260 // for each component identified, as long as emit returns true.  If emit
261 // returns false, TarjanBiconnectedComponents returns immediately.
262 //
264 func (g LabeledUndirected) TarjanBiconnectedComponents(emit func([]LabeledEdge) bool) hlOpen(264,1);{
265     // Implemented closely to pseudocode in "Depth-first search and linear
266     // graph algorithms", Robert Tarjan, SIAM J. Comput. Vol. 1, No. 2,
267     // June 1972.
268     //
270     // His "adjacency list" is an element of a graph.AdjacencyList, also
271     // termed a "to-list", "neighbor list", or "child list."
272     //
273     // Nearly identical code in undir.go.
276     var stack []LabeledEdge
277     var i int
278     var biconnect func(NI, NI) bool
279     biconnect = func(v, u NI) bool hlOpen(279,2);{
280         i++
281         number[v] = i
282         lowpt[v] = i
283         for _, w := range g.LabeledAdjacencyList[v] hlOpen(283,3);{
284             if number[w.To] == 0 hlOpen(284,4);{
285                 stack = append(stack, LabeledEdgehlOpen(285,5);{EdgehlOpen(285,6);{v, w.TohlClose(36, 285);}, w.LabelhlClose(35, 285);})
286                 if !biconnect(w.To, v) hlOpen(286,5);{
287                     return false
288                 hlClose(37, 288);}
289                 if lowpt[w.To] < lowpt[v] hlOpen(289,5);{
290                     lowpt[v] = lowpt[w.To]
291                 hlClose(38, 291);}
292                 if lowpt[w.To] >= number[v] hlOpen(292,5);{
293                     var bcc []LabeledEdge
294                     top := len(stack) - 1
295                     for number[stack[top].N1] >= number[w.To] hlOpen(295,6);{
296                         bcc = append(bcc, stack[top])
297                         stack = stack[:top]
298                         top--
299                     hlClose(40, 299);}
300                     bcc = append(bcc, stack[top])
301                     stack = stack[:top]
302                     top--
303                     if !emit(bcc) hlOpen(303,6);{
304                         return false
305                     hlClose(41, 305);}
306                 hlClose(39, 306);}
307             hlClose(34, 307);} else if number[w.To] < number[v] && w.To != u hlOpen(307,4);{
308                 stack = append(stack, LabeledEdgehlOpen(308,5);{EdgehlOpen(308,6);{v, w.TohlClose(44, 308);}, w.LabelhlClose(43, 308);})
309                 if number[w.To] < lowpt[v] hlOpen(309,5);{
310                     lowpt[v] = number[w.To]
311                 hlClose(45, 311);}
312             hlClose(42, 312);}
313         hlClose(33, 313);}
314         return true
315     hlClose(32, 315);}
316     for w := range g.LabeledAdjacencyList hlOpen(316,2);{
317         if number[w] == 0 && !biconnect(NI(w), 0) hlOpen(317,3);{
318             return
319         hlClose(47, 319);}
320     hlClose(46, 320);}
321 hlClose(31, 321);}
```