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; import flash.utils.Dictionary; /** * Calculates the maximum flow along edges of a graph using the * Edmonds-Karp method. Each edge in the graph will be annotated with its * final flow value, as well as a boolean value indicating if the edge * is part of the minimum cut of the flow graph. Nodes are annotated with * their partition according to the minimum cut: a partition value of 0 * indicates the source-side of the cut, a value of 1 indicates the * sink-side of the cut. */ public class MaxFlowMinCut extends Operator { private var _c:Property = Property.$("props.capacity"); private var _f:Property = Property.$("props.flow"); private var _p:Property = Property.$("props.predecessor"); private var _k:Property = Property.$("props.mincut"); private var _cap:Function = null; /** The property in which to store computed flow values. This property * is used to annotate edges with the computed flow. The default * value is "props.flow". */ public function get flowField():String { return _f.name; } public function set flowField(f:String):void { _f = Property.$(f); } /** The property in which to store minimum-cut data. The default value * is "props.mincut". This property is used to annotate nodes with * their partition (0 for source-side, 1 for sink-side) and to * annotate edges with min-cut membership (true if part of the * minimum cut, false otherwise). */ public function get mincutField():String { return _k.name; } public function set mincutField(f:String):void { _k = Property.$(f); } /** The source node for which to compute the max flow. */ public var source:NodeSprite; /** The sink node for which to compute the max flow. */ public var sink:NodeSprite; /** A function defining the edge capacities for flow. 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 capacity value from an EdgeSprite instance. * If the value is null (the default) all edges will be assumed to have * capacity 1. * *
NOTE: Capacities must be greater than or equal to zero! *
*/ public function get edgeCapacity():Function { return _cap; } public function set edgeCapacity(c:*):void { if (c==null) { _cap = null; } else if (c is String) { _cap = Property.$(String(c)).getValue; } else if (c is Function) { _cap = c; } else { throw new Error("Unrecognized edgeCapacity value. " + "The value should be a Function or String."); } } /** The computed maximum flow value. This value is zero by default * and is populated once the max flow calculation is run. */ public function get maxFlow():Number { return _maxFlow; } private var _data:Data, _s:NodeSprite, _t:NodeSprite; private var _maxFlow:Number = 0; // -------------------------------------------------------------------- /** * Creates a new MaxFlowMinCut operator. * @param source the source node in the flow graph * @param sink the sink node in the flow graph * @param edgeCapacity the edge capacity values. This can either be a *Function
that returns capacity values or a
* String
providing the name of a property to look up on
* EdgeSprite
instances.
*/
public function MaxFlowMinCut(source:NodeSprite=null,
sink:NodeSprite=null, edgeCapacity:*=null)
{
this.source = source;
this.sink = sink;
this.edgeCapacity = edgeCapacity;
}
/** @inheritDoc */
public override function operate(t:Transitioner=null):void
{
calculate(visualization.data, source, sink, _cap);
}
/**
* Calculates the maximum flow and minimum cut for the given data
* @param data the data set containing the flow graph
* @param s the source node in the flow graph
* @param t the target or "sink" node in the flow graph
* @param c a function returning capacity values for edges
*/
public function calculate(data:Data, s:NodeSprite, t:NodeSprite,
c:Function=null):void
{
_data = data; _s = s; _t = t;
_data.nodes.visit(function(n:NodeSprite):void {
_c.setValue(n, 0);
_f.setValue(n, 0);
_p.setValue(n, null);
});
_data.edges.visit(function(e:EdgeSprite):void {
var cap:Number = (c==null ? 1 : c(e));
if (cap < 0) throw new Error("Edge capacity must be > 0!");
_c.setValue(e, cap);
});
// update flows until no more augmenting path
while (augmentingPath()) {
var cap:Number = _c.getValue(_t);
_maxFlow += cap;
var v:NodeSprite = _t, u:NodeSprite, e:EdgeSprite;
while (v != _s) {
e = _p.getValue(v);
u = e.source;
_f.setValue(e, _f.getValue(e) + cap);
_c.setValue(e, _c.getValue(e) - cap);
v = u;
}
}
minCut();
_data.visit(_c.deleteValue);
_data.nodes.visit(_p.deleteValue);
}
/**
* Uses a breadth-first-search to find an augmenting path that
* increases the net flow through the graph.
*/
private function augmentingPath():Boolean
{
_data.nodes.setProperty(_c.name, Number.MAX_VALUE);
var visited:Dictionary = new Dictionary();
var queue:Array = [_s], u:NodeSprite, b:Boolean;
while (queue.length > 0) {
visited[u = queue.shift()] = true;
b = u.visitEdges(function(e:EdgeSprite):Boolean {
// get residual capacity on edge
var cap:Number = _c.getValue(e);
var v:NodeSprite = e.other(u);
if (visited[v] || cap <= 0) return false;
_c.setValue(v, Math.min(_c.getValue(u), cap));
_p.setValue(v, e);
if (v == _t) return true;
queue.push(v);
return false;
}, NodeSprite.OUT_LINKS);
if (b) return true;
}
return false;
}
/**
* Given that the max flow has been computed, finds the minimum-cut
* of the flow graph, annotating nodes according to their partition
* (source-side or sink-side) and annotating the edges that constitute
* the minimum cut.
*/
private function minCut():void
{
_data.nodes.setProperty(_k.name, 1);
var visited:Dictionary = new Dictionary();
var queue:Array = [_s], u:NodeSprite, b:Boolean;
while (queue.length > 0) {
visited[u = queue.shift()] = true;
_k.setValue(u, 0);
u.visitEdges(function(e:EdgeSprite):void {
var v:NodeSprite = e.other(u);
if (!(visited[v] || _c.getValue(e) <= 0))
queue.push(v);
}, NodeSprite.OUT_LINKS);
}
_data.edges.visit(function(e:EdgeSprite):void {
var up:int = _k.getValue(e.source);
var vp:int = _k.getValue(e.target);
_k.setValue(e, (up==0 && vp==1));
});
}
} // end of class MaxFlowMinCut
}