"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
2 // License MIT: http://opensource.org/licenses/MIT
3
4 package graph
5
6 // undir.go has methods specific to undirected graphs, Undirected and
7 // LabeledUndirected.
8
9 import "errors"
10
11 // AddEdge adds an edge to a graph.
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) {
22 // Similar code in LabeledAdjacencyList.AddEdge.
23
24 // determine max of the two end points
25 max := n1
26 if n2 > max {
27 max = n2
28 }
29 // expand graph if needed, to include both
30 g := p.AdjacencyList
31 if int(max) >= len(g) {
32 p.AdjacencyList = make(AdjacencyList, max+1)
33 copy(p.AdjacencyList, g)
34 g = p.AdjacencyList
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 {
40 g[n2] = append(g[n2], n1)
41 }
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) {
56 if len(g.AdjacencyList) == 0 {
57 return nil, nil
58 }
59 e := newEulerian(g.AdjacencyList, m)
60 for e.s >= 0 {
61 v := e.top()
62 e.pushUndir() // call modified method
63 if e.top() != v {
64 return nil, errors.New("not balanced")
65 }
66 e.keep()
67 }
68 if !e.uv.Zero() {
69 return nil, errors.New("not strongly connected")
70 }
71 return e.p, nil
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 //
82 // See also the eqivalent labeled TarjanBiconnectedComponents.
83 func (g Undirected) TarjanBiconnectedComponents(emit func([]Edge) bool) {
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 //
88 // Note Tarjan's "adjacency structure" is graph.AdjacencyList,
89 // His "adjacency list" is an element of a graph.AdjacencyList, also
90 // termed a "to-list", "neighbor list", or "child list."
91 number := make([]int, len(g.AdjacencyList))
92 lowpt := make([]int, len(g.AdjacencyList))
93 var stack []Edge
94 var i int
95 var biconnect func(NI, NI) bool
96 biconnect = func(v, u NI) bool {
97 i++
98 number[v] = i
99 lowpt[v] = i
100 for _, w := range g.AdjacencyList[v] {
101 if number[w] == 0 {
102 stack = append(stack, Edge{v, w})
103 if !biconnect(w, v) {
104 return false
105 }
106 if lowpt[w] < lowpt[v] {
107 lowpt[v] = lowpt[w]
108 }
109 if lowpt[w] >= number[v] {
110 var bcc []Edge
111 top := len(stack) - 1
112 for number[stack[top].N1] >= number[w] {
113 bcc = append(bcc, stack[top])
114 stack = stack[:top]
115 top--
116 }
117 bcc = append(bcc, stack[top])
118 stack = stack[:top]
119 top--
120 if !emit(bcc) {
121 return false
122 }
123 }
124 } else if number[w] < number[v] && w != u {
125 stack = append(stack, Edge{v, w})
126 if number[w] < lowpt[v] {
127 lowpt[v] = number[w]
128 }
129 }
130 }
131 return true
132 }
133 for w := range g.AdjacencyList {
134 if number[w] == 0 && !biconnect(NI(w), 0) {
135 return
136 }
137 }
138 }
139
140 /* half-baked. Read the 72 paper. Maybe revisit at some point.
141 type BiconnectedComponents struct {
142 Graph AdjacencyList
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[0])
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
220 // AddEdge adds an edge to a labeled graph.
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) {
233 // Similar code in AdjacencyList.AddEdge.
234
235 // determine max of the two end points
236 max := e.N1
237 if e.N2 > max {
238 max = e.N2
239 }
240 // expand graph if needed, to include both
241 g := p.LabeledAdjacencyList
242 if max >= NI(len(g)) {
243 p.LabeledAdjacencyList = make(LabeledAdjacencyList, max+1)
244 copy(p.LabeledAdjacencyList, g)
245 g = p.LabeledAdjacencyList
246 }
247 // create one half-arc,
248 g[e.N1] = append(g[e.N1], Half{To: e.N2, Label: l})
249 // and except for loops, create the reciprocal
250 if e.N1 != e.N2 {
251 g[e.N2] = append(g[e.N2], Half{To: e.N1, Label: l})
252 }
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 //
263 // See also the eqivalent unlabeled TarjanBiconnectedComponents.
264 func (g LabeledUndirected) TarjanBiconnectedComponents(emit func([]LabeledEdge) bool) {
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 //
269 // Note Tarjan's "adjacency structure" is graph.AdjacencyList,
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.
274 number := make([]int, len(g.LabeledAdjacencyList))
275 lowpt := make([]int, len(g.LabeledAdjacencyList))
276 var stack []LabeledEdge
277 var i int
278 var biconnect func(NI, NI) bool
279 biconnect = func(v, u NI) bool {
280 i++
281 number[v] = i
282 lowpt[v] = i
283 for _, w := range g.LabeledAdjacencyList[v] {
284 if number[w.To] == 0 {
285 stack = append(stack, LabeledEdge{Edge{v, w.To}, w.Label})
286 if !biconnect(w.To, v) {
287 return false
288 }
289 if lowpt[w.To] < lowpt[v] {
290 lowpt[v] = lowpt[w.To]
291 }
292 if lowpt[w.To] >= number[v] {
293 var bcc []LabeledEdge
294 top := len(stack) - 1
295 for number[stack[top].N1] >= number[w.To] {
296 bcc = append(bcc, stack[top])
297 stack = stack[:top]
298 top--
299 }
300 bcc = append(bcc, stack[top])
301 stack = stack[:top]
302 top--
303 if !emit(bcc) {
304 return false
305 }
306 }
307 } else if number[w.To] < number[v] && w.To != u {
308 stack = append(stack, LabeledEdge{Edge{v, w.To}, w.Label})
309 if number[w.To] < lowpt[v] {
310 lowpt[v] = number[w.To]
311 }
312 }
313 }
314 return true
315 }
316 for w := range g.LabeledAdjacencyList {
317 if number[w] == 0 && !biconnect(NI(w), 0) {
318 return
319 }
320 }
321 }