/*
Author: Corneliu S. (github.com/upphiminn)

This is a javascript implementation of the Louvain
community detection algorithm (http://arxiv.org/abs/0803.0476)
Based on https://bitbucket.org/taynaud/python-louvain/overview

*/
(function(){
	jLouvain = function(){
		//Constants
		var __PASS_MAX = -1
		var __MIN 	 = 0.0000001

		//Local vars
		var original_graph_nodes;
		var original_graph_edges;
		var original_graph = {};
		var partition_init;

		//Helpers
		function make_set(array){
			var set = {};
			array.forEach(function(d,i){
				set[d] = true;
			});
			return Object.keys(set);
		};

		function obj_values(obj){
			 var vals = [];
			 for( var key in obj ) {
			     if ( obj.hasOwnProperty(key) ) {
			         vals.push(obj[key]);
			     }
			 }
			 return vals;
		};

		function get_degree_for_node(graph, node){
			var neighbours = graph._assoc_mat[node] ? Object.keys(graph._assoc_mat[node]) : [];
			var weight = 0;
			neighbours.forEach(function(neighbour,i){
				var value = graph._assoc_mat[node][neighbour] || 1;
				if(node == neighbour)
					value *= 2;
				weight += value;
			});
			return weight;
		};

		function get_neighbours_of_node(graph, node){
			if(typeof graph._assoc_mat[node] == 'undefined')
				return [];

			var neighbours = Object.keys(graph._assoc_mat[node]);
			return neighbours;
		}

		function get_edge_weight(graph, node1, node2){
			return graph._assoc_mat[node1] ? graph._assoc_mat[node1][node2] : undefined;
		}

		function get_graph_size(graph){
			var size = 0;
			graph.edges.forEach(function(edge){
				size += edge.weight;
			});
			return size;
		}

		function add_edge_to_graph(graph, edge){
			update_assoc_mat(graph, edge);

			var edge_index = graph.edges.map(function(d){
				return d.source+'_'+d.target;
			}).indexOf(edge.source+'_'+edge.target);

			if(edge_index != -1)
				graph.edges[edge_index].weight = edge.weight;
			else
				graph.edges.push(edge);
		}

		function make_assoc_mat(edge_list){
			var mat = {};
			edge_list.forEach(function(edge, i){
				mat[edge.source] = mat[edge.source] || {};
				mat[edge.source][edge.target] = edge.weight;
				mat[edge.target] = mat[edge.target] || {};
				mat[edge.target][edge.source] = edge.weight;
			});

			return mat;
		}

		function update_assoc_mat(graph, edge){
			graph._assoc_mat[edge.source] = graph._assoc_mat[edge.source] || {};
			graph._assoc_mat[edge.source][edge.target] = edge.weight;
			graph._assoc_mat[edge.target] = graph._assoc_mat[edge.target] || {};
			graph._assoc_mat[edge.target][edge.source] = edge.weight;
		}

		function clone(obj){
		    if(obj == null || typeof(obj) != 'object')
		        return obj;

		    var temp = obj.constructor();

		    for(var key in obj)
		        temp[key] = clone(obj[key]);
		    return temp;
		}

		//Core-Algorithm Related
		function init_status(graph, status, part){
			status['nodes_to_com'] = {};
			status['total_weight'] = 0;
			status['internals'] = {};
			status['degrees'] = {};
			status['gdegrees'] = {};
			status['loops'] = {};
			status['total_weight'] = get_graph_size(graph);

			if(typeof part == 'undefined'){
				graph.nodes.forEach(function(node,i){
					status.nodes_to_com[node] = i;
					var deg = get_degree_for_node(graph, node);
					if (deg < 0)
						throw 'Bad graph type, use positive weights!';
					status.degrees[i] = deg;
					status.gdegrees[node] = deg;
					status.loops[node] = get_edge_weight(graph, node, node) || 0;
					status.internals[i] = status.loops[node];
				});
			}else{
				graph.nodes.forEach(function(node,i){
					var com = part[node];
					status.nodes_to_com[node] = com;
					var deg = get_degree_for_node(graph, node);
					status.degrees[com] = (status.degrees[com] || 0) + deg;
					status.gdegrees[node] = deg;
					var inc = 0.0;

					var neighbours  = get_neighbours_of_node(graph, node);
					neighbours.forEach(function(neighbour, i){
						var weight = graph._assoc_mat[node][neighbour];
						if (weight <= 0){
							throw "Bad graph type, use positive weights";
						}

						if(part[neighbour] == com){
							if (neighbour == node){
								inc += weight;
							}else{
								inc += weight/2.0;
							}
						}
					});
					status.internals[com] = (status.internals[com] || 0) + inc;
				});
			}
		}

		function __modularity(status){
			var links = status.total_weight;
			var result = 0.0;
			var communities = make_set(obj_values(status.nodes_to_com));

			communities.forEach(function(com,i){
				var in_degree = status.internals[com] || 0 ;
				var degree = status.degrees[com] || 0 ;
				if(links > 0){
					result = result + in_degree / links - Math.pow((degree / (2.0*links)), 2);
				}
			});
			return result;
		}

		function __neighcom(node, graph, status){
			// compute the communities in the neighb. of the node, with the graph given by
			// node_to_com

			var weights = {};
			var neighboorhood = get_neighbours_of_node(graph, node);//make iterable;

			neighboorhood.forEach(function(neighbour, i){
				if(neighbour != node){
					var weight = graph._assoc_mat[node][neighbour] || 1; 
					var neighbourcom = status.nodes_to_com[neighbour];
					weights[neighbourcom] = (weights[neighbourcom] || 0) + weight;
				}	
			});

			return weights;
		}

		function __insert(node, com, weight, status){
			//insert node into com and modify status
			status.nodes_to_com[node] = +com;
			status.degrees[com] = (status.degrees[com] || 0) + (status.gdegrees[node]||0);
			status.internals[com] = (status.internals[com] || 0) + weight + (status.loops[node]||0);
		}

		function __remove(node, com, weight, status){
			//remove node from com and modify status
			status.degrees[com] = ((status.degrees[com] || 0) - (status.gdegrees[node] || 0));
			status.internals[com] = ((status.internals[com] || 0) - weight -(status.loops[node] ||0));
			status.nodes_to_com[node] = -1;
		}

		function __renumber(dict){
			var count = 0;
			var ret = clone(dict); //deep copy :)
			var new_values = {};
			var dict_keys = Object.keys(dict);
			dict_keys.forEach(function(key){
				var value = dict[key];
				var new_value =  typeof new_values[value] =='undefined' ? -1 : new_values[value];
				if(new_value == -1){
					new_values[value] = count;
					new_value = count;
					count = count + 1;
				}
				ret[key] = new_value;
			});
			return ret;
		}

		function __one_level(graph, status){
			//Compute one level of the Communities Dendogram.
			var modif = true,
				nb_pass_done = 0,
				cur_mod = __modularity(status),
				new_mod = cur_mod;

			while (modif && nb_pass_done != __PASS_MAX){
				cur_mod = new_mod;
				modif = false;
				nb_pass_done += 1

				graph.nodes.forEach(function(node,i){
					var com_node = status.nodes_to_com[node];
					var degc_totw = (status.gdegrees[node] || 0) / (status.total_weight * 2.0);
					var neigh_communities = __neighcom(node, graph, status);
					__remove(node, com_node, (neigh_communities[com_node] || 0.0), status);
					var best_com = com_node;
					var best_increase = 0;
					var neigh_communities_entries = Object.keys(neigh_communities);//make iterable;

					neigh_communities_entries.forEach(function(com,i){
						var incr = neigh_communities[com] - (status.degrees[com] || 0.0) * degc_totw;
						if (incr > best_increase){
							best_increase = incr;
							best_com = com;
						}
					});

					__insert(node, best_com, neigh_communities[best_com] || 0, status);

					if(best_com != com_node)
						modif = true;
				});
				new_mod = __modularity(status);
				if(new_mod - cur_mod < __MIN)
					break;
			}
		}

		function induced_graph(partition, graph){
			var ret = {nodes:[], edges:[], _assoc_mat: {}};
			var w_prec, weight;
			//add nodes from partition values
			var partition_values = obj_values(partition);
			ret.nodes = ret.nodes.concat(make_set(partition_values)); //make set
			graph.edges.forEach(function(edge,i){
				weight = edge.weight || 1;
				var com1 = partition[edge.source];
				var com2 = partition[edge.target];
				w_prec = (get_edge_weight(ret, com1, com2) || 0); 
				var new_weight = (w_prec + weight);
				add_edge_to_graph(ret, {'source': com1, 'target': com2, 'weight': new_weight});
			});
			return ret;
		}

		function partition_at_level(dendogram, level){
			var partition = clone(dendogram[0]);
			for(var i = 1; i < level + 1; i++ )
				Object.keys(partition).forEach(function(key,j){
					var node = key;
					var com  = partition[key];
					partition[node] = dendogram[i][com];
				});
			return partition;
		}


		function generate_dendogram(graph, part_init){

			if(graph.edges.length == 0){
				var part = {};
				graph.nodes.forEach(function(node,i){
					part[node] = node;
				});
				return part;
			}
			var status = {};

			init_status(original_graph, status, part_init);
			var mod = __modularity(status);
			var status_list = [];
			__one_level(original_graph, status);
			var new_mod = __modularity(status);
			var partition = __renumber(status.nodes_to_com);
			status_list.push(partition);
			mod = new_mod;
			var current_graph = induced_graph(partition, original_graph);
			init_status(current_graph, status);

			while (true){
				__one_level(current_graph, status);
				new_mod = __modularity(status);
				if(new_mod - mod < __MIN)
					break;

				partition = __renumber(status.nodes_to_com);
				status_list.push(partition); 

				mod = new_mod;
				current_graph = induced_graph(partition, current_graph);
				init_status(current_graph, status);
			}

			return status_list; 
		}

		var core = function(){
			var status = {};
			var dendogram = generate_dendogram(original_graph, partition_init);
			return partition_at_level(dendogram, dendogram.length - 1);
		};

		core.nodes = function(nds){
			if(arguments.length > 0){
				original_graph_nodes = nds;
			}
			return core;
		};

		core.edges = function(edgs){
			if(typeof original_graph_nodes == 'undefined')
				throw 'Please provide the graph nodes first!';

			if(arguments.length > 0){
				original_graph_edges = edgs;
				var assoc_mat = make_assoc_mat(edgs);
				original_graph = { 'nodes': original_graph_nodes,
						  		   'edges': original_graph_edges,
						  		   '_assoc_mat': assoc_mat };
			}
			return core;

		};

		core.partition_init = function(prttn){
			if(arguments.length > 0){
				partition_init = prttn;
			}
			return core;
		};

		return core;
	}
})();