-
Notifications
You must be signed in to change notification settings - Fork 0
/
node.go
191 lines (173 loc) · 5.59 KB
/
node.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
package main
// Functions for handling nodes (also called vertices in graph theory).
// Note that we only consider an undirected graph.
import (
"errors"
"fmt"
)
// Node defines a structure to hold a node including the external
// name used to identify the node and what other nodes a node
// is connected to. The node ID is the position (slide index)
// in the NodeDb.nodes slice.
type Node struct {
// Internal Id of node. This is generated internally and has no
// relation to the original external Id found in the data file.
id int
// The external name or Id (may be an integer id)
externalName string
// Slice of Ids of who this Node links to
links []int
// Number of groups this node is a member of
numGroups int
}
// NodeDb defines a structure to be the Node database.
type NodeDb struct {
// Slice of nodes. The node.id is the slice index location.
nodes []Node
// Hashtable to allow external name lookups
hash map[string]int
}
// Dump the contents of the NodeDb to stdout. (Used for debugging.)
func dumpDb(nodeDb NodeDb) {
fmt.Printf("** NodeDb **\n")
for i := 0; i < len(nodeDb.nodes); i++ {
var n Node = nodeDb.nodes[i]
fmt.Printf("Node#%d: %p id=%d, name='%s', nlinks=%d, links=", i, &nodeDb.nodes[i], n.id, n.externalName, len(n.links))
if len(nodeDb.nodes[i].links) == 0 {
fmt.Print("none")
}
for j := 0; j < len(nodeDb.nodes[i].links); j++ {
if j > 0 {
fmt.Print(",")
}
fmt.Print(nodeDb.nodes[i].links[j])
}
fmt.Println()
}
}
// Dump the contents of the Node to stdout. (Used for debugging.)
func printNode(n *Node) {
fmt.Printf("Node: addr=%p id=%d nLinks=%d\n", n, n.id, len(n.links))
}
func initNodeDb() NodeDb {
var nodeDb NodeDb
// init empty slice of Node
nodeDb.nodes = []Node{}
nodeDb.hash = make(map[string]int)
return nodeDb
}
// Get a Node pointer, or return nil if one does not exist
// for this id.
/* OBE
func getNode(nodeDb NodeDb, id int) (*Node, error) {
if id >= len(nodeDb.nodes) {
return nil, errors.New("No such node")
}
return &(nodeDb.nodes[id]), nil
}
*/
// Create a new Node with the given name. Return the ID.
func createNode(nodeDb *NodeDb, name string) int {
debugMessage(fmt.Sprintf("In createNode with name=%s", name))
var ret Node
lookupID, e := getNodeIDForExternalName(*nodeDb, name)
if e == nil && lookupID >= 0 {
debugMessage(fmt.Sprintf(" Returning existing id=%d\n", lookupID))
return lookupID
}
if lookupID < 0 {
debugMessage(fmt.Sprintf(" Not found name=%s, creating now", name))
lookupID = len(nodeDb.nodes)
}
debugMessage(fmt.Sprintf(" Allocating new Node with id=%d for name=%s", lookupID, name))
ret.id = lookupID
ret.externalName = name
// start with empty slice of int Ids
ret.links = []int{}
ret.externalName = name
ret.numGroups = 0
// append to slize of nodes
nodeDb.nodes = append(nodeDb.nodes, ret)
// Now add to hash table using external name as key
nodeDb.hash[ret.externalName] = ret.id
debugMessage(fmt.Sprintf(" Num nodes is now %d", len(nodeDb.nodes)))
return lookupID
}
// Add a link to a node.
func addLinkToNode(nodeDb *NodeDb, sourceNodeID int, linkedNodeID int) error {
debugMessage(fmt.Sprintf("Adding link to node width id=%d", sourceNodeID))
maxValidID := len(nodeDb.nodes) - 1
// Verify both are valid IDs
if sourceNodeID < 0 || sourceNodeID > maxValidID {
debugMessage("Invalid sourceNodeID")
return fmt.Errorf("invalid sourceNodeID %d", sourceNodeID)
}
if linkedNodeID < 0 || linkedNodeID > maxValidID {
debugMessage("Invalid linkedNodeID")
return fmt.Errorf("invalid linkedNodeID %d", linkedNodeID)
}
// Make sure we don't already have this link
debugMessage(fmt.Sprintf(" Existing links for node: %d", len(nodeDb.nodes[sourceNodeID].links)))
for i := 0; i < len(nodeDb.nodes[sourceNodeID].links); i++ {
if nodeDb.nodes[sourceNodeID].links[i] == linkedNodeID {
// Found link already
debugMessage(" (Link already exists)")
return nil
}
}
// not found -> add to end of list
nodeDb.nodes[sourceNodeID].links = append(nodeDb.nodes[sourceNodeID].links, linkedNodeID)
debugMessage(fmt.Sprintf(" New links for node id=%d: %d", sourceNodeID, len(nodeDb.nodes[sourceNodeID].links)))
return nil
}
// Add a link between two existing nodes. The nodes may or may not already exist.
func addLink(nodeDb *NodeDb, id1 int, id2 int) error {
// Verify both are valid IDs
maxValidID := len(nodeDb.nodes) - 1
if id1 < 0 || id1 > maxValidID {
return fmt.Errorf("invalid sourceNodeId %d", id1)
}
if id2 < 0 || id2 > maxValidID {
return fmt.Errorf("invalid linkedNodeId %d", id2)
}
//name1 := nodeDb.nodes[id1].externalName
//name2 := nodeDb.nodes[id2].externalName
err1 := addLinkToNode(nodeDb, id1, id2)
err2 := addLinkToNode(nodeDb, id2, id1)
if err1 == nil && err2 == nil {
return nil
} else if err1 != nil {
return err1
} else {
return err2
}
}
// Retrieve a Node id from the NodeDb by its external name.
func getNodeIDForExternalName(nodeDb NodeDb, name string) (int, error) {
// Look it up in our map
value, ok := nodeDb.hash[name]
if ok {
// Found. Return the internal Id.
return value, nil
}
// Not found
return -1, errors.New("no such external Id")
}
// Determine if the two nodes are currently linked
func nodeLinksTo(nodeDb NodeDb, id1 int, id2 int) bool {
n1 := nodeDb.nodes[id1]
for i := 0; i < len(n1.links); i++ {
if n1.links[i] == id2 {
return true
}
}
return false
}
// Create an abbreviated version of the external name.
// This is useful for fixed length columns in a plain/text report.
func nodeNameAbbr(node Node, length int) string {
if len(node.externalName) <= length {
return node.externalName
}
return node.externalName[0:length]
}