Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function round(n) {
- return Math.round(n*100) / 100;
- }
- // Represents an edge from source to sink with capacity
- var Edge = function(source, sink, capacity) {
- this.source = source;
- this.sink = sink;
- this.capacity = capacity;
- };
- // Main class to manage the network
- var Graph = function() {
- this.edges = {};
- this.nodes = [];
- this.nodeMap = {};
- // Add a node to the graph
- this.addNode = function(node) {
- this.nodes.push(node);
- this.nodeMap[node] = this.nodes.length-1;
- this.edges[node] = [];
- };
- // Add an edge from source to sink with capacity
- this.addEdge = function(source, sink, capacity) {
- // Create the two edges = one being the reverse of the other
- var edge = new Edge(source, sink, capacity);
- this.edges[source].push(edge);
- };
- // Does edge from source to sink exist?
- this.edgeExists = function(source, sink) {
- if(this.edges[source] !== undefined)
- for(var i=0;i<this.edges[source].length;i++)
- if(this.edges[source][i].sink == sink)
- return this.edges[source][i];
- return null;
- };
- // Turn the set of nodes and edges to a matrix with the value being
- // the capacity between the nodes
- this.getAssociatedMatrix = function() {
- var matrix = [];
- for(var i=0;i<this.nodes.length;i++) {
- var row = [];
- for(var j=0;j<this.nodes.length;j++) {
- var edge = this.edgeExists(this.nodes[j], this.nodes[i]);
- if(i == j) edge = {capacity:1};
- row.push(edge != null ? edge.capacity : 0);
- }
- matrix.push(row);
- }
- return matrix;
- };
- // Normalizes a given matrix
- this.normalize = function(matrix) {
- // Find the sum of each column
- var sums = [];
- for(var col=0;col<matrix.length;col++) {
- var sum = 0;
- for(var row=0;row<matrix.length;row++)
- sum += matrix[row][col];
- sums[col] = sum;
- }
- // For every value in the matrix divide by the sum
- for(var col=0;col<matrix.length;col++)
- for(var row=0;row<matrix.length;row++)
- matrix[row][col] = round(matrix[row][col] / sums[col]);
- };
- // Prints the matrix
- this.print = function(matrix) {
- for(var i=0;i<matrix.length;i++) {
- for(var j=0;j<matrix[i].length;j++) {
- document.write((j==0?'':',')+matrix[i][j]);
- }
- document.write('<br>');
- }
- };
- // Take the (power)th power of the matrix effectively multiplying it with
- // itself pow times
- this.matrixExpand = function(matrix, pow) {
- var resultMatrix = [];
- for(var row=0;row<matrix.length;row++) {
- resultMatrix[row] = [];
- for(var col=0;col<matrix.length;col++) {
- var result = 0;
- for(var c=0;c<matrix.length;c++)
- result += matrix[row][c] * matrix[c][col];
- resultMatrix[row][col] = result;
- }
- }
- return resultMatrix;
- };
- // Applies a power of X to each item in the matrix
- this.matrixInflate = function(matrix, pow) {
- for(var row=0;row<matrix.length;row++)
- for(var col=0;col<matrix.length;col++)
- matrix[row][col] = Math.pow(matrix[row][col], pow);
- };
- // Are the two matrices equal?
- this.equals = function(a,b) {
- for(var i=0;i<a.length;i++)
- for(var j=0;j<a[i].length;j++)
- if(b[i] === undefined || b[i][j] === undefined || a[i][j] - b[i][j] > 0.1) return false;
- return true;
- };
- // Girvan–Newman algorithm
- this.getMarkovCluster = function(power, inflation) {
- var lastMatrix = [];
- var currentMatrix = this.getAssociatedMatrix();
- this.print(currentMatrix);
- this.normalize(currentMatrix);
- currentMatrix = this.matrixExpand(currentMatrix, power);
- this.matrixInflate(currentMatrix, inflation);
- this.normalize(currentMatrix);
- var c = 0;
- while(!this.equals(currentMatrix,lastMatrix)) {
- lastMatrix = currentMatrix.slice(0);
- currentMatrix = this.matrixExpand(currentMatrix, power);
- this.matrixInflate(currentMatrix, inflation);
- this.normalize(currentMatrix);
- if(++c > 500) break; //JIC, fiddle fail
- }
- return currentMatrix;
- };
- };
- var g = new Graph();
- g.addNode('a');
- g.addNode('b');
- g.addNode('c');
- g.addNode('d');
- g.addEdge('a','b',1);
- g.addEdge('b','a',1);
- g.addEdge('a','c',1);
- g.addEdge('c','a',1);
- g.addEdge('a','d',1);
- g.addEdge('d','a',1);
- g.addEdge('a','b',1);
- g.addEdge('b','d',1);
- g.addEdge('d','b',1);
- var result = g.getMarkovCluster(2,2);
- g.print(result);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement