/
graph16.go
92 lines (77 loc) · 2.04 KB
/
graph16.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
package graph // import "github.com/andrewarchi/graph"
import "math/bits"
// Graph16 is a directed graph with at most 16 nodes.
type Graph16 []uint16
var _ Graph = (Graph16)(nil)
// NewGraph16 constructs a graph with a given number of nodes.
func NewGraph16(rank uint) Graph16 {
if rank > 16 {
panic("graph: Graph16 rank out of bounds")
}
return make(Graph16, rank)
}
// Add adds a directed edge from node i to j.
func (g Graph16) Add(i, j uint) {
g[i] |= 1 << j
}
// AddUndirected adds an undirected edge between nodes i and j.
func (g Graph16) AddUndirected(i, j uint) {
g[i] |= 1 << j
g[j] |= 1 << i
}
// Clear removes the directed edge from node i to j.
func (g Graph16) Clear(i, j uint) {
g[i] &^= 1 << j
}
// Swap isomorphically swaps nodes i and j.
func (g Graph16) Swap(i, j uint) {
g[i], g[j] = g[j], g[i]
for n, node := range g {
// Swap individual bits
// http://graphics.stanford.edu/~seander/bithacks.html#SwappingBitsXOR
x := (node>>i ^ node>>j) & 0x1
g[n] = node ^ (x<<i | x<<j)
}
}
// Has returns whether an edge connects node i to j.
func (g Graph16) Has(i, j uint) bool {
return g[i]&(1<<j) != 0
}
// Copy creates a copy of the graph.
func (g Graph16) Copy() Graph {
h := make(Graph16, len(g))
copy(h, g)
return h
}
// Reverse creates a graph with reversed edges.
func (g Graph16) Reverse() Graph {
h := make(Graph16, len(g))
for i, node := range g {
for node != 0 {
j := uint(bits.TrailingZeros16(node))
h.Add(j, uint(i))
node &^= 1 << j
}
}
return h
}
// OutDegree returns the number of edges directed from the given node.
func (g Graph16) OutDegree(i uint) int {
return bits.OnesCount16(uint16(g[i]))
}
// InDegree returns the number of edges directed to the given node.
func (g Graph16) InDegree(i uint) int {
d := 0
for j := 0; j < len(g); j++ {
d += int((g[j] >> i) & 0x1)
}
return d
}
// Len returns the number of nodes in the graph.
func (g Graph16) Len() int {
return len(g)
}
// String formats the graph as a list of edges on a single line.
func (g Graph16) String() string {
return FormatList(g)
}