Skip to content

Instantly share code, notes, and snippets.

@adamstraube
Created October 18, 2016 04:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save adamstraube/251fbaa929c3ec299240d2cd4feaa965 to your computer and use it in GitHub Desktop.
Save adamstraube/251fbaa929c3ec299240d2cd4feaa965 to your computer and use it in GitHub Desktop.
VivaGraphJS - Chrome extension bug
/*! jQuery v3.1.0 | (c) jQuery Foundation | jquery.org/license */
!function(a,b){"use strict";"object"==typeof module&&"object"==typeof module.exports?module.exports=a.document?b(a,!0):function(a){if(!a.document)throw new Error("jQuery requires a window with a document");return b(a)}:b(a)}("undefined"!=typeof window?window:this,function(a,b){"use strict";var c=[],d=a.document,e=Object.getPrototypeOf,f=c.slice,g=c.concat,h=c.push,i=c.indexOf,j={},k=j.toString,l=j.hasOwnProperty,m=l.toString,n=m.call(Object),o={};function p(a,b){b=b||d;var c=b.createElement("script");c.text=a,b.head.appendChild(c).parentNode.removeChild(c)}var q="3.1.0",r=function(a,b){return new r.fn.init(a,b)},s=/^[\s\uFEFF\xA0]+|[\s\uFEFF\xA0]+$/g,t=/^-ms-/,u=/-([a-z])/g,v=function(a,b){return b.toUpperCase()};r.fn=r.prototype={jquery:q,constructor:r,length:0,toArray:function(){return f.call(this)},get:function(a){return null!=a?a<0?this[a+this.length]:this[a]:f.call(this)},pushStack:function(a){var b=r.merge(this.constructor(),a);return b.prevObject=this,b},each:function(a){return r.each(this,a)},map:function(a){return this.pushStack(r.map(this,function(b,c){return a.call(b,c,b)}))},slice:function(){return this.pushStack(f.apply(this,arguments))},first:function(){return this.eq(0)},last:function(){return this.eq(-1)},eq:function(a){var b=this.length,c=+a+(a<0?b:0);return this.pushStack(c>=0&&c<b?[this[c]]:[])},end:function(){return this.prevObject||this.constructor()},push:h,sort:c.sort,splice:c.splice},r.extend=r.fn.extend=function(){var a,b,c,d,e,f,g=arguments[0]||{},h=1,i=arguments.length,j=!1;for("boolean"==typeof g&&(j=g,g=arguments[h]||{},h++),"object"==typeof g||r.isFunction(g)||(g={}),h===i&&(g=this,h--);h<i;h++)if(null!=(a=arguments[h]))for(b in a)c=g[b],d=a[b],g!==d&&(j&&d&&(r.isPlainObject(d)||(e=r.isArray(d)))?(e?(e=!1,f=c&&r.isArray(c)?c:[]):f=c&&r.isPlainObject(c)?c:{},g[b]=r.extend(j,f,d)):void 0!==d&&(g[b]=d));return g},r.extend({expando:"jQuery"+(q+Math.random()).replace(/\D/g,""),isReady:!0,error:function(a){throw new Error(a)},noop:function(){},isFunction:function(a){return"function"===r.type(a)},isArray:Array.isArray,isWindow:function(a){return null!=a&&a===a.window},isNumeric:function(a){var b=r.type(a);return("number"===b||"string"===b)&&!isNaN(a-parseFloat(a))},isPlainObject:function(a){var b,c;return!(!a||"[object Object]"!==k.call(a))&&(!(b=e(a))||(c=l.call(b,"constructor")&&b.constructor,"function"==typeof c&&m.call(c)===n))},isEmptyObject:function(a){var b;for(b in a)return!1;return!0},type:function(a){return null==a?a+"":"object"==typeof a||"function"==typeof a?j[k.call(a)]||"object":typeof a},globalEval:function(a){p(a)},camelCase:function(a){return a.replace(t,"ms-").replace(u,v)},nodeName:function(a,b){return a.nodeName&&a.nodeName.toLowerCase()===b.toLowerCase()},each:function(a,b){var c,d=0;if(w(a)){for(c=a.length;d<c;d++)if(b.call(a[d],d,a[d])===!1)break}else for(d in a)if(b.call(a[d],d,a[d])===!1)break;return a},trim:function(a){return null==a?"":(a+"").replace(s,"")},makeArray:function(a,b){var c=b||[];return null!=a&&(w(Object(a))?r.merge(c,"string"==typeof a?[a]:a):h.call(c,a)),c},inArray:function(a,b,c){return null==b?-1:i.call(b,a,c)},merge:function(a,b){for(var c=+b.length,d=0,e=a.length;d<c;d++)a[e++]=b[d];return a.length=e,a},grep:function(a,b,c){for(var d,e=[],f=0,g=a.length,h=!c;f<g;f++)d=!b(a[f],f),d!==h&&e.push(a[f]);return e},map:function(a,b,c){var d,e,f=0,h=[];if(w(a))for(d=a.length;f<d;f++)e=b(a[f],f,c),null!=e&&h.push(e);else for(f in a)e=b(a[f],f,c),null!=e&&h.push(e);return g.apply([],h)},guid:1,proxy:function(a,b){var c,d,e;if("string"==typeof b&&(c=a[b],b=a,a=c),r.isFunction(a))return d=f.call(arguments,2),e=function(){return a.apply(b||this,d.concat(f.call(arguments)))},e.guid=a.guid=a.guid||r.guid++,e},now:Date.now,support:o}),"function"==typeof Symbol&&(r.fn[Symbol.iterator]=c[Symbol.iterator]),r.each("Boolean Number String Function Array Date RegExp Object Error Symbol".split(" "),function(a,b){j["[object "+b+"]"]=b.toLowerCase()});function w(a){var b=!!a&&"length"in a&&a.length,c=r.type(a);return"function"!==c&&!r.isWindow(a)&&("array"===c||0===b||"number"==typeof b&&b>0&&b-1 in a)}var x=function(a){var b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u="sizzle"+1*new Date,v=a.document,w=0,x=0,y=ha(),z=ha(),A=ha(),B=function(a,b){return a===b&&(l=!0),0},C={}.hasOwnProperty,D=[],E=D.pop,F=D.push,G=D.push,H=D.slice,I=function(a,b){for(var c=0,d=a.length;c<d;c++)if(a[c]===b)return c;return-1},J="checked|selected|async|autofocus|autoplay|controls|defer|disabled|hidden|ismap|loop|multiple|open|readonly|required|scoped",K="[\\x20\\t\\r\\n\\f]",L="(?:\\\\.|[\\w-]|[^\0-\\xa0])+",M="\\["+K+"*("+L+")(?:"+K+"*([*^$|!~]?=)"+K+"*(?:'((?:\\\\.|[^\\\\'])*)'|\"((?:\\\\.|[^\\\\\"])*)\"|("+L+"))|)"+K+"*\\]",N=":("+L+")(?:\\((('((?:\\\\.|[^\\\\'])*)'|\"((?:\\\\.|[^\\\\\"])*)\")|((?:\\\\.|[^\\\\()[\\]]|"+M+")*)|.*)\\)|)",O=new RegExp(K+"+","g"),P=new RegExp("^"+K+"+|((?:^|[^\\\\])(?:\\\\.)*)"+K+"+$","g"),Q=new RegExp("^"+K+"*,"+K+"*"),R=new RegExp("^"+K+"*([>+~]|"+K+")"+K+"*"),S=new RegExp("="+K+"*([^\\]'\"]*?)"+K+"*\\]","g"),T=new RegExp(N),U=new RegExp("^"+L+"$"),V={ID:new RegExp("^#("+L+")"),CLASS:new RegExp("^\\.("+L+")"),TAG:new RegExp("^("+L+"|[*])"),ATTR:new RegExp("^"+M),PSEUDO:new RegExp("^"+N),CHILD:new RegExp("^:(only|first|last|nth|nth-last)-(child|of-type)(?:\\("+K+"*(even|odd|(([+-]|)(\\d*)n|)"+K+"*(?:([+-]|)"+K+"*(\\d+)|))"+K+"*\\)|)","i"),bool:new RegExp("^(?:"+J+")$","i"),needsContext:new RegExp("^"+K+"*[>+~]|:(even|odd|eq|gt|lt|nth|first|last)(?:\\("+K+"*((?:-\\d)?\\d*)"+K+"*\\)|)(?=[^-]|$)","i")},W=/^(?:input|select|textarea|button)$/i,X=/^h\d$/i,Y=/^[^{]+\{\s*\[native \w/,Z=/^(?:#([\w-]+)|(\w+)|\.([\w-]+))$/,$=/[+~]/,_=new RegExp("\\\\([\\da-f]{1,6}"+K+"?|("+K+")|.)","ig"),aa=function(a,b,c){var d="0x"+b-65536;return d!==d||c?b:d<0?String.fromCharCode(d+65536):String.fromCharCode(d>>10|55296,1023&d|56320)},ba=/([\0-\x1f\x7f]|^-?\d)|^-$|[^\x80-\uFFFF\w-]/g,ca=function(a,b){return b?"\0"===a?"\ufffd":a.slice(0,-1)+"\\"+a.charCodeAt(a.length-1).toString(16)+" ":"\\"+a},da=function(){m()},ea=ta(function(a){return a.disabled===!0},{dir:"parentNode",next:"legend"});try{G.apply(D=H.call(v.childNodes),v.childNodes),D[v.childNodes.length].nodeType}catch(fa){G={apply:D.length?function(a,b){F.apply(a,H.call(b))}:function(a,b){var c=a.length,d=0;while(a[c++]=b[d++]);a.length=c-1}}}function ga(a,b,d,e){var f,h,j,k,l,o,r,s=b&&b.ownerDocument,w=b?b.nodeType:9;if(d=d||[],"string"!=typeof a||!a||1!==w&&9!==w&&11!==w)return d;if(!e&&((b?b.ownerDocument||b:v)!==n&&m(b),b=b||n,p)){if(11!==w&&(l=Z.exec(a)))if(f=l[1]){if(9===w){if(!(j=b.getElementById(f)))return d;if(j.id===f)return d.push(j),d}else if(s&&(j=s.getElementById(f))&&t(b,j)&&j.id===f)return d.push(j),d}else{if(l[2])return G.apply(d,b.getElementsByTagName(a)),d;if((f=l[3])&&c.getElementsByClassName&&b.getElementsByClassName)return G.apply(d,b.getElementsByClassName(f)),d}if(c.qsa&&!A[a+" "]&&(!q||!q.test(a))){if(1!==w)s=b,r=a;else if("object"!==b.nodeName.toLowerCase()){(k=b.getAttribute("id"))?k=k.replace(ba,ca):b.setAttribute("id",k=u),o=g(a),h=o.length;while(h--)o[h]="#"+k+" "+sa(o[h]);r=o.join(","),s=$.test(a)&&qa(b.parentNode)||b}if(r)try{return G.apply(d,s.querySelectorAll(r)),d}catch(x){}finally{k===u&&b.removeAttribute("id")}}}return i(a.replace(P,"$1"),b,d,e)}function ha(){var a=[];function b(c,e){return a.push(c+" ")>d.cacheLength&&delete b[a.shift()],b[c+" "]=e}return b}function ia(a){return a[u]=!0,a}function ja(a){var b=n.createElement("fieldset");try{return!!a(b)}catch(c){return!1}finally{b.parentNode&&b.parentNode.removeChild(b),b=null}}function ka(a,b){var c=a.split("|"),e=c.length;while(e--)d.attrHandle[c[e]]=b}function la(a,b){var c=b&&a,d=c&&1===a.nodeType&&1===b.nodeType&&a.sourceIndex-b.sourceIndex;if(d)return d;if(c)while(c=c.nextSibling)if(c===b)return-1;return a?1:-1}function ma(a){return function(b){var c=b.nodeName.toLowerCase();return"input"===c&&b.type===a}}function na(a){return function(b){var c=b.nodeName.toLowerCase();return("input"===c||"button"===c)&&b.type===a}}function oa(a){return function(b){return"label"in b&&b.disabled===a||"form"in b&&b.disabled===a||"form"in b&&b.disabled===!1&&(b.isDisabled===a||b.isDisabled!==!a&&("label"in b||!ea(b))!==a)}}function pa(a){return ia(function(b){return b=+b,ia(function(c,d){var e,f=a([],c.length,b),g=f.length;while(g--)c[e=f[g]]&&(c[e]=!(d[e]=c[e]))})})}function qa(a){return a&&"undefined"!=typeof a.getElementsByTagName&&a}c=ga.support={},f=ga.isXML=function(a){var b=a&&(a.ownerDocument||a).documentElement;return!!b&&"HTML"!==b.nodeName},m=ga.setDocument=function(a){var b,e,g=a?a.ownerDocument||a:v;return g!==n&&9===g.nodeType&&g.documentElement?(n=g,o=n.documentElement,p=!f(n),v!==n&&(e=n.defaultView)&&e.top!==e&&(e.addEventListener?e.addEventListener("unload",da,!1):e.attachEvent&&e.attachEvent("onunload",da)),c.attributes=ja(function(a){return a.className="i",!a.getAttribute("className")}),c.getElementsByTagName=ja(function(a){return a.appendChild(n.createComment("")),!a.getElementsByTagName("*").length}),c.getElementsByClassName=Y.test(n.getElementsByClassName),c.getById=ja(function(a){return o.appendChild(a).id=u,!n.getElementsByName||!n.getElementsByName(u).length}),c.getById?(d.find.ID=function(a,b){if("undefined"!=typeof b.getElementById&&p){var c=b.getElementById(a);return c?[c]:[]}},d.filter.ID=function(a){var b=a.replace(_,aa);return function(a){return a.getAttribute("id")===b}}):(delete d.find.ID,d.filter.ID=function(a){var b=a.replace(_,aa);return function(a){var c="undefined"!=typeof a.getAttributeNode&&a.getAttributeNode("id");return c&&c.value===b}}),d.find.TAG=c.getElementsByTagName?function(a,b){return"undefined"!=typeof b.getElementsByTagName?b.getElementsByTagName(a):c.qsa?b.querySelectorAll(a):void 0}:function(a,b){var c,d=[],e=0,f=b.getElementsByTagName(a);if("*"===a){while(c=f[e++])1===c.nodeType&&d.push(c);return d}return f},d.find.CLASS=c.getElementsByClassName&&function(a,b){if("undefined"!=typeof b.getElementsByClassName&&p)return b.getElementsByClassName(a)},r=[],q=[],(c.qsa=Y.test(n.querySelectorAll))&&(ja(function(a){o.appendChild(a).innerHTML="<a id='"+u+"'></a><select id='"+u+"-\r\\' msallowcapture=''><option selected=''></option></select>",a.querySelectorAll("[msallowcapture^='']").length&&q.push("[*^$]="+K+"*(?:''|\"\")"),a.querySelectorAll("[selected]").length||q.push("\\["+K+"*(?:value|"+J+")"),a.querySelectorAll("[id~="+u+"-]").length||q.push("~="),a.querySelectorAll(":checked").length||q.push(":checked"),a.querySelectorAll("a#"+u+"+*").length||q.push(".#.+[+~]")}),ja(function(a){a.innerHTML="<a href='' disabled='disabled'></a><select disabled='disabled'><option/></select>";var b=n.createElement("input");b.setAttribute("type","hidden"),a.appendChild(b).setAttribute("name","D"),a.querySelectorAll("[name=d]").length&&q.push("name"+K+"*[*^$|!~]?="),2!==a.querySelectorAll(":enabled").length&&q.push(":enabled",":disabled"),o.appendChild(a).disabled=!0,2!==a.querySelectorAll(":disabled").length&&q.push(":enabled",":disabled"),a.querySelectorAll("*,:x"),q.push(",.*:")})),(c.matchesSelector=Y.test(s=o.matches||o.webkitMatchesSelector||o.mozMatchesSelector||o.oMatchesSelector||o.msMatchesSelector))&&ja(function(a){c.disconnectedMatch=s.call(a,"*"),s.call(a,"[s!='']:x"),r.push("!=",N)}),q=q.length&&new RegExp(q.join("|")),r=r.length&&new RegExp(r.join("|")),b=Y.test(o.compareDocumentPosition),t=b||Y.test(o.contains)?function(a,b){var c=9===a.nodeType?a.documentElement:a,d=b&&b.parentNode;return a===d||!(!d||1!==d.nodeType||!(c.contains?c.contains(d):a.compareDocumentPosition&&16&a.compareDocumentPosition(d)))}:function(a,b){if(b)while(b=b.parentNode)if(b===a)return!0;return!1},B=b?function(a,b){if(a===b)return l=!0,0;var d=!a.compareDocumentPosition-!b.compareDocumentPosition;return d?d:(d=(a.ownerDocument||a)===(b.ownerDocument||b)?a.compareDocumentPosition(b):1,1&d||!c.sortDetached&&b.compareDocumentPosition(a)===d?a===n||a.ownerDocument===v&&t(v,a)?-1:b===n||b.ownerDocument===v&&t(v,b)?1:k?I(k,a)-I(k,b):0:4&d?-1:1)}:function(a,b){if(a===b)return l=!0,0;var c,d=0,e=a.parentNode,f=b.parentNode,g=[a],h=[b];if(!e||!f)return a===n?-1:b===n?1:e?-1:f?1:k?I(k,a)-I(k,b):0;if(e===f)return la(a,b);c=a;while(c=c.parentNode)g.unshift(c);c=b;while(c=c.parentNode)h.unshift(c);while(g[d]===h[d])d++;return d?la(g[d],h[d]):g[d]===v?-1:h[d]===v?1:0},n):n},ga.matches=function(a,b){return ga(a,null,null,b)},ga.matchesSelector=function(a,b){if((a.ownerDocument||a)!==n&&m(a),b=b.replace(S,"='$1']"),c.matchesSelector&&p&&!A[b+" "]&&(!r||!r.test(b))&&(!q||!q.test(b)))try{var d=s.call(a,b);if(d||c.disconnectedMatch||a.document&&11!==a.document.nodeType)return d}catch(e){}return ga(b,n,null,[a]).length>0},ga.contains=function(a,b){return(a.ownerDocument||a)!==n&&m(a),t(a,b)},ga.attr=function(a,b){(a.ownerDocument||a)!==n&&m(a);var e=d.attrHandle[b.toLowerCase()],f=e&&C.call(d.attrHandle,b.toLowerCase())?e(a,b,!p):void 0;return void 0!==f?f:c.attributes||!p?a.getAttribute(b):(f=a.getAttributeNode(b))&&f.specified?f.value:null},ga.escape=function(a){return(a+"").replace(ba,ca)},ga.error=function(a){throw new Error("Syntax error, unrecognized expression: "+a)},ga.uniqueSort=function(a){var b,d=[],e=0,f=0;if(l=!c.detectDuplicates,k=!c.sortStable&&a.slice(0),a.sort(B),l){while(b=a[f++])b===a[f]&&(e=d.push(f));while(e--)a.splice(d[e],1)}return k=null,a},e=ga.getText=function(a){var b,c="",d=0,f=a.nodeType;if(f){if(1===f||9===f||11===f){if("string"==typeof a.textContent)return a.textContent;for(a=a.firstChild;a;a=a.nextSibling)c+=e(a)}else if(3===f||4===f)return a.nodeValue}else while(b=a[d++])c+=e(b);return c},d=ga.selectors={cacheLength:50,createPseudo:ia,match:V,attrHandle:{},find:{},relative:{">":{dir:"parentNode",first:!0}," ":{dir:"parentNode"},"+":{dir:"previousSibling",first:!0},"~":{dir:"previousSibling"}},preFilter:{ATTR:function(a){return a[1]=a[1].replace(_,aa),a[3]=(a[3]||a[4]||a[5]||"").replace(_,aa),"~="===a[2]&&(a[3]=" "+a[3]+" "),a.slice(0,4)},CHILD:function(a){return a[1]=a[1].toLowerCase(),"nth"===a[1].slice(0,3)?(a[3]||ga.error(a[0]),a[4]=+(a[4]?a[5]+(a[6]||1):2*("even"===a[3]||"odd"===a[3])),a[5]=+(a[7]+a[8]||"odd"===a[3])):a[3]&&ga.error(a[0]),a},PSEUDO:function(a){var b,c=!a[6]&&a[2];return V.CHILD.test(a[0])?null:(a[3]?a[2]=a[4]||a[5]||"":c&&T.test(c)&&(b=g(c,!0))&&(b=c.indexOf(")",c.length-b)-c.length)&&(a[0]=a[0].slice(0,b),a[2]=c.slice(0,b)),a.slice(0,3))}},filter:{TAG:function(a){var b=a.replace(_,aa).toLowerCase();return"*"===a?function(){return!0}:function(a){return a.nodeName&&a.nodeName.toLowerCase()===b}},CLASS:function(a){var b=y[a+" "];return b||(b=new RegExp("(^|"+K+")"+a+"("+K+"|$)"))&&y(a,function(a){return b.test("string"==typeof a.className&&a.className||"undefined"!=typeof a.getAttribute&&a.getAttribute("class")||"")})},ATTR:function(a,b,c){return function(d){var e=ga.attr(d,a);return null==e?"!="===b:!b||(e+="","="===b?e===c:"!="===b?e!==c:"^="===b?c&&0===e.indexOf(c):"*="===b?c&&e.indexOf(c)>-1:"$="===b?c&&e.slice(-c.length)===c:"~="===b?(" "+e.replace(O," ")+" ").indexOf(c)>-1:"|="===b&&(e===c||e.slice(0,c.length+1)===c+"-"))}},CHILD:function(a,b,c,d,e){var f="nth"!==a.slice(0,3),g="last"!==a.slice(-4),h="of-type"===b;return 1===d&&0===e?function(a){return!!a.parentNode}:function(b,c,i){var j,k,l,m,n,o,p=f!==g?"nextSibling":"previousSibling",q=b.parentNode,r=h&&b.nodeName.toLowerCase(),s=!i&&!h,t=!1;if(q){if(f){while(p){m=b;while(m=m[p])if(h?m.nodeName.toLowerCase()===r:1===m.nodeType)return!1;o=p="only"===a&&!o&&"nextSibling"}return!0}if(o=[g?q.firstChild:q.lastChild],g&&s){m=q,l=m[u]||(m[u]={}),k=l[m.uniqueID]||(l[m.uniqueID]={}),j=k[a]||[],n=j[0]===w&&j[1],t=n&&j[2],m=n&&q.childNodes[n];while(m=++n&&m&&m[p]||(t=n=0)||o.pop())if(1===m.nodeType&&++t&&m===b){k[a]=[w,n,t];break}}else if(s&&(m=b,l=m[u]||(m[u]={}),k=l[m.uniqueID]||(l[m.uniqueID]={}),j=k[a]||[],n=j[0]===w&&j[1],t=n),t===!1)while(m=++n&&m&&m[p]||(t=n=0)||o.pop())if((h?m.nodeName.toLowerCase()===r:1===m.nodeType)&&++t&&(s&&(l=m[u]||(m[u]={}),k=l[m.uniqueID]||(l[m.uniqueID]={}),k[a]=[w,t]),m===b))break;return t-=e,t===d||t%d===0&&t/d>=0}}},PSEUDO:function(a,b){var c,e=d.pseudos[a]||d.setFilters[a.toLowerCase()]||ga.error("unsupported pseudo: "+a);return e[u]?e(b):e.length>1?(c=[a,a,"",b],d.setFilters.hasOwnProperty(a.toLowerCase())?ia(function(a,c){var d,f=e(a,b),g=f.length;while(g--)d=I(a,f[g]),a[d]=!(c[d]=f[g])}):function(a){return e(a,0,c)}):e}},pseudos:{not:ia(function(a){var b=[],c=[],d=h(a.replace(P,"$1"));return d[u]?ia(function(a,b,c,e){var f,g=d(a,null,e,[]),h=a.length;while(h--)(f=g[h])&&(a[h]=!(b[h]=f))}):function(a,e,f){return b[0]=a,d(b,null,f,c),b[0]=null,!c.pop()}}),has:ia(function(a){return function(b){return ga(a,b).length>0}}),contains:ia(function(a){return a=a.replace(_,aa),function(b){return(b.textContent||b.innerText||e(b)).indexOf(a)>-1}}),lang:ia(function(a){return U.test(a||"")||ga.error("unsupported lang: "+a),a=a.replace(_,aa).toLowerCase(),function(b){var c;do if(c=p?b.lang:b.getAttribute("xml:lang")||b.getAttribute("lang"))return c=c.toLowerCase(),c===a||0===c.indexOf(a+"-");while((b=b.parentNode)&&1===b.nodeType);return!1}}),target:function(b){var c=a.location&&a.location.hash;return c&&c.slice(1)===b.id},root:function(a){return a===o},focus:function(a){return a===n.activeElement&&(!n.hasFocus||n.hasFocus())&&!!(a.type||a.href||~a.tabIndex)},enabled:oa(!1),disabled:oa(!0),checked:function(a){var b=a.nodeName.toLowerCase();return"input"===b&&!!a.checked||"option"===b&&!!a.selected},selected:function(a){return a.parentNode&&a.parentNode.selectedIndex,a.selected===!0},empty:function(a){for(a=a.firstChild;a;a=a.nextSibling)if(a.nodeType<6)return!1;return!0},parent:function(a){return!d.pseudos.empty(a)},header:function(a){return X.test(a.nodeName)},input:function(a){return W.test(a.nodeName)},button:function(a){var b=a.nodeName.toLowerCase();return"input"===b&&"button"===a.type||"button"===b},text:function(a){var b;return"input"===a.nodeName.toLowerCase()&&"text"===a.type&&(null==(b=a.getAttribute("type"))||"text"===b.toLowerCase())},first:pa(function(){return[0]}),last:pa(function(a,b){return[b-1]}),eq:pa(function(a,b,c){return[c<0?c+b:c]}),even:pa(function(a,b){for(var c=0;c<b;c+=2)a.push(c);return a}),odd:pa(function(a,b){for(var c=1;c<b;c+=2)a.push(c);return a}),lt:pa(function(a,b,c){for(var d=c<0?c+b:c;--d>=0;)a.push(d);return a}),gt:pa(function(a,b,c){for(var d=c<0?c+b:c;++d<b;)a.push(d);return a})}},d.pseudos.nth=d.pseudos.eq;for(b in{radio:!0,checkbox:!0,file:!0,password:!0,image:!0})d.pseudos[b]=ma(b);for(b in{submit:!0,reset:!0})d.pseudos[b]=na(b);function ra(){}ra.prototype=d.filters=d.pseudos,d.setFilters=new ra,g=ga.tokenize=function(a,b){var c,e,f,g,h,i,j,k=z[a+" "];if(k)return b?0:k.slice(0);h=a,i=[],j=d.preFilter;while(h){c&&!(e=Q.exec(h))||(e&&(h=h.slice(e[0].length)||h),i.push(f=[])),c=!1,(e=R.exec(h))&&(c=e.shift(),f.push({value:c,type:e[0].replace(P," ")}),h=h.slice(c.length));for(g in d.filter)!(e=V[g].exec(h))||j[g]&&!(e=j[g](e))||(c=e.shift(),f.push({value:c,type:g,matches:e}),h=h.slice(c.length));if(!c)break}return b?h.length:h?ga.error(a):z(a,i).slice(0)};function sa(a){for(var b=0,c=a.length,d="";b<c;b++)d+=a[b].value;return d}function ta(a,b,c){var d=b.dir,e=b.next,f=e||d,g=c&&"parentNode"===f,h=x++;return b.first?function(b,c,e){while(b=b[d])if(1===b.nodeType||g)return a(b,c,e)}:function(b,c,i){var j,k,l,m=[w,h];if(i){while(b=b[d])if((1===b.nodeType||g)&&a(b,c,i))return!0}else while(b=b[d])if(1===b.nodeType||g)if(l=b[u]||(b[u]={}),k=l[b.uniqueID]||(l[b.uniqueID]={}),e&&e===b.nodeName.toLowerCase())b=b[d]||b;else{if((j=k[f])&&j[0]===w&&j[1]===h)return m[2]=j[2];if(k[f]=m,m[2]=a(b,c,i))return!0}}}function ua(a){return a.length>1?function(b,c,d){var e=a.length;while(e--)if(!a[e](b,c,d))return!1;return!0}:a[0]}function va(a,b,c){for(var d=0,e=b.length;d<e;d++)ga(a,b[d],c);return c}function wa(a,b,c,d,e){for(var f,g=[],h=0,i=a.length,j=null!=b;h<i;h++)(f=a[h])&&(c&&!c(f,d,e)||(g.push(f),j&&b.push(h)));return g}function xa(a,b,c,d,e,f){return d&&!d[u]&&(d=xa(d)),e&&!e[u]&&(e=xa(e,f)),ia(function(f,g,h,i){var j,k,l,m=[],n=[],o=g.length,p=f||va(b||"*",h.nodeType?[h]:h,[]),q=!a||!f&&b?p:wa(p,m,a,h,i),r=c?e||(f?a:o||d)?[]:g:q;if(c&&c(q,r,h,i),d){j=wa(r,n),d(j,[],h,i),k=j.length;while(k--)(l=j[k])&&(r[n[k]]=!(q[n[k]]=l))}if(f){if(e||a){if(e){j=[],k=r.length;while(k--)(l=r[k])&&j.push(q[k]=l);e(null,r=[],j,i)}k=r.length;while(k--)(l=r[k])&&(j=e?I(f,l):m[k])>-1&&(f[j]=!(g[j]=l))}}else r=wa(r===g?r.splice(o,r.length):r),e?e(null,g,r,i):G.apply(g,r)})}function ya(a){for(var b,c,e,f=a.length,g=d.relative[a[0].type],h=g||d.relative[" "],i=g?1:0,k=ta(function(a){return a===b},h,!0),l=ta(function(a){return I(b,a)>-1},h,!0),m=[function(a,c,d){var e=!g&&(d||c!==j)||((b=c).nodeType?k(a,c,d):l(a,c,d));return b=null,e}];i<f;i++)if(c=d.relative[a[i].type])m=[ta(ua(m),c)];else{if(c=d.filter[a[i].type].apply(null,a[i].matches),c[u]){for(e=++i;e<f;e++)if(d.relative[a[e].type])break;return xa(i>1&&ua(m),i>1&&sa(a.slice(0,i-1).concat({value:" "===a[i-2].type?"*":""})).replace(P,"$1"),c,i<e&&ya(a.slice(i,e)),e<f&&ya(a=a.slice(e)),e<f&&sa(a))}m.push(c)}return ua(m)}function za(a,b){var c=b.length>0,e=a.length>0,f=function(f,g,h,i,k){var l,o,q,r=0,s="0",t=f&&[],u=[],v=j,x=f||e&&d.find.TAG("*",k),y=w+=null==v?1:Math.random()||.1,z=x.length;for(k&&(j=g===n||g||k);s!==z&&null!=(l=x[s]);s++){if(e&&l){o=0,g||l.ownerDocument===n||(m(l),h=!p);while(q=a[o++])if(q(l,g||n,h)){i.push(l);break}k&&(w=y)}c&&((l=!q&&l)&&r--,f&&t.push(l))}if(r+=s,c&&s!==r){o=0;while(q=b[o++])q(t,u,g,h);if(f){if(r>0)while(s--)t[s]||u[s]||(u[s]=E.call(i));u=wa(u)}G.apply(i,u),k&&!f&&u.length>0&&r+b.length>1&&ga.uniqueSort(i)}return k&&(w=y,j=v),t};return c?ia(f):f}return h=ga.compile=function(a,b){var c,d=[],e=[],f=A[a+" "];if(!f){b||(b=g(a)),c=b.length;while(c--)f=ya(b[c]),f[u]?d.push(f):e.push(f);f=A(a,za(e,d)),f.selector=a}return f},i=ga.select=function(a,b,e,f){var i,j,k,l,m,n="function"==typeof a&&a,o=!f&&g(a=n.selector||a);if(e=e||[],1===o.length){if(j=o[0]=o[0].slice(0),j.length>2&&"ID"===(k=j[0]).type&&c.getById&&9===b.nodeType&&p&&d.relative[j[1].type]){if(b=(d.find.ID(k.matches[0].replace(_,aa),b)||[])[0],!b)return e;n&&(b=b.parentNode),a=a.slice(j.shift().value.length)}i=V.needsContext.test(a)?0:j.length;while(i--){if(k=j[i],d.relative[l=k.type])break;if((m=d.find[l])&&(f=m(k.matches[0].replace(_,aa),$.test(j[0].type)&&qa(b.parentNode)||b))){if(j.splice(i,1),a=f.length&&sa(j),!a)return G.apply(e,f),e;break}}}return(n||h(a,o))(f,b,!p,e,!b||$.test(a)&&qa(b.parentNode)||b),e},c.sortStable=u.split("").sort(B).join("")===u,c.detectDuplicates=!!l,m(),c.sortDetached=ja(function(a){return 1&a.compareDocumentPosition(n.createElement("fieldset"))}),ja(function(a){return a.innerHTML="<a href='#'></a>","#"===a.firstChild.getAttribute("href")})||ka("type|href|height|width",function(a,b,c){if(!c)return a.getAttribute(b,"type"===b.toLowerCase()?1:2)}),c.attributes&&ja(function(a){return a.innerHTML="<input/>",a.firstChild.setAttribute("value",""),""===a.firstChild.getAttribute("value")})||ka("value",function(a,b,c){if(!c&&"input"===a.nodeName.toLowerCase())return a.defaultValue}),ja(function(a){return null==a.getAttribute("disabled")})||ka(J,function(a,b,c){var d;if(!c)return a[b]===!0?b.toLowerCase():(d=a.getAttributeNode(b))&&d.specified?d.value:null}),ga}(a);r.find=x,r.expr=x.selectors,r.expr[":"]=r.expr.pseudos,r.uniqueSort=r.unique=x.uniqueSort,r.text=x.getText,r.isXMLDoc=x.isXML,r.contains=x.contains,r.escapeSelector=x.escape;var y=function(a,b,c){var d=[],e=void 0!==c;while((a=a[b])&&9!==a.nodeType)if(1===a.nodeType){if(e&&r(a).is(c))break;d.push(a)}return d},z=function(a,b){for(var c=[];a;a=a.nextSibling)1===a.nodeType&&a!==b&&c.push(a);return c},A=r.expr.match.needsContext,B=/^<([a-z][^\/\0>:\x20\t\r\n\f]*)[\x20\t\r\n\f]*\/?>(?:<\/\1>|)$/i,C=/^.[^:#\[\.,]*$/;function D(a,b,c){if(r.isFunction(b))return r.grep(a,function(a,d){return!!b.call(a,d,a)!==c});if(b.nodeType)return r.grep(a,function(a){return a===b!==c});if("string"==typeof b){if(C.test(b))return r.filter(b,a,c);b=r.filter(b,a)}return r.grep(a,function(a){return i.call(b,a)>-1!==c&&1===a.nodeType})}r.filter=function(a,b,c){var d=b[0];return c&&(a=":not("+a+")"),1===b.length&&1===d.nodeType?r.find.matchesSelector(d,a)?[d]:[]:r.find.matches(a,r.grep(b,function(a){return 1===a.nodeType}))},r.fn.extend({find:function(a){var b,c,d=this.length,e=this;if("string"!=typeof a)return this.pushStack(r(a).filter(function(){for(b=0;b<d;b++)if(r.contains(e[b],this))return!0}));for(c=this.pushStack([]),b=0;b<d;b++)r.find(a,e[b],c);return d>1?r.uniqueSort(c):c},filter:function(a){return this.pushStack(D(this,a||[],!1))},not:function(a){return this.pushStack(D(this,a||[],!0))},is:function(a){return!!D(this,"string"==typeof a&&A.test(a)?r(a):a||[],!1).length}});var E,F=/^(?:\s*(<[\w\W]+>)[^>]*|#([\w-]+))$/,G=r.fn.init=function(a,b,c){var e,f;if(!a)return this;if(c=c||E,"string"==typeof a){if(e="<"===a[0]&&">"===a[a.length-1]&&a.length>=3?[null,a,null]:F.exec(a),!e||!e[1]&&b)return!b||b.jquery?(b||c).find(a):this.constructor(b).find(a);if(e[1]){if(b=b instanceof r?b[0]:b,r.merge(this,r.parseHTML(e[1],b&&b.nodeType?b.ownerDocument||b:d,!0)),B.test(e[1])&&r.isPlainObject(b))for(e in b)r.isFunction(this[e])?this[e](b[e]):this.attr(e,b[e]);return this}return f=d.getElementById(e[2]),f&&(this[0]=f,this.length=1),this}return a.nodeType?(this[0]=a,this.length=1,this):r.isFunction(a)?void 0!==c.ready?c.ready(a):a(r):r.makeArray(a,this)};G.prototype=r.fn,E=r(d);var H=/^(?:parents|prev(?:Until|All))/,I={children:!0,contents:!0,next:!0,prev:!0};r.fn.extend({has:function(a){var b=r(a,this),c=b.length;return this.filter(function(){for(var a=0;a<c;a++)if(r.contains(this,b[a]))return!0})},closest:function(a,b){var c,d=0,e=this.length,f=[],g="string"!=typeof a&&r(a);if(!A.test(a))for(;d<e;d++)for(c=this[d];c&&c!==b;c=c.parentNode)if(c.nodeType<11&&(g?g.index(c)>-1:1===c.nodeType&&r.find.matchesSelector(c,a))){f.push(c);break}return this.pushStack(f.length>1?r.uniqueSort(f):f)},index:function(a){return a?"string"==typeof a?i.call(r(a),this[0]):i.call(this,a.jquery?a[0]:a):this[0]&&this[0].parentNode?this.first().prevAll().length:-1},add:function(a,b){return this.pushStack(r.uniqueSort(r.merge(this.get(),r(a,b))))},addBack:function(a){return this.add(null==a?this.prevObject:this.prevObject.filter(a))}});function J(a,b){while((a=a[b])&&1!==a.nodeType);return a}r.each({parent:function(a){var b=a.parentNode;return b&&11!==b.nodeType?b:null},parents:function(a){return y(a,"parentNode")},parentsUntil:function(a,b,c){return y(a,"parentNode",c)},next:function(a){return J(a,"nextSibling")},prev:function(a){return J(a,"previousSibling")},nextAll:function(a){return y(a,"nextSibling")},prevAll:function(a){return y(a,"previousSibling")},nextUntil:function(a,b,c){return y(a,"nextSibling",c)},prevUntil:function(a,b,c){return y(a,"previousSibling",c)},siblings:function(a){return z((a.parentNode||{}).firstChild,a)},children:function(a){return z(a.firstChild)},contents:function(a){return a.contentDocument||r.merge([],a.childNodes)}},function(a,b){r.fn[a]=function(c,d){var e=r.map(this,b,c);return"Until"!==a.slice(-5)&&(d=c),d&&"string"==typeof d&&(e=r.filter(d,e)),this.length>1&&(I[a]||r.uniqueSort(e),H.test(a)&&e.reverse()),this.pushStack(e)}});var K=/\S+/g;function L(a){var b={};return r.each(a.match(K)||[],function(a,c){b[c]=!0}),b}r.Callbacks=function(a){a="string"==typeof a?L(a):r.extend({},a);var b,c,d,e,f=[],g=[],h=-1,i=function(){for(e=a.once,d=b=!0;g.length;h=-1){c=g.shift();while(++h<f.length)f[h].apply(c[0],c[1])===!1&&a.stopOnFalse&&(h=f.length,c=!1)}a.memory||(c=!1),b=!1,e&&(f=c?[]:"")},j={add:function(){return f&&(c&&!b&&(h=f.length-1,g.push(c)),function d(b){r.each(b,function(b,c){r.isFunction(c)?a.unique&&j.has(c)||f.push(c):c&&c.length&&"string"!==r.type(c)&&d(c)})}(arguments),c&&!b&&i()),this},remove:function(){return r.each(arguments,function(a,b){var c;while((c=r.inArray(b,f,c))>-1)f.splice(c,1),c<=h&&h--}),this},has:function(a){return a?r.inArray(a,f)>-1:f.length>0},empty:function(){return f&&(f=[]),this},disable:function(){return e=g=[],f=c="",this},disabled:function(){return!f},lock:function(){return e=g=[],c||b||(f=c=""),this},locked:function(){return!!e},fireWith:function(a,c){return e||(c=c||[],c=[a,c.slice?c.slice():c],g.push(c),b||i()),this},fire:function(){return j.fireWith(this,arguments),this},fired:function(){return!!d}};return j};function M(a){return a}function N(a){throw a}function O(a,b,c){var d;try{a&&r.isFunction(d=a.promise)?d.call(a).done(b).fail(c):a&&r.isFunction(d=a.then)?d.call(a,b,c):b.call(void 0,a)}catch(a){c.call(void 0,a)}}r.extend({Deferred:function(b){var c=[["notify","progress",r.Callbacks("memory"),r.Callbacks("memory"),2],["resolve","done",r.Callbacks("once memory"),r.Callbacks("once memory"),0,"resolved"],["reject","fail",r.Callbacks("once memory"),r.Callbacks("once memory"),1,"rejected"]],d="pending",e={state:function(){return d},always:function(){return f.done(arguments).fail(arguments),this},"catch":function(a){return e.then(null,a)},pipe:function(){var a=arguments;return r.Deferred(function(b){r.each(c,function(c,d){var e=r.isFunction(a[d[4]])&&a[d[4]];f[d[1]](function(){var a=e&&e.apply(this,arguments);a&&r.isFunction(a.promise)?a.promise().progress(b.notify).done(b.resolve).fail(b.reject):b[d[0]+"With"](this,e?[a]:arguments)})}),a=null}).promise()},then:function(b,d,e){var f=0;function g(b,c,d,e){return function(){var h=this,i=arguments,j=function(){var a,j;if(!(b<f)){if(a=d.apply(h,i),a===c.promise())throw new TypeError("Thenable self-resolution");j=a&&("object"==typeof a||"function"==typeof a)&&a.then,r.isFunction(j)?e?j.call(a,g(f,c,M,e),g(f,c,N,e)):(f++,j.call(a,g(f,c,M,e),g(f,c,N,e),g(f,c,M,c.notifyWith))):(d!==M&&(h=void 0,i=[a]),(e||c.resolveWith)(h,i))}},k=e?j:function(){try{j()}catch(a){r.Deferred.exceptionHook&&r.Deferred.exceptionHook(a,k.stackTrace),b+1>=f&&(d!==N&&(h=void 0,i=[a]),c.rejectWith(h,i))}};b?k():(r.Deferred.getStackHook&&(k.stackTrace=r.Deferred.getStackHook()),a.setTimeout(k))}}return r.Deferred(function(a){c[0][3].add(g(0,a,r.isFunction(e)?e:M,a.notifyWith)),c[1][3].add(g(0,a,r.isFunction(b)?b:M)),c[2][3].add(g(0,a,r.isFunction(d)?d:N))}).promise()},promise:function(a){return null!=a?r.extend(a,e):e}},f={};return r.each(c,function(a,b){var g=b[2],h=b[5];e[b[1]]=g.add,h&&g.add(function(){d=h},c[3-a][2].disable,c[0][2].lock),g.add(b[3].fire),f[b[0]]=function(){return f[b[0]+"With"](this===f?void 0:this,arguments),this},f[b[0]+"With"]=g.fireWith}),e.promise(f),b&&b.call(f,f),f},when:function(a){var b=arguments.length,c=b,d=Array(c),e=f.call(arguments),g=r.Deferred(),h=function(a){return function(c){d[a]=this,e[a]=arguments.length>1?f.call(arguments):c,--b||g.resolveWith(d,e)}};if(b<=1&&(O(a,g.done(h(c)).resolve,g.reject),"pending"===g.state()||r.isFunction(e[c]&&e[c].then)))return g.then();while(c--)O(e[c],h(c),g.reject);return g.promise()}});var P=/^(Eval|Internal|Range|Reference|Syntax|Type|URI)Error$/;r.Deferred.exceptionHook=function(b,c){a.console&&a.console.warn&&b&&P.test(b.name)&&a.console.warn("jQuery.Deferred exception: "+b.message,b.stack,c)},r.readyException=function(b){a.setTimeout(function(){throw b})};var Q=r.Deferred();r.fn.ready=function(a){return Q.then(a)["catch"](function(a){r.readyException(a)}),this},r.extend({isReady:!1,readyWait:1,holdReady:function(a){a?r.readyWait++:r.ready(!0)},ready:function(a){(a===!0?--r.readyWait:r.isReady)||(r.isReady=!0,a!==!0&&--r.readyWait>0||Q.resolveWith(d,[r]))}}),r.ready.then=Q.then;function R(){d.removeEventListener("DOMContentLoaded",R),a.removeEventListener("load",R),r.ready()}"complete"===d.readyState||"loading"!==d.readyState&&!d.documentElement.doScroll?a.setTimeout(r.ready):(d.addEventListener("DOMContentLoaded",R),a.addEventListener("load",R));var S=function(a,b,c,d,e,f,g){var h=0,i=a.length,j=null==c;if("object"===r.type(c)){e=!0;for(h in c)S(a,b,h,c[h],!0,f,g)}else if(void 0!==d&&(e=!0,
r.isFunction(d)||(g=!0),j&&(g?(b.call(a,d),b=null):(j=b,b=function(a,b,c){return j.call(r(a),c)})),b))for(;h<i;h++)b(a[h],c,g?d:d.call(a[h],h,b(a[h],c)));return e?a:j?b.call(a):i?b(a[0],c):f},T=function(a){return 1===a.nodeType||9===a.nodeType||!+a.nodeType};function U(){this.expando=r.expando+U.uid++}U.uid=1,U.prototype={cache:function(a){var b=a[this.expando];return b||(b={},T(a)&&(a.nodeType?a[this.expando]=b:Object.defineProperty(a,this.expando,{value:b,configurable:!0}))),b},set:function(a,b,c){var d,e=this.cache(a);if("string"==typeof b)e[r.camelCase(b)]=c;else for(d in b)e[r.camelCase(d)]=b[d];return e},get:function(a,b){return void 0===b?this.cache(a):a[this.expando]&&a[this.expando][r.camelCase(b)]},access:function(a,b,c){return void 0===b||b&&"string"==typeof b&&void 0===c?this.get(a,b):(this.set(a,b,c),void 0!==c?c:b)},remove:function(a,b){var c,d=a[this.expando];if(void 0!==d){if(void 0!==b){r.isArray(b)?b=b.map(r.camelCase):(b=r.camelCase(b),b=b in d?[b]:b.match(K)||[]),c=b.length;while(c--)delete d[b[c]]}(void 0===b||r.isEmptyObject(d))&&(a.nodeType?a[this.expando]=void 0:delete a[this.expando])}},hasData:function(a){var b=a[this.expando];return void 0!==b&&!r.isEmptyObject(b)}};var V=new U,W=new U,X=/^(?:\{[\w\W]*\}|\[[\w\W]*\])$/,Y=/[A-Z]/g;function Z(a,b,c){var d;if(void 0===c&&1===a.nodeType)if(d="data-"+b.replace(Y,"-$&").toLowerCase(),c=a.getAttribute(d),"string"==typeof c){try{c="true"===c||"false"!==c&&("null"===c?null:+c+""===c?+c:X.test(c)?JSON.parse(c):c)}catch(e){}W.set(a,b,c)}else c=void 0;return c}r.extend({hasData:function(a){return W.hasData(a)||V.hasData(a)},data:function(a,b,c){return W.access(a,b,c)},removeData:function(a,b){W.remove(a,b)},_data:function(a,b,c){return V.access(a,b,c)},_removeData:function(a,b){V.remove(a,b)}}),r.fn.extend({data:function(a,b){var c,d,e,f=this[0],g=f&&f.attributes;if(void 0===a){if(this.length&&(e=W.get(f),1===f.nodeType&&!V.get(f,"hasDataAttrs"))){c=g.length;while(c--)g[c]&&(d=g[c].name,0===d.indexOf("data-")&&(d=r.camelCase(d.slice(5)),Z(f,d,e[d])));V.set(f,"hasDataAttrs",!0)}return e}return"object"==typeof a?this.each(function(){W.set(this,a)}):S(this,function(b){var c;if(f&&void 0===b){if(c=W.get(f,a),void 0!==c)return c;if(c=Z(f,a),void 0!==c)return c}else this.each(function(){W.set(this,a,b)})},null,b,arguments.length>1,null,!0)},removeData:function(a){return this.each(function(){W.remove(this,a)})}}),r.extend({queue:function(a,b,c){var d;if(a)return b=(b||"fx")+"queue",d=V.get(a,b),c&&(!d||r.isArray(c)?d=V.access(a,b,r.makeArray(c)):d.push(c)),d||[]},dequeue:function(a,b){b=b||"fx";var c=r.queue(a,b),d=c.length,e=c.shift(),f=r._queueHooks(a,b),g=function(){r.dequeue(a,b)};"inprogress"===e&&(e=c.shift(),d--),e&&("fx"===b&&c.unshift("inprogress"),delete f.stop,e.call(a,g,f)),!d&&f&&f.empty.fire()},_queueHooks:function(a,b){var c=b+"queueHooks";return V.get(a,c)||V.access(a,c,{empty:r.Callbacks("once memory").add(function(){V.remove(a,[b+"queue",c])})})}}),r.fn.extend({queue:function(a,b){var c=2;return"string"!=typeof a&&(b=a,a="fx",c--),arguments.length<c?r.queue(this[0],a):void 0===b?this:this.each(function(){var c=r.queue(this,a,b);r._queueHooks(this,a),"fx"===a&&"inprogress"!==c[0]&&r.dequeue(this,a)})},dequeue:function(a){return this.each(function(){r.dequeue(this,a)})},clearQueue:function(a){return this.queue(a||"fx",[])},promise:function(a,b){var c,d=1,e=r.Deferred(),f=this,g=this.length,h=function(){--d||e.resolveWith(f,[f])};"string"!=typeof a&&(b=a,a=void 0),a=a||"fx";while(g--)c=V.get(f[g],a+"queueHooks"),c&&c.empty&&(d++,c.empty.add(h));return h(),e.promise(b)}});var $=/[+-]?(?:\d*\.|)\d+(?:[eE][+-]?\d+|)/.source,_=new RegExp("^(?:([+-])=|)("+$+")([a-z%]*)$","i"),aa=["Top","Right","Bottom","Left"],ba=function(a,b){return a=b||a,"none"===a.style.display||""===a.style.display&&r.contains(a.ownerDocument,a)&&"none"===r.css(a,"display")},ca=function(a,b,c,d){var e,f,g={};for(f in b)g[f]=a.style[f],a.style[f]=b[f];e=c.apply(a,d||[]);for(f in b)a.style[f]=g[f];return e};function da(a,b,c,d){var e,f=1,g=20,h=d?function(){return d.cur()}:function(){return r.css(a,b,"")},i=h(),j=c&&c[3]||(r.cssNumber[b]?"":"px"),k=(r.cssNumber[b]||"px"!==j&&+i)&&_.exec(r.css(a,b));if(k&&k[3]!==j){j=j||k[3],c=c||[],k=+i||1;do f=f||".5",k/=f,r.style(a,b,k+j);while(f!==(f=h()/i)&&1!==f&&--g)}return c&&(k=+k||+i||0,e=c[1]?k+(c[1]+1)*c[2]:+c[2],d&&(d.unit=j,d.start=k,d.end=e)),e}var ea={};function fa(a){var b,c=a.ownerDocument,d=a.nodeName,e=ea[d];return e?e:(b=c.body.appendChild(c.createElement(d)),e=r.css(b,"display"),b.parentNode.removeChild(b),"none"===e&&(e="block"),ea[d]=e,e)}function ga(a,b){for(var c,d,e=[],f=0,g=a.length;f<g;f++)d=a[f],d.style&&(c=d.style.display,b?("none"===c&&(e[f]=V.get(d,"display")||null,e[f]||(d.style.display="")),""===d.style.display&&ba(d)&&(e[f]=fa(d))):"none"!==c&&(e[f]="none",V.set(d,"display",c)));for(f=0;f<g;f++)null!=e[f]&&(a[f].style.display=e[f]);return a}r.fn.extend({show:function(){return ga(this,!0)},hide:function(){return ga(this)},toggle:function(a){return"boolean"==typeof a?a?this.show():this.hide():this.each(function(){ba(this)?r(this).show():r(this).hide()})}});var ha=/^(?:checkbox|radio)$/i,ia=/<([a-z][^\/\0>\x20\t\r\n\f]+)/i,ja=/^$|\/(?:java|ecma)script/i,ka={option:[1,"<select multiple='multiple'>","</select>"],thead:[1,"<table>","</table>"],col:[2,"<table><colgroup>","</colgroup></table>"],tr:[2,"<table><tbody>","</tbody></table>"],td:[3,"<table><tbody><tr>","</tr></tbody></table>"],_default:[0,"",""]};ka.optgroup=ka.option,ka.tbody=ka.tfoot=ka.colgroup=ka.caption=ka.thead,ka.th=ka.td;function la(a,b){var c="undefined"!=typeof a.getElementsByTagName?a.getElementsByTagName(b||"*"):"undefined"!=typeof a.querySelectorAll?a.querySelectorAll(b||"*"):[];return void 0===b||b&&r.nodeName(a,b)?r.merge([a],c):c}function ma(a,b){for(var c=0,d=a.length;c<d;c++)V.set(a[c],"globalEval",!b||V.get(b[c],"globalEval"))}var na=/<|&#?\w+;/;function oa(a,b,c,d,e){for(var f,g,h,i,j,k,l=b.createDocumentFragment(),m=[],n=0,o=a.length;n<o;n++)if(f=a[n],f||0===f)if("object"===r.type(f))r.merge(m,f.nodeType?[f]:f);else if(na.test(f)){g=g||l.appendChild(b.createElement("div")),h=(ia.exec(f)||["",""])[1].toLowerCase(),i=ka[h]||ka._default,g.innerHTML=i[1]+r.htmlPrefilter(f)+i[2],k=i[0];while(k--)g=g.lastChild;r.merge(m,g.childNodes),g=l.firstChild,g.textContent=""}else m.push(b.createTextNode(f));l.textContent="",n=0;while(f=m[n++])if(d&&r.inArray(f,d)>-1)e&&e.push(f);else if(j=r.contains(f.ownerDocument,f),g=la(l.appendChild(f),"script"),j&&ma(g),c){k=0;while(f=g[k++])ja.test(f.type||"")&&c.push(f)}return l}!function(){var a=d.createDocumentFragment(),b=a.appendChild(d.createElement("div")),c=d.createElement("input");c.setAttribute("type","radio"),c.setAttribute("checked","checked"),c.setAttribute("name","t"),b.appendChild(c),o.checkClone=b.cloneNode(!0).cloneNode(!0).lastChild.checked,b.innerHTML="<textarea>x</textarea>",o.noCloneChecked=!!b.cloneNode(!0).lastChild.defaultValue}();var pa=d.documentElement,qa=/^key/,ra=/^(?:mouse|pointer|contextmenu|drag|drop)|click/,sa=/^([^.]*)(?:\.(.+)|)/;function ta(){return!0}function ua(){return!1}function va(){try{return d.activeElement}catch(a){}}function wa(a,b,c,d,e,f){var g,h;if("object"==typeof b){"string"!=typeof c&&(d=d||c,c=void 0);for(h in b)wa(a,h,c,d,b[h],f);return a}if(null==d&&null==e?(e=c,d=c=void 0):null==e&&("string"==typeof c?(e=d,d=void 0):(e=d,d=c,c=void 0)),e===!1)e=ua;else if(!e)return a;return 1===f&&(g=e,e=function(a){return r().off(a),g.apply(this,arguments)},e.guid=g.guid||(g.guid=r.guid++)),a.each(function(){r.event.add(this,b,e,d,c)})}r.event={global:{},add:function(a,b,c,d,e){var f,g,h,i,j,k,l,m,n,o,p,q=V.get(a);if(q){c.handler&&(f=c,c=f.handler,e=f.selector),e&&r.find.matchesSelector(pa,e),c.guid||(c.guid=r.guid++),(i=q.events)||(i=q.events={}),(g=q.handle)||(g=q.handle=function(b){return"undefined"!=typeof r&&r.event.triggered!==b.type?r.event.dispatch.apply(a,arguments):void 0}),b=(b||"").match(K)||[""],j=b.length;while(j--)h=sa.exec(b[j])||[],n=p=h[1],o=(h[2]||"").split(".").sort(),n&&(l=r.event.special[n]||{},n=(e?l.delegateType:l.bindType)||n,l=r.event.special[n]||{},k=r.extend({type:n,origType:p,data:d,handler:c,guid:c.guid,selector:e,needsContext:e&&r.expr.match.needsContext.test(e),namespace:o.join(".")},f),(m=i[n])||(m=i[n]=[],m.delegateCount=0,l.setup&&l.setup.call(a,d,o,g)!==!1||a.addEventListener&&a.addEventListener(n,g)),l.add&&(l.add.call(a,k),k.handler.guid||(k.handler.guid=c.guid)),e?m.splice(m.delegateCount++,0,k):m.push(k),r.event.global[n]=!0)}},remove:function(a,b,c,d,e){var f,g,h,i,j,k,l,m,n,o,p,q=V.hasData(a)&&V.get(a);if(q&&(i=q.events)){b=(b||"").match(K)||[""],j=b.length;while(j--)if(h=sa.exec(b[j])||[],n=p=h[1],o=(h[2]||"").split(".").sort(),n){l=r.event.special[n]||{},n=(d?l.delegateType:l.bindType)||n,m=i[n]||[],h=h[2]&&new RegExp("(^|\\.)"+o.join("\\.(?:.*\\.|)")+"(\\.|$)"),g=f=m.length;while(f--)k=m[f],!e&&p!==k.origType||c&&c.guid!==k.guid||h&&!h.test(k.namespace)||d&&d!==k.selector&&("**"!==d||!k.selector)||(m.splice(f,1),k.selector&&m.delegateCount--,l.remove&&l.remove.call(a,k));g&&!m.length&&(l.teardown&&l.teardown.call(a,o,q.handle)!==!1||r.removeEvent(a,n,q.handle),delete i[n])}else for(n in i)r.event.remove(a,n+b[j],c,d,!0);r.isEmptyObject(i)&&V.remove(a,"handle events")}},dispatch:function(a){var b=r.event.fix(a),c,d,e,f,g,h,i=new Array(arguments.length),j=(V.get(this,"events")||{})[b.type]||[],k=r.event.special[b.type]||{};for(i[0]=b,c=1;c<arguments.length;c++)i[c]=arguments[c];if(b.delegateTarget=this,!k.preDispatch||k.preDispatch.call(this,b)!==!1){h=r.event.handlers.call(this,b,j),c=0;while((f=h[c++])&&!b.isPropagationStopped()){b.currentTarget=f.elem,d=0;while((g=f.handlers[d++])&&!b.isImmediatePropagationStopped())b.rnamespace&&!b.rnamespace.test(g.namespace)||(b.handleObj=g,b.data=g.data,e=((r.event.special[g.origType]||{}).handle||g.handler).apply(f.elem,i),void 0!==e&&(b.result=e)===!1&&(b.preventDefault(),b.stopPropagation()))}return k.postDispatch&&k.postDispatch.call(this,b),b.result}},handlers:function(a,b){var c,d,e,f,g=[],h=b.delegateCount,i=a.target;if(h&&i.nodeType&&("click"!==a.type||isNaN(a.button)||a.button<1))for(;i!==this;i=i.parentNode||this)if(1===i.nodeType&&(i.disabled!==!0||"click"!==a.type)){for(d=[],c=0;c<h;c++)f=b[c],e=f.selector+" ",void 0===d[e]&&(d[e]=f.needsContext?r(e,this).index(i)>-1:r.find(e,this,null,[i]).length),d[e]&&d.push(f);d.length&&g.push({elem:i,handlers:d})}return h<b.length&&g.push({elem:this,handlers:b.slice(h)}),g},addProp:function(a,b){Object.defineProperty(r.Event.prototype,a,{enumerable:!0,configurable:!0,get:r.isFunction(b)?function(){if(this.originalEvent)return b(this.originalEvent)}:function(){if(this.originalEvent)return this.originalEvent[a]},set:function(b){Object.defineProperty(this,a,{enumerable:!0,configurable:!0,writable:!0,value:b})}})},fix:function(a){return a[r.expando]?a:new r.Event(a)},special:{load:{noBubble:!0},focus:{trigger:function(){if(this!==va()&&this.focus)return this.focus(),!1},delegateType:"focusin"},blur:{trigger:function(){if(this===va()&&this.blur)return this.blur(),!1},delegateType:"focusout"},click:{trigger:function(){if("checkbox"===this.type&&this.click&&r.nodeName(this,"input"))return this.click(),!1},_default:function(a){return r.nodeName(a.target,"a")}},beforeunload:{postDispatch:function(a){void 0!==a.result&&a.originalEvent&&(a.originalEvent.returnValue=a.result)}}}},r.removeEvent=function(a,b,c){a.removeEventListener&&a.removeEventListener(b,c)},r.Event=function(a,b){return this instanceof r.Event?(a&&a.type?(this.originalEvent=a,this.type=a.type,this.isDefaultPrevented=a.defaultPrevented||void 0===a.defaultPrevented&&a.returnValue===!1?ta:ua,this.target=a.target&&3===a.target.nodeType?a.target.parentNode:a.target,this.currentTarget=a.currentTarget,this.relatedTarget=a.relatedTarget):this.type=a,b&&r.extend(this,b),this.timeStamp=a&&a.timeStamp||r.now(),void(this[r.expando]=!0)):new r.Event(a,b)},r.Event.prototype={constructor:r.Event,isDefaultPrevented:ua,isPropagationStopped:ua,isImmediatePropagationStopped:ua,isSimulated:!1,preventDefault:function(){var a=this.originalEvent;this.isDefaultPrevented=ta,a&&!this.isSimulated&&a.preventDefault()},stopPropagation:function(){var a=this.originalEvent;this.isPropagationStopped=ta,a&&!this.isSimulated&&a.stopPropagation()},stopImmediatePropagation:function(){var a=this.originalEvent;this.isImmediatePropagationStopped=ta,a&&!this.isSimulated&&a.stopImmediatePropagation(),this.stopPropagation()}},r.each({altKey:!0,bubbles:!0,cancelable:!0,changedTouches:!0,ctrlKey:!0,detail:!0,eventPhase:!0,metaKey:!0,pageX:!0,pageY:!0,shiftKey:!0,view:!0,"char":!0,charCode:!0,key:!0,keyCode:!0,button:!0,buttons:!0,clientX:!0,clientY:!0,offsetX:!0,offsetY:!0,pointerId:!0,pointerType:!0,screenX:!0,screenY:!0,targetTouches:!0,toElement:!0,touches:!0,which:function(a){var b=a.button;return null==a.which&&qa.test(a.type)?null!=a.charCode?a.charCode:a.keyCode:!a.which&&void 0!==b&&ra.test(a.type)?1&b?1:2&b?3:4&b?2:0:a.which}},r.event.addProp),r.each({mouseenter:"mouseover",mouseleave:"mouseout",pointerenter:"pointerover",pointerleave:"pointerout"},function(a,b){r.event.special[a]={delegateType:b,bindType:b,handle:function(a){var c,d=this,e=a.relatedTarget,f=a.handleObj;return e&&(e===d||r.contains(d,e))||(a.type=f.origType,c=f.handler.apply(this,arguments),a.type=b),c}}}),r.fn.extend({on:function(a,b,c,d){return wa(this,a,b,c,d)},one:function(a,b,c,d){return wa(this,a,b,c,d,1)},off:function(a,b,c){var d,e;if(a&&a.preventDefault&&a.handleObj)return d=a.handleObj,r(a.delegateTarget).off(d.namespace?d.origType+"."+d.namespace:d.origType,d.selector,d.handler),this;if("object"==typeof a){for(e in a)this.off(e,b,a[e]);return this}return b!==!1&&"function"!=typeof b||(c=b,b=void 0),c===!1&&(c=ua),this.each(function(){r.event.remove(this,a,c,b)})}});var xa=/<(?!area|br|col|embed|hr|img|input|link|meta|param)(([a-z][^\/\0>\x20\t\r\n\f]*)[^>]*)\/>/gi,ya=/<script|<style|<link/i,za=/checked\s*(?:[^=]|=\s*.checked.)/i,Aa=/^true\/(.*)/,Ba=/^\s*<!(?:\[CDATA\[|--)|(?:\]\]|--)>\s*$/g;function Ca(a,b){return r.nodeName(a,"table")&&r.nodeName(11!==b.nodeType?b:b.firstChild,"tr")?a.getElementsByTagName("tbody")[0]||a:a}function Da(a){return a.type=(null!==a.getAttribute("type"))+"/"+a.type,a}function Ea(a){var b=Aa.exec(a.type);return b?a.type=b[1]:a.removeAttribute("type"),a}function Fa(a,b){var c,d,e,f,g,h,i,j;if(1===b.nodeType){if(V.hasData(a)&&(f=V.access(a),g=V.set(b,f),j=f.events)){delete g.handle,g.events={};for(e in j)for(c=0,d=j[e].length;c<d;c++)r.event.add(b,e,j[e][c])}W.hasData(a)&&(h=W.access(a),i=r.extend({},h),W.set(b,i))}}function Ga(a,b){var c=b.nodeName.toLowerCase();"input"===c&&ha.test(a.type)?b.checked=a.checked:"input"!==c&&"textarea"!==c||(b.defaultValue=a.defaultValue)}function Ha(a,b,c,d){b=g.apply([],b);var e,f,h,i,j,k,l=0,m=a.length,n=m-1,q=b[0],s=r.isFunction(q);if(s||m>1&&"string"==typeof q&&!o.checkClone&&za.test(q))return a.each(function(e){var f=a.eq(e);s&&(b[0]=q.call(this,e,f.html())),Ha(f,b,c,d)});if(m&&(e=oa(b,a[0].ownerDocument,!1,a,d),f=e.firstChild,1===e.childNodes.length&&(e=f),f||d)){for(h=r.map(la(e,"script"),Da),i=h.length;l<m;l++)j=e,l!==n&&(j=r.clone(j,!0,!0),i&&r.merge(h,la(j,"script"))),c.call(a[l],j,l);if(i)for(k=h[h.length-1].ownerDocument,r.map(h,Ea),l=0;l<i;l++)j=h[l],ja.test(j.type||"")&&!V.access(j,"globalEval")&&r.contains(k,j)&&(j.src?r._evalUrl&&r._evalUrl(j.src):p(j.textContent.replace(Ba,""),k))}return a}function Ia(a,b,c){for(var d,e=b?r.filter(b,a):a,f=0;null!=(d=e[f]);f++)c||1!==d.nodeType||r.cleanData(la(d)),d.parentNode&&(c&&r.contains(d.ownerDocument,d)&&ma(la(d,"script")),d.parentNode.removeChild(d));return a}r.extend({htmlPrefilter:function(a){return a.replace(xa,"<$1></$2>")},clone:function(a,b,c){var d,e,f,g,h=a.cloneNode(!0),i=r.contains(a.ownerDocument,a);if(!(o.noCloneChecked||1!==a.nodeType&&11!==a.nodeType||r.isXMLDoc(a)))for(g=la(h),f=la(a),d=0,e=f.length;d<e;d++)Ga(f[d],g[d]);if(b)if(c)for(f=f||la(a),g=g||la(h),d=0,e=f.length;d<e;d++)Fa(f[d],g[d]);else Fa(a,h);return g=la(h,"script"),g.length>0&&ma(g,!i&&la(a,"script")),h},cleanData:function(a){for(var b,c,d,e=r.event.special,f=0;void 0!==(c=a[f]);f++)if(T(c)){if(b=c[V.expando]){if(b.events)for(d in b.events)e[d]?r.event.remove(c,d):r.removeEvent(c,d,b.handle);c[V.expando]=void 0}c[W.expando]&&(c[W.expando]=void 0)}}}),r.fn.extend({detach:function(a){return Ia(this,a,!0)},remove:function(a){return Ia(this,a)},text:function(a){return S(this,function(a){return void 0===a?r.text(this):this.empty().each(function(){1!==this.nodeType&&11!==this.nodeType&&9!==this.nodeType||(this.textContent=a)})},null,a,arguments.length)},append:function(){return Ha(this,arguments,function(a){if(1===this.nodeType||11===this.nodeType||9===this.nodeType){var b=Ca(this,a);b.appendChild(a)}})},prepend:function(){return Ha(this,arguments,function(a){if(1===this.nodeType||11===this.nodeType||9===this.nodeType){var b=Ca(this,a);b.insertBefore(a,b.firstChild)}})},before:function(){return Ha(this,arguments,function(a){this.parentNode&&this.parentNode.insertBefore(a,this)})},after:function(){return Ha(this,arguments,function(a){this.parentNode&&this.parentNode.insertBefore(a,this.nextSibling)})},empty:function(){for(var a,b=0;null!=(a=this[b]);b++)1===a.nodeType&&(r.cleanData(la(a,!1)),a.textContent="");return this},clone:function(a,b){return a=null!=a&&a,b=null==b?a:b,this.map(function(){return r.clone(this,a,b)})},html:function(a){return S(this,function(a){var b=this[0]||{},c=0,d=this.length;if(void 0===a&&1===b.nodeType)return b.innerHTML;if("string"==typeof a&&!ya.test(a)&&!ka[(ia.exec(a)||["",""])[1].toLowerCase()]){a=r.htmlPrefilter(a);try{for(;c<d;c++)b=this[c]||{},1===b.nodeType&&(r.cleanData(la(b,!1)),b.innerHTML=a);b=0}catch(e){}}b&&this.empty().append(a)},null,a,arguments.length)},replaceWith:function(){var a=[];return Ha(this,arguments,function(b){var c=this.parentNode;r.inArray(this,a)<0&&(r.cleanData(la(this)),c&&c.replaceChild(b,this))},a)}}),r.each({appendTo:"append",prependTo:"prepend",insertBefore:"before",insertAfter:"after",replaceAll:"replaceWith"},function(a,b){r.fn[a]=function(a){for(var c,d=[],e=r(a),f=e.length-1,g=0;g<=f;g++)c=g===f?this:this.clone(!0),r(e[g])[b](c),h.apply(d,c.get());return this.pushStack(d)}});var Ja=/^margin/,Ka=new RegExp("^("+$+")(?!px)[a-z%]+$","i"),La=function(b){var c=b.ownerDocument.defaultView;return c&&c.opener||(c=a),c.getComputedStyle(b)};!function(){function b(){if(i){i.style.cssText="box-sizing:border-box;position:relative;display:block;margin:auto;border:1px;padding:1px;top:1%;width:50%",i.innerHTML="",pa.appendChild(h);var b=a.getComputedStyle(i);c="1%"!==b.top,g="2px"===b.marginLeft,e="4px"===b.width,i.style.marginRight="50%",f="4px"===b.marginRight,pa.removeChild(h),i=null}}var c,e,f,g,h=d.createElement("div"),i=d.createElement("div");i.style&&(i.style.backgroundClip="content-box",i.cloneNode(!0).style.backgroundClip="",o.clearCloneStyle="content-box"===i.style.backgroundClip,h.style.cssText="border:0;width:8px;height:0;top:0;left:-9999px;padding:0;margin-top:1px;position:absolute",h.appendChild(i),r.extend(o,{pixelPosition:function(){return b(),c},boxSizingReliable:function(){return b(),e},pixelMarginRight:function(){return b(),f},reliableMarginLeft:function(){return b(),g}}))}();function Ma(a,b,c){var d,e,f,g,h=a.style;return c=c||La(a),c&&(g=c.getPropertyValue(b)||c[b],""!==g||r.contains(a.ownerDocument,a)||(g=r.style(a,b)),!o.pixelMarginRight()&&Ka.test(g)&&Ja.test(b)&&(d=h.width,e=h.minWidth,f=h.maxWidth,h.minWidth=h.maxWidth=h.width=g,g=c.width,h.width=d,h.minWidth=e,h.maxWidth=f)),void 0!==g?g+"":g}function Na(a,b){return{get:function(){return a()?void delete this.get:(this.get=b).apply(this,arguments)}}}var Oa=/^(none|table(?!-c[ea]).+)/,Pa={position:"absolute",visibility:"hidden",display:"block"},Qa={letterSpacing:"0",fontWeight:"400"},Ra=["Webkit","Moz","ms"],Sa=d.createElement("div").style;function Ta(a){if(a in Sa)return a;var b=a[0].toUpperCase()+a.slice(1),c=Ra.length;while(c--)if(a=Ra[c]+b,a in Sa)return a}function Ua(a,b,c){var d=_.exec(b);return d?Math.max(0,d[2]-(c||0))+(d[3]||"px"):b}function Va(a,b,c,d,e){for(var f=c===(d?"border":"content")?4:"width"===b?1:0,g=0;f<4;f+=2)"margin"===c&&(g+=r.css(a,c+aa[f],!0,e)),d?("content"===c&&(g-=r.css(a,"padding"+aa[f],!0,e)),"margin"!==c&&(g-=r.css(a,"border"+aa[f]+"Width",!0,e))):(g+=r.css(a,"padding"+aa[f],!0,e),"padding"!==c&&(g+=r.css(a,"border"+aa[f]+"Width",!0,e)));return g}function Wa(a,b,c){var d,e=!0,f=La(a),g="border-box"===r.css(a,"boxSizing",!1,f);if(a.getClientRects().length&&(d=a.getBoundingClientRect()[b]),d<=0||null==d){if(d=Ma(a,b,f),(d<0||null==d)&&(d=a.style[b]),Ka.test(d))return d;e=g&&(o.boxSizingReliable()||d===a.style[b]),d=parseFloat(d)||0}return d+Va(a,b,c||(g?"border":"content"),e,f)+"px"}r.extend({cssHooks:{opacity:{get:function(a,b){if(b){var c=Ma(a,"opacity");return""===c?"1":c}}}},cssNumber:{animationIterationCount:!0,columnCount:!0,fillOpacity:!0,flexGrow:!0,flexShrink:!0,fontWeight:!0,lineHeight:!0,opacity:!0,order:!0,orphans:!0,widows:!0,zIndex:!0,zoom:!0},cssProps:{"float":"cssFloat"},style:function(a,b,c,d){if(a&&3!==a.nodeType&&8!==a.nodeType&&a.style){var e,f,g,h=r.camelCase(b),i=a.style;return b=r.cssProps[h]||(r.cssProps[h]=Ta(h)||h),g=r.cssHooks[b]||r.cssHooks[h],void 0===c?g&&"get"in g&&void 0!==(e=g.get(a,!1,d))?e:i[b]:(f=typeof c,"string"===f&&(e=_.exec(c))&&e[1]&&(c=da(a,b,e),f="number"),null!=c&&c===c&&("number"===f&&(c+=e&&e[3]||(r.cssNumber[h]?"":"px")),o.clearCloneStyle||""!==c||0!==b.indexOf("background")||(i[b]="inherit"),g&&"set"in g&&void 0===(c=g.set(a,c,d))||(i[b]=c)),void 0)}},css:function(a,b,c,d){var e,f,g,h=r.camelCase(b);return b=r.cssProps[h]||(r.cssProps[h]=Ta(h)||h),g=r.cssHooks[b]||r.cssHooks[h],g&&"get"in g&&(e=g.get(a,!0,c)),void 0===e&&(e=Ma(a,b,d)),"normal"===e&&b in Qa&&(e=Qa[b]),""===c||c?(f=parseFloat(e),c===!0||isFinite(f)?f||0:e):e}}),r.each(["height","width"],function(a,b){r.cssHooks[b]={get:function(a,c,d){if(c)return!Oa.test(r.css(a,"display"))||a.getClientRects().length&&a.getBoundingClientRect().width?Wa(a,b,d):ca(a,Pa,function(){return Wa(a,b,d)})},set:function(a,c,d){var e,f=d&&La(a),g=d&&Va(a,b,d,"border-box"===r.css(a,"boxSizing",!1,f),f);return g&&(e=_.exec(c))&&"px"!==(e[3]||"px")&&(a.style[b]=c,c=r.css(a,b)),Ua(a,c,g)}}}),r.cssHooks.marginLeft=Na(o.reliableMarginLeft,function(a,b){if(b)return(parseFloat(Ma(a,"marginLeft"))||a.getBoundingClientRect().left-ca(a,{marginLeft:0},function(){return a.getBoundingClientRect().left}))+"px"}),r.each({margin:"",padding:"",border:"Width"},function(a,b){r.cssHooks[a+b]={expand:function(c){for(var d=0,e={},f="string"==typeof c?c.split(" "):[c];d<4;d++)e[a+aa[d]+b]=f[d]||f[d-2]||f[0];return e}},Ja.test(a)||(r.cssHooks[a+b].set=Ua)}),r.fn.extend({css:function(a,b){return S(this,function(a,b,c){var d,e,f={},g=0;if(r.isArray(b)){for(d=La(a),e=b.length;g<e;g++)f[b[g]]=r.css(a,b[g],!1,d);return f}return void 0!==c?r.style(a,b,c):r.css(a,b)},a,b,arguments.length>1)}});function Xa(a,b,c,d,e){return new Xa.prototype.init(a,b,c,d,e)}r.Tween=Xa,Xa.prototype={constructor:Xa,init:function(a,b,c,d,e,f){this.elem=a,this.prop=c,this.easing=e||r.easing._default,this.options=b,this.start=this.now=this.cur(),this.end=d,this.unit=f||(r.cssNumber[c]?"":"px")},cur:function(){var a=Xa.propHooks[this.prop];return a&&a.get?a.get(this):Xa.propHooks._default.get(this)},run:function(a){var b,c=Xa.propHooks[this.prop];return this.options.duration?this.pos=b=r.easing[this.easing](a,this.options.duration*a,0,1,this.options.duration):this.pos=b=a,this.now=(this.end-this.start)*b+this.start,this.options.step&&this.options.step.call(this.elem,this.now,this),c&&c.set?c.set(this):Xa.propHooks._default.set(this),this}},Xa.prototype.init.prototype=Xa.prototype,Xa.propHooks={_default:{get:function(a){var b;return 1!==a.elem.nodeType||null!=a.elem[a.prop]&&null==a.elem.style[a.prop]?a.elem[a.prop]:(b=r.css(a.elem,a.prop,""),b&&"auto"!==b?b:0)},set:function(a){r.fx.step[a.prop]?r.fx.step[a.prop](a):1!==a.elem.nodeType||null==a.elem.style[r.cssProps[a.prop]]&&!r.cssHooks[a.prop]?a.elem[a.prop]=a.now:r.style(a.elem,a.prop,a.now+a.unit)}}},Xa.propHooks.scrollTop=Xa.propHooks.scrollLeft={set:function(a){a.elem.nodeType&&a.elem.parentNode&&(a.elem[a.prop]=a.now)}},r.easing={linear:function(a){return a},swing:function(a){return.5-Math.cos(a*Math.PI)/2},_default:"swing"},r.fx=Xa.prototype.init,r.fx.step={};var Ya,Za,$a=/^(?:toggle|show|hide)$/,_a=/queueHooks$/;function ab(){Za&&(a.requestAnimationFrame(ab),r.fx.tick())}function bb(){return a.setTimeout(function(){Ya=void 0}),Ya=r.now()}function cb(a,b){var c,d=0,e={height:a};for(b=b?1:0;d<4;d+=2-b)c=aa[d],e["margin"+c]=e["padding"+c]=a;return b&&(e.opacity=e.width=a),e}function db(a,b,c){for(var d,e=(gb.tweeners[b]||[]).concat(gb.tweeners["*"]),f=0,g=e.length;f<g;f++)if(d=e[f].call(c,b,a))return d}function eb(a,b,c){var d,e,f,g,h,i,j,k,l="width"in b||"height"in b,m=this,n={},o=a.style,p=a.nodeType&&ba(a),q=V.get(a,"fxshow");c.queue||(g=r._queueHooks(a,"fx"),null==g.unqueued&&(g.unqueued=0,h=g.empty.fire,g.empty.fire=function(){g.unqueued||h()}),g.unqueued++,m.always(function(){m.always(function(){g.unqueued--,r.queue(a,"fx").length||g.empty.fire()})}));for(d in b)if(e=b[d],$a.test(e)){if(delete b[d],f=f||"toggle"===e,e===(p?"hide":"show")){if("show"!==e||!q||void 0===q[d])continue;p=!0}n[d]=q&&q[d]||r.style(a,d)}if(i=!r.isEmptyObject(b),i||!r.isEmptyObject(n)){l&&1===a.nodeType&&(c.overflow=[o.overflow,o.overflowX,o.overflowY],j=q&&q.display,null==j&&(j=V.get(a,"display")),k=r.css(a,"display"),"none"===k&&(j?k=j:(ga([a],!0),j=a.style.display||j,k=r.css(a,"display"),ga([a]))),("inline"===k||"inline-block"===k&&null!=j)&&"none"===r.css(a,"float")&&(i||(m.done(function(){o.display=j}),null==j&&(k=o.display,j="none"===k?"":k)),o.display="inline-block")),c.overflow&&(o.overflow="hidden",m.always(function(){o.overflow=c.overflow[0],o.overflowX=c.overflow[1],o.overflowY=c.overflow[2]})),i=!1;for(d in n)i||(q?"hidden"in q&&(p=q.hidden):q=V.access(a,"fxshow",{display:j}),f&&(q.hidden=!p),p&&ga([a],!0),m.done(function(){p||ga([a]),V.remove(a,"fxshow");for(d in n)r.style(a,d,n[d])})),i=db(p?q[d]:0,d,m),d in q||(q[d]=i.start,p&&(i.end=i.start,i.start=0))}}function fb(a,b){var c,d,e,f,g;for(c in a)if(d=r.camelCase(c),e=b[d],f=a[c],r.isArray(f)&&(e=f[1],f=a[c]=f[0]),c!==d&&(a[d]=f,delete a[c]),g=r.cssHooks[d],g&&"expand"in g){f=g.expand(f),delete a[d];for(c in f)c in a||(a[c]=f[c],b[c]=e)}else b[d]=e}function gb(a,b,c){var d,e,f=0,g=gb.prefilters.length,h=r.Deferred().always(function(){delete i.elem}),i=function(){if(e)return!1;for(var b=Ya||bb(),c=Math.max(0,j.startTime+j.duration-b),d=c/j.duration||0,f=1-d,g=0,i=j.tweens.length;g<i;g++)j.tweens[g].run(f);return h.notifyWith(a,[j,f,c]),f<1&&i?c:(h.resolveWith(a,[j]),!1)},j=h.promise({elem:a,props:r.extend({},b),opts:r.extend(!0,{specialEasing:{},easing:r.easing._default},c),originalProperties:b,originalOptions:c,startTime:Ya||bb(),duration:c.duration,tweens:[],createTween:function(b,c){var d=r.Tween(a,j.opts,b,c,j.opts.specialEasing[b]||j.opts.easing);return j.tweens.push(d),d},stop:function(b){var c=0,d=b?j.tweens.length:0;if(e)return this;for(e=!0;c<d;c++)j.tweens[c].run(1);return b?(h.notifyWith(a,[j,1,0]),h.resolveWith(a,[j,b])):h.rejectWith(a,[j,b]),this}}),k=j.props;for(fb(k,j.opts.specialEasing);f<g;f++)if(d=gb.prefilters[f].call(j,a,k,j.opts))return r.isFunction(d.stop)&&(r._queueHooks(j.elem,j.opts.queue).stop=r.proxy(d.stop,d)),d;return r.map(k,db,j),r.isFunction(j.opts.start)&&j.opts.start.call(a,j),r.fx.timer(r.extend(i,{elem:a,anim:j,queue:j.opts.queue})),j.progress(j.opts.progress).done(j.opts.done,j.opts.complete).fail(j.opts.fail).always(j.opts.always)}r.Animation=r.extend(gb,{tweeners:{"*":[function(a,b){var c=this.createTween(a,b);return da(c.elem,a,_.exec(b),c),c}]},tweener:function(a,b){r.isFunction(a)?(b=a,a=["*"]):a=a.match(K);for(var c,d=0,e=a.length;d<e;d++)c=a[d],gb.tweeners[c]=gb.tweeners[c]||[],gb.tweeners[c].unshift(b)},prefilters:[eb],prefilter:function(a,b){b?gb.prefilters.unshift(a):gb.prefilters.push(a)}}),r.speed=function(a,b,c){var e=a&&"object"==typeof a?r.extend({},a):{complete:c||!c&&b||r.isFunction(a)&&a,duration:a,easing:c&&b||b&&!r.isFunction(b)&&b};return r.fx.off||d.hidden?e.duration=0:e.duration="number"==typeof e.duration?e.duration:e.duration in r.fx.speeds?r.fx.speeds[e.duration]:r.fx.speeds._default,null!=e.queue&&e.queue!==!0||(e.queue="fx"),e.old=e.complete,e.complete=function(){r.isFunction(e.old)&&e.old.call(this),e.queue&&r.dequeue(this,e.queue)},e},r.fn.extend({fadeTo:function(a,b,c,d){return this.filter(ba).css("opacity",0).show().end().animate({opacity:b},a,c,d)},animate:function(a,b,c,d){var e=r.isEmptyObject(a),f=r.speed(b,c,d),g=function(){var b=gb(this,r.extend({},a),f);(e||V.get(this,"finish"))&&b.stop(!0)};return g.finish=g,e||f.queue===!1?this.each(g):this.queue(f.queue,g)},stop:function(a,b,c){var d=function(a){var b=a.stop;delete a.stop,b(c)};return"string"!=typeof a&&(c=b,b=a,a=void 0),b&&a!==!1&&this.queue(a||"fx",[]),this.each(function(){var b=!0,e=null!=a&&a+"queueHooks",f=r.timers,g=V.get(this);if(e)g[e]&&g[e].stop&&d(g[e]);else for(e in g)g[e]&&g[e].stop&&_a.test(e)&&d(g[e]);for(e=f.length;e--;)f[e].elem!==this||null!=a&&f[e].queue!==a||(f[e].anim.stop(c),b=!1,f.splice(e,1));!b&&c||r.dequeue(this,a)})},finish:function(a){return a!==!1&&(a=a||"fx"),this.each(function(){var b,c=V.get(this),d=c[a+"queue"],e=c[a+"queueHooks"],f=r.timers,g=d?d.length:0;for(c.finish=!0,r.queue(this,a,[]),e&&e.stop&&e.stop.call(this,!0),b=f.length;b--;)f[b].elem===this&&f[b].queue===a&&(f[b].anim.stop(!0),f.splice(b,1));for(b=0;b<g;b++)d[b]&&d[b].finish&&d[b].finish.call(this);delete c.finish})}}),r.each(["toggle","show","hide"],function(a,b){var c=r.fn[b];r.fn[b]=function(a,d,e){return null==a||"boolean"==typeof a?c.apply(this,arguments):this.animate(cb(b,!0),a,d,e)}}),r.each({slideDown:cb("show"),slideUp:cb("hide"),slideToggle:cb("toggle"),fadeIn:{opacity:"show"},fadeOut:{opacity:"hide"},fadeToggle:{opacity:"toggle"}},function(a,b){r.fn[a]=function(a,c,d){return this.animate(b,a,c,d)}}),r.timers=[],r.fx.tick=function(){var a,b=0,c=r.timers;for(Ya=r.now();b<c.length;b++)a=c[b],a()||c[b]!==a||c.splice(b--,1);c.length||r.fx.stop(),Ya=void 0},r.fx.timer=function(a){r.timers.push(a),a()?r.fx.start():r.timers.pop()},r.fx.interval=13,r.fx.start=function(){Za||(Za=a.requestAnimationFrame?a.requestAnimationFrame(ab):a.setInterval(r.fx.tick,r.fx.interval))},r.fx.stop=function(){a.cancelAnimationFrame?a.cancelAnimationFrame(Za):a.clearInterval(Za),Za=null},r.fx.speeds={slow:600,fast:200,_default:400},r.fn.delay=function(b,c){return b=r.fx?r.fx.speeds[b]||b:b,c=c||"fx",this.queue(c,function(c,d){var e=a.setTimeout(c,b);d.stop=function(){a.clearTimeout(e)}})},function(){var a=d.createElement("input"),b=d.createElement("select"),c=b.appendChild(d.createElement("option"));a.type="checkbox",o.checkOn=""!==a.value,o.optSelected=c.selected,a=d.createElement("input"),a.value="t",a.type="radio",o.radioValue="t"===a.value}();var hb,ib=r.expr.attrHandle;r.fn.extend({attr:function(a,b){return S(this,r.attr,a,b,arguments.length>1)},removeAttr:function(a){return this.each(function(){r.removeAttr(this,a)})}}),r.extend({attr:function(a,b,c){var d,e,f=a.nodeType;if(3!==f&&8!==f&&2!==f)return"undefined"==typeof a.getAttribute?r.prop(a,b,c):(1===f&&r.isXMLDoc(a)||(e=r.attrHooks[b.toLowerCase()]||(r.expr.match.bool.test(b)?hb:void 0)),void 0!==c?null===c?void r.removeAttr(a,b):e&&"set"in e&&void 0!==(d=e.set(a,c,b))?d:(a.setAttribute(b,c+""),c):e&&"get"in e&&null!==(d=e.get(a,b))?d:(d=r.find.attr(a,b),null==d?void 0:d))},attrHooks:{type:{set:function(a,b){if(!o.radioValue&&"radio"===b&&r.nodeName(a,"input")){var c=a.value;return a.setAttribute("type",b),c&&(a.value=c),b}}}},removeAttr:function(a,b){var c,d=0,e=b&&b.match(K);
if(e&&1===a.nodeType)while(c=e[d++])a.removeAttribute(c)}}),hb={set:function(a,b,c){return b===!1?r.removeAttr(a,c):a.setAttribute(c,c),c}},r.each(r.expr.match.bool.source.match(/\w+/g),function(a,b){var c=ib[b]||r.find.attr;ib[b]=function(a,b,d){var e,f,g=b.toLowerCase();return d||(f=ib[g],ib[g]=e,e=null!=c(a,b,d)?g:null,ib[g]=f),e}});var jb=/^(?:input|select|textarea|button)$/i,kb=/^(?:a|area)$/i;r.fn.extend({prop:function(a,b){return S(this,r.prop,a,b,arguments.length>1)},removeProp:function(a){return this.each(function(){delete this[r.propFix[a]||a]})}}),r.extend({prop:function(a,b,c){var d,e,f=a.nodeType;if(3!==f&&8!==f&&2!==f)return 1===f&&r.isXMLDoc(a)||(b=r.propFix[b]||b,e=r.propHooks[b]),void 0!==c?e&&"set"in e&&void 0!==(d=e.set(a,c,b))?d:a[b]=c:e&&"get"in e&&null!==(d=e.get(a,b))?d:a[b]},propHooks:{tabIndex:{get:function(a){var b=r.find.attr(a,"tabindex");return b?parseInt(b,10):jb.test(a.nodeName)||kb.test(a.nodeName)&&a.href?0:-1}}},propFix:{"for":"htmlFor","class":"className"}}),o.optSelected||(r.propHooks.selected={get:function(a){var b=a.parentNode;return b&&b.parentNode&&b.parentNode.selectedIndex,null},set:function(a){var b=a.parentNode;b&&(b.selectedIndex,b.parentNode&&b.parentNode.selectedIndex)}}),r.each(["tabIndex","readOnly","maxLength","cellSpacing","cellPadding","rowSpan","colSpan","useMap","frameBorder","contentEditable"],function(){r.propFix[this.toLowerCase()]=this});var lb=/[\t\r\n\f]/g;function mb(a){return a.getAttribute&&a.getAttribute("class")||""}r.fn.extend({addClass:function(a){var b,c,d,e,f,g,h,i=0;if(r.isFunction(a))return this.each(function(b){r(this).addClass(a.call(this,b,mb(this)))});if("string"==typeof a&&a){b=a.match(K)||[];while(c=this[i++])if(e=mb(c),d=1===c.nodeType&&(" "+e+" ").replace(lb," ")){g=0;while(f=b[g++])d.indexOf(" "+f+" ")<0&&(d+=f+" ");h=r.trim(d),e!==h&&c.setAttribute("class",h)}}return this},removeClass:function(a){var b,c,d,e,f,g,h,i=0;if(r.isFunction(a))return this.each(function(b){r(this).removeClass(a.call(this,b,mb(this)))});if(!arguments.length)return this.attr("class","");if("string"==typeof a&&a){b=a.match(K)||[];while(c=this[i++])if(e=mb(c),d=1===c.nodeType&&(" "+e+" ").replace(lb," ")){g=0;while(f=b[g++])while(d.indexOf(" "+f+" ")>-1)d=d.replace(" "+f+" "," ");h=r.trim(d),e!==h&&c.setAttribute("class",h)}}return this},toggleClass:function(a,b){var c=typeof a;return"boolean"==typeof b&&"string"===c?b?this.addClass(a):this.removeClass(a):r.isFunction(a)?this.each(function(c){r(this).toggleClass(a.call(this,c,mb(this),b),b)}):this.each(function(){var b,d,e,f;if("string"===c){d=0,e=r(this),f=a.match(K)||[];while(b=f[d++])e.hasClass(b)?e.removeClass(b):e.addClass(b)}else void 0!==a&&"boolean"!==c||(b=mb(this),b&&V.set(this,"__className__",b),this.setAttribute&&this.setAttribute("class",b||a===!1?"":V.get(this,"__className__")||""))})},hasClass:function(a){var b,c,d=0;b=" "+a+" ";while(c=this[d++])if(1===c.nodeType&&(" "+mb(c)+" ").replace(lb," ").indexOf(b)>-1)return!0;return!1}});var nb=/\r/g,ob=/[\x20\t\r\n\f]+/g;r.fn.extend({val:function(a){var b,c,d,e=this[0];{if(arguments.length)return d=r.isFunction(a),this.each(function(c){var e;1===this.nodeType&&(e=d?a.call(this,c,r(this).val()):a,null==e?e="":"number"==typeof e?e+="":r.isArray(e)&&(e=r.map(e,function(a){return null==a?"":a+""})),b=r.valHooks[this.type]||r.valHooks[this.nodeName.toLowerCase()],b&&"set"in b&&void 0!==b.set(this,e,"value")||(this.value=e))});if(e)return b=r.valHooks[e.type]||r.valHooks[e.nodeName.toLowerCase()],b&&"get"in b&&void 0!==(c=b.get(e,"value"))?c:(c=e.value,"string"==typeof c?c.replace(nb,""):null==c?"":c)}}}),r.extend({valHooks:{option:{get:function(a){var b=r.find.attr(a,"value");return null!=b?b:r.trim(r.text(a)).replace(ob," ")}},select:{get:function(a){for(var b,c,d=a.options,e=a.selectedIndex,f="select-one"===a.type,g=f?null:[],h=f?e+1:d.length,i=e<0?h:f?e:0;i<h;i++)if(c=d[i],(c.selected||i===e)&&!c.disabled&&(!c.parentNode.disabled||!r.nodeName(c.parentNode,"optgroup"))){if(b=r(c).val(),f)return b;g.push(b)}return g},set:function(a,b){var c,d,e=a.options,f=r.makeArray(b),g=e.length;while(g--)d=e[g],(d.selected=r.inArray(r.valHooks.option.get(d),f)>-1)&&(c=!0);return c||(a.selectedIndex=-1),f}}}}),r.each(["radio","checkbox"],function(){r.valHooks[this]={set:function(a,b){if(r.isArray(b))return a.checked=r.inArray(r(a).val(),b)>-1}},o.checkOn||(r.valHooks[this].get=function(a){return null===a.getAttribute("value")?"on":a.value})});var pb=/^(?:focusinfocus|focusoutblur)$/;r.extend(r.event,{trigger:function(b,c,e,f){var g,h,i,j,k,m,n,o=[e||d],p=l.call(b,"type")?b.type:b,q=l.call(b,"namespace")?b.namespace.split("."):[];if(h=i=e=e||d,3!==e.nodeType&&8!==e.nodeType&&!pb.test(p+r.event.triggered)&&(p.indexOf(".")>-1&&(q=p.split("."),p=q.shift(),q.sort()),k=p.indexOf(":")<0&&"on"+p,b=b[r.expando]?b:new r.Event(p,"object"==typeof b&&b),b.isTrigger=f?2:3,b.namespace=q.join("."),b.rnamespace=b.namespace?new RegExp("(^|\\.)"+q.join("\\.(?:.*\\.|)")+"(\\.|$)"):null,b.result=void 0,b.target||(b.target=e),c=null==c?[b]:r.makeArray(c,[b]),n=r.event.special[p]||{},f||!n.trigger||n.trigger.apply(e,c)!==!1)){if(!f&&!n.noBubble&&!r.isWindow(e)){for(j=n.delegateType||p,pb.test(j+p)||(h=h.parentNode);h;h=h.parentNode)o.push(h),i=h;i===(e.ownerDocument||d)&&o.push(i.defaultView||i.parentWindow||a)}g=0;while((h=o[g++])&&!b.isPropagationStopped())b.type=g>1?j:n.bindType||p,m=(V.get(h,"events")||{})[b.type]&&V.get(h,"handle"),m&&m.apply(h,c),m=k&&h[k],m&&m.apply&&T(h)&&(b.result=m.apply(h,c),b.result===!1&&b.preventDefault());return b.type=p,f||b.isDefaultPrevented()||n._default&&n._default.apply(o.pop(),c)!==!1||!T(e)||k&&r.isFunction(e[p])&&!r.isWindow(e)&&(i=e[k],i&&(e[k]=null),r.event.triggered=p,e[p](),r.event.triggered=void 0,i&&(e[k]=i)),b.result}},simulate:function(a,b,c){var d=r.extend(new r.Event,c,{type:a,isSimulated:!0});r.event.trigger(d,null,b)}}),r.fn.extend({trigger:function(a,b){return this.each(function(){r.event.trigger(a,b,this)})},triggerHandler:function(a,b){var c=this[0];if(c)return r.event.trigger(a,b,c,!0)}}),r.each("blur focus focusin focusout resize scroll click dblclick mousedown mouseup mousemove mouseover mouseout mouseenter mouseleave change select submit keydown keypress keyup contextmenu".split(" "),function(a,b){r.fn[b]=function(a,c){return arguments.length>0?this.on(b,null,a,c):this.trigger(b)}}),r.fn.extend({hover:function(a,b){return this.mouseenter(a).mouseleave(b||a)}}),o.focusin="onfocusin"in a,o.focusin||r.each({focus:"focusin",blur:"focusout"},function(a,b){var c=function(a){r.event.simulate(b,a.target,r.event.fix(a))};r.event.special[b]={setup:function(){var d=this.ownerDocument||this,e=V.access(d,b);e||d.addEventListener(a,c,!0),V.access(d,b,(e||0)+1)},teardown:function(){var d=this.ownerDocument||this,e=V.access(d,b)-1;e?V.access(d,b,e):(d.removeEventListener(a,c,!0),V.remove(d,b))}}});var qb=a.location,rb=r.now(),sb=/\?/;r.parseXML=function(b){var c;if(!b||"string"!=typeof b)return null;try{c=(new a.DOMParser).parseFromString(b,"text/xml")}catch(d){c=void 0}return c&&!c.getElementsByTagName("parsererror").length||r.error("Invalid XML: "+b),c};var tb=/\[\]$/,ub=/\r?\n/g,vb=/^(?:submit|button|image|reset|file)$/i,wb=/^(?:input|select|textarea|keygen)/i;function xb(a,b,c,d){var e;if(r.isArray(b))r.each(b,function(b,e){c||tb.test(a)?d(a,e):xb(a+"["+("object"==typeof e&&null!=e?b:"")+"]",e,c,d)});else if(c||"object"!==r.type(b))d(a,b);else for(e in b)xb(a+"["+e+"]",b[e],c,d)}r.param=function(a,b){var c,d=[],e=function(a,b){var c=r.isFunction(b)?b():b;d[d.length]=encodeURIComponent(a)+"="+encodeURIComponent(null==c?"":c)};if(r.isArray(a)||a.jquery&&!r.isPlainObject(a))r.each(a,function(){e(this.name,this.value)});else for(c in a)xb(c,a[c],b,e);return d.join("&")},r.fn.extend({serialize:function(){return r.param(this.serializeArray())},serializeArray:function(){return this.map(function(){var a=r.prop(this,"elements");return a?r.makeArray(a):this}).filter(function(){var a=this.type;return this.name&&!r(this).is(":disabled")&&wb.test(this.nodeName)&&!vb.test(a)&&(this.checked||!ha.test(a))}).map(function(a,b){var c=r(this).val();return null==c?null:r.isArray(c)?r.map(c,function(a){return{name:b.name,value:a.replace(ub,"\r\n")}}):{name:b.name,value:c.replace(ub,"\r\n")}}).get()}});var yb=/%20/g,zb=/#.*$/,Ab=/([?&])_=[^&]*/,Bb=/^(.*?):[ \t]*([^\r\n]*)$/gm,Cb=/^(?:about|app|app-storage|.+-extension|file|res|widget):$/,Db=/^(?:GET|HEAD)$/,Eb=/^\/\//,Fb={},Gb={},Hb="*/".concat("*"),Ib=d.createElement("a");Ib.href=qb.href;function Jb(a){return function(b,c){"string"!=typeof b&&(c=b,b="*");var d,e=0,f=b.toLowerCase().match(K)||[];if(r.isFunction(c))while(d=f[e++])"+"===d[0]?(d=d.slice(1)||"*",(a[d]=a[d]||[]).unshift(c)):(a[d]=a[d]||[]).push(c)}}function Kb(a,b,c,d){var e={},f=a===Gb;function g(h){var i;return e[h]=!0,r.each(a[h]||[],function(a,h){var j=h(b,c,d);return"string"!=typeof j||f||e[j]?f?!(i=j):void 0:(b.dataTypes.unshift(j),g(j),!1)}),i}return g(b.dataTypes[0])||!e["*"]&&g("*")}function Lb(a,b){var c,d,e=r.ajaxSettings.flatOptions||{};for(c in b)void 0!==b[c]&&((e[c]?a:d||(d={}))[c]=b[c]);return d&&r.extend(!0,a,d),a}function Mb(a,b,c){var d,e,f,g,h=a.contents,i=a.dataTypes;while("*"===i[0])i.shift(),void 0===d&&(d=a.mimeType||b.getResponseHeader("Content-Type"));if(d)for(e in h)if(h[e]&&h[e].test(d)){i.unshift(e);break}if(i[0]in c)f=i[0];else{for(e in c){if(!i[0]||a.converters[e+" "+i[0]]){f=e;break}g||(g=e)}f=f||g}if(f)return f!==i[0]&&i.unshift(f),c[f]}function Nb(a,b,c,d){var e,f,g,h,i,j={},k=a.dataTypes.slice();if(k[1])for(g in a.converters)j[g.toLowerCase()]=a.converters[g];f=k.shift();while(f)if(a.responseFields[f]&&(c[a.responseFields[f]]=b),!i&&d&&a.dataFilter&&(b=a.dataFilter(b,a.dataType)),i=f,f=k.shift())if("*"===f)f=i;else if("*"!==i&&i!==f){if(g=j[i+" "+f]||j["* "+f],!g)for(e in j)if(h=e.split(" "),h[1]===f&&(g=j[i+" "+h[0]]||j["* "+h[0]])){g===!0?g=j[e]:j[e]!==!0&&(f=h[0],k.unshift(h[1]));break}if(g!==!0)if(g&&a["throws"])b=g(b);else try{b=g(b)}catch(l){return{state:"parsererror",error:g?l:"No conversion from "+i+" to "+f}}}return{state:"success",data:b}}r.extend({active:0,lastModified:{},etag:{},ajaxSettings:{url:qb.href,type:"GET",isLocal:Cb.test(qb.protocol),global:!0,processData:!0,async:!0,contentType:"application/x-www-form-urlencoded; charset=UTF-8",accepts:{"*":Hb,text:"text/plain",html:"text/html",xml:"application/xml, text/xml",json:"application/json, text/javascript"},contents:{xml:/\bxml\b/,html:/\bhtml/,json:/\bjson\b/},responseFields:{xml:"responseXML",text:"responseText",json:"responseJSON"},converters:{"* text":String,"text html":!0,"text json":JSON.parse,"text xml":r.parseXML},flatOptions:{url:!0,context:!0}},ajaxSetup:function(a,b){return b?Lb(Lb(a,r.ajaxSettings),b):Lb(r.ajaxSettings,a)},ajaxPrefilter:Jb(Fb),ajaxTransport:Jb(Gb),ajax:function(b,c){"object"==typeof b&&(c=b,b=void 0),c=c||{};var e,f,g,h,i,j,k,l,m,n,o=r.ajaxSetup({},c),p=o.context||o,q=o.context&&(p.nodeType||p.jquery)?r(p):r.event,s=r.Deferred(),t=r.Callbacks("once memory"),u=o.statusCode||{},v={},w={},x="canceled",y={readyState:0,getResponseHeader:function(a){var b;if(k){if(!h){h={};while(b=Bb.exec(g))h[b[1].toLowerCase()]=b[2]}b=h[a.toLowerCase()]}return null==b?null:b},getAllResponseHeaders:function(){return k?g:null},setRequestHeader:function(a,b){return null==k&&(a=w[a.toLowerCase()]=w[a.toLowerCase()]||a,v[a]=b),this},overrideMimeType:function(a){return null==k&&(o.mimeType=a),this},statusCode:function(a){var b;if(a)if(k)y.always(a[y.status]);else for(b in a)u[b]=[u[b],a[b]];return this},abort:function(a){var b=a||x;return e&&e.abort(b),A(0,b),this}};if(s.promise(y),o.url=((b||o.url||qb.href)+"").replace(Eb,qb.protocol+"//"),o.type=c.method||c.type||o.method||o.type,o.dataTypes=(o.dataType||"*").toLowerCase().match(K)||[""],null==o.crossDomain){j=d.createElement("a");try{j.href=o.url,j.href=j.href,o.crossDomain=Ib.protocol+"//"+Ib.host!=j.protocol+"//"+j.host}catch(z){o.crossDomain=!0}}if(o.data&&o.processData&&"string"!=typeof o.data&&(o.data=r.param(o.data,o.traditional)),Kb(Fb,o,c,y),k)return y;l=r.event&&o.global,l&&0===r.active++&&r.event.trigger("ajaxStart"),o.type=o.type.toUpperCase(),o.hasContent=!Db.test(o.type),f=o.url.replace(zb,""),o.hasContent?o.data&&o.processData&&0===(o.contentType||"").indexOf("application/x-www-form-urlencoded")&&(o.data=o.data.replace(yb,"+")):(n=o.url.slice(f.length),o.data&&(f+=(sb.test(f)?"&":"?")+o.data,delete o.data),o.cache===!1&&(f=f.replace(Ab,""),n=(sb.test(f)?"&":"?")+"_="+rb++ +n),o.url=f+n),o.ifModified&&(r.lastModified[f]&&y.setRequestHeader("If-Modified-Since",r.lastModified[f]),r.etag[f]&&y.setRequestHeader("If-None-Match",r.etag[f])),(o.data&&o.hasContent&&o.contentType!==!1||c.contentType)&&y.setRequestHeader("Content-Type",o.contentType),y.setRequestHeader("Accept",o.dataTypes[0]&&o.accepts[o.dataTypes[0]]?o.accepts[o.dataTypes[0]]+("*"!==o.dataTypes[0]?", "+Hb+"; q=0.01":""):o.accepts["*"]);for(m in o.headers)y.setRequestHeader(m,o.headers[m]);if(o.beforeSend&&(o.beforeSend.call(p,y,o)===!1||k))return y.abort();if(x="abort",t.add(o.complete),y.done(o.success),y.fail(o.error),e=Kb(Gb,o,c,y)){if(y.readyState=1,l&&q.trigger("ajaxSend",[y,o]),k)return y;o.async&&o.timeout>0&&(i=a.setTimeout(function(){y.abort("timeout")},o.timeout));try{k=!1,e.send(v,A)}catch(z){if(k)throw z;A(-1,z)}}else A(-1,"No Transport");function A(b,c,d,h){var j,m,n,v,w,x=c;k||(k=!0,i&&a.clearTimeout(i),e=void 0,g=h||"",y.readyState=b>0?4:0,j=b>=200&&b<300||304===b,d&&(v=Mb(o,y,d)),v=Nb(o,v,y,j),j?(o.ifModified&&(w=y.getResponseHeader("Last-Modified"),w&&(r.lastModified[f]=w),w=y.getResponseHeader("etag"),w&&(r.etag[f]=w)),204===b||"HEAD"===o.type?x="nocontent":304===b?x="notmodified":(x=v.state,m=v.data,n=v.error,j=!n)):(n=x,!b&&x||(x="error",b<0&&(b=0))),y.status=b,y.statusText=(c||x)+"",j?s.resolveWith(p,[m,x,y]):s.rejectWith(p,[y,x,n]),y.statusCode(u),u=void 0,l&&q.trigger(j?"ajaxSuccess":"ajaxError",[y,o,j?m:n]),t.fireWith(p,[y,x]),l&&(q.trigger("ajaxComplete",[y,o]),--r.active||r.event.trigger("ajaxStop")))}return y},getJSON:function(a,b,c){return r.get(a,b,c,"json")},getScript:function(a,b){return r.get(a,void 0,b,"script")}}),r.each(["get","post"],function(a,b){r[b]=function(a,c,d,e){return r.isFunction(c)&&(e=e||d,d=c,c=void 0),r.ajax(r.extend({url:a,type:b,dataType:e,data:c,success:d},r.isPlainObject(a)&&a))}}),r._evalUrl=function(a){return r.ajax({url:a,type:"GET",dataType:"script",cache:!0,async:!1,global:!1,"throws":!0})},r.fn.extend({wrapAll:function(a){var b;return this[0]&&(r.isFunction(a)&&(a=a.call(this[0])),b=r(a,this[0].ownerDocument).eq(0).clone(!0),this[0].parentNode&&b.insertBefore(this[0]),b.map(function(){var a=this;while(a.firstElementChild)a=a.firstElementChild;return a}).append(this)),this},wrapInner:function(a){return r.isFunction(a)?this.each(function(b){r(this).wrapInner(a.call(this,b))}):this.each(function(){var b=r(this),c=b.contents();c.length?c.wrapAll(a):b.append(a)})},wrap:function(a){var b=r.isFunction(a);return this.each(function(c){r(this).wrapAll(b?a.call(this,c):a)})},unwrap:function(a){return this.parent(a).not("body").each(function(){r(this).replaceWith(this.childNodes)}),this}}),r.expr.pseudos.hidden=function(a){return!r.expr.pseudos.visible(a)},r.expr.pseudos.visible=function(a){return!!(a.offsetWidth||a.offsetHeight||a.getClientRects().length)},r.ajaxSettings.xhr=function(){try{return new a.XMLHttpRequest}catch(b){}};var Ob={0:200,1223:204},Pb=r.ajaxSettings.xhr();o.cors=!!Pb&&"withCredentials"in Pb,o.ajax=Pb=!!Pb,r.ajaxTransport(function(b){var c,d;if(o.cors||Pb&&!b.crossDomain)return{send:function(e,f){var g,h=b.xhr();if(h.open(b.type,b.url,b.async,b.username,b.password),b.xhrFields)for(g in b.xhrFields)h[g]=b.xhrFields[g];b.mimeType&&h.overrideMimeType&&h.overrideMimeType(b.mimeType),b.crossDomain||e["X-Requested-With"]||(e["X-Requested-With"]="XMLHttpRequest");for(g in e)h.setRequestHeader(g,e[g]);c=function(a){return function(){c&&(c=d=h.onload=h.onerror=h.onabort=h.onreadystatechange=null,"abort"===a?h.abort():"error"===a?"number"!=typeof h.status?f(0,"error"):f(h.status,h.statusText):f(Ob[h.status]||h.status,h.statusText,"text"!==(h.responseType||"text")||"string"!=typeof h.responseText?{binary:h.response}:{text:h.responseText},h.getAllResponseHeaders()))}},h.onload=c(),d=h.onerror=c("error"),void 0!==h.onabort?h.onabort=d:h.onreadystatechange=function(){4===h.readyState&&a.setTimeout(function(){c&&d()})},c=c("abort");try{h.send(b.hasContent&&b.data||null)}catch(i){if(c)throw i}},abort:function(){c&&c()}}}),r.ajaxPrefilter(function(a){a.crossDomain&&(a.contents.script=!1)}),r.ajaxSetup({accepts:{script:"text/javascript, application/javascript, application/ecmascript, application/x-ecmascript"},contents:{script:/\b(?:java|ecma)script\b/},converters:{"text script":function(a){return r.globalEval(a),a}}}),r.ajaxPrefilter("script",function(a){void 0===a.cache&&(a.cache=!1),a.crossDomain&&(a.type="GET")}),r.ajaxTransport("script",function(a){if(a.crossDomain){var b,c;return{send:function(e,f){b=r("<script>").prop({charset:a.scriptCharset,src:a.url}).on("load error",c=function(a){b.remove(),c=null,a&&f("error"===a.type?404:200,a.type)}),d.head.appendChild(b[0])},abort:function(){c&&c()}}}});var Qb=[],Rb=/(=)\?(?=&|$)|\?\?/;r.ajaxSetup({jsonp:"callback",jsonpCallback:function(){var a=Qb.pop()||r.expando+"_"+rb++;return this[a]=!0,a}}),r.ajaxPrefilter("json jsonp",function(b,c,d){var e,f,g,h=b.jsonp!==!1&&(Rb.test(b.url)?"url":"string"==typeof b.data&&0===(b.contentType||"").indexOf("application/x-www-form-urlencoded")&&Rb.test(b.data)&&"data");if(h||"jsonp"===b.dataTypes[0])return e=b.jsonpCallback=r.isFunction(b.jsonpCallback)?b.jsonpCallback():b.jsonpCallback,h?b[h]=b[h].replace(Rb,"$1"+e):b.jsonp!==!1&&(b.url+=(sb.test(b.url)?"&":"?")+b.jsonp+"="+e),b.converters["script json"]=function(){return g||r.error(e+" was not called"),g[0]},b.dataTypes[0]="json",f=a[e],a[e]=function(){g=arguments},d.always(function(){void 0===f?r(a).removeProp(e):a[e]=f,b[e]&&(b.jsonpCallback=c.jsonpCallback,Qb.push(e)),g&&r.isFunction(f)&&f(g[0]),g=f=void 0}),"script"}),o.createHTMLDocument=function(){var a=d.implementation.createHTMLDocument("").body;return a.innerHTML="<form></form><form></form>",2===a.childNodes.length}(),r.parseHTML=function(a,b,c){if("string"!=typeof a)return[];"boolean"==typeof b&&(c=b,b=!1);var e,f,g;return b||(o.createHTMLDocument?(b=d.implementation.createHTMLDocument(""),e=b.createElement("base"),e.href=d.location.href,b.head.appendChild(e)):b=d),f=B.exec(a),g=!c&&[],f?[b.createElement(f[1])]:(f=oa([a],b,g),g&&g.length&&r(g).remove(),r.merge([],f.childNodes))},r.fn.load=function(a,b,c){var d,e,f,g=this,h=a.indexOf(" ");return h>-1&&(d=r.trim(a.slice(h)),a=a.slice(0,h)),r.isFunction(b)?(c=b,b=void 0):b&&"object"==typeof b&&(e="POST"),g.length>0&&r.ajax({url:a,type:e||"GET",dataType:"html",data:b}).done(function(a){f=arguments,g.html(d?r("<div>").append(r.parseHTML(a)).find(d):a)}).always(c&&function(a,b){g.each(function(){c.apply(this,f||[a.responseText,b,a])})}),this},r.each(["ajaxStart","ajaxStop","ajaxComplete","ajaxError","ajaxSuccess","ajaxSend"],function(a,b){r.fn[b]=function(a){return this.on(b,a)}}),r.expr.pseudos.animated=function(a){return r.grep(r.timers,function(b){return a===b.elem}).length};function Sb(a){return r.isWindow(a)?a:9===a.nodeType&&a.defaultView}r.offset={setOffset:function(a,b,c){var d,e,f,g,h,i,j,k=r.css(a,"position"),l=r(a),m={};"static"===k&&(a.style.position="relative"),h=l.offset(),f=r.css(a,"top"),i=r.css(a,"left"),j=("absolute"===k||"fixed"===k)&&(f+i).indexOf("auto")>-1,j?(d=l.position(),g=d.top,e=d.left):(g=parseFloat(f)||0,e=parseFloat(i)||0),r.isFunction(b)&&(b=b.call(a,c,r.extend({},h))),null!=b.top&&(m.top=b.top-h.top+g),null!=b.left&&(m.left=b.left-h.left+e),"using"in b?b.using.call(a,m):l.css(m)}},r.fn.extend({offset:function(a){if(arguments.length)return void 0===a?this:this.each(function(b){r.offset.setOffset(this,a,b)});var b,c,d,e,f=this[0];if(f)return f.getClientRects().length?(d=f.getBoundingClientRect(),d.width||d.height?(e=f.ownerDocument,c=Sb(e),b=e.documentElement,{top:d.top+c.pageYOffset-b.clientTop,left:d.left+c.pageXOffset-b.clientLeft}):d):{top:0,left:0}},position:function(){if(this[0]){var a,b,c=this[0],d={top:0,left:0};return"fixed"===r.css(c,"position")?b=c.getBoundingClientRect():(a=this.offsetParent(),b=this.offset(),r.nodeName(a[0],"html")||(d=a.offset()),d={top:d.top+r.css(a[0],"borderTopWidth",!0),left:d.left+r.css(a[0],"borderLeftWidth",!0)}),{top:b.top-d.top-r.css(c,"marginTop",!0),left:b.left-d.left-r.css(c,"marginLeft",!0)}}},offsetParent:function(){return this.map(function(){var a=this.offsetParent;while(a&&"static"===r.css(a,"position"))a=a.offsetParent;return a||pa})}}),r.each({scrollLeft:"pageXOffset",scrollTop:"pageYOffset"},function(a,b){var c="pageYOffset"===b;r.fn[a]=function(d){return S(this,function(a,d,e){var f=Sb(a);return void 0===e?f?f[b]:a[d]:void(f?f.scrollTo(c?f.pageXOffset:e,c?e:f.pageYOffset):a[d]=e)},a,d,arguments.length)}}),r.each(["top","left"],function(a,b){r.cssHooks[b]=Na(o.pixelPosition,function(a,c){if(c)return c=Ma(a,b),Ka.test(c)?r(a).position()[b]+"px":c})}),r.each({Height:"height",Width:"width"},function(a,b){r.each({padding:"inner"+a,content:b,"":"outer"+a},function(c,d){r.fn[d]=function(e,f){var g=arguments.length&&(c||"boolean"!=typeof e),h=c||(e===!0||f===!0?"margin":"border");return S(this,function(b,c,e){var f;return r.isWindow(b)?0===d.indexOf("outer")?b["inner"+a]:b.document.documentElement["client"+a]:9===b.nodeType?(f=b.documentElement,Math.max(b.body["scroll"+a],f["scroll"+a],b.body["offset"+a],f["offset"+a],f["client"+a])):void 0===e?r.css(b,c,h):r.style(b,c,e,h)},b,g?e:void 0,g)}})}),r.fn.extend({bind:function(a,b,c){return this.on(a,null,b,c)},unbind:function(a,b){return this.off(a,null,b)},delegate:function(a,b,c,d){return this.on(b,a,c,d)},undelegate:function(a,b,c){return 1===arguments.length?this.off(a,"**"):this.off(b,a||"**",c)}}),r.parseJSON=JSON.parse,"function"==typeof define&&define.amd&&define("jquery",[],function(){return r});var Tb=a.jQuery,Ub=a.$;return r.noConflict=function(b){return a.$===r&&(a.$=Ub),b&&a.jQuery===r&&(a.jQuery=Tb),r},b||(a.jQuery=a.$=r),r});
{
"manifest_version": 2,
"name": "test plugin",
"version": "0.1",
"requirements": {
"3D": {
"features": ["webgl"]
}
},
"permissions": [
"tabs"
],
"content_scripts": [
{
"matches": ["https://www.google.com/*"],
"js": ["jquery-3.1.0.min.js", "vivagraph.js", "test.js"]
}
]
}
// Chrome extension crash recreation
//
// This will crash the tab that goes to https://www.google.com (or whatever URL the manifest.json file points to)
// To get this to run without crashing simply comment out the following line from below:
// graphics : graphics
function test1() {
var graphGenerator = Viva.Graph.generator();
var graph = graphGenerator.path(4);
var layout = Viva.Graph.Layout.forceDirected(graph, {
springLength : 100,
springCoeff : 0.0008,
dragCoeff : 0.02,
gravity : -1.2
});
var graphics = Viva.Graph.View.webglGraphics();
var renderer = Viva.Graph.View.renderer(graph, {
layout : layout,
graphics : graphics
});
// I'm not quite happy with how events are currently implemented
// in the library and I'm planning to refactor it. But for the
// time beings this is how you track webgl-based input events:
var events = Viva.Graph.webglInputEvents(graphics, graph);
events.mouseEnter(function (node) {
console.log('Mouse entered node: ' + node.id);
}).mouseLeave(function (node) {
console.log('Mouse left node: ' + node.id);
}).dblClick(function (node) {
console.log('Double click on node: ' + node.id);
}).click(function (node) {
console.log('Single click on node: ' + node.id);
});
renderer.run();
}
test1();
!function(e){if("object"==typeof exports&&"undefined"!=typeof module)module.exports=e();else if("function"==typeof define&&define.amd)define([],e);else{var f;"undefined"!=typeof window?f=window:"undefined"!=typeof global?f=global:"undefined"!=typeof self&&(f=self),f.Viva=e()}}(function(){var define,module,exports;return (function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
/**
* This is an entry point for global namespace. If you want to use separate
* modules individually - you are more than welcome to do so.
*/
var random = require('ngraph.random');
var Viva = {
lazyExtend: function() {
return require('ngraph.merge').apply(this, arguments);
},
randomIterator: function() {
return random.randomIterator.apply(random, arguments);
},
random: function() {
return random.random.apply(random, arguments);
},
events: require('ngraph.events')
};
Viva.Graph = {
version: require('./version.js'),
graph: require('ngraph.graph'),
serializer: function() {
return {
loadFromJSON: require('ngraph.fromjson'),
storeToJSON: require('ngraph.tojson')
};
},
centrality: require('./Algorithms/centrality.js'),
operations: require('./Algorithms/operations.js'),
geom: function() {
return {
intersect: require('gintersect'),
intersectRect: require('./Utils/intersectRect.js')
};
},
webgl: require('./WebGL/webgl.js'),
webglInputEvents: require('./WebGL/webglInputEvents.js'),
generator: function() {
return require('ngraph.generators');
},
Input: {
domInputManager: require('./Input/domInputManager.js'),
webglInputManager: require('./Input/webglInputManager.js')
},
Utils: {
// TODO: move to Input
dragndrop: require('./Input/dragndrop.js'),
findElementPosition: require('./Utils/findElementPosition.js'),
timer: require('./Utils/timer.js'),
getDimension: require('./Utils/getDimensions.js'),
events: require('./Utils/backwardCompatibleEvents.js')
},
Layout: {
forceDirected: require('ngraph.forcelayout'),
constant: require('./Layout/constant.js')
},
View: {
// TODO: Move `webglXXX` out to webgl namespace
Texture: require('./WebGL/texture.js'),
// TODO: This should not be even exported
webglAtlas: require('./WebGL/webglAtlas.js'),
webglImageNodeProgram: require('./WebGL/webglImageNodeProgram.js'),
webglLinkProgram: require('./WebGL/webglLinkProgram.js'),
webglNodeProgram: require('./WebGL/webglNodeProgram.js'),
webglLine: require('./WebGL/webglLine.js'),
webglSquare: require('./WebGL/webglSquare.js'),
webglImage: require('./WebGL/webglImage.js'),
webglGraphics: require('./View/webglGraphics.js'),
// TODO: Deprecate this:
_webglUtil: {
parseColor: require('./WebGL/parseColor.js')
},
// TODO: move to svg namespace
svgGraphics: require('./View/svgGraphics.js'),
renderer: require('./View/renderer.js'),
// deprecated
cssGraphics: function() {
throw new Error('cssGraphics is deprecated. Please use older version of vivagraph (< 0.7) if you need it');
},
svgNodeFactory: function() {
throw new Error('svgNodeFactory is deprecated. Please use older version of vivagraph (< 0.7) if you need it');
},
community: function() {
throw new Error('community is deprecated. Please use vivagraph < 0.7 if you need it, or `https://github.com/anvaka/ngraph.slpa` module');
}
},
Rect: require('./Utils/rect.js'),
svg: require('simplesvg'),
// TODO: should be camelCase
BrowserInfo: require('./Utils/browserInfo.js')
};
module.exports = Viva;
},{"./Algorithms/centrality.js":32,"./Algorithms/operations.js":33,"./Input/domInputManager.js":34,"./Input/dragndrop.js":35,"./Input/webglInputManager.js":36,"./Layout/constant.js":37,"./Utils/backwardCompatibleEvents.js":38,"./Utils/browserInfo.js":39,"./Utils/findElementPosition.js":41,"./Utils/getDimensions.js":42,"./Utils/intersectRect.js":43,"./Utils/rect.js":45,"./Utils/timer.js":46,"./View/renderer.js":48,"./View/svgGraphics.js":49,"./View/webglGraphics.js":50,"./WebGL/parseColor.js":51,"./WebGL/texture.js":52,"./WebGL/webgl.js":53,"./WebGL/webglAtlas.js":54,"./WebGL/webglImage.js":55,"./WebGL/webglImageNodeProgram.js":56,"./WebGL/webglInputEvents.js":57,"./WebGL/webglLine.js":58,"./WebGL/webglLinkProgram.js":59,"./WebGL/webglNodeProgram.js":60,"./WebGL/webglSquare.js":61,"./version.js":62,"gintersect":2,"ngraph.events":6,"ngraph.forcelayout":7,"ngraph.fromjson":21,"ngraph.generators":22,"ngraph.graph":23,"ngraph.merge":24,"ngraph.random":25,"ngraph.tojson":26,"simplesvg":27}],2:[function(require,module,exports){
module.exports = intersect;
/**
* Original authors: Mukesh Prasad, Appeared in Graphics Gem II book
* http://www.opensource.apple.com/source/graphviz/graphviz-498/graphviz/dynagraph/common/xlines.c
* and adopted to javascript version by Andrei Kashcha.
*
* This function computes whether two line segments,
* respectively joining the input points (x1,y1) -- (x2,y2)
* and the input points (x3,y3) -- (x4,y4) intersect.
* If the lines intersect, the output variables x, y are
* set to coordinates of the point of intersection.
*
* @param {Number} x1 First line segment coordinates
* @param {Number} y1 First line segment coordinates
* @param {Number} x2 First line segment coordinates
* @param {Number} x2 First line segment coordinates
*
* @param {Number} x3 Second line segment coordinates
* @param {Number} y3 Second line segment coordinates
* @param {Number} x4 Second line segment coordinates
* @param {Number} x4 Second line segment coordinates
*
* @return {Object} x, y coordinates of intersection point or falsy value if no
* intersection found..
*/
function intersect(
x1, y1, x2, y2, // first line segment
x3, y3, x4, y4 // second line segment
) {
var a1, a2, b1, b2, c1, c2, /* Coefficients of line eqns. */
r1, r2, r3, r4, /* 'Sign' values */
denom, offset, num, /* Intermediate values */
result = {
x: 0,
y: 0
};
/* Compute a1, b1, c1, where line joining points 1 and 2
* is "a1 x + b1 y + c1 = 0".
*/
a1 = y2 - y1;
b1 = x1 - x2;
c1 = x2 * y1 - x1 * y2;
/* Compute r3 and r4.
*/
r3 = a1 * x3 + b1 * y3 + c1;
r4 = a1 * x4 + b1 * y4 + c1;
/* Check signs of r3 and r4. If both point 3 and point 4 lie on
* same side of line 1, the line segments do not intersect.
*/
if (r3 !== 0 && r4 !== 0 && ((r3 >= 0) === (r4 >= 4))) {
return null; //no intersection.
}
/* Compute a2, b2, c2 */
a2 = y4 - y3;
b2 = x3 - x4;
c2 = x4 * y3 - x3 * y4;
/* Compute r1 and r2 */
r1 = a2 * x1 + b2 * y1 + c2;
r2 = a2 * x2 + b2 * y2 + c2;
/* Check signs of r1 and r2. If both point 1 and point 2 lie
* on same side of second line segment, the line segments do
* not intersect.
*/
if (r1 !== 0 && r2 !== 0 && ((r1 >= 0) === (r2 >= 0))) {
return null; // no intersection;
}
/* Line segments intersect: compute intersection point.
*/
denom = a1 * b2 - a2 * b1;
if (denom === 0) {
return null; // Actually collinear..
}
offset = denom < 0 ? -denom / 2 : denom / 2;
offset = 0.0;
/* The denom/2 is to get rounding instead of truncating. It
* is added or subtracted to the numerator, depending upon the
* sign of the numerator.
*/
num = b1 * c2 - b2 * c1;
result.x = (num < 0 ? num - offset : num + offset) / denom;
num = a2 * c1 - a1 * c2;
result.y = (num < 0 ? num - offset : num + offset) / denom;
return result;
}
},{}],3:[function(require,module,exports){
module.exports.degree = require('./src/degree.js');
module.exports.betweenness = require('./src/betweenness.js');
},{"./src/betweenness.js":4,"./src/degree.js":5}],4:[function(require,module,exports){
module.exports = betweennes;
/**
* I'm using http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf
* as a reference for this implementation
*/
function betweennes(graph, oriented) {
var Q = [],
S = []; // Queue and Stack
// list of predcessors on shorteest paths from source
var pred = Object.create(null);
// distance from source
var dist = Object.create(null);
// number of shortest paths from source to key
var sigma = Object.create(null);
// dependency of source on key
var delta = Object.create(null);
var currentNode;
var centrality = Object.create(null);
graph.forEachNode(setCentralityToZero);
graph.forEachNode(calculateCentrality);
if (!oriented) {
// The centrality scores need to be divided by two if the graph is not oriented,
// since all shortest paths are considered twice
Object.keys(centrality).forEach(divideByTwo);
}
return centrality;
function divideByTwo(key) {
centrality[key] /= 2;
}
function setCentralityToZero(node) {
centrality[node.id] = 0;
}
function calculateCentrality(node) {
currentNode = node.id;
singleSourceShortestPath(currentNode);
accumulate();
}
function accumulate() {
graph.forEachNode(setDeltaToZero);
while (S.length) {
var w = S.pop();
var coeff = (1 + delta[w])/sigma[w];
var predcessors = pred[w];
for (var idx = 0; idx < predcessors.length; ++idx) {
var v = predcessors[idx];
delta[v] += sigma[v] * coeff;
}
if (w !== currentNode) {
centrality[w] += delta[w];
}
}
}
function setDeltaToZero(node) {
delta[node.id] = 0;
}
function singleSourceShortestPath(source) {
graph.forEachNode(initNode);
dist[source] = 0;
sigma[source] = 1;
Q.push(source);
while (Q.length) {
var v = Q.shift();
var dedup = Object.create(null);
S.push(v);
graph.forEachLinkedNode(v, toId, oriented);
}
function toId(otherNode) {
// NOTE: This code will also consider multi-edges, which are often
// ignored by popular software (Gephi/NetworkX). Depending on your use
// case this may not be desired and deduping needs to be performed. To
// save memory I'm not deduping here...
processNode(otherNode.id);
}
function initNode(node) {
var nodeId = node.id;
pred[nodeId] = []; // empty list
dist[nodeId] = -1;
sigma[nodeId] = 0;
}
function processNode(w) {
// path discovery
if (dist[w] === -1) {
// Node w is found for the first time
dist[w] = dist[v] + 1;
Q.push(w);
}
// path counting
if (dist[w] === dist[v] + 1) {
// edge (v, w) on a shortest path
sigma[w] += sigma[v];
pred[w].push(v);
}
}
}
}
},{}],5:[function(require,module,exports){
module.exports = degree;
/**
* Calculates graph nodes degree centrality (in/out or both).
*
* @see http://en.wikipedia.org/wiki/Centrality#Degree_centrality
*
* @param {ngraph.graph} graph object for which we are calculating centrality.
* @param {string} [kind=both] What kind of degree centrality needs to be calculated:
* 'in' - calculate in-degree centrality
* 'out' - calculate out-degree centrality
* 'inout' - (default) generic degree centrality is calculated
*/
function degree(graph, kind) {
var getNodeDegree,
sortedDegrees = [],
result = Object.create(null),
nodeDegree;
kind = (kind || 'both').toLowerCase();
if (kind === 'both' || kind === 'inout') {
getNodeDegree = inoutDegreeCalculator;
} else if (kind === 'in') {
getNodeDegree = inDegreeCalculator;
} else if (kind === 'out') {
getNodeDegree = outDegreeCalculator;
} else {
throw new Error('Expected centrality degree kind is: in, out or both');
}
graph.forEachNode(calculateNodeDegree);
return result;
function calculateNodeDegree(node) {
var links = graph.getLinks(node.id);
result[node.id] = getNodeDegree(links, node.id);
}
}
function inDegreeCalculator(links, nodeId) {
var total = 0;
for (var i = 0; i < links.length; i += 1) {
total += (links[i].toId === nodeId) ? 1 : 0;
}
return total;
}
function outDegreeCalculator(links, nodeId) {
var total = 0;
for (var i = 0; i < links.length; i += 1) {
total += (links[i].fromId === nodeId) ? 1 : 0;
}
return total;
}
function inoutDegreeCalculator(links) {
return links.length;
}
},{}],6:[function(require,module,exports){
module.exports = function(subject) {
validateSubject(subject);
var eventsStorage = createEventsStorage(subject);
subject.on = eventsStorage.on;
subject.off = eventsStorage.off;
subject.fire = eventsStorage.fire;
return subject;
};
function createEventsStorage(subject) {
// Store all event listeners to this hash. Key is event name, value is array
// of callback records.
//
// A callback record consists of callback function and its optional context:
// { 'eventName' => [{callback: function, ctx: object}] }
var registeredEvents = Object.create(null);
return {
on: function (eventName, callback, ctx) {
if (typeof callback !== 'function') {
throw new Error('callback is expected to be a function');
}
var handlers = registeredEvents[eventName];
if (!handlers) {
handlers = registeredEvents[eventName] = [];
}
handlers.push({callback: callback, ctx: ctx});
return subject;
},
off: function (eventName, callback) {
var wantToRemoveAll = (typeof eventName === 'undefined');
if (wantToRemoveAll) {
// Killing old events storage should be enough in this case:
registeredEvents = Object.create(null);
return subject;
}
if (registeredEvents[eventName]) {
var deleteAllCallbacksForEvent = (typeof callback !== 'function');
if (deleteAllCallbacksForEvent) {
delete registeredEvents[eventName];
} else {
var callbacks = registeredEvents[eventName];
for (var i = 0; i < callbacks.length; ++i) {
if (callbacks[i].callback === callback) {
callbacks.splice(i, 1);
}
}
}
}
return subject;
},
fire: function (eventName) {
var callbacks = registeredEvents[eventName];
if (!callbacks) {
return subject;
}
var fireArguments;
if (arguments.length > 1) {
fireArguments = Array.prototype.splice.call(arguments, 1);
}
for(var i = 0; i < callbacks.length; ++i) {
var callbackInfo = callbacks[i];
callbackInfo.callback.apply(callbackInfo.ctx, fireArguments);
}
return subject;
}
};
}
function validateSubject(subject) {
if (!subject) {
throw new Error('Eventify cannot use falsy object as events subject');
}
var reservedWords = ['on', 'fire', 'off'];
for (var i = 0; i < reservedWords.length; ++i) {
if (subject.hasOwnProperty(reservedWords[i])) {
throw new Error("Subject cannot be eventified, since it already has property '" + reservedWords[i] + "'");
}
}
}
},{}],7:[function(require,module,exports){
module.exports = createLayout;
module.exports.simulator = require('ngraph.physics.simulator');
/**
* Creates force based layout for a given graph.
* @param {ngraph.graph} graph which needs to be laid out
* @param {object} physicsSettings if you need custom settings
* for physics simulator you can pass your own settings here. If it's not passed
* a default one will be created.
*/
function createLayout(graph, physicsSettings) {
if (!graph) {
throw new Error('Graph structure cannot be undefined');
}
var createSimulator = require('ngraph.physics.simulator');
var physicsSimulator = createSimulator(physicsSettings);
var nodeBodies = typeof Object.create === 'function' ? Object.create(null) : {};
var springs = {};
var springTransform = physicsSimulator.settings.springTransform || noop;
// Initialize physical objects according to what we have in the graph:
initPhysics();
listenToGraphEvents();
var api = {
/**
* Performs one step of iterative layout algorithm
*/
step: function() {
return physicsSimulator.step();
},
/**
* For a given `nodeId` returns position
*/
getNodePosition: function (nodeId) {
return getInitializedBody(nodeId).pos;
},
/**
* Sets position of a node to a given coordinates
* @param {string} nodeId node identifier
* @param {number} x position of a node
* @param {number} y position of a node
* @param {number=} z position of node (only if applicable to body)
*/
setNodePosition: function (nodeId) {
var body = getInitializedBody(nodeId);
body.setPosition.apply(body, Array.prototype.slice.call(arguments, 1));
},
/**
* @returns {Object} Link position by link id
* @returns {Object.from} {x, y} coordinates of link start
* @returns {Object.to} {x, y} coordinates of link end
*/
getLinkPosition: function (linkId) {
var spring = springs[linkId];
if (spring) {
return {
from: spring.from.pos,
to: spring.to.pos
};
}
},
/**
* @returns {Object} area required to fit in the graph. Object contains
* `x1`, `y1` - top left coordinates
* `x2`, `y2` - bottom right coordinates
*/
getGraphRect: function () {
return physicsSimulator.getBBox();
},
/*
* Requests layout algorithm to pin/unpin node to its current position
* Pinned nodes should not be affected by layout algorithm and always
* remain at their position
*/
pinNode: function (node, isPinned) {
var body = getInitializedBody(node.id);
body.isPinned = !!isPinned;
},
/**
* Checks whether given graph's node is currently pinned
*/
isNodePinned: function (node) {
return getInitializedBody(node.id).isPinned;
},
/**
* Request to release all resources
*/
dispose: function() {
graph.off('changed', onGraphChanged);
},
/**
* Gets physical body for a given node id. If node is not found undefined
* value is returned.
*/
getBody: getBody,
/**
* Gets spring for a given edge.
*
* @param {string} linkId link identifer. If two arguments are passed then
* this argument is treated as formNodeId
* @param {string=} toId when defined this parameter denotes head of the link
* and first argument is trated as tail of the link (fromId)
*/
getSpring: getSpring,
/**
* [Read only] Gets current physics simulator
*/
simulator: physicsSimulator
};
return api;
function getSpring(fromId, toId) {
var linkId;
if (toId === undefined) {
if (typeof fromId === 'string') {
// assume fromId as a linkId:
linkId = fromId;
} else {
// assume fromId to be a link object:
linkId = fromId.id;
}
} else {
// toId is defined, should grab link:
var link = graph.hasLink(fromId, toId);
if (!link) return;
linkId = link.id;
}
return springs[linkId];
}
function getBody(nodeId) {
return nodeBodies[nodeId];
}
function listenToGraphEvents() {
graph.on('changed', onGraphChanged);
}
function onGraphChanged(changes) {
for (var i = 0; i < changes.length; ++i) {
var change = changes[i];
if (change.changeType === 'add') {
if (change.node) {
initBody(change.node.id);
}
if (change.link) {
initLink(change.link);
}
} else if (change.changeType === 'remove') {
if (change.node) {
releaseNode(change.node);
}
if (change.link) {
releaseLink(change.link);
}
}
}
}
function initPhysics() {
graph.forEachNode(function (node) {
initBody(node.id);
});
graph.forEachLink(initLink);
}
function initBody(nodeId) {
var body = nodeBodies[nodeId];
if (!body) {
var node = graph.getNode(nodeId);
if (!node) {
throw new Error('initBody() was called with unknown node id');
}
var pos = node.position;
if (!pos) {
var neighbors = getNeighborBodies(node);
pos = physicsSimulator.getBestNewBodyPosition(neighbors);
}
body = physicsSimulator.addBodyAt(pos);
nodeBodies[nodeId] = body;
updateBodyMass(nodeId);
if (isNodeOriginallyPinned(node)) {
body.isPinned = true;
}
}
}
function releaseNode(node) {
var nodeId = node.id;
var body = nodeBodies[nodeId];
if (body) {
nodeBodies[nodeId] = null;
delete nodeBodies[nodeId];
physicsSimulator.removeBody(body);
}
}
function initLink(link) {
updateBodyMass(link.fromId);
updateBodyMass(link.toId);
var fromBody = nodeBodies[link.fromId],
toBody = nodeBodies[link.toId],
spring = physicsSimulator.addSpring(fromBody, toBody, link.length);
springTransform(link, spring);
springs[link.id] = spring;
}
function releaseLink(link) {
var spring = springs[link.id];
if (spring) {
var from = graph.getNode(link.fromId),
to = graph.getNode(link.toId);
if (from) updateBodyMass(from.id);
if (to) updateBodyMass(to.id);
delete springs[link.id];
physicsSimulator.removeSpring(spring);
}
}
function getNeighborBodies(node) {
// TODO: Could probably be done better on memory
var neighbors = [];
if (!node.links) {
return neighbors;
}
var maxNeighbors = Math.min(node.links.length, 2);
for (var i = 0; i < maxNeighbors; ++i) {
var link = node.links[i];
var otherBody = link.fromId !== node.id ? nodeBodies[link.fromId] : nodeBodies[link.toId];
if (otherBody && otherBody.pos) {
neighbors.push(otherBody);
}
}
return neighbors;
}
function updateBodyMass(nodeId) {
var body = nodeBodies[nodeId];
body.mass = nodeMass(nodeId);
}
/**
* Checks whether graph node has in its settings pinned attribute,
* which means layout algorithm cannot move it. Node can be preconfigured
* as pinned, if it has "isPinned" attribute, or when node.data has it.
*
* @param {Object} node a graph node to check
* @return {Boolean} true if node should be treated as pinned; false otherwise.
*/
function isNodeOriginallyPinned(node) {
return (node && (node.isPinned || (node.data && node.data.isPinned)));
}
function getInitializedBody(nodeId) {
var body = nodeBodies[nodeId];
if (!body) {
initBody(nodeId);
body = nodeBodies[nodeId];
}
return body;
}
/**
* Calculates mass of a body, which corresponds to node with given id.
*
* @param {String|Number} nodeId identifier of a node, for which body mass needs to be calculated
* @returns {Number} recommended mass of the body;
*/
function nodeMass(nodeId) {
return 1 + graph.getLinks(nodeId).length / 3.0;
}
}
function noop() { }
},{"ngraph.physics.simulator":8}],8:[function(require,module,exports){
/**
* Manages a simulation of physical forces acting on bodies and springs.
*/
module.exports = physicsSimulator;
function physicsSimulator(settings) {
var Spring = require('./lib/spring');
var expose = require('ngraph.expose');
var merge = require('ngraph.merge');
settings = merge(settings, {
/**
* Ideal length for links (springs in physical model).
*/
springLength: 30,
/**
* Hook's law coefficient. 1 - solid spring.
*/
springCoeff: 0.0008,
/**
* Coulomb's law coefficient. It's used to repel nodes thus should be negative
* if you make it positive nodes start attract each other :).
*/
gravity: -1.2,
/**
* Theta coefficient from Barnes Hut simulation. Ranged between (0, 1).
* The closer it's to 1 the more nodes algorithm will have to go through.
* Setting it to one makes Barnes Hut simulation no different from
* brute-force forces calculation (each node is considered).
*/
theta: 0.8,
/**
* Drag force coefficient. Used to slow down system, thus should be less than 1.
* The closer it is to 0 the less tight system will be.
*/
dragCoeff: 0.02,
/**
* Default time step (dt) for forces integration
*/
timeStep : 20,
/**
* Maximum movement of the system which can be considered as stabilized
*/
stableThreshold: 0.009
});
// We allow clients to override basic factory methods:
var createQuadTree = settings.createQuadTree || require('ngraph.quadtreebh');
var createBounds = settings.createBounds || require('./lib/bounds');
var createDragForce = settings.createDragForce || require('./lib/dragForce');
var createSpringForce = settings.createSpringForce || require('./lib/springForce');
var integrate = settings.integrator || require('./lib/eulerIntegrator');
var createBody = settings.createBody || require('./lib/createBody');
var bodies = [], // Bodies in this simulation.
springs = [], // Springs in this simulation.
quadTree = createQuadTree(settings),
bounds = createBounds(bodies, settings),
springForce = createSpringForce(settings),
dragForce = createDragForce(settings);
var publicApi = {
/**
* Array of bodies, registered with current simulator
*
* Note: To add new body, use addBody() method. This property is only
* exposed for testing/performance purposes.
*/
bodies: bodies,
/**
* Array of springs, registered with current simulator
*
* Note: To add new spring, use addSpring() method. This property is only
* exposed for testing/performance purposes.
*/
springs: springs,
/**
* Returns settings with which current simulator was initialized
*/
settings: settings,
/**
* Performs one step of force simulation.
*
* @returns {boolean} true if system is considered stable; False otherwise.
*/
step: function () {
accumulateForces();
var totalMovement = integrate(bodies, settings.timeStep);
bounds.update();
return totalMovement < settings.stableThreshold;
},
/**
* Adds body to the system
*
* @param {ngraph.physics.primitives.Body} body physical body
*
* @returns {ngraph.physics.primitives.Body} added body
*/
addBody: function (body) {
if (!body) {
throw new Error('Body is required');
}
bodies.push(body);
return body;
},
/**
* Adds body to the system at given position
*
* @param {Object} pos position of a body
*
* @returns {ngraph.physics.primitives.Body} added body
*/
addBodyAt: function (pos) {
if (!pos) {
throw new Error('Body position is required');
}
var body = createBody(pos);
bodies.push(body);
return body;
},
/**
* Removes body from the system
*
* @param {ngraph.physics.primitives.Body} body to remove
*
* @returns {Boolean} true if body found and removed. falsy otherwise;
*/
removeBody: function (body) {
if (!body) { return; }
var idx = bodies.indexOf(body);
if (idx < 0) { return; }
bodies.splice(idx, 1);
if (bodies.length === 0) {
bounds.reset();
}
return true;
},
/**
* Adds a spring to this simulation.
*
* @returns {Object} - a handle for a spring. If you want to later remove
* spring pass it to removeSpring() method.
*/
addSpring: function (body1, body2, springLength, springWeight, springCoefficient) {
if (!body1 || !body2) {
throw new Error('Cannot add null spring to force simulator');
}
if (typeof springLength !== 'number') {
springLength = -1; // assume global configuration
}
var spring = new Spring(body1, body2, springLength, springCoefficient >= 0 ? springCoefficient : -1, springWeight);
springs.push(spring);
// TODO: could mark simulator as dirty.
return spring;
},
/**
* Removes spring from the system
*
* @param {Object} spring to remove. Spring is an object returned by addSpring
*
* @returns {Boolean} true if spring found and removed. falsy otherwise;
*/
removeSpring: function (spring) {
if (!spring) { return; }
var idx = springs.indexOf(spring);
if (idx > -1) {
springs.splice(idx, 1);
return true;
}
},
getBestNewBodyPosition: function (neighbors) {
return bounds.getBestNewPosition(neighbors);
},
/**
* Returns bounding box which covers all bodies
*/
getBBox: function () {
return bounds.box;
},
gravity: function (value) {
if (value !== undefined) {
settings.gravity = value;
quadTree.options({gravity: value});
return this;
} else {
return settings.gravity;
}
},
theta: function (value) {
if (value !== undefined) {
settings.theta = value;
quadTree.options({theta: value});
return this;
} else {
return settings.theta;
}
}
};
// allow settings modification via public API:
expose(settings, publicApi);
return publicApi;
function accumulateForces() {
// Accumulate forces acting on bodies.
var body,
i = bodies.length;
if (i) {
// only add bodies if there the array is not empty:
quadTree.insertBodies(bodies); // performance: O(n * log n)
while (i--) {
body = bodies[i];
// If body is pinned there is no point updating its forces - it should
// never move:
if (!body.isPinned) {
body.force.reset();
quadTree.updateBodyForce(body);
dragForce.update(body);
}
}
}
i = springs.length;
while(i--) {
springForce.update(springs[i]);
}
}
};
},{"./lib/bounds":9,"./lib/createBody":10,"./lib/dragForce":11,"./lib/eulerIntegrator":12,"./lib/spring":13,"./lib/springForce":14,"ngraph.expose":15,"ngraph.merge":24,"ngraph.quadtreebh":17}],9:[function(require,module,exports){
module.exports = function (bodies, settings) {
var random = require('ngraph.random').random(42);
var boundingBox = { x1: 0, y1: 0, x2: 0, y2: 0 };
return {
box: boundingBox,
update: updateBoundingBox,
reset : function () {
boundingBox.x1 = boundingBox.y1 = 0;
boundingBox.x2 = boundingBox.y2 = 0;
},
getBestNewPosition: function (neighbors) {
var graphRect = boundingBox;
var baseX = 0, baseY = 0;
if (neighbors.length) {
for (var i = 0; i < neighbors.length; ++i) {
baseX += neighbors[i].pos.x;
baseY += neighbors[i].pos.y;
}
baseX /= neighbors.length;
baseY /= neighbors.length;
} else {
baseX = (graphRect.x1 + graphRect.x2) / 2;
baseY = (graphRect.y1 + graphRect.y2) / 2;
}
var springLength = settings.springLength;
return {
x: baseX + random.next(springLength) - springLength / 2,
y: baseY + random.next(springLength) - springLength / 2
};
}
};
function updateBoundingBox() {
var i = bodies.length;
if (i === 0) { return; } // don't have to wory here.
var x1 = Number.MAX_VALUE,
y1 = Number.MAX_VALUE,
x2 = Number.MIN_VALUE,
y2 = Number.MIN_VALUE;
while(i--) {
// this is O(n), could it be done faster with quadtree?
// how about pinned nodes?
var body = bodies[i];
if (body.isPinned) {
body.pos.x = body.prevPos.x;
body.pos.y = body.prevPos.y;
} else {
body.prevPos.x = body.pos.x;
body.prevPos.y = body.pos.y;
}
if (body.pos.x < x1) {
x1 = body.pos.x;
}
if (body.pos.x > x2) {
x2 = body.pos.x;
}
if (body.pos.y < y1) {
y1 = body.pos.y;
}
if (body.pos.y > y2) {
y2 = body.pos.y;
}
}
boundingBox.x1 = x1;
boundingBox.x2 = x2;
boundingBox.y1 = y1;
boundingBox.y2 = y2;
}
}
},{"ngraph.random":25}],10:[function(require,module,exports){
var physics = require('ngraph.physics.primitives');
module.exports = function(pos) {
return new physics.Body(pos);
}
},{"ngraph.physics.primitives":16}],11:[function(require,module,exports){
/**
* Represents drag force, which reduces force value on each step by given
* coefficient.
*
* @param {Object} options for the drag force
* @param {Number=} options.dragCoeff drag force coefficient. 0.1 by default
*/
module.exports = function (options) {
var merge = require('ngraph.merge'),
expose = require('ngraph.expose');
options = merge(options, {
dragCoeff: 0.02
});
var api = {
update : function (body) {
body.force.x -= options.dragCoeff * body.velocity.x;
body.force.y -= options.dragCoeff * body.velocity.y;
}
};
// let easy access to dragCoeff:
expose(options, api, ['dragCoeff']);
return api;
};
},{"ngraph.expose":15,"ngraph.merge":24}],12:[function(require,module,exports){
/**
* Performs forces integration, using given timestep. Uses Euler method to solve
* differential equation (http://en.wikipedia.org/wiki/Euler_method ).
*
* @returns {Number} squared distance of total position updates.
*/
module.exports = integrate;
function integrate(bodies, timeStep) {
var dx = 0, tx = 0,
dy = 0, ty = 0,
i,
max = bodies.length;
for (i = 0; i < max; ++i) {
var body = bodies[i],
coeff = timeStep / body.mass;
body.velocity.x += coeff * body.force.x;
body.velocity.y += coeff * body.force.y;
var vx = body.velocity.x,
vy = body.velocity.y,
v = Math.sqrt(vx * vx + vy * vy);
if (v > 1) {
body.velocity.x = vx / v;
body.velocity.y = vy / v;
}
dx = timeStep * body.velocity.x;
dy = timeStep * body.velocity.y;
body.pos.x += dx;
body.pos.y += dy;
tx += Math.abs(dx); ty += Math.abs(dy);
}
return (tx * tx + ty * ty)/bodies.length;
}
},{}],13:[function(require,module,exports){
module.exports = Spring;
/**
* Represents a physical spring. Spring connects two bodies, has rest length
* stiffness coefficient and optional weight
*/
function Spring(fromBody, toBody, length, coeff, weight) {
this.from = fromBody;
this.to = toBody;
this.length = length;
this.coeff = coeff;
this.weight = typeof weight === 'number' ? weight : 1;
};
},{}],14:[function(require,module,exports){
/**
* Represents spring force, which updates forces acting on two bodies, conntected
* by a spring.
*
* @param {Object} options for the spring force
* @param {Number=} options.springCoeff spring force coefficient.
* @param {Number=} options.springLength desired length of a spring at rest.
*/
module.exports = function (options) {
var merge = require('ngraph.merge');
var random = require('ngraph.random').random(42);
var expose = require('ngraph.expose');
options = merge(options, {
springCoeff: 0.0002,
springLength: 80
});
var api = {
/**
* Upsates forces acting on a spring
*/
update : function (spring) {
var body1 = spring.from,
body2 = spring.to,
length = spring.length < 0 ? options.springLength : spring.length,
dx = body2.pos.x - body1.pos.x,
dy = body2.pos.y - body1.pos.y,
r = Math.sqrt(dx * dx + dy * dy);
if (r === 0) {
dx = (random.nextDouble() - 0.5) / 50;
dy = (random.nextDouble() - 0.5) / 50;
r = Math.sqrt(dx * dx + dy * dy);
}
var d = r - length;
var coeff = ((!spring.coeff || spring.coeff < 0) ? options.springCoeff : spring.coeff) * d / r * spring.weight;
body1.force.x += coeff * dx;
body1.force.y += coeff * dy;
body2.force.x -= coeff * dx;
body2.force.y -= coeff * dy;
}
};
expose(options, api, ['springCoeff', 'springLength']);
return api;
}
},{"ngraph.expose":15,"ngraph.merge":24,"ngraph.random":25}],15:[function(require,module,exports){
module.exports = exposeProperties;
/**
* Augments `target` object with getter/setter functions, which modify settings
*
* @example
* var target = {};
* exposeProperties({ age: 42}, target);
* target.age(); // returns 42
* target.age(24); // make age 24;
*
* var filteredTarget = {};
* exposeProperties({ age: 42, name: 'John'}, filteredTarget, ['name']);
* filteredTarget.name(); // returns 'John'
* filteredTarget.age === undefined; // true
*/
function exposeProperties(settings, target, filter) {
var needsFilter = Object.prototype.toString.call(filter) === '[object Array]';
if (needsFilter) {
for (var i = 0; i < filter.length; ++i) {
augment(settings, target, filter[i]);
}
} else {
for (var key in settings) {
augment(settings, target, key);
}
}
}
function augment(source, target, key) {
if (source.hasOwnProperty(key)) {
if (typeof target[key] === 'function') {
// this accessor is already defined. Ignore it
return;
}
target[key] = function (value) {
if (value !== undefined) {
source[key] = value;
return target;
}
return source[key];
}
}
}
},{}],16:[function(require,module,exports){
module.exports = {
Body: Body,
Vector2d: Vector2d,
Body3d: Body3d,
Vector3d: Vector3d
};
function Body(x, y) {
this.pos = new Vector2d(x, y);
this.prevPos = new Vector2d(x, y);
this.force = new Vector2d();
this.velocity = new Vector2d();
this.mass = 1;
}
Body.prototype.setPosition = function (x, y) {
this.prevPos.x = this.pos.x = x;
this.prevPos.y = this.pos.y = y;
};
function Vector2d(x, y) {
if (x && typeof x !== 'number') {
// could be another vector
this.x = typeof x.x === 'number' ? x.x : 0;
this.y = typeof x.y === 'number' ? x.y : 0;
} else {
this.x = typeof x === 'number' ? x : 0;
this.y = typeof y === 'number' ? y : 0;
}
}
Vector2d.prototype.reset = function () {
this.x = this.y = 0;
};
function Body3d(x, y, z) {
this.pos = new Vector3d(x, y, z);
this.prevPos = new Vector3d(x, y, z);
this.force = new Vector3d();
this.velocity = new Vector3d();
this.mass = 1;
}
Body3d.prototype.setPosition = function (x, y, z) {
this.prevPos.x = this.pos.x = x;
this.prevPos.y = this.pos.y = y;
this.prevPos.z = this.pos.z = z;
};
function Vector3d(x, y, z) {
if (x && typeof x !== 'number') {
// could be another vector
this.x = typeof x.x === 'number' ? x.x : 0;
this.y = typeof x.y === 'number' ? x.y : 0;
this.z = typeof x.z === 'number' ? x.z : 0;
} else {
this.x = typeof x === 'number' ? x : 0;
this.y = typeof y === 'number' ? y : 0;
this.z = typeof z === 'number' ? z : 0;
}
};
Vector3d.prototype.reset = function () {
this.x = this.y = this.z = 0;
};
},{}],17:[function(require,module,exports){
/**
* This is Barnes Hut simulation algorithm for 2d case. Implementation
* is highly optimized (avoids recusion and gc pressure)
*
* http://www.cs.princeton.edu/courses/archive/fall03/cs126/assignments/barnes-hut.html
*/
module.exports = function(options) {
options = options || {};
options.gravity = typeof options.gravity === 'number' ? options.gravity : -1;
options.theta = typeof options.theta === 'number' ? options.theta : 0.8;
// we require deterministic randomness here
var random = require('ngraph.random').random(1984),
Node = require('./node'),
InsertStack = require('./insertStack'),
isSamePosition = require('./isSamePosition');
var gravity = options.gravity,
updateQueue = [],
insertStack = new InsertStack(),
theta = options.theta,
nodesCache = [],
currentInCache = 0,
newNode = function() {
// To avoid pressure on GC we reuse nodes.
var node = nodesCache[currentInCache];
if (node) {
node.quad0 = null;
node.quad1 = null;
node.quad2 = null;
node.quad3 = null;
node.body = null;
node.mass = node.massX = node.massY = 0;
node.left = node.right = node.top = node.bottom = 0;
} else {
node = new Node();
nodesCache[currentInCache] = node;
}
++currentInCache;
return node;
},
root = newNode(),
// Inserts body to the tree
insert = function(newBody) {
insertStack.reset();
insertStack.push(root, newBody);
while (!insertStack.isEmpty()) {
var stackItem = insertStack.pop(),
node = stackItem.node,
body = stackItem.body;
if (!node.body) {
// This is internal node. Update the total mass of the node and center-of-mass.
var x = body.pos.x;
var y = body.pos.y;
node.mass = node.mass + body.mass;
node.massX = node.massX + body.mass * x;
node.massY = node.massY + body.mass * y;
// Recursively insert the body in the appropriate quadrant.
// But first find the appropriate quadrant.
var quadIdx = 0, // Assume we are in the 0's quad.
left = node.left,
right = (node.right + left) / 2,
top = node.top,
bottom = (node.bottom + top) / 2;
if (x > right) { // somewhere in the eastern part.
quadIdx = quadIdx + 1;
var oldLeft = left;
left = right;
right = right + (right - oldLeft);
}
if (y > bottom) { // and in south.
quadIdx = quadIdx + 2;
var oldTop = top;
top = bottom;
bottom = bottom + (bottom - oldTop);
}
var child = getChild(node, quadIdx);
if (!child) {
// The node is internal but this quadrant is not taken. Add
// subnode to it.
child = newNode();
child.left = left;
child.top = top;
child.right = right;
child.bottom = bottom;
child.body = body;
setChild(node, quadIdx, child);
} else {
// continue searching in this quadrant.
insertStack.push(child, body);
}
} else {
// We are trying to add to the leaf node.
// We have to convert current leaf into internal node
// and continue adding two nodes.
var oldBody = node.body;
node.body = null; // internal nodes do not cary bodies
if (isSamePosition(oldBody.pos, body.pos)) {
// Prevent infinite subdivision by bumping one node
// anywhere in this quadrant
var retriesCount = 3;
do {
var offset = random.nextDouble();
var dx = (node.right - node.left) * offset;
var dy = (node.bottom - node.top) * offset;
oldBody.pos.x = node.left + dx;
oldBody.pos.y = node.top + dy;
retriesCount -= 1;
// Make sure we don't bump it out of the box. If we do, next iteration should fix it
} while (retriesCount > 0 && isSamePosition(oldBody.pos, body.pos));
if (retriesCount === 0 && isSamePosition(oldBody.pos, body.pos)) {
// This is very bad, we ran out of precision.
// if we do not return from the method we'll get into
// infinite loop here. So we sacrifice correctness of layout, and keep the app running
// Next layout iteration should get larger bounding box in the first step and fix this
return;
}
}
// Next iteration should subdivide node further.
insertStack.push(node, oldBody);
insertStack.push(node, body);
}
}
},
update = function(sourceBody) {
var queue = updateQueue,
v,
dx,
dy,
r, fx = 0,
fy = 0,
queueLength = 1,
shiftIdx = 0,
pushIdx = 1;
queue[0] = root;
while (queueLength) {
var node = queue[shiftIdx],
body = node.body;
queueLength -= 1;
shiftIdx += 1;
var differentBody = (body !== sourceBody);
if (body && differentBody) {
// If the current node is a leaf node (and it is not source body),
// calculate the force exerted by the current node on body, and add this
// amount to body's net force.
dx = body.pos.x - sourceBody.pos.x;
dy = body.pos.y - sourceBody.pos.y;
r = Math.sqrt(dx * dx + dy * dy);
if (r === 0) {
// Poor man's protection against zero distance.
dx = (random.nextDouble() - 0.5) / 50;
dy = (random.nextDouble() - 0.5) / 50;
r = Math.sqrt(dx * dx + dy * dy);
}
// This is standard gravition force calculation but we divide
// by r^3 to save two operations when normalizing force vector.
v = gravity * body.mass * sourceBody.mass / (r * r * r);
fx += v * dx;
fy += v * dy;
} else if (differentBody) {
// Otherwise, calculate the ratio s / r, where s is the width of the region
// represented by the internal node, and r is the distance between the body
// and the node's center-of-mass
dx = node.massX / node.mass - sourceBody.pos.x;
dy = node.massY / node.mass - sourceBody.pos.y;
r = Math.sqrt(dx * dx + dy * dy);
if (r === 0) {
// Sorry about code duplucation. I don't want to create many functions
// right away. Just want to see performance first.
dx = (random.nextDouble() - 0.5) / 50;
dy = (random.nextDouble() - 0.5) / 50;
r = Math.sqrt(dx * dx + dy * dy);
}
// If s / r < θ, treat this internal node as a single body, and calculate the
// force it exerts on sourceBody, and add this amount to sourceBody's net force.
if ((node.right - node.left) / r < theta) {
// in the if statement above we consider node's width only
// because the region was squarified during tree creation.
// Thus there is no difference between using width or height.
v = gravity * node.mass * sourceBody.mass / (r * r * r);
fx += v * dx;
fy += v * dy;
} else {
// Otherwise, run the procedure recursively on each of the current node's children.
// I intentionally unfolded this loop, to save several CPU cycles.
if (node.quad0) {
queue[pushIdx] = node.quad0;
queueLength += 1;
pushIdx += 1;
}
if (node.quad1) {
queue[pushIdx] = node.quad1;
queueLength += 1;
pushIdx += 1;
}
if (node.quad2) {
queue[pushIdx] = node.quad2;
queueLength += 1;
pushIdx += 1;
}
if (node.quad3) {
queue[pushIdx] = node.quad3;
queueLength += 1;
pushIdx += 1;
}
}
}
}
sourceBody.force.x += fx;
sourceBody.force.y += fy;
},
insertBodies = function(bodies) {
var x1 = Number.MAX_VALUE,
y1 = Number.MAX_VALUE,
x2 = Number.MIN_VALUE,
y2 = Number.MIN_VALUE,
i,
max = bodies.length;
// To reduce quad tree depth we are looking for exact bounding box of all particles.
i = max;
while (i--) {
var x = bodies[i].pos.x;
var y = bodies[i].pos.y;
if (x < x1) {
x1 = x;
}
if (x > x2) {
x2 = x;
}
if (y < y1) {
y1 = y;
}
if (y > y2) {
y2 = y;
}
}
// Squarify the bounds.
var dx = x2 - x1,
dy = y2 - y1;
if (dx > dy) {
y2 = y1 + dx;
} else {
x2 = x1 + dy;
}
currentInCache = 0;
root = newNode();
root.left = x1;
root.right = x2;
root.top = y1;
root.bottom = y2;
i = max - 1;
if (i > 0) {
root.body = bodies[i];
}
while (i--) {
insert(bodies[i], root);
}
};
return {
insertBodies: insertBodies,
updateBodyForce: update,
options: function(newOptions) {
if (newOptions) {
if (typeof newOptions.gravity === 'number') {
gravity = newOptions.gravity;
}
if (typeof newOptions.theta === 'number') {
theta = newOptions.theta;
}
return this;
}
return {
gravity: gravity,
theta: theta
};
}
};
};
function getChild(node, idx) {
if (idx === 0) return node.quad0;
if (idx === 1) return node.quad1;
if (idx === 2) return node.quad2;
if (idx === 3) return node.quad3;
return null;
}
function setChild(node, idx, child) {
if (idx === 0) node.quad0 = child;
else if (idx === 1) node.quad1 = child;
else if (idx === 2) node.quad2 = child;
else if (idx === 3) node.quad3 = child;
}
},{"./insertStack":18,"./isSamePosition":19,"./node":20,"ngraph.random":25}],18:[function(require,module,exports){
module.exports = InsertStack;
/**
* Our implmentation of QuadTree is non-recursive to avoid GC hit
* This data structure represent stack of elements
* which we are trying to insert into quad tree.
*/
function InsertStack () {
this.stack = [];
this.popIdx = 0;
}
InsertStack.prototype = {
isEmpty: function() {
return this.popIdx === 0;
},
push: function (node, body) {
var item = this.stack[this.popIdx];
if (!item) {
// we are trying to avoid memory pressue: create new element
// only when absolutely necessary
this.stack[this.popIdx] = new InsertStackElement(node, body);
} else {
item.node = node;
item.body = body;
}
++this.popIdx;
},
pop: function () {
if (this.popIdx > 0) {
return this.stack[--this.popIdx];
}
},
reset: function () {
this.popIdx = 0;
}
};
function InsertStackElement(node, body) {
this.node = node; // QuadTree node
this.body = body; // physical body which needs to be inserted to node
}
},{}],19:[function(require,module,exports){
module.exports = function isSamePosition(point1, point2) {
var dx = Math.abs(point1.x - point2.x);
var dy = Math.abs(point1.y - point2.y);
return (dx < 1e-8 && dy < 1e-8);
};
},{}],20:[function(require,module,exports){
/**
* Internal data structure to represent 2D QuadTree node
*/
module.exports = function Node() {
// body stored inside this node. In quad tree only leaf nodes (by construction)
// contain boides:
this.body = null;
// Child nodes are stored in quads. Each quad is presented by number:
// 0 | 1
// -----
// 2 | 3
this.quad0 = null;
this.quad1 = null;
this.quad2 = null;
this.quad3 = null;
// Total mass of current node
this.mass = 0;
// Center of mass coordinates
this.massX = 0;
this.massY = 0;
// bounding box coordinates
this.left = 0;
this.top = 0;
this.bottom = 0;
this.right = 0;
};
},{}],21:[function(require,module,exports){
module.exports = load;
var createGraph = require('ngraph.graph');
function load(jsonGraph, nodeTransform, linkTransform) {
var stored;
nodeTransform = nodeTransform || id;
linkTransform = linkTransform || id;
if (typeof jsonGraph === 'string') {
stored = JSON.parse(jsonGraph);
} else {
stored = jsonGraph;
}
var graph = createGraph(),
i;
if (stored.links === undefined || stored.nodes === undefined) {
throw new Error('Cannot load graph without links and nodes');
}
for (i = 0; i < stored.nodes.length; ++i) {
var parsedNode = nodeTransform(stored.nodes[i]);
if (!parsedNode.hasOwnProperty('id')) {
throw new Error('Graph node format is invalid: Node id is missing');
}
graph.addNode(parsedNode.id, parsedNode.data);
}
for (i = 0; i < stored.links.length; ++i) {
var link = linkTransform(stored.links[i]);
if (!link.hasOwnProperty('fromId') || !link.hasOwnProperty('toId')) {
throw new Error('Graph link format is invalid. Both fromId and toId are required');
}
graph.addLink(link.fromId, link.toId, link.data);
}
return graph;
}
function id(x) { return x; }
},{"ngraph.graph":23}],22:[function(require,module,exports){
module.exports = {
ladder: ladder,
complete: complete,
completeBipartite: completeBipartite,
balancedBinTree: balancedBinTree,
path: path,
circularLadder: circularLadder,
grid: grid,
grid3: grid3,
noLinks: noLinks,
wattsStrogatz: wattsStrogatz
};
var createGraph = require('ngraph.graph');
function ladder(n) {
/**
* Ladder graph is a graph in form of ladder
* @param {Number} n Represents number of steps in the ladder
*/
if (!n || n < 0) {
throw new Error("Invalid number of nodes");
}
var g = createGraph(),
i;
for (i = 0; i < n - 1; ++i) {
g.addLink(i, i + 1);
// first row
g.addLink(n + i, n + i + 1);
// second row
g.addLink(i, n + i);
// ladder's step
}
g.addLink(n - 1, 2 * n - 1);
// last step in the ladder;
return g;
}
function circularLadder(n) {
/**
* Circular ladder with n steps.
*
* @param {Number} n of steps in the ladder.
*/
if (!n || n < 0) {
throw new Error("Invalid number of nodes");
}
var g = ladder(n);
g.addLink(0, n - 1);
g.addLink(n, 2 * n - 1);
return g;
}
function complete(n) {
/**
* Complete graph Kn.
*
* @param {Number} n represents number of nodes in the complete graph.
*/
if (!n || n < 1) {
throw new Error("At least two nodes are expected for complete graph");
}
var g = createGraph(),
i,
j;
for (i = 0; i < n; ++i) {
for (j = i + 1; j < n; ++j) {
if (i !== j) {
g.addLink(i, j);
}
}
}
return g;
}
function completeBipartite (n, m) {
/**
* Complete bipartite graph K n,m. Each node in the
* first partition is connected to all nodes in the second partition.
*
* @param {Number} n represents number of nodes in the first graph partition
* @param {Number} m represents number of nodes in the second graph partition
*/
if (!n || !m || n < 0 || m < 0) {
throw new Error("Graph dimensions are invalid. Number of nodes in each partition should be greater than 0");
}
var g = createGraph(),
i, j;
for (i = 0; i < n; ++i) {
for (j = n; j < n + m; ++j) {
g.addLink(i, j);
}
}
return g;
}
function path(n) {
/**
* Path graph with n steps.
*
* @param {Number} n number of nodes in the path
*/
if (!n || n < 0) {
throw new Error("Invalid number of nodes");
}
var g = createGraph(),
i;
g.addNode(0);
for (i = 1; i < n; ++i) {
g.addLink(i - 1, i);
}
return g;
}
function grid(n, m) {
/**
* Grid graph with n rows and m columns.
*
* @param {Number} n of rows in the graph.
* @param {Number} m of columns in the graph.
*/
if (n < 1 || m < 1) {
throw new Error("Invalid number of nodes in grid graph");
}
var g = createGraph(),
i,
j;
if (n === 1 && m === 1) {
g.addNode(0);
return g;
}
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
var node = i + j * n;
if (i > 0) { g.addLink(node, i - 1 + j * n); }
if (j > 0) { g.addLink(node, i + (j - 1) * n); }
}
}
return g;
}
function grid3(n, m, z) {
/**
* 3D grid with n rows and m columns and z levels.
*
* @param {Number} n of rows in the graph.
* @param {Number} m of columns in the graph.
* @param {Number} z of levels in the graph.
*/
if (n < 1 || m < 1 || z < 1) {
throw new Error("Invalid number of nodes in grid3 graph");
}
var g = createGraph(),
i, j, k;
if (n === 1 && m === 1 && z === 1) {
g.addNode(0);
return g;
}
for (k = 0; k < z; ++k) {
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
var level = k * n * m;
var node = i + j * n + level;
if (i > 0) { g.addLink(node, i - 1 + j * n + level); }
if (j > 0) { g.addLink(node, i + (j - 1) * n + level); }
if (k > 0) { g.addLink(node, i + j * n + (k - 1) * n * m ); }
}
}
}
return g;
}
function balancedBinTree(n) {
/**
* Balanced binary tree with n levels.
*
* @param {Number} n of levels in the binary tree
*/
if (n < 0) {
throw new Error("Invalid number of nodes in balanced tree");
}
var g = createGraph(),
count = Math.pow(2, n),
level;
if (n === 0) {
g.addNode(1);
}
for (level = 1; level < count; ++level) {
var root = level,
left = root * 2,
right = root * 2 + 1;
g.addLink(root, left);
g.addLink(root, right);
}
return g;
}
function noLinks(n) {
/**
* Graph with no links
*
* @param {Number} n of nodes in the graph
*/
if (n < 0) {
throw new Error("Number of nodes shoul be >= 0");
}
var g = createGraph(), i;
for (i = 0; i < n; ++i) {
g.addNode(i);
}
return g;
}
function wattsStrogatz(n, k, p, seed) {
/**
* Watts-Strogatz small-world graph.
*
* @param {Number} n The number of nodes
* @param {Number} k Each node is connected to k nearest neighbors in ring topology
* @param {Number} p The probability of rewiring each edge
* @see https://github.com/networkx/networkx/blob/master/networkx/generators/random_graphs.py
*/
if (k >= n) throw new Error('Choose smaller `k`. It cannot be larger than number of nodes `n`');
var random = require('ngraph.random').random(seed || 42);
var g = createGraph(), i, to;
for (i = 0; i < n; ++i) {
g.addNode(i);
}
// connect each node to k/2 neighbors
var neighborsSize = Math.floor(k/2 + 1);
for (var j = 1; j < neighborsSize; ++j) {
for (i = 0; i < n; ++i) {
to = (j + i) % n;
g.addLink(i, to);
}
}
// rewire edges from each node
// loop over all nodes in order (label) and neighbors in order (distance)
// no self loops or multiple edges allowed
for (j = 1; j < neighborsSize; ++j) {
for (i = 0; i < n; ++i) {
if (random.nextDouble() < p) {
var from = i;
to = (j + i) % n;
var newTo = random.next(n);
var needsRewire = (newTo === from || g.hasLink(from, newTo));
if (needsRewire && g.getLinks(from).length === n - 1) {
// we cannot rewire this node, it has too many links.
continue;
}
// Enforce no self-loops or multiple edges
while (needsRewire) {
newTo = random.next(n);
needsRewire = (newTo === from || g.hasLink(from, newTo));
}
var link = g.hasLink(from, to);
g.removeLink(link);
g.addLink(from, newTo);
}
}
}
return g;
}
},{"ngraph.graph":23,"ngraph.random":25}],23:[function(require,module,exports){
/**
* @fileOverview Contains definition of the core graph object.
*/
/**
* @example
* var graph = require('ngraph.graph')();
* graph.addNode(1); // graph has one node.
* graph.addLink(2, 3); // now graph contains three nodes and one link.
*
*/
module.exports = createGraph;
var eventify = require('ngraph.events');
/**
* Creates a new graph
*/
function createGraph(options) {
// Graph structure is maintained as dictionary of nodes
// and array of links. Each node has 'links' property which
// hold all links related to that node. And general links
// array is used to speed up all links enumeration. This is inefficient
// in terms of memory, but simplifies coding.
options = options || {};
if (options.uniqueLinkId === undefined) {
// Request each link id to be unique between same nodes. This negatively
// impacts `addLink()` performance (O(n), where n - number of edges of each
// vertex), but makes operations with multigraphs more accessible.
options.uniqueLinkId = true;
}
var nodes = typeof Object.create === 'function' ? Object.create(null) : {},
links = [],
// Hash of multi-edges. Used to track ids of edges between same nodes
multiEdges = {},
nodesCount = 0,
suspendEvents = 0,
forEachNode = createNodeIterator(),
createLink = options.uniqueLinkId ? createUniqueLink : createSingleLink,
// Our graph API provides means to listen to graph changes. Users can subscribe
// to be notified about changes in the graph by using `on` method. However
// in some cases they don't use it. To avoid unnecessary memory consumption
// we will not record graph changes until we have at least one subscriber.
// Code below supports this optimization.
//
// Accumulates all changes made during graph updates.
// Each change element contains:
// changeType - one of the strings: 'add', 'remove' or 'update';
// node - if change is related to node this property is set to changed graph's node;
// link - if change is related to link this property is set to changed graph's link;
changes = [],
recordLinkChange = noop,
recordNodeChange = noop,
enterModification = noop,
exitModification = noop;
// this is our public API:
var graphPart = {
/**
* Adds node to the graph. If node with given id already exists in the graph
* its data is extended with whatever comes in 'data' argument.
*
* @param nodeId the node's identifier. A string or number is preferred.
* note: If you request options.uniqueLinkId, then node id should not
* contain '👉 '. This will break link identifiers
* @param [data] additional data for the node being added. If node already
* exists its data object is augmented with the new one.
*
* @return {node} The newly added node or node with given id if it already exists.
*/
addNode: addNode,
/**
* Adds a link to the graph. The function always create a new
* link between two nodes. If one of the nodes does not exists
* a new node is created.
*
* @param fromId link start node id;
* @param toId link end node id;
* @param [data] additional data to be set on the new link;
*
* @return {link} The newly created link
*/
addLink: addLink,
/**
* Removes link from the graph. If link does not exist does nothing.
*
* @param link - object returned by addLink() or getLinks() methods.
*
* @returns true if link was removed; false otherwise.
*/
removeLink: removeLink,
/**
* Removes node with given id from the graph. If node does not exist in the graph
* does nothing.
*
* @param nodeId node's identifier passed to addNode() function.
*
* @returns true if node was removed; false otherwise.
*/
removeNode: removeNode,
/**
* Gets node with given identifier. If node does not exist undefined value is returned.
*
* @param nodeId requested node identifier;
*
* @return {node} in with requested identifier or undefined if no such node exists.
*/
getNode: getNode,
/**
* Gets number of nodes in this graph.
*
* @return number of nodes in the graph.
*/
getNodesCount: function() {
return nodesCount;
},
/**
* Gets total number of links in the graph.
*/
getLinksCount: function() {
return links.length;
},
/**
* Gets all links (inbound and outbound) from the node with given id.
* If node with given id is not found null is returned.
*
* @param nodeId requested node identifier.
*
* @return Array of links from and to requested node if such node exists;
* otherwise null is returned.
*/
getLinks: getLinks,
/**
* Invokes callback on each node of the graph.
*
* @param {Function(node)} callback Function to be invoked. The function
* is passed one argument: visited node.
*/
forEachNode: forEachNode,
/**
* Invokes callback on every linked (adjacent) node to the given one.
*
* @param nodeId Identifier of the requested node.
* @param {Function(node, link)} callback Function to be called on all linked nodes.
* The function is passed two parameters: adjacent node and link object itself.
* @param oriented if true graph treated as oriented.
*/
forEachLinkedNode: forEachLinkedNode,
/**
* Enumerates all links in the graph
*
* @param {Function(link)} callback Function to be called on all links in the graph.
* The function is passed one parameter: graph's link object.
*
* Link object contains at least the following fields:
* fromId - node id where link starts;
* toId - node id where link ends,
* data - additional data passed to graph.addLink() method.
*/
forEachLink: forEachLink,
/**
* Suspend all notifications about graph changes until
* endUpdate is called.
*/
beginUpdate: enterModification,
/**
* Resumes all notifications about graph changes and fires
* graph 'changed' event in case there are any pending changes.
*/
endUpdate: exitModification,
/**
* Removes all nodes and links from the graph.
*/
clear: clear,
/**
* Detects whether there is a link between two nodes.
* Operation complexity is O(n) where n - number of links of a node.
* NOTE: this function is synonim for getLink()
*
* @returns link if there is one. null otherwise.
*/
hasLink: getLink,
/**
* Gets an edge between two nodes.
* Operation complexity is O(n) where n - number of links of a node.
*
* @param {string} fromId link start identifier
* @param {string} toId link end identifier
*
* @returns link if there is one. null otherwise.
*/
getLink: getLink
};
// this will add `on()` and `fire()` methods.
eventify(graphPart);
monitorSubscribers();
return graphPart;
function monitorSubscribers() {
var realOn = graphPart.on;
// replace real `on` with our temporary on, which will trigger change
// modification monitoring:
graphPart.on = on;
function on() {
// now it's time to start tracking stuff:
graphPart.beginUpdate = enterModification = enterModificationReal;
graphPart.endUpdate = exitModification = exitModificationReal;
recordLinkChange = recordLinkChangeReal;
recordNodeChange = recordNodeChangeReal;
// this will replace current `on` method with real pub/sub from `eventify`.
graphPart.on = realOn;
// delegate to real `on` handler:
return realOn.apply(graphPart, arguments);
}
}
function recordLinkChangeReal(link, changeType) {
changes.push({
link: link,
changeType: changeType
});
}
function recordNodeChangeReal(node, changeType) {
changes.push({
node: node,
changeType: changeType
});
}
function addNode(nodeId, data) {
if (nodeId === undefined) {
throw new Error('Invalid node identifier');
}
enterModification();
var node = getNode(nodeId);
if (!node) {
// TODO: Should I check for 👉 here?
node = new Node(nodeId);
nodesCount++;
recordNodeChange(node, 'add');
} else {
recordNodeChange(node, 'update');
}
node.data = data;
nodes[nodeId] = node;
exitModification();
return node;
}
function getNode(nodeId) {
return nodes[nodeId];
}
function removeNode(nodeId) {
var node = getNode(nodeId);
if (!node) {
return false;
}
enterModification();
while (node.links.length) {
var link = node.links[0];
removeLink(link);
}
delete nodes[nodeId];
nodesCount--;
recordNodeChange(node, 'remove');
exitModification();
return true;
}
function addLink(fromId, toId, data) {
enterModification();
var fromNode = getNode(fromId) || addNode(fromId);
var toNode = getNode(toId) || addNode(toId);
var link = createLink(fromId, toId, data);
links.push(link);
// TODO: this is not cool. On large graphs potentially would consume more memory.
fromNode.links.push(link);
if (fromId !== toId) {
// make sure we are not duplicating links for self-loops
toNode.links.push(link);
}
recordLinkChange(link, 'add');
exitModification();
return link;
}
function createSingleLink(fromId, toId, data) {
var linkId = fromId.toString() + toId.toString();
return new Link(fromId, toId, data, linkId);
}
function createUniqueLink(fromId, toId, data) {
var linkId = fromId.toString() + '👉 ' + toId.toString();
var isMultiEdge = multiEdges.hasOwnProperty(linkId);
if (isMultiEdge || getLink(fromId, toId)) {
if (!isMultiEdge) {
multiEdges[linkId] = 0;
}
linkId += '@' + (++multiEdges[linkId]);
}
return new Link(fromId, toId, data, linkId);
}
function getLinks(nodeId) {
var node = getNode(nodeId);
return node ? node.links : null;
}
function removeLink(link) {
if (!link) {
return false;
}
var idx = indexOfElementInArray(link, links);
if (idx < 0) {
return false;
}
enterModification();
links.splice(idx, 1);
var fromNode = getNode(link.fromId);
var toNode = getNode(link.toId);
if (fromNode) {
idx = indexOfElementInArray(link, fromNode.links);
if (idx >= 0) {
fromNode.links.splice(idx, 1);
}
}
if (toNode) {
idx = indexOfElementInArray(link, toNode.links);
if (idx >= 0) {
toNode.links.splice(idx, 1);
}
}
recordLinkChange(link, 'remove');
exitModification();
return true;
}
function getLink(fromNodeId, toNodeId) {
// TODO: Use sorted links to speed this up
var node = getNode(fromNodeId),
i;
if (!node) {
return null;
}
for (i = 0; i < node.links.length; ++i) {
var link = node.links[i];
if (link.fromId === fromNodeId && link.toId === toNodeId) {
return link;
}
}
return null; // no link.
}
function clear() {
enterModification();
forEachNode(function(node) {
removeNode(node.id);
});
exitModification();
}
function forEachLink(callback) {
var i, length;
if (typeof callback === 'function') {
for (i = 0, length = links.length; i < length; ++i) {
callback(links[i]);
}
}
}
function forEachLinkedNode(nodeId, callback, oriented) {
var node = getNode(nodeId);
if (node && node.links && typeof callback === 'function') {
if (oriented) {
return forEachOrientedLink(node.links, nodeId, callback);
} else {
return forEachNonOrientedLink(node.links, nodeId, callback);
}
}
}
function forEachNonOrientedLink(links, nodeId, callback) {
var quitFast;
for (var i = 0; i < links.length; ++i) {
var link = links[i];
var linkedNodeId = link.fromId === nodeId ? link.toId : link.fromId;
quitFast = callback(nodes[linkedNodeId], link);
if (quitFast) {
return true; // Client does not need more iterations. Break now.
}
}
}
function forEachOrientedLink(links, nodeId, callback) {
var quitFast;
for (var i = 0; i < links.length; ++i) {
var link = links[i];
if (link.fromId === nodeId) {
quitFast = callback(nodes[link.toId], link);
if (quitFast) {
return true; // Client does not need more iterations. Break now.
}
}
}
}
// we will not fire anything until users of this library explicitly call `on()`
// method.
function noop() {}
// Enter, Exit modification allows bulk graph updates without firing events.
function enterModificationReal() {
suspendEvents += 1;
}
function exitModificationReal() {
suspendEvents -= 1;
if (suspendEvents === 0 && changes.length > 0) {
graphPart.fire('changed', changes);
changes.length = 0;
}
}
function createNodeIterator() {
// Object.keys iterator is 1.3x faster than `for in` loop.
// See `https://github.com/anvaka/ngraph.graph/tree/bench-for-in-vs-obj-keys`
// branch for perf test
return Object.keys ? objectKeysIterator : forInIterator;
}
function objectKeysIterator(callback) {
if (typeof callback !== 'function') {
return;
}
var keys = Object.keys(nodes);
for (var i = 0; i < keys.length; ++i) {
if (callback(nodes[keys[i]])) {
return true; // client doesn't want to proceed. Return.
}
}
}
function forInIterator(callback) {
if (typeof callback !== 'function') {
return;
}
var node;
for (node in nodes) {
if (callback(nodes[node])) {
return true; // client doesn't want to proceed. Return.
}
}
}
}
// need this for old browsers. Should this be a separate module?
function indexOfElementInArray(element, array) {
if (array.indexOf) {
return array.indexOf(element);
}
var len = array.length,
i;
for (i = 0; i < len; i += 1) {
if (array[i] === element) {
return i;
}
}
return -1;
}
/**
* Internal structure to represent node;
*/
function Node(id) {
this.id = id;
this.links = [];
this.data = null;
}
/**
* Internal structure to represent links;
*/
function Link(fromId, toId, data, id) {
this.fromId = fromId;
this.toId = toId;
this.data = data;
this.id = id;
}
},{"ngraph.events":6}],24:[function(require,module,exports){
module.exports = merge;
/**
* Augments `target` with properties in `options`. Does not override
* target's properties if they are defined and matches expected type in
* options
*
* @returns {Object} merged object
*/
function merge(target, options) {
var key;
if (!target) { target = {}; }
if (options) {
for (key in options) {
if (options.hasOwnProperty(key)) {
var targetHasIt = target.hasOwnProperty(key),
optionsValueType = typeof options[key],
shouldReplace = !targetHasIt || (typeof target[key] !== optionsValueType);
if (shouldReplace) {
target[key] = options[key];
} else if (optionsValueType === 'object') {
// go deep, don't care about loops here, we are simple API!:
target[key] = merge(target[key], options[key]);
}
}
}
}
return target;
}
},{}],25:[function(require,module,exports){
module.exports = {
random: random,
randomIterator: randomIterator
};
/**
* Creates seeded PRNG with two methods:
* next() and nextDouble()
*/
function random(inputSeed) {
var seed = typeof inputSeed === 'number' ? inputSeed : (+ new Date());
var randomFunc = function() {
// Robert Jenkins' 32 bit integer hash function.
seed = ((seed + 0x7ed55d16) + (seed << 12)) & 0xffffffff;
seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
seed = ((seed + 0x165667b1) + (seed << 5)) & 0xffffffff;
seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff;
seed = ((seed + 0xfd7046c5) + (seed << 3)) & 0xffffffff;
seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
return (seed & 0xfffffff) / 0x10000000;
};
return {
/**
* Generates random integer number in the range from 0 (inclusive) to maxValue (exclusive)
*
* @param maxValue Number REQUIRED. Ommitting this number will result in NaN values from PRNG.
*/
next : function (maxValue) {
return Math.floor(randomFunc() * maxValue);
},
/**
* Generates random double number in the range from 0 (inclusive) to 1 (exclusive)
* This function is the same as Math.random() (except that it could be seeded)
*/
nextDouble : function () {
return randomFunc();
}
};
}
/*
* Creates iterator over array, which returns items of array in random order
* Time complexity is guaranteed to be O(n);
*/
function randomIterator(array, customRandom) {
var localRandom = customRandom || random();
if (typeof localRandom.next !== 'function') {
throw new Error('customRandom does not match expected API: next() function is missing');
}
return {
forEach : function (callback) {
var i, j, t;
for (i = array.length - 1; i > 0; --i) {
j = localRandom.next(i + 1); // i inclusive
t = array[j];
array[j] = array[i];
array[i] = t;
callback(t);
}
if (array.length) {
callback(array[0]);
}
},
/**
* Shuffles array randomly, in place.
*/
shuffle : function () {
var i, j, t;
for (i = array.length - 1; i > 0; --i) {
j = localRandom.next(i + 1); // i inclusive
t = array[j];
array[j] = array[i];
array[i] = t;
}
return array;
}
};
}
},{}],26:[function(require,module,exports){
module.exports = save;
function save(graph, customNodeTransform, customLinkTransform) {
// Object contains `nodes` and `links` arrays.
var result = {
nodes: [],
links: []
};
var nodeTransform = customNodeTransform || defaultTransformForNode;
var linkTransform = customLinkTransform || defaultTransformForLink;
graph.forEachNode(saveNode);
graph.forEachLink(saveLink);
return JSON.stringify(result);
function saveNode(node) {
// Each node of the graph is processed to take only required fields
// `id` and `data`
result.nodes.push(nodeTransform(node));
}
function saveLink(link) {
// Each link of the graph is also processed to take `fromId`, `toId` and
// `data`
result.links.push(linkTransform(link));
}
function defaultTransformForNode(node) {
var result = {
id: node.id
};
// We don't want to store undefined fields when it's not necessary:
if (node.data !== undefined) {
result.data = node.data;
}
return result;
}
function defaultTransformForLink(link) {
var result = {
fromId: link.fromId,
toId: link.toId,
};
if (link.data !== undefined) {
result.data = link.data;
}
return result;
}
}
},{}],27:[function(require,module,exports){
module.exports = svg;
svg.compile = require('./lib/compile');
var compileTemplate = svg.compileTemplate = require('./lib/compile_template');
var domEvents = require('add-event-listener');
var svgns = "http://www.w3.org/2000/svg";
var xlinkns = "http://www.w3.org/1999/xlink";
function svg(element, attrBag) {
var svgElement = augment(element);
if (attrBag === undefined) {
return svgElement;
}
var attributes = Object.keys(attrBag);
for (var i = 0; i < attributes.length; ++i) {
var attributeName = attributes[i];
var value = attrBag[attributeName];
if (attributeName === 'link') {
svgElement.link(value);
} else {
svgElement.attr(attributeName, value);
}
}
return svgElement;
}
function augment(element) {
var svgElement = element;
if (typeof element === "string") {
svgElement = window.document.createElementNS(svgns, element);
} else if (element.simplesvg) {
return element;
}
var compiledTempalte;
svgElement.simplesvg = true; // this is not good, since we are monkey patching svg
svgElement.attr = attr;
svgElement.append = append;
svgElement.link = link;
svgElement.text = text;
// add easy eventing
svgElement.on = on;
svgElement.off = off;
// data binding:
svgElement.dataSource = dataSource;
return svgElement;
function dataSource(model) {
if (!compiledTempalte) compiledTempalte = compileTemplate(svgElement);
compiledTempalte.link(model);
return svgElement;
}
function on(name, cb, useCapture) {
domEvents.addEventListener(svgElement, name, cb, useCapture);
return svgElement;
}
function off(name, cb, useCapture) {
domEvents.removeEventListener(svgElement, name, cb, useCapture);
return svgElement;
}
function append(content) {
var child = svg(content);
svgElement.appendChild(child);
return child;
}
function attr(name, value) {
if (arguments.length === 2) {
if (value !== null) {
svgElement.setAttributeNS(null, name, value);
} else {
svgElement.removeAttributeNS(null, name);
}
return svgElement;
}
return svgElement.getAttributeNS(null, name);
}
function link(target) {
if (arguments.length) {
svgElement.setAttributeNS(xlinkns, "xlink:href", target);
return svgElement;
}
return svgElement.getAttributeNS(xlinkns, "xlink:href");
}
function text(textContent) {
if (textContent !== undefined) {
svgElement.textContent = textContent;
return svgElement;
}
return svgElement.textContent;
}
}
},{"./lib/compile":28,"./lib/compile_template":29,"add-event-listener":31}],28:[function(require,module,exports){
var parser = require('./domparser.js');
var svg = require('../');
module.exports = compile;
function compile(svgText) {
try {
svgText = addNamespaces(svgText);
return svg(parser.parseFromString(svgText, "text/xml").documentElement);
} catch (e) {
throw e;
}
}
function addNamespaces(text) {
if (!text) return;
var namespaces = 'xmlns:svg="http://www.w3.org/2000/svg" xmlns="http://www.w3.org/2000/svg"';
var match = text.match(/^<\w+/);
if (match) {
var tagLength = match[0].length;
return text.substr(0, tagLength) + ' ' + namespaces + ' ' + text.substr(tagLength);
} else {
throw new Error('Cannot parse input text: invalid xml?');
}
}
},{"../":27,"./domparser.js":30}],29:[function(require,module,exports){
module.exports = template;
var BINDING_EXPR = /{{(.+?)}}/;
function template(domNode) {
var allBindings = Object.create(null);
extractAllBindings(domNode, allBindings);
return {
link: function(model) {
Object.keys(allBindings).forEach(function(key) {
var setter = allBindings[key];
setter.forEach(changeModel);
});
function changeModel(setter) {
setter(model);
}
}
};
}
function extractAllBindings(domNode, allBindings) {
var nodeType = domNode.nodeType;
var typeSupported = (nodeType === 1) || (nodeType === 3);
if (!typeSupported) return;
var i;
if (domNode.hasChildNodes()) {
var domChildren = domNode.childNodes;
for (i = 0; i < domChildren.length; ++i) {
extractAllBindings(domChildren[i], allBindings);
}
}
if (nodeType === 3) { // text:
bindTextContent(domNode, allBindings);
}
if (!domNode.attributes) return; // this might be a text. Need to figure out what to do in that case
var attrs = domNode.attributes;
for (i = 0; i < attrs.length; ++i) {
bindDomAttribute(attrs[i], domNode, allBindings);
}
}
function bindDomAttribute(domAttribute, element, allBindings) {
var value = domAttribute.value;
if (!value) return; // unary attribute?
var modelNameMatch = value.match(BINDING_EXPR);
if (!modelNameMatch) return; // does not look like a binding
var attrName = domAttribute.localName;
var modelPropertyName = modelNameMatch[1];
var isSimpleValue = modelPropertyName.indexOf('.') < 0;
if (!isSimpleValue) throw new Error('simplesvg currently does not support nested bindings');
var propertyBindings = allBindings[modelPropertyName];
if (!propertyBindings) {
propertyBindings = allBindings[modelPropertyName] = [attributeSetter];
} else {
propertyBindings.push(attributeSetter);
}
function attributeSetter(model) {
element.setAttributeNS(null, attrName, model[modelPropertyName]);
}
}
function bindTextContent(element, allBindings) {
// todo reduce duplication
var value = element.nodeValue;
if (!value) return; // unary attribute?
var modelNameMatch = value.match(BINDING_EXPR);
if (!modelNameMatch) return; // does not look like a binding
var modelPropertyName = modelNameMatch[1];
var isSimpleValue = modelPropertyName.indexOf('.') < 0;
var propertyBindings = allBindings[modelPropertyName];
if (!propertyBindings) {
propertyBindings = allBindings[modelPropertyName] = [textSetter];
} else {
propertyBindings.push(textSetter);
}
function textSetter(model) {
element.nodeValue = model[modelPropertyName];
}
}
},{}],30:[function(require,module,exports){
module.exports = createDomparser();
function createDomparser() {
if (typeof DOMParser === 'undefined') {
return {
parseFromString: fail
};
}
return new DOMParser();
}
function fail() {
throw new Error('DOMParser is not supported by this platform. Please open issue here https://github.com/anvaka/simplesvg');
}
},{}],31:[function(require,module,exports){
addEventListener.removeEventListener = removeEventListener
addEventListener.addEventListener = addEventListener
module.exports = addEventListener
var Events = null
function addEventListener(el, eventName, listener, useCapture) {
Events = Events || (
document.addEventListener ?
{add: stdAttach, rm: stdDetach} :
{add: oldIEAttach, rm: oldIEDetach}
)
return Events.add(el, eventName, listener, useCapture)
}
function removeEventListener(el, eventName, listener, useCapture) {
Events = Events || (
document.addEventListener ?
{add: stdAttach, rm: stdDetach} :
{add: oldIEAttach, rm: oldIEDetach}
)
return Events.rm(el, eventName, listener, useCapture)
}
function stdAttach(el, eventName, listener, useCapture) {
el.addEventListener(eventName, listener, useCapture)
}
function stdDetach(el, eventName, listener, useCapture) {
el.removeEventListener(eventName, listener, useCapture)
}
function oldIEAttach(el, eventName, listener, useCapture) {
if(useCapture) {
throw new Error('cannot useCapture in oldIE')
}
el.attachEvent('on' + eventName, listener)
}
function oldIEDetach(el, eventName, listener, useCapture) {
el.detachEvent('on' + eventName, listener)
}
},{}],32:[function(require,module,exports){
var centrality = require('ngraph.centrality');
module.exports = centralityWrapper;
function centralityWrapper() {
// TODO: This should not be a function
return {
betweennessCentrality: betweennessCentrality,
degreeCentrality: degreeCentrality
};
}
function betweennessCentrality(g) {
var betweenness = centrality.betweenness(g);
return toVivaGraphCentralityFormat(betweenness);
}
function degreeCentrality(g, kind) {
var degree = centrality.degree(g, kind);
return toVivaGraphCentralityFormat(degree);
}
function toVivaGraphCentralityFormat(centrality) {
return Object.keys(centrality).sort(byValue).map(toKeyValue);
function byValue(x, y) {
return centrality[y] - centrality[x];
}
function toKeyValue(key) {
return {
key: key,
value: centrality[key]
};
}
}
},{"ngraph.centrality":3}],33:[function(require,module,exports){
/**
* @fileOverview Contains collection of primitive operations under graph.
*
* @author Andrei Kashcha (aka anvaka) / https://github.com/anvaka
*/
module.exports = operations;
function operations() {
return {
/**
* Gets graph density, which is a ratio of actual number of edges to maximum
* number of edges. I.e. graph density 1 means all nodes are connected with each other with an edge.
* Density 0 - graph has no edges. Runtime: O(1)
*
* @param graph represents oriented graph structure.
* @param directed (optional boolean) represents if the graph should be treated as a directed graph.
*
* @returns density of the graph if graph has nodes. NaN otherwise. Returns density for undirected graph by default but returns density for directed graph if a boolean 'true' is passed along with the graph.
*/
density : function (graph,directed) {
var nodes = graph.getNodesCount();
if (nodes === 0) {
return NaN;
}
if(directed){
return graph.getLinksCount() / (nodes * (nodes - 1));
} else {
return 2 * graph.getLinksCount() / (nodes * (nodes - 1));
}
}
};
};
},{}],34:[function(require,module,exports){
/**
* @author Andrei Kashcha (aka anvaka) / https://github.com/anvaka
*/
module.exports = domInputManager;
var dragndrop = require('./dragndrop.js');
function domInputManager(graph, graphics) {
var nodeEvents = {};
return {
/**
* Called by renderer to listen to drag-n-drop events from node. E.g. for SVG
* graphics we may listen to DOM events, whereas for WebGL the graphics
* should provide custom eventing mechanism.
*
* @param node - to be monitored.
* @param handlers - object with set of three callbacks:
* onStart: function(),
* onDrag: function(e, offset),
* onStop: function()
*/
bindDragNDrop: bindDragNDrop
};
function bindDragNDrop(node, handlers) {
var events;
if (handlers) {
var nodeUI = graphics.getNodeUI(node.id);
events = dragndrop(nodeUI);
if (typeof handlers.onStart === 'function') {
events.onStart(handlers.onStart);
}
if (typeof handlers.onDrag === 'function') {
events.onDrag(handlers.onDrag);
}
if (typeof handlers.onStop === 'function') {
events.onStop(handlers.onStop);
}
nodeEvents[node.id] = events;
} else if ((events = nodeEvents[node.id])) {
events.release();
delete nodeEvents[node.id];
}
}
}
},{"./dragndrop.js":35}],35:[function(require,module,exports){
/**
* @author Andrei Kashcha (aka anvaka) / https://github.com/anvaka
*/
module.exports = dragndrop;
var documentEvents = require('../Utils/documentEvents.js');
var browserInfo = require('../Utils/browserInfo.js');
var findElementPosition = require('../Utils/findElementPosition.js');
// TODO: Move to input namespace
// TODO: Methods should be extracted into the prototype. This class
// does not need to consume so much memory for every tracked element
function dragndrop(element) {
var start,
drag,
end,
scroll,
prevSelectStart,
prevDragStart,
startX = 0,
startY = 0,
dragObject,
touchInProgress = false,
pinchZoomLength = 0,
getMousePos = function (e) {
var posx = 0,
posy = 0;
e = e || window.event;
if (e.pageX || e.pageY) {
posx = e.pageX;
posy = e.pageY;
} else if (e.clientX || e.clientY) {
posx = e.clientX + window.document.body.scrollLeft + window.document.documentElement.scrollLeft;
posy = e.clientY + window.document.body.scrollTop + window.document.documentElement.scrollTop;
}
return [posx, posy];
},
move = function (e, clientX, clientY) {
if (drag) {
drag(e, {x : clientX - startX, y : clientY - startY });
}
startX = clientX;
startY = clientY;
},
stopPropagation = function (e) {
if (e.stopPropagation) { e.stopPropagation(); } else { e.cancelBubble = true; }
},
preventDefault = function (e) {
if (e.preventDefault) { e.preventDefault(); }
},
handleDisabledEvent = function (e) {
stopPropagation(e);
return false;
},
handleMouseMove = function (e) {
e = e || window.event;
move(e, e.clientX, e.clientY);
},
handleMouseDown = function (e) {
e = e || window.event;
if (touchInProgress) {
// modern browsers will fire mousedown for touch events too
// we do not want this, since touch is handled separately.
stopPropagation(e);
return false;
}
// for IE, left click == 1
// for Firefox, left click == 0
var isLeftButton = ((e.button === 1 && window.event !== null) || e.button === 0);
if (isLeftButton) {
startX = e.clientX;
startY = e.clientY;
// TODO: bump zIndex?
dragObject = e.target || e.srcElement;
if (start) { start(e, {x: startX, y : startY}); }
documentEvents.on('mousemove', handleMouseMove);
documentEvents.on('mouseup', handleMouseUp);
stopPropagation(e);
// TODO: What if event already there? Not bullet proof:
prevSelectStart = window.document.onselectstart;
prevDragStart = window.document.ondragstart;
window.document.onselectstart = handleDisabledEvent;
dragObject.ondragstart = handleDisabledEvent;
// prevent text selection (except IE)
return false;
}
},
handleMouseUp = function (e) {
e = e || window.event;
documentEvents.off('mousemove', handleMouseMove);
documentEvents.off('mouseup', handleMouseUp);
window.document.onselectstart = prevSelectStart;
dragObject.ondragstart = prevDragStart;
dragObject = null;
if (end) { end(e); }
},
handleMouseWheel = function (e) {
if (typeof scroll !== 'function') {
return;
}
e = e || window.event;
if (e.preventDefault) {
e.preventDefault();
}
e.returnValue = false;
var delta,
mousePos = getMousePos(e),
elementOffset = findElementPosition(element),
relMousePos = {
x: mousePos[0] - elementOffset[0],
y: mousePos[1] - elementOffset[1]
};
if (e.wheelDelta) {
delta = e.wheelDelta / 360; // Chrome/Safari
} else {
delta = e.detail / -9; // Mozilla
}
scroll(e, delta, relMousePos);
},
updateScrollEvents = function (scrollCallback) {
if (!scroll && scrollCallback) {
// client is interested in scrolling. Start listening to events:
if (browserInfo.browser === 'webkit') {
element.addEventListener('mousewheel', handleMouseWheel, false); // Chrome/Safari
} else {
element.addEventListener('DOMMouseScroll', handleMouseWheel, false); // Others
}
} else if (scroll && !scrollCallback) {
if (browserInfo.browser === 'webkit') {
element.removeEventListener('mousewheel', handleMouseWheel, false); // Chrome/Safari
} else {
element.removeEventListener('DOMMouseScroll', handleMouseWheel, false); // Others
}
}
scroll = scrollCallback;
},
getPinchZoomLength = function(finger1, finger2) {
return (finger1.clientX - finger2.clientX) * (finger1.clientX - finger2.clientX) +
(finger1.clientY - finger2.clientY) * (finger1.clientY - finger2.clientY);
},
handleTouchMove = function (e) {
if (e.touches.length === 1) {
stopPropagation(e);
var touch = e.touches[0];
move(e, touch.clientX, touch.clientY);
} else if (e.touches.length === 2) {
// it's a zoom:
var currentPinchLength = getPinchZoomLength(e.touches[0], e.touches[1]);
var delta = 0;
if (currentPinchLength < pinchZoomLength) {
delta = -1;
} else if (currentPinchLength > pinchZoomLength) {
delta = 1;
}
scroll(e, delta, {x: e.touches[0].clientX, y: e.touches[0].clientY});
pinchZoomLength = currentPinchLength;
stopPropagation(e);
preventDefault(e);
}
},
handleTouchEnd = function (e) {
touchInProgress = false;
documentEvents.off('touchmove', handleTouchMove);
documentEvents.off('touchend', handleTouchEnd);
documentEvents.off('touchcancel', handleTouchEnd);
dragObject = null;
if (end) { end(e); }
},
handleSignleFingerTouch = function (e, touch) {
stopPropagation(e);
preventDefault(e);
startX = touch.clientX;
startY = touch.clientY;
dragObject = e.target || e.srcElement;
if (start) { start(e, {x: startX, y : startY}); }
// TODO: can I enter into the state when touch is in progress
// but it's still a single finger touch?
if (!touchInProgress) {
touchInProgress = true;
documentEvents.on('touchmove', handleTouchMove);
documentEvents.on('touchend', handleTouchEnd);
documentEvents.on('touchcancel', handleTouchEnd);
}
},
handleTouchStart = function (e) {
if (e.touches.length === 1) {
return handleSignleFingerTouch(e, e.touches[0]);
} else if (e.touches.length === 2) {
// handleTouchMove() will care about pinch zoom.
stopPropagation(e);
preventDefault(e);
pinchZoomLength = getPinchZoomLength(e.touches[0], e.touches[1]);
}
// don't care about the rest.
};
element.addEventListener('mousedown', handleMouseDown);
element.addEventListener('touchstart', handleTouchStart);
return {
onStart : function (callback) {
start = callback;
return this;
},
onDrag : function (callback) {
drag = callback;
return this;
},
onStop : function (callback) {
end = callback;
return this;
},
/**
* Occurs when mouse wheel event happens. callback = function(e, scrollDelta, scrollPoint);
*/
onScroll : function (callback) {
updateScrollEvents(callback);
return this;
},
release : function () {
// TODO: could be unsafe. We might wanna release dragObject, etc.
element.removeEventListener('mousedown', handleMouseDown);
element.removeEventListener('touchstart', handleTouchStart);
documentEvents.off('mousemove', handleMouseMove);
documentEvents.off('mouseup', handleMouseUp);
documentEvents.off('touchmove', handleTouchMove);
documentEvents.off('touchend', handleTouchEnd);
documentEvents.off('touchcancel', handleTouchEnd);
updateScrollEvents(null);
}
};
}
},{"../Utils/browserInfo.js":39,"../Utils/documentEvents.js":40,"../Utils/findElementPosition.js":41}],36:[function(require,module,exports){
/**
* @author Andrei Kashcha (aka anvaka) / https://github.com/anvaka
*/
module.exports = webglInputManager;
var createInputEvents = require('../WebGL/webglInputEvents.js');
function webglInputManager(graph, graphics) {
var inputEvents = createInputEvents(graphics),
draggedNode = null,
internalHandlers = {},
pos = {x : 0, y : 0};
inputEvents.mouseDown(function (node, e) {
draggedNode = node;
pos.x = e.clientX;
pos.y = e.clientY;
inputEvents.mouseCapture(draggedNode);
var handlers = internalHandlers[node.id];
if (handlers && handlers.onStart) {
handlers.onStart(e, pos);
}
return true;
}).mouseUp(function (node) {
inputEvents.releaseMouseCapture(draggedNode);
draggedNode = null;
var handlers = internalHandlers[node.id];
if (handlers && handlers.onStop) {
handlers.onStop();
}
return true;
}).mouseMove(function (node, e) {
if (draggedNode) {
var handlers = internalHandlers[draggedNode.id];
if (handlers && handlers.onDrag) {
handlers.onDrag(e, {x : e.clientX - pos.x, y : e.clientY - pos.y });
}
pos.x = e.clientX;
pos.y = e.clientY;
return true;
}
});
return {
/**
* Called by renderer to listen to drag-n-drop events from node. E.g. for SVG
* graphics we may listen to DOM events, whereas for WebGL we graphics
* should provide custom eventing mechanism.
*
* @param node - to be monitored.
* @param handlers - object with set of three callbacks:
* onStart: function(),
* onDrag: function(e, offset),
* onStop: function()
*/
bindDragNDrop : function (node, handlers) {
internalHandlers[node.id] = handlers;
if (!handlers) {
delete internalHandlers[node.id];
}
}
};
}
},{"../WebGL/webglInputEvents.js":57}],37:[function(require,module,exports){
module.exports = constant;
var merge = require('ngraph.merge');
var random = require('ngraph.random').random;
var Rect = require('../Utils/rect.js');
/**
* Does not really perform any layouting algorithm but is compliant
* with renderer interface. Allowing clients to provide specific positioning
* callback and get static layout of the graph
*
* @param {Viva.Graph.graph} graph to layout
* @param {Object} userSettings
*/
function constant(graph, userSettings) {
userSettings = merge(userSettings, {
maxX : 1024,
maxY : 1024,
seed : 'Deterministic randomness made me do this'
});
// This class simply follows API, it does not use some of the arguments:
/*jshint unused: false */
var rand = random(userSettings.seed),
graphRect = new Rect(Number.MAX_VALUE, Number.MAX_VALUE, Number.MIN_VALUE, Number.MIN_VALUE),
layoutLinks = {},
placeNodeCallback = function (node) {
return {
x: rand.next(userSettings.maxX),
y: rand.next(userSettings.maxY)
};
},
updateGraphRect = function (position, graphRect) {
if (position.x < graphRect.x1) { graphRect.x1 = position.x; }
if (position.x > graphRect.x2) { graphRect.x2 = position.x; }
if (position.y < graphRect.y1) { graphRect.y1 = position.y; }
if (position.y > graphRect.y2) { graphRect.y2 = position.y; }
},
layoutNodes = typeof Object.create === 'function' ? Object.create(null) : {},
ensureNodeInitialized = function (node) {
layoutNodes[node.id] = placeNodeCallback(node);
updateGraphRect(layoutNodes[node.id], graphRect);
},
updateNodePositions = function () {
if (graph.getNodesCount() === 0) { return; }
graphRect.x1 = Number.MAX_VALUE;
graphRect.y1 = Number.MAX_VALUE;
graphRect.x2 = Number.MIN_VALUE;
graphRect.y2 = Number.MIN_VALUE;
graph.forEachNode(ensureNodeInitialized);
},
ensureLinkInitialized = function (link) {
layoutLinks[link.id] = link;
},
onGraphChanged = function(changes) {
for (var i = 0; i < changes.length; ++i) {
var change = changes[i];
if (change.node) {
if (change.changeType === 'add') {
ensureNodeInitialized(change.node);
} else {
delete layoutNodes[change.node.id];
}
} if (change.link) {
if (change.changeType === 'add') {
ensureLinkInitialized(change.link);
} else {
delete layoutLinks[change.link.id];
}
}
}
};
graph.forEachNode(ensureNodeInitialized);
graph.forEachLink(ensureLinkInitialized);
graph.on('changed', onGraphChanged);
return {
/**
* Attempts to layout graph within given number of iterations.
*
* @param {integer} [iterationsCount] number of algorithm's iterations.
* The constant layout ignores this parameter.
*/
run : function (iterationsCount) {
this.step();
},
/**
* One step of layout algorithm.
*/
step : function () {
updateNodePositions();
return true; // no need to continue.
},
/**
* Returns rectangle structure {x1, y1, x2, y2}, which represents
* current space occupied by graph.
*/
getGraphRect : function () {
return graphRect;
},
/**
* Request to release all resources
*/
dispose : function () {
graph.off('change', onGraphChanged);
},
/*
* Checks whether given node is pinned; all nodes in this layout are pinned.
*/
isNodePinned: function (node) {
return true;
},
/*
* Requests layout algorithm to pin/unpin node to its current position
* Pinned nodes should not be affected by layout algorithm and always
* remain at their position
*/
pinNode: function (node, isPinned) {
// noop
},
/*
* Gets position of a node by its id. If node was not seen by this
* layout algorithm undefined value is returned;
*/
getNodePosition: getNodePosition,
/**
* Returns {from, to} position of a link.
*/
getLinkPosition: function (linkId) {
var link = layoutLinks[linkId];
return {
from : getNodePosition(link.fromId),
to : getNodePosition(link.toId)
};
},
/**
* Sets position of a node to a given coordinates
*/
setNodePosition: function (nodeId, x, y) {
var pos = layoutNodes[nodeId];
if (pos) {
pos.x = x;
pos.y = y;
}
},
// Layout specific methods:
/**
* Based on argument either update default node placement callback or
* attempts to place given node using current placement callback.
* Setting new node callback triggers position update for all nodes.
*
* @param {Object} newPlaceNodeCallbackOrNode - if it is a function then
* default node placement callback is replaced with new one. Node placement
* callback has a form of function (node) {}, and is expected to return an
* object with x and y properties set to numbers.
*
* Otherwise if it's not a function the argument is treated as graph node
* and current node placement callback will be used to place it.
*/
placeNode : function (newPlaceNodeCallbackOrNode) {
if (typeof newPlaceNodeCallbackOrNode === 'function') {
placeNodeCallback = newPlaceNodeCallbackOrNode;
updateNodePositions();
return this;
}
// it is not a request to update placeNodeCallback, trying to place
// a node using current callback:
return placeNodeCallback(newPlaceNodeCallbackOrNode);
}
};
function getNodePosition(nodeId) {
return layoutNodes[nodeId];
}
}
},{"../Utils/rect.js":45,"ngraph.merge":24,"ngraph.random":25}],38:[function(require,module,exports){
/**
* This module provides compatibility layer with 0.6.x library. It will be
* removed in the next version
*/
var events = require('ngraph.events');
module.exports = backwardCompatibleEvents;
function backwardCompatibleEvents(g) {
console.log("This method is deprecated. Please use Viva.events() instead");
if (!g) {
return g;
}
var eventsDefined = (g.on !== undefined) ||
(g.off !== undefined) ||
(g.fire !== undefined);
if (eventsDefined) {
// events already defined, ignore
return {
extend: function() {
return g;
},
on: g.on,
stop: g.off
};
}
return {
extend: extend,
on: g.on,
stop: g.off
};
function extend() {
var backwardCompatible = events(g);
backwardCompatible.addEventListener = backwardCompatible.on;
return backwardCompatible;
}
}
},{"ngraph.events":6}],39:[function(require,module,exports){
module.exports = browserInfo();
function browserInfo() {
if (typeof window === "undefined" || !window.hasOwnProperty("navigator")) {
return {
browser : "",
version : "0"
};
}
var ua = window.navigator.userAgent.toLowerCase(),
// Useragent RegExp
rwebkit = /(webkit)[ \/]([\w.]+)/,
ropera = /(opera)(?:.*version)?[ \/]([\w.]+)/,
rmsie = /(msie) ([\w.]+)/,
rmozilla = /(mozilla)(?:.*? rv:([\w.]+))?/,
match = rwebkit.exec(ua) ||
ropera.exec(ua) ||
rmsie.exec(ua) ||
(ua.indexOf("compatible") < 0 && rmozilla.exec(ua)) ||
[];
return {
browser: match[1] || "",
version: match[2] || "0"
};
}
},{}],40:[function(require,module,exports){
var nullEvents = require('./nullEvents.js');
module.exports = createDocumentEvents();
function createDocumentEvents() {
if (typeof document === undefined) {
return nullEvents;
}
return {
on: on,
off: off
};
}
function on(eventName, handler) {
document.addEventListener(eventName, handler);
}
function off(eventName, handler) {
document.removeEventListener(eventName, handler);
}
},{"./nullEvents.js":44}],41:[function(require,module,exports){
/**
* Finds the absolute position of an element on a page
*/
module.exports = findElementPosition;
function findElementPosition(obj) {
var curleft = 0,
curtop = 0;
if (obj.offsetParent) {
do {
curleft += obj.offsetLeft;
curtop += obj.offsetTop;
} while ((obj = obj.offsetParent) !== null);
}
return [curleft, curtop];
}
},{}],42:[function(require,module,exports){
module.exports = getDimension;
function getDimension(container) {
if (!container) {
throw {
message : 'Cannot get dimensions of undefined container'
};
}
// TODO: Potential cross browser bug.
var width = container.clientWidth;
var height = container.clientHeight;
return {
left : 0,
top : 0,
width : width,
height : height
};
}
},{}],43:[function(require,module,exports){
var intersect = require('gintersect');
module.exports = intersectRect;
function intersectRect(left, top, right, bottom, x1, y1, x2, y2) {
return intersect(left, top, left, bottom, x1, y1, x2, y2) ||
intersect(left, bottom, right, bottom, x1, y1, x2, y2) ||
intersect(right, bottom, right, top, x1, y1, x2, y2) ||
intersect(right, top, left, top, x1, y1, x2, y2);
}
},{"gintersect":2}],44:[function(require,module,exports){
module.exports = createNullEvents();
function createNullEvents() {
return {
on: noop,
off: noop,
stop: noop
};
}
function noop() { }
},{}],45:[function(require,module,exports){
module.exports = Rect;
/**
* Very generic rectangle.
*/
function Rect (x1, y1, x2, y2) {
this.x1 = x1 || 0;
this.y1 = y1 || 0;
this.x2 = x2 || 0;
this.y2 = y2 || 0;
}
},{}],46:[function(require,module,exports){
(function (global){
/**
* @author Andrei Kashcha (aka anvaka) / http://anvaka.blogspot.com
*/
module.exports = createTimer();
function createTimer() {
var lastTime = 0,
vendors = ['ms', 'moz', 'webkit', 'o'],
i,
scope;
if (typeof window !== 'undefined') {
scope = window;
} else if (typeof global !== 'undefined') {
scope = global;
} else {
scope = {
setTimeout: noop,
clearTimeout: noop
};
}
for (i = 0; i < vendors.length && !scope.requestAnimationFrame; ++i) {
var vendorPrefix = vendors[i];
scope.requestAnimationFrame = scope[vendorPrefix + 'RequestAnimationFrame'];
scope.cancelAnimationFrame =
scope[vendorPrefix + 'CancelAnimationFrame'] || scope[vendorPrefix + 'CancelRequestAnimationFrame'];
}
if (!scope.requestAnimationFrame) {
scope.requestAnimationFrame = rafPolyfill;
}
if (!scope.cancelAnimationFrame) {
scope.cancelAnimationFrame = cancelRafPolyfill;
}
return timer;
/**
* Timer that fires callback with given interval (in ms) until
* callback returns true;
*/
function timer(callback) {
var intervalId;
startTimer(); // start it right away.
return {
/**
* Stops execution of the callback
*/
stop: stopTimer,
restart: restart
};
function startTimer() {
intervalId = scope.requestAnimationFrame(startTimer);
if (!callback()) {
stopTimer();
}
}
function stopTimer() {
scope.cancelAnimationFrame(intervalId);
intervalId = 0;
}
function restart() {
if (!intervalId) {
startTimer();
}
}
}
function rafPolyfill(callback) {
var currTime = new Date().getTime();
var timeToCall = Math.max(0, 16 - (currTime - lastTime));
var id = scope.setTimeout(function() {
callback(currTime + timeToCall);
}, timeToCall);
lastTime = currTime + timeToCall;
return id;
}
function cancelRafPolyfill(id) {
scope.clearTimeout(id);
}
}
function noop() {}
}).call(this,typeof global !== "undefined" ? global : typeof self !== "undefined" ? self : typeof window !== "undefined" ? window : {})
},{}],47:[function(require,module,exports){
var nullEvents = require('./nullEvents.js');
module.exports = createDocumentEvents();
function createDocumentEvents() {
if (typeof window === 'undefined') {
return nullEvents;
}
return {
on: on,
off: off
};
}
function on(eventName, handler) {
window.addEventListener(eventName, handler);
}
function off(eventName, handler) {
window.removeEventListener(eventName, handler);
}
},{"./nullEvents.js":44}],48:[function(require,module,exports){
/**
* @fileOverview Defines a graph renderer that uses CSS based drawings.
*
* @author Andrei Kashcha (aka anvaka) / https://github.com/anvaka
*/
module.exports = renderer;
var eventify = require('ngraph.events');
var forceDirected = require('ngraph.forcelayout');
var svgGraphics = require('./svgGraphics.js');
var windowEvents = require('../Utils/windowEvents.js');
var domInputManager = require('../Input/domInputManager.js');
var timer = require('../Utils/timer.js');
var getDimension = require('../Utils/getDimensions.js');
var dragndrop = require('../Input/dragndrop.js');
/**
* This is heart of the rendering. Class accepts graph to be rendered and rendering settings.
* It monitors graph changes and depicts them accordingly.
*
* @param graph - Viva.Graph.graph() object to be rendered.
* @param settings - rendering settings, composed from the following parts (with their defaults shown):
* settings = {
* // Represents a module that is capable of displaying graph nodes and links.
* // all graphics has to correspond to defined interface and can be later easily
* // replaced for specific needs (e.g. adding WebGL should be piece of cake as long
* // as WebGL has implemented required interface). See svgGraphics for example.
* graphics : Viva.Graph.View.svgGraphics(),
*
* // Where the renderer should draw graph. Container size matters, because
* // renderer will attempt center graph to that size. Also graphics modules
* // might depend on it.
* container : document.body,
*
* // Defines whether graph can respond to use input
* interactive: true,
*
* // Layout algorithm to be used. The algorithm is expected to comply with defined
* // interface and is expected to be iterative. Renderer will use it then to calculate
* // grpaph's layout. For examples of the interface refer to Viva.Graph.Layout.forceDirected()
* layout : Viva.Graph.Layout.forceDirected(),
*
* // Directs renderer to display links. Usually rendering links is the slowest part of this
* // library. So if you don't need to display links, consider settings this property to false.
* renderLinks : true,
*
* // Number of layout iterations to run before displaying the graph. The bigger you set this number
* // the closer to ideal position graph will appear first time. But be careful: for large graphs
* // it can freeze the browser.
* prerender : 0
* }
*/
function renderer(graph, settings) {
// TODO: This class is getting hard to understand. Consider refactoring.
// TODO: I have a technical debt here: fix scaling/recentering! Currently it's a total mess.
var FRAME_INTERVAL = 30;
settings = settings || {};
var layout = settings.layout,
graphics = settings.graphics,
container = settings.container,
interactive = settings.interactive !== undefined ? settings.interactive : true,
inputManager,
animationTimer,
rendererInitialized = false,
updateCenterRequired = true,
currentStep = 0,
totalIterationsCount = 0,
isStable = false,
userInteraction = false,
isPaused = false,
transform = {
offsetX: 0,
offsetY: 0,
scale: 1
},
publicEvents = eventify({}),
containerDrag;
return {
/**
* Performs rendering of the graph.
*
* @param iterationsCount if specified renderer will run only given number of iterations
* and then stop. Otherwise graph rendering is performed infinitely.
*
* Note: if rendering stopped by used started dragging nodes or new nodes were added to the
* graph renderer will give run more iterations to reflect changes.
*/
run: function(iterationsCount) {
if (!rendererInitialized) {
prepareSettings();
prerender();
initDom();
updateCenter();
listenToEvents();
rendererInitialized = true;
}
renderIterations(iterationsCount);
return this;
},
reset: function() {
graphics.resetScale();
updateCenter();
transform.scale = 1;
},
pause: function() {
isPaused = true;
animationTimer.stop();
},
resume: function() {
isPaused = false;
animationTimer.restart();
},
rerender: function() {
renderGraph();
return this;
},
zoomOut: function() {
return scale(true);
},
zoomIn: function() {
return scale(false);
},
/**
* Centers renderer at x,y graph's coordinates
*/
moveTo: function(x, y) {
graphics.graphCenterChanged(transform.offsetX - x * transform.scale, transform.offsetY - y * transform.scale);
renderGraph();
},
/**
* Gets current graphics object
*/
getGraphics: function() {
return graphics;
},
/**
* Removes this renderer and deallocates all resources/timers
*/
dispose: function() {
stopListenToEvents(); // I quit!
},
on: function(eventName, callback) {
publicEvents.on(eventName, callback);
return this;
},
off: function(eventName, callback) {
publicEvents.off(eventName, callback);
return this;
}
};
/**
* Checks whether given interaction (node/scroll) is enabled
*/
function isInteractive(interactionName) {
if (typeof interactive === 'string') {
return interactive.indexOf(interactionName) >= 0;
} else if (typeof interactive === 'boolean') {
return interactive;
}
return true; // default setting
}
function prepareSettings() {
container = container || window.document.body;
layout = layout || forceDirected(graph, {
springLength: 80,
springCoeff: 0.0002,
});
graphics = graphics || svgGraphics(graph, {
container: container
});
if (!settings.hasOwnProperty('renderLinks')) {
settings.renderLinks = true;
}
settings.prerender = settings.prerender || 0;
inputManager = (graphics.inputManager || domInputManager)(graph, graphics);
}
function renderGraph() {
graphics.beginRender();
// todo: move this check graphics
if (settings.renderLinks) {
graphics.renderLinks();
}
graphics.renderNodes();
graphics.endRender();
}
function onRenderFrame() {
isStable = layout.step() && !userInteraction;
renderGraph();
return !isStable;
}
function renderIterations(iterationsCount) {
if (animationTimer) {
totalIterationsCount += iterationsCount;
return;
}
if (iterationsCount) {
totalIterationsCount += iterationsCount;
animationTimer = timer(function() {
return onRenderFrame();
}, FRAME_INTERVAL);
} else {
currentStep = 0;
totalIterationsCount = 0;
animationTimer = timer(onRenderFrame, FRAME_INTERVAL);
}
}
function resetStable() {
if (isPaused) {
return;
}
isStable = false;
animationTimer.restart();
}
function prerender() {
// To get good initial positions for the graph
// perform several prerender steps in background.
if (typeof settings.prerender === 'number' && settings.prerender > 0) {
for (var i = 0; i < settings.prerender; i += 1) {
layout.step();
}
}
}
function updateCenter() {
var graphRect = layout.getGraphRect(),
containerSize = getDimension(container);
var cx = (graphRect.x2 + graphRect.x1) / 2;
var cy = (graphRect.y2 + graphRect.y1) / 2;
transform.offsetX = containerSize.width / 2 - (cx * transform.scale - cx);
transform.offsetY = containerSize.height / 2 - (cy * transform.scale - cy);
graphics.graphCenterChanged(transform.offsetX, transform.offsetY);
updateCenterRequired = false;
}
function createNodeUi(node) {
var nodePosition = layout.getNodePosition(node.id);
graphics.addNode(node, nodePosition);
}
function removeNodeUi(node) {
graphics.releaseNode(node);
}
function createLinkUi(link) {
var linkPosition = layout.getLinkPosition(link.id);
graphics.addLink(link, linkPosition);
}
function removeLinkUi(link) {
graphics.releaseLink(link);
}
function listenNodeEvents(node) {
if (!isInteractive('node')) {
return;
}
var wasPinned = false;
// TODO: This may not be memory efficient. Consider reusing handlers object.
inputManager.bindDragNDrop(node, {
onStart: function() {
wasPinned = layout.isNodePinned(node);
layout.pinNode(node, true);
userInteraction = true;
resetStable();
},
onDrag: function(e, offset) {
var oldPos = layout.getNodePosition(node.id);
layout.setNodePosition(node.id,
oldPos.x + offset.x / transform.scale,
oldPos.y + offset.y / transform.scale);
userInteraction = true;
renderGraph();
},
onStop: function() {
layout.pinNode(node, wasPinned);
userInteraction = false;
}
});
}
function releaseNodeEvents(node) {
inputManager.bindDragNDrop(node, null);
}
function initDom() {
graphics.init(container);
graph.forEachNode(createNodeUi);
if (settings.renderLinks) {
graph.forEachLink(createLinkUi);
}
}
function releaseDom() {
graphics.release(container);
}
function processNodeChange(change) {
var node = change.node;
if (change.changeType === 'add') {
createNodeUi(node);
listenNodeEvents(node);
if (updateCenterRequired) {
updateCenter();
}
} else if (change.changeType === 'remove') {
releaseNodeEvents(node);
removeNodeUi(node);
if (graph.getNodesCount() === 0) {
updateCenterRequired = true; // Next time when node is added - center the graph.
}
} else if (change.changeType === 'update') {
releaseNodeEvents(node);
removeNodeUi(node);
createNodeUi(node);
listenNodeEvents(node);
}
}
function processLinkChange(change) {
var link = change.link;
if (change.changeType === 'add') {
if (settings.renderLinks) {
createLinkUi(link);
}
} else if (change.changeType === 'remove') {
if (settings.renderLinks) {
removeLinkUi(link);
}
} else if (change.changeType === 'update') {
throw 'Update type is not implemented. TODO: Implement me!';
}
}
function onGraphChanged(changes) {
var i, change;
for (i = 0; i < changes.length; i += 1) {
change = changes[i];
if (change.node) {
processNodeChange(change);
} else if (change.link) {
processLinkChange(change);
}
}
resetStable();
}
function onWindowResized() {
updateCenter();
onRenderFrame();
}
function releaseContainerDragManager() {
if (containerDrag) {
containerDrag.release();
containerDrag = null;
}
}
function releaseGraphEvents() {
graph.off('changed', onGraphChanged);
}
function scale(out, scrollPoint) {
if (!scrollPoint) {
var containerSize = getDimension(container);
scrollPoint = {
x: containerSize.width / 2,
y: containerSize.height / 2
};
}
var scaleFactor = Math.pow(1 + 0.4, out ? -0.2 : 0.2);
transform.scale = graphics.scale(scaleFactor, scrollPoint);
renderGraph();
publicEvents.fire('scale', transform.scale);
return transform.scale;
}
function listenToEvents() {
windowEvents.on('resize', onWindowResized);
releaseContainerDragManager();
if (isInteractive('drag')) {
containerDrag = dragndrop(container);
containerDrag.onDrag(function(e, offset) {
graphics.translateRel(offset.x, offset.y);
renderGraph();
});
}
if (isInteractive('scroll')) {
if (!containerDrag) {
containerDrag = dragndrop(container);
}
containerDrag.onScroll(function(e, scaleOffset, scrollPoint) {
scale(scaleOffset < 0, scrollPoint);
});
}
graph.forEachNode(listenNodeEvents);
releaseGraphEvents();
graph.on('changed', onGraphChanged);
}
function stopListenToEvents() {
rendererInitialized = false;
releaseGraphEvents();
releaseContainerDragManager();
windowEvents.off('resize', onWindowResized);
publicEvents.off();
animationTimer.stop();
graph.forEachLink(function(link) {
if (settings.renderLinks) {
removeLinkUi(link);
}
});
graph.forEachNode(function(node) {
releaseNodeEvents(node);
removeNodeUi(node);
});
layout.dispose();
releaseDom();
}
}
},{"../Input/domInputManager.js":34,"../Input/dragndrop.js":35,"../Utils/getDimensions.js":42,"../Utils/timer.js":46,"../Utils/windowEvents.js":47,"./svgGraphics.js":49,"ngraph.events":6,"ngraph.forcelayout":7}],49:[function(require,module,exports){
/**
* @fileOverview Defines a graph renderer that uses SVG based drawings.
*
* @author Andrei Kashcha (aka anvaka) / http://anvaka.blogspot.com
*/
module.exports = svgGraphics;
var svg = require('simplesvg');
var eventify = require('ngraph.events');
var domInputManager = require('../Input/domInputManager.js');
/**
* Performs svg-based graph rendering. This module does not perform
* layout, but only visualizes nodes and edges of the graph.
*/
function svgGraphics() {
var svgContainer,
svgRoot,
offsetX = 0,
offsetY = 0,
initCallback,
actualScale = 1,
allNodes = {},
allLinks = {},
/*jshint unused: false */
nodeBuilder = function (node) {
return svg("rect")
.attr("width", 10)
.attr("height", 10)
.attr("fill", "#00a2e8");
},
nodePositionCallback = function (nodeUI, pos) {
// TODO: Remove magic 5. It should be half of the width or height of the node.
nodeUI.attr("x", pos.x - 5)
.attr("y", pos.y - 5);
},
linkBuilder = function (link) {
return svg("line").attr("stroke", "#999");
},
linkPositionCallback = function (linkUI, fromPos, toPos) {
linkUI.attr("x1", fromPos.x)
.attr("y1", fromPos.y)
.attr("x2", toPos.x)
.attr("y2", toPos.y);
},
fireRescaled = function (graphics) {
// TODO: maybe we shall copy changes?
graphics.fire("rescaled");
},
cachedPos = {x : 0, y: 0},
cachedFromPos = {x : 0, y: 0},
cachedToPos = {x : 0, y: 0},
updateTransform = function () {
if (svgContainer) {
var transform = "matrix(" + actualScale + ", 0, 0," + actualScale + "," + offsetX + "," + offsetY + ")";
svgContainer.attr("transform", transform);
}
};
svgRoot = createSvgRoot();
var graphics = {
getNodeUI: function (nodeId) {
return allNodes[nodeId];
},
getLinkUI: function (linkId) {
return allLinks[linkId];
},
/**
* Sets the callback that creates node representation.
*
* @param builderCallback a callback function that accepts graph node
* as a parameter and must return an element representing this node.
*
* @returns If builderCallbackOrNode is a valid callback function, instance of this is returned;
* Otherwise undefined value is returned
*/
node : function (builderCallback) {
if (typeof builderCallback !== "function") {
return; // todo: throw? This is not compatible with old versions
}
nodeBuilder = builderCallback;
return this;
},
/**
* Sets the callback that creates link representation
*
* @param builderCallback a callback function that accepts graph link
* as a parameter and must return an element representing this link.
*
* @returns If builderCallback is a valid callback function, instance of this is returned;
* Otherwise undefined value is returned.
*/
link : function (builderCallback) {
if (typeof builderCallback !== "function") {
return; // todo: throw? This is not compatible with old versions
}
linkBuilder = builderCallback;
return this;
},
/**
* Allows to override default position setter for the node with a new
* function. newPlaceCallback(nodeUI, position, node) is function which
* is used by updateNodePosition().
*/
placeNode : function (newPlaceCallback) {
nodePositionCallback = newPlaceCallback;
return this;
},
placeLink : function (newPlaceLinkCallback) {
linkPositionCallback = newPlaceLinkCallback;
return this;
},
/**
* Called every before renderer starts rendering.
*/
beginRender : function () {},
/**
* Called every time when renderer finishes one step of rendering.
*/
endRender : function () {},
/**
* Sets translate operation that should be applied to all nodes and links.
*/
graphCenterChanged : function (x, y) {
offsetX = x;
offsetY = y;
updateTransform();
},
/**
* Default input manager listens to DOM events to process nodes drag-n-drop
*/
inputManager : domInputManager,
translateRel : function (dx, dy) {
var p = svgRoot.createSVGPoint(),
t = svgContainer.getCTM(),
origin = svgRoot.createSVGPoint().matrixTransform(t.inverse());
p.x = dx;
p.y = dy;
p = p.matrixTransform(t.inverse());
p.x = (p.x - origin.x) * t.a;
p.y = (p.y - origin.y) * t.d;
t.e += p.x;
t.f += p.y;
var transform = "matrix(" + t.a + ", 0, 0," + t.d + "," + t.e + "," + t.f + ")";
svgContainer.attr("transform", transform);
},
scale : function (scaleFactor, scrollPoint) {
var p = svgRoot.createSVGPoint();
p.x = scrollPoint.x;
p.y = scrollPoint.y;
p = p.matrixTransform(svgContainer.getCTM().inverse()); // translate to SVG coordinates
// Compute new scale matrix in current mouse position
var k = svgRoot.createSVGMatrix().translate(p.x, p.y).scale(scaleFactor).translate(-p.x, -p.y),
t = svgContainer.getCTM().multiply(k);
actualScale = t.a;
offsetX = t.e;
offsetY = t.f;
var transform = "matrix(" + t.a + ", 0, 0," + t.d + "," + t.e + "," + t.f + ")";
svgContainer.attr("transform", transform);
fireRescaled(this);
return actualScale;
},
resetScale : function () {
actualScale = 1;
var transform = "matrix(1, 0, 0, 1, 0, 0)";
svgContainer.attr("transform", transform);
fireRescaled(this);
return this;
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider prepare to render.
*/
init : function (container) {
container.appendChild(svgRoot);
updateTransform();
// Notify the world if someone waited for update. TODO: should send an event
if (typeof initCallback === "function") {
initCallback(svgRoot);
}
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider release occupied resources.
*/
release : function (container) {
if (svgRoot && container) {
container.removeChild(svgRoot);
}
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider prepare to render given link of the graph
*
* @param link - model of a link
*/
addLink: function (link, pos) {
var linkUI = linkBuilder(link);
if (!linkUI) { return; }
linkUI.position = pos;
linkUI.link = link;
allLinks[link.id] = linkUI;
if (svgContainer.childElementCount > 0) {
svgContainer.insertBefore(linkUI, svgContainer.firstChild);
} else {
svgContainer.appendChild(linkUI);
}
return linkUI;
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider remove link from rendering surface.
*
* @param linkUI visual representation of the link created by link() execution.
**/
releaseLink : function (link) {
var linkUI = allLinks[link.id];
if (linkUI) {
svgContainer.removeChild(linkUI);
delete allLinks[link.id];
}
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider prepare to render given node of the graph.
*
* @param nodeUI visual representation of the node created by node() execution.
**/
addNode : function (node, pos) {
var nodeUI = nodeBuilder(node);
if (!nodeUI) {
return;
}
nodeUI.position = pos;
nodeUI.node = node;
allNodes[node.id] = nodeUI;
svgContainer.appendChild(nodeUI);
return nodeUI;
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider remove node from rendering surface.
*
* @param node graph's node
**/
releaseNode : function (node) {
var nodeUI = allNodes[node.id];
if (nodeUI) {
svgContainer.removeChild(nodeUI);
delete allNodes[node.id];
}
},
renderNodes : function () {
for (var key in allNodes) {
if (allNodes.hasOwnProperty(key)) {
var nodeUI = allNodes[key];
cachedPos.x = nodeUI.position.x;
cachedPos.y = nodeUI.position.y;
nodePositionCallback(nodeUI, cachedPos, nodeUI.node);
}
}
},
renderLinks : function () {
for (var key in allLinks) {
if (allLinks.hasOwnProperty(key)) {
var linkUI = allLinks[key];
cachedFromPos.x = linkUI.position.from.x;
cachedFromPos.y = linkUI.position.from.y;
cachedToPos.x = linkUI.position.to.x;
cachedToPos.y = linkUI.position.to.y;
linkPositionCallback(linkUI, cachedFromPos, cachedToPos, linkUI.link);
}
}
},
/**
* Returns root element which hosts graphics.
*/
getGraphicsRoot : function (callbackWhenReady) {
// todo: should fire an event, instead of having this context.
if (typeof callbackWhenReady === "function") {
if (svgRoot) {
callbackWhenReady(svgRoot);
} else {
initCallback = callbackWhenReady;
}
}
return svgRoot;
},
/**
* Returns root SVG element.
*
* Note: This is internal method specific to this renderer
*/
getSvgRoot : function () {
return svgRoot;
}
};
// Let graphics fire events before we return it to the caller.
eventify(graphics);
return graphics;
function createSvgRoot() {
var svgRoot = svg("svg");
svgContainer = svg("g")
.attr("buffered-rendering", "dynamic");
svgRoot.appendChild(svgContainer);
return svgRoot;
}
}
},{"../Input/domInputManager.js":34,"ngraph.events":6,"simplesvg":27}],50:[function(require,module,exports){
/**
* @fileOverview Defines a graph renderer that uses WebGL based drawings.
*
* @author Andrei Kashcha (aka anvaka) / https://github.com/anvaka
*/
module.exports = webglGraphics;
var webglInputManager = require('../Input/webglInputManager.js');
var webglLinkProgram = require('../WebGL/webglLinkProgram.js');
var webglNodeProgram = require('../WebGL/webglNodeProgram.js');
var webglSquare = require('../WebGL/webglSquare.js');
var webglLine = require('../WebGL/webglLine.js');
var eventify = require('ngraph.events');
var merge = require('ngraph.merge');
/**
* Performs webgl-based graph rendering. This module does not perform
* layout, but only visualizes nodes and edges of the graph.
*
* @param options - to customize graphics behavior. Currently supported parameter
* enableBlending - true by default, allows to use transparency in node/links colors.
* preserveDrawingBuffer - false by default, tells webgl to preserve drawing buffer.
* See https://www.khronos.org/registry/webgl/specs/1.0/#5.2
*/
function webglGraphics(options) {
options = merge(options, {
enableBlending : true,
preserveDrawingBuffer : false,
clearColor: false,
clearColorValue : {
r : 1,
g : 1,
b : 1,
a : 1
}
});
var container,
graphicsRoot,
gl,
width,
height,
nodesCount = 0,
linksCount = 0,
transform = [
1, 0, 0, 0,
0, 1, 0, 0,
0, 0, 1, 0,
0, 0, 0, 1
],
userPlaceNodeCallback,
userPlaceLinkCallback,
nodes = [],
links = [],
initCallback,
allNodes = {},
allLinks = {},
linkProgram = webglLinkProgram(),
nodeProgram = webglNodeProgram(),
/*jshint unused: false */
nodeUIBuilder = function (node) {
return webglSquare(); // Just make a square, using provided gl context (a nodeProgram);
},
linkUIBuilder = function (link) {
return webglLine(0xb3b3b3ff);
},
/*jshint unused: true */
updateTransformUniform = function () {
linkProgram.updateTransform(transform);
nodeProgram.updateTransform(transform);
},
resetScaleInternal = function () {
transform = [1, 0, 0, 0,
0, 1, 0, 0,
0, 0, 1, 0,
0, 0, 0, 1];
},
updateSize = function () {
if (container && graphicsRoot) {
width = graphicsRoot.width = Math.max(container.offsetWidth, 1);
height = graphicsRoot.height = Math.max(container.offsetHeight, 1);
if (gl) { gl.viewport(0, 0, width, height); }
if (linkProgram) { linkProgram.updateSize(width / 2, height / 2); }
if (nodeProgram) { nodeProgram.updateSize(width / 2, height / 2); }
}
},
fireRescaled = function (graphics) {
graphics.fire("rescaled");
};
graphicsRoot = window.document.createElement("canvas");
var graphics = {
getLinkUI: function (linkId) {
return allLinks[linkId];
},
getNodeUI: function (nodeId) {
return allNodes[nodeId];
},
/**
* Sets the callback that creates node representation.
*
* @param builderCallback a callback function that accepts graph node
* as a parameter and must return an element representing this node.
*
* @returns If builderCallbackOrNode is a valid callback function, instance of this is returned;
* Otherwise undefined value is returned
*/
node : function (builderCallback) {
if (typeof builderCallback !== "function") {
return; // todo: throw? This is not compatible with old versions
}
nodeUIBuilder = builderCallback;
return this;
},
/**
* Sets the callback that creates link representation
*
* @param builderCallback a callback function that accepts graph link
* as a parameter and must return an element representing this link.
*
* @returns If builderCallback is a valid callback function, instance of this is returned;
* Otherwise undefined value is returned.
*/
link : function (builderCallback) {
if (typeof builderCallback !== "function") {
return; // todo: throw? This is not compatible with old versions
}
linkUIBuilder = builderCallback;
return this;
},
/**
* Allows to override default position setter for the node with a new
* function. newPlaceCallback(nodeUI, position) is function which
* is used by updateNodePosition().
*/
placeNode : function (newPlaceCallback) {
userPlaceNodeCallback = newPlaceCallback;
return this;
},
placeLink : function (newPlaceLinkCallback) {
userPlaceLinkCallback = newPlaceLinkCallback;
return this;
},
/**
* Custom input manager listens to mouse events to process nodes drag-n-drop inside WebGL canvas
*/
inputManager : webglInputManager,
/**
* Called every time before renderer starts rendering.
*/
beginRender : function () {
// this function could be replaced by this.init,
// based on user options.
},
/**
* Called every time when renderer finishes one step of rendering.
*/
endRender : function () {
if (linksCount > 0) {
linkProgram.render();
}
if (nodesCount > 0) {
nodeProgram.render();
}
},
bringLinkToFront : function (linkUI) {
var frontLinkId = linkProgram.getFrontLinkId(),
srcLinkId,
temp;
linkProgram.bringToFront(linkUI);
if (frontLinkId > linkUI.id) {
srcLinkId = linkUI.id;
temp = links[frontLinkId];
links[frontLinkId] = links[srcLinkId];
links[frontLinkId].id = frontLinkId;
links[srcLinkId] = temp;
links[srcLinkId].id = srcLinkId;
}
},
/**
* Sets translate operation that should be applied to all nodes and links.
*/
graphCenterChanged : function (x, y) {
transform[12] = (2 * x / width) - 1;
transform[13] = 1 - (2 * y / height);
updateTransformUniform();
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider prepare to render given link of the graph
*
* @param link - model of a link
*/
addLink: function (link, boundPosition) {
var uiid = linksCount++,
ui = linkUIBuilder(link);
ui.id = uiid;
ui.pos = boundPosition;
linkProgram.createLink(ui);
links[uiid] = ui;
allLinks[link.id] = ui;
return ui;
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider prepare to render given node of the graph.
*
* @param nodeUI visual representation of the node created by node() execution.
**/
addNode : function (node, boundPosition) {
var uiid = nodesCount++,
ui = nodeUIBuilder(node);
ui.id = uiid;
ui.position = boundPosition;
ui.node = node;
nodeProgram.createNode(ui);
nodes[uiid] = ui;
allNodes[node.id] = ui;
return ui;
},
translateRel : function (dx, dy) {
transform[12] += (2 * transform[0] * dx / width) / transform[0];
transform[13] -= (2 * transform[5] * dy / height) / transform[5];
updateTransformUniform();
},
scale : function (scaleFactor, scrollPoint) {
// Transform scroll point to clip-space coordinates:
var cx = 2 * scrollPoint.x / width - 1,
cy = 1 - (2 * scrollPoint.y) / height;
cx -= transform[12];
cy -= transform[13];
transform[12] += cx * (1 - scaleFactor);
transform[13] += cy * (1 - scaleFactor);
transform[0] *= scaleFactor;
transform[5] *= scaleFactor;
updateTransformUniform();
fireRescaled(this);
return transform[0];
},
resetScale : function () {
resetScaleInternal();
if (gl) {
updateSize();
// TODO: what is this?
// gl.useProgram(linksProgram);
// gl.uniform2f(linksProgram.screenSize, width, height);
updateTransformUniform();
}
return this;
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider prepare to render.
*/
init : function (c) {
var contextParameters = {};
if (options.preserveDrawingBuffer) {
contextParameters.preserveDrawingBuffer = true;
}
container = c;
updateSize();
resetScaleInternal();
container.appendChild(graphicsRoot);
gl = graphicsRoot.getContext("experimental-webgl", contextParameters);
if (!gl) {
var msg = "Could not initialize WebGL. Seems like the browser doesn't support it.";
window.alert(msg);
throw msg;
}
if (options.enableBlending) {
gl.blendFunc(gl.SRC_ALPHA, gl.ONE_MINUS_SRC_ALPHA);
gl.enable(gl.BLEND);
}
if (options.clearColor) {
var color = options.clearColorValue;
gl.clearColor(color.r, color.g, color.b, color.a);
// TODO: not the best way, really. Should come up with something better
// what if we need more updates inside beginRender, like depth buffer?
this.beginRender = function () {
gl.clear(gl.COLOR_BUFFER_BIT);
};
}
linkProgram.load(gl);
linkProgram.updateSize(width / 2, height / 2);
nodeProgram.load(gl);
nodeProgram.updateSize(width / 2, height / 2);
updateTransformUniform();
// Notify the world if someone waited for update. TODO: should send an event
if (typeof initCallback === "function") {
initCallback(graphicsRoot);
}
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider release occupied resources.
*/
release : function (container) {
if (graphicsRoot && container) {
container.removeChild(graphicsRoot);
// TODO: anything else?
}
},
/**
* Checks whether webgl is supported by this browser.
*/
isSupported : function () {
var c = window.document.createElement("canvas"),
gl = c && c.getContext && c.getContext("experimental-webgl");
return gl;
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider remove link from rendering surface.
*
* @param linkUI visual representation of the link created by link() execution.
**/
releaseLink : function (link) {
if (linksCount > 0) { linksCount -= 1; }
var linkUI = allLinks[link.id];
delete allLinks[link.id];
linkProgram.removeLink(linkUI);
var linkIdToRemove = linkUI.id;
if (linkIdToRemove < linksCount) {
if (linksCount === 0 || linksCount === linkIdToRemove) {
return; // no more links or removed link is the last one.
}
var lastLinkUI = links[linksCount];
links[linkIdToRemove] = lastLinkUI;
lastLinkUI.id = linkIdToRemove;
}
},
/**
* Called by Viva.Graph.View.renderer to let concrete graphic output
* provider remove node from rendering surface.
*
* @param nodeUI visual representation of the node created by node() execution.
**/
releaseNode : function (node) {
if (nodesCount > 0) { nodesCount -= 1; }
var nodeUI = allNodes[node.id];
delete allNodes[node.id];
nodeProgram.removeNode(nodeUI);
var nodeIdToRemove = nodeUI.id;
if (nodeIdToRemove < nodesCount) {
if (nodesCount === 0 || nodesCount === nodeIdToRemove) {
return; // no more nodes or removed node is the last in the list.
}
var lastNodeUI = nodes[nodesCount];
nodes[nodeIdToRemove] = lastNodeUI;
lastNodeUI.id = nodeIdToRemove;
// Since concrete shaders may cache properties in the UI element
// we are letting them to make this swap (e.g. image node shader
// uses this approach to update node's offset in the atlas)
nodeProgram.replaceProperties(nodeUI, lastNodeUI);
}
},
renderNodes: function () {
var pos = {x : 0, y : 0};
// WebGL coordinate system is different. Would be better
// to have this transform in the shader code, but it would
// require every shader to be updated..
for (var i = 0; i < nodesCount; ++i) {
var ui = nodes[i];
pos.x = ui.position.x;
pos.y = ui.position.y;
if (userPlaceNodeCallback) {
userPlaceNodeCallback(ui, pos);
}
nodeProgram.position(ui, pos);
}
},
renderLinks: function () {
if (this.omitLinksRendering) { return; }
var toPos = {x : 0, y : 0};
var fromPos = {x : 0, y : 0};
for (var i = 0; i < linksCount; ++i) {
var ui = links[i];
var pos = ui.pos.from;
fromPos.x = pos.x;
fromPos.y = -pos.y;
pos = ui.pos.to;
toPos.x = pos.x;
toPos.y = -pos.y;
if (userPlaceLinkCallback) {
userPlaceLinkCallback(ui, fromPos, toPos);
}
linkProgram.position(ui, fromPos, toPos);
}
},
/**
* Returns root element which hosts graphics.
*/
getGraphicsRoot : function (callbackWhenReady) {
// todo: should fire an event, instead of having this context.
if (typeof callbackWhenReady === "function") {
if (graphicsRoot) {
callbackWhenReady(graphicsRoot);
} else {
initCallback = callbackWhenReady;
}
}
return graphicsRoot;
},
/**
* Updates default shader which renders nodes
*
* @param newProgram to use for nodes.
*/
setNodeProgram : function (newProgram) {
if (!gl && newProgram) {
// Nothing created yet. Just set shader to the new one
// and let initialization logic take care about the rest.
nodeProgram = newProgram;
} else if (newProgram) {
throw "Not implemented. Cannot swap shader on the fly... Yet.";
// TODO: unload old shader and reinit.
}
},
/**
* Updates default shader which renders links
*
* @param newProgram to use for links.
*/
setLinkProgram : function (newProgram) {
if (!gl && newProgram) {
// Nothing created yet. Just set shader to the new one
// and let initialization logic take care about the rest.
linkProgram = newProgram;
} else if (newProgram) {
throw "Not implemented. Cannot swap shader on the fly... Yet.";
// TODO: unload old shader and reinit.
}
},
/**
* Transforms client coordinates into layout coordinates. Client coordinates
* are DOM coordinates relative to the rendering container. Layout
* coordinates are those assigned by by layout algorithm to each node.
*
* @param {Object} p - a point object with `x` and `y` attributes.
* This method mutates p.
*/
transformClientToGraphCoordinates: function (p) {
// TODO: could be a problem when container has margins?
// normalize
p.x = ((2 * p.x) / width) - 1;
p.y = 1 - ((2 * p.y) / height);
// apply transform
p.x = (p.x - transform[12]) / transform[0];
p.y = (p.y - transform[13]) / transform[5];
// transform to graph coordinates
p.x = p.x * (width / 2);
p.y = p.y * (-height / 2);
return p;
},
/**
* Transforms WebGL coordinates into client coordinates. Reverse of
* `transformClientToGraphCoordinates()`
*
* @param {Object} p - a point object with `x` and `y` attributes, which
* represents a layout coordinate. This method mutates p.
*/
transformGraphToClientCoordinates: function (p) {
// TODO: could be a problem when container has margins?
// transform from graph coordinates
p.x = p.x / (width / 2);
p.y = p.y / (-height / 2);
// apply transform
p.x = (p.x * transform[0]) + transform[12];
p.y = (p.y * transform[5]) + transform[13];
// denormalize
p.x = ((p.x + 1) * width) / 2;
p.y = ((1 - p.y) * height) / 2;
return p;
},
getNodeAtClientPos: function (clientPos, preciseCheck) {
if (typeof preciseCheck !== "function") {
// we don't know anything about your node structure here :(
// potentially this could be delegated to node program, but for
// right now, we are giving up if you don't pass boundary check
// callback. It answers to a question is nodeUI covers (x, y)
return null;
}
// first transform to graph coordinates:
this.transformClientToGraphCoordinates(clientPos);
// now using precise check iterate over each node and find one within box:
// TODO: This is poor O(N) performance.
for (var i = 0; i < nodesCount; ++i) {
if (preciseCheck(nodes[i], clientPos.x, clientPos.y)) {
return nodes[i].node;
}
}
return null;
}
};
// Let graphics fire events before we return it to the caller.
eventify(graphics);
return graphics;
}
},{"../Input/webglInputManager.js":36,"../WebGL/webglLine.js":58,"../WebGL/webglLinkProgram.js":59,"../WebGL/webglNodeProgram.js":60,"../WebGL/webglSquare.js":61,"ngraph.events":6,"ngraph.merge":24}],51:[function(require,module,exports){
module.exports = parseColor;
function parseColor(color) {
var parsedColor = 0x009ee8ff;
if (typeof color === 'string' && color) {
if (color.length === 4) { // #rgb
color = color.replace(/([^#])/g, '$1$1'); // duplicate each letter except first #.
}
if (color.length === 9) { // #rrggbbaa
parsedColor = parseInt(color.substr(1), 16);
} else if (color.length === 7) { // or #rrggbb.
parsedColor = (parseInt(color.substr(1), 16) << 8) | 0xff;
} else {
throw 'Color expected in hex format with preceding "#". E.g. #00ff00. Got value: ' + color;
}
} else if (typeof color === 'number') {
parsedColor = color;
}
return parsedColor;
}
},{}],52:[function(require,module,exports){
module.exports = Texture;
/**
* Single texture in the webglAtlas.
*/
function Texture(size) {
this.canvas = window.document.createElement("canvas");
this.ctx = this.canvas.getContext("2d");
this.isDirty = false;
this.canvas.width = this.canvas.height = size;
}
},{}],53:[function(require,module,exports){
/**
* @fileOverview Utility functions for webgl rendering.
*
* @author Andrei Kashcha (aka anvaka) / http://anvaka.blogspot.com
*/
module.exports = webgl;
function webgl(gl) {
return {
createProgram: createProgram,
extendArray: extendArray,
copyArrayPart: copyArrayPart,
swapArrayPart: swapArrayPart,
getLocations: getLocations,
context: gl
};
function createShader(shaderText, type) {
var shader = gl.createShader(type);
gl.shaderSource(shader, shaderText);
gl.compileShader(shader);
if (!gl.getShaderParameter(shader, gl.COMPILE_STATUS)) {
var msg = gl.getShaderInfoLog(shader);
window.alert(msg);
throw msg;
}
return shader;
}
function createProgram(vertexShaderSrc, fragmentShaderSrc) {
var program = gl.createProgram();
var vs = createShader(vertexShaderSrc, gl.VERTEX_SHADER);
var fs = createShader(fragmentShaderSrc, gl.FRAGMENT_SHADER);
gl.attachShader(program, vs);
gl.attachShader(program, fs);
gl.linkProgram(program);
if (!gl.getProgramParameter(program, gl.LINK_STATUS)) {
var msg = gl.getShaderInfoLog(program);
window.alert(msg);
throw msg;
}
return program;
}
function extendArray(buffer, itemsInBuffer, elementsPerItem) {
if ((itemsInBuffer + 1) * elementsPerItem > buffer.length) {
// Every time we run out of space create new array twice bigger.
// TODO: it seems buffer size is limited. Consider using multiple arrays for huge graphs
var extendedArray = new Float32Array(buffer.length * elementsPerItem * 2);
extendedArray.set(buffer);
return extendedArray;
}
return buffer;
}
function getLocations(program, uniformOrAttributeNames) {
var foundLocations = {};
for (var i = 0; i < uniformOrAttributeNames.length; ++i) {
var name = uniformOrAttributeNames[i];
var location = -1;
if (name[0] === 'a' && name[1] === '_') {
location = gl.getAttribLocation(program, name);
if (location === -1) {
throw new Error("Program doesn't have required attribute: " + name);
}
foundLocations[name.slice(2)] = location;
} else if (name[0] === 'u' && name[1] === '_') {
location = gl.getUniformLocation(program, name);
if (location === null) {
throw new Error("Program doesn't have required uniform: " + name);
}
foundLocations[name.slice(2)] = location;
} else {
throw new Error("Couldn't figure out your intent. All uniforms should start with 'u_' prefix, and attributes with 'a_'");
}
}
return foundLocations;
}
}
function copyArrayPart(array, to, from, elementsCount) {
for (var i = 0; i < elementsCount; ++i) {
array[to + i] = array[from + i];
}
}
function swapArrayPart(array, from, to, elementsCount) {
for (var i = 0; i < elementsCount; ++i) {
var tmp = array[from + i];
array[from + i] = array[to + i];
array[to + i] = tmp;
}
}
},{}],54:[function(require,module,exports){
var Texture = require('./texture.js');
module.exports = webglAtlas;
/**
* My naive implementation of textures atlas. It allows clients to load
* multiple images into atlas and get canvas representing all of them.
*
* @param tilesPerTexture - indicates how many images can be loaded to one
* texture of the atlas. If number of loaded images exceeds this
* parameter a new canvas will be created.
*/
function webglAtlas(tilesPerTexture) {
var tilesPerRow = Math.sqrt(tilesPerTexture || 1024) << 0,
tileSize = tilesPerRow,
lastLoadedIdx = 1,
loadedImages = {},
dirtyTimeoutId,
skipedDirty = 0,
textures = [],
trackedUrls = [];
if (!isPowerOf2(tilesPerTexture)) {
throw "Tiles per texture should be power of two.";
}
// this is the return object
var api = {
/**
* indicates whether atlas has changed texture in it. If true then
* some of the textures has isDirty flag set as well.
*/
isDirty: false,
/**
* Clears any signs of atlas changes.
*/
clearDirty: clearDirty,
/**
* Removes given url from collection of tiles in the atlas.
*/
remove: remove,
/**
* Gets all textures in the atlas.
*/
getTextures: getTextures,
/**
* Gets coordinates of the given image in the atlas. Coordinates is an object:
* {offset : int } - where offset is an absolute position of the image in the
* atlas.
*
* Absolute means it can be larger than tilesPerTexture parameter, and in that
* case clients should get next texture in getTextures() collection.
*/
getCoordinates: getCoordinates,
/**
* Asynchronously Loads the image to the atlas. Cross-domain security
* limitation applies.
*/
load: load
};
return api;
function clearDirty() {
var i;
api.isDirty = false;
for (i = 0; i < textures.length; ++i) {
textures[i].isDirty = false;
}
}
function remove(imgUrl) {
var coordinates = loadedImages[imgUrl];
if (!coordinates) {
return false;
}
delete loadedImages[imgUrl];
lastLoadedIdx -= 1;
if (lastLoadedIdx === coordinates.offset) {
return true; // Ignore if it's last image in the whole set.
}
var tileToRemove = getTileCoordinates(coordinates.offset),
lastTileInSet = getTileCoordinates(lastLoadedIdx);
copy(lastTileInSet, tileToRemove);
var replacedOffset = loadedImages[trackedUrls[lastLoadedIdx]];
replacedOffset.offset = coordinates.offset;
trackedUrls[coordinates.offset] = trackedUrls[lastLoadedIdx];
markDirty();
return true;
}
function getTextures() {
return textures; // I trust you...
}
function getCoordinates(imgUrl) {
return loadedImages[imgUrl];
}
function load(imgUrl, callback) {
if (loadedImages.hasOwnProperty(imgUrl)) {
callback(loadedImages[imgUrl]);
} else {
var img = new window.Image(),
imgId = lastLoadedIdx;
lastLoadedIdx += 1;
img.crossOrigin = "anonymous";
img.onload = function() {
markDirty();
drawAt(imgId, img, callback);
};
img.src = imgUrl;
}
}
function createTexture() {
var texture = new Texture(tilesPerRow * tileSize);
textures.push(texture);
}
function drawAt(tileNumber, img, callback) {
var tilePosition = getTileCoordinates(tileNumber),
coordinates = {
offset: tileNumber
};
if (tilePosition.textureNumber >= textures.length) {
createTexture();
}
var currentTexture = textures[tilePosition.textureNumber];
currentTexture.ctx.drawImage(img, tilePosition.col * tileSize, tilePosition.row * tileSize, tileSize, tileSize);
trackedUrls[tileNumber] = img.src;
loadedImages[img.src] = coordinates;
currentTexture.isDirty = true;
callback(coordinates);
}
function getTileCoordinates(absolutePosition) {
var textureNumber = (absolutePosition / tilesPerTexture) << 0,
localTileNumber = (absolutePosition % tilesPerTexture),
row = (localTileNumber / tilesPerRow) << 0,
col = (localTileNumber % tilesPerRow);
return {
textureNumber: textureNumber,
row: row,
col: col
};
}
function markDirtyNow() {
api.isDirty = true;
skipedDirty = 0;
dirtyTimeoutId = null;
}
function markDirty() {
// delay this call, since it results in texture reload
if (dirtyTimeoutId) {
window.clearTimeout(dirtyTimeoutId);
skipedDirty += 1;
dirtyTimeoutId = null;
}
if (skipedDirty > 10) {
markDirtyNow();
} else {
dirtyTimeoutId = window.setTimeout(markDirtyNow, 400);
}
}
function copy(from, to) {
var fromCanvas = textures[from.textureNumber].canvas,
toCtx = textures[to.textureNumber].ctx,
x = to.col * tileSize,
y = to.row * tileSize;
toCtx.drawImage(fromCanvas, from.col * tileSize, from.row * tileSize, tileSize, tileSize, x, y, tileSize, tileSize);
textures[from.textureNumber].isDirty = true;
textures[to.textureNumber].isDirty = true;
}
}
function isPowerOf2(n) {
return (n & (n - 1)) === 0;
}
},{"./texture.js":52}],55:[function(require,module,exports){
module.exports = webglImage;
/**
* Represents a model for image.
*/
function webglImage(size, src) {
return {
/**
* Gets texture index where current image is placed.
*/
_texture : 0,
/**
* Gets offset in the texture where current image is placed.
*/
_offset : 0,
/**
* Gets size of the square with the image.
*/
size : typeof size === 'number' ? size : 32,
/**
* Source of the image. If image is coming not from your domain
* certain origin restrictions applies.
* See http://www.khronos.org/registry/webgl/specs/latest/#4.2 for more details.
*/
src : src
};
}
},{}],56:[function(require,module,exports){
/**
* @fileOverview Defines an image nodes for webglGraphics class.
* Shape of nodes is square.
*
* @author Andrei Kashcha (aka anvaka) / http://anvaka.blogspot.com
*/
var WebglAtlas = require('./webglAtlas.js');
var glUtils = require('./webgl.js');
module.exports = webglImageNodeProgram;
/**
* Defines simple UI for nodes in webgl renderer. Each node is rendered as an image.
*/
function webglImageNodeProgram() {
// WebGL is gian state machine, we store some properties of the state here:
var ATTRIBUTES_PER_PRIMITIVE = 18;
var nodesFS = createNodeFragmentShader();
var nodesVS = createNodeVertexShader();
var tilesPerTexture = 1024; // TODO: Get based on max texture size
var atlas;
var program;
var gl;
var buffer;
var utils;
var locations;
var nodesCount = 0;
var nodes = new Float32Array(64);
var width;
var height;
var transform;
var sizeDirty;
return {
load: load,
/**
* Updates position of current node in the buffer of nodes.
*
* @param idx - index of current node.
* @param pos - new position of the node.
*/
position: position,
createNode: createNode,
removeNode: removeNode,
replaceProperties: replaceProperties,
updateTransform: updateTransform,
updateSize: updateSize,
render: render
};
function refreshTexture(texture, idx) {
if (texture.nativeObject) {
gl.deleteTexture(texture.nativeObject);
}
var nativeObject = gl.createTexture();
gl.activeTexture(gl["TEXTURE" + idx]);
gl.bindTexture(gl.TEXTURE_2D, nativeObject);
gl.texImage2D(gl.TEXTURE_2D, 0, gl.RGBA, gl.RGBA, gl.UNSIGNED_BYTE, texture.canvas);
gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MAG_FILTER, gl.LINEAR);
gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MIN_FILTER, gl.LINEAR_MIPMAP_NEAREST);
gl.generateMipmap(gl.TEXTURE_2D);
gl.uniform1i(locations["sampler" + idx], idx);
texture.nativeObject = nativeObject;
}
function ensureAtlasTextureUpdated() {
if (atlas.isDirty) {
var textures = atlas.getTextures(),
i;
for (i = 0; i < textures.length; ++i) {
if (textures[i].isDirty || !textures[i].nativeObject) {
refreshTexture(textures[i], i);
}
}
atlas.clearDirty();
}
}
function load(glContext) {
gl = glContext;
utils = glUtils(glContext);
atlas = new WebglAtlas(tilesPerTexture);
program = utils.createProgram(nodesVS, nodesFS);
gl.useProgram(program);
locations = utils.getLocations(program, ["a_vertexPos", "a_customAttributes", "u_screenSize", "u_transform", "u_sampler0", "u_sampler1", "u_sampler2", "u_sampler3", "u_tilesPerTexture"]);
gl.uniform1f(locations.tilesPerTexture, tilesPerTexture);
gl.enableVertexAttribArray(locations.vertexPos);
gl.enableVertexAttribArray(locations.customAttributes);
buffer = gl.createBuffer();
}
function position(nodeUI, pos) {
var idx = nodeUI.id * ATTRIBUTES_PER_PRIMITIVE;
nodes[idx] = pos.x - nodeUI.size;
nodes[idx + 1] = pos.y - nodeUI.size;
nodes[idx + 2] = nodeUI._offset * 4;
nodes[idx + 3] = pos.x + nodeUI.size;
nodes[idx + 4] = pos.y - nodeUI.size;
nodes[idx + 5] = nodeUI._offset * 4 + 1;
nodes[idx + 6] = pos.x - nodeUI.size;
nodes[idx + 7] = pos.y + nodeUI.size;
nodes[idx + 8] = nodeUI._offset * 4 + 2;
nodes[idx + 9] = pos.x - nodeUI.size;
nodes[idx + 10] = pos.y + nodeUI.size;
nodes[idx + 11] = nodeUI._offset * 4 + 2;
nodes[idx + 12] = pos.x + nodeUI.size;
nodes[idx + 13] = pos.y - nodeUI.size;
nodes[idx + 14] = nodeUI._offset * 4 + 1;
nodes[idx + 15] = pos.x + nodeUI.size;
nodes[idx + 16] = pos.y + nodeUI.size;
nodes[idx + 17] = nodeUI._offset * 4 + 3;
}
function createNode(ui) {
nodes = utils.extendArray(nodes, nodesCount, ATTRIBUTES_PER_PRIMITIVE);
nodesCount += 1;
var coordinates = atlas.getCoordinates(ui.src);
if (coordinates) {
ui._offset = coordinates.offset;
} else {
ui._offset = 0;
// Image is not yet loaded into the atlas. Reload it:
atlas.load(ui.src, function(coordinates) {
ui._offset = coordinates.offset;
});
}
}
function removeNode(nodeUI) {
if (nodesCount > 0) {
nodesCount -= 1;
}
if (nodeUI.id < nodesCount && nodesCount > 0) {
if (nodeUI.src) {
atlas.remove(nodeUI.src);
}
utils.copyArrayPart(nodes, nodeUI.id * ATTRIBUTES_PER_PRIMITIVE, nodesCount * ATTRIBUTES_PER_PRIMITIVE, ATTRIBUTES_PER_PRIMITIVE);
}
}
function replaceProperties(replacedNode, newNode) {
newNode._offset = replacedNode._offset;
}
function updateTransform(newTransform) {
sizeDirty = true;
transform = newTransform;
}
function updateSize(w, h) {
width = w;
height = h;
sizeDirty = true;
}
function render() {
gl.useProgram(program);
gl.bindBuffer(gl.ARRAY_BUFFER, buffer);
gl.bufferData(gl.ARRAY_BUFFER, nodes, gl.DYNAMIC_DRAW);
if (sizeDirty) {
sizeDirty = false;
gl.uniformMatrix4fv(locations.transform, false, transform);
gl.uniform2f(locations.screenSize, width, height);
}
gl.vertexAttribPointer(locations.vertexPos, 2, gl.FLOAT, false, 3 * Float32Array.BYTES_PER_ELEMENT, 0);
gl.vertexAttribPointer(locations.customAttributes, 1, gl.FLOAT, false, 3 * Float32Array.BYTES_PER_ELEMENT, 2 * 4);
ensureAtlasTextureUpdated();
gl.drawArrays(gl.TRIANGLES, 0, nodesCount * 6);
}
}
// TODO: Use glslify for shaders
function createNodeFragmentShader() {
return [
"precision mediump float;",
"varying vec4 color;",
"varying vec3 vTextureCoord;",
"uniform sampler2D u_sampler0;",
"uniform sampler2D u_sampler1;",
"uniform sampler2D u_sampler2;",
"uniform sampler2D u_sampler3;",
"void main(void) {",
" if (vTextureCoord.z == 0.) {",
" gl_FragColor = texture2D(u_sampler0, vTextureCoord.xy);",
" } else if (vTextureCoord.z == 1.) {",
" gl_FragColor = texture2D(u_sampler1, vTextureCoord.xy);",
" } else if (vTextureCoord.z == 2.) {",
" gl_FragColor = texture2D(u_sampler2, vTextureCoord.xy);",
" } else if (vTextureCoord.z == 3.) {",
" gl_FragColor = texture2D(u_sampler3, vTextureCoord.xy);",
" } else { gl_FragColor = vec4(0, 1, 0, 1); }",
"}"
].join("\n");
}
function createNodeVertexShader() {
return [
"attribute vec2 a_vertexPos;",
"attribute float a_customAttributes;",
"uniform vec2 u_screenSize;",
"uniform mat4 u_transform;",
"uniform float u_tilesPerTexture;",
"varying vec3 vTextureCoord;",
"void main(void) {",
" gl_Position = u_transform * vec4(a_vertexPos/u_screenSize, 0, 1);",
"float corner = mod(a_customAttributes, 4.);",
"float tileIndex = mod(floor(a_customAttributes / 4.), u_tilesPerTexture);",
"float tilesPerRow = sqrt(u_tilesPerTexture);",
"float tileSize = 1./tilesPerRow;",
"float tileColumn = mod(tileIndex, tilesPerRow);",
"float tileRow = floor(tileIndex/tilesPerRow);",
"if(corner == 0.0) {",
" vTextureCoord.xy = vec2(0, 1);",
"} else if(corner == 1.0) {",
" vTextureCoord.xy = vec2(1, 1);",
"} else if(corner == 2.0) {",
" vTextureCoord.xy = vec2(0, 0);",
"} else {",
" vTextureCoord.xy = vec2(1, 0);",
"}",
"vTextureCoord *= tileSize;",
"vTextureCoord.x += tileColumn * tileSize;",
"vTextureCoord.y += tileRow * tileSize;",
"vTextureCoord.z = floor(floor(a_customAttributes / 4.)/u_tilesPerTexture);",
"}"
].join("\n");
}
},{"./webgl.js":53,"./webglAtlas.js":54}],57:[function(require,module,exports){
var documentEvents = require('../Utils/documentEvents.js');
module.exports = webglInputEvents;
/**
* Monitors graph-related mouse input in webgl graphics and notifies subscribers.
*
* @param {Viva.Graph.View.webglGraphics} webglGraphics
*/
function webglInputEvents(webglGraphics) {
if (webglGraphics.webglInputEvents) {
// Don't listen twice, if we are already attached to this graphics:
return webglGraphics.webglInputEvents;
}
var mouseCapturedNode = null,
mouseEnterCallback = [],
mouseLeaveCallback = [],
mouseDownCallback = [],
mouseUpCallback = [],
mouseMoveCallback = [],
clickCallback = [],
dblClickCallback = [],
prevSelectStart,
boundRect;
var root = webglGraphics.getGraphicsRoot();
startListen(root);
var api = {
mouseEnter: mouseEnter,
mouseLeave: mouseLeave,
mouseDown: mouseDown,
mouseUp: mouseUp,
mouseMove: mouseMove,
click: click,
dblClick: dblClick,
mouseCapture: mouseCapture,
releaseMouseCapture: releaseMouseCapture
};
// TODO I don't remember why this is needed:
webglGraphics.webglInputEvents = api;
return api;
function releaseMouseCapture() {
mouseCapturedNode = null;
}
function mouseCapture(node) {
mouseCapturedNode = node;
}
function dblClick(callback) {
if (typeof callback === 'function') {
dblClickCallback.push(callback);
}
return api;
}
function click(callback) {
if (typeof callback === 'function') {
clickCallback.push(callback);
}
return api;
}
function mouseMove(callback) {
if (typeof callback === 'function') {
mouseMoveCallback.push(callback);
}
return api;
}
function mouseUp(callback) {
if (typeof callback === 'function') {
mouseUpCallback.push(callback);
}
return api;
}
function mouseDown(callback) {
if (typeof callback === 'function') {
mouseDownCallback.push(callback);
}
return api;
}
function mouseLeave(callback) {
if (typeof callback === 'function') {
mouseLeaveCallback.push(callback);
}
return api;
}
function mouseEnter(callback) {
if (typeof callback === 'function') {
mouseEnterCallback.push(callback);
}
return api;
}
function preciseCheck(nodeUI, x, y) {
if (nodeUI && nodeUI.size) {
var pos = nodeUI.position,
half = nodeUI.size;
return pos.x - half < x && x < pos.x + half &&
pos.y - half < y && y < pos.y + half;
}
return true;
}
function getNodeAtClientPos(pos) {
return webglGraphics.getNodeAtClientPos(pos, preciseCheck);
}
function stopPropagation(e) {
if (e.stopPropagation) {
e.stopPropagation();
} else {
e.cancelBubble = true;
}
}
function handleDisabledEvent(e) {
stopPropagation(e);
return false;
}
function invoke(callbacksChain, args) {
var i, stopPropagation;
for (i = 0; i < callbacksChain.length; i += 1) {
stopPropagation = callbacksChain[i].apply(undefined, args);
if (stopPropagation) {
return true;
}
}
}
function startListen(root) {
var pos = {
x: 0,
y: 0
},
lastFound = null,
lastUpdate = 1,
lastClickTime = +new Date(),
handleMouseMove = function(e) {
invoke(mouseMoveCallback, [lastFound, e]);
pos.x = e.clientX;
pos.y = e.clientY;
},
handleMouseUp = function() {
documentEvents.off('mousemove', handleMouseMove);
documentEvents.off('mouseup', handleMouseUp);
},
updateBoundRect = function() {
boundRect = root.getBoundingClientRect();
};
window.addEventListener('resize', updateBoundRect);
updateBoundRect();
// mouse move inside container serves only to track mouse enter/leave events.
root.addEventListener('mousemove',
function(e) {
if (mouseCapturedNode) {
return;
}
if (lastUpdate++ % 7 === 0) {
// since there is no bullet proof method to detect resize
// event, we preemptively update the bounding rectangle
updateBoundRect();
lastUpdate = 1;
}
var cancelBubble = false,
node;
pos.x = e.clientX - boundRect.left;
pos.y = e.clientY - boundRect.top;
node = getNodeAtClientPos(pos);
if (node && lastFound !== node) {
lastFound = node;
cancelBubble = cancelBubble || invoke(mouseEnterCallback, [lastFound]);
} else if (node === null && lastFound !== node) {
cancelBubble = cancelBubble || invoke(mouseLeaveCallback, [lastFound]);
lastFound = null;
}
if (cancelBubble) {
stopPropagation(e);
}
});
root.addEventListener('mousedown',
function(e) {
var cancelBubble = false,
args;
updateBoundRect();
pos.x = e.clientX - boundRect.left;
pos.y = e.clientY - boundRect.top;
args = [getNodeAtClientPos(pos), e];
if (args[0]) {
cancelBubble = invoke(mouseDownCallback, args);
// we clicked on a node. Following drag should be handled on document events:
documentEvents.on('mousemove', handleMouseMove);
documentEvents.on('mouseup', handleMouseUp);
prevSelectStart = window.document.onselectstart;
window.document.onselectstart = handleDisabledEvent;
lastFound = args[0];
} else {
lastFound = null;
}
if (cancelBubble) {
stopPropagation(e);
}
});
root.addEventListener('mouseup',
function(e) {
var clickTime = +new Date(),
args;
pos.x = e.clientX - boundRect.left;
pos.y = e.clientY - boundRect.top;
var nodeAtClientPos = getNodeAtClientPos(pos);
var sameNode = nodeAtClientPos === lastFound;
args = [nodeAtClientPos || lastFound, e];
if (args[0]) {
window.document.onselectstart = prevSelectStart;
if (clickTime - lastClickTime < 400 && sameNode) {
invoke(dblClickCallback, args);
} else {
invoke(clickCallback, args);
}
lastClickTime = clickTime;
if (invoke(mouseUpCallback, args)) {
stopPropagation(e);
}
}
});
}
}
},{"../Utils/documentEvents.js":40}],58:[function(require,module,exports){
var parseColor = require('./parseColor.js');
module.exports = webglLine;
/**
* Defines a webgl line. This class has no rendering logic at all,
* it's just passed to corresponding shader and the shader should
* figure out how to render it.
*
*/
function webglLine(color) {
return {
/**
* Gets or sets color of the line. If you set this property externally
* make sure it always come as integer of 0xRRGGBBAA format
*/
color: parseColor(color)
};
}
},{"./parseColor.js":51}],59:[function(require,module,exports){
/**
* @fileOverview Defines a naive form of links for webglGraphics class.
* This form allows to change color of links.
**/
var glUtils = require('./webgl.js');
module.exports = webglLinkProgram;
/**
* Defines UI for links in webgl renderer.
*/
function webglLinkProgram() {
var ATTRIBUTES_PER_PRIMITIVE = 6, // primitive is Line with two points. Each has x,y and color = 3 * 2 attributes.
BYTES_PER_LINK = 2 * (2 * Float32Array.BYTES_PER_ELEMENT + Uint32Array.BYTES_PER_ELEMENT), // two nodes * (x, y + color)
linksFS = [
'precision mediump float;',
'varying vec4 color;',
'void main(void) {',
' gl_FragColor = color;',
'}'
].join('\n'),
linksVS = [
'attribute vec2 a_vertexPos;',
'attribute vec4 a_color;',
'uniform vec2 u_screenSize;',
'uniform mat4 u_transform;',
'varying vec4 color;',
'void main(void) {',
' gl_Position = u_transform * vec4(a_vertexPos/u_screenSize, 0.0, 1.0);',
' color = a_color.abgr;',
'}'
].join('\n'),
program,
gl,
buffer,
utils,
locations,
linksCount = 0,
frontLinkId, // used to track z-index of links.
storage = new ArrayBuffer(16 * BYTES_PER_LINK),
positions = new Float32Array(storage),
colors = new Uint32Array(storage),
width,
height,
transform,
sizeDirty,
ensureEnoughStorage = function () {
// TODO: this is a duplicate of webglNodeProgram code. Extract it to webgl.js
if ((linksCount+1)*BYTES_PER_LINK > storage.byteLength) {
// Every time we run out of space create new array twice bigger.
// TODO: it seems buffer size is limited. Consider using multiple arrays for huge graphs
var extendedStorage = new ArrayBuffer(storage.byteLength * 2),
extendedPositions = new Float32Array(extendedStorage),
extendedColors = new Uint32Array(extendedStorage);
extendedColors.set(colors); // should be enough to copy just one view.
positions = extendedPositions;
colors = extendedColors;
storage = extendedStorage;
}
};
return {
load : function (glContext) {
gl = glContext;
utils = glUtils(glContext);
program = utils.createProgram(linksVS, linksFS);
gl.useProgram(program);
locations = utils.getLocations(program, ['a_vertexPos', 'a_color', 'u_screenSize', 'u_transform']);
gl.enableVertexAttribArray(locations.vertexPos);
gl.enableVertexAttribArray(locations.color);
buffer = gl.createBuffer();
},
position: function (linkUi, fromPos, toPos) {
var linkIdx = linkUi.id,
offset = linkIdx * ATTRIBUTES_PER_PRIMITIVE;
positions[offset] = fromPos.x;
positions[offset + 1] = fromPos.y;
colors[offset + 2] = linkUi.color;
positions[offset + 3] = toPos.x;
positions[offset + 4] = toPos.y;
colors[offset + 5] = linkUi.color;
},
createLink : function (ui) {
ensureEnoughStorage();
linksCount += 1;
frontLinkId = ui.id;
},
removeLink : function (ui) {
if (linksCount > 0) { linksCount -= 1; }
// swap removed link with the last link. This will give us O(1) performance for links removal:
if (ui.id < linksCount && linksCount > 0) {
// using colors as a view to array buffer is okay here.
utils.copyArrayPart(colors, ui.id * ATTRIBUTES_PER_PRIMITIVE, linksCount * ATTRIBUTES_PER_PRIMITIVE, ATTRIBUTES_PER_PRIMITIVE);
}
},
updateTransform : function (newTransform) {
sizeDirty = true;
transform = newTransform;
},
updateSize : function (w, h) {
width = w;
height = h;
sizeDirty = true;
},
render : function () {
gl.useProgram(program);
gl.bindBuffer(gl.ARRAY_BUFFER, buffer);
gl.bufferData(gl.ARRAY_BUFFER, storage, gl.DYNAMIC_DRAW);
if (sizeDirty) {
sizeDirty = false;
gl.uniformMatrix4fv(locations.transform, false, transform);
gl.uniform2f(locations.screenSize, width, height);
}
gl.vertexAttribPointer(locations.vertexPos, 2, gl.FLOAT, false, 3 * Float32Array.BYTES_PER_ELEMENT, 0);
gl.vertexAttribPointer(locations.color, 4, gl.UNSIGNED_BYTE, true, 3 * Float32Array.BYTES_PER_ELEMENT, 2 * 4);
gl.drawArrays(gl.LINES, 0, linksCount * 2);
frontLinkId = linksCount - 1;
},
bringToFront : function (link) {
if (frontLinkId > link.id) {
utils.swapArrayPart(positions, link.id * ATTRIBUTES_PER_PRIMITIVE, frontLinkId * ATTRIBUTES_PER_PRIMITIVE, ATTRIBUTES_PER_PRIMITIVE);
}
if (frontLinkId > 0) {
frontLinkId -= 1;
}
},
getFrontLinkId : function () {
return frontLinkId;
}
};
}
},{"./webgl.js":53}],60:[function(require,module,exports){
/**
* @fileOverview Defines a naive form of nodes for webglGraphics class.
* This form allows to change color of node. Shape of nodes is rectangular.
*
* @author Andrei Kashcha (aka anvaka) / https://github.com/anvaka
*/
var glUtils = require('./webgl.js');
module.exports = webglNodeProgram;
/**
* Defines simple UI for nodes in webgl renderer. Each node is rendered as square. Color and size can be changed.
*/
function webglNodeProgram() {
var ATTRIBUTES_PER_PRIMITIVE = 4; // Primitive is point, x, y, size, color
// x, y, z - floats, color = uint.
var BYTES_PER_NODE = 3 * Float32Array.BYTES_PER_ELEMENT + Uint32Array.BYTES_PER_ELEMENT;
var nodesFS = [
'precision mediump float;',
'varying vec4 color;',
'void main(void) {',
' gl_FragColor = color;',
'}'
].join('\n');
var nodesVS = [
'attribute vec3 a_vertexPos;',
'attribute vec4 a_color;',
'uniform vec2 u_screenSize;',
'uniform mat4 u_transform;',
'varying vec4 color;',
'void main(void) {',
' gl_Position = u_transform * vec4(a_vertexPos.xy/u_screenSize, 0, 1);',
' gl_PointSize = a_vertexPos.z * u_transform[0][0];',
' color = a_color.abgr;',
'}'
].join('\n');
var program;
var gl;
var buffer;
var locations;
var utils;
var storage = new ArrayBuffer(16 * BYTES_PER_NODE);
var positions = new Float32Array(storage);
var colors = new Uint32Array(storage);
var nodesCount = 0;
var width;
var height;
var transform;
var sizeDirty;
return {
load: load,
/**
* Updates position of node in the buffer of nodes.
*
* @param idx - index of current node.
* @param pos - new position of the node.
*/
position: position,
updateTransform: updateTransform,
updateSize: updateSize,
removeNode: removeNode,
createNode: createNode,
replaceProperties: replaceProperties,
render: render
};
function ensureEnoughStorage() {
if ((nodesCount + 1) * BYTES_PER_NODE >= storage.byteLength) {
// Every time we run out of space create new array twice bigger.
// TODO: it seems buffer size is limited. Consider using multiple arrays for huge graphs
var extendedStorage = new ArrayBuffer(storage.byteLength * 2),
extendedPositions = new Float32Array(extendedStorage),
extendedColors = new Uint32Array(extendedStorage);
extendedColors.set(colors); // should be enough to copy just one view.
positions = extendedPositions;
colors = extendedColors;
storage = extendedStorage;
}
}
function load(glContext) {
gl = glContext;
utils = glUtils(glContext);
program = utils.createProgram(nodesVS, nodesFS);
gl.useProgram(program);
locations = utils.getLocations(program, ['a_vertexPos', 'a_color', 'u_screenSize', 'u_transform']);
gl.enableVertexAttribArray(locations.vertexPos);
gl.enableVertexAttribArray(locations.color);
buffer = gl.createBuffer();
}
function position(nodeUI, pos) {
var idx = nodeUI.id;
positions[idx * ATTRIBUTES_PER_PRIMITIVE] = pos.x;
positions[idx * ATTRIBUTES_PER_PRIMITIVE + 1] = -pos.y;
positions[idx * ATTRIBUTES_PER_PRIMITIVE + 2] = nodeUI.size;
colors[idx * ATTRIBUTES_PER_PRIMITIVE + 3] = nodeUI.color;
}
function updateTransform(newTransform) {
sizeDirty = true;
transform = newTransform;
}
function updateSize(w, h) {
width = w;
height = h;
sizeDirty = true;
}
function removeNode(node) {
if (nodesCount > 0) {
nodesCount -= 1;
}
if (node.id < nodesCount && nodesCount > 0) {
// we can use colors as a 'view' into array array buffer.
utils.copyArrayPart(colors, node.id * ATTRIBUTES_PER_PRIMITIVE, nodesCount * ATTRIBUTES_PER_PRIMITIVE, ATTRIBUTES_PER_PRIMITIVE);
}
}
function createNode() {
ensureEnoughStorage();
nodesCount += 1;
}
function replaceProperties(/* replacedNode, newNode */) {}
function render() {
gl.useProgram(program);
gl.bindBuffer(gl.ARRAY_BUFFER, buffer);
gl.bufferData(gl.ARRAY_BUFFER, storage, gl.DYNAMIC_DRAW);
if (sizeDirty) {
sizeDirty = false;
gl.uniformMatrix4fv(locations.transform, false, transform);
gl.uniform2f(locations.screenSize, width, height);
}
gl.vertexAttribPointer(locations.vertexPos, 3, gl.FLOAT, false, ATTRIBUTES_PER_PRIMITIVE * Float32Array.BYTES_PER_ELEMENT, 0);
gl.vertexAttribPointer(locations.color, 4, gl.UNSIGNED_BYTE, true, ATTRIBUTES_PER_PRIMITIVE * Float32Array.BYTES_PER_ELEMENT, 3 * 4);
gl.drawArrays(gl.POINTS, 0, nodesCount);
}
}
},{"./webgl.js":53}],61:[function(require,module,exports){
var parseColor = require('./parseColor.js');
module.exports = webglSquare;
/**
* Can be used as a callback in the webglGraphics.node() function, to
* create a custom looking node.
*
* @param size - size of the node in pixels.
* @param color - color of the node in '#rrggbbaa' or '#rgb' format.
*/
function webglSquare(size, color) {
return {
/**
* Gets or sets size of the square side.
*/
size: typeof size === 'number' ? size : 10,
/**
* Gets or sets color of the square.
*/
color: parseColor(color)
};
}
},{"./parseColor.js":51}],62:[function(require,module,exports){
// todo: this should be generated at build time.
module.exports = '0.8.1';
},{}]},{},[1])(1)
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment