    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;
        }
    }