/*
 * Created on Sep 19, 2005
 *
 * Copyright (c) 2005, 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.metrics;

import org.apache.commons.collections15.Transformer;

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

/**
 * Calculates some of the measures from Burt's text "Structural Holes: 
 * The Social Structure of Competition".
 * 
 * <p><b>Notes</b>: 
 * <ul>
 * <li/>Each of these measures assumes that each edge has an associated 
 * non-null weight whose value is accessed through the specified 
 * <code>Transformer</code> instance.
 * <li/>Nonexistent edges are treated as edges with weight 0 for purposes 
 * of edge weight calculations.
 * </ul>
 *  
 * <p>Based on code donated by Jasper Voskuilen and 
 * Diederik van Liere of the Department of Information and Decision Sciences
 * at Erasmus University.</p>
 * 
 * @author Joshua O'Madadhain
 * @author Jasper Voskuilen
 * @see "Ronald Burt, Structural Holes: The Social Structure of Competition"
 * @author Tom Nelson - converted to jung2
 */
public class StructuralHoles<V,E> {
	
    protected Transformer<E, ? extends Number> edge_weight;
    protected Graph<V,E> g;
    
    /**
     * Creates a <code>StructuralHoles</code> instance based on the 
     * edge weights specified by <code>nev</code>.
     */
    public StructuralHoles(Graph<V,E> graph, Transformer<E, ? extends Number> nev) 
    {
        this.g = graph;
        this.edge_weight = nev;
    }

    /**
     * Burt's measure of the effective size of a vertex's network.  Essentially, the
     * number of neighbors minus the average degree of those in <code>v</code>'s neighbor set,
     * not counting ties to <code>v</code>.  Formally: 
     * <pre>
     * effectiveSize(v) = v.degree() - (sum_{u in N(v)} sum_{w in N(u), w !=u,v} p(v,w)*m(u,w))
     * </pre>
     * where 
     * <ul>
     * <li/><code>N(a) = a.getNeighbors()</code>
     * <li/><code>p(v,w) =</code> normalized mutual edge weight of v and w
     * <li/><code>m(u,w)</code> = maximum-scaled mutual edge weight of u and w
     * </ul>
     * @see #normalizedMutualEdgeWeight(Object, Object)
     * @see #maxScaledMutualEdgeWeight(Object, Object) 
     */
    public double effectiveSize(V v)
    {
        double result = g.degree(v);
        for(V u : g.getNeighbors(v)) {

            for(V w : g.getNeighbors(u)) {

                if (w != v && w != u)
                    result -= normalizedMutualEdgeWeight(v,w) * 
                              maxScaledMutualEdgeWeight(u,w);
            }
        }
        return result;
    }
    
    /**
     * Returns the effective size of <code>v</code> divided by the number of 
     * alters in <code>v</code>'s network.  (In other words, 
     * <code>effectiveSize(v) / v.degree()</code>.)
     * If <code>v.degree() == 0</code>, returns 0.
     */
    public double efficiency(V v) {
        double degree = g.degree(v);
        
        if (degree == 0)
            return 0;
        else
            return effectiveSize(v) / degree;
    }

    /**
     * Burt's constraint measure (equation 2.4, page 55 of Burt, 1992). Essentially a
     * measure of the extent to which <code>v</code> is invested in people who are invested in
     * other of <code>v</code>'s alters (neighbors).  The "constraint" is characterized
     * by a lack of primary holes around each neighbor.  Formally:
     * <pre>
     * constraint(v) = sum_{w in MP(v), w != v} localConstraint(v,w)
     * </pre>
     * where MP(v) is the subset of v's neighbors that are both predecessors and successors of v. 
     * @see #localConstraint(Object, Object)
     */
    public double constraint(V v) {
        double result = 0;
        for(V w : g.getSuccessors(v)) {

            if (v != w && g.isPredecessor(v,w))
            {
                result += localConstraint(v, w);
            }
        }

        return result;
    }

    
    /**
     * Calculates the hierarchy value for a given vertex.  Returns <code>NaN</code> when
     * <code>v</code>'s degree is 0, and 1 when <code>v</code>'s degree is 1.
     * Formally:
     * <pre>
     * hierarchy(v) = (sum_{v in N(v), w != v} s(v,w) * log(s(v,w))}) / (v.degree() * Math.log(v.degree()) 
     * </pre>
     * where
     * <ul>
     * <li/><code>N(v) = v.getNeighbors()</code> 
     * <li/><code>s(v,w) = localConstraint(v,w) / (aggregateConstraint(v) / v.degree())</code>
     * </ul>
     * @see #localConstraint(Object, Object)
     * @see #aggregateConstraint(Object)
     */
    public double hierarchy(V v)
    {
        double v_degree = g.degree(v);
        
        if (v_degree == 0)
            return Double.NaN;
        if (v_degree == 1)
            return 1;
        
        double v_constraint = aggregateConstraint(v);

        double numerator = 0;
        for (V w : g.getNeighbors(v)) {
        
            if (v != w)
            {
                double sl_constraint = localConstraint(v, w) / (v_constraint / v_degree);
                numerator += sl_constraint * Math.log(sl_constraint);
            }
        }

        return numerator / (v_degree * Math.log(v_degree));
    }

    /**
     * Returns the local constraint on <code>v</code> from a lack of primary holes 
     * around its neighbor <code>v2</code>.
     * Based on Burt's equation 2.4.  Formally:
     * <pre>
     * localConstraint(v1, v2) = ( p(v1,v2) + ( sum_{w in N(v)} p(v1,w) * p(w, v2) ) )^2
     * </pre>
     * where 
     * <ul>
     * <li/><code>N(v) = v.getNeighbors()</code>
     * <li/><code>p(v,w) =</code> normalized mutual edge weight of v and w
     * </ul>
     * @see #normalizedMutualEdgeWeight(Object, Object)
     */
    public double localConstraint(V v1, V v2) 
    {
        double nmew_vw = normalizedMutualEdgeWeight(v1, v2);
        double inner_result = 0;
        for (V w : g.getNeighbors(v1)) {

            inner_result += normalizedMutualEdgeWeight(v1,w) * 
                normalizedMutualEdgeWeight(w,v2);
        }
        return (nmew_vw + inner_result) * (nmew_vw + inner_result);
    }
    
    /**
     * The aggregate constraint on <code>v</code>.  Based on Burt's equation 2.7.  
     * Formally:
     * <pre>
     * aggregateConstraint(v) = sum_{w in N(v)} localConstraint(v,w) * O(w)
     * </pre>
     * where
     * <ul>
     * <li/><code>N(v) = v.getNeighbors()</code>
     * <li/><code>O(w) = organizationalMeasure(w)</code>
     * </ul>
     */
    public double aggregateConstraint(V v)
    {
        double result = 0;
        for (V w : g.getNeighbors(v)) {

            result += localConstraint(v, w) * organizationalMeasure(g, w);
        }
        return result;
    }
    
    /**
     * A measure of the organization of individuals within the subgraph 
     * centered on <code>v</code>.  Burt's text suggests that this is 
     * in some sense a measure of how "replaceable" <code>v</code> is by 
     * some other element of this subgraph.  Should be a number in the
     * closed interval [0,1].
     * 
     * <p>This implementation returns 1.  Users may wish to override this
     * method in order to define their own behavior.</p>
     */
    protected double organizationalMeasure(Graph<V,E> g, V v) {
        return 1.0;
    }
    
   
    /**
     * Returns the proportion of <code>v1</code>'s network time and energy invested
     * in the relationship with <code>v2</code>.  Formally:
     * <pre>
     * normalizedMutualEdgeWeight(a,b) = mutual_weight(a,b) / (sum_c mutual_weight(a,c))
     * </pre>
     * Returns 0 if either numerator or denominator = 0, or if <code>v1 == v2</code>.
     * @see #mutualWeight(Object, Object)
     */
    protected double normalizedMutualEdgeWeight(V v1, V v2)
    {
        if (v1 == v2)
            return 0;
        
        double numerator = mutualWeight(v1, v2);
        
        if (numerator == 0)
            return 0;
        
        double denominator = 0;
        for (V v : g.getNeighbors(v1)) {
            denominator += mutualWeight(v1, v);
        }
        if (denominator == 0)
            return 0;
        
        return numerator / denominator;
    }
    
    /**
     * Returns the weight of the edge from <code>v1</code> to <code>v2</code>
     * plus the weight of the edge from <code>v2</code> to <code>v1</code>;
     * if either edge does not exist, it is treated as an edge with weight 0. 
     * Undirected edges are treated as two antiparallel directed edges (that
     * is, if there is one undirected edge with weight <i>w</i> connecting 
     * <code>v1</code> to <code>v2</code>, the value returned is 2<i>w</i>).
     * Ignores parallel edges; if there are any such, one is chosen at random.
     * Throws <code>NullPointerException</code> if either edge is 
     * present but not assigned a weight by the constructor-specified
     * <code>NumberEdgeValue</code>.
     */
    protected double mutualWeight(V v1, V v2)
    {
        E e12 = g.findEdge(v1,v2);
        E e21 = g.findEdge(v2,v1);
        double w12 = (e12 != null ? edge_weight.transform(e12).doubleValue() : 0);
        double w21 = (e21 != null ? edge_weight.transform(e21).doubleValue() : 0);
        
        return w12 + w21;
    }
    
    /**
     * The marginal strength of v1's relation with contact vertex2.
     * Formally:
     * <pre>
     * normalized_mutual_weight = mutual_weight(a,b) / (max_c mutual_weight(a,c))
     * </pre>
     * Returns 0 if either numerator or denominator is 0, or if <code>v1 == v2</code>.
     * @see #mutualWeight(Object, Object)
     */
    protected double maxScaledMutualEdgeWeight(V v1, V v2)
    {
        if (v1 == v2)
            return 0;

        double numerator = mutualWeight(v1, v2);

        if (numerator == 0)
            return 0;
        
        double denominator = 0;
        for (V w : g.getNeighbors(v1)) {

            if (v2 != w)
                denominator = Math.max(numerator, mutualWeight(v1, w));
        }
        
        if (denominator == 0)
            return 0;
        
        return numerator / denominator;
    }
}