Google Git
Sign in
apache / echarts-examples / refs/heads/v4 / . / public / vendors / echarts / extension / graph-modularity.js
blob: 292b6eb35ce36b8b57ac8693ba94bd840f46e186 [file] [log] [blame]
(function webpackUniversalModuleDefinition(root, factory) {
if(typeof exports === 'object' && typeof module === 'object')
module.exports = factory(require("echarts"));
else if(typeof define === 'function' && define.amd)
define(["echarts"], factory);
else if(typeof exports === 'object')
exports["echarts-graph-modularity"] = factory(require("echarts"));
else
root["echarts-graph-modularity"] = factory(root["echarts"]);
})(this, function(__WEBPACK_EXTERNAL_MODULE_9__) {
return /******/ (function(modules) { // webpackBootstrap
/******/ // The module cache
/******/ var installedModules = {};
/******/
/******/ // The require function
/******/ function __webpack_require__(moduleId) {
/******/
/******/ // Check if module is in cache
/******/ if(installedModules[moduleId]) {
/******/ return installedModules[moduleId].exports;
/******/ }
/******/ // Create a new module (and put it into the cache)
/******/ var module = installedModules[moduleId] = {
/******/ i: moduleId,
/******/ l: false,
/******/ exports: {}
/******/ };
/******/
/******/ // Execute the module function
/******/ modules[moduleId].call(module.exports, module, module.exports, __webpack_require__);
/******/
/******/ // Flag the module as loaded
/******/ module.l = true;
/******/
/******/ // Return the exports of the module
/******/ return module.exports;
/******/ }
/******/
/******/
/******/ // expose the modules object (__webpack_modules__)
/******/ __webpack_require__.m = modules;
/******/
/******/ // expose the module cache
/******/ __webpack_require__.c = installedModules;
/******/
/******/ // define getter function for harmony exports
/******/ __webpack_require__.d = function(exports, name, getter) {
/******/ if(!__webpack_require__.o(exports, name)) {
/******/ Object.defineProperty(exports, name, {
/******/ configurable: false,
/******/ enumerable: true,
/******/ get: getter
/******/ });
/******/ }
/******/ };
/******/
/******/ // getDefaultExport function for compatibility with non-harmony modules
/******/ __webpack_require__.n = function(module) {
/******/ var getter = module && module.__esModule ?
/******/ function getDefault() { return module['default']; } :
/******/ function getModuleExports() { return module; };
/******/ __webpack_require__.d(getter, 'a', getter);
/******/ return getter;
/******/ };
/******/
/******/ // Object.prototype.hasOwnProperty.call
/******/ __webpack_require__.o = function(object, property) { return Object.prototype.hasOwnProperty.call(object, property); };
/******/
/******/ // __webpack_public_path__
/******/ __webpack_require__.p = "";
/******/
/******/ // Load entry module and return exports
/******/ return __webpack_require__(__webpack_require__.s = 0);
/******/ })
/************************************************************************/
/******/ ([
/* 0 */
/***/ (function(module, exports, __webpack_require__) {
module.exports = __webpack_require__(1);
/***/ }),
/* 1 */
/***/ (function(module, exports, __webpack_require__) {
var Modularity = __webpack_require__(2);
var echarts = __webpack_require__(9);
var createNGraph = __webpack_require__(10);
function createModularityVisual(chartType) {
return function (ecModel, api) {
var paletteScope = {};
ecModel.eachSeriesByType(chartType, function (seriesModel) {
var modularityOpt = seriesModel.get('modularity');
if (modularityOpt) {
var graph = seriesModel.getGraph();
var idIndexMap = {};
var ng = createNGraph();
graph.data.each(function (idx) {
var node = graph.getNodeByIndex(idx);
idIndexMap[node.id] = idx;
ng.addNode(node.id);
return node.id;
});
graph.edgeData.each('value', function (val, idx) {
var edge = graph.getEdgeByIndex(idx);
ng.addLink(edge.node1.id, edge.node2.id);
return {
source: edge.node1.id,
target: edge.node2.id,
value: val
};
});
var modularity = new Modularity(seriesModel.get('modularity.resolution') || 1);
var result = modularity.execute(ng);
var communities = {};
for (var id in result) {
var comm = result[id];
communities[comm] = communities[comm] || 0;
communities[comm]++;
}
var communitiesList = Object.keys(communities);
if (seriesModel.get('modularity.sort')) {
communitiesList.sort(function (a, b) {
return b - a;
});
}
var colors = {};
communitiesList.forEach(function (comm) {
colors[comm] = seriesModel.getColorFromPalette(comm, paletteScope);
});
for (var id in result) {
var comm = result[id];
graph.data.setItemVisual(idIndexMap[id], 'color', colors[comm]);
}
graph.edgeData.each(function (idx) {
var itemModel = graph.edgeData.getItemModel(idx);
var edge = graph.getEdgeByIndex(idx);
var color = itemModel.get('lineStyle.normal.color');
switch (color) {
case 'source':
color = edge.node1.getVisual('color');
break;
case 'target':
color = edge.node2.getVisual('color');
break;
}
if (color != null) {
edge.setVisual('color', color);
}
});
}
});
};
}
echarts.registerVisual(echarts.PRIORITY.VISUAL.CHART + 1, createModularityVisual('graph'));
echarts.registerVisual(echarts.PRIORITY.VISUAL.CHART + 1, createModularityVisual('graphGL'));
/***/ }),
/* 2 */
/***/ (function(module, exports, __webpack_require__) {
/*
Copyright 2008-2011 Gephi
Authors : Patick J. McSweeney <pjmcswee@syr.edu>, Sebastien Heymann <seb@gephi.org>
Website : http://www.gephi.org
This file is part of Gephi.
DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
Copyright 2011 Gephi Consortium. All rights reserved.
The contents of this file are subject to the terms of either the GNU
General Public License Version 3 only ("GPL") or the Common
Development and Distribution License("CDDL") (collectively, the
"License"). You may not use this file except in compliance with the
License. You can obtain a copy of the License at
http://gephi.org/about/legal/license-notice/
or /cddl-1.0.txt and /gpl-3.0.txt. See the License for the
specific language governing permissions and limitations under the
License. When distributing the software, include this License Header
Notice in each file and include the License files at
/cddl-1.0.txt and /gpl-3.0.txt. If applicable, add the following below the
License Header, with the fields enclosed by brackets [] replaced by
your own identifying information:
"Portions Copyrighted [year] [name of copyright owner]"
If you wish your version of this file to be governed by only the CDDL
or only the GPL Version 3, indicate your decision by adding
"[Contributor] elects to include this software in this distribution
under the [CDDL or GPL Version 3] license." If you do not indicate a
single choice of license, a recipient has the option to distribute
your version of this file under either the CDDL, the GPL Version 3 or
to extend the choice of license to its licensees as provided above.
However, if you add GPL Version 3 code and therefore, elected the GPL
Version 3 license, then the option applies only if the new code is
made subject to such option by the copyright holder.
Contributor(s): Thomas Aynaud <taynaud@gmail.com>
Portions Copyrighted 2011 Gephi Consortium.
*/
var CommunityStructure = __webpack_require__(3)
, centrality = __webpack_require__(6)
;
/**
* @constructor
*/
function Modularity (resolution, useWeight) {
this.isRandomized = false;
this.useWeight = useWeight;
this.resolution = resolution || 1.;
/**
* @type {CommunityStructure}
*/
this.structure = null;
}
/**
* @param {IGraph} graph
*/
Modularity.prototype.execute = function (graph/*, AttributeModel attributeModel*/) {
this.structure = new CommunityStructure(graph, this.useWeight);
var comStructure = new Array(graph.getNodesCount());
var computedModularityMetrics = this.computeModularity(
graph
, this.structure
, comStructure
, this.resolution
, this.isRandomized
, this.useWeight
);
var result = {};
this.structure.map.forEach(function (i, node) {
result[node] = comStructure[i];
});
return result;
};
/**
*
* @param {IGraph} graph
* @param {CommunityStructure} theStructure
* @param {Array.<Number>} comStructure
* @param {Number} currentResolution
* @param {Boolean} randomized
* @param {Boolean} weighted
* @returns {Object.<String, Number>}
*/
Modularity.prototype.computeModularity = function(graph, theStructure, comStructure, currentResolution, randomized, weighted) {
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min)) + min;
}
var totalWeight = theStructure.graphWeightSum;
var nodeDegrees = theStructure.weights.slice();
var /** @type {Object.<String, Number>} */ results = Object.create(null);
var someChange = true;
while (someChange) {
someChange = false;
var localChange = true;
while (localChange) {
localChange = false;
var start = 0;
if (randomized) {
//start = Math.abs(rand.nextInt()) % theStructure.N;
start = getRandomInt(0,theStructure.N);
}
var step = 0;
for (var i = start; step < theStructure.N; i = (i + 1) % theStructure.N) {
step++;
var bestCommunity = this.updateBestCommunity(theStructure, i, currentResolution);
if ((theStructure.nodeCommunities[i] != bestCommunity) && (bestCommunity != null)) {
theStructure.moveNodeTo(i, bestCommunity);
localChange = true;
}
}
someChange = localChange || someChange;
}
if (someChange) {
theStructure.zoomOut();
}
}
this.fillComStructure(graph, theStructure, comStructure);
/*
//TODO: uncomment when finalQ will be implemented
var degreeCount = this.fillDegreeCount(graph, theStructure, comStructure, nodeDegrees, weighted);
var computedModularity = this._finalQ(comStructure, degreeCount, graph, theStructure, totalWeight, 1., weighted);
var computedModularityResolution = this._finalQ(comStructure, degreeCount, graph, theStructure, totalWeight, currentResolution, weighted);
results["modularity"] = computedModularity;
results["modularityResolution"] = computedModularityResolution;
*/
return results;
};
/**
* @param {CommunityStructure} theStructure
* @param {Number} i
* @param {Number} currentResolution
* @returns {Community}
*/
Modularity.prototype.updateBestCommunity = function(theStructure, i, currentResolution) {
var best = this.q(i, theStructure.nodeCommunities[i], theStructure, currentResolution);
var bestCommunity = theStructure.nodeCommunities[i];
//var /*Set<Community>*/ iter = theStructure.nodeConnectionsWeight[i].keySet();
theStructure.nodeConnectionsWeight[i].forEach(function (_$$val, com) {
var qValue = this.q(i, com, theStructure, currentResolution);
if (qValue > best) {
best = qValue;
bestCommunity = com;
}
}, this);
return bestCommunity;
};
/**
*
* @param {IGraph} graph
* @param {CommunityStructure} theStructure
* @param {Array.<Number>} comStructure
* @returns {Array.<Number>}
*/
Modularity.prototype.fillComStructure = function(graph, theStructure, comStructure) {
var count = 0;
theStructure.communities.forEach(function (com) {
com.nodes.forEach(function (node) {
var hidden = theStructure.invMap.get(node);
hidden.nodes.forEach( function (nodeInt){
comStructure[nodeInt] = count;
});
});
count++;
});
return comStructure;
};
/**
* @param {IGraph} graph
* @param {CommunityStructure} theStructure
* @param {Array.<Number>} comStructure
* @param {Array.<Number>} nodeDegrees
* @param {Boolean} weighted
* @returns {Array.<Number>}
*/
Modularity.prototype.fillDegreeCount = function(graph, theStructure, comStructure, nodeDegrees, weighted) {
var degreeCount = new Array(theStructure.communities.length);
var degreeCentrality = centrality.degree(graph);
graph.forEachNode(function(node){
var index = theStructure.map.get(node);
if (weighted) {
degreeCount[comStructure[index]] += nodeDegrees[index];
} else {
degreeCount[comStructure[index]] += degreeCentrality[node.id];
}
});
return degreeCount;
};
/**
*
* @param {Array.<Number>} struct
* @param {Array.<Number>} degrees
* @param {IGraph} graph
* @param {CommunityStructure} theStructure
* @param {Number} totalWeight
* @param {Number} usedResolution
* @param {Boolean} weighted
* @returns {Number}
*/
Modularity.prototype._finalQ = function(struct, degrees, graph, theStructure, totalWeight, usedResolution, weighted) {
//TODO: rewrite for wighted version of algorithm
throw new Error("not implemented properly");
var res = 0;
var internal = new Array(degrees.length);
graph.forEachNode(function(n){
var n_index = theStructure.map.get(n);
graph.forEachLinkedNode(n.id, function(neighbor){
if (n == neighbor) {
return;
}
var neigh_index = theStructure.map.get(neighbor);
if (struct[neigh_index] == struct[n_index]) {
if (weighted) {
//throw new Error("weighted aren't implemented");
//internal[struct[neigh_index]] += graph.getEdge(n, neighbor).getWeight();
} else {
internal[struct[neigh_index]]++;
}
}
}.bind(this), false);
}.bind(this));
for (var i = 0; i < degrees.length; i++) {
internal[i] /= 2.0;
res += usedResolution * (internal[i] / totalWeight) - Math.pow(degrees[i] / (2 * totalWeight), 2);//HERE
}
return res;
};
/**
*
* @param {Number} nodeId
* @param {Community} community
* @param {CommunityStructure} theStructure
* @param {Number} currentResolution
* @returns {Number}
*/
Modularity.prototype.q = function(nodeId, community, theStructure, currentResolution) {
var edgesToFloat = theStructure.nodeConnectionsWeight[nodeId].get(community);
var edgesTo = 0;
if (edgesToFloat != null) {
edgesTo = edgesToFloat;
}
var weightSum = community.weightSum;
var nodeWeight = theStructure.weights[nodeId];
var qValue = currentResolution * edgesTo - (nodeWeight * weightSum) / (2.0 * theStructure.graphWeightSum);
if ((theStructure.nodeCommunities[nodeId] == community) && (theStructure.nodeCommunities[nodeId].size() > 1)) {
qValue = currentResolution * edgesTo - (nodeWeight * (weightSum - nodeWeight)) / (2.0 * theStructure.graphWeightSum);
}
if ((theStructure.nodeCommunities[nodeId] == community) && (theStructure.nodeCommunities[nodeId].size() == 1)) {
qValue = 0.;
}
return qValue;
};
module.exports = Modularity;
/***/ }),
/* 3 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var Community = __webpack_require__(4)
, ModEdge = __webpack_require__(5)
;
/**
*
* @param {IGraph} graph
* @param useWeight
* @param {CommunityStructure} structure
* @constructor
*/
function CommunityStructure(graph, useWeight) {
//this.graph = graph;
this.N = graph.getNodesCount();
this.graphWeightSum = 0;
this.structure = this;
/** @type {Map.<Number, Community>} */
this.invMap = new Map();
/** @type {Array.< Map.<Community, Number> >} */
this.nodeConnectionsWeight = new Array(this.N);
/** @type {Array.< Map.<Community, Number> >} */
this.nodeConnectionsCount = new Array(this.N);
/** @type {Array.<Community>} */
this.nodeCommunities = new Array(this.N);
/** @type {Map.<Node, Number>} */
this.map = new Map();
/** @type {Array.< Array.<ModEdge> >} */
this.topology = new Array(this.N);
for (var i = 0; i < this.N; i++) this.topology[i] = [];
/** @type {Array.<Community>} */
this.communities = [];
/**@type {Array.<Number>} */
this.weights = new Array(this.N);
var index = 0;
graph.forEachNode(function (node) {
this.map.set(node.id, index);
this.nodeCommunities[index] = new Community(this);
this.nodeConnectionsWeight[index] = new Map();
this.nodeConnectionsCount[index] = new Map();
this.weights[index] = 0;
this.nodeCommunities[index].seed(index);
var hidden = new Community(this);
hidden.nodes.add(index);
this.invMap.set(index, hidden);
this.communities.push(this.nodeCommunities[index]);
index++;
}.bind(this));
graph.forEachLink(function (link) {
var node_index = this.map.get(link.fromId)
, neighbor_index = this.map.get(link.toId)
, weight = 1
;
if (node_index === neighbor_index) {
return;
}
if (useWeight) {
weight = link.data.weight;
}
this.setUpLink(node_index, neighbor_index, weight);
this.setUpLink(neighbor_index, node_index, weight);
}.bind(this));
this.graphWeightSum /= 2.0;
}
CommunityStructure.prototype.setUpLink = function (node_index, neighbor_index, weight) {
this.weights[node_index] += weight;
var /** @type {ModEdge} */ me = new ModEdge(node_index, neighbor_index, weight);
this.topology[node_index].push(me);
var /** @type {Community} **/ adjCom = this.nodeCommunities[neighbor_index];
this.nodeConnectionsWeight[node_index].set(adjCom, weight);
this.nodeConnectionsCount[node_index].set(adjCom, 1);
this.nodeCommunities[node_index].connectionsWeight.set(adjCom, weight);
this.nodeCommunities[node_index].connectionsCount.set(adjCom, 1);
this.nodeConnectionsWeight[neighbor_index].set(this.nodeCommunities[node_index], weight);
this.nodeConnectionsCount[neighbor_index].set(this.nodeCommunities[node_index], 1);
this.nodeCommunities[neighbor_index].connectionsWeight.set(this.nodeCommunities[node_index], weight);
this.nodeCommunities[neighbor_index].connectionsCount.set(this.nodeCommunities[node_index], 1);
this.graphWeightSum += weight;
};
/**
* @param {Number} node
* @param {Community} to
*/
CommunityStructure.prototype.addNodeTo = function (node, to) {
to.add(node);
this.nodeCommunities[node] = to;
var nodeTopology = this.topology[node];
for (var topologyKey in nodeTopology) {
//noinspection JSUnfilteredForInLoop
var /** @type {ModEdge} */ e = nodeTopology[topologyKey];
var neighbor = e.target;
//Remove Node Connection to this community
var neighEdgesTo = this.nodeConnectionsWeight[neighbor].get(to);
if (neighEdgesTo === undefined) {
this.nodeConnectionsWeight[neighbor].set(to, e.weight);
} else {
this.nodeConnectionsWeight[neighbor].set(to, neighEdgesTo + e.weight);
}
var neighCountEdgesTo = this.nodeConnectionsCount[neighbor].get(to);
if (neighCountEdgesTo === undefined) {
this.nodeConnectionsCount[neighbor].set(to, 1);
} else {
this.nodeConnectionsCount[neighbor].set(to, neighCountEdgesTo + 1);
}
var /** @type {Community} */ adjCom = this.nodeCommunities[neighbor];
var wEdgesto = adjCom.connectionsWeight.get(to);
if (wEdgesto === undefined) {
adjCom.connectionsWeight.set(to, e.weight);
} else {
adjCom.connectionsWeight.set(to, wEdgesto + e.weight);
}
var cEdgesto = adjCom.connectionsCount.get(to);
if (cEdgesto === undefined) {
adjCom.connectionsCount.set(to, 1);
} else {
adjCom.connectionsCount.set(to, cEdgesto + 1);
}
var nodeEdgesTo = this.nodeConnectionsWeight[node].get(adjCom);
if (nodeEdgesTo === undefined) {
this.nodeConnectionsWeight[node].set(adjCom, e.weight);
} else {
this.nodeConnectionsWeight[node].set(adjCom, nodeEdgesTo + e.weight);
}
var nodeCountEdgesTo = this.nodeConnectionsCount[node].get(adjCom);
if (nodeCountEdgesTo === undefined) {
this.nodeConnectionsCount[node].set(adjCom, 1);
} else {
this.nodeConnectionsCount[node].set(adjCom, nodeCountEdgesTo + 1);
}
if (to != adjCom) {
var comEdgesto = to.connectionsWeight.get(adjCom);
if (comEdgesto === undefined) {
to.connectionsWeight.set(adjCom, e.weight);
} else {
to.connectionsWeight.set(adjCom, comEdgesto + e.weight);
}
var comCountEdgesto = to.connectionsCount.get(adjCom);
if (comCountEdgesto === undefined) {
to.connectionsCount.set(adjCom, 1);
} else {
to.connectionsCount.set(adjCom, comCountEdgesto + 1);
}
}
}
};
/**
* @param {Number} node
* @param {Community} source
*/
CommunityStructure.prototype.removeNodeFrom = function (node, source) {
var community = this.nodeCommunities[node];
var nodeTopology = this.topology[node];
for (var topologyKey in nodeTopology) {
//noinspection JSUnfilteredForInLoop
var /** @type {ModEdge} */ e = nodeTopology[topologyKey];
var neighbor = e.target;
//Remove Node Connection to this community
var edgesTo = this.nodeConnectionsWeight[neighbor].get(community);
var countEdgesTo = this.nodeConnectionsCount[neighbor].get(community);
if ((countEdgesTo - 1) == 0) {
this.nodeConnectionsWeight[neighbor].delete(community);
this.nodeConnectionsCount[neighbor].delete(community);
} else {
this.nodeConnectionsWeight[neighbor].set(community, edgesTo - e.weight);
this.nodeConnectionsCount[neighbor].set(community, countEdgesTo - 1);
}
//Remove Adjacency Community's connection to this community
var adjCom = this.nodeCommunities[neighbor];
var oEdgesto = adjCom.connectionsWeight.get(community);
var oCountEdgesto = adjCom.connectionsCount.get(community);
if ((oCountEdgesto - 1) == 0) {
adjCom.connectionsWeight.delete(community);
adjCom.connectionsCount.delete(community);
} else {
adjCom.connectionsWeight.set(community, oEdgesto - e.weight);
adjCom.connectionsCount.set(community, oCountEdgesto - 1);
}
if (node == neighbor) {
continue;
}
if (adjCom != community) {
var comEdgesto = community.connectionsWeight.get(adjCom);
var comCountEdgesto = community.connectionsCount.get(adjCom);
if (comCountEdgesto - 1 == 0) {
community.connectionsWeight.delete(adjCom);
community.connectionsCount.delete(adjCom);
} else {
community.connectionsWeight.set(adjCom, comEdgesto - e.weight);
community.connectionsCount.set(adjCom, comCountEdgesto - 1);
}
}
var nodeEdgesTo = this.nodeConnectionsWeight[node].get(adjCom);
var nodeCountEdgesTo = this.nodeConnectionsCount[node].get(adjCom);
if ((nodeCountEdgesTo - 1) == 0) {
this.nodeConnectionsWeight[node].delete(adjCom);
this.nodeConnectionsCount[node].delete(adjCom);
} else {
this.nodeConnectionsWeight[node].set(adjCom, nodeEdgesTo - e.weight);
this.nodeConnectionsCount[node].set(adjCom, nodeCountEdgesTo - 1);
}
}
source.remove(node);
};
/**
* @param {Number} node
* @param {Community} to
*/
CommunityStructure.prototype.moveNodeTo = function (node, to) {
var source = this.nodeCommunities[node];
this.removeNodeFrom(node, source);
this.addNodeTo(node, to);
};
CommunityStructure.prototype.zoomOut = function () {
var realCommunities = this.communities.reduce(function (arr, value) {
arr.push(value);
return arr;
}, []);
var M = realCommunities.length; // size
var /** @type Array.< Array.<ModEdge> > */ newTopology = new Array(M);
var index = 0;
this.nodeCommunities = new Array(M);
this.nodeConnectionsWeight = new Array(M);
this.nodeConnectionsCount = new Array(M);
var /** @type Map.<Number, Community>*/ newInvMap = new Map();
realCommunities.forEach(function (com) {
var weightSum = 0;
this.nodeConnectionsWeight[index] = new Map();
this.nodeConnectionsCount[index] = new Map();
newTopology[index] = [];
this.nodeCommunities[index] = new Community(com);
//var iter = com.connectionsWeight.keySet();
var hidden = new Community(this.structure);
com.nodes.forEach(function (nodeInt) {
var oldHidden = this.invMap.get(nodeInt);
oldHidden.nodes.forEach(hidden.nodes.add.bind(hidden.nodes));
}, this);
newInvMap.set(index, hidden);
com.connectionsWeight.forEach(function (weight, adjCom) {
var target = realCommunities.indexOf(adjCom);
if (!~target) return;
if (target == index) {
weightSum += 2. * weight;
} else {
weightSum += weight;
}
var e = new ModEdge(index, target, weight);
newTopology[index].push(e);
}, this);
this.weights[index] = weightSum;
this.nodeCommunities[index].seed(index);
index++;
}.bind(this));
this.communities = [];
for (var i = 0; i < M; i++) {
var com = this.nodeCommunities[i];
this.communities.push(com);
for (var ei in newTopology[i]) {
//noinspection JSUnfilteredForInLoop
var e = newTopology[i][ei];
this.nodeConnectionsWeight[i].set(this.nodeCommunities[e.target], e.weight);
this.nodeConnectionsCount[i].set(this.nodeCommunities[e.target], 1);
com.connectionsWeight.set(this.nodeCommunities[e.target], e.weight);
com.connectionsCount.set(this.nodeCommunities[e.target], 1);
}
}
this.N = M;
this.topology = newTopology;
this.invMap = newInvMap;
};
module.exports = CommunityStructure;
/***/ }),
/* 4 */
/***/ (function(module, exports) {
/**
* @param {CommunityStructure|Community} com
* @constructor
*/
function Community(com) {
/** @type {CommunityStructure} */
this.structure = com.structure ? com.structure : com;
/** @type {Map.<Community, Number>} */
this.connectionsWeight = new Map();
/** @type {Map.<Community, Number>} */
this.connectionsCount = new Map();
/** @type {Set.<Number>} */
this.nodes = new Set;
this.weightSum = 0;
}
/**
* @public
* @returns {Number}
*/
Community.prototype.size = function() {
return this.nodes.size;
};
/**
* @param {Number} node
*/
Community.prototype.seed = function(node) {
this.nodes.add(node);
this.weightSum += this.structure.weights[node];
};
/**
* @param {Number} nodeId
* @returns {boolean}
*/
Community.prototype.add = function(nodeId) {
this.nodes.add(nodeId);
this.weightSum += this.structure.weights[nodeId];
return true;
};
/**
* @param {Number} node
* @returns {boolean}
*/
Community.prototype.remove = function(node) {
var result = this.nodes.delete(node);
this.weightSum -= this.structure.weights[node];
if (!this.nodes.size) {
var index = this.structure.communities.indexOf(this);
delete this.structure.communities[index];
}
return result;
};
module.exports = Community;
/***/ }),
/* 5 */
/***/ (function(module, exports) {
/**
*
* @param s
* @param t
* @param w
* @constructor
*/
function ModEdge(s, t, w) {
/** @type {Number} */
this.source = s;
/** @type {Number} */
this.target = t;
/** @type {Number} */
this.weight = w;
}
module.exports = ModEdge;
/***/ }),
/* 6 */
/***/ (function(module, exports, __webpack_require__) {
module.exports.degree = __webpack_require__(7);
module.exports.betweenness = __webpack_require__(8);
/***/ }),
/* 7 */
/***/ (function(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;
if (!links) return total;
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;
if (!links) return total;
for (var i = 0; i < links.length; i += 1) {
total += (links[i].fromId === nodeId) ? 1 : 0;
}
return total;
}
function inoutDegreeCalculator(links) {
if (!links) return 0;
return links.length;
}
/***/ }),
/* 8 */
/***/ (function(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);
}
}
}
}
/***/ }),
/* 9 */
/***/ (function(module, exports) {
module.exports = __WEBPACK_EXTERNAL_MODULE_9__;
/***/ }),
/* 10 */
/***/ (function(module, exports, __webpack_require__) {
/**
* @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 = __webpack_require__(11);
/**
* 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.
* @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) {
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();
if (node.links) {
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.
addLinkToNode(fromNode, link);
if (fromId !== toId) {
// make sure we are not duplicating links for self-loops
addLinkToNode(toNode, link);
}
recordLinkChange(link, 'add');
exitModification();
return link;
}
function createSingleLink(fromId, toId, data) {
var linkId = makeLinkId(fromId, toId);
return new Link(fromId, toId, data, linkId);
}
function createUniqueLink(fromId, toId, data) {
// TODO: Get rid of this method.
var linkId = makeLinkId(fromId, toId);
var isMultiEdge = multiEdges.hasOwnProperty(linkId);
if (isMultiEdge || getLink(fromId, toId)) {
if (!isMultiEdge) {
multiEdges[linkId] = 0;
}
var suffix = '@' + (++multiEdges[linkId]);
linkId = makeLinkId(fromId + suffix, toId + suffix);
}
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 || !node.links) {
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) return -1;
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 = null;
this.data = null;
}
function addLinkToNode(node, link) {
if (node.links) {
node.links.push(link);
} else {
node.links = [link];
}
}
/**
* Internal structure to represent links;
*/
function Link(fromId, toId, data, id) {
this.fromId = fromId;
this.toId = toId;
this.data = data;
this.id = id;
}
function hashCode(str) {
var hash = 0, i, chr, len;
if (str.length == 0) return hash;
for (i = 0, len = str.length; i < len; i++) {
chr = str.charCodeAt(i);
hash = ((hash << 5) - hash) + chr;
hash |= 0; // Convert to 32bit integer
}
return hash;
}
function makeLinkId(fromId, toId) {
return hashCode(fromId.toString() + '👉 ' + toId.toString());
}
/***/ }),
/* 11 */
/***/ (function(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] + "'");
}
}
}
/***/ })
/******/ ]);
});