/*-
 * Copyright (c) 2009, Alexandre P. Francisco <aplf@ist.utl.pt>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

package rank;

import cern.colt.list.*;
import cern.colt.map.OpenIntDoubleHashMap;
import it.unimi.dsi.logging.*;
import it.unimi.dsi.webgraph.labelling.ArcLabelledNodeIterator.LabelledArcIterator;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/*
 * Heat kernel as described in "Chung, F.: The heat kernel as the pagerank
 * of a graph. Proceedings of the National Academy of Sciences 104(50)
 * (2007) 19735". This implementation is based on an approximation method
 * from "Yang, H., King, I., Lyu, M.R.: Diffusionrank: a possible
 * penicillin for web spamming. In Kraaij, W., de Vries, A.P., Clarke,
 * C.L.A., Fuhr, N., Kando, N., eds.: SIGIR, ACM (2007) 431-438".
 */

public class HeatKernel extends RankMethod {

	private static Logger LOGGER = LoggerFactory.getLogger(HeatKernel.class.getName());

	//final private ProgressLogger pl = new ProgressLogger(LOGGER, ClusterIt.LOGINT);

	public HeatKernel(WeightedImmutableGraph ig, double alpha, int maxIter) {
		super(ig, alpha, maxIter);
	}
	
	public OpenIntDoubleHashMap  computeOneStep(OpenIntDoubleHashMap rankVector) {
		OpenIntDoubleHashMap newRankVector = new OpenIntDoubleHashMap();

		IntArrayList rankIndexList = rankVector.keys();

		//pl.start("Computing new rank vector...");
		//pl.expectedUpdates = rankIndexList.size();
		//pl.itemsName = "nodes";

		for (int k = 0; k < rankIndexList.size(); k++) {
			int i = rankIndexList.get(k);

			LabelledArcIterator successors = ig.successors(i);

			double val_i = rankVector.get(i);
			newRankVector.put(i,
					newRankVector.get(i) + val_i*(1 - alpha/maxIter));

			int j = successors.nextInt();
			while (j != -1) {

				double add_j = val_i * (alpha/maxIter)
					* (Float.intBitsToFloat(successors.label().getInt()) / ig.outweight(i));

				newRankVector.put(j, newRankVector.get(j) + add_j);
				
				j = successors.nextInt();
			}
			//pl.update();
		}
		//pl.done();

		//LOGGER.debug(newRankVector.toString());

		return newRankVector;
	}
}