package edu.claflin.finder.algo.clustering.struct.leading_eigenvector_struct;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

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

// Class made to allow LeadingEigenvectorAlgorithm to be called on disconnected graphs.
// It works by separating the graph into its separate components, treating them
// all as separate graphs by running the leading eigenvector algorithm on each
// graph separately, then agglomerating the results. Realistically speaking
// the algorithm should not be used on disconnected graphs but since
// some of the provided test graphs have disconnected components I decided
// to just add this functionality. If the graph being processed is not
// disconnected, the result will be the same as if running the algorithm
// directly on the graph, so for the intended case results will be the same.

//@author Samuel Perez

public class LeadingEigenvectorCaller {
	private Graph graph;
	private ArrayList<Graph> components;
	private HashMap<Integer, List<Node>> communities = new HashMap<>();
	
	public LeadingEigenvectorCaller(Graph g) {
		this.graph = g;
		
		// retrieve each separate component of the graph
		components = getComponents(graph);
		
		// if there is a single component, run the algorithm normally
		if(components.size() == 1) {
			LeadingEigenvectorAlgorithm leigen = new LeadingEigenvectorAlgorithm(g);
			communities = leigen.getCommunities();
		}
		else {
			int counter = 0;
			int totalCommunities = 0;
			
			for(Graph graph : components) {
				LeadingEigenvectorAlgorithm leigen = new LeadingEigenvectorAlgorithm(graph);
				HashMap<Integer, List<Node>> currCommunities = new HashMap<>();
				currCommunities = leigen.getCommunities();
				
				for(Integer communityLabel : currCommunities.keySet()) {
					communities.put(communityLabel + totalCommunities, currCommunities.get(communityLabel));
					counter += 1;
				}
				
				totalCommunities += counter;
				counter = 0;
			}
		}
		
		int currSize = communities.size();
		
		// check if there are unconnected communities in the result and if there are fix them
		for(int i = 1; i <= currSize; i++) {
			Graph currGraph = graph.getSubGraph(communities.get(i), "");
			ArrayList<Graph> currComponents = getComponents(currGraph);
			
			if(currComponents.size() > 1) {
				communities.put(i, currComponents.get(0).getNodeList());
				
				for(int j = 1; j < currComponents.size(); j++) {
					communities.put(communities.size() + 1, currComponents.get(j).getNodeList());
				}
			}
		}
	}
	
	// returns the separate components of a graph in an ArrayList, if there are no
	// separate components returns an ArrayList with a single element: the entire graph
	private ArrayList<Graph> getComponents(Graph g) {
		// create the adjacency matrix which will be traversed
		int[][] adjMatrix = new int[g.getNodeCount()][g.getNodeCount()];
		
		for(Edge edge: g.getEdgeList()) {
			int sourceIntegerIdentifier = edge.getSource().getIntegerIdentifier();
			int targetIntegerIdentifier = edge.getTarget().getIntegerIdentifier();
			
			adjMatrix[sourceIntegerIdentifier][targetIntegerIdentifier] = 1;
			adjMatrix[targetIntegerIdentifier][sourceIntegerIdentifier] = 1;
		}
		
		int[] visited = new int[g.getNodeCount()];
		int visitedIter = 1;
		
		while(true) {
			int foundEntryPoint = -1;
			
			// find a node which hasn't been visited and visit it
			for(int i = 0; i < visited.length; i++) {
				if(visited[i] == 0) {
					foundEntryPoint = i;
				}
			}
			
			if(foundEntryPoint == -1) {
				break;
			}
			else {
				visited[foundEntryPoint] = visitedIter;
				dfs(adjMatrix, foundEntryPoint, visited, visitedIter);
			}
			
			// update the iteration
			visitedIter += 1;
		}
		
		return getGraphList(visited, g);
	}
	
	private ArrayList<Graph> getGraphList(int[] groupVector, Graph g){
		ArrayList<Graph> results = new ArrayList<>();
		
		boolean moreGroups = true;
		int group = 1;
		
		while(moreGroups){
			moreGroups = false;
			
			List<Node> nodeList = new ArrayList<Node>();
			
			for(int i = 0; i < groupVector.length; i++) {
				if(groupVector[i] == group) {
					nodeList.add(g.getNodeList().get(i));
				}
				
				if(groupVector[i] == group + 1) {
					moreGroups = true;
				}
			}
			
			results.add(g.getSubGraph(nodeList, "Component " + 1 + " of "));
			
			group += 1;
		}
		
		return results;
	}
	
	private void dfs(int[][] matrix, int start, int[] visited, int visitedIter) {
		for(int i = 0; i < matrix.length; i++) {
			if(visited[i] == 0 && matrix[start][i] == 1) {
				visited[i] = visitedIter;
				dfs(matrix, i, visited, visitedIter);
			}
		}
	}
	
	public HashMap<Integer, List<Node>> getCommunities() {
		return this.communities;
	}
	
}
