maxflowmincut.as

用于flash/flex的 as3的 2D图形图像图表的动态生成

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.
		 *  
		 *  <p><b>NOTE:</b> Capacities must be greater than or equal to zero!
		 *  </p> */
		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
		 *  <code>Function</code> that returns capacity values or a
		 *  <code>String</code> providing the name of a property to look up on
		 *  <code>EdgeSprite</code> 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
}