"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
2 // License MIT: https://opensource.org/licenses/MIT
3
4 package graph
5
6 // adj.go contains methods on AdjacencyList and LabeledAdjacencyList.
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) {
33 var t NodeList
34 for n, to := range g {
35 if len(to) == 0 {
36 continue
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[0]
42 for _, to := range t[1:] {
43 if to == t0 {
44 return true, NI(n), t0
45 }
46 t0 = to
47 }
48 }
49 return false, -1, -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) {
57 // similar code in dot/writeUndirected
58 unpaired := make(AdjacencyList, len(g))
59 for fr, to := range g {
60 arc: // for each arc in g
61 for _, to := range to {
62 if to == NI(fr) {
63 continue // loop
64 }
65 // search unpaired arcs
66 ut := unpaired[to]
67 for i, u := range ut {
68 if u == NI(fr) { // found reciprocal
69 last := len(ut) - 1
70 ut[i] = ut[last]
71 unpaired[to] = ut[:last]
72 continue arc
73 }
74 }
75 // reciprocal not found
76 unpaired[fr] = append(unpaired[fr], to)
77 }
78 }
79 for fr, to := range unpaired {
80 if len(to) > 0 {
81 return false, NI(fr), to[0]
82 }
83 }
84 return true, -1, -1
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 //
92 // See also WeightedEdgeList method.
93 func (g LabeledAdjacencyList) EdgeList() (el []LabeledEdge) {
94 for fr, to := range g {
95 for _, to := range to {
96 el = append(el, LabeledEdge{Edge{NI(fr), to.To}, to.Label})
97 }
98 }
99 return
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) {
112 d = newFWd(len(g))
113 for fr, to := range g {
114 for _, to := range to {
115 d[fr][to.To] = w(to.Label)
116 }
117 }
118 solveFW(d)
119 return
120 }
121
122 // little helper function, makes a blank matrix for FloydWarshall.
123 func newFWd(n int) [][]float64 {
124 d := make([][]float64, n)
125 for i := range d {
126 di := make([]float64, n)
127 for j := range di {
128 if j != i {
129 di[j] = math.Inf(1)
130 }
131 }
132 d[i] = di
133 }
134 return d
135 }
136
137 // Floyd Warshall solver, once the matrix d is initialized by arc weights.
138 func solveFW(d [][]float64) {
139 for k, dk := range d {
140 for _, di := range d {
141 dik := di[k]
142 for j := range d {
143 if d2 := dik + dk[j]; d2 < di[j] {
144 di[j] = d2
145 }
146 }
147 }
148 }
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) {
157 t := Half{to, l}
158 for x, h := range g[fr] {
159 if h == t {
160 return true, x
161 }
162 }
163 return false, -1
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) {
181 var t NodeList
182 for n, to := range g {
183 if len(to) == 0 {
184 continue
185 }
186 // slightly different code needed here compared to AdjacencyList
187 t = t[:0]
188 for _, to := range to {
189 t = append(t, to.To)
190 }
191 sort.Sort(t)
192 t0 := t[0]
193 for _, to := range t[1:] {
194 if to == t0 {
195 return true, NI(n), t0
196 }
197 t0 = to
198 }
199 }
200 return false, -1, -1
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) {
212 unpaired := make(LabeledAdjacencyList, len(g))
213 for fr, to := range g {
214 arc: // for each arc in g
215 for _, to := range to {
216 if to.To == NI(fr) {
217 continue // loop
218 }
219 // search unpaired arcs
220 ut := unpaired[to.To]
221 for i, u := range ut {
222 if u.To == NI(fr) && u.Label == to.Label { // found reciprocal
223 last := len(ut) - 1
224 ut[i] = ut[last]
225 unpaired[to.To] = ut[:last]
226 continue arc
227 }
228 }
229 // reciprocal not found
230 unpaired[fr] = append(unpaired[fr], to)
231 }
232 }
233 for fr, to := range unpaired {
234 if len(to) > 0 {
235 return false, NI(fr), to[0]
236 }
237 }
238 return true, -1, to
239 }
240
241 // NegativeArc returns true if the receiver graph contains a negative arc.
242 func (g LabeledAdjacencyList) NegativeArc(w WeightFunc) bool {
243 for _, nbs := range g {
244 for _, nb := range nbs {
245 if w(nb.Label) < 0 {
246 return true
247 }
248 }
249 }
250 return false
251 }
252
253 // Unlabeled constructs the unlabeled graph corresponding to g.
254 func (g LabeledAdjacencyList) Unlabeled() AdjacencyList {
255 a := make(AdjacencyList, len(g))
256 for n, nbs := range g {
257 to := make([]NI, len(nbs))
258 for i, nb := range nbs {
259 to[i] = nb.To
260 }
261 a[n] = to
262 }
263 return a
264 }
265
266 // WeightedEdgeList constructs a WeightedEdgeList object from a
267 // LabeledAdjacencyList.
268 //
269 // Internally it calls g.EdgeList() to obtain the Edges member.
270 // See LabeledAdjacencyList.EdgeList().
271 func (g LabeledAdjacencyList) WeightedEdgeList(w WeightFunc) *WeightedEdgeList {
272 return &WeightedEdgeList{
273 Order: len(g),
274 WeightFunc: w,
275 Edges: g.EdgeList(),
276 }
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 {
289 ind := make([]float64, len(g))
290 for _, to := range g {
291 for _, to := range to {
292 ind[to.To] += w(to.Label)
293 }
294 }
295 return ind
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) {
312 for _, to := range g[n] {
313 d += w(to.Label)
314 }
315 return
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.