/*
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;
  };
})();