forked from snapapps/edgy
-
Notifications
You must be signed in to change notification settings - Fork 0
/
jsnetworkx.js
455 lines (455 loc) · 201 KB
/
jsnetworkx.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
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
(function(global, factory) { function extractNS(){ var g = {}; return factory.call(g, global),g.jsnx;} if(typeof define === 'function' && define.amd){ /*AMD*/ define(extractNS); } else if (typeof module !== 'undefined' && module.exports){ /*node*/ module.exports = extractNS(); } else { factory.call(global, global); } }(this, function(window) {var COMPILED=!0,goog=goog||{};goog.global=this;goog.exportPath_=function(a,b,c){a=a.split(".");c=c||goog.global;a[0]in c||!c.execScript||c.execScript("var "+a[0]);for(var d;a.length&&(d=a.shift());)a.length||void 0===b?c=c[d]?c[d]:c[d]={}:c[d]=b};goog.define=function(a,b){var c=b;COMPILED||goog.global.CLOSURE_DEFINES&&Object.prototype.hasOwnProperty.call(goog.global.CLOSURE_DEFINES,a)&&(c=goog.global.CLOSURE_DEFINES[a]);goog.exportPath_(a,c)};goog.DEBUG=!1;goog.LOCALE="en";goog.TRUSTED_SITE=!0;
goog.provide=function(a){if(!COMPILED){if(goog.isProvided_(a))throw Error('Namespace "'+a+'" already declared.');delete goog.implicitNamespaces_[a];for(var b=a;(b=b.substring(0,b.lastIndexOf(".")))&&!goog.getObjectByName(b);)goog.implicitNamespaces_[b]=!0}goog.exportPath_(a)};goog.setTestOnly=function(a){if(COMPILED&&!goog.DEBUG)throw a=a||"",Error("Importing test-only code into non-debug environment"+a?": "+a:".");};goog.forwardDeclare=function(a){};
COMPILED||(goog.isProvided_=function(a){return!goog.implicitNamespaces_[a]&&goog.isDefAndNotNull(goog.getObjectByName(a))},goog.implicitNamespaces_={});goog.getObjectByName=function(a,b){for(var c=a.split("."),d=b||goog.global,e;e=c.shift();)if(goog.isDefAndNotNull(d[e]))d=d[e];else return null;return d};goog.globalize=function(a,b){var c=b||goog.global,d;for(d in a)c[d]=a[d]};
goog.addDependency=function(a,b,c){if(goog.DEPENDENCIES_ENABLED){var d;a=a.replace(/\\/g,"/");for(var e=goog.dependencies_,f=0;d=b[f];f++)e.nameToPath[d]=a,a in e.pathToNames||(e.pathToNames[a]={}),e.pathToNames[a][d]=!0;for(d=0;b=c[d];d++)a in e.requires||(e.requires[a]={}),e.requires[a][b]=!0}};goog.ENABLE_DEBUG_LOADER=!0;
goog.require=function(a){if(!COMPILED&&!goog.isProvided_(a)){if(goog.ENABLE_DEBUG_LOADER){var b=goog.getPathFromDeps_(a);if(b){goog.included_[b]=!0;goog.writeScripts_();return}}a="goog.require could not find: "+a;goog.global.console&&goog.global.console.error(a);throw Error(a);}};goog.basePath="";goog.nullFunction=function(){};goog.identityFunction=function(a,b){return a};goog.abstractMethod=function(){throw Error("unimplemented abstract method");};
goog.addSingletonGetter=function(a){a.getInstance=function(){if(a.instance_)return a.instance_;goog.DEBUG&&(goog.instantiatedSingletons_[goog.instantiatedSingletons_.length]=a);return a.instance_=new a}};goog.instantiatedSingletons_=[];goog.DEPENDENCIES_ENABLED=!COMPILED&&goog.ENABLE_DEBUG_LOADER;
goog.DEPENDENCIES_ENABLED&&(goog.included_={},goog.dependencies_={pathToNames:{},nameToPath:{},requires:{},visited:{},written:{}},goog.inHtmlDocument_=function(){var a=goog.global.document;return"undefined"!=typeof a&&"write"in a},goog.findBasePath_=function(){if(goog.global.CLOSURE_BASE_PATH)goog.basePath=goog.global.CLOSURE_BASE_PATH;else if(goog.inHtmlDocument_())for(var a=goog.global.document.getElementsByTagName("script"),b=a.length-1;0<=b;--b){var c=a[b].src,d=c.lastIndexOf("?"),d=-1==d?c.length:
d;if("base.js"==c.substr(d-7,7)){goog.basePath=c.substr(0,d-7);break}}},goog.importScript_=function(a){var b=goog.global.CLOSURE_IMPORT_SCRIPT||goog.writeScriptTag_;!goog.dependencies_.written[a]&&b(a)&&(goog.dependencies_.written[a]=!0)},goog.writeScriptTag_=function(a){if(goog.inHtmlDocument_()){var b=goog.global.document;if("complete"==b.readyState){if(/\bdeps.js$/.test(a))return!1;throw Error('Cannot write "'+a+'" after document load');}b.write('<script type="text/javascript" src="'+a+'">\x3c/script>');
return!0}return!1},goog.writeScripts_=function(){function a(e){if(!(e in d.written)){if(!(e in d.visited)&&(d.visited[e]=!0,e in d.requires))for(var g in d.requires[e])if(!goog.isProvided_(g))if(g in d.nameToPath)a(d.nameToPath[g]);else throw Error("Undefined nameToPath for "+g);e in c||(c[e]=!0,b.push(e))}}var b=[],c={},d=goog.dependencies_,e;for(e in goog.included_)d.written[e]||a(e);for(e=0;e<b.length;e++)if(b[e])goog.importScript_(goog.basePath+b[e]);else throw Error("Undefined script input");
},goog.getPathFromDeps_=function(a){return a in goog.dependencies_.nameToPath?goog.dependencies_.nameToPath[a]:null},goog.findBasePath_(),goog.global.CLOSURE_NO_DEPS||goog.importScript_(goog.basePath+"deps.js"));
goog.typeOf=function(a){var b=typeof a;if("object"==b)if(a){if(a instanceof Array)return"array";if(a instanceof Object)return b;var c=Object.prototype.toString.call(a);if("[object Window]"==c)return"object";if("[object Array]"==c||"number"==typeof a.length&&"undefined"!=typeof a.splice&&"undefined"!=typeof a.propertyIsEnumerable&&!a.propertyIsEnumerable("splice"))return"array";if("[object Function]"==c||"undefined"!=typeof a.call&&"undefined"!=typeof a.propertyIsEnumerable&&!a.propertyIsEnumerable("call"))return"function"}else return"null";
else if("function"==b&&"undefined"==typeof a.call)return"object";return b};goog.isDef=function(a){return void 0!==a};goog.isNull=function(a){return null===a};goog.isDefAndNotNull=function(a){return null!=a};goog.isArray=function(a){return"array"==goog.typeOf(a)};goog.isArrayLike=function(a){var b=goog.typeOf(a);return"array"==b||"object"==b&&"number"==typeof a.length};goog.isDateLike=function(a){return goog.isObject(a)&&"function"==typeof a.getFullYear};goog.isString=function(a){return"string"==typeof a};
goog.isBoolean=function(a){return"boolean"==typeof a};goog.isNumber=function(a){return"number"==typeof a};goog.isFunction=function(a){return"function"==goog.typeOf(a)};goog.isObject=function(a){var b=typeof a;return"object"==b&&null!=a||"function"==b};goog.getUid=function(a){return a[goog.UID_PROPERTY_]||(a[goog.UID_PROPERTY_]=++goog.uidCounter_)};goog.hasUid=function(a){return!!a[goog.UID_PROPERTY_]};goog.removeUid=function(a){"removeAttribute"in a&&a.removeAttribute(goog.UID_PROPERTY_);try{delete a[goog.UID_PROPERTY_]}catch(b){}};
goog.UID_PROPERTY_="closure_uid_"+(1E9*Math.random()>>>0);goog.uidCounter_=0;goog.getHashCode=goog.getUid;goog.removeHashCode=goog.removeUid;goog.cloneObject=function(a){var b=goog.typeOf(a);if("object"==b||"array"==b){if(a.clone)return a.clone();var b="array"==b?[]:{},c;for(c in a)b[c]=goog.cloneObject(a[c]);return b}return a};goog.bindNative_=function(a,b,c){return a.call.apply(a.bind,arguments)};
goog.bindJs_=function(a,b,c){if(!a)throw Error();if(2<arguments.length){var d=Array.prototype.slice.call(arguments,2);return function(){var c=Array.prototype.slice.call(arguments);Array.prototype.unshift.apply(c,d);return a.apply(b,c)}}return function(){return a.apply(b,arguments)}};goog.bind=function(a,b,c){Function.prototype.bind&&-1!=Function.prototype.bind.toString().indexOf("native code")?goog.bind=goog.bindNative_:goog.bind=goog.bindJs_;return goog.bind.apply(null,arguments)};
goog.partial=function(a,b){var c=Array.prototype.slice.call(arguments,1);return function(){var b=c.slice();b.push.apply(b,arguments);return a.apply(this,b)}};goog.mixin=function(a,b){for(var c in b)a[c]=b[c]};goog.now=goog.TRUSTED_SITE&&Date.now||function(){return+new Date};
goog.globalEval=function(a){if(goog.global.execScript)goog.global.execScript(a,"JavaScript");else if(goog.global.eval)if(null==goog.evalWorksForGlobals_&&(goog.global.eval("var _et_ = 1;"),"undefined"!=typeof goog.global._et_?(delete goog.global._et_,goog.evalWorksForGlobals_=!0):goog.evalWorksForGlobals_=!1),goog.evalWorksForGlobals_)goog.global.eval(a);else{var b=goog.global.document,c=b.createElement("script");c.type="text/javascript";c.defer=!1;c.appendChild(b.createTextNode(a));b.body.appendChild(c);
b.body.removeChild(c)}else throw Error("goog.globalEval not available");};goog.evalWorksForGlobals_=null;goog.getCssName=function(a,b){var c=function(a){return goog.cssNameMapping_[a]||a},d=function(a){a=a.split("-");for(var b=[],d=0;d<a.length;d++)b.push(c(a[d]));return b.join("-")},d=goog.cssNameMapping_?"BY_WHOLE"==goog.cssNameMappingStyle_?c:d:function(a){return a};return b?a+"-"+d(b):d(a)};goog.setCssNameMapping=function(a,b){goog.cssNameMapping_=a;goog.cssNameMappingStyle_=b};
!COMPILED&&goog.global.CLOSURE_CSS_NAME_MAPPING&&(goog.cssNameMapping_=goog.global.CLOSURE_CSS_NAME_MAPPING);goog.getMsg=function(a,b){var c=b||{},d;for(d in c){var e=(""+c[d]).replace(/\$/g,"$$$$");a=a.replace(RegExp("\\{\\$"+d+"\\}","gi"),e)}return a};goog.getMsgWithFallback=function(a,b){return a};goog.exportSymbol=function(a,b,c){goog.exportPath_(a,b,c)};goog.exportProperty=function(a,b,c){a[b]=c};
goog.inherits=function(a,b){function c(){}c.prototype=b.prototype;a.superClass_=b.prototype;a.prototype=new c;a.prototype.constructor=a;a.base=function(a,c,f){var g=Array.prototype.slice.call(arguments,2);return b.prototype[c].apply(a,g)}};
goog.base=function(a,b,c){var d=arguments.callee.caller;if(goog.DEBUG&&!d)throw Error("arguments.caller not defined. goog.base() expects not to be running in strict mode. See http://www.ecma-international.org/ecma-262/5.1/#sec-C");if(d.superClass_)return d.superClass_.constructor.apply(a,Array.prototype.slice.call(arguments,1));for(var e=Array.prototype.slice.call(arguments,2),f=!1,g=a.constructor;g;g=g.superClass_&&g.superClass_.constructor)if(g.prototype[b]===d)f=!0;else if(f)return g.prototype[b].apply(a,
e);if(a[b]===d)return a.constructor.prototype[b].apply(a,e);throw Error("goog.base called from a method of one name to a method of a different name");};goog.scope=function(a){a.call(goog.global)};goog.functions={};goog.functions.constant=function(a){return function(){return a}};goog.functions.FALSE=goog.functions.constant(!1);goog.functions.TRUE=goog.functions.constant(!0);goog.functions.NULL=goog.functions.constant(null);goog.functions.identity=function(a,b){return a};goog.functions.error=function(a){return function(){throw Error(a);}};goog.functions.fail=function(a){return function(){throw a;}};
goog.functions.lock=function(a,b){b=b||0;return function(){return a.apply(this,Array.prototype.slice.call(arguments,0,b))}};goog.functions.nth=function(a){return function(){return arguments[a]}};goog.functions.withReturnValue=function(a,b){return goog.functions.sequence(a,goog.functions.constant(b))};goog.functions.compose=function(a,b){var c=arguments,d=c.length;return function(){var a;d&&(a=c[d-1].apply(this,arguments));for(var b=d-2;0<=b;b--)a=c[b].call(this,a);return a}};
goog.functions.sequence=function(a){var b=arguments,c=b.length;return function(){for(var a,e=0;e<c;e++)a=b[e].apply(this,arguments);return a}};goog.functions.and=function(a){var b=arguments,c=b.length;return function(){for(var a=0;a<c;a++)if(!b[a].apply(this,arguments))return!1;return!0}};goog.functions.or=function(a){var b=arguments,c=b.length;return function(){for(var a=0;a<c;a++)if(b[a].apply(this,arguments))return!0;return!1}};
goog.functions.not=function(a){return function(){return!a.apply(this,arguments)}};goog.functions.create=function(a,b){var c=function(){};c.prototype=a.prototype;c=new c;a.apply(c,Array.prototype.slice.call(arguments,1));return c};goog.functions.CACHE_RETURN_VALUE=!0;goog.functions.cacheReturnValue=function(a){var b=!1,c;return function(){if(!goog.functions.CACHE_RETURN_VALUE)return a();b||(c=a(),b=!0);return c}};goog.dom={};goog.dom.NodeType={ELEMENT:1,ATTRIBUTE:2,TEXT:3,CDATA_SECTION:4,ENTITY_REFERENCE:5,ENTITY:6,PROCESSING_INSTRUCTION:7,COMMENT:8,DOCUMENT:9,DOCUMENT_TYPE:10,DOCUMENT_FRAGMENT:11,NOTATION:12};goog.debug={};goog.debug.Error=function(a){if(Error.captureStackTrace)Error.captureStackTrace(this,goog.debug.Error);else{var b=Error().stack;b&&(this.stack=b)}a&&(this.message=String(a))};goog.inherits(goog.debug.Error,Error);goog.debug.Error.prototype.name="CustomError";goog.string={};goog.string.Unicode={NBSP:"\u00a0"};goog.string.startsWith=function(a,b){return 0==a.lastIndexOf(b,0)};goog.string.endsWith=function(a,b){var c=a.length-b.length;return 0<=c&&a.indexOf(b,c)==c};goog.string.caseInsensitiveStartsWith=function(a,b){return 0==goog.string.caseInsensitiveCompare(b,a.substr(0,b.length))};goog.string.caseInsensitiveEndsWith=function(a,b){return 0==goog.string.caseInsensitiveCompare(b,a.substr(a.length-b.length,b.length))};
goog.string.caseInsensitiveEquals=function(a,b){return a.toLowerCase()==b.toLowerCase()};goog.string.subs=function(a,b){for(var c=a.split("%s"),d="",e=Array.prototype.slice.call(arguments,1);e.length&&1<c.length;)d+=c.shift()+e.shift();return d+c.join("%s")};goog.string.collapseWhitespace=function(a){return a.replace(/[\s\xa0]+/g," ").replace(/^\s+|\s+$/g,"")};goog.string.isEmpty=function(a){return/^[\s\xa0]*$/.test(a)};goog.string.isEmptySafe=function(a){return goog.string.isEmpty(goog.string.makeSafe(a))};
goog.string.isBreakingWhitespace=function(a){return!/[^\t\n\r ]/.test(a)};goog.string.isAlpha=function(a){return!/[^a-zA-Z]/.test(a)};goog.string.isNumeric=function(a){return!/[^0-9]/.test(a)};goog.string.isAlphaNumeric=function(a){return!/[^a-zA-Z0-9]/.test(a)};goog.string.isSpace=function(a){return" "==a};goog.string.isUnicodeChar=function(a){return 1==a.length&&" "<=a&&"~">=a||"\u0080"<=a&&"\ufffd">=a};goog.string.stripNewlines=function(a){return a.replace(/(\r\n|\r|\n)+/g," ")};
goog.string.canonicalizeNewlines=function(a){return a.replace(/(\r\n|\r|\n)/g,"\n")};goog.string.normalizeWhitespace=function(a){return a.replace(/\xa0|\s/g," ")};goog.string.normalizeSpaces=function(a){return a.replace(/\xa0|[ \t]+/g," ")};goog.string.collapseBreakingSpaces=function(a){return a.replace(/[\t\r\n ]+/g," ").replace(/^[\t\r\n ]+|[\t\r\n ]+$/g,"")};goog.string.trim=function(a){return a.replace(/^[\s\xa0]+|[\s\xa0]+$/g,"")};
goog.string.trimLeft=function(a){return a.replace(/^[\s\xa0]+/,"")};goog.string.trimRight=function(a){return a.replace(/[\s\xa0]+$/,"")};goog.string.caseInsensitiveCompare=function(a,b){var c=String(a).toLowerCase(),d=String(b).toLowerCase();return c<d?-1:c==d?0:1};goog.string.numerateCompareRegExp_=/(\.\d+)|(\d+)|(\D+)/g;
goog.string.numerateCompare=function(a,b){if(a==b)return 0;if(!a)return-1;if(!b)return 1;for(var c=a.toLowerCase().match(goog.string.numerateCompareRegExp_),d=b.toLowerCase().match(goog.string.numerateCompareRegExp_),e=Math.min(c.length,d.length),f=0;f<e;f++){var g=c[f],h=d[f];if(g!=h)return c=parseInt(g,10),!isNaN(c)&&(d=parseInt(h,10),!isNaN(d)&&c-d)?c-d:g<h?-1:1}return c.length!=d.length?c.length-d.length:a<b?-1:1};goog.string.urlEncode=function(a){return encodeURIComponent(String(a))};
goog.string.urlDecode=function(a){return decodeURIComponent(a.replace(/\+/g," "))};goog.string.newLineToBr=function(a,b){return a.replace(/(\r\n|\r|\n)/g,b?"<br />":"<br>")};
goog.string.htmlEscape=function(a,b){if(b)return a.replace(goog.string.amperRe_,"&").replace(goog.string.ltRe_,"<").replace(goog.string.gtRe_,">").replace(goog.string.quotRe_,""").replace(goog.string.singleQuoteRe_,"'");if(!goog.string.allRe_.test(a))return a;-1!=a.indexOf("&")&&(a=a.replace(goog.string.amperRe_,"&"));-1!=a.indexOf("<")&&(a=a.replace(goog.string.ltRe_,"<"));-1!=a.indexOf(">")&&(a=a.replace(goog.string.gtRe_,">"));-1!=a.indexOf('"')&&(a=a.replace(goog.string.quotRe_,
"""));-1!=a.indexOf("'")&&(a=a.replace(goog.string.singleQuoteRe_,"'"));return a};goog.string.amperRe_=/&/g;goog.string.ltRe_=/</g;goog.string.gtRe_=/>/g;goog.string.quotRe_=/"/g;goog.string.singleQuoteRe_=/'/g;goog.string.allRe_=/[&<>"']/;goog.string.unescapeEntities=function(a){return goog.string.contains(a,"&")?"document"in goog.global?goog.string.unescapeEntitiesUsingDom_(a):goog.string.unescapePureXmlEntities_(a):a};
goog.string.unescapeEntitiesWithDocument=function(a,b){return goog.string.contains(a,"&")?goog.string.unescapeEntitiesUsingDom_(a,b):a};
goog.string.unescapeEntitiesUsingDom_=function(a,b){var c={"&":"&","<":"<",">":">",""":'"'},d;d=b?b.createElement("div"):document.createElement("div");return a.replace(goog.string.HTML_ENTITY_PATTERN_,function(a,b){var g=c[a];if(g)return g;if("#"==b.charAt(0)){var h=Number("0"+b.substr(1));isNaN(h)||(g=String.fromCharCode(h))}g||(d.innerHTML=a+" ",g=d.firstChild.nodeValue.slice(0,-1));return c[a]=g})};
goog.string.unescapePureXmlEntities_=function(a){return a.replace(/&([^;]+);/g,function(a,c){switch(c){case "amp":return"&";case "lt":return"<";case "gt":return">";case "quot":return'"';default:if("#"==c.charAt(0)){var d=Number("0"+c.substr(1));if(!isNaN(d))return String.fromCharCode(d)}return a}})};goog.string.HTML_ENTITY_PATTERN_=/&([^;\s<&]+);?/g;goog.string.whitespaceEscape=function(a,b){return goog.string.newLineToBr(a.replace(/ /g,"  "),b)};
goog.string.stripQuotes=function(a,b){for(var c=b.length,d=0;d<c;d++){var e=1==c?b:b.charAt(d);if(a.charAt(0)==e&&a.charAt(a.length-1)==e)return a.substring(1,a.length-1)}return a};goog.string.truncate=function(a,b,c){c&&(a=goog.string.unescapeEntities(a));a.length>b&&(a=a.substring(0,b-3)+"...");c&&(a=goog.string.htmlEscape(a));return a};
goog.string.truncateMiddle=function(a,b,c,d){c&&(a=goog.string.unescapeEntities(a));if(d&&a.length>b){d>b&&(d=b);var e=a.length-d;a=a.substring(0,b-d)+"..."+a.substring(e)}else a.length>b&&(d=Math.floor(b/2),e=a.length-d,a=a.substring(0,d+b%2)+"..."+a.substring(e));c&&(a=goog.string.htmlEscape(a));return a};goog.string.specialEscapeChars_={"\x00":"\\0","\b":"\\b","\f":"\\f","\n":"\\n","\r":"\\r","\t":"\\t","\x0B":"\\x0B",'"':'\\"',"\\":"\\\\"};goog.string.jsEscapeCache_={"'":"\\'"};
goog.string.quote=function(a){a=String(a);if(a.quote)return a.quote();for(var b=['"'],c=0;c<a.length;c++){var d=a.charAt(c),e=d.charCodeAt(0);b[c+1]=goog.string.specialEscapeChars_[d]||(31<e&&127>e?d:goog.string.escapeChar(d))}b.push('"');return b.join("")};goog.string.escapeString=function(a){for(var b=[],c=0;c<a.length;c++)b[c]=goog.string.escapeChar(a.charAt(c));return b.join("")};
goog.string.escapeChar=function(a){if(a in goog.string.jsEscapeCache_)return goog.string.jsEscapeCache_[a];if(a in goog.string.specialEscapeChars_)return goog.string.jsEscapeCache_[a]=goog.string.specialEscapeChars_[a];var b=a,c=a.charCodeAt(0);if(31<c&&127>c)b=a;else{if(256>c){if(b="\\x",16>c||256<c)b+="0"}else b="\\u",4096>c&&(b+="0");b+=c.toString(16).toUpperCase()}return goog.string.jsEscapeCache_[a]=b};goog.string.toMap=function(a){for(var b={},c=0;c<a.length;c++)b[a.charAt(c)]=!0;return b};
goog.string.contains=function(a,b){return-1!=a.indexOf(b)};goog.string.countOf=function(a,b){return a&&b?a.split(b).length-1:0};goog.string.removeAt=function(a,b,c){var d=a;0<=b&&b<a.length&&0<c&&(d=a.substr(0,b)+a.substr(b+c,a.length-b-c));return d};goog.string.remove=function(a,b){var c=RegExp(goog.string.regExpEscape(b),"");return a.replace(c,"")};goog.string.removeAll=function(a,b){var c=RegExp(goog.string.regExpEscape(b),"g");return a.replace(c,"")};
goog.string.regExpEscape=function(a){return String(a).replace(/([-()\[\]{}+?*.$\^|,:#<!\\])/g,"\\$1").replace(/\x08/g,"\\x08")};goog.string.repeat=function(a,b){return Array(b+1).join(a)};goog.string.padNumber=function(a,b,c){a=goog.isDef(c)?a.toFixed(c):String(a);c=a.indexOf(".");-1==c&&(c=a.length);return goog.string.repeat("0",Math.max(0,b-c))+a};goog.string.makeSafe=function(a){return null==a?"":String(a)};goog.string.buildString=function(a){return Array.prototype.join.call(arguments,"")};
goog.string.getRandomString=function(){return Math.floor(2147483648*Math.random()).toString(36)+Math.abs(Math.floor(2147483648*Math.random())^goog.now()).toString(36)};
goog.string.compareVersions=function(a,b){for(var c=0,d=goog.string.trim(String(a)).split("."),e=goog.string.trim(String(b)).split("."),f=Math.max(d.length,e.length),g=0;0==c&&g<f;g++){var h=d[g]||"",k=e[g]||"",l=RegExp("(\\d*)(\\D*)","g"),m=RegExp("(\\d*)(\\D*)","g");do{var n=l.exec(h)||["","",""],p=m.exec(k)||["","",""];if(0==n[0].length&&0==p[0].length)break;var c=0==n[1].length?0:parseInt(n[1],10),t=0==p[1].length?0:parseInt(p[1],10),c=goog.string.compareElements_(c,t)||goog.string.compareElements_(0==
n[2].length,0==p[2].length)||goog.string.compareElements_(n[2],p[2])}while(0==c)}return c};goog.string.compareElements_=function(a,b){return a<b?-1:a>b?1:0};goog.string.HASHCODE_MAX_=4294967296;goog.string.hashCode=function(a){for(var b=0,c=0;c<a.length;++c)b=31*b+a.charCodeAt(c),b%=goog.string.HASHCODE_MAX_;return b};goog.string.uniqueStringCounter_=2147483648*Math.random()|0;goog.string.createUniqueString=function(){return"goog_"+goog.string.uniqueStringCounter_++};
goog.string.toNumber=function(a){var b=Number(a);return 0==b&&goog.string.isEmpty(a)?NaN:b};goog.string.isLowerCamelCase=function(a){return/^[a-z]+([A-Z][a-z]*)*$/.test(a)};goog.string.isUpperCamelCase=function(a){return/^([A-Z][a-z]*)+$/.test(a)};goog.string.toCamelCase=function(a){return String(a).replace(/\-([a-z])/g,function(a,c){return c.toUpperCase()})};goog.string.toSelectorCase=function(a){return String(a).replace(/([A-Z])/g,"-$1").toLowerCase()};
goog.string.toTitleCase=function(a,b){var c=goog.isString(b)?goog.string.regExpEscape(b):"\\s";return a.replace(RegExp("(^"+(c?"|["+c+"]+":"")+")([a-z])","g"),function(a,b,c){return b+c.toUpperCase()})};goog.string.parseInt=function(a){isFinite(a)&&(a=String(a));return goog.isString(a)?/^\s*-?0x/i.test(a)?parseInt(a,16):parseInt(a,10):NaN};goog.string.splitLimit=function(a,b,c){a=a.split(b);for(var d=[];0<c&&a.length;)d.push(a.shift()),c--;a.length&&d.push(a.join(b));return d};goog.asserts={};goog.asserts.ENABLE_ASSERTS=goog.DEBUG;goog.asserts.AssertionError=function(a,b){b.unshift(a);goog.debug.Error.call(this,goog.string.subs.apply(null,b));b.shift();this.messagePattern=a};goog.inherits(goog.asserts.AssertionError,goog.debug.Error);goog.asserts.AssertionError.prototype.name="AssertionError";goog.asserts.doAssertFailure_=function(a,b,c,d){var e="Assertion failed";if(c)var e=e+(": "+c),f=d;else a&&(e+=": "+a,f=b);throw new goog.asserts.AssertionError(""+e,f||[]);};
goog.asserts.assert=function(a,b,c){goog.asserts.ENABLE_ASSERTS&&!a&&goog.asserts.doAssertFailure_("",null,b,Array.prototype.slice.call(arguments,2));return a};goog.asserts.fail=function(a,b){if(goog.asserts.ENABLE_ASSERTS)throw new goog.asserts.AssertionError("Failure"+(a?": "+a:""),Array.prototype.slice.call(arguments,1));};
goog.asserts.assertNumber=function(a,b,c){goog.asserts.ENABLE_ASSERTS&&!goog.isNumber(a)&&goog.asserts.doAssertFailure_("Expected number but got %s: %s.",[goog.typeOf(a),a],b,Array.prototype.slice.call(arguments,2));return a};goog.asserts.assertString=function(a,b,c){goog.asserts.ENABLE_ASSERTS&&!goog.isString(a)&&goog.asserts.doAssertFailure_("Expected string but got %s: %s.",[goog.typeOf(a),a],b,Array.prototype.slice.call(arguments,2));return a};
goog.asserts.assertFunction=function(a,b,c){goog.asserts.ENABLE_ASSERTS&&!goog.isFunction(a)&&goog.asserts.doAssertFailure_("Expected function but got %s: %s.",[goog.typeOf(a),a],b,Array.prototype.slice.call(arguments,2));return a};goog.asserts.assertObject=function(a,b,c){goog.asserts.ENABLE_ASSERTS&&!goog.isObject(a)&&goog.asserts.doAssertFailure_("Expected object but got %s: %s.",[goog.typeOf(a),a],b,Array.prototype.slice.call(arguments,2));return a};
goog.asserts.assertArray=function(a,b,c){goog.asserts.ENABLE_ASSERTS&&!goog.isArray(a)&&goog.asserts.doAssertFailure_("Expected array but got %s: %s.",[goog.typeOf(a),a],b,Array.prototype.slice.call(arguments,2));return a};goog.asserts.assertBoolean=function(a,b,c){goog.asserts.ENABLE_ASSERTS&&!goog.isBoolean(a)&&goog.asserts.doAssertFailure_("Expected boolean but got %s: %s.",[goog.typeOf(a),a],b,Array.prototype.slice.call(arguments,2));return a};
goog.asserts.assertElement=function(a,b,c){!goog.asserts.ENABLE_ASSERTS||goog.isObject(a)&&a.nodeType==goog.dom.NodeType.ELEMENT||goog.asserts.doAssertFailure_("Expected Element but got %s: %s.",[goog.typeOf(a),a],b,Array.prototype.slice.call(arguments,2));return a};goog.asserts.assertInstanceof=function(a,b,c,d){!goog.asserts.ENABLE_ASSERTS||a instanceof b||goog.asserts.doAssertFailure_("instanceof check failed.",null,c,Array.prototype.slice.call(arguments,3));return a};
goog.asserts.assertObjectPrototypeIsIntact=function(){for(var a in Object.prototype)goog.asserts.fail(a+" should not be enumerable in Object.prototype.")};goog.array={};goog.NATIVE_ARRAY_PROTOTYPES=goog.TRUSTED_SITE;goog.array.ASSUME_NATIVE_FUNCTIONS=!1;goog.array.peek=function(a){return a[a.length-1]};goog.array.ARRAY_PROTOTYPE_=Array.prototype;
goog.array.indexOf=goog.NATIVE_ARRAY_PROTOTYPES&&(goog.array.ASSUME_NATIVE_FUNCTIONS||goog.array.ARRAY_PROTOTYPE_.indexOf)?function(a,b,c){goog.asserts.assert(null!=a.length);return goog.array.ARRAY_PROTOTYPE_.indexOf.call(a,b,c)}:function(a,b,c){c=null==c?0:0>c?Math.max(0,a.length+c):c;if(goog.isString(a))return goog.isString(b)&&1==b.length?a.indexOf(b,c):-1;for(;c<a.length;c++)if(c in a&&a[c]===b)return c;return-1};
goog.array.lastIndexOf=goog.NATIVE_ARRAY_PROTOTYPES&&(goog.array.ASSUME_NATIVE_FUNCTIONS||goog.array.ARRAY_PROTOTYPE_.lastIndexOf)?function(a,b,c){goog.asserts.assert(null!=a.length);return goog.array.ARRAY_PROTOTYPE_.lastIndexOf.call(a,b,null==c?a.length-1:c)}:function(a,b,c){c=null==c?a.length-1:c;0>c&&(c=Math.max(0,a.length+c));if(goog.isString(a))return goog.isString(b)&&1==b.length?a.lastIndexOf(b,c):-1;for(;0<=c;c--)if(c in a&&a[c]===b)return c;return-1};
goog.array.forEach=goog.NATIVE_ARRAY_PROTOTYPES&&(goog.array.ASSUME_NATIVE_FUNCTIONS||goog.array.ARRAY_PROTOTYPE_.forEach)?function(a,b,c){goog.asserts.assert(null!=a.length);goog.array.ARRAY_PROTOTYPE_.forEach.call(a,b,c)}:function(a,b,c){for(var d=a.length,e=goog.isString(a)?a.split(""):a,f=0;f<d;f++)f in e&&b.call(c,e[f],f,a)};goog.array.forEachRight=function(a,b,c){for(var d=a.length,e=goog.isString(a)?a.split(""):a,d=d-1;0<=d;--d)d in e&&b.call(c,e[d],d,a)};
goog.array.filter=goog.NATIVE_ARRAY_PROTOTYPES&&(goog.array.ASSUME_NATIVE_FUNCTIONS||goog.array.ARRAY_PROTOTYPE_.filter)?function(a,b,c){goog.asserts.assert(null!=a.length);return goog.array.ARRAY_PROTOTYPE_.filter.call(a,b,c)}:function(a,b,c){for(var d=a.length,e=[],f=0,g=goog.isString(a)?a.split(""):a,h=0;h<d;h++)if(h in g){var k=g[h];b.call(c,k,h,a)&&(e[f++]=k)}return e};
goog.array.map=goog.NATIVE_ARRAY_PROTOTYPES&&(goog.array.ASSUME_NATIVE_FUNCTIONS||goog.array.ARRAY_PROTOTYPE_.map)?function(a,b,c){goog.asserts.assert(null!=a.length);return goog.array.ARRAY_PROTOTYPE_.map.call(a,b,c)}:function(a,b,c){for(var d=a.length,e=Array(d),f=goog.isString(a)?a.split(""):a,g=0;g<d;g++)g in f&&(e[g]=b.call(c,f[g],g,a));return e};
goog.array.reduce=goog.NATIVE_ARRAY_PROTOTYPES&&(goog.array.ASSUME_NATIVE_FUNCTIONS||goog.array.ARRAY_PROTOTYPE_.reduce)?function(a,b,c,d){goog.asserts.assert(null!=a.length);d&&(b=goog.bind(b,d));return goog.array.ARRAY_PROTOTYPE_.reduce.call(a,b,c)}:function(a,b,c,d){var e=c;goog.array.forEach(a,function(c,g){e=b.call(d,e,c,g,a)});return e};
goog.array.reduceRight=goog.NATIVE_ARRAY_PROTOTYPES&&(goog.array.ASSUME_NATIVE_FUNCTIONS||goog.array.ARRAY_PROTOTYPE_.reduceRight)?function(a,b,c,d){goog.asserts.assert(null!=a.length);d&&(b=goog.bind(b,d));return goog.array.ARRAY_PROTOTYPE_.reduceRight.call(a,b,c)}:function(a,b,c,d){var e=c;goog.array.forEachRight(a,function(c,g){e=b.call(d,e,c,g,a)});return e};
goog.array.some=goog.NATIVE_ARRAY_PROTOTYPES&&(goog.array.ASSUME_NATIVE_FUNCTIONS||goog.array.ARRAY_PROTOTYPE_.some)?function(a,b,c){goog.asserts.assert(null!=a.length);return goog.array.ARRAY_PROTOTYPE_.some.call(a,b,c)}:function(a,b,c){for(var d=a.length,e=goog.isString(a)?a.split(""):a,f=0;f<d;f++)if(f in e&&b.call(c,e[f],f,a))return!0;return!1};
goog.array.every=goog.NATIVE_ARRAY_PROTOTYPES&&(goog.array.ASSUME_NATIVE_FUNCTIONS||goog.array.ARRAY_PROTOTYPE_.every)?function(a,b,c){goog.asserts.assert(null!=a.length);return goog.array.ARRAY_PROTOTYPE_.every.call(a,b,c)}:function(a,b,c){for(var d=a.length,e=goog.isString(a)?a.split(""):a,f=0;f<d;f++)if(f in e&&!b.call(c,e[f],f,a))return!1;return!0};goog.array.count=function(a,b,c){var d=0;goog.array.forEach(a,function(a,f,g){b.call(c,a,f,g)&&++d},c);return d};
goog.array.find=function(a,b,c){b=goog.array.findIndex(a,b,c);return 0>b?null:goog.isString(a)?a.charAt(b):a[b]};goog.array.findIndex=function(a,b,c){for(var d=a.length,e=goog.isString(a)?a.split(""):a,f=0;f<d;f++)if(f in e&&b.call(c,e[f],f,a))return f;return-1};goog.array.findRight=function(a,b,c){b=goog.array.findIndexRight(a,b,c);return 0>b?null:goog.isString(a)?a.charAt(b):a[b]};
goog.array.findIndexRight=function(a,b,c){for(var d=a.length,e=goog.isString(a)?a.split(""):a,d=d-1;0<=d;d--)if(d in e&&b.call(c,e[d],d,a))return d;return-1};goog.array.contains=function(a,b){return 0<=goog.array.indexOf(a,b)};goog.array.isEmpty=function(a){return 0==a.length};goog.array.clear=function(a){if(!goog.isArray(a))for(var b=a.length-1;0<=b;b--)delete a[b];a.length=0};goog.array.insert=function(a,b){goog.array.contains(a,b)||a.push(b)};
goog.array.insertAt=function(a,b,c){goog.array.splice(a,c,0,b)};goog.array.insertArrayAt=function(a,b,c){goog.partial(goog.array.splice,a,c,0).apply(null,b)};goog.array.insertBefore=function(a,b,c){var d;2==arguments.length||0>(d=goog.array.indexOf(a,c))?a.push(b):goog.array.insertAt(a,b,d)};goog.array.remove=function(a,b){var c=goog.array.indexOf(a,b),d;(d=0<=c)&&goog.array.removeAt(a,c);return d};
goog.array.removeAt=function(a,b){goog.asserts.assert(null!=a.length);return 1==goog.array.ARRAY_PROTOTYPE_.splice.call(a,b,1).length};goog.array.removeIf=function(a,b,c){b=goog.array.findIndex(a,b,c);return 0<=b?(goog.array.removeAt(a,b),!0):!1};goog.array.concat=function(a){return goog.array.ARRAY_PROTOTYPE_.concat.apply(goog.array.ARRAY_PROTOTYPE_,arguments)};goog.array.toArray=function(a){var b=a.length;if(0<b){for(var c=Array(b),d=0;d<b;d++)c[d]=a[d];return c}return[]};goog.array.clone=goog.array.toArray;
goog.array.extend=function(a,b){for(var c=1;c<arguments.length;c++){var d=arguments[c],e;if(goog.isArray(d)||(e=goog.isArrayLike(d))&&Object.prototype.hasOwnProperty.call(d,"callee"))a.push.apply(a,d);else if(e)for(var f=a.length,g=d.length,h=0;h<g;h++)a[f+h]=d[h];else a.push(d)}};goog.array.splice=function(a,b,c,d){goog.asserts.assert(null!=a.length);return goog.array.ARRAY_PROTOTYPE_.splice.apply(a,goog.array.slice(arguments,1))};
goog.array.slice=function(a,b,c){goog.asserts.assert(null!=a.length);return 2>=arguments.length?goog.array.ARRAY_PROTOTYPE_.slice.call(a,b):goog.array.ARRAY_PROTOTYPE_.slice.call(a,b,c)};goog.array.removeDuplicates=function(a,b,c){b=b||a;var d=function(a){return goog.isObject(g)?"o"+goog.getUid(g):(typeof g).charAt(0)+g};c=c||d;for(var d={},e=0,f=0;f<a.length;){var g=a[f++],h=c(g);Object.prototype.hasOwnProperty.call(d,h)||(d[h]=!0,b[e++]=g)}b.length=e};
goog.array.binarySearch=function(a,b,c){return goog.array.binarySearch_(a,c||goog.array.defaultCompare,!1,b)};goog.array.binarySelect=function(a,b,c){return goog.array.binarySearch_(a,b,!0,void 0,c)};goog.array.binarySearch_=function(a,b,c,d,e){for(var f=0,g=a.length,h;f<g;){var k=f+g>>1,l;l=c?b.call(e,a[k],k,a):b(d,a[k]);0<l?f=k+1:(g=k,h=!l)}return h?f:~f};goog.array.sort=function(a,b){a.sort(b||goog.array.defaultCompare)};
goog.array.stableSort=function(a,b){for(var c=0;c<a.length;c++)a[c]={index:c,value:a[c]};var d=b||goog.array.defaultCompare;goog.array.sort(a,function(a,b){return d(a.value,b.value)||a.index-b.index});for(c=0;c<a.length;c++)a[c]=a[c].value};goog.array.sortObjectsByKey=function(a,b,c){var d=c||goog.array.defaultCompare;goog.array.sort(a,function(a,c){return d(a[b],c[b])})};
goog.array.isSorted=function(a,b,c){b=b||goog.array.defaultCompare;for(var d=1;d<a.length;d++){var e=b(a[d-1],a[d]);if(0<e||0==e&&c)return!1}return!0};goog.array.equals=function(a,b,c){if(!goog.isArrayLike(a)||!goog.isArrayLike(b)||a.length!=b.length)return!1;var d=a.length;c=c||goog.array.defaultCompareEquality;for(var e=0;e<d;e++)if(!c(a[e],b[e]))return!1;return!0};
goog.array.compare3=function(a,b,c){c=c||goog.array.defaultCompare;for(var d=Math.min(a.length,b.length),e=0;e<d;e++){var f=c(a[e],b[e]);if(0!=f)return f}return goog.array.defaultCompare(a.length,b.length)};goog.array.defaultCompare=function(a,b){return a>b?1:a<b?-1:0};goog.array.defaultCompareEquality=function(a,b){return a===b};goog.array.binaryInsert=function(a,b,c){c=goog.array.binarySearch(a,b,c);return 0>c?(goog.array.insertAt(a,b,-(c+1)),!0):!1};
goog.array.binaryRemove=function(a,b,c){b=goog.array.binarySearch(a,b,c);return 0<=b?goog.array.removeAt(a,b):!1};goog.array.bucket=function(a,b,c){for(var d={},e=0;e<a.length;e++){var f=a[e],g=b.call(c,f,e,a);goog.isDef(g)&&(d[g]||(d[g]=[])).push(f)}return d};goog.array.toObject=function(a,b,c){var d={};goog.array.forEach(a,function(e,f){d[b.call(c,e,f,a)]=e});return d};
goog.array.range=function(a,b,c){var d=[],e=0,f=a;c=c||1;void 0!==b&&(e=a,f=b);if(0>c*(f-e))return[];if(0<c)for(a=e;a<f;a+=c)d.push(a);else for(a=e;a>f;a+=c)d.push(a);return d};goog.array.repeat=function(a,b){for(var c=[],d=0;d<b;d++)c[d]=a;return c};goog.array.flatten=function(a){for(var b=[],c=0;c<arguments.length;c++){var d=arguments[c];goog.isArray(d)?b.push.apply(b,goog.array.flatten.apply(null,d)):b.push(d)}return b};
goog.array.rotate=function(a,b){goog.asserts.assert(null!=a.length);a.length&&(b%=a.length,0<b?goog.array.ARRAY_PROTOTYPE_.unshift.apply(a,a.splice(-b,b)):0>b&&goog.array.ARRAY_PROTOTYPE_.push.apply(a,a.splice(0,-b)));return a};goog.array.moveItem=function(a,b,c){goog.asserts.assert(0<=b&&b<a.length);goog.asserts.assert(0<=c&&c<a.length);b=goog.array.ARRAY_PROTOTYPE_.splice.call(a,b,1);goog.array.ARRAY_PROTOTYPE_.splice.call(a,c,0,b[0])};
goog.array.zip=function(a){if(!arguments.length)return[];for(var b=[],c=0;;c++){for(var d=[],e=0;e<arguments.length;e++){var f=arguments[e];if(c>=f.length)return b;d.push(f[c])}b.push(d)}};goog.array.shuffle=function(a,b){for(var c=b||Math.random,d=a.length-1;0<d;d--){var e=Math.floor(c()*(d+1)),f=a[d];a[d]=a[e];a[e]=f}};goog.math={};goog.math.randomInt=function(a){return Math.floor(Math.random()*a)};goog.math.uniformRandom=function(a,b){return a+Math.random()*(b-a)};goog.math.clamp=function(a,b,c){return Math.min(Math.max(a,b),c)};goog.math.modulo=function(a,b){var c=a%b;return 0>c*b?c+b:c};goog.math.lerp=function(a,b,c){return a+c*(b-a)};goog.math.nearlyEquals=function(a,b,c){return Math.abs(a-b)<=(c||1E-6)};goog.math.standardAngle=function(a){return goog.math.modulo(a,360)};
goog.math.toRadians=function(a){return a*Math.PI/180};goog.math.toDegrees=function(a){return 180*a/Math.PI};goog.math.angleDx=function(a,b){return b*Math.cos(goog.math.toRadians(a))};goog.math.angleDy=function(a,b){return b*Math.sin(goog.math.toRadians(a))};goog.math.angle=function(a,b,c,d){return goog.math.standardAngle(goog.math.toDegrees(Math.atan2(d-b,c-a)))};goog.math.angleDifference=function(a,b){var c=goog.math.standardAngle(b)-goog.math.standardAngle(a);180<c?c-=360:-180>=c&&(c=360+c);return c};
goog.math.sign=function(a){return 0==a?0:0>a?-1:1};goog.math.longestCommonSubsequence=function(a,b,c,d){c=c||function(a,b){return a==b};d=d||function(b,c){return a[b]};for(var e=a.length,f=b.length,g=[],h=0;h<e+1;h++)g[h]=[],g[h][0]=0;for(var k=0;k<f+1;k++)g[0][k]=0;for(h=1;h<=e;h++)for(k=1;k<=f;k++)c(a[h-1],b[k-1])?g[h][k]=g[h-1][k-1]+1:g[h][k]=Math.max(g[h-1][k],g[h][k-1]);for(var l=[],h=e,k=f;0<h&&0<k;)c(a[h-1],b[k-1])?(l.unshift(d(h-1,k-1)),h--,k--):g[h-1][k]>g[h][k-1]?h--:k--;return l};
goog.math.sum=function(a){return goog.array.reduce(arguments,function(a,c){return a+c},0)};goog.math.average=function(a){return goog.math.sum.apply(null,arguments)/arguments.length};goog.math.sampleVariance=function(a){var b=arguments.length;if(2>b)return 0;var c=goog.math.average.apply(null,arguments);return goog.math.sum.apply(null,goog.array.map(arguments,function(a){return Math.pow(a-c,2)}))/(b-1)};goog.math.standardDeviation=function(a){return Math.sqrt(goog.math.sampleVariance.apply(null,arguments))};
goog.math.isInt=function(a){return isFinite(a)&&0==a%1};goog.math.isFiniteNumber=function(a){return isFinite(a)&&!isNaN(a)};goog.math.safeFloor=function(a,b){goog.asserts.assert(!goog.isDef(b)||0<b);return Math.floor(a+(b||2E-15))};goog.math.safeCeil=function(a,b){goog.asserts.assert(!goog.isDef(b)||0<b);return Math.ceil(a-(b||2E-15))};goog.iter={};goog.iter.StopIteration="StopIteration"in goog.global?goog.global.StopIteration:Error("StopIteration");goog.iter.Iterator=function(){};goog.iter.Iterator.prototype.next=function(){throw goog.iter.StopIteration;};goog.iter.Iterator.prototype.__iterator__=function(a){return this};
goog.iter.toIterator=function(a){if(a instanceof goog.iter.Iterator)return a;if("function"==typeof a.__iterator__)return a.__iterator__(!1);if(goog.isArrayLike(a)){var b=0,c=new goog.iter.Iterator;c.next=function(){for(;;){if(b>=a.length)throw goog.iter.StopIteration;if(b in a)return a[b++];b++}};return c}throw Error("Not implemented");};
goog.iter.forEach=function(a,b,c){if(goog.isArrayLike(a))try{goog.array.forEach(a,b,c)}catch(d){if(d!==goog.iter.StopIteration)throw d;}else{a=goog.iter.toIterator(a);try{for(;;)b.call(c,a.next(),void 0,a)}catch(e){if(e!==goog.iter.StopIteration)throw e;}}};goog.iter.filter=function(a,b,c){var d=goog.iter.toIterator(a);a=new goog.iter.Iterator;a.next=function(){for(;;){var a=d.next();if(b.call(c,a,void 0,d))return a}};return a};
goog.iter.range=function(a,b,c){var d=0,e=a,f=c||1;1<arguments.length&&(d=a,e=b);if(0==f)throw Error("Range step argument must not be zero");var g=new goog.iter.Iterator;g.next=function(){if(0<f&&d>=e||0>f&&d<=e)throw goog.iter.StopIteration;var a=d;d+=f;return a};return g};goog.iter.join=function(a,b){return goog.iter.toArray(a).join(b)};goog.iter.map=function(a,b,c){var d=goog.iter.toIterator(a);a=new goog.iter.Iterator;a.next=function(){for(;;){var a=d.next();return b.call(c,a,void 0,d)}};return a};
goog.iter.reduce=function(a,b,c,d){var e=c;goog.iter.forEach(a,function(a){e=b.call(d,e,a)});return e};goog.iter.some=function(a,b,c){a=goog.iter.toIterator(a);try{for(;;)if(b.call(c,a.next(),void 0,a))return!0}catch(d){if(d!==goog.iter.StopIteration)throw d;}return!1};goog.iter.every=function(a,b,c){a=goog.iter.toIterator(a);try{for(;;)if(!b.call(c,a.next(),void 0,a))return!1}catch(d){if(d!==goog.iter.StopIteration)throw d;}return!0};
goog.iter.chain=function(a){var b=goog.iter.toIterator(arguments),c=new goog.iter.Iterator,d=null;c.next=function(){for(;;){if(null==d){var a=b.next();d=goog.iter.toIterator(a)}try{return d.next()}catch(c){if(c!==goog.iter.StopIteration)throw c;d=null}}};return c};goog.iter.chainFromIterable=function(a){return goog.iter.chain.apply(void 0,a)};
goog.iter.dropWhile=function(a,b,c){var d=goog.iter.toIterator(a);a=new goog.iter.Iterator;var e=!0;a.next=function(){for(;;){var a=d.next();if(!e||!b.call(c,a,void 0,d))return e=!1,a}};return a};goog.iter.takeWhile=function(a,b,c){var d=goog.iter.toIterator(a);a=new goog.iter.Iterator;var e=!0;a.next=function(){for(;;)if(e){var a=d.next();if(b.call(c,a,void 0,d))return a;e=!1}else throw goog.iter.StopIteration;};return a};
goog.iter.toArray=function(a){if(goog.isArrayLike(a))return goog.array.toArray(a);a=goog.iter.toIterator(a);var b=[];goog.iter.forEach(a,function(a){b.push(a)});return b};goog.iter.equals=function(a,b){var c=goog.iter.zipLongest({},a,b);return goog.iter.every(c,function(a){return a[0]==a[1]})};goog.iter.nextOrValue=function(a,b){try{return goog.iter.toIterator(a).next()}catch(c){if(c!=goog.iter.StopIteration)throw c;return b}};
goog.iter.product=function(a){if(goog.array.some(arguments,function(a){return!a.length})||!arguments.length)return new goog.iter.Iterator;var b=new goog.iter.Iterator,c=arguments,d=goog.array.repeat(0,c.length);b.next=function(){if(d){for(var a=goog.array.map(d,function(a,b){return c[b][a]}),b=d.length-1;0<=b;b--){goog.asserts.assert(d);if(d[b]<c[b].length-1){d[b]++;break}if(0==b){d=null;break}d[b]=0}return a}throw goog.iter.StopIteration;};return b};
goog.iter.cycle=function(a){var b=goog.iter.toIterator(a),c=[],d=0;a=new goog.iter.Iterator;var e=!1;a.next=function(){var a=null;if(!e)try{return a=b.next(),c.push(a),a}catch(g){if(g!=goog.iter.StopIteration||goog.array.isEmpty(c))throw g;e=!0}a=c[d];d=(d+1)%c.length;return a};return a};goog.iter.count=function(a,b){var c=a||0,d=goog.isDef(b)?b:1,e=new goog.iter.Iterator;e.next=function(){var a=c;c+=d;return a};return e};
goog.iter.repeat=function(a){var b=new goog.iter.Iterator;b.next=goog.functions.constant(a);return b};goog.iter.accumulate=function(a){var b=goog.iter.toIterator(a),c=0;a=new goog.iter.Iterator;a.next=function(){return c+=b.next()};return a};goog.iter.zip=function(a){var b=arguments,c=new goog.iter.Iterator;if(0<b.length){var d=goog.array.map(b,goog.iter.toIterator);c.next=function(){return goog.array.map(d,function(a){return a.next()})}}return c};
goog.iter.zipLongest=function(a,b){var c=goog.array.slice(arguments,1),d=new goog.iter.Iterator;if(0<c.length){var e=goog.array.map(c,goog.iter.toIterator);d.next=function(){var b=!1,c=goog.array.map(e,function(c){var d;try{d=c.next(),b=!0}catch(e){if(e!==goog.iter.StopIteration)throw e;d=a}return d});if(!b)throw goog.iter.StopIteration;return c}}return d};goog.iter.compress=function(a,b){var c=goog.iter.toIterator(b);return goog.iter.filter(a,function(){return!!c.next()})};
goog.iter.GroupByIterator_=function(a,b){this.iterator=goog.iter.toIterator(a);this.keyFunc=b||goog.functions.identity};goog.inherits(goog.iter.GroupByIterator_,goog.iter.Iterator);goog.iter.GroupByIterator_.prototype.next=function(){for(;this.currentKey==this.targetKey;)this.currentValue=this.iterator.next(),this.currentKey=this.keyFunc(this.currentValue);this.targetKey=this.currentKey;return[this.currentKey,this.groupItems_(this.targetKey)]};
goog.iter.GroupByIterator_.prototype.groupItems_=function(a){for(var b=[];this.currentKey==a;){b.push(this.currentValue);try{this.currentValue=this.iterator.next()}catch(c){if(c!==goog.iter.StopIteration)throw c;break}this.currentKey=this.keyFunc(this.currentValue)}return b};goog.iter.groupBy=function(a,b){return new goog.iter.GroupByIterator_(a,b)};
goog.iter.tee=function(a,b){var c=goog.iter.toIterator(a),d=goog.isNumber(b)?b:2,e=goog.array.map(goog.array.range(d),function(){return[]}),f=function(){var a=c.next();goog.array.forEach(e,function(b){b.push(a)})};return goog.array.map(e,function(a){var b=new goog.iter.Iterator;b.next=function(){goog.array.isEmpty(a)&&f();goog.asserts.assert(!goog.array.isEmpty(a));return a.shift()};return b})};goog.iter.enumerate=function(a,b){return goog.iter.zip(goog.iter.count(b),a)};
goog.iter.limit=function(a,b){goog.asserts.assert(goog.math.isInt(b)&&0<=b);var c=goog.iter.toIterator(a),d=new goog.iter.Iterator,e=b;d.next=function(){if(0<e--)return c.next();throw goog.iter.StopIteration;};return d};goog.iter.consume=function(a,b){goog.asserts.assert(goog.math.isInt(b)&&0<=b);for(var c=goog.iter.toIterator(a);0<b--;)goog.iter.nextOrValue(c,null);return c};
goog.iter.slice=function(a,b,c){goog.asserts.assert(goog.math.isInt(b)&&0<=b);a=goog.iter.consume(a,b);goog.isNumber(c)&&(goog.asserts.assert(goog.math.isInt(c)&&c>=b),a=goog.iter.limit(a,c-b));return a};goog.iter.hasDuplicates_=function(a){var b=[];goog.array.removeDuplicates(a,b);return a.length!=b.length};goog.iter.permutations=function(a,b){var c=goog.iter.toArray(a),d=goog.isNumber(b)?b:c.length,c=goog.array.repeat(c,d),c=goog.iter.product.apply(void 0,c);return goog.iter.filter(c,function(a){return!goog.iter.hasDuplicates_(a)})};
goog.iter.combinations=function(a,b){function c(a){return d[a]}var d=goog.iter.toArray(a),e=goog.iter.range(d.length),e=goog.iter.permutations(e,b),f=goog.iter.filter(e,function(a){return goog.array.isSorted(a)}),e=new goog.iter.Iterator;e.next=function(){return goog.array.map(f.next(),c)};return e};
goog.iter.combinationsWithReplacement=function(a,b){function c(a){return d[a]}var d=goog.iter.toArray(a),e=goog.array.range(d.length),e=goog.array.repeat(e,b),e=goog.iter.product.apply(void 0,e),f=goog.iter.filter(e,function(a){return goog.array.isSorted(a)}),e=new goog.iter.Iterator;e.next=function(){return goog.array.map(f.next(),c)};return e};goog.ui={};goog.ui.IdGenerator=function(){};goog.addSingletonGetter(goog.ui.IdGenerator);goog.ui.IdGenerator.prototype.nextId_=0;goog.ui.IdGenerator.prototype.getNextUniqueId=function(){return":"+(this.nextId_++).toString(36)};var jsnx={utils:{}};jsnx.utils.misc={};jsnx.utils.misc.is_list_of_ints=function(a){if(!goog.isArrayLike(a))return!1;for(var b=0,c=a.length;b<c;b++)if(isNaN(a[b]))return!1;return!0};goog.exportSymbol("jsnx.utils.misc.is_list_of_ints",jsnx.utils.misc.is_list_of_ints);goog.exportSymbol("jsnx.utils.is_list_of_ints",jsnx.utils.misc.is_list_of_ints);jsnx.utils.misc.cumulative_sum=function(a){var b=0;return goog.iter.map(a,function(a){return b+=a})};goog.exportSymbol("jsnx.utils.misc.cumulative_sum",jsnx.utils.misc.cumulative_sum);
goog.exportSymbol("jsnx.utils.cumulative_sum",jsnx.utils.misc.cumulative_sum);jsnx.utils.misc.generate_unique_node=function(){return goog.ui.IdGenerator.getInstance().getNextUniqueId()};goog.exportSymbol("jsnx.utils.misc.generate_unique_node",jsnx.utils.misc.generate_unique_node);goog.exportSymbol("jsnx.utils.generate_unique_node",jsnx.utils.misc.generate_unique_node);goog.object={};goog.object.forEach=function(a,b,c){for(var d in a)b.call(c,a[d],d,a)};goog.object.filter=function(a,b,c){var d={},e;for(e in a)b.call(c,a[e],e,a)&&(d[e]=a[e]);return d};goog.object.map=function(a,b,c){var d={},e;for(e in a)d[e]=b.call(c,a[e],e,a);return d};goog.object.some=function(a,b,c){for(var d in a)if(b.call(c,a[d],d,a))return!0;return!1};goog.object.every=function(a,b,c){for(var d in a)if(!b.call(c,a[d],d,a))return!1;return!0};
goog.object.getCount=function(a){var b=0,c;for(c in a)b++;return b};goog.object.getAnyKey=function(a){for(var b in a)return b};goog.object.getAnyValue=function(a){for(var b in a)return a[b]};goog.object.contains=function(a,b){return goog.object.containsValue(a,b)};goog.object.getValues=function(a){var b=[],c=0,d;for(d in a)b[c++]=a[d];return b};goog.object.getKeys=function(a){var b=[],c=0,d;for(d in a)b[c++]=d;return b};
goog.object.getValueByKeys=function(a,b){for(var c=goog.isArrayLike(b),d=c?b:arguments,c=c?0:1;c<d.length&&(a=a[d[c]],goog.isDef(a));c++);return a};goog.object.containsKey=function(a,b){return b in a};goog.object.containsValue=function(a,b){for(var c in a)if(a[c]==b)return!0;return!1};goog.object.findKey=function(a,b,c){for(var d in a)if(b.call(c,a[d],d,a))return d};goog.object.findValue=function(a,b,c){return(b=goog.object.findKey(a,b,c))&&a[b]};
goog.object.isEmpty=function(a){for(var b in a)return!1;return!0};goog.object.clear=function(a){for(var b in a)delete a[b]};goog.object.remove=function(a,b){var c;(c=b in a)&&delete a[b];return c};goog.object.add=function(a,b,c){if(b in a)throw Error('The object already contains the key "'+b+'"');goog.object.set(a,b,c)};goog.object.get=function(a,b,c){return b in a?a[b]:c};goog.object.set=function(a,b,c){a[b]=c};goog.object.setIfUndefined=function(a,b,c){return b in a?a[b]:a[b]=c};
goog.object.clone=function(a){var b={},c;for(c in a)b[c]=a[c];return b};goog.object.unsafeClone=function(a){var b=goog.typeOf(a);if("object"==b||"array"==b){if(a.clone)return a.clone();var b="array"==b?[]:{},c;for(c in a)b[c]=goog.object.unsafeClone(a[c]);return b}return a};goog.object.transpose=function(a){var b={},c;for(c in a)b[a[c]]=c;return b};goog.object.PROTOTYPE_FIELDS_="constructor hasOwnProperty isPrototypeOf propertyIsEnumerable toLocaleString toString valueOf".split(" ");
goog.object.extend=function(a,b){for(var c,d,e=1;e<arguments.length;e++){d=arguments[e];for(c in d)a[c]=d[c];for(var f=0;f<goog.object.PROTOTYPE_FIELDS_.length;f++)c=goog.object.PROTOTYPE_FIELDS_[f],Object.prototype.hasOwnProperty.call(d,c)&&(a[c]=d[c])}};
goog.object.create=function(a){var b=arguments.length;if(1==b&&goog.isArray(arguments[0]))return goog.object.create.apply(null,arguments[0]);if(b%2)throw Error("Uneven number of arguments");for(var c={},d=0;d<b;d+=2)c[arguments[d]]=arguments[d+1];return c};goog.object.createSet=function(a){var b=arguments.length;if(1==b&&goog.isArray(arguments[0]))return goog.object.createSet.apply(null,arguments[0]);for(var c={},d=0;d<b;d++)c[arguments[d]]=!0;return c};
goog.object.createImmutableView=function(a){var b=a;Object.isFrozen&&!Object.isFrozen(a)&&(b=Object.create(a),Object.freeze(b));return b};goog.object.isImmutableView=function(a){return!!Object.isFrozen&&Object.isFrozen(a)};jsnx.contrib={};jsnx.contrib.Tuple=function(a){var b=arguments;1===arguments.length&&goog.isArrayLike(arguments[0])&&(b=arguments[0]);this.__hash__="t";for(var c=0,d=b.length;c<d;c++)this[c]=b[c],this.__hash__+=jsnx.contrib.misc.get_hash(b[c]);this.length=b.length;return goog.object.createImmutableView(this)};jsnx.contrib.Tuple.prototype.__hash__="";jsnx.contrib.Tuple.prototype.length=0;goog.exportSymbol("jsnx.contrib.Tuple.prototype.length",jsnx.contrib.Tuple.prototype.length);
jsnx.contrib.Tuple.prototype.toString=function(){return this.__hash__};goog.exportSymbol("jsnx.contrib.Tuple.prototype.toString",jsnx.contrib.Tuple.prototype.toString);jsnx.contrib.Tuple.createTuple=function(a){return goog.isArrayLike(arguments[0])?new jsnx.contrib.Tuple(arguments[0]):new jsnx.contrib.Tuple(arguments)};goog.exportSymbol("jsnx.Tuple",jsnx.contrib.Tuple.createTuple);goog.exportSymbol("jsnx.t",jsnx.contrib.Tuple.createTuple);jsnx.exception={};jsnx.exception.JSNetworkXException=function(a){this.name="JSNetworkXException";this.message=a};goog.exportSymbol("jsnx.exception.JSNetworkXException",jsnx.exception.JSNetworkXException);jsnx.exception.JSNetworkXException.prototype=Error();jsnx.exception.JSNetworkXException.prototype.constructor=jsnx.exception.JSNetworkXException;goog.exportSymbol("jsnx.JSNetworkXException",jsnx.exception.JSNetworkXException);
jsnx.exception.JSNetworkXError=function(a){jsnx.exception.JSNetworkXException.call(this,a);this.name="JSNetworkXError"};goog.inherits(jsnx.exception.JSNetworkXError,jsnx.exception.JSNetworkXException);goog.exportSymbol("jsnx.exception.JSNetworkXError",jsnx.exception.JSNetworkXError);goog.exportSymbol("jsnx.JSNetworkXError",jsnx.exception.JSNetworkXError);jsnx.exception.JSNetworkXPointlessConcept=function(a){jsnx.exception.JSNetworkXException.call(this,a);this.name="JSNetworkXPointlessConcept"};
goog.inherits(jsnx.exception.JSNetworkXPointlessConcept,jsnx.exception.JSNetworkXException);goog.exportSymbol("jsnx.exception.JSNetworkXPointlessConcept",jsnx.exception.JSNetworkXPointlessConcept);goog.exportSymbol("jsnx.JSNetworkXPointlessConcept",jsnx.exception.JSNetworkXPointlessConcept);jsnx.exception.JSNetworkXAlgorithmError=function(a){jsnx.exception.JSNetworkXException.call(this,a);this.name="JSNetworkXAlgorithmError"};goog.inherits(jsnx.exception.JSNetworkXAlgorithmError,jsnx.exception.JSNetworkXException);
goog.exportSymbol("jsnx.exception.JSNetworkXAlgorithmError",jsnx.exception.JSNetworkXAlgorithmError);goog.exportSymbol("jsnx.JSNetworkXAlgorithmError",jsnx.exception.JSNetworkXAlgorithmError);jsnx.exception.JSNetworkXUnfeasible=function(a){jsnx.exception.JSNetworkXAlgorithmError.call(this,a);this.name="JSNetworkXUnfeasible"};goog.inherits(jsnx.exception.JSNetworkXUnfeasible,jsnx.exception.JSNetworkXAlgorithmError);goog.exportSymbol("jsnx.exception.JSNetworkXUnfeasible",jsnx.exception.JSNetworkXUnfeasible);
goog.exportSymbol("jsnx.JSNetworkXUnfeasible",jsnx.exception.JSNetworkXUnfeasible);jsnx.exception.JSNetworkXNoPath=function(a){jsnx.exception.JSNetworkXUnfeasible.call(this,a);this.name="JSNetworkXNoPath"};goog.inherits(jsnx.exception.JSNetworkXNoPath,jsnx.exception.JSNetworkXUnfeasible);goog.exportSymbol("jsnx.exception.JSNetworkXNoPath",jsnx.exception.JSNetworkXNoPath);goog.exportSymbol("jsnx.JSNetworkXNoPath",jsnx.exception.JSNetworkXNoPath);
jsnx.exception.JSNetworkXUnbounded=function(a){jsnx.exception.JSNetworkXAlgorithmError.call(this,a);this.name="JSNetworkXUnbounded"};goog.inherits(jsnx.exception.JSNetworkXUnbounded,jsnx.exception.JSNetworkXAlgorithmError);goog.exportSymbol("jsnx.exception.JSNetworkXUnbounded",jsnx.exception.JSNetworkXUnbounded);goog.exportSymbol("jsnx.JSNetworkXUnbounded",jsnx.exception.JSNetworkXUnbounded);jsnx.exception.KeyError=function(a){this.name="KeyError";this.message=a};
jsnx.exception.KeyError.prototype=Error();jsnx.exception.KeyError.prototype.constructor=jsnx.exception.KeyError;goog.exportSymbol("jsnx.KeyError",jsnx.exception.KeyError);jsnx.TESTING=!1;jsnx.version="0.2.0";goog.exportSymbol("jsnx.version",jsnx.version);jsnx.contrib.misc={};jsnx.contrib.misc.get_hash=function(a,b){var c=typeof a;return"object"===c||"function"===c?a.hasOwnProperty("__hash__")?a.__hash__:a.toString!==Object.prototype.toString&&a.toString!==Array.prototype.toString?a.toString():b?b(a):"o"+goog.getUid(a):c.substr(0,1)+a};goog.exportSymbol("jsnx.contrib.misc.get_hash",jsnx.contrib.misc.get_hash);jsnx.TESTING&&goog.exportSymbol("jsnx.contrib.misc.get_hash",jsnx.contrib.misc.get_hash);jsnx.contrib.Map=function(a){this.string_values_={};this.number_values_={};this.values_={};this.keys_={};if(goog.isDefAndNotNull(a))if(jsnx.helper.isIterator(a)||goog.isArrayLike(a))jsnx.helper.forEach(a,function(a){this.set.apply(this,a)},this);else if(goog.isObject(a))for(var b in a)this.set(isNaN(+b)?b:+b,a[b])};goog.exportSymbol("jsnx.contrib.Map",jsnx.contrib.Map);goog.exportSymbol("jsnx.Map",jsnx.contrib.Map);
jsnx.contrib.Map.prototype.get_storage_=function(a){switch(typeof a){case "number":return this.number_values_;case "string":return this.string_values_;default:return this.values_}};jsnx.contrib.Map.prototype.get=function(a,b){var c=this.get_storage_(a);if("undefined"!==typeof c[a])return c[a];if(goog.isDef(b))return b;throw new jsnx.exception.KeyError("Map does not contain key "+goog.json.serialize(a));};goog.exportProperty(jsnx.contrib.Map.prototype,"get",jsnx.contrib.Map.prototype.get);
jsnx.contrib.Map.prototype.has=function(a){return"undefined"!==typeof this.get_storage_(a)[a]};goog.exportProperty(jsnx.contrib.Map.prototype,"has",jsnx.contrib.Map.prototype.has);jsnx.contrib.Map.prototype.set=function(a,b){var c=this.get_storage_(a);c[a]=b;c===this.values_&&(this.keys_[a]=a);return b};goog.exportProperty(jsnx.contrib.Map.prototype,"set",jsnx.contrib.Map.prototype.set);
jsnx.contrib.Map.prototype.remove=function(a){var b=this.get_storage_(a);if("undefined"!==typeof b[a])delete b[a],b===this.values_&&delete this.keys_[a];else throw new jsnx.exception.KeyError("Map does not contain key "+goog.json.serialize(a));};goog.exportProperty(jsnx.contrib.Map.prototype,"remove",jsnx.contrib.Map.prototype.remove);
jsnx.contrib.Map.prototype.items=function(){var a=[],b;for(b in this.number_values_)a.push([+b,this.number_values_[b]]);for(b in this.string_values_)a.push([b,this.string_values_[b]]);for(b in this.values_)a.push([this.keys_[b],this.values_[b]]);return a};goog.exportProperty(jsnx.contrib.Map.prototype,"items",jsnx.contrib.Map.prototype.items);jsnx.contrib.Map.prototype.copy=function(a){return jsnx.helper.deepcopy_instance(this,a)};
jsnx.contrib.Map.prototype.keys=function(){return goog.array.map(goog.object.getKeys(this.number_values_),function(a){return+a}).concat(goog.object.getKeys(this.string_values_)).concat(goog.object.getValues(this.keys_))};goog.exportProperty(jsnx.contrib.Map.prototype,"keys",jsnx.contrib.Map.prototype.keys);jsnx.contrib.Map.prototype.values=function(){return goog.object.getValues(this.number_values_).concat(goog.object.getValues(this.string_values_)).concat(goog.object.getValues(this.values_))};
goog.exportProperty(jsnx.contrib.Map.prototype,"values",jsnx.contrib.Map.prototype.values);
jsnx.contrib.Map.prototype.__iterator__=function(){var a=new goog.iter.Iterator,b=goog.object.getKeys(this.string_values_),c=goog.object.getKeys(this.number_values_),d=goog.object.getKeys(this.values_),e=0,f=0,g=0;a.next=goog.bind(function(){var a;if(e<c.length)return a=c[e++],[+a,this.number_values_[a]];if(f<b.length)return a=b[f++],[a,this.string_values_[a]];if(g<d.length)return a=d[g++],[this.keys_[a],this.values_[a]];throw goog.iter.StopIteration;},this);return a};
jsnx.contrib.Map.prototype.count=function(){return goog.object.getCount(this.values_)+goog.object.getCount(this.number_values_)+goog.object.getCount(this.string_values_)};goog.exportProperty(jsnx.contrib.Map.prototype,"count",jsnx.contrib.Map.prototype.count);jsnx.contrib.Map.prototype.clear=function(){goog.object.clear(this.string_values_);goog.object.clear(this.number_values_);goog.object.clear(this.values_);goog.object.clear(this.keys_)};goog.exportProperty(jsnx.contrib.Map.prototype,"clear",jsnx.contrib.Map.prototype.clear);
jsnx.contrib.Map.prototype.forEach=function(a,b){goog.iter.forEach(this,function(c){a.apply(b,c)})};goog.exportProperty(jsnx.contrib.Map.prototype,"forEach",jsnx.contrib.Map.prototype.forEach);jsnx.contrib.Set=function(a){this.map_=new jsnx.contrib.Map;goog.isDefAndNotNull(a)&&(jsnx.helper.isIterator(a)||goog.isArrayLike(a))&&jsnx.helper.forEach(a,function(a){this.add(a)},this)};goog.exportSymbol("jsnx.contrib.Set",jsnx.contrib.Set);goog.exportSymbol("jsnx.Set",jsnx.contrib.Set);jsnx.contrib.Set.prototype.has=function(a){return this.map_.has(a)};goog.exportProperty(jsnx.contrib.Set.prototype,"has",jsnx.contrib.Set.prototype.has);
jsnx.contrib.Set.prototype.add=function(a){this.map_.set(a,!0)};goog.exportProperty(jsnx.contrib.Set.prototype,"add",jsnx.contrib.Set.prototype.add);jsnx.contrib.Set.prototype.remove=function(a){try{this.map_.remove(a)}catch(b){if(!(b instanceof jsnx.exception.KeyError))throw b;}};goog.exportProperty(jsnx.contrib.Set.prototype,"remove",jsnx.contrib.Set.prototype.remove);jsnx.contrib.Set.prototype.copy=function(a){return jsnx.helper.deepcopy_instance(this,a)};jsnx.contrib.Set.prototype.values=function(){return this.map_.keys()};
goog.exportProperty(jsnx.contrib.Set.prototype,"values",jsnx.contrib.Set.prototype.values);jsnx.contrib.Set.prototype.__iterator__=function(){return goog.iter.map(this.map_,function(a){return a[0]})};jsnx.contrib.Set.prototype.difference=function(a){for(var b=new jsnx.contrib.Set(this.values()),c=0,d=arguments.length;c<d;c++){var e=arguments[c];e instanceof jsnx.contrib.Set&&(e=e.values());for(var f=0,g=e.length;f<g;f++)b.remove(e[f])}return b};
goog.exportProperty(jsnx.contrib.Set.prototype,"difference",jsnx.contrib.Set.prototype.difference);jsnx.contrib.Set.prototype.intersection=function(a){for(var b=new jsnx.contrib.Set,c=0,d=arguments.length;c<d;c++){var e=arguments[c];e instanceof jsnx.contrib.Set&&(e=e.values());for(var f=0,g=e.length;f<g;f++)this.has(e[f])&&b.add(e[f])}return b};goog.exportProperty(jsnx.contrib.Set.prototype,"intersection",jsnx.contrib.Set.prototype.intersection);jsnx.contrib.Set.prototype.count=function(){return this.map_.count()};
goog.exportProperty(jsnx.contrib.Set.prototype,"count",jsnx.contrib.Set.prototype.count);jsnx.contrib.Set.prototype.clear=function(){this.map_.clear()};goog.exportProperty(jsnx.contrib.Set.prototype,"clear",jsnx.contrib.Set.prototype.clear);jsnx.contrib.Set.prototype.forEach=function(a,b){goog.iter.forEach(this,a,b)};goog.exportProperty(jsnx.contrib.Set.prototype,"forEach",jsnx.contrib.Set.prototype.forEach);jsnx.helper={};goog.exportSymbol("jsnx.filter",goog.iter.filter);jsnx.helper.objectFromKV=function(a){return goog.iter.reduce(jsnx.helper.iter(a),function(a,c){a[c[0]]=c[1];return a},{})};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.objectFromKV",jsnx.helper.objectFromKV);jsnx.helper.fromkeys=function(a,b){goog.isDef(b)||(b=null);var c={};jsnx.helper.forEach(a,function(a){c[a]=b});return c};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.fromkeys",jsnx.helper.fromkeys);
jsnx.helper.mapfromkeys=function(a,b){goog.isDef(b)||(b=null);var c=new jsnx.contrib.Map;jsnx.helper.forEach(a,function(a){c.set(a,b)});return c};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.mapfromkeys",jsnx.helper.mapfromkeys);jsnx.helper.isIterator=function(a){return goog.isDefAndNotNull(a)&&(a instanceof goog.iter.Iterator||goog.isFunction(a.__iterator__))};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.isIterator",jsnx.helper.isIterator);
jsnx.helper.isIterable=function(a){return"object"===goog.typeOf(a)||goog.isArrayLike(a)||jsnx.helper.isIterator(a)};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.isIterable",jsnx.helper.isIterable);jsnx.helper.len=function(a){if(a instanceof jsnx.classes.Graph)return a.number_of_nodes();if(goog.isString(a)||goog.isArrayLike(a))return a.length;if(jsnx.helper.isPlainObject(a))return goog.object.getCount(a);throw new TypeError;};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.len",jsnx.helper.len);
jsnx.helper.forEach=function(a,b,c,d){goog.isBoolean(c)&&(d=c,c=null);if(d){var e=b;b=function(a){e.apply(this,a)}}a instanceof jsnx.classes.Graph?goog.iter.forEach(jsnx.helper.iter(a),b,c):jsnx.helper.isIterator(a)?goog.iter.forEach(a,b,c):goog.isArrayLike(a)||goog.isString(a)?goog.array.forEach(a,b,c):goog.isObject(a)&&jsnx.helper.forEach(goog.object.getKeys(a),b,c)};goog.exportSymbol("jsnx.forEach",jsnx.helper.forEach);jsnx.TESTING&&goog.exportSymbol("jsnx.helper.forEach",jsnx.helper.forEach);
jsnx.helper.map=function(a,b,c){if(a instanceof jsnx.classes.Graph)return jsnx.helper.map(jsnx.helper.iter(a),b,c);if(goog.isArrayLike(a))return goog.array.map(a,b,c);if(jsnx.helper.isIterator(a))return goog.iter.map(a,b,c);if(goog.isObject(a))return goog.object.map(a,b,c);throw new TypeError;};goog.exportSymbol("jsnx.map",jsnx.helper.map);jsnx.TESTING&&goog.exportSymbol("jsnx.helper.map",jsnx.helper.map);
jsnx.helper.zip=function(a){var b=arguments,c=b[0];if(goog.isArrayLike(c))return goog.array.zip.apply(null,b);if(jsnx.helper.isIterator(c)){var c=new goog.iter.Iterator,d=b.length;c.next=function(){for(var a=[],c=0;c<d;c++)a.push(b[c].next());return a};return c}if(goog.isObject(c))return goog.array.zip.apply(null,goog.array.map(b,goog.object.getKeys));throw new TypeError;};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.zip",jsnx.helper.zip);
jsnx.helper.max=function(a,b){a=goog.isFunction(b)?jsnx.helper.toArray(jsnx.helper.map(a,function(){return b.apply(null,arguments)})):jsnx.helper.toArray(a);return Math.max.apply(null,a)};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.max",jsnx.helper.max);
jsnx.helper.range=function(a,b,c){if(0===arguments.length)return goog.iter.toIterator([]);if(1===arguments.length)b=a,a=0,c=1;else if(2===arguments.length)c=1;else if(3===arguments.length&&0===arguments[2])throw"range() step argument must not be zero";var d=new goog.iter.Iterator,e=0>c,f=a,g;d.next=function(){if(e&&f<=b||!e&&f>=b)throw goog.iter.StopIteration;g=f;f+=c;return g};return d};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.range",jsnx.helper.range);
jsnx.helper.combinations=function(a,b){var c=jsnx.helper.toArray(a),d=c.length;if(b>d)return new goog.iter.Iterator;var e=jsnx.helper.toArray(jsnx.helper.range(b)),f=new goog.iter.Iterator;f.next=function(){var a=goog.array.map(e,function(a){return c[a]});this.next=function(){var a=!1,f;for(f=b;f--;)if(e[f]!=f+d-b){a=!0;break}if(!a)throw goog.iter.StopIteration;e[f]+=1;for(a=f+1;a<b;a++)e[a]=e[a-1]+1;return goog.array.map(e,function(a){return c[a]})};return a};return f};
jsnx.TESTING&&goog.exportSymbol("jsnx.helper.combinations",jsnx.helper.combinations);
jsnx.helper.permutations=function(a,b){var c=jsnx.helper.toArray(a),d=c.length,e=goog.isNumber(b)?b:d;if(e>d)return new goog.iter.Iterator;var f=jsnx.helper.toArray(jsnx.helper.range(d)),g=jsnx.helper.toArray(jsnx.helper.range(d,d-e,-1)),h=new goog.iter.Iterator,k=new goog.iter.Iterator,l,m=!0;h.next=function(){this.next=l.next;return goog.array.map(f.slice(0,e),function(a){return c[a]})};k.next=function(){return m};l=jsnx.helper.nested_chain(k,function(a){if(!a)throw goog.iter.StopIteration;m=!1;
return jsnx.helper.range(e-1,-1,-1)},function(a){if(!m)if(g[a]-=1,0===g[a])f.splice.apply(f,[a,f.length].concat(f.slice(a+1).concat([f[a]]))),g[a]=d-a;else{var b=g[a],h=f[a];f[a]=f[f.length-b];f[f.length-b]=h;m=!0;return jsnx.helper.iter([goog.array.map(f.slice(0,e),function(a){return c[a]})])}},function(a){return a});return h};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.permutations",jsnx.helper.permutations);
jsnx.helper.extend=function(a,b){for(var c,d,e=1;e<arguments.length;e++){d=arguments[e];for(c in d)goog.isDef(a[c])&&"object"===goog.typeOf(a[c])?"object"===goog.typeOf(a[c])&&"object"===goog.typeOf(d)&&jsnx.helper.extend(a[c],d[c]):a[c]=jsnx.helper.deepcopy(d[c]);for(var f=0;f<goog.object.PROTOTYPE_FIELDS_.length;f++)c=goog.object.PROTOTYPE_FIELDS_[f],Object.prototype.hasOwnProperty.call(d,c)&&(goog.isDef(a[c])&&"object"===goog.typeOf(a[c])?"object"===goog.typeOf(a[c])&&"object"===goog.typeOf(d)&&
jsnx.helper.extend(a[c],d[c]):a[c]=jsnx.helper.deepcopy(d[c]))}};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.extend",jsnx.helper.extend);jsnx.helper.mixin=function(a,b){for(var c in b)b.hasOwnProperty(c)&&"constructor"!==c&&(a[c]=b[c])};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.mixin",jsnx.helper.mixin);
jsnx.helper.toArray=function(a){if(a instanceof jsnx.classes.Graph)return jsnx.helper.toArray(jsnx.helper.iter(a));if(goog.isArrayLike(a))return goog.array.toArray(a);if(jsnx.helper.isIterator(a))return goog.iter.toArray(a);if(goog.isObject(a))return goog.object.getKeys(a);throw new TypeError;};goog.exportSymbol("jsnx.toArray",jsnx.helper.toArray);jsnx.TESTING&&goog.exportSymbol("jsnx.helper.toArray",jsnx.helper.toArray);
jsnx.helper.items=function(a){var b=[];goog.object.forEach(a,function(a,d){b.push([d,a])});return b};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.items",jsnx.helper.items);jsnx.helper.iteritems=function(a){var b=new goog.iter.Iterator,c=goog.iter.toIterator(goog.object.getKeys(a));b.next=function(){var b=c.next();return[b,a[b]]};return b};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.iteritems",jsnx.helper.iteritems);
jsnx.helper.iter=function(a){if(a instanceof jsnx.classes.Graph)return jsnx.helper.iter(a.adj.keys());"object"!==goog.typeOf(a)||goog.isArrayLike(a)||jsnx.helper.isIterator(a)||(a=goog.object.getKeys(a));return goog.iter.toIterator(a)};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.iter",jsnx.helper.iter);
jsnx.helper.nested_chain=function(a,b){var c=new goog.iter.Iterator,d=goog.array.slice(arguments,1);if(0===d.length)return a;try{a=goog.iter.toIterator(a)}catch(e){return c.next=function(){if("Not implemented"===e.message)throw new TypeError;},c}var f=0,g=d.length,h=[a];c.next=function(){do try{var a,b;do a=h[f].next(),goog.isDef(a)&&(b=d[f](a));while(!goog.isDef(a));if(jsnx.helper.isIterator(b)){if(f===g-1)return b;h.push(b);f+=1}else if(goog.isDef(b))return b}catch(c){if(c!==goog.iter.StopIteration)throw c;
if(0<f)h.pop(),f-=1;else throw c;}while(1)};return c};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.nested_chain",jsnx.helper.nested_chain);jsnx.helper.sentinelIterator=function(a,b){var c=new goog.iter.Iterator;c.next=function(){return goog.iter.nextOrValue(a,b)};return c};goog.exportSymbol("jsnx.sentinelIterator",jsnx.helper.sentinelIterator);jsnx.TESTING&&goog.exportSymbol("jsnx.helper.sentinelIterator",jsnx.helper.sentinelIterator);
jsnx.helper.isPlainObject=function(a){var b=Object.prototype.hasOwnProperty;if(!a||"object"!==goog.typeOf(a)||a.nodeType||a==a.window)return!1;try{if(a.constructor&&!b.call(a,"constructor")&&!b.call(a.constructor.prototype,"isPrototypeOf"))return!1}catch(c){return!1}for(var d in a);return void 0===d||b.call(a,d)};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.isPlainObject",jsnx.helper.isPlainObject);
jsnx.helper.deepcopy=function(a,b){b=b||[];var c=goog.typeOf(a);if("object"==c&&(goog.isFunction(a.copy)||jsnx.helper.isPlainObject(a))||"array"==c){for(var d=0,e=b.length;d<e;d+=2)if(a===b[d])return b[d+1];if(goog.isFunction(a.copy))return c=a.copy(b),b.push(a,c),c;c="array"==c?[]:{};b.push(a,c);for(var f in a)c[f]=jsnx.helper.deepcopy(a[f],b);return c}return a};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.deepcopy",jsnx.helper.deepcopy);
jsnx.helper.deepcopy_instance=function(a,b){var c=function(){},d={},e;c.prototype=a.constructor.prototype;for(e in a)a.hasOwnProperty(e)&&(d[e]=a[e]);d=jsnx.helper.deepcopy(d,b);c=new c;for(e in d)c[e]=d[e];return c};jsnx.TESTING&&goog.exportSymbol("jsnx.helper.deepcopy_instance",jsnx.helper.deepcopy_instance);jsnx.helper.gcd=function gcd(b,c){return 0===c?b:gcd(c,b%c)};jsnx.contrib.convert={};jsnx.contrib.convert.to_map_of_lists=function(a,b){var c=new jsnx.contrib.Map;if(goog.isDefAndNotNull(b)){b=jsnx.helper.toArray(b);var d=function(a){return goog.array.contains(goog.asserts.assertArray(b),a)};goog.array.forEach(b,function(b){c.set(b,goog.array.filter(a.neighbors(b),d))})}else jsnx.helper.forEach(a,function(b){c.set(b,a.neighbors(b))});return c};goog.exportSymbol("jsnx.contrib.convert.to_map_of_lists",jsnx.contrib.convert.to_map_of_lists);
goog.exportSymbol("jsnx.to_map_of_lists",jsnx.contrib.convert.to_map_of_lists);jsnx.contrib.convert.from_map_of_lists=function(a,b){var c=jsnx.convert.prep_create_using_(b);c.add_nodes_from(a.keys());if(c.is_multigraph()&&!c.is_directed()){var d=new jsnx.contrib.Map;a.forEach(function(a,b){goog.array.forEach(b,function(b){d.has(b)||c.add_edge(a,b)});d.set(a,1)})}else a.forEach(function(a,b){goog.array.forEach(b,function(b){c.add_edge(a,b)})});return c};
goog.exportSymbol("jsnx.contrib.convert.from_map_of_lists",jsnx.contrib.convert.from_map_of_lists);
jsnx.contrib.convert.to_map_of_maps=function(a,b,c){var d=new jsnx.contrib.Map;goog.isDefAndNotNull(b)?(b=jsnx.helper.toArray(b),goog.isDefAndNotNull(c)?goog.array.forEach(b,function(e){var f=d.set(e,new jsnx.contrib.Map);a.get(e).forEach(function(a,d){goog.asserts.assertArray(b);goog.array.contains(b,a)&&f.set(a,c)})}):goog.array.forEach(b,function(c){var f=d.set(c,new jsnx.contrib.Map);a.get(c).forEach(function(a,c){goog.asserts.assertArray(b);goog.array.contains(b,a)&&f.set(a,c)})})):goog.isDefAndNotNull(c)?
goog.iter.forEach(a.adjacency_iter(),function(a,b){var g=d.set(b,new jsnx.contrib.Map);a.forEach(function(a,b){g.set(a,c)})}):goog.iter.forEach(a.adjacency_iter(),function(a,b){var c=d.set(b,new jsnx.contrib.Map);a.forEach(function(a,b){c.set(a,b)})});return d};goog.exportSymbol("jsnx.contrib.convert.to_map_of_maps",jsnx.contrib.convert.to_map_of_maps);
jsnx.contrib.convert.from_map_of_maps=function(a,b,c){var d=jsnx.convert.prep_create_using_(b),e=new jsnx.contrib.Map,f=[];d.add_nodes_from(a.keys());c?d.is_directed()?d.is_multigraph()?a.forEach(function(a,b){if(goog.isArrayLike(b))throw Error("Value is not a map.");b.forEach(function(b,c){goog.object.forEach(c,function(c,e){goog.asserts.assertInstanceof(d,jsnx.classes.MultiDiGraph);d.add_edge(a,b,e,c)})})}):a.forEach(function(a,b){if(goog.isArrayLike(b))throw Error();b.forEach(function(b,c){goog.object.forEach(c,
function(c,e){d.add_edge(a,b,c)})})}):d.is_multigraph()?a.forEach(function(a,b){if(goog.isArrayLike(b))throw Error();b.forEach(function(b,c){f[0]=a;f[1]=b;e.has(f)||(goog.object.forEach(c,function(c,e){goog.asserts.assertInstanceof(d,jsnx.classes.MultiGraph);d.add_edge(a,b,e,c)}),f[0]=b,f[1]=a,e.set(f,1))})}):a.forEach(function(a,b){if(goog.isArrayLike(b))throw Error();b.forEach(function(b,c){f[0]=a;f[1]=b;e.has(f)||(goog.object.forEach(c,function(c,e){d.add_edge(a,b,c)}),f[0]=b,f[1]=a,e.set(f,1))})}):
d.is_multigraph()&&!d.is_directed()?a.forEach(function(a,b){if(goog.isArrayLike(b))throw Error();b.forEach(function(b,c){f[0]=a;f[1]=b;e.has(f)||(d.add_edge(a,b,c),f[0]=b,f[1]=a,e.set(f,1))})}):a.forEach(function(a,b){if(goog.isArrayLike(b))throw Error();b.forEach(function(b,c){d.add_edge(a,b,c)})});return d};goog.exportSymbol("jsnx.contrib.convert.from_map_of_maps",jsnx.contrib.convert.from_map_of_maps);goog.structs={};goog.structs.Collection=function(){};goog.structs.getCount=function(a){return"function"==typeof a.getCount?a.getCount():goog.isArrayLike(a)||goog.isString(a)?a.length:goog.object.getCount(a)};goog.structs.getValues=function(a){if("function"==typeof a.getValues)return a.getValues();if(goog.isString(a))return a.split("");if(goog.isArrayLike(a)){for(var b=[],c=a.length,d=0;d<c;d++)b.push(a[d]);return b}return goog.object.getValues(a)};
goog.structs.getKeys=function(a){if("function"==typeof a.getKeys)return a.getKeys();if("function"!=typeof a.getValues){if(goog.isArrayLike(a)||goog.isString(a)){var b=[];a=a.length;for(var c=0;c<a;c++)b.push(c);return b}return goog.object.getKeys(a)}};goog.structs.contains=function(a,b){return"function"==typeof a.contains?a.contains(b):"function"==typeof a.containsValue?a.containsValue(b):goog.isArrayLike(a)||goog.isString(a)?goog.array.contains(a,b):goog.object.containsValue(a,b)};
goog.structs.isEmpty=function(a){return"function"==typeof a.isEmpty?a.isEmpty():goog.isArrayLike(a)||goog.isString(a)?goog.array.isEmpty(a):goog.object.isEmpty(a)};goog.structs.clear=function(a){"function"==typeof a.clear?a.clear():goog.isArrayLike(a)?goog.array.clear(a):goog.object.clear(a)};
goog.structs.forEach=function(a,b,c){if("function"==typeof a.forEach)a.forEach(b,c);else if(goog.isArrayLike(a)||goog.isString(a))goog.array.forEach(a,b,c);else for(var d=goog.structs.getKeys(a),e=goog.structs.getValues(a),f=e.length,g=0;g<f;g++)b.call(c,e[g],d&&d[g],a)};
goog.structs.filter=function(a,b,c){if("function"==typeof a.filter)return a.filter(b,c);if(goog.isArrayLike(a)||goog.isString(a))return goog.array.filter(a,b,c);var d,e=goog.structs.getKeys(a),f=goog.structs.getValues(a),g=f.length;if(e){d={};for(var h=0;h<g;h++)b.call(c,f[h],e[h],a)&&(d[e[h]]=f[h])}else for(d=[],h=0;h<g;h++)b.call(c,f[h],void 0,a)&&d.push(f[h]);return d};
goog.structs.map=function(a,b,c){if("function"==typeof a.map)return a.map(b,c);if(goog.isArrayLike(a)||goog.isString(a))return goog.array.map(a,b,c);var d,e=goog.structs.getKeys(a),f=goog.structs.getValues(a),g=f.length;if(e){d={};for(var h=0;h<g;h++)d[e[h]]=b.call(c,f[h],e[h],a)}else for(d=[],h=0;h<g;h++)d[h]=b.call(c,f[h],void 0,a);return d};
goog.structs.some=function(a,b,c){if("function"==typeof a.some)return a.some(b,c);if(goog.isArrayLike(a)||goog.isString(a))return goog.array.some(a,b,c);for(var d=goog.structs.getKeys(a),e=goog.structs.getValues(a),f=e.length,g=0;g<f;g++)if(b.call(c,e[g],d&&d[g],a))return!0;return!1};
goog.structs.every=function(a,b,c){if("function"==typeof a.every)return a.every(b,c);if(goog.isArrayLike(a)||goog.isString(a))return goog.array.every(a,b,c);for(var d=goog.structs.getKeys(a),e=goog.structs.getValues(a),f=e.length,g=0;g<f;g++)if(!b.call(c,e[g],d&&d[g],a))return!1;return!0};goog.structs.Map=function(a,b){this.map_={};this.keys_=[];this.version_=this.count_=0;var c=arguments.length;if(1<c){if(c%2)throw Error("Uneven number of arguments");for(var d=0;d<c;d+=2)this.set(arguments[d],arguments[d+1])}else a&&this.addAll(a)};goog.structs.Map.prototype.getCount=function(){return this.count_};goog.structs.Map.prototype.getValues=function(){this.cleanupKeysArray_();for(var a=[],b=0;b<this.keys_.length;b++)a.push(this.map_[this.keys_[b]]);return a};
goog.structs.Map.prototype.getKeys=function(){this.cleanupKeysArray_();return this.keys_.concat()};goog.structs.Map.prototype.containsKey=function(a){return goog.structs.Map.hasKey_(this.map_,a)};goog.structs.Map.prototype.containsValue=function(a){for(var b=0;b<this.keys_.length;b++){var c=this.keys_[b];if(goog.structs.Map.hasKey_(this.map_,c)&&this.map_[c]==a)return!0}return!1};
goog.structs.Map.prototype.equals=function(a,b){if(this===a)return!0;if(this.count_!=a.getCount())return!1;var c=b||goog.structs.Map.defaultEquals;this.cleanupKeysArray_();for(var d,e=0;d=this.keys_[e];e++)if(!c(this.get(d),a.get(d)))return!1;return!0};goog.structs.Map.defaultEquals=function(a,b){return a===b};goog.structs.Map.prototype.isEmpty=function(){return 0==this.count_};goog.structs.Map.prototype.clear=function(){this.map_={};this.version_=this.count_=this.keys_.length=0};
goog.structs.Map.prototype.remove=function(a){return goog.structs.Map.hasKey_(this.map_,a)?(delete this.map_[a],this.count_--,this.version_++,this.keys_.length>2*this.count_&&this.cleanupKeysArray_(),!0):!1};
goog.structs.Map.prototype.cleanupKeysArray_=function(){if(this.count_!=this.keys_.length){for(var a=0,b=0;a<this.keys_.length;){var c=this.keys_[a];goog.structs.Map.hasKey_(this.map_,c)&&(this.keys_[b++]=c);a++}this.keys_.length=b}if(this.count_!=this.keys_.length){for(var d={},b=a=0;a<this.keys_.length;)c=this.keys_[a],goog.structs.Map.hasKey_(d,c)||(this.keys_[b++]=c,d[c]=1),a++;this.keys_.length=b}};
goog.structs.Map.prototype.get=function(a,b){return goog.structs.Map.hasKey_(this.map_,a)?this.map_[a]:b};goog.structs.Map.prototype.set=function(a,b){goog.structs.Map.hasKey_(this.map_,a)||(this.count_++,this.keys_.push(a),this.version_++);this.map_[a]=b};goog.structs.Map.prototype.addAll=function(a){var b;a instanceof goog.structs.Map?(b=a.getKeys(),a=a.getValues()):(b=goog.object.getKeys(a),a=goog.object.getValues(a));for(var c=0;c<b.length;c++)this.set(b[c],a[c])};
goog.structs.Map.prototype.clone=function(){return new goog.structs.Map(this)};goog.structs.Map.prototype.transpose=function(){for(var a=new goog.structs.Map,b=0;b<this.keys_.length;b++){var c=this.keys_[b];a.set(this.map_[c],c)}return a};goog.structs.Map.prototype.toObject=function(){this.cleanupKeysArray_();for(var a={},b=0;b<this.keys_.length;b++){var c=this.keys_[b];a[c]=this.map_[c]}return a};goog.structs.Map.prototype.getKeyIterator=function(){return this.__iterator__(!0)};
goog.structs.Map.prototype.getValueIterator=function(){return this.__iterator__(!1)};goog.structs.Map.prototype.__iterator__=function(a){this.cleanupKeysArray_();var b=0,c=this.keys_,d=this.map_,e=this.version_,f=this,g=new goog.iter.Iterator;g.next=function(){for(;;){if(e!=f.version_)throw Error("The map has changed since the iterator was created");if(b>=c.length)throw goog.iter.StopIteration;var g=c[b++];return a?g:d[g]}};return g};
goog.structs.Map.hasKey_=function(a,b){return Object.prototype.hasOwnProperty.call(a,b)};goog.structs.Set=function(a){this.map_=new goog.structs.Map;a&&this.addAll(a)};goog.structs.Set.getKey_=function(a){var b=typeof a;return"object"==b&&a||"function"==b?"o"+goog.getUid(a):b.substr(0,1)+a};goog.structs.Set.prototype.getCount=function(){return this.map_.getCount()};goog.structs.Set.prototype.add=function(a){this.map_.set(goog.structs.Set.getKey_(a),a)};goog.structs.Set.prototype.addAll=function(a){a=goog.structs.getValues(a);for(var b=a.length,c=0;c<b;c++)this.add(a[c])};
goog.structs.Set.prototype.removeAll=function(a){a=goog.structs.getValues(a);for(var b=a.length,c=0;c<b;c++)this.remove(a[c])};goog.structs.Set.prototype.remove=function(a){return this.map_.remove(goog.structs.Set.getKey_(a))};goog.structs.Set.prototype.clear=function(){this.map_.clear()};goog.structs.Set.prototype.isEmpty=function(){return this.map_.isEmpty()};goog.structs.Set.prototype.contains=function(a){return this.map_.containsKey(goog.structs.Set.getKey_(a))};
goog.structs.Set.prototype.containsAll=function(a){return goog.structs.every(a,this.contains,this)};goog.structs.Set.prototype.intersection=function(a){var b=new goog.structs.Set;a=goog.structs.getValues(a);for(var c=0;c<a.length;c++){var d=a[c];this.contains(d)&&b.add(d)}return b};goog.structs.Set.prototype.difference=function(a){var b=this.clone();b.removeAll(a);return b};goog.structs.Set.prototype.getValues=function(){return this.map_.getValues()};goog.structs.Set.prototype.clone=function(){return new goog.structs.Set(this)};
goog.structs.Set.prototype.equals=function(a){return this.getCount()==goog.structs.getCount(a)&&this.isSubsetOf(a)};goog.structs.Set.prototype.isSubsetOf=function(a){var b=goog.structs.getCount(a);if(this.getCount()>b)return!1;!(a instanceof goog.structs.Set)&&5<b&&(a=new goog.structs.Set(a));return goog.structs.every(this,function(b){return goog.structs.contains(a,b)})};goog.structs.Set.prototype.__iterator__=function(a){return this.map_.__iterator__(!1)};jsnx.convert={};jsnx.convert.prep_create_using_=function(a){if(goog.isDefAndNotNull(a))try{a.clear()}catch(b){throw Error("Input graph is not a jsnx graph type");}else a=new jsnx.classes.Graph;return a};
jsnx.convert.to_networkx_graph=function(a,b,c){var d=null;if(a.hasOwnProperty("adj"))try{return d=jsnx.contrib.convert.from_map_of_maps(a.adj,b,a.is_multigraph()),goog.object.containsKey(a,"graph")&&"object"===goog.typeOf(a.graph)&&(d.graph=goog.object.clone(a.graph)),goog.object.containsKey(a,"node")&&a.node instanceof jsnx.contrib.Map&&(d.node=new jsnx.contrib.Map,a.node.forEach(function(a,b){d.node.set(a,goog.object.clone(b))})),d}catch(e){throw e;}if(a instanceof jsnx.contrib.Map)try{return jsnx.contrib.convert.from_map_of_maps(a,
b,c)}catch(f){try{return jsnx.contrib.convert.from_map_of_lists(a,b)}catch(g){throw Error("Input is not known type.");}}if("object"===goog.typeOf(a))try{return jsnx.convert.from_dict_of_dicts(a,b,c)}catch(h){try{return jsnx.convert.from_dict_of_lists(a,b)}catch(k){throw Error("Input is not known type.");}}if(goog.isArrayLike(a))try{return jsnx.convert.from_edgelist(a,b)}catch(l){throw Error("Input is not valid edge list");}return d};goog.exportSymbol("jsnx.convert.to_networkx_graph",jsnx.convert.to_networkx_graph);
goog.exportSymbol("jsnx.to_networkx_graph",jsnx.convert.to_networkx_graph);jsnx.convert.convert_to_undirected=function(a){return a.to_undirected()};goog.exportSymbol("jsnx.convert.convert_to_undirected",jsnx.convert.convert_to_undirected);goog.exportSymbol("jsnx.convert_to_undirected",jsnx.convert.convert_to_undirected);jsnx.convert.convert_to_directed=function(a){return a.to_directed()};goog.exportSymbol("jsnx.convert.convert_to_directed",jsnx.convert.convert_to_directed);
goog.exportSymbol("jsnx.convert_to_undirected",jsnx.convert.convert_to_directed);jsnx.convert.to_dict_of_lists=function(a,b){var c=function(a){return goog.array.contains(goog.asserts.assertArray(b),a)},d={};goog.isDefAndNotNull(b)?b=jsnx.helper.toArray(b):(b=a,c=function(a){return b.has_node(a)});jsnx.helper.forEach(b,function(b){d[b]=goog.array.filter(a.neighbors(b),c)});return d};goog.exportSymbol("jsnx.convert.to_dict_of_lists",jsnx.convert.to_dict_of_lists);
goog.exportSymbol("jsnx.to_dict_of_lists",jsnx.convert.to_dict_of_lists);
jsnx.convert.from_dict_of_lists=function(a,b){var c=jsnx.convert.prep_create_using_(b);c.add_nodes_from(goog.iter.map(jsnx.helper.iteritems(a),function(a){return isNaN(a[0])?a[0]:+a[0]}));if(c.is_multigraph()&&!c.is_directed()){var d={};goog.object.forEach(a,function(a,b){b=isNaN(b)?b:+b;goog.array.forEach(a,function(a){goog.object.containsKey(d,a)||c.add_edge(b,a)});d[b]=1})}else{var e=[];goog.object.forEach(a,function(a,b){b=isNaN(b)?b:+b;goog.array.forEach(a,function(a){e.push([b,a])})});c.add_edges_from(e)}return c};
goog.exportSymbol("jsnx.convert.from_dict_of_lists",jsnx.convert.from_dict_of_lists);
jsnx.convert.to_dict_of_dicts=function(a,b,c){var d={};goog.isDefAndNotNull(b)?(b=jsnx.helper.toArray(b),goog.isDefAndNotNull(c)?goog.array.forEach(b,function(e){d[e]={};goog.object.forEach(a.get(e),function(a,g){goog.asserts.assertArray(b);goog.array.contains(b,g)&&(d[e][g]=c)})}):goog.array.forEach(b,function(c){d[c]={};goog.object.forEach(a.get(c),function(a,g){goog.asserts.assertArray(b);goog.array.contains(b,g)&&(d[c][g]=a)})})):goog.isDefAndNotNull(c)?goog.iter.forEach(a.adjacency_iter(),function(a,
b){d[b]=goog.object.map(a,function(){return c})}):goog.iter.forEach(a.adjacency_iter(),function(a,b){d[b]=goog.object.clone(a)});return d};goog.exportSymbol("jsnx.convert.to_dict_of_dicts",jsnx.convert.to_dict_of_dicts);
jsnx.convert.from_dict_of_dicts=function(a,b,c){var d=jsnx.convert.prep_create_using_(b),e,f;d.add_nodes_from(goog.iter.map(jsnx.helper.iteritems(a),function(a){return isNaN(a[0])?a[0]:+a[0]}));c?d.is_directed()?(d.is_multigraph()?(e=[],goog.object.forEach(a,function(a,b){if(goog.isArrayLike(a))throw Error();b=isNaN(b)?b:+b;goog.object.forEach(a,function(a,c){c=isNaN(c)?c:+c;goog.object.forEach(a,function(a,d){e.push([b,c,d,a])})})})):(e=[],goog.object.forEach(a,function(a,b){if(goog.isArrayLike(a))throw Error();
b=isNaN(b)?b:+b;goog.object.forEach(a,function(a,c){c=isNaN(c)?c:+c;goog.object.forEach(a,function(a,d){e.push([b,c,a])})})})),d.add_edges_from(e)):d.is_multigraph()?(f=new goog.structs.Set,goog.object.forEach(a,function(a,b){if(goog.isArrayLike(a))throw Error();b=isNaN(b)?b:+b;goog.object.forEach(a,function(a,c){c=isNaN(c)?c:+c;f.contains([b,c].toString())||(e=[],goog.object.forEach(a,function(a,d){e.push([b,c,d,a])}),d.add_edges_from(e),f.add([c,b].toString()))})})):(f=new goog.structs.Set,goog.object.forEach(a,
function(a,b){if(goog.isArrayLike(a))throw Error();b=isNaN(b)?b:+b;goog.object.forEach(a,function(a,c){c=isNaN(c)?c:+c;f.contains([b,c].toString())||(e=[],goog.object.forEach(a,function(a,d){e.push([b,c,a])}),d.add_edges_from(e),f.add([c,b].toString()))})})):d.is_multigraph()&&!d.is_directed()?(f=new goog.structs.Set,goog.object.forEach(a,function(a,b){if(goog.isArrayLike(a))throw Error();b=isNaN(b)?b:+b;goog.object.forEach(a,function(a,c){c=isNaN(c)?c:+c;f.contains([b,c].toString())||(d.add_edge(b,
c,a),f.add([c,b].toString()))})})):(e=[],goog.object.forEach(a,function(a,b){if(goog.isArrayLike(a))throw Error();b=isNaN(b)?b:+b;goog.object.forEach(a,function(a,c){c=isNaN(c)?c:+c;e.push([b,c,a])})}),d.add_edges_from(e));return d};goog.exportSymbol("jsnx.convert.from_dict_of_dicts",jsnx.convert.from_dict_of_dicts);jsnx.convert.to_edgelist=function(a,b){return goog.isDefAndNotNull(b)?a.edges(b,!0):a.edges(null,!0)};goog.exportSymbol("jsnx.convert.to_edgelist",jsnx.convert.to_edgelist);
jsnx.convert.from_edgelist=function(a,b){var c=jsnx.convert.prep_create_using_(b);c.add_edges_from(a);return c};goog.exportSymbol("jsnx.convert.from_edgelist",jsnx.convert.from_edgelist);goog.json={};goog.json.USE_NATIVE_JSON=!1;goog.json.isValid_=function(a){return/^\s*$/.test(a)?!1:/^[\],:{}\s\u2028\u2029]*$/.test(a.replace(/\\["\\\/bfnrtu]/g,"@").replace(/"[^"\\\n\r\u2028\u2029\x00-\x08\x0a-\x1f]*"|true|false|null|-?\d+(?:\.\d*)?(?:[eE][+\-]?\d+)?/g,"]").replace(/(?:^|:|,)(?:[\s\u2028\u2029]*\[)+/g,""))};
goog.json.parse=goog.json.USE_NATIVE_JSON?goog.global.JSON.parse:function(a){a=String(a);if(goog.json.isValid_(a))try{return eval("("+a+")")}catch(b){}throw Error("Invalid JSON string: "+a);};goog.json.unsafeParse=goog.json.USE_NATIVE_JSON?goog.global.JSON.parse:function(a){return eval("("+a+")")};goog.json.serialize=goog.json.USE_NATIVE_JSON?goog.global.JSON.stringify:function(a,b){return(new goog.json.Serializer(b)).serialize(a)};goog.json.Serializer=function(a){this.replacer_=a};
goog.json.Serializer.prototype.serialize=function(a){var b=[];this.serialize_(a,b);return b.join("")};
goog.json.Serializer.prototype.serialize_=function(a,b){switch(typeof a){case "string":this.serializeString_(a,b);break;case "number":this.serializeNumber_(a,b);break;case "boolean":b.push(a);break;case "undefined":b.push("null");break;case "object":if(null==a){b.push("null");break}if(goog.isArray(a)){this.serializeArray(a,b);break}this.serializeObject_(a,b);break;case "function":break;default:throw Error("Unknown type: "+typeof a);}};
goog.json.Serializer.charToJsonCharCache_={'"':'\\"',"\\":"\\\\","/":"\\/","\b":"\\b","\f":"\\f","\n":"\\n","\r":"\\r","\t":"\\t","\x0B":"\\u000b"};goog.json.Serializer.charsToReplace_=/\uffff/.test("\uffff")?/[\\\"\x00-\x1f\x7f-\uffff]/g:/[\\\"\x00-\x1f\x7f-\xff]/g;
goog.json.Serializer.prototype.serializeString_=function(a,b){b.push('"',a.replace(goog.json.Serializer.charsToReplace_,function(a){if(a in goog.json.Serializer.charToJsonCharCache_)return goog.json.Serializer.charToJsonCharCache_[a];var b=a.charCodeAt(0),e="\\u";16>b?e+="000":256>b?e+="00":4096>b&&(e+="0");return goog.json.Serializer.charToJsonCharCache_[a]=e+b.toString(16)}),'"')};goog.json.Serializer.prototype.serializeNumber_=function(a,b){b.push(isFinite(a)&&!isNaN(a)?a:"null")};
goog.json.Serializer.prototype.serializeArray=function(a,b){var c=a.length;b.push("[");for(var d="",e=0;e<c;e++)b.push(d),d=a[e],this.serialize_(this.replacer_?this.replacer_.call(a,String(e),d):d,b),d=",";b.push("]")};
goog.json.Serializer.prototype.serializeObject_=function(a,b){b.push("{");var c="",d;for(d in a)if(Object.prototype.hasOwnProperty.call(a,d)){var e=a[d];"function"!=typeof e&&(b.push(c),this.serializeString_(d,b),b.push(":"),this.serialize_(this.replacer_?this.replacer_.call(a,d,e):e,b),c=",")}b.push("}")};jsnx.classes={};jsnx.classes.Graph=function(a,b){if(!(this instanceof jsnx.classes.Graph))return new jsnx.classes.Graph(a,b);this.graph={};this.node=new jsnx.contrib.Map;this.adj=new jsnx.contrib.Map;goog.isDefAndNotNull(a)&&jsnx.convert.to_networkx_graph(a,this);goog.object.extend(this.graph,b||{});this.edge=this.adj};goog.exportSymbol("jsnx.classes.Graph",jsnx.classes.Graph);goog.exportSymbol("jsnx.Graph",jsnx.classes.Graph);jsnx.classes.Graph.__name__="Graph";
jsnx.classes.Graph.prototype.graph=null;goog.exportProperty(jsnx.classes.Graph.prototype,"graph",jsnx.classes.Graph.prototype.graph);jsnx.classes.Graph.prototype.node=null;goog.exportProperty(jsnx.classes.Graph.prototype,"node",jsnx.classes.Graph.prototype.node);jsnx.classes.Graph.prototype.adj=null;goog.exportProperty(jsnx.classes.Graph.prototype,"adj",jsnx.classes.Graph.prototype.adj);jsnx.classes.Graph.prototype.edge=null;goog.exportProperty(jsnx.classes.Graph.prototype,"edge",jsnx.classes.Graph.prototype.edge);
jsnx.classes.Graph.prototype.name=function(a){if(goog.isDef(a))this.graph.name=a.toString();else return this.graph.name||""};goog.exportProperty(jsnx.classes.Graph.prototype,"name",jsnx.classes.Graph.prototype.name);jsnx.classes.Graph.prototype.toString=function(){return this.name()};goog.exportProperty(jsnx.classes.Graph.prototype,"toString",jsnx.classes.Graph.prototype.toString);
jsnx.classes.Graph.prototype.get=function(a){try{return this.adj.get(a)}catch(b){if(!(b instanceof jsnx.exception.KeyError))throw b;throw new jsnx.exception.KeyError("Graph does not contain node "+a+".");}};goog.exportProperty(jsnx.classes.Graph.prototype,"get",jsnx.classes.Graph.prototype.get);
jsnx.classes.Graph.prototype.add_node=function(a,b){goog.isDefAndNotNull(b)||(b={});if("object"!==goog.typeOf(b))throw new jsnx.exception.JSNetworkXError("The attr_dict argument must be an object.");this.adj.has(a)?goog.object.extend(this.node.get(a),b):(this.adj.set(a,new jsnx.contrib.Map),this.node.set(a,b))};goog.exportProperty(jsnx.classes.Graph.prototype,"add_node",jsnx.classes.Graph.prototype.add_node);
jsnx.classes.Graph.prototype.add_nodes_from=function(a,b){goog.isDefAndNotNull(b)||(b={});jsnx.helper.forEach(a,function(a){if(goog.isArray(a)&&2===a.length&&goog.isObject(a[1])){var d=a[0];a=a[1];if(this.adj.has(d))d=this.node.get(d),goog.object.extend(d,b,a);else{this.adj.set(d,new jsnx.contrib.Map);var e=goog.object.clone(b);goog.object.extend(e,a);this.node.set(d,e)}}else this.adj.has(a)?goog.object.extend(this.node.get(a),b):(this.adj.set(a,new jsnx.contrib.Map),this.node.set(a,goog.object.clone(b)))},
this)};goog.exportProperty(jsnx.classes.Graph.prototype,"add_nodes_from",jsnx.classes.Graph.prototype.add_nodes_from);jsnx.classes.Graph.prototype.remove_node=function(a){var b=this.adj;try{var c=this.adj.get(a).keys();this.node.remove(a);goog.array.forEach(c,function(c){b.get(c).remove(a)});b.remove(a)}catch(d){if(!(d instanceof jsnx.exception.KeyError))throw d;throw new jsnx.exception.JSNetworkXError(goog.string.subs("The node %s is not in the graph",goog.json.serialize(a)));}};
goog.exportProperty(jsnx.classes.Graph.prototype,"remove_node",jsnx.classes.Graph.prototype.remove_node);jsnx.classes.Graph.prototype.remove_nodes_from=function(a){var b=this.adj;jsnx.helper.forEach(a,function(a){try{this.node.remove(a),b.get(a).forEach(function(d){b.get(d).remove(a)}),b.remove(a)}catch(d){if(!(d instanceof jsnx.exception.KeyError))throw d;}},this)};goog.exportProperty(jsnx.classes.Graph.prototype,"remove_nodes_from",jsnx.classes.Graph.prototype.remove_nodes_from);
jsnx.classes.Graph.prototype.nodes_iter=function(a){return a?goog.iter.toIterator(this.node):goog.iter.toIterator(this.adj.keys())};goog.exportProperty(jsnx.classes.Graph.prototype,"nodes_iter",jsnx.classes.Graph.prototype.nodes_iter);jsnx.classes.Graph.prototype.nodes=function(a){return a?this.node.items():this.node.keys()};goog.exportProperty(jsnx.classes.Graph.prototype,"nodes",jsnx.classes.Graph.prototype.nodes);jsnx.classes.Graph.prototype.number_of_nodes=function(){return this.adj.count()};
goog.exportProperty(jsnx.classes.Graph.prototype,"number_of_nodes",jsnx.classes.Graph.prototype.number_of_nodes);jsnx.classes.Graph.prototype.order=function(){return this.adj.count()};goog.exportProperty(jsnx.classes.Graph.prototype,"order",jsnx.classes.Graph.prototype.order);jsnx.classes.Graph.prototype.has_node=function(a){try{return this.adj.has(a)}catch(b){if(b instanceof TypeError)return!1;throw b;}};goog.exportProperty(jsnx.classes.Graph.prototype,"has_node",jsnx.classes.Graph.prototype.has_node);
jsnx.classes.Graph.prototype.add_edge=function(a,b,c){c=c||{};if("object"!==goog.typeOf(c))throw new jsnx.exception.JSNetworkXError("The attr_dict argument must be an object.");this.adj.has(a)||(this.adj.set(a,new jsnx.contrib.Map),this.node.set(a,{}));this.adj.has(b)||(this.adj.set(b,new jsnx.contrib.Map),this.node.set(b,{}));var d=this.adj.get(a).get(b,{});goog.object.extend(d,c);this.adj.get(a).set(b,d);this.adj.get(b).set(a,d)};goog.exportProperty(jsnx.classes.Graph.prototype,"add_edge",jsnx.classes.Graph.prototype.add_edge);
jsnx.classes.Graph.prototype.add_edges_from=function(a,b){b=b||{};if("object"!==goog.typeOf(b))throw new jsnx.exception.JSNetworkXError("The attr_dict argument must be an object.");jsnx.helper.forEach(a,function(a){var d=jsnx.helper.len(a),e;if(3===d)d=a[0],e=a[1],a=a[2];else if(2===d)d=a[0],e=a[1],a={};else throw new jsnx.exception.JSNetworkXError(goog.string.subs("Edge tuple %s must be a 2-tuple or 3-tuple.",goog.json.serialize(a)));this.adj.has(d)||(this.adj.set(d,new jsnx.contrib.Map),this.node.set(d,
{}));this.adj.has(e)||(this.adj.set(e,new jsnx.contrib.Map),this.node.set(e,{}));var f=this.adj.get(d).get(e,{});goog.object.extend(f,b,a);this.adj.get(d).set(e,f);this.adj.get(e).set(d,f)},this)};goog.exportProperty(jsnx.classes.Graph.prototype,"add_edges_from",jsnx.classes.Graph.prototype.add_edges_from);
jsnx.classes.Graph.prototype.add_weighted_edges_from=function(a,b,c){c=c||{};goog.isString(b)||(c=b,b="weight");this.add_edges_from(jsnx.helper.map(a,function(a){var c={};c[b]=a[2];if(!goog.isDef(c[b]))throw new TypeError("Values must consist of three elements: "+goog.json.serialize(a));return[a[0],a[1],c]}),c)};goog.exportProperty(jsnx.classes.Graph.prototype,"add_weighted_edges_from",jsnx.classes.Graph.prototype.add_weighted_edges_from);
jsnx.classes.Graph.prototype.remove_edge=function(a,b){try{this.adj.get(a).remove(b),jsnx.contrib.misc.get_hash(a)!==jsnx.contrib.misc.get_hash(b)&&this.adj.get(b).remove(a)}catch(c){if(c instanceof jsnx.exception.KeyError)throw new jsnx.exception.JSNetworkXError(goog.string.subs("The edge %s-%s is not in the graph",goog.json.serialize(a),goog.json.serialize(b)));throw c;}};goog.exportProperty(jsnx.classes.Graph.prototype,"remove_edge",jsnx.classes.Graph.prototype.remove_edge);
jsnx.classes.Graph.prototype.remove_edges_from=function(a){jsnx.helper.forEach(a,function(a){var c=a[0];a=a[1];this.adj.has(c)&&this.adj.get(c).has(a)&&(this.adj.get(c).remove(a),jsnx.contrib.misc.get_hash(c)!==jsnx.contrib.misc.get_hash(a)&&this.adj.get(a).remove(c))},this)};goog.exportProperty(jsnx.classes.Graph.prototype,"remove_edges_from",jsnx.classes.Graph.prototype.remove_edges_from);jsnx.classes.Graph.prototype.has_edge=function(a,b){return this.adj.has(a)&&this.adj.get(a).has(b)};
goog.exportProperty(jsnx.classes.Graph.prototype,"has_edge",jsnx.classes.Graph.prototype.has_edge);jsnx.classes.Graph.prototype.neighbors=function(a){try{return this.adj.get(a).keys()}catch(b){if(b instanceof jsnx.exception.KeyError)throw new jsnx.exception.JSNetworkXError(goog.string.subs("The node %s is not in the graph.",goog.json.serialize(a)));throw b;}};goog.exportProperty(jsnx.classes.Graph.prototype,"neighbors",jsnx.classes.Graph.prototype.neighbors);
jsnx.classes.Graph.prototype.neighbors_iter=function(a){try{return goog.iter.toIterator(this.adj.get(a).keys())}catch(b){if(b instanceof jsnx.exception.KeyError)throw new jsnx.exception.JSNetworkXError(goog.string.subs("The node %s is not in the graph.",goog.json.serialize(a)));throw b;}};goog.exportProperty(jsnx.classes.Graph.prototype,"neighbors_iter",jsnx.classes.Graph.prototype.neighbors_iter);jsnx.classes.Graph.prototype.edges=function(a,b){return goog.iter.toArray(this.edges_iter(a,b))};
goog.exportProperty(jsnx.classes.Graph.prototype,"edges",jsnx.classes.Graph.prototype.edges);
jsnx.classes.Graph.prototype.edges_iter=function(a,b){goog.isBoolean(a)&&(b=a,a=null);var c=new jsnx.contrib.Map,d,e;d=goog.isDefAndNotNull(a)?goog.iter.map(this.nbunch_iter(a),function(a){return[a,this.adj.get(a)]},this):goog.iter.toIterator(this.adj);return b?jsnx.helper.nested_chain(d,function(a){e=a[0];var b=new goog.iter.Iterator,d=goog.iter.toIterator(a[1]);b.next=function(){try{return d.next()}catch(a){throw a===goog.iter.StopIteration&&c.set(e,1),a;}};return b},function(a){if(!c.has(a[0]))return[e,
a[0],a[1]]}):jsnx.helper.nested_chain(d,function(a){e=a[0];var b=new goog.iter.Iterator,d=goog.iter.toIterator(a[1]);b.next=function(){try{return d.next()}catch(a){throw a===goog.iter.StopIteration&&c.set(e,1),a;}};return b},function(a){if(!c.has(a[0]))return[e,a[0]]})};goog.exportProperty(jsnx.classes.Graph.prototype,"edges_iter",jsnx.classes.Graph.prototype.edges_iter);
jsnx.classes.Graph.prototype.get_edge_data=function(a,b,c){try{return this.adj.get(a).get(b)}catch(d){if(d instanceof jsnx.exception.KeyError)return c;throw d;}};goog.exportProperty(jsnx.classes.Graph.prototype,"get_edge_data",jsnx.classes.Graph.prototype.get_edge_data);jsnx.classes.Graph.prototype.adjacency_list=function(){return goog.iter.toArray(goog.iter.map(this.adjacency_iter(),function(a){return a[1].keys()}))};goog.exportProperty(jsnx.classes.Graph.prototype,"adjacency_list",jsnx.classes.Graph.prototype.adjacency_list);
jsnx.classes.Graph.prototype.adjacency_iter=function(){return goog.iter.toIterator(this.adj)};goog.exportProperty(jsnx.classes.Graph.prototype,"adjacency_iter",jsnx.classes.Graph.prototype.adjacency_iter);jsnx.classes.Graph.prototype.degree=function(a,b){return goog.isDefAndNotNull(a)&&this.has_node(a)?this.degree_iter(a,b).next()[1]:new jsnx.contrib.Map(this.degree_iter(a,b))};goog.exportProperty(jsnx.classes.Graph.prototype,"degree",jsnx.classes.Graph.prototype.degree);
jsnx.classes.Graph.prototype.degree_iter=function(a,b){var c;c=goog.isDefAndNotNull(a)?goog.iter.map(this.nbunch_iter(a),function(a){return[a,this.adj.get(a)]},this):goog.iter.toIterator(this.adj);return b?goog.iter.map(c,function(a){var c=a[0],f=a[1],g=0;f.forEach(function(a,c){g+=+goog.object.get(c,goog.asserts.assert(b),1)});g+=+(f.has(c)&&goog.object.get(f.get(c),goog.asserts.assert(b),1));a[1]=g;return a}):goog.iter.map(c,function(a){a[1]=a[1].count()+ +a[1].has(a[0]);return a})};
goog.exportProperty(jsnx.classes.Graph.prototype,"degree_iter",jsnx.classes.Graph.prototype.degree_iter);jsnx.classes.Graph.prototype.clear=function(){this.name("");this.adj.clear();this.node.clear();goog.object.clear(this.graph)};goog.exportProperty(jsnx.classes.Graph.prototype,"clear",jsnx.classes.Graph.prototype.clear);jsnx.classes.Graph.prototype.copy=function(){return jsnx.helper.deepcopy_instance(this)};goog.exportProperty(jsnx.classes.Graph.prototype,"copy",jsnx.classes.Graph.prototype.copy);
jsnx.classes.Graph.prototype.is_multigraph=function(){return!1};goog.exportProperty(jsnx.classes.Graph.prototype,"is_multigraph",jsnx.classes.Graph.prototype.is_multigraph);jsnx.classes.Graph.prototype.is_directed=function(){return!1};goog.exportProperty(jsnx.classes.Graph.prototype,"is_directed",jsnx.classes.Graph.prototype.is_directed);
jsnx.classes.Graph.prototype.to_directed=function(){var a=new jsnx.classes.DiGraph;a.name(this.name());a.add_nodes_from(this);a.add_edges_from(function(){var a;return jsnx.helper.nested_chain(this.adjacency_iter(),function(c){a=c[0];return goog.iter.toIterator(c[1])},function(c){c[2]=jsnx.helper.deepcopy(c[1]);c[1]=c[0];c[0]=a;return c})}.call(this));a.graph=jsnx.helper.deepcopy(this.graph);a.node=jsnx.helper.deepcopy(this.node);return a};
goog.exportProperty(jsnx.classes.Graph.prototype,"to_directed",jsnx.classes.Graph.prototype.to_directed);jsnx.classes.Graph.prototype.to_undirected=function(){return jsnx.helper.deepcopy_instance(this)};goog.exportProperty(jsnx.classes.Graph.prototype,"to_undirected",jsnx.classes.Graph.prototype.to_undirected);
jsnx.classes.Graph.prototype.subgraph=function(a){a=this.nbunch_iter(a);var b=new this.constructor,c=b.adj,d=this.adj;goog.iter.forEach(a,function(a){var b=new jsnx.contrib.Map;c.set(a,b);d.get(a).forEach(function(d,h){c.has(d)&&(b.set(d,h),c.get(d).set(a,h))})});jsnx.helper.forEach(b,function(a){b.node.set(a,this.node.get(a))},this);b.graph=this.graph;return b};goog.exportProperty(jsnx.classes.Graph.prototype,"subgraph",jsnx.classes.Graph.prototype.subgraph);
jsnx.classes.Graph.prototype.nodes_with_selfloops=function(){return goog.array.map(goog.array.filter(this.adj.items(),function(a){return a[1].has(a[0])}),function(a){return a[0]})};goog.exportProperty(jsnx.classes.Graph.prototype,"nodes_with_selfloops",jsnx.classes.Graph.prototype.nodes_with_selfloops);
jsnx.classes.Graph.prototype.selfloop_edges=function(a){return a?goog.array.map(goog.array.filter(this.adj.items(),function(a){return a[1].has(a[0])}),function(a){a[2]=a[1].get(a[0]);a[1]=a[0];return a}):goog.array.map(goog.array.filter(this.adj.items(),function(a){return a[1].has(a[0])}),function(a){a[1]=a[0];return a})};goog.exportProperty(jsnx.classes.Graph.prototype,"selfloop_edges",jsnx.classes.Graph.prototype.selfloop_edges);jsnx.classes.Graph.prototype.number_of_selfloops=function(){return this.selfloop_edges().length};
goog.exportProperty(jsnx.classes.Graph.prototype,"number_of_selfloops",jsnx.classes.Graph.prototype.number_of_selfloops);jsnx.classes.Graph.prototype.size=function(a){var b=goog.math.sum.apply(null,goog.asserts.assertObject(this.degree(null,a)).values())/2;return goog.isDefAndNotNull(a)?b:Math.floor(b)};goog.exportProperty(jsnx.classes.Graph.prototype,"size",jsnx.classes.Graph.prototype.size);
jsnx.classes.Graph.prototype.number_of_edges=function(a,b){return goog.isDefAndNotNull(a)?this.adj.get(a).has(b)?1:0:Math.floor(this.size())};goog.exportProperty(jsnx.classes.Graph.prototype,"number_of_edges",jsnx.classes.Graph.prototype.number_of_edges);jsnx.classes.Graph.prototype.add_star=function(a,b){var c=jsnx.helper.toArray(a),d=c[0],c=goog.iter.map(goog.array.slice(c,1),function(a){return[d,a]});this.add_edges_from(c,b)};goog.exportProperty(jsnx.classes.Graph.prototype,"add_star",jsnx.classes.Graph.prototype.add_star);
jsnx.classes.Graph.prototype.add_path=function(a,b){var c=jsnx.helper.toArray(a),c=goog.array.zip(goog.array.slice(c,0,c.length-1),goog.array.slice(c,1));this.add_edges_from(c,b)};goog.exportProperty(jsnx.classes.Graph.prototype,"add_path",jsnx.classes.Graph.prototype.add_path);jsnx.classes.Graph.prototype.add_cycle=function(a,b){var c=jsnx.helper.toArray(a),c=goog.array.zip(c,goog.array.concat(goog.array.slice(c,1),[c[0]]));this.add_edges_from(c,b)};
goog.exportProperty(jsnx.classes.Graph.prototype,"add_cycle",jsnx.classes.Graph.prototype.add_cycle);
jsnx.classes.Graph.prototype.nbunch_iter=function(a){return goog.isDefAndNotNull(a)?this.has_node(a)?goog.iter.toIterator([a]):function(a,c){var d=new goog.iter.Iterator,e=jsnx.helper.nested_chain(a,function(a){if(c.has(a))return a});d.next=function(){try{return e.next()}catch(a){if(a instanceof TypeError)throw new jsnx.exception.JSNetworkXError("nbunch is not a node or a sequence of nodes");throw a;}};return d}(a,this.adj):goog.iter.toIterator(this.adj.keys())};
goog.exportProperty(jsnx.classes.Graph.prototype,"nbunch_iter",jsnx.classes.Graph.prototype.nbunch_iter);jsnx.classes.DiGraph=function(a,b){if(!(this instanceof jsnx.classes.DiGraph))return new jsnx.classes.DiGraph(a,b);this.graph={};this.node=new jsnx.contrib.Map;this.adj=new jsnx.contrib.Map;this.pred=new jsnx.contrib.Map;this.succ=this.adj;goog.isDefAndNotNull(a)&&jsnx.convert.to_networkx_graph(a,this);goog.object.extend(this.graph,b||{});this.edge=this.adj};goog.exportSymbol("jsnx.classes.DiGraph",jsnx.classes.DiGraph);goog.exportSymbol("jsnx.DiGraph",jsnx.classes.DiGraph);
goog.inherits(jsnx.classes.DiGraph,jsnx.classes.Graph);jsnx.classes.DiGraph.__name__="DiGraph";jsnx.classes.DiGraph.prototype.pred=null;goog.exportProperty(jsnx.classes.DiGraph.prototype,"pred",jsnx.classes.DiGraph.prototype.pred);jsnx.classes.DiGraph.prototype.succ=null;goog.exportProperty(jsnx.classes.DiGraph.prototype,"succ",jsnx.classes.DiGraph.prototype.succ);
jsnx.classes.DiGraph.prototype.add_node=function(a,b){goog.isDefAndNotNull(b)||(b={});if("object"!==goog.typeOf(b))throw new jsnx.exception.JSNetworkXError("The attr_dict argument must be an object.");this.succ.has(a)?goog.object.extend(this.node.get(a),b):(this.succ.set(a,new jsnx.contrib.Map),this.pred.set(a,new jsnx.contrib.Map),this.node.set(a,b))};goog.exportProperty(jsnx.classes.DiGraph.prototype,"add_node",jsnx.classes.DiGraph.prototype.add_node);
jsnx.classes.DiGraph.prototype.add_nodes_from=function(a,b){var c,d,e,f,g;goog.isDefAndNotNull(b)||(b={});jsnx.helper.forEach(jsnx.helper.iter(a),function(a){c=!this.succ.has(a);goog.isArray(a)&&2===a.length&&goog.isObject(a[1])?(d=a[0],e=a[1],this.succ.has(d)?(g=this.node.get(d),goog.object.extend(g,b,e)):(this.succ.set(d,new jsnx.contrib.Map),this.pred.set(d,new jsnx.contrib.Map),f=goog.object.clone(b),goog.object.extend(f,e),this.node.set(d,f))):c?(this.succ.set(a,new jsnx.contrib.Map),this.pred.set(a,
new jsnx.contrib.Map),this.node.set(a,goog.object.clone(b))):goog.object.extend(this.node.get(a),b)},this)};goog.exportProperty(jsnx.classes.DiGraph.prototype,"add_nodes_from",jsnx.classes.DiGraph.prototype.add_nodes_from);
jsnx.classes.DiGraph.prototype.remove_node=function(a){var b;try{b=this.succ.get(a),this.node.remove(a)}catch(c){if(!(c instanceof jsnx.exception.KeyError))throw c;throw new jsnx.exception.JSNetworkXError(goog.string.subs("The node %s is not in the graph",goog.json.serialize(a)));}b.forEach(function(b){this.pred.get(b).remove(a)},this);this.succ.remove(a);this.pred.get(a).forEach(function(b){this.succ.get(b).remove(a)},this);this.pred.remove(a)};
goog.exportProperty(jsnx.classes.DiGraph.prototype,"remove_node",jsnx.classes.DiGraph.prototype.remove_node);jsnx.classes.DiGraph.prototype.remove_nodes_from=function(a){var b;jsnx.helper.forEach(a,function(a){this.succ.has(a)&&(b=this.succ.get(a),this.node.remove(a),b.forEach(function(b){this.pred.get(b).remove(a)},this),this.succ.remove(a),this.pred.get(a).forEach(function(b){this.succ.get(b).remove(a)},this),this.pred.remove(a))},this)};
goog.exportProperty(jsnx.classes.DiGraph.prototype,"remove_nodes_from",jsnx.classes.DiGraph.prototype.remove_nodes_from);
jsnx.classes.DiGraph.prototype.add_edge=function(a,b,c){c=c||{};if("object"!==goog.typeOf(c))throw new jsnx.exception.JSNetworkXError("The attr_dict argument must be an object.");this.succ.has(a)||(this.succ.set(a,new jsnx.contrib.Map),this.pred.set(a,new jsnx.contrib.Map),this.node.set(a,{}));this.succ.has(b)||(this.succ.set(b,new jsnx.contrib.Map),this.pred.set(b,new jsnx.contrib.Map),this.node.set(b,{}));var d=this.adj.get(a).get(b,{});goog.object.extend(d,c);this.succ.get(a).set(b,d);this.pred.get(b).set(a,
d)};goog.exportProperty(jsnx.classes.DiGraph.prototype,"add_edge",jsnx.classes.DiGraph.prototype.add_edge);
jsnx.classes.DiGraph.prototype.add_edges_from=function(a,b){b=b||{};if("object"!==goog.typeOf(b))throw new jsnx.exception.JSNetworkXError("The attr_dict argument must be an object.");jsnx.helper.forEach(a,function(a){var d=jsnx.helper.len(a),e;if(3===d)d=a[0],e=a[1],a=a[2];else if(2===d)d=a[0],e=a[1],a={};else throw new jsnx.exception.JSNetworkXError("Edge tuple "+a.toString()+" must be a 2-tuple or 3-tuple.");this.succ.has(d)||(this.succ.set(d,new jsnx.contrib.Map),this.pred.set(d,new jsnx.contrib.Map),
this.node.set(d,{}));this.succ.has(e)||(this.succ.set(e,new jsnx.contrib.Map),this.pred.set(e,new jsnx.contrib.Map),this.node.set(e,{}));var f=this.adj.get(d).get(e,{});goog.object.extend(f,b,a);this.succ.get(d).set(e,f);this.pred.get(e).set(d,f)},this)};goog.exportProperty(jsnx.classes.DiGraph.prototype,"add_edges_from",jsnx.classes.DiGraph.prototype.add_edges_from);
jsnx.classes.DiGraph.prototype.remove_edge=function(a,b){try{this.succ.get(a).remove(b),this.pred.get(b).remove(a)}catch(c){if(c instanceof TypeError)throw new jsnx.exception.JSNetworkXError(goog.string.subs("The edge %s-%s is not in the graph",goog.json.serialize(a),goog.json.serialize(b)));throw c;}};goog.exportProperty(jsnx.classes.DiGraph.prototype,"remove_edge",jsnx.classes.DiGraph.prototype.remove_edge);
jsnx.classes.DiGraph.prototype.remove_edges_from=function(a){jsnx.helper.forEach(a,function(a){var c=a[0];a=a[1];try{this.succ.get(c).remove(a),this.pred.get(a).remove(c)}catch(d){}},this)};goog.exportProperty(jsnx.classes.DiGraph.prototype,"remove_edges_from",jsnx.classes.DiGraph.prototype.remove_edges_from);jsnx.classes.DiGraph.prototype.has_successor=function(a,b){return this.succ.has(a)&&this.succ.get(a).has(b)};goog.exportProperty(jsnx.classes.DiGraph.prototype,"has_successor",jsnx.classes.DiGraph.prototype.has_successor);
jsnx.classes.DiGraph.prototype.has_predecessor=function(a,b){return this.pred.has(a)&&this.pred.get(a).has(b)};goog.exportProperty(jsnx.classes.DiGraph.prototype,"has_predecessor",jsnx.classes.DiGraph.prototype.has_predecessor);jsnx.classes.DiGraph.prototype.successors_iter=function(a){try{return goog.iter.map(this.succ.get(a),function(a){return a[0]})}catch(b){if(!(b instanceof jsnx.exception.KeyError))throw b;throw new jsnx.exception.JSNetworkXError("The node "+a+" is not in the digraph.");}};
goog.exportProperty(jsnx.classes.DiGraph.prototype,"successors_iter",jsnx.classes.DiGraph.prototype.successors_iter);jsnx.classes.DiGraph.prototype.predecessors_iter=function(a){try{return goog.iter.map(this.pred.get(a),function(a){return a[0]})}catch(b){if(!(b instanceof jsnx.exception.KeyError))throw b;throw new jsnx.exception.JSNetworkXError("The node "+a+" is not in the digraph.");}};goog.exportProperty(jsnx.classes.DiGraph.prototype,"predecessors_iter",jsnx.classes.DiGraph.prototype.predecessors_iter);
jsnx.classes.DiGraph.prototype.successors=function(a){try{return this.succ.get(a).keys()}catch(b){if(!(b instanceof jsnx.exception.KeyError))throw b;throw new jsnx.exception.JSNetworkXError("The node "+a+" is not in the digraph.");}};goog.exportProperty(jsnx.classes.DiGraph.prototype,"successors",jsnx.classes.DiGraph.prototype.successors);
jsnx.classes.DiGraph.prototype.predecessors=function(a){try{return this.pred.get(a).keys()}catch(b){if(!(b instanceof jsnx.exception.KeyError))throw b;throw new jsnx.exception.JSNetworkXError("The node "+a+" is not in the digraph.");}};goog.exportProperty(jsnx.classes.DiGraph.prototype,"predecessors",jsnx.classes.DiGraph.prototype.predecessors);jsnx.classes.DiGraph.prototype.neighbors=jsnx.classes.DiGraph.prototype.successors;goog.exportProperty(jsnx.classes.DiGraph.prototype,"neighbors",jsnx.classes.DiGraph.prototype.neighbors);
jsnx.classes.DiGraph.prototype.neighbors_iter=jsnx.classes.DiGraph.prototype.successors_iter;goog.exportProperty(jsnx.classes.DiGraph.prototype,"neighbors_iter",jsnx.classes.DiGraph.prototype.neighbors_iter);
jsnx.classes.DiGraph.prototype.edges_iter=function(a,b){goog.isBoolean(a)&&(b=a,a=null);var c,d;if(goog.isDefAndNotNull(a)){var e=[];c=jsnx.helper.map(this.nbunch_iter(a),function(a){e[0]=a;e[1]=this.adj.get(a);return e},this)}else c=this.adj;return b?jsnx.helper.nested_chain(c,function(a){d=a[0];return goog.iter.toIterator(a[1])},function(a){return[d,a[0],a[1]]}):jsnx.helper.nested_chain(c,function(a){d=a[0];return goog.iter.toIterator(a[1])},function(a){return[d,a[0]]})};
goog.exportProperty(jsnx.classes.DiGraph.prototype,"edges_iter",jsnx.classes.DiGraph.prototype.edges_iter);jsnx.classes.DiGraph.prototype.out_edges_iter=jsnx.classes.DiGraph.prototype.edges_iter;goog.exportProperty(jsnx.classes.DiGraph.prototype,"out_edges_iter",jsnx.classes.DiGraph.prototype.out_edges_iter);jsnx.classes.DiGraph.prototype.out_edges=jsnx.classes.Graph.prototype.edges;goog.exportProperty(jsnx.classes.DiGraph.prototype,"out_edges",jsnx.classes.DiGraph.prototype.out_edges);
jsnx.classes.DiGraph.prototype.in_edges_iter=function(a,b){goog.isBoolean(a)&&(b=a,a=null);var c,d;if(goog.isDefAndNotNull(a)){var e=[];c=jsnx.helper.map(this.nbunch_iter(a),function(a){e[0]=a;e[1]=this.pred.get(a);return e},this)}else c=this.pred;return b?jsnx.helper.nested_chain(c,function(a){d=a[0];return goog.iter.toIterator(a[1])},function(a){a[2]=a[1];a[1]=d;return a}):jsnx.helper.nested_chain(c,function(a){d=a[0];return goog.iter.toIterator(a[1])},function(a){a[1]=d;return a})};
goog.exportProperty(jsnx.classes.DiGraph.prototype,"in_edges_iter",jsnx.classes.DiGraph.prototype.in_edges_iter);jsnx.classes.DiGraph.prototype.in_edges=function(a,b){return jsnx.helper.toArray(this.in_edges_iter(a,b))};goog.exportProperty(jsnx.classes.DiGraph.prototype,"in_edges",jsnx.classes.DiGraph.prototype.in_edges);
jsnx.classes.DiGraph.prototype.degree_iter=function(a,b){var c;c=goog.isDefAndNotNull(a)?jsnx.helper.zip(goog.iter.map(this.nbunch_iter(a),function(a){return[a,this.succ.get(a)]},this),jsnx.helper.map(this.nbunch_iter(a),function(a){return[a,this.pred.get(a)]},this)):jsnx.helper.zip(goog.iter.toIterator(this.succ),goog.iter.toIterator(this.pred));return goog.isString(b)?jsnx.helper.map(c,function(a){var c=a[1][1],f=0;a[0][1].forEach(function(a,c){f+=+goog.object.get(c,b,1)});c.forEach(function(a,
c){f+=+goog.object.get(c,b,1)});return[a[0][0],f]}):goog.iter.map(c,function(a){return[a[0][0],a[0][1].count()+a[1][1].count()]})};goog.exportProperty(jsnx.classes.DiGraph.prototype,"degree_iter",jsnx.classes.DiGraph.prototype.degree_iter);
jsnx.classes.DiGraph.prototype.in_degree_iter=function(a,b){var c;c=goog.isDefAndNotNull(a)?jsnx.helper.map(this.nbunch_iter(a),function(a){return[a,this.pred.get(a)]},this):this.pred;return goog.isDefAndNotNull(b)?jsnx.helper.map(c,function(a){var c=0;a[1].forEach(function(a,d){c+=+goog.object.get(d,b,1)});a[1]=c;return a}):jsnx.helper.map(c,function(a){a[1]=a[1].count();return a})};goog.exportProperty(jsnx.classes.DiGraph.prototype,"in_degree_iter",jsnx.classes.DiGraph.prototype.in_degree_iter);
jsnx.classes.DiGraph.prototype.out_degree_iter=function(a,b){var c;if(goog.isDefAndNotNull(a)){var d=[];c=jsnx.helper.map(this.nbunch_iter(a),function(a){d[0]=a;d[1]=this.succ.get(a);return d},this)}else c=goog.iter.toIterator(this.succ);return goog.isDefAndNotNull(b)?jsnx.helper.map(c,function(a){var c=0;a[1].forEach(function(a,d){c+=+goog.object.get(d,b,1)});return[a[0],c]}):jsnx.helper.map(c,function(a){return[a[0],a[1].count()]})};
goog.exportProperty(jsnx.classes.DiGraph.prototype,"out_degree_iter",jsnx.classes.DiGraph.prototype.out_degree_iter);jsnx.classes.DiGraph.prototype.in_degree=function(a,b){return goog.isDefAndNotNull(a)&&this.has_node(a)?this.in_degree_iter(a,b).next()[1]:new jsnx.contrib.Map(this.in_degree_iter(a,b))};goog.exportProperty(jsnx.classes.DiGraph.prototype,"in_degree",jsnx.classes.DiGraph.prototype.in_degree);
jsnx.classes.DiGraph.prototype.out_degree=function(a,b){return goog.isDefAndNotNull(a)&&this.has_node(a)?this.out_degree_iter(a,b).next()[1]:new jsnx.contrib.Map(this.out_degree_iter(a,b))};goog.exportProperty(jsnx.classes.DiGraph.prototype,"out_degree",jsnx.classes.DiGraph.prototype.out_degree);jsnx.classes.DiGraph.prototype.clear=function(){this.succ.clear();this.pred.clear();this.node.clear();goog.object.clear(this.graph)};goog.exportProperty(jsnx.classes.DiGraph.prototype,"clear",jsnx.classes.DiGraph.prototype.clear);
jsnx.classes.DiGraph.prototype.is_multigraph=function(){return!1};goog.exportProperty(jsnx.classes.DiGraph.prototype,"is_multigraph",jsnx.classes.DiGraph.prototype.is_multigraph);jsnx.classes.DiGraph.prototype.is_directed=function(){return!0};goog.exportProperty(jsnx.classes.DiGraph.prototype,"is_directed",jsnx.classes.DiGraph.prototype.is_directed);jsnx.classes.DiGraph.prototype.to_directed=function(){return jsnx.helper.deepcopy_instance(this)};
goog.exportProperty(jsnx.classes.DiGraph.prototype,"to_directed",jsnx.classes.DiGraph.prototype.to_directed);
jsnx.classes.DiGraph.prototype.to_undirected=function(a){var b=new jsnx.classes.Graph;b.name(this.name());b.add_nodes_from(this);var c=this.pred,d=[];a?b.add_edges_from(jsnx.helper.nested_chain(this.adjacency_iter(),function(a){d[0]=a[0];return goog.iter.toIterator(a[1])},function(a){if(c.get(d[0]).has(a[0]))return d[1]=a[0],d[2]=jsnx.helper.deepcopy(a[1]),d})):b.add_edges_from(jsnx.helper.nested_chain(this.adjacency_iter(),function(a){d[0]=a[0];return goog.iter.toIterator(a[1])},function(a){d[1]=
a[0];d[2]=jsnx.helper.deepcopy(a[1]);return d}));b.graph=jsnx.helper.deepcopy(this.graph);b.node=jsnx.helper.deepcopy(this.node);return b};goog.exportProperty(jsnx.classes.DiGraph.prototype,"to_undirected",jsnx.classes.DiGraph.prototype.to_undirected);
jsnx.classes.DiGraph.prototype.reverse=function(a){(a=!goog.isDef(a)||a)?(a=new this.constructor(null,{name:"Reverse of ("+this.name()+")"}),a.add_nodes_from(this),a.add_edges_from(jsnx.helper.map(this.edges_iter(null,!0),function(a){var c=a[0];a[0]=a[1];a[1]=c;a[2]=jsnx.helper.deepcopy(a[2]);return a})),a.graph=jsnx.helper.deepcopy(this.graph),a.node=jsnx.helper.deepcopy(this.node)):(a=this.succ,this.succ=this.pred,this.pred=a,this.adj=this.succ,a=this);return a};
goog.exportProperty(jsnx.classes.DiGraph.prototype,"reverse",jsnx.classes.DiGraph.prototype.reverse);
jsnx.classes.DiGraph.prototype.subgraph=function(a){a=this.nbunch_iter(a);var b=new this.constructor,c=b.succ,d=b.pred,e=this.succ;jsnx.helper.forEach(a,function(a){c.set(a,new jsnx.contrib.Map);d.set(a,new jsnx.contrib.Map)});c.forEach(function(a,b){e.get(a).forEach(function(e,k){c.has(e)&&(b.set(e,k),d.get(e).set(a,k))})});jsnx.helper.forEach(b,function(a){b.node.set(a,this.node.get(a))},this);b.graph=this.graph;return b};goog.exportProperty(jsnx.classes.DiGraph.prototype,"subgraph",jsnx.classes.DiGraph.prototype.subgraph);jsnx.classes.MultiGraph=function(a,b){if(!(this instanceof jsnx.classes.MultiGraph))return new jsnx.classes.MultiGraph(a,b);jsnx.classes.Graph.call(this,a,b)};goog.inherits(jsnx.classes.MultiGraph,jsnx.classes.Graph);goog.exportSymbol("jsnx.classes.MultiGraph",jsnx.classes.MultiGraph);goog.exportSymbol("jsnx.MultiGraph",jsnx.classes.MultiGraph);jsnx.classes.MultiGraph.__name__="MultiGraph";
jsnx.classes.MultiGraph.prototype.add_edge=function(a,b,c,d){var e,f;!goog.isDefAndNotNull(c)||goog.isString(c)||goog.isNumber(c)||(d=goog.asserts.assertObject(c),c=null);d=d||{};if("object"!==goog.typeOf(d))throw new jsnx.exception.JSNetworkXError("The attr_dict argument must be an object.");this.adj.has(a)||(this.adj.set(a,new jsnx.contrib.Map),this.node.set(a,{}));this.adj.has(b)||(this.adj.set(b,new jsnx.contrib.Map),this.node.set(b,{}));if(this.adj.get(a).has(b)){f=this.adj.get(a).get(b);if(!goog.isDefAndNotNull(c))for(c=
goog.object.getCount(f);goog.object.containsKey(f,c);)c+=1;e=goog.object.get(f,""+c,{});goog.object.extend(e,d);f[c]=e}else goog.isDefAndNotNull(c)||(c=0),e={},goog.object.extend(e,d),f=goog.object.create(c,e),this.adj.get(a).set(b,f),this.adj.get(b).set(a,f)};goog.exportProperty(jsnx.classes.MultiGraph.prototype,"add_edge",jsnx.classes.MultiGraph.prototype.add_edge);
jsnx.classes.MultiGraph.prototype.add_edges_from=function(a,b){b=b||{};if("object"!==goog.typeOf(b))throw new jsnx.exception.JSNetworkXError("The attr_dict argument must be an object.");jsnx.helper.forEach(a,function(a){var d=jsnx.helper.len(a),e,f=null,g={};if(4===d)d=a[0],e=a[1],f=a[2],g=a[3];else if(3===d)d=a[0],e=a[1],g=a[2];else if(2===d)d=a[0],e=a[1];else throw new jsnx.exception.JSNetworkXError("Edge tuple "+goog.json.serialize(a)+" must be a 2-tuple, 3-tuple or 4-tuple.");a=this.adj.has(d)?
this.adj.get(d).get(e,{}):{};if(!goog.isDefAndNotNull(f))for(f=goog.object.getCount(a);goog.object.containsKey(a,f);)f+=1;a=goog.object.get(a,f,{});goog.object.extend(a,b,g);this.add_edge(d,e,f,a)},this)};goog.exportProperty(jsnx.classes.MultiGraph.prototype,"add_edges_from",jsnx.classes.MultiGraph.prototype.add_edges_from);
jsnx.classes.MultiGraph.prototype.remove_edge=function(a,b,c){var d;try{d=this.adj.get(a).get(b)}catch(e){if(!(e instanceof jsnx.exception.KeyError))throw e;throw new jsnx.exception.JSNetworkXError("The edge "+a+"-"+b+" is not in the graph");}if(goog.isDefAndNotNull(c)){if(!goog.object.containsKey(d,c))throw new jsnx.exception.JSNetworkXError("The edge "+a+"-"+b+" with key "+c+" is not in the graph");goog.object.remove(d,c)}else goog.object.remove(d,goog.object.getAnyKey(d));0===goog.object.getCount(d)&&
(this.adj.get(a).remove(b),a!==b&&this.adj.get(b).remove(a))};goog.exportProperty(jsnx.classes.MultiGraph.prototype,"remove_edge",jsnx.classes.MultiGraph.prototype.remove_edge);jsnx.classes.MultiGraph.prototype.remove_edges_from=function(a){jsnx.helper.forEach(a,function(a){try{this.remove_edge(a[0],a[1],a[2])}catch(c){if(!(c instanceof jsnx.exception.JSNetworkXError))throw c;}},this)};goog.exportProperty(jsnx.classes.MultiGraph.prototype,"remove_edges_from",jsnx.classes.MultiGraph.prototype.remove_edges_from);
jsnx.classes.MultiGraph.prototype.has_edge=function(a,b,c){try{return goog.isDefAndNotNull(c)?goog.object.containsKey(this.adj.get(a).get(b),c):this.adj.get(a).has(b)}catch(d){if(!(d instanceof jsnx.exception.KeyError))throw d;return!1}};goog.exportProperty(jsnx.classes.MultiGraph.prototype,"has_edge",jsnx.classes.MultiGraph.prototype.has_edge);jsnx.classes.MultiGraph.prototype.edges=function(a,b,c){return goog.iter.toArray(this.edges_iter(a,b,c))};
goog.exportProperty(jsnx.classes.MultiGraph.prototype,"edges",jsnx.classes.MultiGraph.prototype.edges);
jsnx.classes.MultiGraph.prototype.edges_iter=function(a,b,c){goog.isBoolean(a)&&(goog.isBoolean(b)&&(c=b),b=goog.asserts.assertBoolean(a),a=null);var d=new jsnx.contrib.Map,e,f;if(goog.isDefAndNotNull(a)){var g=[];a=jsnx.helper.map(this.nbunch_iter(a),function(a){g[0]=a;g[1]=this.adj.get(a);return g},this)}else a=goog.iter.toIterator(this.adj);return b?jsnx.helper.nested_chain(a,function(a){e=a[0];var b=new goog.iter.Iterator,c=goog.iter.toIterator(a[1]);b.next=function(){try{return c.next()}catch(a){throw a===
goog.iter.StopIteration&&d.set(e,!0),a;}};return b},function(a){f=a[0];if(!d.has(f))return jsnx.helper.iteritems(a[1])},function(a){return c?[e,f,a[0],a[1]]:[e,f,a[1]]}):jsnx.helper.nested_chain(a,function(a){e=a[0];var b=new goog.iter.Iterator,c=goog.iter.toIterator(a[1]);b.next=function(){try{return c.next()}catch(a){throw a===goog.iter.StopIteration&&d.set(e,!0),a;}};return b},function(a){f=a[0];if(!d.has(f))return jsnx.helper.iteritems(a[1])},function(a){return c?[e,f,a[0]]:[e,f]})};
goog.exportProperty(jsnx.classes.MultiGraph.prototype,"edges_iter",jsnx.classes.MultiGraph.prototype.edges_iter);jsnx.classes.MultiGraph.prototype.get_edge_data=function(a,b,c,d){goog.isDef(d)||(d=null);try{return goog.isDefAndNotNull(c)?goog.object.get(this.adj.get(a).get(b),""+c,d):this.adj.get(a).get(b)}catch(e){if(!(e instanceof jsnx.exception.KeyError))throw e;return d}};goog.exportProperty(jsnx.classes.MultiGraph.prototype,"get_edge_data",jsnx.classes.MultiGraph.prototype.get_edge_data);
jsnx.classes.MultiGraph.prototype.degree_iter=function(a,b){var c;if(goog.isDefAndNotNull(a)){var d=[];c=jsnx.helper.map(this.nbunch_iter(a),function(a){d[0]=a;d[1]=this.adj.get(a);return d},this)}else c=goog.iter.toIterator(this.adj);return goog.isDefAndNotNull(b)?goog.iter.map(c,function(a){var c=a[0];a=a[1];var d=0;a.forEach(function(a,c){goog.object.forEach(c,function(a){d+=goog.object.get(a,goog.asserts.assert(b),1)})});a.has(c)&&goog.object.forEach(a.get(c),function(a){d+=goog.object.get(a,
goog.asserts.assert(b),1)});return[c,d]}):goog.iter.map(c,function(a){var b=a[0];a=a[1];var c=0;a.forEach(function(a,b){c+=goog.object.getCount(b)});return[b,c+ +(a.has(b)&&goog.object.getCount(a.get(b)))]})};goog.exportProperty(jsnx.classes.MultiGraph.prototype,"degree_iter",jsnx.classes.MultiGraph.prototype.degree_iter);jsnx.classes.MultiGraph.prototype.is_multigraph=function(){return!0};goog.exportProperty(jsnx.classes.MultiGraph.prototype,"is_multigraph",jsnx.classes.MultiGraph.prototype.is_multigraph);
jsnx.classes.MultiGraph.prototype.is_directed=function(){return!1};goog.exportProperty(jsnx.classes.MultiGraph.prototype,"is_directed",jsnx.classes.MultiGraph.prototype.is_directed);
jsnx.classes.MultiGraph.prototype.to_directed=function(){var a=new jsnx.classes.MultiDiGraph;a.add_nodes_from(this);a.add_edges_from(function(){var a,c;return jsnx.helper.nested_chain(this.adjacency_iter(),function(c){a=c[0];return goog.iter.toIterator(c[1])},function(a){c=a[0];return jsnx.helper.iteritems(a[1])},function(d){return[a,c,d[0],jsnx.helper.deepcopy(d[1])]})}.call(this));a.graph=jsnx.helper.deepcopy(this.graph);a.node=jsnx.helper.deepcopy(this.node);return a};
goog.exportProperty(jsnx.classes.MultiGraph.prototype,"to_directed",jsnx.classes.MultiGraph.prototype.to_directed);
jsnx.classes.MultiGraph.prototype.selfloop_edges=function(a,b){var c=[];a?b?this.adj.forEach(function(a,b){b.has(a)&&goog.object.forEach(b.get(a),function(b,e){c.push([a,a,e,b])})}):this.adj.forEach(function(a,b){b.has(a)&&goog.object.forEach(b.get(a),function(b){c.push([a,a,b])})}):b?this.adj.forEach(function(a,b){b.has(a)&&goog.object.forEach(b.get(a),function(b,e){c.push([a,a,e])})}):this.adj.forEach(function(a,b){b.has(a)&&goog.object.forEach(b.get(a),function(){c.push([a,a])})});return c};
goog.exportProperty(jsnx.classes.MultiGraph.prototype,"selfloop_edges",jsnx.classes.MultiGraph.prototype.selfloop_edges);jsnx.classes.MultiGraph.prototype.number_of_edges=function(a,b){if(!goog.isDefAndNotNull(a))return this.size();try{return goog.object.getCount(this.adj.get(a).get(a))}catch(c){if(!(c instanceof jsnx.exception.KeyError))throw c;return 0}};goog.exportProperty(jsnx.classes.MultiGraph.prototype,"number_of_edges",jsnx.classes.MultiGraph.prototype.number_of_edges);
jsnx.classes.MultiGraph.prototype.subgraph=function(a){a=this.nbunch_iter(a);var b=new this.constructor,c=b.adj,d=this.adj;goog.iter.forEach(a,function(a){var b=new jsnx.contrib.Map;c.set(a,b);d.get(a).forEach(function(d,h){if(c.has(d)){var k=goog.object.clone(h);b.set(d,k);c.get(d).set(a,k)}})});this.node.forEach(function(a,c){b.node.set(a,c)});b.graph=this.graph;return b};goog.exportProperty(jsnx.classes.MultiGraph.prototype,"subgraph",jsnx.classes.MultiGraph.prototype.subgraph);jsnx.classes.MultiDiGraph=function(a,b){if(!(this instanceof jsnx.classes.MultiDiGraph))return new jsnx.classes.MultiDiGraph(a,b);jsnx.classes.DiGraph.call(this,a,b)};goog.inherits(jsnx.classes.MultiDiGraph,jsnx.classes.DiGraph);jsnx.helper.mixin(jsnx.classes.MultiDiGraph.prototype,jsnx.classes.MultiGraph.prototype);goog.exportSymbol("jsnx.classes.MultiDiGraph",jsnx.classes.MultiDiGraph);goog.exportSymbol("jsnx.MultiDiGraph",jsnx.classes.MultiDiGraph);jsnx.classes.MultiDiGraph.__name__="MultiDiGraph";
jsnx.classes.MultiDiGraph.prototype.add_edge=function(a,b,c,d){var e,f;!goog.isDefAndNotNull(c)||goog.isString(c)||goog.isNumber(c)||(d=c,c=null);d=d||{};if("object"!==goog.typeOf(d))throw new jsnx.exception.JSNetworkXError("The attr_dict argument must be an object.");this.succ.has(a)||(this.succ.set(a,new jsnx.contrib.Map),this.pred.set(a,new jsnx.contrib.Map),this.node.set(a,{}));this.succ.has(b)||(this.succ.set(b,new jsnx.contrib.Map),this.pred.set(b,new jsnx.contrib.Map),this.node.set(b,{}));
if(this.succ.get(a).has(b)){f=this.adj.get(a).get(b);if(!goog.isDefAndNotNull(c))for(c=goog.object.getCount(f);goog.object.containsKey(f,c);)c+=1;e=goog.object.get(f,c.toString(),{});goog.object.extend(e,d);f[c]=e}else goog.isDefAndNotNull(c)||(c=0),e={},goog.object.extend(e,d),f=goog.object.create(c,e),this.succ.get(a).set(b,f),this.pred.get(b).set(a,f)};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"add_edge",jsnx.classes.MultiDiGraph.prototype.add_edge);
jsnx.classes.MultiDiGraph.prototype.remove_edge=function(a,b,c){var d;try{d=this.adj.get(a).get(b)}catch(e){if(!(e instanceof jsnx.exception.KeyError))throw e;throw new jsnx.exception.JSNetworkXError("The edge "+a+"-"+b+" is not in the graph");}if(goog.isDefAndNotNull(c)){if(!goog.object.containsKey(d,c))throw new jsnx.exception.JSNetworkXError("The edge "+a+"-"+b+" with key "+c+" is not in the graph");goog.object.remove(d,c)}else goog.object.remove(d,goog.object.getAnyKey(d));0===goog.object.getCount(d)&&
(this.succ.get(a).remove(b),this.pred.get(b).remove(a))};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"remove_edge",jsnx.classes.MultiDiGraph.prototype.remove_edge);
jsnx.classes.MultiDiGraph.prototype.edges_iter=function(a,b,c){goog.isBoolean(a)&&(goog.isBoolean(b)&&(c=b),b=a,a=null);var d,e;if(goog.isDefAndNotNull(a)){var f=[];a=jsnx.helper.map(this.nbunch_iter(a),function(a){f[0]=a;f[1]=this.adj.get(a);return f},this)}else a=goog.iter.toIterator(this.adj);return b?jsnx.helper.nested_chain(a,function(a){d=a[0];return goog.iter.toIterator(a[1])},function(a){e=a[0];return jsnx.helper.iteritems(a[1])},function(a){return c?[d,e,a[0],a[1]]:[d,e,a[1]]}):jsnx.helper.nested_chain(a,
function(a){d=a[0];return goog.iter.toIterator(a[1])},function(a){e=a[0];return jsnx.helper.iteritems(a[1])},function(a){return c?[d,e,a[0]]:[d,e]})};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"edges_iter",jsnx.classes.MultiDiGraph.prototype.edges_iter);jsnx.classes.MultiDiGraph.prototype.out_edges_iter=jsnx.classes.MultiDiGraph.prototype.edges_iter;goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"out_edges_iter",jsnx.classes.MultiDiGraph.prototype.out_edges_iter);
jsnx.classes.MultiDiGraph.prototype.out_edges=function(a,b,c){return goog.iter.toArray(this.out_edges_iter(a,b,c))};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"out_edges",jsnx.classes.MultiDiGraph.prototype.out_edges);
jsnx.classes.MultiDiGraph.prototype.in_edges_iter=function(a,b,c){goog.isBoolean(a)&&(b=a,a=null);var d,e;if(goog.isDefAndNotNull(a)){var f=[];a=jsnx.helper.map(this.nbunch_iter(a),function(a){f[0]=a;f[1]=this.pred.get(a);return f},this)}else a=goog.iter.toIterator(this.pred);return b?jsnx.helper.nested_chain(a,function(a){d=a[0];return goog.iter.toIterator(a[1])},function(a){e=a[0];return jsnx.helper.iteritems(a[1])},function(a){return c?[e,d,a[0],a[1]]:[e,d,a[1]]}):jsnx.helper.nested_chain(a,function(a){d=
a[0];return goog.iter.toIterator(a[1])},function(a){e=a[0];return jsnx.helper.iteritems(a[1])},function(a){return c?[e,d,a[0]]:[e,d]})};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"in_edges_iter",jsnx.classes.MultiDiGraph.prototype.in_edges_iter);jsnx.classes.MultiDiGraph.prototype.in_edges=function(a,b,c){return goog.iter.toArray(this.in_edges_iter(a,b,c))};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"in_edges",jsnx.classes.MultiDiGraph.prototype.in_edges);
jsnx.classes.MultiDiGraph.prototype.degree_iter=function(a,b){var c;if(goog.isDefAndNotNull(a)){var d=[],e=[];c=jsnx.helper.zip(goog.iter.map(this.nbunch_iter(a),function(a){d[0]=a;d[1]=this.succ.get(a);return d},this),goog.iter.map(this.nbunch_iter(a),function(a){e[0]=a;e[1]=this.pred.get(a);return e},this))}else c=jsnx.helper.zip(goog.iter.toIterator(this.succ),goog.iter.toIterator(this.pred));return goog.isDefAndNotNull(b)?jsnx.helper.map(c,function(a){var c=a[0][1],d=0;a[1][1].forEach(function(a,
c){goog.object.forEach(c,function(a){d+=+goog.object.get(a,goog.asserts.assert(b),1)})});c.forEach(function(a,c){goog.object.forEach(c,function(a){d+=+goog.object.get(a,goog.asserts.assert(b),1)})});return[a[0][0],d]}):jsnx.helper.map(c,function(a){var b=0,c=0;a[1][1].forEach(function(a,c){b+=goog.object.getCount(c)});a[0][1].forEach(function(a,b){c+=goog.object.getCount(b)});return[a[0][0],b+c]})};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"degree_iter",jsnx.classes.MultiDiGraph.prototype.degree_iter);
jsnx.classes.MultiDiGraph.prototype.in_degree_iter=function(a,b){var c;if(goog.isDefAndNotNull(a)){var d=[];c=jsnx.helper.map(this.nbunch_iter(a),function(a){d[0]=a;d[1]=this.pred.get(a);return d},this)}else c=goog.iter.toIterator(this.pred);return goog.isDefAndNotNull(b)?jsnx.helper.map(c,function(a){var c=0;a[1].forEach(function(a,d){goog.object.forEach(d,function(a){c+=+goog.object.get(a,goog.asserts.assert(b),1)})});return[a[0],c]}):jsnx.helper.map(c,function(a){var b=0;a[1].forEach(function(a,
c){b+=goog.object.getCount(c)});return[a[0],b]})};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"in_degree_iter",jsnx.classes.MultiDiGraph.prototype.in_degree_iter);
jsnx.classes.MultiDiGraph.prototype.out_degree_iter=function(a,b){var c;if(goog.isDefAndNotNull(a)){var d=[];c=jsnx.helper.map(this.nbunch_iter(a),function(a){d[0]=a;d[1]=this.succ.get(a);return d},this)}else c=goog.iter.toIterator(this.succ);return goog.isDefAndNotNull(b)?jsnx.helper.map(c,function(a){var c=0;a[1].forEach(function(a,d){goog.object.forEach(d,function(a){c+=+goog.object.get(a,goog.asserts.assert(b),1)})});return[a[0],c]}):jsnx.helper.map(c,function(a){var b=0;a[1].forEach(function(a,
c){b+=goog.object.getCount(c)});return[a[0],b]})};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"out_degree_iter",jsnx.classes.MultiDiGraph.prototype.out_degree_iter);jsnx.classes.MultiDiGraph.prototype.is_multigraph=function(){return!0};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"is_multigraph",jsnx.classes.MultiDiGraph.prototype.is_multigraph);jsnx.classes.MultiDiGraph.prototype.is_directed=function(){return!0};
goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"is_directed",jsnx.classes.MultiDiGraph.prototype.is_directed);jsnx.classes.MultiDiGraph.prototype.to_directed=function(){return jsnx.helper.deepcopy_instance(this)};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"to_directed",jsnx.classes.MultiDiGraph.prototype.to_directed);
jsnx.classes.MultiDiGraph.prototype.to_undirected=function(a){var b=new jsnx.classes.MultiGraph;b.name(this.name());b.add_nodes_from(this);var c,d;a?b.add_edges_from(jsnx.helper.nested_chain(this.adjacency_iter(),function(a){c=a[0];return goog.iter.toIterator(a[1])},function(a){d=a[0];return jsnx.helper.iteritems(a[1])},goog.bind(function(a){if(this.has_edge(d,c,a[0]))return[c,d,a[0],jsnx.helper.deepcopy(a[1])]},this))):b.add_edges_from(jsnx.helper.nested_chain(this.adjacency_iter(),function(a){c=
a[0];return goog.iter.toIterator(a[1])},function(a){d=a[0];return jsnx.helper.iteritems(a[1])},function(a){return[c,d,a[0],jsnx.helper.deepcopy(a[1])]}));b.graph=jsnx.helper.deepcopy(this.graph);b.node=jsnx.helper.deepcopy(this.node);return b};goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"to_undirected",jsnx.classes.MultiDiGraph.prototype.to_undirected);
jsnx.classes.MultiDiGraph.prototype.subgraph=function(a){a=this.nbunch_iter(a);var b=new this.constructor,c=b.succ,d=b.pred,e=this.succ;goog.iter.forEach(a,function(a){c.set(a,new jsnx.contrib.Map);d.set(a,new jsnx.contrib.Map)});c.forEach(function(a,b){e.get(a).forEach(function(e,k){if(c.has(e)){var l=goog.object.clone(k);b.set(e,l);d.get(e).set(a,l)}})});this.node.forEach(function(a,c){b.node.set(a,c)});b.graph=this.graph;return b};
goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"subgraph",jsnx.classes.MultiDiGraph.prototype.subgraph);
jsnx.classes.MultiDiGraph.prototype.reverse=function(a){(a=!goog.isDef(a)||a)?(a=new this.constructor(null,{name:"Reverse of ("+this.name()+")"}),a.add_nodes_from(this),a.add_edges_from(goog.iter.map(this.edges_iter(null,!0,!0),function(a){return[a[1],a[0],a[2],jsnx.helper.deepcopy(a[3])]})),a.graph=jsnx.helper.deepcopy(this.graph),a.node=jsnx.helper.deepcopy(this.node)):(a=this.succ,this.succ=this.pred,this.pred=a,this.adj=this.succ,a=this);return a};
goog.exportProperty(jsnx.classes.MultiDiGraph.prototype,"reverse",jsnx.classes.MultiDiGraph.prototype.reverse);jsnx.classes.func={};jsnx.classes.func.nodes=function(a){return a.nodes()};goog.exportSymbol("jsnx.classes.func.nodes",jsnx.classes.func.nodes);goog.exportSymbol("jsnx.nodes",jsnx.classes.func.nodes);jsnx.classes.func.nodes_iter=function(a){return a.nodes_iter()};goog.exportSymbol("jsnx.classes.func.nodes_iter",jsnx.classes.func.nodes_iter);goog.exportSymbol("jsnx.nodes_iter",jsnx.classes.func.nodes_iter);jsnx.classes.func.edges=function(a,b){return a.edges(b)};
goog.exportSymbol("jsnx.classes.func.edges",jsnx.classes.func.edges);goog.exportSymbol("jsnx.edges",jsnx.classes.func.edges);jsnx.classes.func.edges_iter=function(a,b){return a.edges_iter(b)};goog.exportSymbol("jsnx.classes.func.edges_iter",jsnx.classes.func.edges_iter);goog.exportSymbol("jsnx.edges_iter",jsnx.classes.func.edges_iter);jsnx.classes.func.degree=function(a,b,c){return a.degree(b,c)};goog.exportSymbol("jsnx.degree",jsnx.classes.func.degree);jsnx.classes.func.neighbors=function(a,b){return a.neighbors(b)};
goog.exportSymbol("jsnx.classes.func.neighbors",jsnx.classes.func.neighbors);goog.exportSymbol("jsnx.neighbors",jsnx.classes.func.neighbors);jsnx.classes.func.number_of_nodes=function(a){return a.number_of_nodes()};goog.exportSymbol("jsnx.classes.func.number_of_nodes",jsnx.classes.func.number_of_nodes);goog.exportSymbol("jsnx.number_of_nodes",jsnx.classes.func.number_of_nodes);jsnx.classes.func.number_of_edges=function(a){return a.number_of_edges()};
goog.exportSymbol("jsnx.classes.func.number_of_edges",jsnx.classes.func.number_of_edges);goog.exportSymbol("jsnx.number_of_edges",jsnx.classes.func.number_of_edges);jsnx.classes.func.density=function(a){var b=a.number_of_nodes(),c=a.number_of_edges();return 0===c?0:a.is_directed()?c/(b*(b-1)):2*c/(b*(b-1))};goog.exportSymbol("jsnx.classes.func.density",jsnx.classes.func.density);goog.exportSymbol("jsnx.density",jsnx.classes.func.density);
jsnx.classes.func.degree_histogram=function(a){a=a.degree().values();var b=Math.max.apply(Math,a)+1,c=goog.array.repeat(0,b);goog.array.forEach(a,function(a){c[a]+=1});return c};goog.exportSymbol("jsnx.classes.func.degree_histogram",jsnx.classes.func.degree_histogram);goog.exportSymbol("jsnx.degree_histogram",jsnx.classes.func.degree_histogram);jsnx.classes.func.is_directed=function(a){return a.is_directed()};goog.exportSymbol("jsnx.classes.func.is_directed",jsnx.classes.func.is_directed);
goog.exportSymbol("jsnx.is_directed",jsnx.classes.func.is_directed);jsnx.classes.func.freeze=function(a){function b(){throw new jsnx.exception.JSNetworkXError("Frozen graph can't be modified");}a.add_node=a.add_node=b;a.add_nodes_from=a.add_nodes_from=b;a.remove_node=a.remove_node=b;a.remove_nodes_from=a.remove_nodes_from=b;a.add_edge=a.add_edge=b;a.add_edges_from=a.add_edges_from=b;a.remove_edge=a.remove_edge=b;a.remove_edges_from=a.remove_edges_from=b;a.clear=a.clear=b;a.frozen=a.frozen=!0;return a};
goog.exportSymbol("jsnx.classes.func.freeze",jsnx.classes.func.freeze);goog.exportSymbol("jsnx.freeze",jsnx.classes.func.freeze);jsnx.classes.func.is_frozen=function(a){return!!a.frozen};goog.exportSymbol("jsnx.classes.func.is_frozen",jsnx.classes.func.is_frozen);goog.exportSymbol("jsnx.is_frozen",jsnx.classes.func.is_frozen);jsnx.classes.func.subgraph=function(a,b){return a.subgraph(b)};goog.exportSymbol("jsnx.classes.func.subgraph",jsnx.classes.func.subgraph);goog.exportSymbol("jsnx.subgraph",jsnx.classes.func.subgraph);
jsnx.classes.func.create_empty_copy=function(a,b){goog.isDef(b)||(b=!0);var c=new a.constructor;b&&c.add_nodes_from(a);return c};goog.exportSymbol("jsnx.classes.func.create_empty_copy",jsnx.classes.func.create_empty_copy);goog.exportSymbol("jsnx.create_empty_copy",jsnx.classes.func.create_empty_copy);
jsnx.classes.func.info=function(a,b){var c="";if(goog.isDefAndNotNull(b)){if(!a.has_node(b))throw new jsnx.exception.JSNetworkXError("node "+b+" not in graph");c=c+("Node "+b+" has the following properties:\n")+("Degree: "+a.degree(b)+"\n");c+="Neighbors: "+a.neighbors(b).join(" ")}else{var c=c+("Name: "+a.name()+"\n"),c=c+("Type: "+a.constructor.__name__+"\n"),c=c+("Number of nodes: "+a.number_of_nodes()+"\n"),c=c+("Number of edges: "+a.number_of_edges()+"\n"),d=a.number_of_nodes();if(0<d)if(a.is_directed())c+=
"Average in degree: "+(goog.math.sum.apply(null,a.in_degree().values())/d).toFixed(4)+"\n",c+="Average out degree: "+(goog.math.sum.apply(null,a.out_degree().values())/d).toFixed(4);else var e=goog.math.sum.apply(null,a.degree().values()),c=c+("Average degree: "+(e/d).toFixed(4))}return c};goog.exportSymbol("jsnx.classes.func.info",jsnx.classes.func.info);goog.exportSymbol("jsnx.info",jsnx.classes.func.info);
jsnx.classes.func.set_node_attributes=function(a,b,c){goog.object.forEach(c,function(c,e){a.node.get(e)[b]=c})};goog.exportSymbol("jsnx.classes.func.set_node_attributes",jsnx.classes.func.set_node_attributes);goog.exportSymbol("jsnx.set_node_attributes",jsnx.classes.func.set_node_attributes);jsnx.classes.func.get_node_attributes=function(a,b){var c=new jsnx.contrib.Map;a.node.forEach(function(a,e){goog.object.containsKey(e,b)&&c.set(a,e[b])});return c};
goog.exportSymbol("jsnx.classes.func.get_node_attributes",jsnx.classes.func.get_node_attributes);goog.exportSymbol("jsnx.get_node_attributes",jsnx.classes.func.get_node_attributes);jsnx.classes.func.set_edge_attributes=function(a,b,c){c.forEach(function(c,e){a.get(c[0]).get(c[1])[b]=e})};goog.exportSymbol("jsnx.classes.func.set_edge_attributes",jsnx.classes.func.set_edge_attributes);goog.exportSymbol("jsnx.set_edge_attributes",jsnx.classes.func.set_edge_attributes);
jsnx.classes.func.get_edge_attributes=function(a,b){var c=new jsnx.contrib.Map;goog.object.forEach(a.edges(null,!0),function(a){if(goog.object.containsKey(a[2],b)){var e=a[2][b];a.length=2;c.set(a,e)}});return c};goog.exportSymbol("jsnx.classes.func.get_edge_attributes",jsnx.classes.func.get_edge_attributes);goog.exportSymbol("jsnx.get_edge_attributes",jsnx.classes.func.get_edge_attributes);jsnx.algorithms={};jsnx.algorithms.cluster={};jsnx.algorithms.cluster.triangles=function(a,b){if(a.is_directed())throw new jsnx.exception.JSNetworkXError("triangles() is not defined for directed graphs.");if(goog.isDefAndNotNull(b)&&a.has_node(b))return Math.floor(jsnx.algorithms.cluster.triangles_and_degree_iter_(a,b).next()[2]/2);var c=new jsnx.contrib.Map;goog.iter.forEach(jsnx.algorithms.cluster.triangles_and_degree_iter_(a,b),function(a){c.set(a[0],Math.floor(a[2]/2))});return c};
goog.exportSymbol("jsnx.algorithms.cluster.triangles",jsnx.algorithms.cluster.triangles);goog.exportSymbol("jsnx.triangles",jsnx.algorithms.cluster.triangles);
jsnx.algorithms.cluster.triangles_and_degree_iter_=function(a,b){if(a.is_multigraph())throw new jsnx.exception.JSNetworkXError("Not defined for multigraphs.");var c;c=goog.isDefAndNotNull(b)?jsnx.helper.nested_chain(a.nbunch_iter(b),function(b){return[b,a.get(b)]}):goog.iter.toIterator(a.adj);return goog.iter.map(c,function(b){var c=new jsnx.contrib.Set(b[1].keys()),f=0;c.remove(b[0]);goog.iter.forEach(c,function(b){var d=new jsnx.contrib.Set(a.get(b).keys());d.remove(b);f+=c.intersection(d).count()});
return[b[0],c.count(),f]})};
jsnx.algorithms.cluster.weighted_triangles_and_degree_iter_=function(a,b,c){if(a.is_multigraph())throw new jsnx.exception.JSNetworkXError("Not defined for multigraphs.");goog.isString(c)||(c="weight");var d;d=0===a.number_of_edges()?1:jsnx.helper.max(a.edges(!0),function(a){return goog.object.get(a[2],c,1)});b=goog.isDefAndNotNull(b)?jsnx.helper.nested_chain(a.nbunch_iter(b),function(b){return[b,a.get(b)]}):goog.iter.toIterator(a.adj);return goog.iter.map(b,function(b){var f=b[0],g=new jsnx.contrib.Set(b[1].keys());
g.remove(f);var h=0,k=new jsnx.contrib.Set;goog.iter.forEach(g,function(b){var e=goog.object.get(a.get(f).get(b),c,1)/d;k.add(b);var n=(new jsnx.contrib.Set(a.get(b).keys())).difference(k);goog.iter.forEach(g.intersection(n),function(g){var k=goog.object.get(a.get(b).get(g),c,1)/d;g=goog.object.get(a.get(f).get(g),c,1)/d;h+=Math.pow(e*k*g,1/3)})});return[f,g.count(),2*h]})};
jsnx.algorithms.cluster.average_clustering=function(a,b,c,d){2===arguments.length?goog.isString(b)?(c=b,b=null):goog.isBoolean(b)&&(d=b,b=null):3===arguments.length&&goog.isBoolean(c)&&(d=c,c=null);goog.isDefAndNotNull(d)||(d=!0);var e=jsnx.algorithms.cluster.clustering(a,b,c).values();d||(e=goog.array.filter(e,function(a){return 0<a}));return goog.math.sum.apply(goog.math,e)/e.length};goog.exportSymbol("jsnx.algorithms.cluster.average_clustering",jsnx.algorithms.cluster.average_clustering);
goog.exportSymbol("jsnx.average_clustering",jsnx.algorithms.cluster.average_clustering);
jsnx.algorithms.cluster.clustering=function(a,b,c){if(a.is_directed())throw new jsnx.exception.JSNetworkXError("Clustering algorithms are not defined for directed graphs.");c=goog.isDefAndNotNull(c)?jsnx.algorithms.cluster.weighted_triangles_and_degree_iter_(a,b,c):jsnx.algorithms.cluster.triangles_and_degree_iter_(a,b);var d=new jsnx.contrib.Map;goog.iter.forEach(c,function(a){d.set(a[0],0===a[2]?0:a[2]/(a[1]*(a[1]-1)))});return goog.isDefAndNotNull(b)&&a.has_node(b)?d.values()[0]:d};
goog.exportSymbol("jsnx.algorithms.cluster.clustering",jsnx.algorithms.cluster.clustering);goog.exportSymbol("jsnx.clustering",jsnx.algorithms.cluster.clustering);jsnx.algorithms.cluster.transitivity=function(a){var b=0,c=0;goog.iter.forEach(jsnx.algorithms.cluster.triangles_and_degree_iter_(a),function(a){c+=a[1]*(a[1]-1);b+=a[2]});return 0===b?0:b/c};goog.exportSymbol("jsnx.algorithms.cluster.transitivity",jsnx.algorithms.cluster.transitivity);goog.exportSymbol("jsnx.transitivity",jsnx.algorithms.cluster.transitivity);
jsnx.algorithms.cluster.square_clustering=function(a,b){var c=goog.isDefAndNotNull(b)?a.nbunch_iter(b):jsnx.helper.iter(a),d=new jsnx.contrib.Map;goog.iter.forEach(c,function(b){d.set(b,0);var c=0;goog.iter.forEach(jsnx.helper.combinations(a.get(b).keys(),2),function(g){var h=g[0];g=g[1];var k=(new jsnx.contrib.Set(a.get(h).keys())).intersection(a.get(g).keys());k.remove(b);k=k.count();d.set(b,d.get(b)+k);var l=k+1;a.get(h).has(g)&&(l+=1);c+=(a.get(h).count()-l)*(a.get(g).count()-l)+k});0<c&&d.set(b,
d.get(b)/c)});return goog.isDefAndNotNull(b)&&a.has_node(b)?d.values()[0]:d};goog.exportSymbol("jsnx.algorithms.cluster.square_clustering",jsnx.algorithms.cluster.square_clustering);goog.exportSymbol("jsnx.square_clustering",jsnx.algorithms.cluster.square_clustering);jsnx.algorithms.clique={};
jsnx.algorithms.clique.find_cliques=function(a){var b=-1,c=new jsnx.contrib.Map,d=new jsnx.contrib.Set;goog.iter.forEach(a.adjacency_iter(),function(a){var e=new jsnx.contrib.Set(a[1].keys());e.remove(a[0]);var f=e.count();f>b?(c.set(a[0],e),d=e,b=f):c.set(a[0],e)});var e=new jsnx.contrib.Set(c.keys()),f=e.difference(d),g=new jsnx.contrib.Set,h=[],k=[];a=new goog.iter.Iterator;a.next=function(){if(0===f.count()&&0===h.length)throw goog.iter.StopIteration;var a,m;if(0<f.count())a=goog.iter.toIterator(f).next(),
f.remove(a);else{var n=h.pop();e=n[0];g=n[1];f=n[2];k.pop();return this.next()}k.push(a);e.remove(a);g.add(a);var p=c.get(a),n=e.intersection(p),p=g.intersection(p);if(0===n.count()&&(0===p.count()&&(m=goog.array.clone(k)),k.pop(),m))return m;if(0===p.count()&&1===n.count())return m=goog.array.concat(k,n.values()),k.pop(),m;var t=n.count(),q=-1,s,u;for(m=goog.iter.toIterator(p);null!==(a=goog.iter.nextOrValue(m,null))&&!(a=n.intersection(c.get(a)),u=a.count(),u>q&&(s=a,q=u,q===t)););if(q===t)return k.pop(),
this.next();b=-1;for(m=goog.iter.toIterator(n);null!==(a=goog.iter.nextOrValue(m,null))&&!(a=n.intersection(c.get(a)),u=a.count(),u>b&&(d=a,b=u,b===t-1)););q>b&&(d=s);h.push([e,g,f]);e=n;g=p;f=e.difference(d);return this.next()};return a};goog.exportSymbol("jsnx.algorithms.clique.find_cliques",jsnx.algorithms.clique.find_cliques);goog.exportSymbol("jsnx.find_cliques",jsnx.algorithms.clique.find_cliques);
jsnx.algorithms.clique.find_cliques_recursive=function(a){var b=new jsnx.contrib.Map;goog.iter.forEach(a.adjacency_iter(),function(a){var c=new jsnx.contrib.Set(a[1].keys());c.remove(a[0]);b.set(a[0],c)});if(0===b.count())return[];a=new jsnx.contrib.Set(b.keys());var c=new jsnx.contrib.Set,d=[];jsnx.algorithms.clique.extend_(b,a,c,[],d);return d};goog.exportSymbol("jsnx.algorithms.clique.find_cliques_recursive",jsnx.algorithms.clique.find_cliques_recursive);
goog.exportSymbol("jsnx.find_cliques_recursive",jsnx.algorithms.clique.find_cliques_recursive);
jsnx.algorithms.clique.extend_=function(a,b,c,d,e){var f=-1,g=b.count(),h,k,l,m;for(k=goog.iter.toIterator(c);null!==(l=goog.iter.nextOrValue(k,null));)if(l=b.intersection(a.get(l)),m=l.count(),m>f&&(h=l,f=m,m===g))return;goog.iter.forEach(b,function(c){c=b.intersection(a.get(c));var d=c.count();d>f&&(h=c,f=d)});g=b.difference(h);goog.iter.forEach(g,function(f){b.remove(f);d.push(f);var g=a.get(f);f=b.intersection(g);g=c.intersection(g);0===f.count()&&0===g.count()?e.push(goog.array.clone(d)):0===
g.count()&&1===f.count()?e.push(goog.array.concat(d,f.values())):jsnx.algorithms.clique.extend_(a,f,g,d,e);c.add(d.pop())})};jsnx.algorithms.clique.graph_clique_number=function(a,b){goog.isDefAndNotNull(b)||(b=jsnx.algorithms.clique.find_cliques(a));var c=0;jsnx.helper.forEach(b,function(a){c=a.length>c?a.length:c});return c};goog.exportSymbol("jsnx.algorithms.clique.graph_clique_number",jsnx.algorithms.clique.graph_clique_number);goog.exportSymbol("jsnx.graph_clique_number",jsnx.algorithms.clique.graph_clique_number);
jsnx.algorithms.clique.graph_number_of_cliques=function(a,b){goog.isDefAndNotNull(b)||(b=jsnx.algorithms.clique.find_cliques(a));return jsnx.helper.toArray(b).length};goog.exportSymbol("jsnx.algorithms.clique.graph_number_of_cliques",jsnx.algorithms.clique.graph_number_of_cliques);goog.exportSymbol("jsnx.graph_number_of_cliques",jsnx.algorithms.clique.graph_number_of_cliques);
jsnx.algorithms.clique.number_of_cliques=function(a,b,c){c=goog.isDefAndNotNull(c)?goog.iter.toArray(c):goog.iter.toArray(jsnx.algorithms.clique.find_cliques(a));goog.isDefAndNotNull(b)||(b=a.nodes());var d;if(goog.isArray(b))d=new jsnx.contrib.Map,goog.array.forEach(b,function(a){d.set(a,goog.array.filter(goog.asserts.assertArray(c),function(b){return(new jsnx.contrib.Set(b)).has(a)}).length)});else{var e=b;d=goog.array.filter(goog.asserts.assertArray(c),function(a){return(new jsnx.contrib.Set(a)).has(e)}).length}return d};
goog.exportSymbol("jsnx.algorithms.clique.number_of_cliques",jsnx.algorithms.clique.number_of_cliques);goog.exportSymbol("jsnx.number_of_cliques",jsnx.algorithms.clique.number_of_cliques);jsnx.algorithms.isomorphism={};
jsnx.algorithms.isomorphism.could_be_isomorphic=function(a,b){if(a.order()!=b.order())return!1;var c=a.degree(),d=jsnx.algorithms.cluster.triangles(a),e=jsnx.algorithms.clique.number_of_cliques(a),f=[];c.forEach(function(a){f.push([c.get(a),d.get(a),e.get(a)])});f.sort(function(a,b){return a[0]!==b[0]?a[0]-b[0]:a[1]!==b[1]?a[1]-b[1]:a[2]-b[2]});var g=b.degree(),h=jsnx.algorithms.cluster.triangles(b),k=jsnx.algorithms.clique.number_of_cliques(b),l=[];g.forEach(function(a){l.push([g.get(a),h.get(a),
k.get(a)])});l.sort(function(a,b){return a[0]!==b[0]?a[0]-b[0]:a[1]!==b[1]?a[1]-b[1]:a[2]-b[2]});return goog.array.equals(f,l,function(a,b){return goog.array.equals(a,b)})?!0:!1};goog.exportSymbol("jsnx.algorithms.isomorphism.could_be_isomorphic",jsnx.algorithms.isomorphism.could_be_isomorphic);goog.exportSymbol("jsnx.could_be_isomorphic",jsnx.algorithms.isomorphism.could_be_isomorphic);
jsnx.algorithms.isomorphism.fast_could_be_isomorphic=function(a,b){if(a.order()!=b.order())return!1;var c=a.degree(),d=jsnx.algorithms.cluster.triangles(a),e=[];c.forEach(function(a){e.push([c.get(a),d.get(a)])});e.sort(function(a,b){return a[0]!==b[0]?a[0]-b[0]:a[1]-b[1]});var f=b.degree(),g=jsnx.algorithms.cluster.triangles(b),h=[];f.forEach(function(a){h.push([f.get(a),g.get(a)])});h.sort(function(a,b){return a[0]!==b[0]?a[0]-b[0]:a[1]-b[1]});return goog.array.equals(e,h,function(a,b){return goog.array.equals(a,
b)})?!0:!1};goog.exportSymbol("jsnx.algorithms.isomorphism.fast_could_be_isomorphic",jsnx.algorithms.isomorphism.fast_could_be_isomorphic);goog.exportSymbol("jsnx.fast_could_be_isomorphic",jsnx.algorithms.isomorphism.fast_could_be_isomorphic);jsnx.algorithms.isomorphism.faster_could_be_isomorphic=function(a,b){if(a.order()!=b.order())return!1;var c=a.degree().values();c.sort();var d=b.degree().values();d.sort();return goog.array.equals(c,d)?!0:!1};
goog.exportSymbol("jsnx.algorithms.isomorphism.faster_could_be_isomorphic",jsnx.algorithms.isomorphism.faster_could_be_isomorphic);goog.exportSymbol("jsnx.faster_could_be_isomorphic",jsnx.algorithms.isomorphism.faster_could_be_isomorphic);jsnx.algorithms.graphical={};jsnx.algorithms.graphical.is_valid_degree_sequence=function(a,b){if("eg"===b)return jsnx.algorithms.graphical.is_valid_degree_sequence_erdos_gallai(a);if(goog.isDefAndNotNull(b)&&"hh"!==b)throw new jsnx.exception.JSNetworkXException("`opt_method` must be 'eg' or 'hh'");return jsnx.algorithms.graphical.is_valid_degree_sequence_havel_hakimi(a)};goog.exportSymbol("jsnx.algorithms.graphical.is_valid_degree_sequence",jsnx.algorithms.graphical.is_valid_degree_sequence);
goog.exportSymbol("jsnx.is_valid_degree_sequence",jsnx.algorithms.graphical.is_valid_degree_sequence);jsnx.algorithms.graphical.is_valid_degree_sequence_havel_hakimi=function(a){if(0===a.length)return!0;if(!jsnx.utils.misc.is_list_of_ints(a)||0>Math.min.apply(null,a)||0!==goog.math.sum.apply(null,a)%2)return!1;for(a=goog.array.clone(a);0<a.length;){goog.array.sort(a);if(0>a[0])break;var b=a.pop();if(0===b)return!0;if(b>a.length)break;for(var c=a.length-1,b=a.length-(b+1);c>b;c--)a[c]-=1}return!1};
goog.exportSymbol("jsnx.algorithms.graphical.is_valid_degree_sequence_havel_hakimi",jsnx.algorithms.graphical.is_valid_degree_sequence_havel_hakimi);goog.exportSymbol("jsnx.is_valid_degree_sequence_havel_hakimi",jsnx.algorithms.graphical.is_valid_degree_sequence_havel_hakimi);
jsnx.algorithms.graphical.is_valid_degree_sequence_erdos_gallai=function(a){if(0===a.length)return!0;if(!jsnx.utils.misc.is_list_of_ints(a)||0>Math.min.apply(null,a)||0!==goog.math.sum.apply(null,a)%2)return!1;var b=a.length,c=goog.array.clone(a).sort(function(a,b){return b-a}),d=[],e;e=1;for(a=c.length;e<a;e++)c[e]<c[e-1]&&d.push(e);var f,g;e=0;for(a=d.length;e<a;e++)if(f=goog.math.sum.apply(null,c.slice(0,d[e])),g=d[e]*(d[e]-1)+goog.math.sum.apply(null,goog.iter.toArray(goog.iter.map(jsnx.helper.range(d[e],
b),function(a){return Math.min(d[e],c[a])}))),f>g)return!1;return!0};goog.exportSymbol("jsnx.algorithms.graphical.is_valid_degree_sequence_erdos_gallai",jsnx.algorithms.graphical.is_valid_degree_sequence_erdos_gallai);goog.exportSymbol("jsnx.is_valid_degree_sequence_erdos_gallai",jsnx.algorithms.graphical.is_valid_degree_sequence_erdos_gallai);jsnx.algorithms.dag={};jsnx.algorithms.dag.is_directed_acyclic_graph=function(a){try{return jsnx.algorithms.dag.topological_sort(a),!0}catch(b){if(b instanceof jsnx.exception.JSNetworkXUnfeasible)return!1;throw b;}};goog.exportSymbol("jsnx.algorithms.dag.is_directed_acyclic_graph",jsnx.algorithms.dag.is_directed_acyclic_graph);goog.exportSymbol("jsnx.is_directed_acyclic_graph",jsnx.algorithms.dag.is_directed_acyclic_graph);
jsnx.algorithms.dag.topological_sort=function(a,b){if(!a.is_directed())throw new jsnx.exception.JSNetworkXError("Topological sort not defined on undirected graphs.");var c=new jsnx.contrib.Set,d=[],e=new jsnx.contrib.Set;goog.isDefAndNotNull(b)||(b=a.nodes_iter());jsnx.helper.forEach(b,function(b){if(!e.has(b))for(b=[b];0<b.length;){var g=b[b.length-1];if(e.has(g))b.pop();else{c.add(g);var h=[];a.get(g).forEach(function(a){if(!e.has(a)){if(c.has(a))throw new jsnx.exception.JSNetworkXUnfeasible("Graph contains a cycle");
h.push(a)}});0<h.length?b.push.apply(b,h):(e.add(g),goog.array.insertAt(d,g))}}});return d};goog.exportSymbol("jsnx.algorithms.dag.topological_sort",jsnx.algorithms.dag.topological_sort);goog.exportSymbol("jsnx.topological_sort",jsnx.algorithms.dag.topological_sort);
jsnx.algorithms.dag.topological_sort_recursive=function(a,b){function c(a,b,d,e){b.add(e);a.get(e).forEach(function(e){if(!b.has(e)){if(!c(a,b,d,e))return!1}else if(b.has(e)&&!goog.array.contains(d,e))throw new jsnx.exception.JSNetworkXUnfeasible("Graph contains a cycle");});goog.array.insertAt(d,e);return!0}if(!a.is_directed())throw new jsnx.exception.JSNetworkXError("Topological sort not defined on undirected graphs.");var d=new jsnx.contrib.Set,e=[];goog.isDefAndNotNull(b)||(b=a.nodes_iter());
jsnx.helper.forEach(b,function(b){if(!goog.array.contains(e,b)&&!c(a,d,e,b))throw new jsnx.exception.JSNetworkXUnfeasible("Graph contains a cycle");});return e};goog.exportSymbol("jsnx.algorithms.dag.topological_sort_recursive",jsnx.algorithms.dag.topological_sort_recursive);goog.exportSymbol("jsnx.topological_sort_recursive",jsnx.algorithms.dag.topological_sort_recursive);
jsnx.algorithms.dag.is_aperiodic=function is_aperiodic(b){if(!b.is_directed())throw new jsnx.exception.JSNetworkXError("is_aperiodic not defined for undirected graphs.");var c=b.nodes_iter().next(),d=new jsnx.contrib.Map;d.set(c,0);for(var c=[c],e=0,f=1;0<c.length;){var g=[];goog.array.forEach(c,function(c){b.get(c).forEach(function(b){d.has(b)?e=jsnx.helper.gcd(e,d.get(c)-d.get(b)+1):(g.push(b),d.set(b,f))})});c=g;f+=1}return d.count()===jsnx.helper.len(b)?1===e:1===e&&is_aperiodic(b.subgraph((new jsnx.contrib.Set(b.nodes())).difference(d.keys())))};
goog.exportSymbol("jsnx.algorithms.dag.is_aperiodic",jsnx.algorithms.dag.is_aperiodic);goog.exportSymbol("jsnx.is_aperiodic",jsnx.algorithms.dag.is_aperiodic);goog.structs.Node=function(a,b){this.key_=a;this.value_=b};goog.structs.Node.prototype.getKey=function(){return this.key_};goog.structs.Node.prototype.getValue=function(){return this.value_};goog.structs.Node.prototype.clone=function(){return new goog.structs.Node(this.key_,this.value_)};goog.structs.Heap=function(a){this.nodes_=[];a&&this.insertAll(a)};goog.structs.Heap.prototype.insert=function(a,b){var c=new goog.structs.Node(a,b),d=this.nodes_;d.push(c);this.moveUp_(d.length-1)};
goog.structs.Heap.prototype.insertAll=function(a){var b,c;if(a instanceof goog.structs.Heap){if(b=a.getKeys(),c=a.getValues(),0>=a.getCount()){a=this.nodes_;for(var d=0;d<b.length;d++)a.push(new goog.structs.Node(b[d],c[d]));return}}else b=goog.object.getKeys(a),c=goog.object.getValues(a);for(d=0;d<b.length;d++)this.insert(b[d],c[d])};goog.structs.Heap.prototype.remove=function(){var a=this.nodes_,b=a.length,c=a[0];if(!(0>=b))return 1==b?goog.array.clear(a):(a[0]=a.pop(),this.moveDown_(0)),c.getValue()};
goog.structs.Heap.prototype.peek=function(){var a=this.nodes_;return 0==a.length?void 0:a[0].getValue()};goog.structs.Heap.prototype.peekKey=function(){return this.nodes_[0]&&this.nodes_[0].getKey()};goog.structs.Heap.prototype.moveDown_=function(a){for(var b=this.nodes_,c=b.length,d=b[a];a<c>>1;){var e=this.getLeftChildIndex_(a),f=this.getRightChildIndex_(a),e=f<c&&b[f].getKey()<b[e].getKey()?f:e;if(b[e].getKey()>d.getKey())break;b[a]=b[e];a=e}b[a]=d};
goog.structs.Heap.prototype.moveUp_=function(a){for(var b=this.nodes_,c=b[a];0<a;){var d=this.getParentIndex_(a);if(b[d].getKey()>c.getKey())b[a]=b[d],a=d;else break}b[a]=c};goog.structs.Heap.prototype.getLeftChildIndex_=function(a){return 2*a+1};goog.structs.Heap.prototype.getRightChildIndex_=function(a){return 2*a+2};goog.structs.Heap.prototype.getParentIndex_=function(a){return a-1>>1};
goog.structs.Heap.prototype.getValues=function(){for(var a=this.nodes_,b=[],c=a.length,d=0;d<c;d++)b.push(a[d].getValue());return b};goog.structs.Heap.prototype.getKeys=function(){for(var a=this.nodes_,b=[],c=a.length,d=0;d<c;d++)b.push(a[d].getKey());return b};goog.structs.Heap.prototype.containsValue=function(a){return goog.array.some(this.nodes_,function(b){return b.getValue()==a})};
goog.structs.Heap.prototype.containsKey=function(a){return goog.array.some(this.nodes_,function(b){return b.getKey()==a})};goog.structs.Heap.prototype.clone=function(){return new goog.structs.Heap(this)};goog.structs.Heap.prototype.getCount=function(){return this.nodes_.length};goog.structs.Heap.prototype.isEmpty=function(){return goog.array.isEmpty(this.nodes_)};goog.structs.Heap.prototype.clear=function(){goog.array.clear(this.nodes_)};goog.structs.PriorityQueue=function(){goog.structs.Heap.call(this)};goog.inherits(goog.structs.PriorityQueue,goog.structs.Heap);goog.structs.PriorityQueue.prototype.enqueue=function(a,b){this.insert(a,b)};goog.structs.PriorityQueue.prototype.dequeue=function(){return this.remove()};jsnx.algorithms.centrality={};jsnx.algorithms.centrality.betweenness={};
jsnx.algorithms.centrality.betweenness.betweenness_centrality=function(a,b){goog.isDefAndNotNull(b)||(b={});if("object"!==goog.typeOf(b))throw new jsnx.exception.JSNetworkXError("The arg_dict argument must be an object.");var c=jsnx.helper.mapfromkeys(a,0),d=a.nodes();"k"in b&&(goog.array.shuffle(d),d=d.slice(0,b.k));jsnx.helper.forEach(d.sort(),function(d){var f=[];goog.asserts.assertObject(b);var f=null===goog.object.get(b,"weight",null)?jsnx.algorithms.centrality.betweenness.single_source_shortest_path_basic(a,
d):jsnx.algorithms.centrality.betweenness.single_source_dijkstra_path_basic(a,d,b.weight),g=f[0],h=f[1],f=f[2];c=goog.object.get(b,"endpoints",!1)?jsnx.algorithms.centrality.betweenness.accumulate_endpoints(c,g,h,f,d):jsnx.algorithms.centrality.betweenness.accumulate_basic(c,g,h,f,d)});return c=jsnx.algorithms.centrality.betweenness.rescale(c,jsnx.helper.len(a),goog.object.get(b,"normalized",!0),a.is_directed(),goog.object.get(b,"k",null))};
goog.exportSymbol("jsnx.algorithms.centrality.betweenness.betweenness_centrality",jsnx.algorithms.centrality.betweenness.betweenness_centrality);goog.exportSymbol("jsnx.betweenness_centrality",jsnx.algorithms.centrality.betweenness.betweenness_centrality);
jsnx.algorithms.centrality.betweenness.edge_betweenness_centrality=function(a,b){goog.isDefAndNotNull(b)||(b={});if("object"!==goog.typeOf(b))throw new jsnx.exception.JSNetworkXError("The arg_dict argument must be an object.");var c=jsnx.helper.mapfromkeys(a,0);goog.iter.forEach(a.edges_iter(),function(a){c.set(a,0)});var d=a.nodes();jsnx.helper.forEach(d.sort(),function(d){var f=[];goog.asserts.assertObject(b);f=null===goog.object.get(b,"weight",null)?jsnx.algorithms.centrality.betweenness.single_source_shortest_path_basic(a,
d):jsnx.algorithms.centrality.betweenness.single_source_dijkstra_path_basic(a,d,b.weight);c=jsnx.algorithms.centrality.betweenness.accumulate_edges(c,f[0],f[1],f[2],d)});jsnx.helper.forEach(d,function(a){c.remove(a)});return c=jsnx.algorithms.centrality.betweenness.rescale_e(c,jsnx.helper.len(a),goog.object.get(b,"normalized",!0),a.is_directed())};goog.exportSymbol("jsnx.algorithms.centrality.betweenness.edge_betweenness_centrality",jsnx.algorithms.centrality.betweenness.edge_betweenness_centrality);
goog.exportSymbol("jsnx.edge_betweenness_centrality",jsnx.algorithms.centrality.betweenness.edge_betweenness_centrality);
jsnx.algorithms.centrality.betweenness.single_source_shortest_path_basic=function(a,b){var c=[],d=new jsnx.contrib.Map;goog.iter.forEach(a.nodes_iter(),function(a){d.set(a,[])});var e=jsnx.helper.mapfromkeys(a,0),f=new jsnx.contrib.Map;e.set(b,1);f.set(b,0);for(var g=[b];0<g.length;){var h=g.shift();c.push(h);var k=f.get(h),l=e.get(h);goog.array.forEach(a.neighbors(h),function(a){f.has(a)||(g.push(a),f.set(a,k+1));f.get(a)===k+1&&(e.set(a,e.get(a)+l),d.get(a).push(h))})}return[c,d,e]};
jsnx.algorithms.centrality.betweenness.single_source_dijkstra_path_basic=function(a,b,c){var d=[],e=new jsnx.contrib.Map;jsnx.helper.forEach(a.nodes(),function(a){e.set(a,[])});var f=jsnx.helper.mapfromkeys(a,0),g=new jsnx.contrib.Map;f.set(b,1);var h=new jsnx.contrib.Map;h.set(b,0);var k=new goog.structs.PriorityQueue;for(k.enqueue(0,[b,b]);!k.isEmpty();){var l=k.peekKey();b=k.dequeue();var m=b[0],n=b[1];g.has(n)||(f.set(n,f.get(n)+f.get(m)),d.push(n),g.set(n,l),goog.iter.forEach(a.edges_iter(n,
!0),function(a){var b=a[1];a=l+goog.object.get(a[2],c,1);g.has(b)||h.has(b)&&!(a<h.get(b))?a===h.get(b)&&(f.set(b,f.get(b)+f.get(n)),e.get(b).push(n)):(h.set(b,a),k.enqueue(a,[n,b]),f.set(b,0),e.set(b,[n]))}))}return[d,e,f]};
jsnx.algorithms.centrality.betweenness.accumulate_basic=function(a,b,c,d,e){for(var f=jsnx.helper.mapfromkeys(b,0);0<b.length;){var g=b.pop(),h=(1+f.get(g))/d.get(g);goog.array.forEach(c.get(g),function(a){f.set(a,f.get(a)+d.get(a)*h)});(g!==e||goog.isObject(g)&&g.toString()!==e.toString())&&a.set(g,a.get(g)+f.get(g))}return a};
jsnx.algorithms.centrality.betweenness.accumulate_endpoints=function(a,b,c,d,e){a.set(e,a.get(e)+b.length-1);for(var f=jsnx.helper.mapfromkeys(b,0);0<b.length;){var g=b.pop(),h=(1+f.get(g))/d.get(g);goog.array.forEach(c.get(g),function(a){f.set(a,f.get(a)+d.get(a)*h)});(g!==e||goog.isObject(g)&&g.toString()!==e.toString())&&a.set(g,a.get(g)+f.get(g)+1)}return a};
jsnx.algorithms.centrality.betweenness.accumulate_edges=function(a,b,c,d,e){for(var f=jsnx.helper.mapfromkeys(b,0);0<b.length;){var g=b.pop(),h=(1+f.get(g))/d.get(g);goog.array.forEach(c.get(g),function(b){var c=d.get(b)*h,e=[b,g];a.has(e)||(e=[g,b]);a.set(e,a.get(e)+c);f.set(b,f.get(b)+c)});(g!==e||goog.isObject(g)&&g.toString()!==e.toString())&&a.set(g,a.get(g)+f.get(g))}return a};
jsnx.algorithms.centrality.betweenness.rescale=function(a,b,c,d,e){var f;goog.isBoolean(c)&&c?2<b&&(f=1/((b-1)*(b-2))):goog.isBoolean(d)&&!d&&(f=0.5);goog.isDef(f)&&(goog.isDefAndNotNull(e)&&(f=f*b/e),a.forEach(function(b,c){a.set(b,c*f)}));return a};jsnx.algorithms.centrality.betweenness.rescale_e=function(a,b,c,d){var e;goog.isBoolean(c)&&c?1<b&&(e=1/(b*(b-1))):goog.isBoolean(d)&&!d&&(e=0.5);goog.isDef(e)&&a.forEach(function(b,c){a.set(b,c*e)});return a};jsnx.algorithms.shortest_paths={};jsnx.algorithms.shortest_paths.unweighted={};jsnx.algorithms.shortest_paths.unweighted.single_source_shortest_path_length=function(a,b,c){var d=new jsnx.contrib.Map,e=0,f=new jsnx.contrib.Map;for(f.set(b,1);0<f.count();){b=f;f=new jsnx.contrib.Map;b.forEach(function(b){d.has(b)||(d.set(b,e),a.get(b).forEach(function(a){f.set(a,1)}))});if(goog.isNumber(c)&&c<=e)break;e+=1}return d};
goog.exportSymbol("jsnx.algorithms.shortest_paths.unweighted.single_source_shortest_path_length",jsnx.algorithms.shortest_paths.unweighted.single_source_shortest_path_length);goog.exportSymbol("jsnx.single_source_shortest_path_length",jsnx.algorithms.shortest_paths.unweighted.single_source_shortest_path_length);
jsnx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path_length=function(a,b){var c=new jsnx.contrib.Map;jsnx.helper.forEach(a,function(d){c.set(d,jsnx.algorithms.shortest_paths.unweighted.single_source_shortest_path_length(a,d,b))});return c};goog.exportSymbol("jsnx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path_length",jsnx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path_length);goog.exportSymbol("jsnx.all_pairs_shortest_path_length",jsnx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path_length);
jsnx.algorithms.shortest_paths.unweighted.bidirectional_shortest_path=function(a,b,c){c=jsnx.algorithms.shortest_paths.unweighted.bidirectional_pred_succ_(a,b,c);a=c[0];b=c[1];c=c[2];for(var d=[];goog.isDefAndNotNull(c);)d.push(c),c=b.get(c);for(c=a.get(d[0]);goog.isDefAndNotNull(c);)d.unshift(c),c=a.get(c);return d};goog.exportSymbol("jsnx.algorithms.shortest_paths.unweighted.bidirectional_shortest_path",jsnx.algorithms.shortest_paths.unweighted.bidirectional_shortest_path);
goog.exportSymbol("jsnx.bidirectional_shortest_path",jsnx.algorithms.shortest_paths.unweighted.bidirectional_shortest_path);
jsnx.algorithms.shortest_paths.unweighted.bidirectional_pred_succ_=function(a,b,c){if(!goog.isDef(b)||!goog.isDef(c))throw new jsnx.exception.JSNetworkXException("Bidirectional shortest path called without source or target");var d=new jsnx.contrib.Map,e=new jsnx.contrib.Map;if(c===b)return d.set(c,null),e.set(b,null),[d,e,b];var f,g;a.is_directed()?(f=a.predecessors_iter,g=a.successors_iter):g=f=a.neighbors_iter;d.set(b,null);e.set(c,null);for(var h=[b],k=[c],l,m;0<h.length&&0<k.length&&!m;)h.length<=
k.length?(l=h,h=[],goog.array.forEach(l,function(b){m||goog.iter.forEach(g.call(a,b),function(a){m||(d.has(a)||(h.push(a),d.set(a,b)),e.has(a)&&(m=[d,e,a]))})})):(l=k,k=[],goog.array.forEach(l,function(b){m||goog.iter.forEach(f.call(a,b),function(a){m||(e.has(a)||(e.set(a,b),k.push(a)),d.has(a)&&(m=[d,e,a]))})}));if(m)return m;throw new jsnx.exception.JSNetworkXNoPath("No path between "+b+" and "+c+".");};
jsnx.algorithms.shortest_paths.unweighted.single_source_shortest_path=function(a,b,c){var d=0,e=new jsnx.contrib.Map([[b,1]]),f=new jsnx.contrib.Map([[b,[b]]]);if(0===c)return f;for(;0<e.count()&&!(b=e,e=new jsnx.contrib.Map,b.forEach(function(b){a.get(b).forEach(function(a){f.has(a)||(f.set(a,f.get(b).concat([a])),e.set(a,1))})}),d+=1,goog.isDef(c)&&c<=d););return f};goog.exportSymbol("jsnx.algorithms.shortest_paths.unweighted.single_source_shortest_path",jsnx.algorithms.shortest_paths.unweighted.single_source_shortest_path);
goog.exportSymbol("jsnx.single_source_shortest_path",jsnx.algorithms.shortest_paths.unweighted.single_source_shortest_path);jsnx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path=function(a,b){var c=new jsnx.contrib.Map;jsnx.helper.forEach(a,function(d){c.set(d,jsnx.algorithms.shortest_paths.unweighted.single_source_shortest_path(a,d,b))});return c};goog.exportSymbol("jsnx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path",jsnx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path);
goog.exportSymbol("jsnx.all_pairs_shortest_path",jsnx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path);
jsnx.algorithms.shortest_paths.unweighted.predecessor=function(a,b,c,d,e){for(var f=0,g=[b],h=new jsnx.contrib.Map([[b,f]]),k=new jsnx.contrib.Map([[b,[]]]);0<g.length&&!(f+=1,b=g,g=[],goog.array.forEach(b,function(b){a.get(b).forEach(function(a){h.has(a)?h.get(a)===f&&k.get(a).push(b):(k.set(a,[b]),h.set(a,f),g.push(a))})}),goog.isDefAndNotNull(d)&&d<=f););return goog.isDefAndNotNull(c)?e?k.has(c)?[k.get(c),h.get(c)]:[[],-1]:k.has(c)?k.get(c):[]:e?[k,h]:k};
goog.exportSymbol("jsnx.algorithms.shortest_paths.unweighted.predecessor",jsnx.algorithms.shortest_paths.unweighted.predecessor);goog.exportSymbol("jsnx.predecessor",jsnx.algorithms.shortest_paths.unweighted.predecessor);jsnx.drawing={};jsnx.drawing.jsnx_d3={};jsnx.drawing.jsnx_d3.last_container_element_=null;jsnx.drawing.jsnx_d3.last_configuration_=null;jsnx.drawing.jsnx_d3.MUTATOR_METHODS_="add_node add_nodes_from add_edge add_edges_from remove_node remove_nodes_from remove_edge remove_edges_from clear".split(" ");jsnx.drawing.jsnx_d3.D3_DATA_NAME_="__d3datum__";
jsnx.drawing.jsnx_d3.draw=function(a,b,c){goog.isBoolean(b)&&(c=b,b=null);b=b||jsnx.drawing.jsnx_d3.last_configuration_||{};var d=b.d3||window.d3,e={};jsnx.helper.extend(e,jsnx.drawing.jsnx_d3.default_config_,b);jsnx.drawing.jsnx_d3.last_configuration_=b;if(!d)throw Error("D3 requried for draw()");if(!goog.isDefAndNotNull(e.element)&&!goog.isDefAndNotNull(jsnx.drawing.jsnx_d3.last_element_))throw Error("Output element required for draw()");jsnx.drawing.jsnx_d3.last_element_=goog.object.get(e,"element",
jsnx.drawing.jsnx_d3.last_element_);d.select(jsnx.drawing.jsnx_d3.last_element_).select("svg.jsnx").remove();var f=d.select(jsnx.drawing.jsnx_d3.last_element_),g=f.append("svg").classed("jsnx",!0).attr("pointer-events","all"),h=g.append("g");b=h.append("g").classed("edges",!0).selectAll("g.edge");var k=h.append("g").classed("nodes",!0).selectAll("g.node"),l=(e.layout||d.layout.force)(),m=e.width||parseInt(f.style("width"),10),n=e.height||parseInt(f.style("height"),10),p=e.layout_attr,f=e.nodelist||
null,t,q,s,u=a.is_directed(),w=e.weighted,v={node_selection:k,edge_selection:b};if(e.with_labels){var z=e.labels;t="object"===goog.typeOf(z)?function(a){return goog.object.get(z,a.node,"")}:goog.isFunction(z)?z:goog.isString(z)?function(a){return a.data[z]}:function(a){return a.node}}e.labels=t;if(w){var B=e.weights;s="object"===goog.typeOf(B)?function(a){return goog.object.get(B,a.node,1)}:goog.isFunction(B)?B:goog.isString(B)?function(a){return goog.object.get(a.data,B,1)}:function(a){return 1}}if(e.with_edge_labels){var C=
e.edge_labels;q=w&&!goog.isDef(C)?s:"object"===goog.typeOf(C)?function(a){return goog.object.get(z,a.node,"")}:goog.isFunction(C)?C:goog.isString(C)?function(a){return a.data[C]}:function(a){return a.edge};e.edge_labels=q}if(w&&e.weighted_stroke){var w=goog.iter.reduce(a.edges_iter(null,!0),function(a,b){b=s({data:b[2]});return a>b?a:b},0),K=d.scale.linear().range([2,e.edge_style["stroke-width"]]).domain([0,w]);e.edge_style["stroke-width"]=function(a){return K(s.call(this,a))}}g.select("svg.jsnx").remove();
g.attr("width",m+"px").attr("height",n+"px");var L={size:!0,nodes:!0,links:!0,start:!0};jsnx.helper.forEach(p,function(a){if(!goog.object.containsKey(L,a)&&goog.isFunction(l[a]))l[a](p[a])});l.nodes([]).links([]).size([m,n]);var D=1,r=1;if(e.pan_zoom.enabled){var H=e.pan_zoom.scale;(function(){var a=!1,b=1,c=D;g.call(d.behavior.zoom().on("zoomstart",function(){"wheel"!==d.event.sourceEvent.type&&g.style("cursor","move")}).on("zoomend",function(){d.event.sourceEvent&&g.style("cursor","")}).on("zoom",
function(){var e=d.event.sourceEvent.shiftKey;(e=H&&e||!(H||e))&&!a?(b=d.event.scale,c=D,a=!0):!e&&a&&(a=!1);D=e?d.event.scale/b*c:D;r=e?r:D/d.event.scale;e=d.event.translate;h.attr("transform","translate("+e[0]+","+e[1]+")scale("+d.event.scale+")");I()}))})()}var J=goog.nullFunction,A=e.edge_offset,E=e.node_attr.r,F=e.node_style["stroke-width"];"circle"===e.node_shape?(goog.isFunction(E)||(E=function(){return e.node_attr.r}),goog.isFunction(F)||(F=function(){return e.node_style["stroke-width"]}),
A=function(a){return[E(a.source)+F(a.source),E(a.target)+F(a.target)]}):(goog.isArray(A)&&(A=function(){return e.edge_offset}),goog.isNumber(A)&&(A=function(){return[e.edge_offset,e.edge_offset]}));var x=e.edge_style["stroke-width"];goog.isFunction(x)||(x=function(){return e.edge_style["stroke-width"]});var y=e.edge_label_offset,G=e.edge_len;goog.isFunction(G)||(G=function(){return e.edge_len});var J=u?function(){v.edge_selection.each(function(a){var b=d.select(this),c=a.source.x,f=a.source.y,g=a.target.x,
h=a.target.y,k=goog.math.angle(c,f,g,h),g=Math.sqrt(Math.pow(g-c,2)+Math.pow(h-f,2))*G(a),h=A(a),l=x(a)*r,m=1/r,h=[h[0]*r,h[1]*r];if(a.source===a.target){var l=g/2,n=90<k&&279>k;b.attr("transform",["translate(",c,",",f,")rotate(",k,")"].join(""));b.select(".line").attr("d",d.svg.line().interpolate("bundle")([[0,-h[0]/2],[20,-h[0]/2-45],[-20,-h[0]/2-45],[0,-h[0]/2]]));b.select(".line").style("stroke-width",x(a)/2*r);e.with_edge_labels&&b.select("text").attr("x",(n?1:-1)*y.x*m+h[0]+(g*m-h[0]-h[1])/
2).attr("y",-x(a)/4+-y.y*m+h[0]/2-45).attr("transform","scale("+r+")"+(n?"rotate(180,"+1/r*l+",0)":""))}else b.attr("transform",["translate(",c,",",f,")rotate(",k,")"].join("")),c=g-h[1]-2*l,f=l/2,b.select(".line").attr("d",["M",h[0],0,"L",h[0],-f,"L",c,-f,"L",c,-l,"L",g-h[1],0,"z"].join(" ")),b.select("text").attr("x",y.x*m+h[0]+(g*m-h[0]-h[1])/2).attr("y",-x(a)/2+-y.y*m).attr("transform","scale("+r+")")})}:function(){v.edge_selection.each(function(a){var b=d.select(this),c=a.source.x,f=a.source.y,
g=a.target.x,h=a.target.y,k=goog.math.angle(c,f,g,h),g=Math.sqrt(Math.pow(g-c,2)+Math.pow(h-f,2))*G(a),h=g/2,l=A(a),l=[l[0]*r,l[1]*r],m=1/r,n=x(a)*r,t=90<k&&279>k;a.source===a.target?(b.attr("transform",["translate(",c,",",f,")rotate(",k,")"].join("")),b.select(".line").attr("d",d.svg.line().interpolate("bundle")([[0,-l[0]/2],[20,-l[0]/2-45],[-20,-l[0]/2-45],[0,-l[0]/2]])),b.select(".line").style("stroke-width",x(a)/2*r),e.with_edge_labels&&b.select("text").attr("x",(t?1:-1)*y.x*m+l[0]+(g*m-l[0]-
l[1])/2).attr("y",-x(a)/4+-y.y*m+l[0]/2-45).attr("transform","scale("+r+")"+(t?"rotate(180,"+1/r*h+",0)":""))):(b.attr("transform",["translate(",c,",",f,")rotate(",k,")"].join("")),b.select(".line").attr("d",["M",l[0],n/4,"L",l[0],-n/4,"L",g-l[1],-n/4,"L",g-l[1],n/4,"z"].join(" ")),e.with_edge_labels&&b.select("text").attr("x",(t?1:-1)*y.x*m+l[0]+(g*m-l[0]-l[1])/2).attr("y",-x(a)/4+-y.y*m).attr("transform","scale("+r+")"+(t?"rotate(180,"+1/r*h+",0)":"")))})},I=function(){v.node_selection.attr("transform",
function(a){return["translate(",a.x,",",a.y,")scale(",r,")"].join("")});J()};l.on("tick",I);m=a.nodes_iter();n=a.edges_iter();f&&(c=!1,m=a.nbunch_iter(f),n=a.edges_iter(f));v.node_selection=jsnx.drawing.jsnx_d3.add_nodes_(a,m,l,k,e.node_shape,t);v.edge_selection=jsnx.drawing.jsnx_d3.add_edges_(a,n,l,b,q);jsnx.drawing.jsnx_d3.update_node_attr_(v.node_selection,{attr:e.node_attr,style:e.node_style,label_style:e.label_style,label_attr:e.label_attr},e.with_labels);jsnx.drawing.jsnx_d3.update_edge_attr_(v.edge_selection,
{attr:e.edge_attr,style:e.edge_style,label_style:e.edge_label_style,label_attr:e.edge_label_attr},e.with_edge_labels,null,u);c?jsnx.drawing.jsnx_d3.bind_(a,l,e,v):jsnx.drawing.jsnx_d3.is_bound(a)?jsnx.drawing.jsnx_d3.unbind(a):jsnx.drawing.jsnx_d3.clean_(a);l.start();return l};goog.exportSymbol("jsnx.draw",jsnx.drawing.jsnx_d3.draw);
jsnx.drawing.jsnx_d3.add_nodes_=function(a,b,c,d,e,f){var g=c.nodes();jsnx.helper.forEach(b,function(b){var c=a.node.get(b);b={node:b,data:c,G:a};g.push(b);c[jsnx.drawing.jsnx_d3.D3_DATA_NAME_]=b});d=d.data(g,jsnx.drawing.jsnx_d3.node_key_function);b=c.drag().on("dragstart",function(a){d3.event.sourceEvent.stopPropagation()});b=d.enter().append("g").classed("node",!0).call(b);b.append(e).classed("node-shape",!0);f&&b.append("text").text(f);return d};
jsnx.drawing.jsnx_d3.add_edges_=function(a,b,c,d,e){var f=c.links();jsnx.helper.forEach(b,function(b){var c=b[0],d=b[1];b=b[2]||a.get_edge_data(c,d);c={edge:[c,d],redge:[d,c],source:a.node.get(c)[jsnx.drawing.jsnx_d3.D3_DATA_NAME_],target:a.node.get(d)[jsnx.drawing.jsnx_d3.D3_DATA_NAME_],data:b,G:a};f.push(c);b[jsnx.drawing.jsnx_d3.D3_DATA_NAME_]=c});d=d.data(f,jsnx.drawing.jsnx_d3.edge_key_function);b=d.enter().append("g").classed("edge",!0);b.append("path").classed("line",!0);e&&b.append("text").text(e);
return d};
jsnx.drawing.jsnx_d3.update_node_attr_=function(a,b,c,d){if(goog.isDefAndNotNull(d)){var e={};jsnx.helper.forEach(d,function(a){e[goog.isArrayLike(a)?a[0]:a]=!0});a=a.filter(function(a){return goog.object.containsKey(e,a.node)})}var f=a.selectAll(".node-shape");goog.object.forEach(b.attr,function(a,b){f.attr(b,a)});goog.object.forEach(b.style,function(a,b){f.style(b,a)});if(c){var g=a.selectAll("text");goog.object.forEach(b.label_attr,function(a,b){g.attr(b,a)});goog.object.forEach(b.label_style,function(a,
b){g.style(b,a)})}};
jsnx.drawing.jsnx_d3.update_edge_attr_=function(a,b,c,d,e){if(goog.isDefAndNotNull(d)){var f={};jsnx.helper.forEach(d,function(a){f[[a[0],a[1]]]=!0});a=a.filter(function(a){return goog.object.containsKey(f,a.edge)||e||goog.object.containsKey(f,a.redge)})}var g=a.selectAll(".line");goog.object.forEach(b.attr,function(a,b){g.attr(b,a)});goog.object.forEach(b.style,function(a,b){"stroke-width"!=b&&g.style(b,a)});g.style("stroke-width",0);d=a.filter(function(a){return a.source===a.target}).selectAll(".line");d.style("fill",
"none");d.style("stroke",b.style.fill);if(c){var h=a.selectAll("text");goog.object.forEach(b.label_attr,function(a,b){h.attr(b,a)});goog.object.forEach(b.label_style,function(a,b){h.style(b,a)})}};jsnx.drawing.jsnx_d3.node_key_function=function(a){return a.node};jsnx.drawing.jsnx_d3.edge_key_function=function(a){return a.edge};
jsnx.drawing.jsnx_d3.remove_nodes_=function(a,b,c,d){var e=c.nodes();jsnx.helper.forEach(a.nbunch_iter(b),function(b){goog.array.remove(e,a.node.get(b)[jsnx.drawing.jsnx_d3.D3_DATA_NAME_])});d=d.data(e,jsnx.drawing.jsnx_d3.node_key_function);d.exit().remove();return d};
jsnx.drawing.jsnx_d3.remove_edges_=function(a,b,c,d){var e=c.links();jsnx.helper.forEach(b,function(b){goog.array.remove(e,goog.object.get(a.get_edge_data(b[0],b[1],{}),jsnx.drawing.jsnx_d3.D3_DATA_NAME_,null))});d=d.data(e,jsnx.drawing.jsnx_d3.edge_key_function);d.exit().remove();return d};
jsnx.drawing.jsnx_d3.bind_=function(a,b,c,d){jsnx.drawing.jsnx_d3.unbind(a,!1);var e=a.constructor.prototype,f=c.node_shape,g={attr:c.node_attr,style:c.node_style,label_attr:c.label_attr,label_style:c.label_style},h={attr:c.edge_attr,style:c.edge_style,label_attr:c.edge_label_attr,label_style:c.edge_label_style},k=c.labels,l=c.edge_labels,m=c.with_labels,n=c.with_edge_labels,p=a.is_directed();a.add_node=a.add_node=function(a){var c=!this.has_node(a);e.add_node.apply(this,arguments);c&&(d.node_selection=
jsnx.drawing.jsnx_d3.add_nodes_(this,[a],b,d.node_selection,f,k));jsnx.drawing.jsnx_d3.update_node_attr_(d.node_selection,g,m,[a]);b.start()};a.add_nodes_from=a.add_nodes_from=function(a){var c=goog.array.filter(goog.array.map(jsnx.helper.toArray(a),function(a){return goog.isArrayLike(a)?a[0]:a}),function(a){return!this.has_node(a)},this);e.add_nodes_from.apply(this,arguments);0<c.length&&(d.node_selection=jsnx.drawing.jsnx_d3.add_nodes_(this,c,b,d.node_selection,f,k));jsnx.drawing.jsnx_d3.update_node_attr_(d.node_selection,
g,m,a);b.start()};a.add_edge=a.add_edge=function(c,q){var s=!this.has_edge(c,q),u=[];s&&(u=goog.array.filter(c==q?[c]:[c,q],function(a){return!this.has_node(a)},this));e.add_edge.apply(a,arguments);0<u.length&&(d.node_selection=jsnx.drawing.jsnx_d3.add_nodes_(this,u,b,d.node_selection,f,k),jsnx.drawing.jsnx_d3.update_node_attr_(d.node_selection,g,m,u));s&&(d.edge_selection=jsnx.drawing.jsnx_d3.add_edges_(this,[[c,q]],b,d.edge_selection,l));jsnx.drawing.jsnx_d3.update_edge_attr_(d.edge_selection,h,
n,[[c,q]],p);b.start()};a.add_edges_from=a.add_edges_from=function(c){var q=[],s=[],p={},w={},v=this.is_directed();jsnx.helper.forEach(c,function(a){var b=a[0];a=a[1];this.has_edge(b,a)||goog.object.containsKey(p,[b,a])||!v&&goog.object.containsKey(p,[a,b])||(q.push([b,a]),p[[b,a]]=!0,this.has_node(b)||goog.object.containsKey(w,b)||(s.push(b),w[b]=!0),this.has_node(a)||goog.object.containsKey(w,a)||(s.push(a),w[a]=!0))},this);e.add_edges_from.apply(a,arguments);0<s.length&&(d.node_selection=jsnx.drawing.jsnx_d3.add_nodes_(this,
s,b,d.node_selection,f,k),jsnx.drawing.jsnx_d3.update_node_attr_(d.node_selection,g,m,s));0<q.length&&(d.edge_selection=jsnx.drawing.jsnx_d3.add_edges_(this,q,b,d.edge_selection,l));jsnx.drawing.jsnx_d3.update_edge_attr_(d.edge_selection,h,n,q,v);b.start()};a.remove_node=a.remove_node=function(c){try{if(this.has_node(c)){d.node_selection=jsnx.drawing.jsnx_d3.remove_nodes_(this,[c],b,d.node_selection);var f=this.edges_iter([c]);this.is_directed()&&(f=goog.iter.chain(f,this.in_edges_iter([c])));d.edge_selection=
jsnx.drawing.jsnx_d3.remove_edges_(this,f,b,d.edge_selection);b.start()}}catch(g){}e.remove_node.apply(a,arguments)};a.remove_nodes_from=a.remove_nodes_from=function(c){try{d.node_selection=jsnx.drawing.jsnx_d3.remove_nodes_(this,c,b,d.node_selection);var f=this.edges_iter(c);this.is_directed()&&(f=goog.iter.chain(f,this.in_edges_iter(c)));d.edge_selection=jsnx.drawing.jsnx_d3.remove_edges_(this,f,b,d.edge_selection);b.start()}catch(g){}e.remove_nodes_from.apply(a,arguments)};a.remove_edge=a.remove_edge=
function(c,f){try{d.edge_selection=jsnx.drawing.jsnx_d3.remove_edges_(this,[[c,f]],b,d.edge_selection),b.start()}catch(g){}e.remove_edge.apply(a,arguments)};a.remove_edges_from=a.remove_edges_from=function(c){try{d.edge_selection=jsnx.drawing.jsnx_d3.remove_edges_(this,c,b,d.edge_selection),b.start()}catch(f){}e.remove_edges_from.apply(a,arguments)};a.clear=a.clear=function(){d.node_selection=d.node_selection.data([],jsnx.drawing.jsnx_d3.node_key_function);d.node_selection.exit().remove();d.edge_selection=
d.edge_selection.data([],jsnx.drawing.jsnx_d3.edge_key_function);d.edge_selection.exit().remove();b.nodes([]).links([]).resume();e.clear.apply(a,arguments)};a.bound=!0};jsnx.drawing.jsnx_d3.is_bound=function(a){return a.bound};goog.exportSymbol("jsnx.is_bound",jsnx.drawing.jsnx_d3.is_bound);
jsnx.drawing.jsnx_d3.unbind=function(a,b){if(jsnx.drawing.jsnx_d3.is_bound(a)){var c=a.constructor.prototype;goog.array.forEach(jsnx.drawing.jsnx_d3.MUTATOR_METHODS_,function(b){a[b]=c[b]});delete a.bound;goog.isDef(b)&&!b||jsnx.drawing.jsnx_d3.clean_(a)}};goog.exportSymbol("jsnx.unbind",jsnx.drawing.jsnx_d3.unbind);
jsnx.drawing.jsnx_d3.clean_=function(a){jsnx.helper.forEach(a.nodes_iter(!0),function(a){goog.object.remove(a[1],jsnx.drawing.jsnx_d3.D3_DATA_NAME_)});jsnx.helper.forEach(a.edges_iter(null,!0),function(a){goog.object.remove(a[2],jsnx.drawing.jsnx_d3.D3_DATA_NAME_)})};
jsnx.drawing.jsnx_d3.default_config_={layout_attr:{charge:-120,linkDistance:60},node_shape:"circle",node_attr:{r:10},node_style:{"stroke-width":2,stroke:"#333",fill:"#999",cursor:"pointer"},edge_len:1,edge_attr:{},edge_style:{fill:"#000","stroke-width":3},label_attr:{},label_style:{"text-anchor":"middle","dominant-baseline":"central",cursor:"pointer","-webkit-user-select":"none",fill:"#000"},edge_label_attr:{},edge_label_style:{"font-size":"0.8em","text-anchor":"middle","-webkit-user-select":"none"},
edge_label_offset:{x:0,y:0.5},with_labels:!1,with_edge_labels:!1,edge_offset:10,weighted:!1,weights:"weight",weighted_stroke:!0,pan_zoom:{enabled:!0,scale:!0}};jsnx.generators={};jsnx.generators.classic={};jsnx.generators.classic.tree_edges_=function(a,b){var c=jsnx.helper.range(a),d,e,f=new goog.iter.Iterator;try{e=[c.next()]}catch(g){if(g!==goog.iter.StopIteration)throw g;return f}f.next=function(){if(0===e.length)throw goog.iter.StopIteration;return e.splice(0,1)[0]};return jsnx.helper.nested_chain(f,function(a){d=a;return jsnx.helper.range(b)},function(a){try{var b=c.next();e.push(b);return[d,b]}catch(f){if(f!==goog.iter.StopIteration)throw f;}})};
jsnx.generators.classic.full_rary_tree=function(a,b,c){c=jsnx.generators.classic.empty_graph(b,c);c.add_edges_from(jsnx.generators.classic.tree_edges_(b,a));return c};goog.exportSymbol("jsnx.generators.classic.full_rary_tree",jsnx.generators.classic.full_rary_tree);goog.exportSymbol("jsnx.full_rary_tree",jsnx.generators.classic.full_rary_tree);
jsnx.generators.classic.balanced_tree=function(a,b,c){b=1===a?2:Math.floor((1-Math.pow(a,b+1))/(1-a));c=jsnx.generators.classic.empty_graph(b,c);c.add_edges_from(jsnx.generators.classic.tree_edges_(b,a));return c};goog.exportSymbol("jsnx.generators.classic.balanced_tree",jsnx.generators.classic.balanced_tree);goog.exportSymbol("jsnx.balanced_tree",jsnx.generators.classic.balanced_tree);
jsnx.generators.classic.complete_graph=function(a,b){var c=jsnx.generators.classic.empty_graph(a,b);c.name("complete_graph("+a+")");1<a&&c.add_edges_from(c.is_directed()?jsnx.helper.permutations(jsnx.helper.range(a),2):jsnx.helper.combinations(jsnx.helper.range(a),2));return c};goog.exportSymbol("jsnx.generators.classic.complete_graph",jsnx.generators.classic.complete_graph);goog.exportSymbol("jsnx.complete_graph",jsnx.generators.classic.complete_graph);
jsnx.generators.classic.cycle_graph=function(a,b){var c=jsnx.generators.classic.path_graph(a,b);c.name("cycle_graph("+a+")");1<a&&c.add_edge(a-1,0);return c};goog.exportSymbol("jsnx.generators.classic.cycle_graph",jsnx.generators.classic.cycle_graph);goog.exportSymbol("jsnx.cycle_graph",jsnx.generators.classic.cycle_graph);
jsnx.generators.classic.empty_graph=function(a,b){a instanceof jsnx.classes.Graph&&(b=a,a=null);goog.isDefAndNotNull(a)||(a=0);var c;goog.isDefAndNotNull(b)?(c=b,c.clear()):c=new jsnx.classes.Graph;c.add_nodes_from(jsnx.helper.range(a));c.name("empty_graph("+a+")");return c};goog.exportSymbol("jsnx.generators.classic.empty_graph",jsnx.generators.classic.empty_graph);goog.exportSymbol("jsnx.empty_graph",jsnx.generators.classic.empty_graph);
jsnx.generators.classic.grid_2d_graph=function(a,b,c,d){var e=jsnx.generators.classic.empty_graph(0,d);e.name("grid_2d_graph");d=goog.iter.toArray(jsnx.helper.range(a));var f=goog.iter.toArray(jsnx.helper.range(b));goog.array.forEach(d,function(a){goog.array.forEach(f,function(b){e.add_node([a,b])})});goog.iter.forEach(jsnx.helper.range(1,a),function(a){goog.array.forEach(f,function(b){e.add_edge([a,b],[a-1,b])})});goog.array.forEach(d,function(a){goog.iter.forEach(jsnx.helper.range(1,b),function(b){e.add_edge([a,
b],[a,b-1])})});e.is_directed()&&(goog.iter.forEach(jsnx.helper.range(0,a-1),function(a){goog.array.forEach(f,function(b){e.add_edge([a,b],[a+1,b])})}),goog.array.forEach(d,function(a){goog.iter.forEach(jsnx.helper.range(0,b-1),function(b){e.add_edge([a,b],[a,b+1])})}));c&&(2<b&&(goog.array.forEach(d,function(a){e.add_edge([a,0],[a,b-1])}),e.is_directed()&&goog.array.forEach(d,function(a){e.add_edge([a,b-1],[a,0])})),2<a&&(goog.array.forEach(f,function(b){e.add_edge([0,b],[a-1,b])}),e.is_directed()&&
goog.array.forEach(f,function(b){e.add_edge([a-1,b],[0,b])})),e.name("periodic_grid_2d_graph("+a+","+b+")"));return e};goog.exportSymbol("jsnx.generators.classic.grid_2d_graph",jsnx.generators.classic.grid_2d_graph);goog.exportSymbol("jsnx.grid_2d_graph",jsnx.generators.classic.grid_2d_graph);jsnx.generators.classic.null_graph=function(a){a=jsnx.generators.classic.empty_graph(0,a);a.name("null_graph()");return a};goog.exportSymbol("jsnx.generators.classic.null_graph",jsnx.generators.classic.null_graph);
goog.exportSymbol("jsnx.null_graph",jsnx.generators.classic.null_graph);jsnx.generators.classic.path_graph=function(a,b){var c=jsnx.generators.classic.empty_graph(a,b);c.name("path_graph("+a+")");c.add_edges_from(goog.iter.map(jsnx.helper.range(a-1),function(a){return[a,a+1]}));return c};goog.exportSymbol("jsnx.generators.classic.path_graph",jsnx.generators.classic.path_graph);goog.exportSymbol("jsnx.path_graph",jsnx.generators.classic.path_graph);
jsnx.generators.classic.trivial_graph=function(a){a=jsnx.generators.classic.empty_graph(1,a);a.name("null_graph()");return a};goog.exportSymbol("jsnx.generators.classic.trivial_graph",jsnx.generators.classic.trivial_graph);goog.exportSymbol("jsnx.trivial_graph",jsnx.generators.classic.trivial_graph);jsnx.generators.random_graphs={};
jsnx.generators.random_graphs.fast_gnp_random_graph=function(a,b,c){goog.isDefAndNotNull(c)||(c=!1);var d=jsnx.generators.classic.empty_graph(a);d.name("fast_gnp_random_graph("+a+","+b+")");if(0>=b||1<=b)return jsnx.generators.random_graphs.gnp_random_graph(a,b,c);var e=1,f=-1;b=Math.log(1-b);if(c)for(d=new jsnx.classes.DiGraph(d);e<a;){c=Math.log(1-Math.random());f=f+1+Math.floor(c/b);for(e===f&&(f+=1);f>=a&&e<a;)f-=a,e+=1,e==f&&(f+=1);e<a&&d.add_edge(e,f)}else for(;e<a;){c=Math.log(1-Math.random());
for(f=f+1+Math.floor(c/b);f>=e&&e<a;)f-=e,e+=1;e<a&&d.add_edge(e,f)}return d};goog.exportSymbol("jsnx.generators.random_graphs.fast_gnp_random_graph",jsnx.generators.random_graphs.fast_gnp_random_graph);goog.exportSymbol("jsnx.fast_gnp_random_graph",jsnx.generators.random_graphs.fast_gnp_random_graph);
jsnx.generators.random_graphs.gnp_random_graph=function(a,b,c){var d;d=c?new jsnx.classes.DiGraph:new jsnx.classes.Graph;d.add_nodes_from(jsnx.helper.range(a));d.name("gnp_random_graph("+a+","+b+")");if(0>=b)return d;if(1<=b)return jsnx.generators.classic.complete_graph(a,d);a=d.is_directed()?jsnx.helper.permutations(jsnx.helper.range(a),2):jsnx.helper.combinations(jsnx.helper.range(a),2);goog.iter.forEach(a,function(a){Math.random()<b&&d.add_edge(a[0],a[1])});return d};
goog.exportSymbol("jsnx.generators.random_graphs.gnp_random_graph",jsnx.generators.random_graphs.gnp_random_graph);goog.exportSymbol("jsnx.gnp_random_graph",jsnx.generators.random_graphs.gnp_random_graph);goog.exportSymbol("jsnx.binomial_graph",jsnx.generators.random_graphs.gnp_random_graph);goog.exportSymbol("jsnx.erdos_renyi_graph",jsnx.generators.random_graphs.gnp_random_graph);jsnx.generators.degree_seq={};
jsnx.generators.degree_seq.havel_hakimi_graph=function(a,b){if(!jsnx.algorithms.graphical.is_valid_degree_sequence(a))throw new jsnx.exception.JSNetworkXError("Invalid degree sequence");if(goog.isDefAndNotNull(b)){if(b.is_directed())throw new jsnx.exception.JSNetworkXError("Directed Graph not supported");if(b.is_multigraph())throw new jsnx.exception.JSNetworkXError("Havel-Hakimi requires simple graph");}var c=a.length,d=jsnx.generators.classic.empty_graph(c,b);if(0===c||0===Math.max.apply(null,a))return d;
for(c=goog.iter.toArray(jsnx.helper.map(d,function(b){return[a[b],b]}));0<c.length;){c.sort(function(a,b){return a[0]!==b[0]?a[0]-b[0]:+a[1]-+b[1]});if(0>c[0][0])return!1;var e=c.pop();if(0===e[0])break;if(e[0]>c.length)return!1;for(var f=c.length,g=f-e[0];g<f;g++)d.add_edge(e[1],c[g][1]),c[g][0]-=1}d.name("havel_hakimi_graph "+d.order()+" nodes "+d.size()+" edges");return d};goog.exportSymbol("jsnx.generators.degree_seq.havel_hakimi_graph",jsnx.generators.degree_seq.havel_hakimi_graph);
goog.exportSymbol("jsnx.havel_hakimi_graph",jsnx.generators.degree_seq.havel_hakimi_graph);jsnx.generators.social={};
jsnx.generators.social.karate_club_graph=function(){var a=new jsnx.classes.Graph;a.add_nodes_from(jsnx.helper.range(34));a.name("Zachary's Karate Club");var b=0;goog.array.forEach("0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0;1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0;1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0;1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1;0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1;1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1;0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1;1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1;1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 1;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1;0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1;0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1;0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1;1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1;0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 0 0 0 0 0 1 1 1 0 1;0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0".split(";"),function(c){c=
c.split(" ");jsnx.helper.forEach(c,function(c,e){"1"===c&&a.add_edge(b,e)});b+=1});return a};goog.exportSymbol("jsnx.generators.social.karate_club_graph",jsnx.generators.social.karate_club_graph);goog.exportSymbol("jsnx.karate_club_graph",jsnx.generators.social.karate_club_graph);
jsnx.generators.social.davis_southern_women_graph=function(){var a=new jsnx.classes.Graph;a.add_nodes_from("Evelyn Jefferson;Laura Mandeville;Theresa Anderson;Brenda Rogers;Charlotte McDowd;Frances Anderson;Eleanor Nye;Pearl Oglethorpe;Ruth DeSand;Verne Sanderson;Myra Liddel;Katherina Rogers;Sylvia Avondale;Nora Fayette;Helen Lloyd;Dorothy Murchison;Olivia Carleton;Flora Price".split(";"),{bipartite:0});a.add_nodes_from("E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 E13 E14".split(" "),{bipartite:1});a.add_edges_from([["Evelyn Jefferson",
"E1"],["Evelyn Jefferson","E2"],["Evelyn Jefferson","E3"],["Evelyn Jefferson","E4"],["Evelyn Jefferson","E5"],["Evelyn Jefferson","E6"],["Evelyn Jefferson","E8"],["Evelyn Jefferson","E9"],["Laura Mandeville","E1"],["Laura Mandeville","E2"],["Laura Mandeville","E3"],["Laura Mandeville","E5"],["Laura Mandeville","E6"],["Laura Mandeville","E7"],["Laura Mandeville","E8"],["Theresa Anderson","E2"],["Theresa Anderson","E3"],["Theresa Anderson","E4"],["Theresa Anderson","E5"],["Theresa Anderson","E6"],["Theresa Anderson",
"E7"],["Theresa Anderson","E8"],["Theresa Anderson","E9"],["Brenda Rogers","E1"],["Brenda Rogers","E3"],["Brenda Rogers","E4"],["Brenda Rogers","E5"],["Brenda Rogers","E6"],["Brenda Rogers","E7"],["Brenda Rogers","E8"],["Charlotte McDowd","E3"],["Charlotte McDowd","E4"],["Charlotte McDowd","E5"],["Charlotte McDowd","E7"],["Frances Anderson","E3"],["Frances Anderson","E5"],["Frances Anderson","E6"],["Frances Anderson","E8"],["Eleanor Nye","E5"],["Eleanor Nye","E6"],["Eleanor Nye","E7"],["Eleanor Nye",
"E8"],["Pearl Oglethorpe","E6"],["Pearl Oglethorpe","E8"],["Pearl Oglethorpe","E9"],["Ruth DeSand","E5"],["Ruth DeSand","E7"],["Ruth DeSand","E8"],["Ruth DeSand","E9"],["Verne Sanderson","E7"],["Verne Sanderson","E8"],["Verne Sanderson","E9"],["Verne Sanderson","E12"],["Myra Liddel","E8"],["Myra Liddel","E9"],["Myra Liddel","E10"],["Myra Liddel","E12"],["Katherina Rogers","E8"],["Katherina Rogers","E9"],["Katherina Rogers","E10"],["Katherina Rogers","E12"],["Katherina Rogers","E13"],["Katherina Rogers",
"E14"],["Sylvia Avondale","E7"],["Sylvia Avondale","E8"],["Sylvia Avondale","E9"],["Sylvia Avondale","E10"],["Sylvia Avondale","E12"],["Sylvia Avondale","E13"],["Sylvia Avondale","E14"],["Nora Fayette","E6"],["Nora Fayette","E7"],["Nora Fayette","E9"],["Nora Fayette","E10"],["Nora Fayette","E11"],["Nora Fayette","E12"],["Nora Fayette","E13"],["Nora Fayette","E14"],["Helen Lloyd","E7"],["Helen Lloyd","E8"],["Helen Lloyd","E10"],["Helen Lloyd","E11"],["Helen Lloyd","E12"],["Dorothy Murchison","E8"],
["Dorothy Murchison","E9"],["Olivia Carleton","E9"],["Olivia Carleton","E11"],["Flora Price","E9"],["Flora Price","E11"]]);return a};goog.exportSymbol("jsnx.generators.social.davis_southern_women_graph",jsnx.generators.social.davis_southern_women_graph);goog.exportSymbol("jsnx.davis_southern_women_graph",jsnx.generators.social.davis_southern_women_graph);
jsnx.generators.social.florentine_families_graph=function(){var a=new jsnx.classes.Graph;a.add_edge("Acciaiuoli","Medici");a.add_edge("Castellani","Peruzzi");a.add_edge("Castellani","Strozzi");a.add_edge("Castellani","Barbadori");a.add_edge("Medici","Barbadori");a.add_edge("Medici","Ridolfi");a.add_edge("Medici","Tornabuoni");a.add_edge("Medici","Albizzi");a.add_edge("Medici","Salviati");a.add_edge("Salviati","Pazzi");a.add_edge("Peruzzi","Strozzi");a.add_edge("Peruzzi","Bischeri");a.add_edge("Strozzi",
"Ridolfi");a.add_edge("Strozzi","Bischeri");a.add_edge("Ridolfi","Tornabuoni");a.add_edge("Tornabuoni","Guadagni");a.add_edge("Albizzi","Ginori");a.add_edge("Albizzi","Guadagni");a.add_edge("Bischeri","Guadagni");a.add_edge("Guadagni","Lamberteschi");return a};goog.exportSymbol("jsnx.generators.social.florentine_families_graph",jsnx.generators.social.florentine_families_graph);goog.exportSymbol("jsnx.florentine_families_graph",jsnx.generators.social.florentine_families_graph);jsnx.generators.small={};jsnx.generators.small.make_small_undirected_graph=function(a,b){if(goog.isDefAndNotNull(b)&&b.is_directed())throw new jsnx.exception.JSNetworkXError("Directed Graph not supported");return jsnx.generators.small.make_small_graph(a,b)};goog.exportSymbol("jsnx.generators.small.make_small_undirected_graph",jsnx.generators.small.make_small_undirected_graph);
jsnx.generators.small.make_small_graph=function(a,b){var c=a[0],d=a[1],e=a[2],f=jsnx.generators.classic.empty_graph(e,b),g=f.nodes();if("adjacencylist"==c){var h=a[3];if(h.length!=e)throw new jsnx.exception.JSNetworkXError("invalid graph_description");goog.array.forEach(g,function(a){jsnx.helper.forEach(h[a],function(b){f.add_edge(b-1,a)})})}else"edgelist"==c&&jsnx.helper.forEach(a[3],function(a){var b=a[0]-1;a=a[1]-1;if(0>b||b>e-1||0>a||a>e-1)throw new jsnx.exception.JSNetworkXError("invalid graph_description");
f.add_edge(b,a)});f.name=d;return f};goog.exportSymbol("jsnx.generators.small.make_small_graph",jsnx.generators.small.make_small_graph);goog.exportSymbol("jsnx.make_small_graph",jsnx.generators.small.make_small_graph);jsnx.generators.small.bull_graph=function(a){return jsnx.generators.small.make_small_undirected_graph(["adjacencylist","Bull Graph",5,[[2,3],[1,3,4],[1,2,5],[2],[3]]],a)};goog.exportSymbol("jsnx.generators.small.bull_graph",jsnx.generators.small.bull_graph);
goog.exportSymbol("jsnx.bull_graph",jsnx.generators.small.bull_graph);jsnx.generators.small.krackhardt_kite_graph=function(a){return jsnx.generators.small.make_small_undirected_graph(["adjacencylist","Krackhardt Kite Social Network",10,[[2,3,4,6],[1,4,5,7],[1,4,6],[1,2,3,5,6,7],[2,4,7],[1,3,4,7,8],[2,4,5,6,8],[6,7,9],[8,10],[9]]],a)};goog.exportSymbol("jsnx.generators.small.krackhardt_kite_graph",jsnx.generators.small.krackhardt_kite_graph);goog.exportSymbol("jsnx.krackhardt_kite_graph",jsnx.generators.small.krackhardt_kite_graph);jsnx.relabel={};jsnx.relabel.relabel_nodes=function(a,b,c){var d=b;goog.isFunction(d.set)||goog.isFunction(d.get)||(d=new jsnx.contrib.Map(d));goog.isFunction(b)&&(d=new jsnx.contrib.Map,goog.iter.forEach(a.nodes_iter(),function(a){d.set(a,goog.asserts.assertFunction(b)(a))}));return!goog.isDef(c)||c?jsnx.relabel.relabel_copy_(a,goog.asserts.assertInstanceof(d,jsnx.contrib.Map)):jsnx.relabel.relabel_inplace_(a,goog.asserts.assertInstanceof(d,jsnx.contrib.Map))};
goog.exportSymbol("jsnx.relabel.relabel_nodes",jsnx.relabel.relabel_nodes);goog.exportSymbol("jsnx.relabel_nodes",jsnx.relabel.relabel_nodes);
jsnx.relabel.relabel_inplace_=function(a,b){var c=new jsnx.contrib.Set(b.keys()),d;if(0<c.intersection(b.values()).count()){c=new jsnx.classes.DiGraph(b);c.remove_edges_from(c.selfloop_edges());try{d=jsnx.algorithms.dag.topological_sort(c)}catch(e){if(e instanceof jsnx.exception.JSNetworkXUnfeasible)throw new jsnx.exception.JSNetworkXUnfeasible("The node label sets are overlapping and no ordering can resolve the mapping. Use copy=True.");}d.reverse()}else d=c;var f=a.is_multigraph(),g=a.is_directed(),
h;goog.iter.forEach(d,function(c){var d;if(b.has(c)){d=b.get(c);if(!a.has_node(c))throw new jsnx.exception.JSNetworkXError("Node "+c+" is not in the graph.");a.add_node(d,a.node.get(c));f?(h=goog.array.map(a.edges(c,!0,!0),function(a){return[d,a[1],a[2],a[3]]}),g&&(h=goog.array.concat(h,goog.array.map(goog.asserts.assertInstanceof(a,jsnx.classes.MultiDiGraph).in_edges(c,!0,!0),function(a){return[a[0],d,a[2],a[3]]})))):(h=goog.array.map(a.edges(c,!0),function(a){return[d,a[1],a[2]]}),g&&(h=goog.array.concat(h,
goog.array.map(a.in_edges(c,!0),function(a){return[a[0],d,a[2]]}))));a.remove_node(c);a.add_edges_from(h)}});return a};
jsnx.relabel.relabel_copy_=function(a,b){var c=new a.constructor;c.name("("+a.name()+")");a.is_multigraph()?c.add_edges_from(goog.iter.map(a.edges_iter(null,!0,!0),function(a){return[b.get(a[0],a[0]),b.get(a[1],a[1]),a[2],goog.object.clone(a[3])]})):c.add_edges_from(goog.iter.map(a.edges_iter(null,!0),function(a){return[b.get(a[0],a[0]),b.get(a[1],a[1]),goog.object.clone(a[2])]}));c.add_nodes_from(goog.iter.map(jsnx.helper.iter(a),function(a){return b.get(a,a)}));var d=new jsnx.contrib.Map;a.node.forEach(function(c){d.set(b.get(c,
c),goog.object.clone(a.node.get(c)))});d.forEach(function(a,b){c.node.set(a,b)});goog.object.extend(c.graph,goog.object.clone(a.graph));return c};
jsnx.relabel.convert_node_labels_to_integers=function(a,b,c,d){3===arguments.length&&goog.isBoolean(c)?(d=goog.asserts.assertBoolean(c),c=null):2===arguments.length&&(goog.isBoolean(b)?(d=goog.asserts.assertBoolean(b),b=null):goog.isString(b)&&(c=goog.asserts.assertString(b),b=null));goog.isDefAndNotNull(b)||(b=0);goog.isDefAndNotNull(c)||(c="default");goog.isDefAndNotNull(d)||(d=!0);a.number_of_nodes();var e=new jsnx.contrib.Map,f,g,h,k;if("default"===c)for(f=a.nodes(),g=0,h=b,k=f.length;g<k;g++,
h++)e.set(f[g],h);else if("sorted"===c)for(f=a.nodes(),goog.array.sort(f),g=0,h=b,k=f.length;g<k;g++,h++)e.set(f[g],h);else if("increasing degree"===c)for(f=goog.iter.toArray(a.degree_iter()),f.sort(function(a,b){return a[1]-b[1]}),g=0,h=b,k=f.length;g<k;g++,h++)e.set(f[g][0],h);else if("decreasing degree"===c)for(f=goog.iter.toArray(a.degree_iter()),f.sort(function(a,b){return b[1]-a[1]}),g=0,h=b,k=f.length;g<k;g++,h++)e.set(f[g][0],h);else throw new jsnx.exception.JSNetworkXError("Unkown node ordering: "+
c);g=jsnx.relabel.relabel_nodes(a,e);g.name("("+a.name()+")_with_int_labels");d||(g.node_labels=e);return g};goog.exportSymbol("jsnx.relabel.convert_node_labels_to_integers",jsnx.relabel.convert_node_labels_to_integers);goog.exportSymbol("jsnx.convert_node_labels_to_integers",jsnx.relabel.convert_node_labels_to_integers);}));