package comparison.kernel.graph;

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

import algorithm.graph.isomorphism.labelrefinement.VertexLabelConverter;
import algorithm.graph.isomorphism.labelrefinement.WeisfeilerLehmanRefiner;
import comparison.kernel.CompositeKernel;
import comparison.kernel.ExplicitMappingKernel;
import comparison.kernel.Kernel;
import concepts.TransformationTools;
import datastructure.FeatureVector;
import graph.LGraph;

/**
 * Implementation of Weisfeiler-Lehman graph kernels depending on an arbitrary
 * base kernel (Shervashidze, 2011). This class computes a sequence of graphs
 * with refined vertex labels for both input graphs and compares the i-th graph
 * in the first sequence with the i-th graph in the second sequence by the base 
 * kernel, where 0 <= i <= sequenceSize.
 * This class supports 1:1 kernel computation as well as explicit mapping into 
 * feature space for fast n:n computation if the base kernel supports explicit
 * mapping.
 * 
 * @see WeisfeilerLehmanShortestPathKernel
 * 
 * @author kriege
 * @param V vertex label type
 * @param E edge label type
 * @param F feature type of explicit mapping
 */
//TODO make this a general class for all types of vertex refinements
public class WeisfeilerLehmanKernel<V,E,F>	implements 
	CompositeKernel<LGraph<V, E>>, 
	ExplicitMappingKernel<LGraph<V, E>, F> 
{

	protected int height;
	protected Kernel<LGraph<Integer, E>> baseKernel;
	
	/**
	 * Creates a new instance of a Weisfeiler-Lehmann kernel.
	 * 
	 * @param height the number of WL refinement steps, in total the number of graphs 
	 * in the computed WL sequence is height+1 
	 * @param baseKernel kernel applied to the individual graphs of the WL sequence
	 */
	public WeisfeilerLehmanKernel(int height, Kernel<LGraph<Integer, E>> baseKernel) {
		this.height = height;
		this.baseKernel = baseKernel;
	}
	
	/**
	 * Returns a separate result for each graph of the WL graph sequence.
	 */
	public double[] computeComposition(LGraph<V, E> g1, LGraph<V, E> g2) {
		double[] d = new double[height+1];

		// do initial label refinement
		VertexLabelConverter<E> vlc = new VertexLabelConverter<E>();
		LGraph<Integer, E> slg1 = vlc.refineGraph(g1);
		LGraph<Integer, E> slg2 = vlc.refineGraph(g2);
		vlc.clearLabelMap();
		
		// first iteration
		d[0] = baseKernel.compute(slg1, slg2);

		// additional iterations
		WeisfeilerLehmanRefiner<E> wlr = new WeisfeilerLehmanRefiner<E>();
		for (int i=1; i<=height; i++) {
			slg1 = vlc.refineGraph(wlr.refineGraph(slg1));
			slg2 = vlc.refineGraph(wlr.refineGraph(slg2));
			vlc.clearLabelMap();
			d[i] = baseKernel.compute(slg1, slg2);
		}
		
		return d;
	}
	
	@Override
	public FeatureVector<F> getFeatureVector(LGraph<V, E> t) throws IllegalStateException {
		throw new UnsupportedOperationException("No canonical color map implemented, feature vectors "
				+ "are generated by multiple calls are incompatible!");
	}
	
	/**
	 * {@inheritDoc}
	 * 
	 * Note: The feature vectors generated by two separate calls to this method are incompatible and
	 * should not be compared in any way.
	 * 
	 * @throws IllegalStateException if the underlying base kernel does not allow explicit mapping 
	 */
	@SuppressWarnings("unchecked")
	public ArrayList<FeatureVector<F>> getFeatureVectors(List<? extends LGraph<V, E>> graphs) {
		ExplicitMappingKernel<LGraph<Integer, E>, F> baseKernel = 
			(ExplicitMappingKernel<LGraph<Integer, E>, F>)this.baseKernel;
		
		int n = graphs.size();
		VertexLabelConverter<E> vlc = new VertexLabelConverter<E>();

		// assign integer label
		// using the same VertexLabelConverter assures that new labels (from refinement) will 
		// be assigned higher integer values, such that labels of different iterations can be
		// distinguished
		ArrayList<LGraph<Integer, E>> lgs = TransformationTools.transformAll(vlc, graphs);
		vlc.clearLabelMap(); 
		
		// create initial feature vectors
		ArrayList<FeatureVector<F>> result = baseKernel.getFeatureVectors(lgs);
		
		WeisfeilerLehmanRefiner<E> wlr = new WeisfeilerLehmanRefiner<E>();
		for (int i=1; i<=height; i++) {
			// refinement
			ArrayList<LGraph<String, E>> refLgs = TransformationTools.transformAll(wlr, lgs);
			// compression
			lgs = TransformationTools.transformAll(vlc, refLgs);
			vlc.clearLabelMap();
			
			// compute new feature vectors and combine with the old one
			ArrayList<FeatureVector<F>> r2 = baseKernel.getFeatureVectors(lgs);
			for (int j=0; j<n; j++) {
				result.get(j).add(r2.get(j));
			}
		}
		
		return result;
	}
	
	public int getHeight() {
		return height;
	}
	
	public void setHeight(int height) {
		this.height = height;
	}

	/**
	 * {@inheritDoc}
	 */
	public int getComponentCount() {
		return height+1;
	}
	
	@Override
	public String toString() {
		return "Weisfeiler-Lehman kernel+\n"+
			"\theight="+height+"\n"+
			"\tbaseKernel="+String.valueOf(baseKernel);
	}
	
	public String getID() {
		return "WL_"+height+"_"+baseKernel.getID();
	}

}
