/*
 * Created on Jul 14, 2007
 *
 * Copyright (c) 2007, the JUNG Project and the Regents of the University 
 * of California
 * All rights reserved.
 *
 * This software is open-source under the BSD license; see either
 * "license.txt" or
 * http://jung.sourceforge.net/license.txt for a description.
 */
package edu.uci.ics.jung.algorithms.scoring;

import org.apache.commons.collections15.Transformer;
import org.apache.commons.collections15.functors.ConstantTransformer;

import edu.uci.ics.jung.graph.Hypergraph;

/**
 * A generalization of HITS that permits non-uniformly-distributed random jumps.
 * The 'vertex_priors' (that is, prior probabilities for each vertex) may be
 * thought of as the fraction of the total 'potential' (hub or authority score)
 * that is assigned to that vertex out of the portion that is assigned according
 * to random jumps.
 * 
 * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
 */
public class HITSWithPriors<V, E> 
	extends AbstractIterativeScorerWithPriors<V,E,HITS.Scores>
{
    /**
     * The sum of the potential, at each step, associated with vertices with no outedges (authority)
     * or no inedges (hub).
     */
    protected HITS.Scores disappearing_potential;

    /**
     * Creates an instance for the specified graph, edge weights, vertex prior probabilities,
     * and random jump probability (alpha).
     * @param g the input graph
     * @param edge_weights the edge weights 
     * @param vertex_priors the prior probability for each vertex
     * @param alpha the probability of a random jump at each step
     */
    public HITSWithPriors(Hypergraph<V,E> g,
            Transformer<E, ? extends Number> edge_weights,
            Transformer<V, HITS.Scores> vertex_priors, double alpha)
    {
        super(g, edge_weights, vertex_priors, alpha);
        disappearing_potential = new HITS.Scores(0,0);
    }

    /**
     * Creates an instance for the specified graph, vertex priors, and random
     * jump probability (alpha).  The edge weights default to 1.0.
     * @param g the input graph
     * @param vertex_priors the prior probability for each vertex
     * @param alpha the probability of a random jump at each step
     */
    @SuppressWarnings("unchecked")
    public HITSWithPriors(Hypergraph<V,E> g, 
          Transformer<V, HITS.Scores> vertex_priors, double alpha)
    {
    	super(g, new ConstantTransformer(1.0), vertex_priors, alpha);
        disappearing_potential = new HITS.Scores(0,0);
    }

    /**
     * Updates the value for this vertex.
     */
    @Override
    protected double update(V v)
    {
        collectDisappearingPotential(v);
        
        double v_auth = 0;
        for (E e : graph.getInEdges(v))
        {
        	int incident_count = getAdjustedIncidentCount(e);
        	for (V w : graph.getIncidentVertices(e)) 
        	{
        		if (!w.equals(v) || hyperedges_are_self_loops) 
        			v_auth += (getCurrentValue(w).hub * 
        					getEdgeWeight(w,e).doubleValue() / incident_count);
        	}
//            V w = graph.getOpposite(v, e);
//            auth += (getCurrentValue(w).hub * getEdgeWeight(w, e).doubleValue());
        }
        
        double v_hub = 0;
        for (E e : graph.getOutEdges(v))
        {
        	int incident_count = getAdjustedIncidentCount(e);
        	for (V w : graph.getIncidentVertices(e)) 
        	{
        		if (!w.equals(v) || hyperedges_are_self_loops) 
        			v_hub += (getCurrentValue(w).authority * 
        					getEdgeWeight(w,e).doubleValue() / incident_count);
        	}
//            V x = graph.getOpposite(v,e);
//            hub += (getCurrentValue(x).authority * getEdgeWeight(x, e).doubleValue()); 
        }
        
        // modify total_input according to alpha
        if (alpha > 0) 
        {
	        v_auth = v_auth * (1 - alpha) + getVertexPrior(v).authority * alpha;
	        v_hub = v_hub * (1 - alpha) + getVertexPrior(v).hub * alpha;
        }
        setOutputValue(v, new HITS.Scores(v_hub, v_auth));

        return Math.max(Math.abs(getCurrentValue(v).hub - v_hub), 
                        Math.abs(getCurrentValue(v).authority - v_auth));
    }

    /**
     * Code which is executed after each step.  In this case, deals with the
     * 'disappearing potential', normalizes the scores, and then calls
     * <code>super.afterStep()</code>.
     * @see #collectDisappearingPotential(Object)
     */
    @Override
    protected void afterStep()
    {
        if (disappearing_potential.hub > 0 || disappearing_potential.authority > 0)
        {
            for (V v : graph.getVertices())
            {
                double new_hub = getOutputValue(v).hub + 
                    (1 - alpha) * (disappearing_potential.hub * getVertexPrior(v).hub);
                double new_auth = getOutputValue(v).authority + 
                    (1 - alpha) * (disappearing_potential.authority * getVertexPrior(v).authority);
                setOutputValue(v, new HITS.Scores(new_hub, new_auth));
            }
            disappearing_potential.hub = 0;
            disappearing_potential.authority = 0;
        }
        
    	normalizeScores();
    	
        super.afterStep();
    }

	/**
	 * Normalizes scores so that sum of their squares = 1.
	 * This method may be overridden so as to yield different 
	 * normalizations.
	 */
	protected void normalizeScores() {
    	double hub_ssum = 0;
    	double auth_ssum = 0;
    	for (V v : graph.getVertices())
    	{
    		double hub_val = getOutputValue(v).hub;
    		double auth_val = getOutputValue(v).authority;
    		hub_ssum += (hub_val * hub_val);
    		auth_ssum += (auth_val * auth_val);
    	}

    	hub_ssum = Math.sqrt(hub_ssum);
    	auth_ssum = Math.sqrt(auth_ssum);
    	
    	for (V v : graph.getVertices())
    	{
    		HITS.Scores values = getOutputValue(v);
    		setOutputValue(v, new HITS.Scores(
    				values.hub / hub_ssum,
    				values.authority / auth_ssum));
    	}
	}
    
	/**
	 * Collects the "disappearing potential" associated with vertices that have either 
	 * no incoming edges, no outgoing edges, or both.  Vertices that have no incoming edges
	 * do not directly contribute to the hub scores of other vertices; similarly, vertices
	 * that have no outgoing edges do not directly contribute to the authority scores of
	 * other vertices.  These values are collected at each step and then distributed across all vertices
	 * as a part of the normalization process.  (This process is not required for, and does
	 * not affect, the 'sum-of-squares'-style normalization.) 
	 */
    @Override
    protected void collectDisappearingPotential(V v)
    {
        if (graph.outDegree(v) == 0)
        {
            if (isDisconnectedGraphOK())
                disappearing_potential.hub += getCurrentValue(v).authority;
            else
                throw new IllegalArgumentException("Outdegree of " + v + " must be > 0");
        }
        if (graph.inDegree(v) == 0)
        {
            if (isDisconnectedGraphOK())
                disappearing_potential.authority += getCurrentValue(v).hub;
            else
                throw new IllegalArgumentException("Indegree of " + v + " must be > 0");
        }
    }

}