forked from purpleidea/mgmt
-
Notifications
You must be signed in to change notification settings - Fork 0
/
pgraph.go
696 lines (623 loc) · 20 KB
/
pgraph.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
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
// Mgmt
// Copyright (C) 2013-2018+ James Shubin and the project contributors
// Written by James Shubin <james@shubin.ca> and the project contributors
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
// Package pgraph represents the internal "pointer graph" that we use.
package pgraph
import (
"fmt"
"sort"
"strings"
errwrap "github.com/pkg/errors"
)
// Graph is the graph structure in this library.
// The graph abstract data type (ADT) is defined as follows:
// * the directed graph arrows point from left to right ( -> )
// * the arrows point away from their dependencies (eg: arrows mean "before")
// * IOW, you might see package -> file -> service (where package runs first)
// * This is also the direction that the notify should happen in...
type Graph struct {
Name string
adjacency map[Vertex]map[Vertex]Edge // Vertex -> Vertex (edge)
kv map[string]interface{} // some values associated with the graph
}
// Vertex is the primary vertex struct in this library. It can be anything that
// implements Stringer. The string output must be stable and unique in a graph.
type Vertex interface {
fmt.Stringer // String() string
}
// Edge is the primary edge struct in this library. It can be anything that
// implements Stringer. The string output must be stable and unique in a graph.
type Edge interface {
fmt.Stringer // String() string
}
// Init initializes the graph which populates all the internal structures.
func (g *Graph) Init() error {
if g.Name == "" { // FIXME: is this really a good requirement?
return fmt.Errorf("can't initialize graph with empty name")
}
if g.adjacency == nil {
g.adjacency = make(map[Vertex]map[Vertex]Edge)
}
//g.kv = make(map[string]interface{}) // not required
return nil
}
// NewGraph builds a new graph.
func NewGraph(name string) (*Graph, error) {
g := &Graph{
Name: name,
}
if err := g.Init(); err != nil {
return nil, err
}
return g, nil
}
// Value returns a value stored alongside the graph in a particular key.
func (g *Graph) Value(key string) (interface{}, bool) {
val, exists := g.kv[key]
return val, exists
}
// SetValue sets a value to be stored alongside the graph in a particular key.
func (g *Graph) SetValue(key string, val interface{}) {
if g.kv == nil { // initialize on first use
g.kv = make(map[string]interface{})
}
g.kv[key] = val
}
// Copy makes a copy of the graph struct.
func (g *Graph) Copy() *Graph {
if g == nil { // allow nil graphs through
return g
}
newGraph := &Graph{
Name: g.Name,
adjacency: make(map[Vertex]map[Vertex]Edge, len(g.adjacency)),
kv: g.kv,
}
for k, v := range g.adjacency {
newGraph.adjacency[k] = v // copy
}
return newGraph
}
// GetName returns the name of the graph.
func (g *Graph) GetName() string {
return g.Name
}
// SetName sets the name of the graph.
func (g *Graph) SetName(name string) {
g.Name = name
}
// AddVertex uses variadic input to add all listed vertices to the graph.
func (g *Graph) AddVertex(xv ...Vertex) {
if g.adjacency == nil { // initialize on first use
g.adjacency = make(map[Vertex]map[Vertex]Edge)
}
for _, v := range xv {
if _, exists := g.adjacency[v]; !exists {
g.adjacency[v] = make(map[Vertex]Edge)
}
}
}
// DeleteVertex deletes a particular vertex from the graph.
func (g *Graph) DeleteVertex(v Vertex) {
delete(g.adjacency, v)
for k := range g.adjacency {
delete(g.adjacency[k], v)
}
}
// AddEdge adds a directed edge to the graph from v1 to v2.
func (g *Graph) AddEdge(v1, v2 Vertex, e Edge) {
// NOTE: this doesn't allow more than one edge between two vertexes...
g.AddVertex(v1, v2) // supports adding N vertices now
// TODO: check if an edge exists to avoid overwriting it!
// NOTE: VertexMerge() depends on overwriting it at the moment...
g.adjacency[v1][v2] = e
}
// DeleteEdge deletes a particular edge from the graph.
func (g *Graph) DeleteEdge(e Edge) {
for v1 := range g.adjacency {
for v2, edge := range g.adjacency[v1] {
if e == edge {
delete(g.adjacency[v1], v2)
}
}
}
}
// HasVertex returns if the input vertex exists in the graph.
func (g *Graph) HasVertex(v Vertex) bool {
if _, exists := g.adjacency[v]; exists {
return true
}
return false
}
// NumVertices returns the number of vertices in the graph.
func (g *Graph) NumVertices() int {
return len(g.adjacency)
}
// NumEdges returns the number of edges in the graph.
func (g *Graph) NumEdges() int {
count := 0
for k := range g.adjacency {
count += len(g.adjacency[k])
}
return count
}
// Adjacency returns the adjacency map representing this graph. This is useful
// for users who which to operate on the raw data structure more efficiently.
// This works because maps are reference types so we can edit this at will.
func (g *Graph) Adjacency() map[Vertex]map[Vertex]Edge {
return g.adjacency
}
// FindEdge returns the edge from v1 -> v2 if it exists. Otherwise nil.
func (g *Graph) FindEdge(v1, v2 Vertex) Edge {
x, exists := g.adjacency[v1]
if !exists {
return nil // not found
}
edge, exists := x[v2]
if !exists {
return nil
}
return edge
}
// Vertices returns a randomly sorted slice of all vertices in the graph.
// The order is random, because the map implementation is intentionally so!
func (g *Graph) Vertices() []Vertex {
var vertices []Vertex
for k := range g.adjacency {
vertices = append(vertices, k)
}
return vertices
}
// Edges returns a randomly sorted slice of all edges in the graph.
// The order is random, because the map implementation is intentionally so!
func (g *Graph) Edges() []Edge {
var edges []Edge
for vertex := range g.adjacency {
for _, edge := range g.adjacency[vertex] {
edges = append(edges, edge)
}
}
return edges
}
// VerticesChan returns a channel of all vertices in the graph.
func (g *Graph) VerticesChan() chan Vertex {
ch := make(chan Vertex)
go func(ch chan Vertex) {
for k := range g.adjacency {
ch <- k
}
close(ch)
}(ch)
return ch
}
// VertexSlice is a linear list of vertices. It can be sorted.
type VertexSlice []Vertex
func (vs VertexSlice) Len() int { return len(vs) }
func (vs VertexSlice) Swap(i, j int) { vs[i], vs[j] = vs[j], vs[i] }
func (vs VertexSlice) Less(i, j int) bool { return vs[i].String() < vs[j].String() }
// VerticesSorted returns a sorted slice of all vertices in the graph.
// The order is sorted by String() to avoid the non-determinism in the map type.
func (g *Graph) VerticesSorted() []Vertex {
var vertices []Vertex
for k := range g.adjacency {
vertices = append(vertices, k)
}
sort.Sort(VertexSlice(vertices)) // add determinism
return vertices
}
// String makes the graph pretty print.
func (g *Graph) String() string {
if g == nil { // don't panic if we're printing a nil graph
return fmt.Sprintf("%v", nil) // prints a <nil>
}
return fmt.Sprintf("Vertices(%d), Edges(%d)", g.NumVertices(), g.NumEdges())
}
// Sprint prints a full graph in textual form out to a string. To log this you
// might want to use Logf, which will keep everything aligned with whatever your
// logging prefix is.
func (g *Graph) Sprint() string {
var str string
for v := range g.Adjacency() {
str += fmt.Sprintf("Vertex: %s\n", v)
}
for v1 := range g.Adjacency() {
for v2, e := range g.Adjacency()[v1] {
str += fmt.Sprintf("Edge: %s -> %s # %s\n", v1, v2, e)
}
}
return strings.TrimSuffix(str, "\n") // trim off trailing \n if it exists
}
// Logf logs a printed representation of the graph with the logf of your choice.
// This is helpful to ensure each line of logged output has the prefix you want.
func (g *Graph) Logf(logf func(format string, v ...interface{})) {
for _, x := range strings.Split(g.Sprint(), "\n") {
logf("%s", x)
}
}
// IncomingGraphVertices returns an array (slice) of all directed vertices to
// vertex v (??? -> v). OKTimestamp should probably use this.
func (g *Graph) IncomingGraphVertices(v Vertex) []Vertex {
// TODO: we might be able to implement this differently by reversing
// the Adjacency graph and then looping through it again...
var s []Vertex
for k := range g.adjacency { // reverse paths
for w := range g.adjacency[k] {
if w == v {
s = append(s, k)
}
}
}
return s
}
// OutgoingGraphVertices returns an array (slice) of all vertices that vertex v
// points to (v -> ???). Poke should probably use this.
func (g *Graph) OutgoingGraphVertices(v Vertex) []Vertex {
var s []Vertex
for k := range g.adjacency[v] { // forward paths
s = append(s, k)
}
return s
}
// GraphVertices returns an array (slice) of all vertices that connect to vertex v.
// This is the union of IncomingGraphVertices and OutgoingGraphVertices.
func (g *Graph) GraphVertices(v Vertex) []Vertex {
var s []Vertex
s = append(s, g.IncomingGraphVertices(v)...)
s = append(s, g.OutgoingGraphVertices(v)...)
return s
}
// IncomingGraphEdges returns all of the edges that point to vertex v (??? -> v).
func (g *Graph) IncomingGraphEdges(v Vertex) []Edge {
var edges []Edge
for v1 := range g.adjacency { // reverse paths
for v2, e := range g.adjacency[v1] {
if v2 == v {
edges = append(edges, e)
}
}
}
return edges
}
// OutgoingGraphEdges returns all of the edges that point from vertex v (v -> ???).
func (g *Graph) OutgoingGraphEdges(v Vertex) []Edge {
var edges []Edge
for _, e := range g.adjacency[v] { // forward paths
edges = append(edges, e)
}
return edges
}
// GraphEdges returns an array (slice) of all edges that connect to vertex v.
// This is the union of IncomingGraphEdges and OutgoingGraphEdges.
func (g *Graph) GraphEdges(v Vertex) []Edge {
var edges []Edge
edges = append(edges, g.IncomingGraphEdges(v)...)
edges = append(edges, g.OutgoingGraphEdges(v)...)
return edges
}
// DFS returns a depth first search for the graph, starting at the input vertex.
func (g *Graph) DFS(start Vertex) []Vertex {
var d []Vertex // discovered
var s []Vertex // stack
if _, exists := g.adjacency[start]; !exists {
return nil // TODO: error
}
v := start
s = append(s, v)
for len(s) > 0 {
v, s = s[len(s)-1], s[:len(s)-1] // s.pop()
if !VertexContains(v, d) { // if not discovered
d = append(d, v) // label as discovered
for _, w := range g.GraphVertices(v) {
s = append(s, w)
}
}
}
return d
}
// FilterGraph builds a new graph containing only vertices from the list.
func (g *Graph) FilterGraph(name string, vertices []Vertex) (*Graph, error) {
newGraph := &Graph{Name: name}
if err := newGraph.Init(); err != nil {
return nil, errwrap.Wrapf(err, "could not run FilterGraph() properly")
}
for k1, x := range g.adjacency {
for k2, e := range x {
//log.Printf("Filter: %s -> %s # %s", k1.Name, k2.Name, e.Name)
if VertexContains(k1, vertices) || VertexContains(k2, vertices) {
newGraph.AddEdge(k1, k2, e)
}
}
}
return newGraph, nil
}
// DisconnectedGraphs returns a list containing the N disconnected graphs.
func (g *Graph) DisconnectedGraphs() ([]*Graph, error) {
graphs := []*Graph{}
var start Vertex
var d []Vertex // discovered
c := g.NumVertices()
for len(d) < c {
// get an undiscovered vertex to start from
for _, s := range g.Vertices() {
if !VertexContains(s, d) {
start = s
}
}
// dfs through the graph
dfs := g.DFS(start)
// filter all the collected elements into a new graph
newgraph, err := g.FilterGraph(g.Name, dfs)
if err != nil {
return nil, errwrap.Wrapf(err, "could not run DisconnectedGraphs() properly")
}
// add number of elements found to found variable
d = append(d, dfs...) // extend
// append this new graph to the list
graphs = append(graphs, newgraph)
// if we've found all the elements, then we're done
// otherwise loop through to continue...
}
return graphs, nil
}
// InDegree returns the count of vertices that point to me in one big lookup map.
func (g *Graph) InDegree() map[Vertex]int {
result := make(map[Vertex]int)
if g == nil || g.adjacency == nil {
return result
}
for k := range g.adjacency {
result[k] = 0 // initialize
}
for k := range g.adjacency {
for z := range g.adjacency[k] {
result[z]++
}
}
return result
}
// OutDegree returns the count of vertices that point away in one big lookup map.
func (g *Graph) OutDegree() map[Vertex]int {
result := make(map[Vertex]int)
if g == nil || g.adjacency == nil {
return result
}
for k := range g.adjacency {
result[k] = 0 // initialize
for range g.adjacency[k] {
result[k]++
}
}
return result
}
// TopologicalSort returns the sort of graph vertices in that order.
// It is based on descriptions and code from wikipedia and rosetta code.
// TODO: add memoization, and cache invalidation to speed this up :)
func (g *Graph) TopologicalSort() ([]Vertex, error) { // kahn's algorithm
var L []Vertex // empty list that will contain the sorted elements
var S []Vertex // set of all nodes with no incoming edges
remaining := make(map[Vertex]int) // amount of edges remaining
for v, d := range g.InDegree() {
if d == 0 {
// accumulate set of all nodes with no incoming edges
S = append(S, v)
} else {
// initialize remaining edge count from indegree
remaining[v] = d
}
}
for len(S) > 0 {
last := len(S) - 1 // remove a node v from S
v := S[last]
S = S[:last]
L = append(L, v) // add v to tail of L
for n := range g.adjacency[v] {
// for each node n remaining in the graph, consume from
// remaining, so for remaining[n] > 0
if remaining[n] > 0 {
remaining[n]-- // remove edge from the graph
if remaining[n] == 0 { // if n has no other incoming edges
S = append(S, n) // insert n into S
}
}
}
}
// if graph has edges, eg if any value in rem is > 0
for c, in := range remaining {
if in > 0 {
for n := range g.adjacency[c] {
if remaining[n] > 0 {
return nil, fmt.Errorf("not a dag")
}
}
}
}
return L, nil
}
// Reachability finds the shortest path in a DAG from a to b, and returns the
// slice of vertices that matched this particular path including both a and b.
// It returns nil if a or b is nil, and returns empty list if no path is found.
// Since there could be more than one possible result for this operation, we
// arbitrarily choose one of the shortest possible. As a result, this should
// actually return a tree if we cared about correctness.
// This operates by a recursive algorithm; a more efficient version is likely.
// If you don't give this function a DAG, you might cause infinite recursion!
func (g *Graph) Reachability(a, b Vertex) ([]Vertex, error) {
if a == nil || b == nil {
return nil, fmt.Errorf("empty vertex")
}
if _, err := g.TopologicalSort(); err != nil {
return nil, err // not a dag?
}
vertices := g.OutgoingGraphVertices(a) // what points away from a ?
if len(vertices) == 0 {
return []Vertex{}, nil // nope
}
if VertexContains(b, vertices) {
return []Vertex{a, b}, nil // found
}
// TODO: parallelize this with go routines?
var collected = make([][]Vertex, len(vertices))
var err error
pick := -1
for i, v := range vertices {
collected[i], err = g.Reachability(v, b) // find b by recursion
if err != nil {
return nil, err
}
if l := len(collected[i]); l > 0 {
// pick shortest path
// TODO: technically i should return a tree
if pick < 0 || l < len(collected[pick]) {
pick = i
}
}
}
if pick < 0 {
return []Vertex{}, nil // nope
}
result := []Vertex{a} // tack on a
result = append(result, collected[pick]...)
return result, nil
}
// VertexMatchFn searches for a vertex in the graph and returns the vertex if
// one matches. It uses a user defined function to match. That function must
// return true on match, and an error if anything goes wrong.
func (g *Graph) VertexMatchFn(fn func(Vertex) (bool, error)) (Vertex, error) {
for v := range g.adjacency {
if b, err := fn(v); err != nil {
return nil, errwrap.Wrapf(err, "fn in VertexMatchFn() errored")
} else if b {
return v, nil
}
}
return nil, nil // nothing found
}
// GraphCmp compares the topology of this graph to another and returns nil if
// they're equal. It uses a user defined function to compare topologically
// equivalent vertices, and edges.
// FIXME: add more test cases
func (g *Graph) GraphCmp(graph *Graph, vertexCmpFn func(Vertex, Vertex) (bool, error), edgeCmpFn func(Edge, Edge) (bool, error)) error {
if graph == nil || g == nil {
if graph != g {
return fmt.Errorf("one graph is nil")
}
return nil
}
n1, n2 := g.NumVertices(), graph.NumVertices()
if n1 != n2 {
return fmt.Errorf("base graph has %d vertices, while input graph has %d", n1, n2)
}
if e1, e2 := g.NumEdges(), graph.NumEdges(); e1 != e2 {
return fmt.Errorf("base graph has %d edges, while input graph has %d", e1, e2)
}
var m = make(map[Vertex]Vertex) // g to graph vertex correspondence
Loop:
// check vertices
for v1 := range g.Adjacency() { // for each vertex in g
for v2 := range graph.Adjacency() { // does it match in graph ?
b, err := vertexCmpFn(v1, v2)
if err != nil {
return errwrap.Wrapf(err, "could not run vertexCmpFn() properly")
}
// does it match ?
if b {
m[v1] = v2 // store the mapping
continue Loop
}
}
return fmt.Errorf("base graph, has no match in input graph for: %s", v1)
}
// vertices match :)
// is the mapping the right length?
if n1 := len(m); n1 != n2 {
return fmt.Errorf("mapping only has correspondence of %d, when it should have %d", n1, n2)
}
// check if mapping is unique (are there duplicates?)
m1 := []Vertex{}
m2 := []Vertex{}
for k, v := range m {
if VertexContains(k, m1) {
return fmt.Errorf("mapping from %s is used more than once to: %s", k, m1)
}
if VertexContains(v, m2) {
return fmt.Errorf("mapping to %s is used more than once from: %s", v, m2)
}
m1 = append(m1, k)
m2 = append(m2, v)
}
// check edges
for v1 := range g.Adjacency() { // for each vertex in g
v2 := m[v1] // lookup in map to get correspondance
// g.Adjacency()[v1] corresponds to graph.Adjacency()[v2]
if e1, e2 := len(g.Adjacency()[v1]), len(graph.Adjacency()[v2]); e1 != e2 {
return fmt.Errorf("base graph, vertex(%s) has %d edges, while input graph, vertex(%s) has %d", v1, e1, v2, e2)
}
for vv1, ee1 := range g.Adjacency()[v1] {
vv2 := m[vv1]
ee2 := graph.Adjacency()[v2][vv2]
// these are edges from v1 -> vv1 via ee1 (graph 1)
// to cmp to edges from v2 -> vv2 via ee2 (graph 2)
// check: (1) vv1 == vv2 ? (we've already checked this!)
// check: (2) ee1 == ee2
b, err := edgeCmpFn(ee1, ee2)
if err != nil {
return errwrap.Wrapf(err, "could not run edgeCmpFn() properly")
}
if !b {
return fmt.Errorf("base graph edge(%s) doesn't match input graph edge(%s)", ee1, ee2)
}
}
}
return nil // success!
}
// VertexContains is an "in array" function to test for a vertex in a slice of vertices.
func VertexContains(needle Vertex, haystack []Vertex) bool {
for _, v := range haystack {
if needle == v {
return true
}
}
return false
}
// EdgeContains is an "in array" function to test for an edge in a slice of edges.
func EdgeContains(needle Edge, haystack []Edge) bool {
for _, v := range haystack {
if needle == v {
return true
}
}
return false
}
// Reverse reverses a list of vertices.
func Reverse(vs []Vertex) []Vertex {
out := []Vertex{}
l := len(vs)
for i := range vs {
out = append(out, vs[l-i-1])
}
return out
}
// Sort the list of vertices and return a copy without modifying the input.
func Sort(vs []Vertex) []Vertex {
vertices := []Vertex{}
for _, v := range vs { // copy
vertices = append(vertices, v)
}
sort.Sort(VertexSlice(vertices))
return vertices
// sort.Sort(VertexSlice(vs)) // this is wrong, it would modify input!
//return vs
}