package flare.analytics.cluster
{
	import flare.animate.Transitioner;
	import flare.util.math.IMatrix;
	import flare.vis.data.DataList;
	
	/**
	 * Hierarchically clusters a network based on inferred community structure.
	 * The result is a cluster tree in which each merge is chosen so as to
	 * maximize within-cluster linkage while minimizing between-cluster linkage.
	 * This class uses <a href="http://arxiv.org/abs/cond-mat/0309508">Newman's
	 * fast algorithm for detecting community structure</a>. Optionally allows
	 * clients to provide an edge weight function indicating the strength of
	 * ties within the network.
	 */
	public class CommunityStructure extends HierarchicalCluster
	{
		/** A function defining edge weights in the graph. */
		public var edgeWeights:Function = null;
		
		// --------------------------------------------------------------------
		
		/**
		 * Creates a new community structure instance
		 */
		public function CommunityStructure()
		{
		}
		
		/** @inheritDoc */
		public override function operate(t:Transitioner=null):void
		{
			calculate(visualization.data.group(group), edgeWeights);
		}
		
		/**
		 * Calculates the community structure clustering. As a result of this
		 * method, a cluster tree will be computed and graph nodes will be
		 * annotated with both community and sequence indices.
		 * @param list the data list to cluster
		 * @param w an edge weighting function. If null, each edge will be
		 *  given weight one.
		 */
		public function calculate(list:DataList, w:Function=null):void
		{
			compute(list.adjacencyMatrix(w));
			_tree = buildTree(list);
			labelNodes();
		}
		
		/** Computes the clustering */
		private function compute(G:IMatrix):void
		{
			_merges = new MergeEdge(-1, -1); _qvals = [];
			_size = G.rows;
			var i:int, j:int, k:int, s:int, t:int, v:Number;
			var Q:Number=0, Qmax:Number=0, dQ:Number, dQmax:Number=0, imax:int;
			
			// initialize normalized matrix
			var N:int = G.rows, Z:IMatrix = G.clone();
			for (i=0; i<N; ++i) Z.set(i,i,0); // clear diagonal
			Z.scale(1 / Z.sum); // normalize matrix
			
			// initialize column sums and edge list
			var E:MergeEdge = new MergeEdge(-1,-1);
			var e:MergeEdge = E, m:MergeEdge = _merges;
			var eMax:MergeEdge = new MergeEdge(0,0);
			var A:Array = new Array(N);
			
			for (i=0; i<N; ++i) {
				A[i] = 0;
				for (j=0; j<N; ++j) {
					if ((v=Z.get(i,j)) != 0) {
						A[i] += v;
						e = e.add(new MergeEdge(i,j));
					}
				}
			}
			
			// run the clustering algorithm
			for (var ii:int=0; ii<N-1 && E.next; ++ii) {
				dQmax = Number.NEGATIVE_INFINITY;
				eMax.update(0,0);
				
				// find the edge to merge
				for (e=E.next; e!=null; e=e.next) {
					i = e.i; j = e.j;
					if (i==j) continue;
					dQ = Z.get(i,j) + Z.get(j,i) - 2*A[i]*A[j];
					if (dQ > dQmax) {
						dQmax = dQ; eMax.update(i,j);
					}
				}
				
				// perform merge on graph
				i = eMax.i; j = eMax.j; if (j<i) { i=eMax.j; j=eMax.i; }
				var na:Number = 0;
				for (k=0; k<N; ++k) {
					v = Z.get(i,k) + Z.get(j,k);
					if (v != 0) {
						na += v; Z.set(i,k,v); Z.set(j,k,0);
					}
				}
				for (k=0; k<N; ++k) {
					v = Z.get(k,i) + Z.get(k,j);
					if (v != 0) {
						Z.set(k,i,v); Z.set(k,j,0);
					}
				}
				A[i] = na;
				A[j] = 0;
				for (e=E.next; e!=null; e=e.next) {
					s = e.i; t = e.j;
					if ((i==s && j==t) || (i==t && j==s)) {
						e.remove();
					} else if (s==j) {
						e.i = i;
					} else if (t==j) {
						e.j = i;
					}
				}
				
				Q += dQmax;
				if (Q > Qmax) {
					Qmax = Q;
					imax = ii;
				}
				_qvals.push(Q);
				m = m.add(new MergeEdge(i,j));
			}
		}
		
	} // end of class CommunityStructure
}