/*-
 * 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 it.unimi.dsi.logging.ProgressLogger;
import it.unimi.dsi.webgraph.labelling.ArcLabelledNodeIterator.LabelledArcIterator;

//import org.apache.log4j.Logger;

import cern.colt.list.IntArrayList;
import cern.colt.map.OpenIntDoubleHashMap;

/*
 * Random walk as described in "Andersen, R., Lang, K.J.: Communities from
 * seed sets. In Carr, L., Roure, D.D., Iyengar, A., Goble, C.A., Dahlin,
 * M., eds.: WWW, ACM (2006) 223-232".
 */

public class RandomWalk extends RankMethod {
	
	//private static Logger LOGGER = Logger.getLogger(RandomWalk.class.getName());

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

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

		//LOGGER.debug("Selecting non-zero values... " + rankVector.cardinality());

		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) + 0.5*val_i);

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

				double add_j = val_i  * Float.intBitsToFloat(successors.label().getInt()) * 0.5 / ig.outdegree(i);

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

		//LOGGER.debug("Rank vector size change: " +
		//	rankVector.cardinality() + " -> " + newRankVector.cardinality());

		/* LOGGER.debug(newRankVector); */

		return newRankVector;
	}
}