-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathL1-Game2.html
530 lines (505 loc) · 26 KB
/
L1-Game2.html
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
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
<!-- https://gojs.net/latest/intro/dataBinding.html#TwoWayDataBinding -->
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>Game 2 - Lecture 1 - ORF363 Fall 2020</title>
<meta name="description" content="Interactive Max-Flow and Stabe-Set"/>
<meta name="viewport" content="width=device-width, initial-scale=1">
<!-- Copyright 1998-2020 by Northwoods Software Corporation. -->
<script src="https://unpkg.com/gojs/release/go-debug.js "></script>
<!-- <script src="https://cdnjs.cloudflare.com/ajax/libs/seedrandom/3.0.5/seedrandom.min.js"> -->
<!-- </script> -->
<!-- <script src="../assets/js/goSamples.js"></script> -->
<!-- this is only for the GoJS Samples framework -->
<meta name="author" content="Shen Shen @shensquared"/>
<!-- <link rel="start" href="{{ HOME_PATH }}" /> -->
<!-- {% if page.keywords %} -->
<meta name="keywords" content="Max-Flow and Stable-Set JavaScript Interactive">
<script id="code">
function init() {
var iffirstgame = false
var $ = go.GraphObject.make; // for conciseness in defining templates
myDiagram =
$(go.Diagram, "myDiagramDiv", // must be the ID or reference to div
{
initialAutoScale: go.Diagram.UniformToFill,
padding: 10,
// autoScale: go.Diagram.UniformToFill,
// contentAlignment: go.Spot.Center,
// layout: $(go.ForceDirectedLayout, { defaultSpringLength: 10 }),
// maxSelectionCount: 2
});
// define the Node template
myDiagram.nodeTemplate =
$(go.Node, "Auto",
new go.Binding("location", "loc", go.Point.parse),
{
// locationSpot: go.Spot.Center, // Node.location is the center of the Shape
// locationObjectName: "SHAPE",
selectionAdorned: false,
selectionChanged: nodeSelectionChanged
},
$(go.Panel, "Auto",
$(go.Shape, "Ellipse",
{
name: "SHAPE",
fill: "lightgray", // default value, but also data-bound
stroke: "transparent", // modified by highlighting
strokeWidth: 2,
desiredSize: new go.Size(50, 50),
portId: ""
}, // so links will go to the shape, not the whole node
new go.Binding("fill", "isSelected", function (s, obj) {
return s ? "red" : obj.part.data.color;
}).ofObject()),
// $(go.TextBlock,
// new go.Binding("text", "distance", function(d) { if (d === Infinity) return "INF"; else return d | 0; }))
),
$(go.TextBlock,
new go.Binding("text")));
// if (iffirstgame) {
// define the Link template
linkTemplate1 =
$(go.Link,
{
selectable: false,
// selectionChanged: linkSelectionChanged,
// curve: go.Link.Bezier,
layerName: "Background",
mouseEnter: function (e, obj) {
e.diagram.commandHandler.editTextBlock(obj.part.findObject("FLOW"));
// console.log('23')
// console.log(e.diagram.toolManager.textEditingTool.);
// e.diagram.toolManager.textEditingTool.acceptText();
// console.log('24');
// console.log(e.diagram.toolManager.textEditingTool.isActive);
},
mouseLeave: function (e, obj) {
// console.log(e.diagram.toolManager.textEditingTool.isActive)
// e.diagram.toolManager.textEditingTool.acceptText(e.diagram.toolManager.textEditingTool.Enter);
// console.log('ha')
// e.diagram.toolManager.textEditingTool.currentTextEditor.textEditingTool.acceptText(go.TextEditingTool.Enter)
// e.diagram.toolManager.textEditingTool.acceptText()
}
},
$(go.Shape, // this shape only shows when it isHighlighted
{isPanelMain: true, stroke: null, strokeWidth: 10},
// new go.Binding("stroke", "isHighlighted", function(h) { return h ? "red" : null; }).ofObject(),
new go.Binding("stroke", "isSelected", function (h) {
return h ? "red" : null;
}).ofObject(),
),
$(go.Shape,
// mark each Shape to get the link geometry with isPanelMain: true
{isPanelMain: true, stroke: "black", strokeWidth: 3},
// new go.Binding("stroke", "color")
),
$(go.Shape, {toArrow: "Standard", strokeWidth: 2}),
$(go.TextBlock, {
name: "FLOW",
text: "??", font: "bold 12pt serif", stroke: "red",
editable: true, isMultiline: false, segmentOffset: new go.Point(-1, -15)
}),
// https://gojs.net/latest/extensions/LinkLabelDragging.html
$(go.TextBlock, {
font: "bold 14pt serif",
segmentOffset: new go.Point(-1, 20)
}, new go.Binding("text", "text")),
)
// } else {
linkTemplate2 =
$(go.Link, {
selectable: false,
// selectionChanged: linkSelectionChanged,
curve: go.Link.Bezier,
layerName: "Background",
},new go.Binding("curviness", "curviness"),
$(go.Shape, // this shape only shows when it isHighlighted
{isPanelMain: true, stroke: null, strokeWidth: 10},
new go.Binding("stroke", "isHighlighted", function(h) { return h ? "red" : null; }).ofObject(),
// new go.Binding("stroke", "isSelected", function (h) {
// return h ? "red" : null;
// }
// ).ofObject(),
),
$(go.Shape,
// mark each Shape to get the link geometry with isPanelMain: true
{isPanelMain: true, stroke: "black", strokeWidth: 3},
// new go.Binding("stroke", "color")
))
// }
// Override the clickSelectingTool's standardMouseSelect
// If less than 2 nodes are selected, always add to the selection
myDiagram.toolManager.clickSelectingTool.standardMouseSelect = function () {
var diagram = this.diagram;
if (diagram === null || !diagram.allowSelect) return;
var e = diagram.lastInput;
var curobj = diagram.findPartAt(e.documentPoint, false);
if (curobj !== null) {
if (!curobj.isSelected) {
var part = curobj;
if (part !== null) part.isSelected = true;
} else {
curobj.isSelected = false
}
} else if (e.left && !(e.control || e.meta) && !e.shift) {
// left click on background with no modifier: clear selection
// diagram.clearSelection();
}
}
var button1 = document.getElementById('ShowButton');
button1.addEventListener('click', function () {
myDiagram.clearSelection()
// // if (iffirstgame) {
// // document.getElementById("gametitle").innerHTML = "Two finals in one day? No thanks.";
// // document.getElementById("rule1").innerHTML = "Goal: Find the largest collection of nodes such that no two nodes share an edge.";
// // document.getElementById("rule2").innerHTML = "";
// // document.getElementById("rule3").innerHTML = "";
// // } else {
// // document.getElementById("gametitle").innerHTML = "Let's ship some oil together!";
// // document.getElementById("rule1").innerHTML = "Cannot exceed capacity on the edges.";
// // document.getElementById("rule2").innerHTML = "For each node, except for S ant T, flow in = flow out (i.e., no storage).";
// // document.getElementById("rule3").innerHTML = "Goal: ship as much oil as you can from S to T.";
// // }
// // iffirstgame = !iffirstgame;
// // generateGraph(iffirstgame);
});
generateGraph(iffirstgame)
// select two nodes that connect from the first one to the second one
// var num = myDiagram.model.nodeDataArray.length;
// var node1 = null;
// var node2 = null;
// for (var i = 0; i < num; i++) {
// node1 = myDiagram.findNodeForKey(i);
// var distances = findDistances(node1);
// for (var j = 0; j < num; j++) {
// node2 = myDiagram.findNodeForKey(j);
// var dist = distances.get(node2);
// if (dist > 1 && dist < Infinity) {
// node1.isSelected = true;
// node2.isSelected = true;
// break;
// }
// }
// if (myDiagram.selection.count > 0) break;
// }
}
function generateGraph(iffirstgame) {
if (iffirstgame) {
var names = ["S", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "T"];
// var names = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11"];
// "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];
// var a = [01,03,05,04,12,13,17,37,35,45,410,57,56,28,78,76,611,69,811,911,10|9,11|7]
var max_flows = [10, 2, 4, 5, 4, 2, 2, 8, 5, 3, 2, 7, 2, 3, 2, 2, 6, 10, 9, 7, 5, 6, 1];
var a = [0, 0, 0, 0, 1, 1, 1, 3, 3, 4, 4, 5, 5, 2, 7, 7, 6, 6, 8, 9, 10, 11, 10];
var ccc = a;
var b = [1, 3, 5, 4, 2, 3, 7, 7, 5, 5, 10, 7, 6, 8, 8, 6, 11, 9, 11, 11, 9, 7, 6]
var locs = ["-617 10", "-428 -227", "-125 -301", "-328 -94", "-390 241", "-230 111", "117 93", "-43 -123", "195 -238", "356 208", "40 295", "403 -25"]
myDiagram.linkTemplate = linkTemplate1
} else {
var names = ["00", "01", "02", "03", "04", "05", "06", "07", "08", "09", "10", "11", "12"];
var a = [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 8,]
var b = [2, 7, 9, 12, 8, 5, 3, 4, 6, 10, 7, 11, 6, 7, 11, 8, 6, 9, 12, 10, 10, 12, 9, 10, 12, 11, 12, 6]
var ccc = [30, 70, -30, -220, -50, 20, 20, 100, -10, 3, 30, 100, -40, 4, 20, 5, 5, 5, -20, 1, 7, 100, -8, -20, -9, -10, 101, 8]
var locs = ["-617 10", "-509 -170", "-334 -279", "56 -251", "348 -201", "-262 -38", "2 -62", "234 -35", "-393 50", "-169 107", "129 86", "403 51", "-136 267"]
var max_flows = a
myDiagram.linkTemplate = linkTemplate2
}
var nodeDataArray = [];
for (var i = 1; i < names.length - 1; i++) {
nodeDataArray.push({key: i, text: names[i], loc: locs[i], color: 'lightgray'});
}
if(iffirstgame){
nodeDataArray.push({key: 0, text: names[0], loc: locs[0], color: 'lightblue'});
nodeDataArray.push({
key: names.length - 1,
text: names[names.length - 1],
loc: locs[names.length - 1],
color: 'lightblue'
});
}
else{
nodeDataArray.push({
key: names.length - 1,
text: names[names.length - 1],
loc: locs[names.length - 1],
color: 'lightgray'
});
}
var linkDataArray = [];
// var myrng = new Math.seedrandom('ORF');
var num = a.length;
for (var i = 0; i < num; i++) {
linkDataArray.push({
from: a[i], to: b[i], color: go.Brush.randomColor(0, 127),
text: max_flows[i], curviness: ccc[i]
});
}
myDiagram.model = new go.GraphLinksModel(nodeDataArray, linkDataArray);
}
// There are three bits of functionality here:
// 1: findDistances(Node) computes the distance of each Node from the given Node.
// This function is used by showDistances to update the model data.
// 2: findShortestPath(Node, Node) finds a shortest path from one Node to another.
// This uses findDistances. This is used by highlightShortestPath.
// 3: collectAllPaths(Node, Node) produces a collection of all paths from one Node to another.
// This is used by listAllPaths. The result is remembered in a global variable
// which is used by highlightSelectedPath. This does not depend on findDistances.
// Returns a Map of Nodes with distance values from the given source Node.
// Assumes all links are unidirectional.
function findDistances(source) {
var diagram = source.diagram;
// keep track of distances from the source node
var distances = new go.Map(/*go.Node, "number"*/);
// all nodes start with distance Infinity
var nit = diagram.nodes;
while (nit.next()) {
var n = nit.value;
distances.set(n, Infinity);
}
// the source node starts with distance 0
distances.set(source, 0);
// keep track of nodes for which we have set a non-Infinity distance,
// but which we have not yet finished examining
var seen = new go.Set(/*go.Node*/);
seen.add(source);
// keep track of nodes we have finished examining;
// this avoids unnecessary traversals and helps keep the SEEN collection small
var finished = new go.Set(/*go.Node*/);
while (seen.count > 0) {
// look at the unfinished node with the shortest distance so far
var least = leastNode(seen, distances);
var leastdist = distances.get(least);
// by the end of this loop we will have finished examining this LEAST node
seen.delete(least);
finished.add(least);
// look at all Links connected with this node
var it = least.findLinksOutOf();
while (it.next()) {
var link = it.value;
var neighbor = link.getOtherNode(least);
// skip nodes that we have finished
if (finished.has(neighbor)) continue;
var neighbordist = distances.get(neighbor);
// assume "distance" along a link is unitary, but could be any non-negative number.
var dist = leastdist + 1; //Math.sqrt(least.location.distanceSquaredPoint(neighbor.location));
if (dist < neighbordist) {
// if haven't seen that node before, add it to the SEEN collection
if (neighbordist === Infinity) {
seen.add(neighbor);
}
// record the new best distance so far to that node
distances.set(neighbor, dist);
}
}
}
return distances;
}
// This helper function finds a Node in the given collection that has the smallest distance.
function leastNode(coll, distances) {
var bestdist = Infinity;
var bestnode = null;
var it = coll.iterator;
while (it.next()) {
var n = it.value;
var dist = distances.get(n);
if (dist < bestdist) {
bestdist = dist;
bestnode = n;
}
}
return bestnode;
}
// Find a path that is shortest from the BEGIN node to the END node.
// (There might be more than one, and there might be none.)
function findShortestPath(begin, end) {
// compute and remember the distance of each node from the BEGIN node
distances = findDistances(begin);
// now find a path from END to BEGIN, always choosing the adjacent Node with the lowest distance
var path = new go.List();
path.add(end);
while (end !== null) {
var next = leastNode(end.findNodesInto(), distances);
if (next !== null) {
if (distances.get(next) < distances.get(end)) {
path.add(next); // making progress towards the beginning
} else {
next = null; // nothing better found -- stop looking
}
}
end = next;
}
// reverse the list to start at the node closest to BEGIN that is on the path to END
// NOTE: if there's no path from BEGIN to END, the first node won't be BEGIN!
path.reverse();
return path;
}
// Recursively walk the graph starting from the BEGIN node;
// when reaching the END node remember the list of nodes along the current path.
// Finally return the collection of paths, which may be empty.
// This assumes all links are unidirectional.
function collectAllPaths(begin, end) {
var stack = new go.List(/*go.Node*/);
var coll = new go.List(/*go.List*/);
function find(source, end) {
source.findNodesOutOf().each(function (n) {
if (n === source) return; // ignore reflexive links
if (n === end) { // success
var path = stack.copy();
path.add(end); // finish the path at the end node
coll.add(path); // remember the whole path
} else if (!stack.has(n)) { // inefficient way to check having visited
stack.add(n); // remember that we've been here for this path (but not forever)
find(n, end);
stack.removeAt(stack.count - 1);
} // else might be a cycle
});
}
stack.add(begin); // start the path at the begin node
find(begin, end);
return coll;
}
// Return a string representation of a path for humans to read.
function pathToString(path) {
var s = path.length + ": ";
for (var i = 0; i < path.length; i++) {
if (i > 0) s += " -- ";
s += path.get(i).data.text;
}
return s;
}
// When a node is selected show distances from the first selected node.
// When a second node is selected, highlight the shortest path between two selected nodes.
// If a node is deselected, clear all highlights.
function nodeSelectionChanged(node) {
var diagram = node.diagram;
if (diagram === null) return;
// diagram.clearHighlighteds();
if (node.isSelected) {
var it = node.findLinksConnected();
// console.log(it)
while (it.next()) {
var item = it.value;
// console.log(it.value)
// console.log(item.isSelected)
item.isHighlighted=true
}
// when there is a selection made, always clear out the list of all paths
// var sel = document.getElementById("myPaths");
// sel.innerHTML = "";
// show the distance for each node from the selected node
// var begin = diagram.selection.first();
// showDistances(begin);
// if (diagram.selection.count === 2) {
// var end = node; // just became selected
// highlight the shortest path
// highlightShortestPath(begin, end);
// list all paths
// listAllPaths(begin, end);
// console.log(node.location)
}
else{
var it = node.findLinksConnected();
// console.log(it)
while (it.next()) {
var item = it.value;
// console.log(it.value)
// console.log(item.isSelected)
item.isHighlighted=false
// item.stroke='red'
}
}
}
function linkSelectionChanged(link) {
var diagram = link.diagram;
if (diagram === null) return;
diagram.clearHighlighteds();
if (link.isSelected) {
// when there is a selection made, always clear out the list of all paths
// var sel = document.getElementById("myPaths");
// sel.innerHTML = "";
}
}
// Have each node show how far it is from the BEGIN node.
function showDistances(begin) {
// compute and remember the distance of each node from the BEGIN node
distances = findDistances(begin);
// show the distance on each node
var it = distances.iterator;
while (it.next()) {
var n = it.key;
var dist = it.value;
myDiagram.model.setDataProperty(n.data, "distance", dist);
}
}
// Highlight links along one of the shortest paths between the BEGIN and the END nodes.
// Assume links are unidirectional.
function highlightShortestPath(begin, end) {
highlightPath(findShortestPath(begin, end));
}
// List all paths from BEGIN to END
function listAllPaths(begin, end) {
// compute and remember all paths from BEGIN to END: Lists of Nodes
paths = collectAllPaths(begin, end);
// update the Selection element with a bunch of Option elements, one per path
// var sel = document.getElementById("myPaths");
// sel.innerHTML = ""; // clear out any old Option elements
paths.each(function (p) {
var opt = document.createElement("option");
opt.text = pathToString(p);
sel.add(opt, null);
});
sel.onchange = highlightSelectedPath;
}
// A collection of all of the paths between a pair of nodes, a List of Lists of Nodes
var paths = null;
// This is only used for listing all paths for the selection onchange event.
// When the selected item changes in the Selection element,
// highlight the corresponding path of nodes.
function highlightSelectedPath() {
// var sel = document.getElementById("myPaths");
// var idx = sel.selectedIndex;
// var opt = sel.options[idx];
// var val = opt.value;
// highlightPath(paths.get(sel.selectedIndex));
}
// Highlight a particular path, a List of Nodes.
function highlightPath(path) {
myDiagram.clearHighlighteds();
for (var i = 0; i < path.count - 1; i++) {
var f = path.get(i);
var t = path.get(i + 1);
f.findLinksTo(t).each(function (l) {
l.isHighlighted = true;
});
}
}
</script>
</head>
<body onload="init()">
<div id="sample">
<a href="http://aaa.princeton.edu/orf363">Go Back to ORF363</a>
<p></p>
<p style="color:steelblue; text-align:center; font-family:verdana; font-size:180%" , id='gametitle'>Two finals in one day? No thanks.</p>
<button id="ShowButton" type="button">Clear all selections</button>
<div id="myDiagramDiv" style="border: solid 1px black; background: white; width: 100%; height: 700px"></div>
<ul>
<p style="color:black; text-align:left; font-family:verdana; font-size:200%">Rules of the game:</p>
<p id = 'rule1'>
Goal: Find a largest collection of pairwise non-adjacent nodes.
</p>
<!-- <p id = 'rule2'>
For each node, except for S ant T, flow in = flow out (i.e., no storage).
</p>
<p id = 'rule3'>Goal: ship as much oil as you can from S to T.
</p>
--> </ul>
<p>
<!-- Here is a list of all paths between the first and second selected nodes. -->
<!-- Clicking on a third node will de-select the first two. -->
</p>
<!-- <select id="myPaths" style="min-width:300px" size="10"></select>-->
</div>
</body>
</html>