forked from aaasen/kapok
-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.go
157 lines (126 loc) · 3.56 KB
/
graph.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
// A memory-efficient graph for large datasets.
//
// Time complexities:
// Storage: O(V + E)
// Add Node: O(1)
// Add Arc: O(1)
// Remove Node: O(E)
// Remove Arc: O(1)
package graph
import (
"encoding/gob"
"fmt"
"io"
"strings"
)
// Graph is memory-efficient labeled graph for large datasets.
type Graph struct {
Nodes map[*Node][]*Node
Names map[string]*Node
}
// NewGraph returns an empty graph.
func NewGraph() *Graph {
return &Graph{
Nodes: make(map[*Node][]*Node),
Names: make(map[string]*Node),
}
}
// Get returns the node with the given name or null if none exists.
func (self *Graph) Get(name string) *Node {
return self.Names[name]
}
// SafeGet returns the node with the given name
// or creates a new node with the given name if one does not exist.
func (self *Graph) SafeGet(name string) *Node {
node := self.Names[name]
if node == nil {
node = NewNode(name)
self.Add(node)
}
return node
}
// Add adds a node to the graph.
func (self *Graph) Add(node *Node) {
self.Nodes[node] = make([]*Node, 0)
self.Names[node.Name] = node
}
// Remove removes a node from the graph along with all arcs pointing to it.
func (self *Graph) Remove(node *Node) {
delete(self.Nodes, node)
delete(self.Names, node.Name)
for neighbor, _ := range self.Nodes {
self.RemoveArc(node, neighbor)
}
}
// AddArc adds an arc between the origin and destination nodes.
func (self *Graph) AddArc(origin *Node, dest *Node) {
self.Nodes[origin] = append(self.Nodes[origin], dest)
}
// RemoveArc removes the arc between the origin and destination nodes.
func (self *Graph) RemoveArc(origin *Node, toRemove *Node) {
i := indexOf(self.Nodes[origin], toRemove)
if i >= 0 {
self.Nodes[origin] = append(self.Nodes[origin][:i], self.Nodes[origin][i+1:]...)
}
}
// Adjacent returns true if the origin node has an arc to the destination node
// and false otherwise.
func (self *Graph) Adjacent(origin *Node, target *Node) bool {
destIndex := indexOf(self.Nodes[origin], target)
if destIndex == -1 {
return false
}
return true
}
// Neighbors returns all nodes that the given node points to.
func (self *Graph) Neighbors(origin *Node) []*Node {
return self.Nodes[origin]
}
// PointingTo returns all nodes that have arcs to the given node
func (self *Graph) PointingTo(dest *Node) []*Node {
nodes := make([]*Node, 0)
for node, _ := range self.Nodes {
if self.Adjacent(node, dest) {
nodes = append(nodes, node)
}
}
return nodes
}
// String creates a string representation of the graph in the following form:
//
// node -> neighbor, neighbor, neighbor
func (self *Graph) String() string {
str := ""
for node, neighbors := range self.Nodes {
str += fmt.Sprintf("%s -> (", node.String())
neighborStrings := make([]string, len(neighbors))
for i, neighbor := range neighbors {
neighborStrings[i] = neighbor.String()
}
str += strings.Join(neighborStrings, ", ")
str += ")\n"
}
return str
}
// Export writes a gob dump of the graph to the given writer
// and returns any error that it encounters.
func (self *Graph) Export(writer io.Writer) error {
encoder := gob.NewEncoder(writer)
return encoder.Encode(self)
}
// Import creates a graph from a gob dump in the given writer.
// and returns any errors that it encounters.
func Import(reader io.Reader) (error, *Graph) {
decoder := gob.NewDecoder(reader)
var graph Graph
return decoder.Decode(&graph), &graph
}
// indexOf returns the index of the value in a slice or -1 if it is not found.
func indexOf(slice []*Node, target *Node) int {
for i, node := range slice {
if node == target {
return i
}
}
return -1
}