    package flare.vis.data
    {
        import flare.util.IEvaluable;
        import flare.util.Property;
        import flare.util.heap.FibonacciHeap;
        import flare.util.heap.HeapNode;

        import flash.utils.Dictionary;

        /**
         * Calculates a spanning tree for a graph structure. This class can
         * create spanning trees by breadth-first search, depth-first search, or by
         * computing a minimum spanning tree. The default is to find a minimum
         * spanning tree, which in turn defaults to breadth-first search if no edge
         * weight function is provided.
         *
         * <p>This class can annotate graph edges as belonging to the spanning tree
         * (done if the <code>annotateEdges</code> property is true), and can
         * construct a <code>Tree</code> instance (done if the
         * <code>buildTree<code> property is true). Generated <code>Tree<code>
         * instances are stored in the <code>tree</code> property. Generated trees
         * contain the original nodes and edges in the input graph, and any
         * previous parent or child links for input nodes will be cleared and
         * overwritten.</p>
         *
         * <p>This class is intended as a support class for creating spanning trees
         * for <code>flare.vis.data.Data</code> instances. To create annotated
         * spanning trees for other purposes, see the
         * <code>flare.analytics.graph.SpanningTree</code> class, which provides a
         * tree builder that can also be used a visualization operator.</p>
         */
        public class TreeBuilder
        {
            /** Policy for a spanning tree built using depth-first search. */
            public static const DEPTH_FIRST:String   = "depth-first";
            /** Policy for a spanning tree built using breadth-first search. */
            public static const BREADTH_FIRST:String = "breadth-first";
            /** Policy for building a minimum spanning tree. */
            public static const MINIMUM_SPAN:String  = "minimum-span";

            private var _s:Property = Property.$("props.spanning");
            private var _w:Function = null;
            private var _policy:String = MINIMUM_SPAN;
            private var _links:int = NodeSprite.GRAPH_LINKS;
            private var _tree:Tree = null;

            /** Flag indicating if a spanning tree instance should be created. */
            public var buildTree:Boolean;
            /** Flag indicating if edges in the spanning tree should be annotated.
             *  If so, the <code>spanningField</code> property will be set for
             *  each edge in the graph. */
            public var annotateEdges:Boolean;

            /** The tree created by this operator. */
            public function get tree():Tree { return _tree; }

            /** The traveral policy used to generate the spanning tree. Should be
             *  one of DEPTH_FIRST, BREADTH_FIRST, or MINIMUM_SPAN (default). */
            public function get policy():String { return _policy; }
            public function set policy(p:String):void {
                if (p==DEPTH_FIRST || p==BREADTH_FIRST || p==MINIMUM_SPAN) {
                    _policy = p;
                } else {
                    throw new Error("Unrecognized policy: "+p);
                }
            }

            /** The property with which to annotate edges that make up the spanning
             *  tree. The default value is "props.spanning". This property is used
             *  to annotate edges as "true" (if in the spanning forest) or "false"
             *  (if not in the spanning forest). */
            public function get spanningField():String { return _s.name; }
            public function set spanningField(f:String):void { _s = Property.$(f); }

            /** The root node for the spanning tree. */
            public var root:NodeSprite;

            /** The link type to consider when constructing a spanning tree. 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);
                }
            }

            /** A function determining edge weights used in the spanning tree
             *  calculation. When setting this value, one can pass in either a
             *  Function, which should take an EdgeSprite as input and return a
             *  Number as output, or a String, in which case the string will be
             *  used as a property name from which to retrieve the edge weight
             *  value from an EdgeSprite instance. If the value is null (the
             *  default) all edges will be assumed to have weight 1.
             *
             *  <p><b>NOTE:</b> Edge weights must be greater than or equal to zero!
             *  </p> */
            public function get edgeWeight():Function { return _w; }
            public function set edgeWeight(w:*):void {
                if (w==null) {
                    _w = null;
                } else if (w is String) {
                    _w = Property.$(String(w)).getValue;
                } else if (w is IEvaluable) {
                    _w = IEvaluable(w).eval;
                } else if (w is Function) {
                    _w = w;
                } else {
                    throw new Error("Unrecognized edgeWeight value. " +
                        "The value should be a Function or String.");
                }
            }

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

            /**
             * Creates a new SpanningTree operator
             * @param policy the spanning tree creation policy. The default is
             *  <code>SpanningTree.MINIMUM_SPAN</code>
             * @param buildTree if true, this operator will build a new
             *  <code>Tree</code> instance containing the spanning tree
             * @param annotateEdges if true, this operator will annotate the
             *  edges of the original graph as belonging to the spanning tree
             * @param root the root node from which to compute the spanning tree
             * @param edgeWeight the edge weight values. This can either be a
             *  <code>Function</code> that returns weight values or a
             *  <code>String</code> providing the name of a property to look up on
             *  <code>EdgeSprite</code> instances.
             */
            public function TreeBuilder(policy:String=null,
                buildTree:Boolean=true, annotateEdges:Boolean=false,
                root:NodeSprite=null, edgeWeight:*=n