/*
  This file is part of the BJP package.

  BJP package is free software: you can redistribute it and/or modify it
  under the terms of the GNU Lesser General Public License as published by the
  Free Software Foundation, either version 3 of the License, or (at your
  option) any later version.

  BJP package is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with BJP package.  If not, see <http://www.gnu.org/licenses/>.
 */
package util.math;


import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.jgrapht.GraphPath;
import org.jgrapht.alg.BronKerboschCliqueFinder;
import org.jgrapht.alg.CliqueMinimalSeparatorDecomposition;
import org.jgrapht.alg.ConnectivityInspector;
import org.jgrapht.alg.FloydWarshallShortestPaths;
import org.jgrapht.alg.StoerWagnerMinimumCut;
import org.jgrapht.alg.util.VertexDegreeComparator;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleGraph;
import org.jgrapht.graph.UndirectedSubgraph;

import rep.UndirectedGraph;

/**
 * Compiles a series of methods to use the JGRAPHT library for graphs manipulation
 *
 */
public class JGraphtUtils {

	/**
	 * Transforms from the UndirectedGraph representation of this package to the one used in JGRAPHT
	 * @param g1 The graph to transform
	 * @return The graph transformed
	 */
	public static SimpleGraph<String, DefaultEdge> getJGraphTSimpleGraph(
			UndirectedGraph g1) {
		int n = g1.getNumberOfNodes();
		SimpleGraph<String, DefaultEdge> g2 = new SimpleGraph<String, DefaultEdge>(
				DefaultEdge.class);
		for (int i = 0; i < n; ++i) {
			g2.addVertex("" + i);
		}
		for (int i = 0; i < n; ++i) {
			for (int j = i; j < n; ++j) {
				if (g1.existEdge(i, j)) {
					g2.addEdge("" + i, "" + j);
				}
			}
		}
		return g2;
	}
	
	/**
	 * Returns a graph weighted by its degredd
	 * @param g1 The graph to explore
	 * @return A graph weighted by its degredd
	 */
	public static SimpleGraph<String, DefaultWeightedEdge> getGraphWeightedByDegree(
			UndirectedGraph g1) {
		int n = g1.getNumberOfNodes();
		SimpleGraph<String, DefaultWeightedEdge> g2 = new SimpleGraph<String, DefaultWeightedEdge>(
				DefaultWeightedEdge.class);
		for (int i = 0; i < n; ++i) {
			g2.addVertex("" + i);
		}
		for (int i = 0; i < n; ++i) {
			for (int j = i; j < n; ++j) {
				if (g1.existEdge(i, j)) {
					g2.addEdge("" + i, "" + j);
				}
			}
		}
		
		for(DefaultWeightedEdge e: g2.edgeSet()){
			int degreeofSource = g2.degreeOf(g2.getEdgeSource(e));
			int degreeofTarget = g2.degreeOf(g2.getEdgeTarget(e));
			g2.setEdgeWeight(e, degreeofSource+degreeofTarget);
		}
		return g2;
	}

	/**
	 * Returns a boolean value indicating if a graph is chordal
	 * @param g The graph to explore
	 * @return A boolean value indicating if a graph is chordal
	 */
	public static boolean isChordal(UndirectedGraph g) {
		CliqueMinimalSeparatorDecomposition<String, DefaultEdge> cliqueMinimalSeparatorDecomposition = new CliqueMinimalSeparatorDecomposition<String, DefaultEdge>(
				getJGraphTSimpleGraph(g));
		return cliqueMinimalSeparatorDecomposition.isChordal();
	}
	

	/**
	 * Returns all the maximal cliques of a graph
	 * @param g The graph to explore
	 * @return All the maximal cliques of a graph
	 */
	public static Collection<java.util.Set<String>> getAllMaximalCliques(
			UndirectedGraph g) {
		BronKerboschCliqueFinder<String, DefaultEdge> finder = new BronKerboschCliqueFinder<String, DefaultEdge>(
				getJGraphTSimpleGraph(g));
		return finder.getAllMaximalCliques();
	}

	/**
	 * Sorts the nodes of a graph by its degree in ascending order
	 * @param g1 The graph to explore
	 * @return An array with the nodes of a graph sorted by its degree in ascending order
	 */
	public static String[] sortNodesByDegreeInAscendingOrder(UndirectedGraph g1) {
		int n= g1.getNumberOfNodes();
		
		org.jgrapht.UndirectedGraph<String, DefaultEdge> sg = new UndirectedSubgraph<String, DefaultEdge>(getJGraphTSimpleGraph(g1), null, null);
		String[] sortedNodes = new String[n];
		sg.vertexSet().toArray(sortedNodes);

		VertexDegreeComparator<String,DefaultEdge> comp = new VertexDegreeComparator<String,DefaultEdge>(sg, true);
		Arrays.sort(sortedNodes, comp);	
		
		return sortedNodes;
	}
	
	/**
	 * Returns the connected sets of a graph
	 * @param g The graph to explore
	 * @return The connected sets of a graph
	 */
	public static List<Set<String>> getConnectedSets(UndirectedGraph g) {
		SimpleGraph<String, DefaultEdge> graph = getJGraphTSimpleGraph(g);
		ConnectivityInspector<String, DefaultEdge> ci = new ConnectivityInspector<String, DefaultEdge>(graph);		
		return ci.connectedSets();
	}
	
	/**
	 * Returns the best cut of a graph
	 * @param graph The graph to explore
	 * @return The best cut of a graph
	 */
	public static Set<String> bestCut(SimpleGraph<String, DefaultWeightedEdge> graph ){
		StoerWagnerMinimumCut<String, DefaultWeightedEdge> swmc = new StoerWagnerMinimumCut<String, DefaultWeightedEdge>(graph);
		return swmc.minCut();
	}
	
	/**
	 * Returns a boolean value indicating if a path exists between to nodes in a graph
	 * @param x The first node
	 * @param y The second node
	 * @param g The graph to explore
	 * @return A boolean value indicating if a path exists between to nodes in a graph
	 */
	public static boolean pathExist(int x, int y, UndirectedGraph g){
		SimpleGraph<String, DefaultEdge> graph = getJGraphTSimpleGraph(g);
		 ConnectivityInspector<String, DefaultEdge> ci = new ConnectivityInspector<String, DefaultEdge>(graph);
		 return ci.pathExists(""+x, ""+y);
	}

	/**
	 * Returns the shortest path that exists between to nodes in a graph
	 * @param x The first node
	 * @param y The second node
	 * @param g The graph to explore
	 * @return The shortest path that exists between to nodes in a graph
	 */
	public static GraphPath<String, DefaultEdge> shortestPath(int x, int y, UndirectedGraph g){
		SimpleGraph<String, DefaultEdge> graph = getJGraphTSimpleGraph(g);
		FloydWarshallShortestPaths<String, DefaultEdge> fwsp = new FloydWarshallShortestPaths<String,DefaultEdge>(graph);
		GraphPath<String, DefaultEdge> shortestPath = fwsp.getShortestPath(""+x,""+y); 
		return shortestPath;
	}
	
	/**
	 * Returns all the shortest path that exists between to nodes in a graph using the Floy Warshall algorithm
	 * @param g The graph to explore
	 * @return All the shortest path that exists between to nodes in a graph using the Floy Warshall algorithm
	 */
	public static Collection<GraphPath<String, DefaultEdge>> shortestPaths(UndirectedGraph g){
		SimpleGraph<String, DefaultEdge> graph = getJGraphTSimpleGraph(g);
		FloydWarshallShortestPaths<String, DefaultEdge> fwsp = new FloydWarshallShortestPaths<String,DefaultEdge>(graph);
		Collection<GraphPath<String, DefaultEdge>> shortestPaths = fwsp.getShortestPaths(); 
		return shortestPaths;
	}
	
	/**
	 * Finds a bridge in a graph 
	 * @param graph The graph to explore
	 * @return A bridge in a graph
	 */
	public static <V,E>E findBridge(SimpleGraph<V,E> graph){
		  @SuppressWarnings("unchecked") SimpleGraph<V,E> gc=(SimpleGraph<V,E>)graph.clone();
		  int size=new ConnectivityInspector<V,E>(graph).connectedSets().size();
		  for (  E e : graph.edgeSet()) {
		    gc.removeEdge(e);
		    
		    int nsize=new ConnectivityInspector<V,E>(gc).connectedSets().size();
		    if (nsize > size)     return e;
		    V source=graph.getEdgeSource(e);
		    V target=graph.getEdgeTarget(e);
		    gc.addEdge(source,target);
		  }
		  return null;
	}
	
	
	/**
	 * Finds all bridges of a graph 
	 * @param graph The graph to explore 
	 * @return All bridges of a graph
	 */
	public static <V,E>Set<E> findAllBridges(SimpleGraph<V,E> graph){
		  Set<E> bridges=new HashSet<E>();
		  @SuppressWarnings("unchecked") SimpleGraph<V,E> gc=(SimpleGraph<V,E>)graph.clone();
		  int size=new ConnectivityInspector<V,E>(graph).connectedSets().size();
		  for (  E e : graph.edgeSet()) {
		    gc.removeEdge(e);
		    int nsize=new ConnectivityInspector<V,E>(gc).connectedSets().size();
		    if (nsize > size)     bridges.add(e);
		    V source=graph.getEdgeSource(e);
		    V target=graph.getEdgeTarget(e);
		    gc.addEdge(source,target);
		  }
		  return bridges;
		}
	
	

}
