-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathBasicGraph.as
More file actions
279 lines (251 loc) · 7.86 KB
/
Copy pathBasicGraph.as
File metadata and controls
279 lines (251 loc) · 7.86 KB
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
package mathgraph
{
/**
* A data structure that represents a simple mathematics graph. It contains a set of nodes connected by edges.
* Edges are either undirected or directed, and may have weights associated with them.
* Pairs of nodes can be permitted to either allow only 1 edge between them, or multiple edges.
* Nodes may have loops if allowed (edges connecting a node to itself).
* @author Sean Snyder
*/
public class BasicGraph
{
//each index of this array represents a node, and contains an array of the index values of adjacent nodes
protected var adjacencyList:Array; //ex: [ [1,3], [0,1], undefined, [0,1], []]
//each index of this array represents a node, and contains an array of the weights for its edges
private var weightedList:Array; //ex: [ [50, 90], [120, 70], undefined, [45, 125], []]
protected var numNodes:int = 0;
protected var numEdges:int = 0;
private var _allowLoops:Boolean;
private var _allowDirectedEdges:Boolean;
private var _allowQuiverEdges:Boolean;
public function BasicGraph(allowLoops:Boolean=false, allowDirectedEdges:Boolean=false, allowQuiverEdges:Boolean=false)
{
adjacencyList = new Array();
weightedList = new Array();
_allowLoops = allowLoops;
_allowDirectedEdges = allowDirectedEdges;
_allowQuiverEdges = allowQuiverEdges;
}
//returns an array containing the indexes of all loaded nodes
public function getAllNodes():Array {
var nodes:Array = new Array();
for (var i:int = 0; i < adjacencyList.length; i++)
{
if (adjacencyList[i] != null) nodes.push(i);
}
return nodes;
}
public function totalNodes():int
{
return numNodes;
}
public function totalEdges():int
{
return numEdges;
}
//returns how many edges a node has connected from it to other nodes, or -1 if the node doesnt exist
public function numberEdges(node:int):int {
var adjList:Array = adjacencyList[node];
if (adjList == null) return -1;
else return adjList.length;
}
//checks if a node exists in the graph
public function hasNode(node:int):Boolean {
return adjacencyList[node] != null;
}
//adds a new node to the graph
public function addNode(node:int):Boolean {
if (node < 0) return false;
if (node >= adjacencyList.length || adjacencyList[node] == null) {
adjacencyList[node] = new Array();
weightedList[node] = new Array();
numNodes++;
return true;
}
return false;
}
//removes a node from a graph
public function removeNode(node:int):Boolean {
var adjList:Array = adjacencyList[node];
if (adjList != null) {
//remove this node from all other adjacency lists
for (var adjNode:int = 0; adjNode < adjacencyList.length; adjNode++)
{
if (!hasNode(adjNode)) {
continue;
}
while (adjacent(adjNode, node)) {
removeEdge(adjNode, node);
}
}
//remove all edges from this node's adkacency list
while (adjList.length > 0) {
adjList.pop();
numEdges--;
}
if (node == adjacencyList.length - 1) {
adjacencyList.pop();
weightedList.pop();
}
else {
adjacencyList[node] = null;
weightedList[node] = null;
}
numNodes--;
return true;
}
return false;
}
//add an edge between 2 nodes
public function addEdge(nodeA:int, nodeB:int, weight:int=1):Boolean {
if (nodeA == nodeB && !allowsLoops) {
return false;
}
else if (weight < 0) { //invalid weight: must be positive
return false;
}
else {
var adjListA:Array = adjacencyList[nodeA];
var adjListB:Array = adjacencyList[nodeB];
var weightListA:Array = weightedList[nodeA];
var weightListB:Array = weightedList[nodeB];
if (adjListA == null || adjListB == null || (!allowsQuivers && adjListA.indexOf(nodeB) != -1)) {
return false;
}
adjListA.push(nodeB);
weightListA.push(weight);
if (!hasDirectionalEdges && nodeA != nodeB) {
if (!allowsQuivers && adjListB.indexOf(nodeA) != -1) {
return false;
}
adjListB.push(nodeA);
weightListB.push(weight);
}
numEdges++;
return true;
}
}
//remove an edge between 2 nodes
public function removeEdge(nodeA:int, nodeB:int):Boolean {
if (nodeA == nodeB && !allowsLoops) {
return false;
}
var adjListA:Array = adjacencyList[nodeA];
var weightListA:Array = weightedList[nodeA];
if (adjListA == null) {
return false;
}
var nodeBIndex:int = adjListA.indexOf(nodeB);
if (nodeBIndex == -1) {
return false;
}
adjListA.splice(nodeBIndex, 1);
weightListA.splice(nodeBIndex, 1);
if (!hasDirectionalEdges && nodeA != nodeB) {
var adjListB:Array = adjacencyList[nodeB];
var weightListB:Array = weightedList[nodeB];
if (adjListB == null) {
return false;
}
var nodeAIndex:int = adjListB.indexOf(nodeA);
if (nodeAIndex == -1) {
return false;
}
adjListB.splice(nodeAIndex, 1);
weightListB.splice(nodeAIndex, 1);
}
numEdges--;
return true;
}
//returns an array containing all adjacent nodes
/**
* Returns a list of nodes that are adjacent to the specified node.
* @param node any nodes adjacent to this node will be provided
* @param exclusive Applies only if quivers are enabled; If true, adjacent nodes appear only once in the list.
* @return an array containing all adjacent nodes
*/
public function neighbors(node:int, exclusive:Boolean=true):Array {
if (exclusive && allowsQuivers) {
var exclNodes:Array = new Array();
var exclAdjList:Array = new Array();
for each (var node:int in adjacencyList[node])
{
if (exclNodes[node] == null) {
exclAdjList.push(node);
exclNodes[node] = 0;
}
}
return exclAdjList;
}
else {
var adjList:Array = adjacencyList[node];
return adjList == null ? null : adjList.concat();
}
}
//tests whether there is an edge between 2 nodes
public function adjacent(nodeA:int, nodeB:int):Boolean {
var adjListA:Array = adjacencyList[nodeA];
return hasAdjacentNode(nodeB, adjListA);
}
/**
* Gets the weight of an edge between 2 nodes.
* If the Graph has directional edges, only the edges from the starting node to the ending node will be considered.
* @param nodeA starting node
* @param nodeB ending node
* @param shortest Only applies if quivers are allowed. If true, always choose the shortest edge, otherwise choose any valid edge at random.
* @return the weight of an edge, or -1 if that edge does not exist.
*/
public function getWeight(nodeA:int, nodeB:int, shortest:Boolean=true):int
{
var weights:Array = new Array();
var currentIndex:int = 0;
var adjListA:Array = adjacencyList[nodeA];
var weightListA:Array = weightedList[nodeA];
while (currentIndex != -1 && currentIndex < adjListA.length) {
currentIndex = adjListA.indexOf(nodeB, currentIndex);
if (currentIndex != -1) {
weights.push(weightListA[currentIndex]);
currentIndex++;
}
}
if (weights.length == 0) return -1;
else if (shortest) {
var shortestWeight:int = int.MAX_VALUE;
for each (var weight:int in weights)
{
if (weight < shortestWeight) shortestWeight = weight;
}
return shortestWeight;
}
else {
var randomIndex:int = Math.floor(Math.random() * weights.length)
return weights[randomIndex];
}
}
public function get allowsLoops():Boolean
{
return _allowLoops
}
public function get hasDirectionalEdges():Boolean
{
return _allowDirectedEdges;
}
public function get allowsQuivers():Boolean
{
return _allowQuiverEdges;
}
//tests whether a node is found in a list of adjacent nodes
private function hasAdjacentNode(node:int, adjList:Array):Boolean {
if (adjList == null || adjList.length == 0) {
return false;
}
for each (var adjNode:int in adjList)
{
if (adjNode == node) {
return true;
}
}
return false;
}
}
}