package flare.analytics.graph
{
    import flare.animate.Transitioner;
    import flare.util.Property;
    import flare.vis.data.Data;
    import flare.vis.data.DataList;
    import flare.vis.data.NodeSprite;
    import flare.vis.operator.Operator;
    
    /**
     * Calculates betweenness centrality measures for nodes in a graph.
     * The algorithm used is due to Ulrik Brandes, as published in the
     * <a href="http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf">
     * Journal of Mathematical Sociology, 25(2):163-177, 2001</a>.
     */
    public class BetweennessCentrality extends Operator
    {
        private var _bc:Property = Property.$("props.centrality");
        
        /** The property in which to store the centrality score. This property
         *  is used to annotate nodes with their betweenness centrality score.
         *  The default value is "props.centrality". */
        public function get centralityField():String { return _bc.name; }
        public function set centralityField(f:String):void { _bc = Property.$(f); }
        
        /** Flag indicating the type of links to follow in the graph. The
         *  default is <code>NodeSprite.GRAPH_LINKS</code>. */
        public var links:int = NodeSprite.GRAPH_LINKS;

        /**
         * Creates a new BetweennessCentrality operator.
         */
        public function BetweennessCentrality()
        {
        }
        
        /** @inheritDoc */
        public override function operate(t:Transitioner=null):void
        {
            calculate(visualization.data);
        }
        
        /**
         * Calculates the betweenness centrality values for the given data set. 
         * @param data the data set for which to compute centrality measures
         */
        public function calculate(data:Data):void
        {
            var nodes:DataList = data.nodes; var N:int = nodes.length, i:int;
            var n:NodeSprite, v:NodeSprite, w:NodeSprite;
            var si:Score, sv:Score, sw:Score;
            
            nodes.visit(function(n:NodeSprite):void {
                _bc.setValue(n, 0);
                n.props._score = new Score();
            });
            
            for (i=0; i<N; ++i) {
                nodes.visit(function(n:NodeSprite):void {
                    n.props._score.reset();
                });
                n  = nodes[i];
                si = n.props._score;
                si.paths = 1;
                si.distance = 0;
                
                var stack:Array = [];
                var queue:Array = [n];
                
                while (queue.length > 0) {
                    stack.push(v = queue.shift()); si = v.props._score;
                    
                    v.visitNodes(function(w:NodeSprite):void {
                        var sv:Score = si, sw:Score = w.props._score;
                        if (sw.distance < 0) {
                            queue.push(w);
                            sw.distance = sv.distance + 1;
                        }
                        if (sw.distance == sv.distance + 1) {
                            sw.paths += sv.paths;
                            sw.predecessors.push(v);
                        }
                    }, links);
                }
                while (stack.length > 0) {
                    w = stack.pop(); sw = w.props._score;
                    for each (v in sw.predecessors) {
                        sv = v.props._score;
                        sv.dependency += (sv.paths/sw.paths) * (1+sw.dependency);
                    }
                    if (w !== n) sw.centrality += sw.dependency;
                }
            }
            
            nodes.visit(function(n:NodeSprite):void {
                _bc.setValue(n, n.props._score.centrality);
                delete n.props._score;
            });
        }
        
    } // end of class BetweennessCentrality
}

import flare.util.Arrays;

/** Helper class for storing intermediate centrality computations */
class Score {
    public var dependency:Number = 0;
    public var distance:Number = -1;
    public var paths:Number = 0;
    public var predecessors:Array = [];
    public var centrality:Number = 0;
    
    public function reset():void {
        Arrays.clear(predecessors);
        dependency = 0;
        distance = -1;
        paths = 0;
    }
}