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
}