## "Fossies" - the Fresh Open Source Software Archive ### Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/adj.go" (28 May 2021, 9326 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
7 //
8 // AdjacencyList methods are placed first and are alphabetized.
9 // LabeledAdjacencyList methods follow, also alphabetized.
10 // Only exported methods need be alphabetized; non-exported methods can
11 // be left near their use.
12
13 import (
14     "math"
15     "sort"
16 )
17
18 // HasParallelSort identifies if a graph contains parallel arcs, multiple arcs
19 // that lead from a node to the same node.
20 //
21 // If the graph has parallel arcs, the results fr and to represent an example
22 // where there are parallel arcs from node fr to node to.
23 //
24 // If there are no parallel arcs, the method returns false -1 -1.
25 //
26 // Multiple loops on a node count as parallel arcs.
27 //
28 // "Sort" in the method name indicates that sorting is used to detect parallel
29 // arcs.  Compared to method HasParallelMap, this may give better performance
30 // for small or sparse graphs but will have asymtotically worse performance for
31 // large dense graphs.
32 func (g AdjacencyList) HasParallelSort() (has bool, fr, to NI) hlOpen(32,1);{
33     var t NodeList
34     for n, to := range g hlOpen(34,2);{
35         if len(to) == 0 hlOpen(35,3);{
36             continue
37         hlClose(3, 37);}
38         // different code in the labeled version, so no code gen.
39         t = append(t[:0], to...)
40         sort.Sort(t)
41         t0 := t
42         for _, to := range t[1:] hlOpen(42,3);{
43             if to == t0 hlOpen(43,4);{
44                 return true, NI(n), t0
45             hlClose(5, 45);}
46             t0 = to
47         hlClose(4, 47);}
48     hlClose(2, 48);}
49     return false, -1, -1
50 hlClose(1, 50);}
51
52 // IsUndirected returns true if g represents an undirected graph.
53 //
54 // Returns true when all non-loop arcs are paired in reciprocal pairs.
55 // Otherwise returns false and an example unpaired arc.
56 func (g AdjacencyList) IsUndirected() (u bool, from, to NI) hlOpen(56,1);{
57     // similar code in dot/writeUndirected
59     for fr, to := range g hlOpen(59,2);{
60     arc: // for each arc in g
61         for _, to := range to hlOpen(61,3);{
62             if to == NI(fr) hlOpen(62,4);{
63                 continue // loop
64             hlClose(9, 64);}
65             // search unpaired arcs
66             ut := unpaired[to]
67             for i, u := range ut hlOpen(67,4);{
68                 if u == NI(fr) hlOpen(68,5);{ // found reciprocal
69                     last := len(ut) - 1
70                     ut[i] = ut[last]
71                     unpaired[to] = ut[:last]
72                     continue arc
73                 hlClose(11, 73);}
74             hlClose(10, 74);}
76             unpaired[fr] = append(unpaired[fr], to)
77         hlClose(8, 77);}
78     hlClose(7, 78);}
79     for fr, to := range unpaired hlOpen(79,2);{
80         if len(to) > 0 hlOpen(80,3);{
81             return false, NI(fr), to
82         hlClose(13, 82);}
83     hlClose(12, 83);}
84     return true, -1, -1
85 hlClose(6, 85);}
86
87 // Edgelist constructs the edge list rerpresentation of a graph.
88 //
89 // An edge is returned for each arc of the graph.  For undirected graphs
90 // this includes reciprocal edges.
91 //
93 func (g LabeledAdjacencyList) EdgeList() (el []LabeledEdge) hlOpen(93,1);{
94     for fr, to := range g hlOpen(94,2);{
95         for _, to := range to hlOpen(95,3);{
96             el = append(el, LabeledEdgehlOpen(96,4);{EdgehlOpen(96,5);{NI(fr), to.TohlClose(18, 96);}, to.LabelhlClose(17, 96);})
97         hlClose(16, 97);}
98     hlClose(15, 98);}
99     return
100 hlClose(14, 100);}
101
102 // FloydWarshall finds all pairs shortest distances for a simple weighted
103 // graph without negative cycles.
104 //
105 // In result array d, d[i][j] will be the shortest distance from node i
106 // to node j.  Any diagonal element < 0 indicates a negative cycle exists.
107 //
108 // If g is an undirected graph with no negative edge weights, the result
109 // array will be a distance matrix, for example as used by package
110 // github.com/soniakeys/cluster.
111 func (g LabeledAdjacencyList) FloydWarshall(w WeightFunc) (d [][]float64) hlOpen(111,1);{
112     d = newFWd(len(g))
113     for fr, to := range g hlOpen(113,2);{
114         for _, to := range to hlOpen(114,3);{
115             d[fr][to.To] = w(to.Label)
116         hlClose(21, 116);}
117     hlClose(20, 117);}
118     solveFW(d)
119     return
120 hlClose(19, 120);}
121
122 // little helper function, makes a blank matrix for FloydWarshall.
123 func newFWd(n int) [][]float64 hlOpen(123,1);{
124     d := make([][]float64, n)
125     for i := range d hlOpen(125,2);{
126         di := make([]float64, n)
127         for j := range di hlOpen(127,3);{
128             if j != i hlOpen(128,4);{
129                 di[j] = math.Inf(1)
130             hlClose(25, 130);}
131         hlClose(24, 131);}
132         d[i] = di
133     hlClose(23, 133);}
134     return d
135 hlClose(22, 135);}
136
137 // Floyd Warshall solver, once the matrix d is initialized by arc weights.
138 func solveFW(d [][]float64) hlOpen(138,1);{
139     for k, dk := range d hlOpen(139,2);{
140         for _, di := range d hlOpen(140,3);{
141             dik := di[k]
142             for j := range d hlOpen(142,4);{
143                 if d2 := dik + dk[j]; d2 < di[j] hlOpen(143,5);{
144                     di[j] = d2
145                 hlClose(30, 145);}
146             hlClose(29, 146);}
147         hlClose(28, 147);}
148     hlClose(27, 148);}
149 hlClose(26, 149);}
150
151 // HasArcLabel returns true if g has any arc from node fr to node to
152 // with label l.
153 //
154 // Also returned is the index within the slice of arcs from node fr.
155 // If no arc from fr to to is present, HasArcLabel returns false, -1.
156 func (g LabeledAdjacencyList) HasArcLabel(fr, to NI, l LI) (bool, int) hlOpen(156,1);{
157     t := HalfhlOpen(157,2);{to, lhlClose(32, 157);}
158     for x, h := range g[fr] hlOpen(158,2);{
159         if h == t hlOpen(159,3);{
160             return true, x
161         hlClose(34, 161);}
162     hlClose(33, 162);}
163     return false, -1
164 hlClose(31, 164);}
165
166 // HasParallelSort identifies if a graph contains parallel arcs, multiple arcs
167 // that lead from a node to the same node.
168 //
169 // If the graph has parallel arcs, the results fr and to represent an example
170 // where there are parallel arcs from node fr to node to.
171 //
172 // If there are no parallel arcs, the method returns -1 -1.
173 //
174 // Multiple loops on a node count as parallel arcs.
175 //
176 // "Sort" in the method name indicates that sorting is used to detect parallel
177 // arcs.  Compared to method HasParallelMap, this may give better performance
178 // for small or sparse graphs but will have asymtotically worse performance for
179 // large dense graphs.
180 func (g LabeledAdjacencyList) HasParallelSort() (has bool, fr, to NI) hlOpen(180,1);{
181     var t NodeList
182     for n, to := range g hlOpen(182,2);{
183         if len(to) == 0 hlOpen(183,3);{
184             continue
185         hlClose(37, 185);}
186         // slightly different code needed here compared to AdjacencyList
187         t = t[:0]
188         for _, to := range to hlOpen(188,3);{
189             t = append(t, to.To)
190         hlClose(38, 190);}
191         sort.Sort(t)
192         t0 := t
193         for _, to := range t[1:] hlOpen(193,3);{
194             if to == t0 hlOpen(194,4);{
195                 return true, NI(n), t0
196             hlClose(40, 196);}
197             t0 = to
198         hlClose(39, 198);}
199     hlClose(36, 199);}
200     return false, -1, -1
201 hlClose(35, 201);}
202
203 // IsUndirected returns true if g represents an undirected graph.
204 //
205 // Returns true when all non-loop arcs are paired in reciprocal pairs with
206 // matching labels.  Otherwise returns false and an example unpaired arc.
207 //
208 // Note the requirement that reciprocal pairs have matching labels is
209 // an additional test not present in the otherwise equivalent unlabeled version
210 // of IsUndirected.
211 func (g LabeledAdjacencyList) IsUndirected() (u bool, from NI, to Half) hlOpen(211,1);{
213     for fr, to := range g hlOpen(213,2);{
214     arc: // for each arc in g
215         for _, to := range to hlOpen(215,3);{
216             if to.To == NI(fr) hlOpen(216,4);{
217                 continue // loop
218             hlClose(44, 218);}
219             // search unpaired arcs
220             ut := unpaired[to.To]
221             for i, u := range ut hlOpen(221,4);{
222                 if u.To == NI(fr) && u.Label == to.Label hlOpen(222,5);{ // found reciprocal
223                     last := len(ut) - 1
224                     ut[i] = ut[last]
225                     unpaired[to.To] = ut[:last]
226                     continue arc
227                 hlClose(46, 227);}
228             hlClose(45, 228);}
230             unpaired[fr] = append(unpaired[fr], to)
231         hlClose(43, 231);}
232     hlClose(42, 232);}
233     for fr, to := range unpaired hlOpen(233,2);{
234         if len(to) > 0 hlOpen(234,3);{
235             return false, NI(fr), to
236         hlClose(48, 236);}
237     hlClose(47, 237);}
238     return true, -1, to
239 hlClose(41, 239);}
240
241 // NegativeArc returns true if the receiver graph contains a negative arc.
242 func (g LabeledAdjacencyList) NegativeArc(w WeightFunc) bool hlOpen(242,1);{
243     for _, nbs := range g hlOpen(243,2);{
244         for _, nb := range nbs hlOpen(244,3);{
245             if w(nb.Label) < 0 hlOpen(245,4);{
246                 return true
247             hlClose(52, 247);}
248         hlClose(51, 248);}
249     hlClose(50, 249);}
250     return false
251 hlClose(49, 251);}
252
253 // Unlabeled constructs the unlabeled graph corresponding to g.
256     for n, nbs := range g hlOpen(256,2);{
257         to := make([]NI, len(nbs))
258         for i, nb := range nbs hlOpen(258,3);{
259             to[i] = nb.To
260         hlClose(55, 260);}
261         a[n] = to
262     hlClose(54, 262);}
263     return a
264 hlClose(53, 264);}
265
266 // WeightedEdgeList constructs a WeightedEdgeList object from a
268 //
269 // Internally it calls g.EdgeList() to obtain the Edges member.
271 func (g LabeledAdjacencyList) WeightedEdgeList(w WeightFunc) *WeightedEdgeList hlOpen(271,1);{
272     return &WeightedEdgeListhlOpen(272,2);{
273         Order:      len(g),
274         WeightFunc: w,
275         Edges:      g.EdgeList(),
276     hlClose(57, 276);}
277 hlClose(56, 277);}
278
279 // WeightedInDegree computes the weighted in-degree of each node in g
280 // for a given weight function w.
281 //
282 // The weighted in-degree of a node is the sum of weights of arcs going to
283 // the node.
284 //
285 // A weighted degree of a node is often termed the "strength" of a node.
286 //
287 // See note for undirected graphs at LabeledAdjacencyList.WeightedOutDegree.
288 func (g LabeledAdjacencyList) WeightedInDegree(w WeightFunc) []float64 hlOpen(288,1);{
289     ind := make([]float64, len(g))
290     for _, to := range g hlOpen(290,2);{
291         for _, to := range to hlOpen(291,3);{
292             ind[to.To] += w(to.Label)
293         hlClose(60, 293);}
294     hlClose(59, 294);}
295     return ind
296 hlClose(58, 296);}
297
298 // WeightedOutDegree computes the weighted out-degree of the specified node
299 // for a given weight function w.
300 //
301 // The weighted out-degree of a node is the sum of weights of arcs going from
302 // the node.
303 //
304 // A weighted degree of a node is often termed the "strength" of a node.
305 //
306 // Note for undirected graphs, the WeightedOutDegree result for a node will
307 // equal the WeightedInDegree for the node.  You can use WeightedInDegree if
308 // you have need for the weighted degrees of all nodes or use WeightedOutDegree
309 // to compute the weighted degrees of individual nodes.  In either case loops
310 // are counted just once, unlike the (unweighted) UndirectedDegree methods.
311 func (g LabeledAdjacencyList) WeightedOutDegree(n NI, w WeightFunc) (d float64) hlOpen(311,1);{
312     for _, to := range g[n] hlOpen(312,2);{
313         d += w(to.Label)
314     hlClose(62, 314);}
315     return
316 hlClose(61, 316);}
317
318 // More about loops and strength:  I didn't see consensus on this especially
319 // in the case of undirected graphs.  Some sources said to add in-degree and
320 // out-degree, which would seemingly double both loops and non-loops.
321 // Some said to double loops.  Some said sum the edge weights and had no
322 // comment on loops.  R of course makes everything an option.  The meaning
323 // of "strength" where loops exist is unclear.  So while I could write an
324 // UndirectedWeighted degree function that doubles loops but not edges,
325 // I'm going to just leave this for now.
```