package edu.claflin.finder.algo.clustering;

import static edu.claflin.finder.Global.getLogger;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;

import edu.claflin.finder.algo.ArgumentsBundle;
import edu.claflin.finder.algo.clustering.struct.girvan_newman_struct.BetweennessCentrality;
import edu.claflin.finder.log.LogLevel;
import edu.claflin.finder.logic.Edge;
import edu.claflin.finder.logic.Graph;
import edu.claflin.finder.logic.Node;

/**
 * Girvan-Newman Algorithm for Community Detection. Based on python's igraph
 * library and JUNG's graph library.
 * 
 * @see <a href="https://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm">Wikipedia Summary</a>
 * @see <a href="https://www.pnas.org/content/99/12/7821">Original Paper</a>
 * @see <a href="https://github.com/igraph/igraph/blob/master/src/community/edge_betweenness.c">Original igraph implementation</a>
 * @see <a href="https://github.com/jrtom/jung/blob/master/jung-algorithms/src/main/java/edu/uci/ics/jung/algorithms/cluster/EdgeBetweennessClusterer.java">Original JUNG implementation</a>
 * @author Cesar Martin
 *
 */
public class GirvanNewman extends ClusteringAlgorithm
{

	public GirvanNewman(ArgumentsBundle args)
	{
		super(args);

		if (getLogger() != null)
		{
			getLogger().logInfo(LogLevel.DEBUG, "Edge Betweenness with Girvan Newman algorithm initialized.");
		}

	}

	@Override
	public String toString()
	{
		return "Girvan Newman Algorithm";
	}

	/**
	 * Performs Edge Betweenness community detection with Girvan-Newman algorithm a
	 * given Graph, returning the clustering with the maximum modularity.
	 *
	 * @param graph the Graph to perform FastGreedy on
	 * @return the list of Graphs representing the clustering with the maximum
	 *         modularity
	 */
	@Override
	public ArrayList<Graph> process(Graph graph)
	{
		if (getLogger() != null)
		{
			getLogger().logAlgo(LogLevel.NORMAL,
					"EdgeBetweenness: Searching Graph: " + graph.getName() + "\nRunning Algorithm");
		}

		if (graph.getNodeCount() < 1)
		{
			return new ArrayList<Graph>();
		}

		Graph communityGraph = graph.uniqueCopy(); // graph to get communities from
		Graph algoGraph = graph.uniqueCopy(); // graph modified by the algorithm

		Communities maxCommunities = null;
		double maxModularity = Double.NEGATIVE_INFINITY;
		int clusterCount = -1;

		// remove edges with maximum edge betweenness until there are no edges left
		setProgress(0D);
		while (algoGraph.getEdgeCount() > 0)
		{
			BetweennessCentrality bc = new BetweennessCentrality(algoGraph, isWeighted());

			Edge to_remove = null;
			double score = 0;
			for (Edge e : algoGraph.getEdgeList()) // get edge with maximum score
			{
				if (bc.getEdgeScore(e) > score)
				{
					to_remove = e;
					score = bc.getEdgeScore(e);
				}
			}

			algoGraph.removeEdge(to_remove);

			// find connected components after removing the edge
			Set<Set<Node>> comNodes = this.getComponents(algoGraph.getNodeList());

			// build communities and store them if they have maximum modularity
			if (comNodes.size() != clusterCount)
			{
				Map<Integer, List<Node>> map = new HashMap<>();

				// store nodes in the map
				int index = 0;
				for (Set<Node> nodes : comNodes)
				{
					Set<Node> cNodes = nodes.stream()
							.map(nAlgo -> communityGraph.getNode(nAlgo.getIdentifier())).collect(Collectors.toSet());
					map.put(index, new ArrayList<Node>(cNodes));
					index++;
				}

				Communities cms = new Communities(map, communityGraph, isWeighted()); // build new communities

				double modularity = cms.modularity();
				if (modularity > maxModularity) // check if new maximum modularity
				{
					maxModularity = modularity;
					maxCommunities = cms;
				}

				clusterCount = comNodes.size();
			}

			setProgress(1D * (((double) graph.getEdgeCount() - algoGraph.getEdgeCount()) / graph.getEdgeCount()));
		}

		if (getLogger() != null)
		{
			getLogger().logAlgo(LogLevel.NORMAL,
					"EdgeBetweenness: Algorithm done. Getting Clustering with Maximum Modularity");
		}

		ArrayList<Graph> communities = new ArrayList<>();

		// build communities with maximum modularity
		if (maxCommunities != null)
		{
			communities = this.buildCommunityGraphs(maxCommunities.getList(), graph, "Edge Betweenness");
		}

		return cull(communities);
	}
	
	/**
	 * Extracts the weak components from a graph.
	 * 
	 * @param nList the list of Nodes of the Graph
	 * @return the list of weak components
	 */
	private Set<Set<Node>> getComponents(List<Node> nList)
	{

		Set<Set<Node>> clusterSet = new HashSet<Set<Node>>();

		HashSet<Node> unvisitedVertices = new HashSet<Node>(nList);

		while (!unvisitedVertices.isEmpty())
		{
			Set<Node> cluster = new HashSet<Node>();
			Node root = unvisitedVertices.iterator().next();
			unvisitedVertices.remove(root);
			cluster.add(root);

			Queue<Node> queue = new LinkedList<Node>();
			queue.add(root);

			while (!queue.isEmpty())
			{
				Node currentVertex = queue.remove();
				List<Node> neighbors = currentVertex.getNeighbors();

				for (Node neighbor : neighbors)
				{
					if (unvisitedVertices.contains(neighbor))
					{
						queue.add(neighbor);
						unvisitedVertices.remove(neighbor);
						cluster.add(neighbor);
					}
				}
			}
			clusterSet.add(cluster);
		}
		return clusterSet;
	}

}
