    package flare.analytics.graph
    {
        import flare.animate.Transitioner;
        import flare.util.Property;
        import flare.vis.data.Data;
        import flare.vis.data.EdgeSprite;
        import flare.vis.data.NodeSprite;
        import flare.vis.operator.Operator;

        /**
         * Calculates the link distance from a source node based on a breadth-first
         * traversal. Link distance is calculated as the smallest number of edges
         * connecting a node to a source node. Any edge weights are ignored, to
         * include weighted edges in the calculation, use the
         * <code>ShortestPaths</code> operator instead.
         *
         * </p>Nodes are annotated with both the computed distance and the incoming
         * edge in the shortest link distance path to a source node. Edges are
         * annotated with a Boolean value indicating whether or not the edge lies
         * along one of these computed shortest paths.</p>
         */
        public class LinkDistance extends Operator
        {
            private var _d:Property = Property.$("props.distance");
            private var _p:Property = Property.$("props.incoming");
            private var _e:Property = Property.$("props.onpath");
            private var _links:int = NodeSprite.GRAPH_LINKS;

            /** The roots of the breadth-first search. The elements of the array
             *  should either be NodeSprite instances or integer indices into
             *  the node array. */
            public var sources:Array;

            /** The property in which to store the link distance. This property
             *  is used to annotate nodes with the minimum link distance to one of
             *  the source nodes. The default value is "props.distance". */
            public function get distanceField():String { return _d.name; }
            public function set distanceField(f:String):void { _d = Property.$(f); }

            /** The property in which to store incoming edges along a shortest
             *  path. This property is used to annotate nodes with the incoming
             *  along a shortest path from one of the source nodes. By following
             *  sequential incoming edges, one can recreate the shortest path from
             *  the nearest source node. The default value is "props.incoming". */
            public function get incomingField():String { return _p.name; }
            public function set incomingField(f:String):void { _p = Property.$(f); }

            /** The property in which to store a path inclusion flag for edges.
             *  This property is used to mark edges as belonging to one of the
             *  computed shortest paths: <code>true</code> indicates that the edge
             *  participates in a shortest path, <code>false</code> indicates that
             *  the edge does not lie along a shortest path. The default value is
             *  "props.onpath". */
            public function get onpathField():String { return _p.name; }
            public function set onpathField(f:String):void { _p = Property.$(f); }

            /** The link type to consider when calculating link distance. Should
             *  be one of <code>NodeSprite.GRAPH_LINKS</code>,
             *  <code>NodeSprite.IN_LINKS</code>, or
             *  <code>NodeSprite.OUT_LINKS</code>. */
            public function get links():int { return _links; }
            public function set links(linkType:int):void {
                if (linkType == NodeSprite.GRAPH_LINKS ||
                    linkType == NodeSprite.IN_LINKS ||
                    linkType == NodeSprite.OUT_LINKS)
                {
                    _links = linkType;
                } else {
                    throw new Error("Unsupported link type: "+linkType);
                }
            }

            // --------------------------------------------------------------------

            /**
             * Creates a new LinkDistance operator.
             * @param sources an Array specifying the roots of the breadth-first
             *  search. The elements of the array should either be
             *  <code>NodeSprite</code> instances or integer indices into the node
             *  array.
             */
            public function LinkDistance(sources:Array=null)
            {
                this.sources = sources;
            }

            /** @inheritDoc */
            public override function operate(t:Transitioner=null):void
            {
                calculate(visualization.data, sources);
            }

            /**
             * Calculates link distances from a set of source nodes for for each
             * node in the graph. Each node in the graph will be annotated with
             * its link distance from the nearest source node.
             * @param data the graph to calculate distances for
             * @param sources one or more source nodes from which to measure the
             *  distance. This input can either be a single node or an array of
             *  nodes. Nodes can be indicated as either a <code>NodeSprite</code>
             *  instance or an integer index into the <code>data.nodes</code>
             *  property.
             */
            public function calculate(data:Data, sources:*):void
            {
                var i:int, n:NodeSprite;
                data.edges.setProperty(_e.name, false);
                data.nodes.visit(function(n:NodeSprite):void {
                    _d.setValue(n, Number.POSITIVE_INFINITY);
                    _p.setValue(n, null);
                });

                // initialize queue
                var roots:Array = sources is Array ? sources as Array : [sources];
                var queue:Array = [];
                for (i=0; i<roots.length; ++i) {
                    var r:Object = roots[i];
                    if (r is NodeSprite) {
                        n = NodeSprite(r);
                    } else if (r is int) {
                        n = data.nodes[int(r)];
                    }
                    queue.push(n);
                    _d.setValue(n, 0);
                }

                while (queue.length > 0) {
                    var u:NodeSprite = queue.shift();
                    var du:int = _d.getValue(u) + 1;
                    u.visitEdges(function(e:EdgeSprite):void {
                        var v:NodeSprite = e.other(u);
                        var d:Number = _d.getValue(v);
                        if (!isFinite(d)) {
                            queue.push(v);
                            _d.setValue(v, du);
                            _p.setValue(v, e);
                        } else if (d > du) {
                            _d.setValue(v, du);
                            _p.setValue(v, e);
                        }
                    }, _links);
                }

                data.nodes.visit(function(n:NodeSprite):void {
                    var e:EdgeSprite = _p.getValue(n);
                    if (e) _e.setValue(e, true);
                });
            }

        } // end of class LinkDistance
    }