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