-
Notifications
You must be signed in to change notification settings - Fork 4
/
Graph.js
357 lines (338 loc) · 9.88 KB
/
Graph.js
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
/*
* Mathematical Graph library. For details on how to use please read:
*
* README.markdown
*
* or go to
*
* http://github.com/yoni/Grap
*
* @author Yoni Ben-Meshulam
*/
/**
* A vertex (basic element) is simply drawn as a node or a dot. The vertex set of G
* is usually denoted by V(G), or V when there is no danger of confusion.
*/
function Vertex (obj) {
// A Vertex is nothing more than an object
// This allows you to extend vertices in any way desirable
// Note: we are making a shallow copy of obj, which means that any changes to its member variables
// will be reflected in this vertex.
for (var k in obj) {
this[k] = obj[k];
}
}
/**
* An edge (a set of two elements) is drawn as a line connecting two vertices, called
* endvertices, or endpoints. An edge with endvertices x and y is denoted by xy
* (without any symbol in between). The edge set of G is usually denoted by E(G), or
* E when there is no danger of confusion.
*/
function Edge (v1, v2, directed){
if ((!v1) || (!v2)) {
throw "Illegal arguments for constructing an Edge. Expected two vertices. Example: <code>var e = new Edge(v1, v2);</code>";
}
this.v1 = v1;
this.v2 = v2;
this.directed = directed;
}
/**
* A graph G consists of two types of elements: vertices and edges. Every edge
* has two endpoints in the set of vertices, and is said to connect or join the two
* endpoints. An edge can thus be defined as a set of two vertices (or an ordered pair,
* in the case of a directed graph - see Section Direction).
*
* Note: The uniqueness of Vertices and Edges is not guaranteed. See multiplicity.
*/
function Graph (){
this.V = []; // the set of vertices in this graph
this.E = []; // the set of edges in this graph
/**
* In a Directed Graph, the order of Vertices in an Edge matters. In an Undirected
* Graph, the order
* A directed arc, or directed edge, is an ordered pair of endvertices that can be represented
* graphically as an arrow drawn between the endvertices. In such an ordered pair the first vertex
* is called the initial vertex or tail; the second one is called the terminal vertex or head (because
* it appears at the arrow head). An undirected edge disregards any sense of direction and treats
* both endvertices interchangeably. A loop in a digraph, however, keeps a sense of direction and
* treats both head and tail identically. A set of arcs are multiple, or parallel, if they share the
* same head and the same tail. A pair of arcs are anti-parallel if one's head/tail is the other's
* tail/head. A digraph, or directed graph, or oriented graph, is analogous to an undirected graph
* except that it contains only arcs. A mixed graph may contain both directed and undirected edges;
* it generalizes both directed and undirected graphs. When stated without any qualification, a graph
* is almost always assumed to be undirected.
* @param toggle
*/
this.directed = function(toggle) {
if(toggle) {
_directed = !_directed;
}
return _directed;
};
var _directed = arguments.directed;// a Graph can be initialized as a directed graph
/**
* Adds the given vertex to the graph
* @param {Vertex} v
*/
this.addVertex = function(v){
if (typeof(v) != 'object') throw "A vertex must be an object.";
this.V.push(v);
return this;
};
/**
*
* @param {Array of Vertices} V
*/
this.addVertices = function(V){
for (var i in V) {
this.addVertex(V[i]);
}
return this;
};
/**
* @param {Edge} e
*/
this.addEdge = function(e){
if (!e.v1 || !e.v2) throw "Illegal argument. An edge must be incident on two vertices.";
this.E.push(e);
return this;
};
/**
* @param {Array of Edges} E
*/
this.addEdges = function(E){
for (var i in E) {
this.addEdge(E[i]);
}
return this;
};
}
/**
* A walk is an alternating sequence of vertices and edges, beginning and ending with a vertex, where each vertex
* is incident to both the edge that precedes it and the edge that follows it in the sequence, and where the vertices
* that precede and follow an edge are the end vertices of that edge.
* @param {Graph} G
*/
/*
function Walk (G){
this.E = [];
if (G.directed) {
// adds the edge to the walk
this.addEdge = function(e){
if (e.v1 !== E[E.length - 1].v2) {
throw "Illegal edge " + e + ". v1 of the added edge must be equal to v2 of the last edge in the walk.";
}
else {
E.push(e);
}
};
//A walk is closed if its first and last vertices are the same, and open if they are different.
this.closed = function(){
};
this.open = function(){
};
}
else {
// adds the edge to the walk
this.addEdge = function(e){
if (e.v1 !== E[E.length - 1].v2) {
throw "Illegal edge " + e + ". v1 of the added edge must be equal to v2 of the last edge in the walk.";
}
else {
E.push(e);
}
};
//A walk is closed if its first and last vertices are the same, and open if they are different.
this.closed = function(){
throw "Can't do this yet.";
};
this.open = function(){
throw "Can't do this yet.";
};
}
},
*/
/**
* <p>The functional design of the graph library means that the following functions do not affect the state of their inputs,
* they simple produce an output. That is the general contract of functional programming, which differs from
* the Object-oriented paradigm used above, in describing the stateful Objects we were dealing with.</p>
*
*/
var graph = {
/**
* The order of a graph is the number of vertices, i.e. |V(G)|.
* @param {Graph} G
*/
order:function(G){
return G.V.length;
},
"|V(G)|":function(G){
return order(G);
},
/**
* The size of a graph is the number of its edges, i.e. |E(G)|.
* @param {Graph} G
*/
size:function(G){
return G.E.length;
},
"|E(G)|":function(G){
return size(G);
},
/**
* The multiplicity of a graph is the maximum multiplicity of its edges.
* @param {Graph} G
*/
multiplicity:function(G){
var max = 0;
for (var i in G.E) {
var e = G.E[i];
var eMultiplicity = edge.multiplicity(e, G);
if (max < eMultiplicity) max = eMultiplicity;
}
return max;
},
/**
* A graph has a loop if any of its edges is a loop
* @param {Graph} G
*/
hasLoops:function(G){
for (var i in G.E) {
if ( edge.isLoop(G.E[i]) ) return true;
}
return false;
},
/**
* A graph is a simple graph if it has no multiple edges or loops
* @param {Graph} G
*/
isSimple:function(G){
return !(graph.hasLoops(G) || graph.isMulti(G));
},
/**
* A graph is a multigraph if it has multiple edges, but no loops
* @param {Graph} G
*/
isMulti:function(G){
return graph.multiplicity(G) != 1;
},
/**
* A graph is a pseudograph if it contains both multiple edges and loops
* @param {Graph} G
*/
isPseudo:function(G){
return graph.hasLoops(G) && (graph.multiplicity(G) !== 1);
},
/**
* An anti-edge is an edge that "is not there". More formally, for two vertices u and v, {u,v} is
* an anti-edge in a graph G whenever {u,v} is not an edge in G. This means that there is either
* no edge between the two vertices or (for directed graphs) at most one of (u,v) and (v,u)
* from v is an arc in G.
* @param {Edge} e
*/
isAntiEdge:function(G,e){
return !graph.containsEdge(G,e);
},
/**
* @param {Graph} G
* @param {Edge} e
*/
containsEdge:function(G, e){
for (var i in G.E) {
if ( edge.equal(e, G.E[i]) ) return true;
}
return false;
},
/**
* The complement of a graph G is a graph with the same vertex set as G but with an edge set
* such that xy is an edge in complement(G) if and only if xy is not an edge in G.
* @param {Graph} G
*/
complement:function(G){
var C = new Graph();
C.addVertices(G.V);
for (var i in G.V) {
for (var j in G.V) {
var e = new Edge(G.V[i], G.V[j]);
if ( graph.isAntiEdge(G,e) ) {
C.addEdge(e);
}
}
}
return C;
}
};
var edge = {
/**
* A loop is an edge whose end vertices are the same vertex.
* @param {Edge} e
*/
isLoop:function(e){
return (e.v1 === e.v2);
},
/**
* A link has two distinct end vertices.
* @param {Edge} e
*/
isLink:function(e){
return !edge.isLoop(e);
},
/**
* Two edges are equal
* @param {Edge} e1
* @param {Edge} e2
*/
equal:function(e1, e2){
// In an undirected edge, the order of vertices does not matter. {v1,v2} is the same as {v2,v1}
// v1-v2
if( e1.directed || e2.directed ) {
return ( e1.v1 === e2.v1 && e1.v2 === e2.v2 );
}
// In a directed edge, the order of vertices matters.
// v1 can be thought of as the head and v2 the tail,
// v1->v2
else {
return ( e1.v1 === e2.v1 && e1.v2 === e2.v2 )
||( e1.v1 === e2.v2 && e1.v2 === e2.v1 );
}
},
/**
* The multiplicity of an edge is the number of multiple edges sharing the same endvertices
* @param {Edge} e
* @param {Graph} G
*/
multiplicity:function(e,G){
var m = 0;
for (var key in G.E) {
var e2 = G.E[key];
if(edge.equal(e2, e)) {
m++;
}
}
return m;
},
/**
* An edge is multiple if there is another edge with the same endvertices
* @param {Edge} e
* @param {Graph} G
*/
isMultiple:function(e,G){
return edge.multiplicity(e,G) > 1;
},
/**
* An edge is exactly one edge with the same endvertices
*
* @param {Edge} e
* @param {Graph} G
*/
isSimple:function(e,G){
return edge.multiplicity(e,G) === 1;
}
}
// Stateful entities
exports.Graph = Graph;
exports.Edge = Edge;
exports.Vertex = Vertex;
// Functional libraries
exports.graph = graph;
exports.edge = edge;