/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package edu.claflin.finder.algo.clustering;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

import edu.claflin.finder.logic.Edge;
import edu.claflin.finder.logic.Graph;
import edu.claflin.finder.logic.Node;

/**
 *
 * @author Cesar Martin
 */
public class Communities
{
	/**
	 * Map of Community Number to Nodes of the Community.
	 * Some algorithms may rely on these numbers staying
	 * in the same order.
	 */	
	private Map<Integer, List<Node>> list;
	private Graph g;
	private boolean weighted;
	private double m2; // number of 1s in adjacency matrix

	/**
	 * Constructor to initialize 1-Node Communities from a Graph.
	 * @param g the graph
	 * @param weighted finding weighted communities?
	 */
	public Communities(Graph g, boolean weighted)
	{
		this.list = new HashMap<>();
		this.g = g;
		this.weighted = weighted;

		List<Node> nodes = g.getNodeList();
		Collections.sort(nodes);

		// initialize 1-Node Communities
		for (int index = 0; index < nodes.size(); index++)
		{
			list.put(index, new ArrayList<>(Arrays.asList(nodes.get(index))));
		}

		if (weighted)
		{
			m2 = 2 * this.g.getGraphWeight();
		}
		else
		{
			m2 = 2 * this.g.getEdgeCount();
		}
	}

	/**
	 * Constructor to create Communities from existing Community group.
	 * @param list the existing Communities
	 * @param g the graph
	 * @param weighted finding weighted communities?
	 */
	public Communities(Map<Integer, List<Node>> list, Graph g, boolean weighted)
	{
		this.list = list;
		this.g = g;
		this.weighted = weighted;

		if (weighted)
		{
			m2 = 2 * this.g.getGraphWeight();
		}
		else
		{
			m2 = 2 * this.g.getEdgeCount();
		}
	}

	/**
	 * Constructor called by copy(). Copies values without
	 * looping because the looping was done in copy().
	 * 
	 * @param list the Communities
	 * @param g the Graph
	 * @param weighted finding weighted Communities?
	 * @param m2 the m2
	 */
	private Communities(Map<Integer, List<Node>> list, Graph g, boolean weighted, double m2)
	{
		this.list = list;
		this.g = g;
		this.weighted = weighted;
		this.m2 = m2;
	}

	public Communities copy()
	{
		Map<Integer, List<Node>> newlist = new HashMap<>();

		for (Integer i : this.list.keySet())
		{
			newlist.put(i, new ArrayList<>(this.list.get(i)));
		}

		Communities newc = new Communities(newlist, g, weighted, m2);
		return newc;
	}

	public int size()
	{
		return list.size();
	}

	public boolean isWeighted()
	{
		return weighted;
	}

	public double getM2()
	{
		return m2;
	}

	/**
	 * Get Community.
	 * @param key the index of the Community
	 * @return the Community
	 */
	public List<Node> get(Integer key)
	{
		return list.get(key);
	}

	/**
	 * Get Community indices.
	 * @return the Community indices
	 */
	public List<Integer> keys()
	{
		return new ArrayList<>(list.keySet());
	}

	/**
	 * Whether the Community structure contains the given
	 * community index.
	 * @param key the community index
	 * @return true if the Community structure contains the index, false otherwise
	 */
	public boolean containsKey(Integer key)
	{
		return list.containsKey(key);
	}

	/**
	 * Get Community structure as a List of Node Lists.
	 * @return the Communities as lists.
	 */
	public List<List<Node>> getList()
	{
		List<List<Node>> copy = new ArrayList<>();

		for (Integer i : list.keySet())
		{
			copy.add(this.get(i));
		}
		return copy;
	}

	/**
	 * Get the index of the Community the given Node is in.
	 * @param n the node
	 * @return the index of the Community the given Node is in. 
	 */
	public int indexOfNode(Node n)
	{
		for (Integer i : this.list.keySet())
		{
			List<Node> community = this.get(i);
			if (community.contains(n))
			{
				return i;
			}
		}
		return -1;
	}

	/**
	 * Determine if 2 Nodes are in the same Community.
	 *
	 * @param n1 NodeStats 1
	 * @param n2 NodeStats 2
	 *
	 * @return 1 if Nodes in same Community, 0 otherwise
	 */
	public int NodesInSameCommunity(Node n1, Node n2)
	{
		for (Integer i : this.list.keySet())
		{
			List<Node> community = this.get(i);
			if (community.contains(n1) && community.contains(n2))
			{
				return 1;
			}
		}

		return 0;
	}

	/**
	 * Determine whether 2 Communities are connected.
	 * @param c1 Community 1
	 * @param c2 Community 2
	 * @return true if Communities are connected, false otherwise
	 */
	public boolean connectedCommunities(List<Node> c1, List<Node> c2)
	{
		HashSet<Node> adjacent1 = new HashSet<>(); // stores all Nodes that can be reached from c1

		for (Node n : c1)
		{
			adjacent1.addAll(n.getNeighbors());
		}

		// remove destinations of c1 that are not members of c2
		adjacent1.retainAll(c2);

		return !adjacent1.isEmpty(); // any destinations of c1 were members of c2?
	}

	/**
	 * Fraction of edges incident to Nodes in the given Community. 
	 * @param c the Community
	 * @return the fraction of edges incident to Nodes in the Community
	 */
	public double a(List<Node> c)
	{
		if (m2 <= 0)
		{
			return Double.NEGATIVE_INFINITY;
		}

		double sum = 0.0;

		for (Node v : c)
		{
			sum += weighted ? v.getWeight() : v.getDegree();
		}

		return sum / m2;
	}

	/**
	 * Fraction of edges that join vertices in 2 given Communities.
	 * @param c1 Community 1
	 * @param c2 Community 2
	 * @return the fraction of edges that join vertices in the 2 Communities
	 */
	public double e(List<Node> c1, List<Node> c2)
	{
		if (m2 <= 0)
		{
			return Double.NEGATIVE_INFINITY;
		}

		double sum = 0.0;

		// collect the edges from nodes in c1 to nodes in c2
		
		Set<Edge> edge_collection = new HashSet<>();
		
		// c1 edges
		c1.stream().forEach(n ->
		{
			edge_collection.addAll(n.getEdges());
		});
		
		
		// c2 edges
		c2.stream().forEach(n ->
		{
			edge_collection.addAll(n.getEdges());
		});
		
		// filter out edges that go to other Communities
		Set<Edge> edges = edge_collection.stream().filter(e ->
		{
			Node source = e.getSource();
			Node target = e.getTarget();

			return (c1.contains(source) && c2.contains(target)) || (c1.contains(target) && c2.contains(source));
		}).collect(Collectors.toSet());

		for (Edge e : edges)
		{
			// count twice when the communities are the same
			sum += (weighted ? e.getData() : 1) * (c1 == c2 ? 2 : 1);
		}

		return sum / m2;
	}

	/**
	 * The Community Structure Quality Measure used by the algorithms.
	 * It is the sum of the fractions of the deviation edges that join
	 * vertices between each Community to itself from the expected fraction
	 * in a random network.
	 * 
	 * @return the modularity
	 */
	public double modularity()
	{
		double sum = 0.0;

		for (Integer i : this.list.keySet())
		{
			List<Node> community = list.get(i);
			if (!community.isEmpty())
			{
				sum += e(community, community) - Math.pow(a(community), 2);
			}
		}

		return sum;
	}

	/**
	 * Merge community j and i into j
	 *
	 * @param j the community to store the result
	 * @param i the community the offers its Nodes
	 */
	public void mergeCommunities(int j, int i)
	{
		if (this.list.containsKey(j) && this.list.containsKey(i))
		{
			this.list.get(j).addAll(this.list.get(i));
			this.list.remove(i);
		}

	}

	@Override
	public String toString()
	{
		String result = "";

		for (Integer i : this.list.keySet())
		{
			List<Node> community = new ArrayList<>(this.get(i));
			Collections.sort(community);
			if (!community.isEmpty())
			{
				result += i + ": " + community + "\n";
			}
		}
		return result + "Modularity: " + this.modularity();
	}

}
