-
Notifications
You must be signed in to change notification settings - Fork 7
/
adj.go
399 lines (376 loc) · 11.3 KB
/
adj.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
// Copyright 2014 Sonia Keys
// License MIT: https://opensource.org/licenses/MIT
package graph
// adj.go contains methods on AdjacencyList and LabeledAdjacencyList.
//
// AdjacencyList methods are placed first and are alphabetized.
// LabeledAdjacencyList methods follow, also alphabetized.
// Only exported methods need be alphabetized; non-exported methods can
// be left near their use.
import (
"sort"
"github.com/soniakeys/bits"
)
// AnyParallel identifies if a graph contains parallel arcs, multiple arcs
// that lead from a node to the same node.
//
// If the graph has parallel arcs, the results fr and to represent an example
// where there are parallel arcs from node `fr` to node `to`.
//
// If there are no parallel arcs, the method returns false -1 -1.
//
// Multiple loops on a node count as parallel arcs.
//
// See also alt.AnyParallelMap, which can perform better for some large
// or dense graphs.
func (g AdjacencyList) AnyParallel() (has bool, fr, to NI) {
var t []NI
for n, to := range g {
if len(to) == 0 {
continue
}
// different code in the labeled version, so no code gen.
t = append(t[:0], to...)
sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
t0 := t[0]
for _, to := range t[1:] {
if to == t0 {
return true, NI(n), t0
}
t0 = to
}
}
return false, -1, -1
}
// Complement returns the arc-complement of a simple graph.
//
// The result will have an arc for every pair of distinct nodes where there
// is not an arc in g. The complement is valid for both directed and
// undirected graphs. If g is undirected, the complement will be undirected.
// The result will always be a simple graph, having no loops or parallel arcs.
func (g AdjacencyList) Complement() AdjacencyList {
c := make(AdjacencyList, len(g))
b := bits.New(len(g))
for n, to := range g {
b.ClearAll()
for _, to := range to {
b.SetBit(int(to), 1)
}
b.SetBit(n, 1)
ct := make([]NI, len(g)-b.OnesCount())
i := 0
b.IterateZeros(func(to int) bool {
ct[i] = NI(to)
i++
return true
})
c[n] = ct
}
return c
}
// IsUndirected returns true if g represents an undirected graph.
//
// Returns true when all non-loop arcs are paired in reciprocal pairs.
// Otherwise returns false and an example unpaired arc.
func (g AdjacencyList) IsUndirected() (u bool, from, to NI) {
// similar code in dot/writeUndirected
unpaired := make(AdjacencyList, len(g))
for fr, to := range g {
arc: // for each arc in g
for _, to := range to {
if to == NI(fr) {
continue // loop
}
// search unpaired arcs
ut := unpaired[to]
for i, u := range ut {
if u == NI(fr) { // found reciprocal
last := len(ut) - 1
ut[i] = ut[last]
unpaired[to] = ut[:last]
continue arc
}
}
// reciprocal not found
unpaired[fr] = append(unpaired[fr], to)
}
}
for fr, to := range unpaired {
if len(to) > 0 {
return false, NI(fr), to[0]
}
}
return true, -1, -1
}
// SortArcLists sorts the arc lists of each node of receiver g.
//
// Nodes are not relabeled and the graph remains equivalent.
func (g AdjacencyList) SortArcLists() {
for _, to := range g {
sort.Slice(to, func(i, j int) bool { return to[i] < to[j] })
}
}
// ------- Labeled methods below -------
// ArcsAsEdges constructs an edge list with an edge for each arc, including
// reciprocals.
//
// This is a simple way to construct an edge list for algorithms that allow
// the duplication represented by the reciprocal arcs. (e.g. Kruskal)
//
// See also LabeledUndirected.Edges for the edge list without this duplication.
func (g LabeledAdjacencyList) ArcsAsEdges() (el []LabeledEdge) {
for fr, to := range g {
for _, to := range to {
el = append(el, LabeledEdge{Edge{NI(fr), to.To}, to.Label})
}
}
return
}
// DistanceMatrix constructs a distance matrix corresponding to the arcs
// of graph g and weight function w.
//
// An arc from f to t with WeightFunc return w is represented by d[f][t] == w.
// In case of parallel arcs, the lowest weight is stored. The distance from
// any node to itself d[n][n] is 0, unless the node has a loop with a negative
// weight. If g has no arc from f to distinct t, +Inf is stored for d[f][t].
//
// The returned DistanceMatrix is suitable for DistanceMatrix.FloydWarshall.
func (g LabeledAdjacencyList) DistanceMatrix(w WeightFunc) (d DistanceMatrix) {
d = newDM(len(g))
for fr, to := range g {
for _, to := range to {
// < to pick min of parallel arcs (also nicely ignores NaN)
if wt := w(to.Label); wt < d[fr][to.To] {
d[fr][to.To] = wt
}
}
}
return
}
// HasArcLabel returns true if g has any arc from node `fr` to node `to`
// with label `l`.
//
// Also returned is the index within the slice of arcs from node `fr`.
// If no arc from `fr` to `to` with label `l` is present, HasArcLabel returns
// false, -1.
func (g LabeledAdjacencyList) HasArcLabel(fr, to NI, l LI) (bool, int) {
t := Half{to, l}
for x, h := range g[fr] {
if h == t {
return true, x
}
}
return false, -1
}
// AnyParallel identifies if a graph contains parallel arcs, multiple arcs
// that lead from a node to the same node.
//
// If the graph has parallel arcs, the results fr and to represent an example
// where there are parallel arcs from node `fr` to node `to`.
//
// If there are no parallel arcs, the method returns -1 -1.
//
// Multiple loops on a node count as parallel arcs.
//
// See also alt.AnyParallelMap, which can perform better for some large
// or dense graphs.
func (g LabeledAdjacencyList) AnyParallel() (has bool, fr, to NI) {
var t []NI
for n, to := range g {
if len(to) == 0 {
continue
}
// slightly different code needed here compared to AdjacencyList
t = t[:0]
for _, to := range to {
t = append(t, to.To)
}
sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
t0 := t[0]
for _, to := range t[1:] {
if to == t0 {
return true, NI(n), t0
}
t0 = to
}
}
return false, -1, -1
}
// AnyParallelLabel identifies if a graph contains parallel arcs with the same
// label.
//
// If the graph has parallel arcs with the same label, the results fr and to
// represent an example where there are parallel arcs from node `fr`
// to node `to`.
//
// If there are no parallel arcs, the method returns false -1 Half{}.
//
// Multiple loops on a node count as parallel arcs.
func (g LabeledAdjacencyList) AnyParallelLabel() (has bool, fr NI, to Half) {
var t []Half
for n, to := range g {
if len(to) == 0 {
continue
}
// slightly different code needed here compared to AdjacencyList
t = t[:0]
for _, to := range to {
t = append(t, to)
}
sort.Slice(t, func(i, j int) bool {
return t[i].To < t[j].To ||
t[i].To == t[j].To && t[i].Label < t[j].Label
})
t0 := t[0]
for _, to := range t[1:] {
if to == t0 {
return true, NI(n), t0
}
t0 = to
}
}
return false, -1, Half{}
}
// IsUndirected returns true if g represents an undirected graph.
//
// Returns true when all non-loop arcs are paired in reciprocal pairs with
// matching labels. Otherwise returns false and an example unpaired arc.
//
// Note the requirement that reciprocal pairs have matching labels is
// an additional test not present in the otherwise equivalent unlabeled version
// of IsUndirected.
func (g LabeledAdjacencyList) IsUndirected() (u bool, from NI, to Half) {
// similar code in LabeledAdjacencyList.Edges
unpaired := make(LabeledAdjacencyList, len(g))
for fr, to := range g {
arc: // for each arc in g
for _, to := range to {
if to.To == NI(fr) {
continue // loop
}
// search unpaired arcs
ut := unpaired[to.To]
for i, u := range ut {
if u.To == NI(fr) && u.Label == to.Label { // found reciprocal
last := len(ut) - 1
ut[i] = ut[last]
unpaired[to.To] = ut[:last]
continue arc
}
}
// reciprocal not found
unpaired[fr] = append(unpaired[fr], to)
}
}
for fr, to := range unpaired {
if len(to) > 0 {
return false, NI(fr), to[0]
}
}
return true, -1, to
}
// ArcLabels constructs the multiset of LIs present in g.
func (g LabeledAdjacencyList) ArcLabels() map[LI]int {
s := map[LI]int{}
for _, to := range g {
for _, to := range to {
s[to.Label]++
}
}
return s
}
// NegativeArc returns true if the receiver graph contains a negative arc.
func (g LabeledAdjacencyList) NegativeArc(w WeightFunc) bool {
for _, nbs := range g {
for _, nb := range nbs {
if w(nb.Label) < 0 {
return true
}
}
}
return false
}
// ParallelArcsLabel identifies all arcs from node `fr` to node `to` with label `l`.
//
// The returned slice contains an element for each arc from node `fr` to node `to`
// with label `l`. The element value is the index within the slice of arcs from node
// `fr`.
//
// See also the method HasArcLabel, which stops after finding a single arc.
func (g LabeledAdjacencyList) ParallelArcsLabel(fr, to NI, l LI) (p []int) {
t := Half{to, l}
for x, h := range g[fr] {
if h == t {
p = append(p, x)
}
}
return
}
// Unlabeled constructs the unlabeled graph corresponding to g.
func (g LabeledAdjacencyList) Unlabeled() AdjacencyList {
a := make(AdjacencyList, len(g))
for n, nbs := range g {
to := make([]NI, len(nbs))
for i, nb := range nbs {
to[i] = nb.To
}
a[n] = to
}
return a
}
// WeightedArcsAsEdges constructs a WeightedEdgeList object from the receiver.
//
// Internally it calls g.ArcsAsEdges() to obtain the Edges member.
// See LabeledAdjacencyList.ArcsAsEdges().
func (g LabeledAdjacencyList) WeightedArcsAsEdges(w WeightFunc) *WeightedEdgeList {
return &WeightedEdgeList{
Order: g.Order(),
WeightFunc: w,
Edges: g.ArcsAsEdges(),
}
}
// WeightedInDegree computes the weighted in-degree of each node in g
// for a given weight function w.
//
// The weighted in-degree of a node is the sum of weights of arcs going to
// the node.
//
// A weighted degree of a node is often termed the "strength" of a node.
//
// See note for undirected graphs at LabeledAdjacencyList.WeightedOutDegree.
func (g LabeledAdjacencyList) WeightedInDegree(w WeightFunc) []float64 {
ind := make([]float64, len(g))
for _, to := range g {
for _, to := range to {
ind[to.To] += w(to.Label)
}
}
return ind
}
// WeightedOutDegree computes the weighted out-degree of the specified node
// for a given weight function w.
//
// The weighted out-degree of a node is the sum of weights of arcs going from
// the node.
//
// A weighted degree of a node is often termed the "strength" of a node.
//
// Note for undirected graphs, the WeightedOutDegree result for a node will
// equal the WeightedInDegree for the node. You can use WeightedInDegree if
// you have need for the weighted degrees of all nodes or use WeightedOutDegree
// to compute the weighted degrees of individual nodes. In either case loops
// are counted just once, unlike the (unweighted) UndirectedDegree methods.
func (g LabeledAdjacencyList) WeightedOutDegree(n NI, w WeightFunc) (d float64) {
for _, to := range g[n] {
d += w(to.Label)
}
return
}
// More about loops and strength: I didn't see consensus on this especially
// in the case of undirected graphs. Some sources said to add in-degree and
// out-degree, which would seemingly double both loops and non-loops.
// Some said to double loops. Some said sum the edge weights and had no
// comment on loops. R of course makes everything an option. The meaning
// of "strength" where loops exist is unclear. So while I could write an
// UndirectedWeighted degree function that doubles loops but not edges,
// I'm going to just leave this for now.