TopolSegmentation.h

#ifndef TopolSegmentation_H
#define TopolSegmentation_H

#include "SOMSegmentation.h"

class TopolSegmentation : public SOMSegmentation {
public:
        TopolSegmentation( const SOM * som ) : SOMSegmentation( som ) {};
        TIntVector Segment();

private:
        bool element_in( TVecCluster vec1, TVecCluster vec2 );

        void vector_copy( TVecCluster & vec1, TVecCluster vec2 );

        void group( TMatrix group_dist, TMatrix mean_vector, TMatrix group_in );

        bool isActive( TMatrix mean_vector, int index, int d );
};

TIntVector 
TopolSegmentation::Segment( const SOM * som ) {
        int i,k, j;
        Value_Type min, dist, diff;
        int m                           = netParams.getMapcode()->getMapSize();
        int n                           = netParams.getData()->getDataSize();
        int d                           = netParams.getData()->getDimension();
        int     lattice                 = netParams.getMapcode()->getLattice();
        int*    dimensions      = netParams.getMapcode()->getDimensions();
        TBMU * bmu                      = getLearningAlgorithm()->getBMU();
        TMatrix codebook        = netParams.getMapcode()->getCodebook();        
        TMatrix delta           = netParams.getDelta();

        // Initialize group_in[1..m][1..m] variable with zeros and ones in the diagonal
        TIntVector tmp = create_intvector(1, d);        
        TMatrix group_in = create_matrix(1,m,1,m);
        for (i=1; i<=m; i++) for (j=1; j<=m; j++)
                if ( i == j ) group_in[i][j] = 1;
                else group_in[i][j] = 0;

        // Initialize the mean_vector[1..m] for each group
        TvecMean mean_vector;
        for (i=1; i<=m; i++) {          
                for (k=1; k<=d; k++) tmp[k] = codebook[i][k];
                mean_vector.push_back( mean_node( tmp, 1 ) );           
        }

        // Sum of all code vectors for each group
        for (i=0; i<n; i++) {
                if ( delta[bmu[0][i][0].i][bmu[0][i][1].i] < sqrt(2) ) {
                        for (k=1; k<=d; k++) {
                                mean_vector[ bmu[0][i][0].i - 1 ].mean[k] += codebook[ bmu[0][i][1].i ][k];                     
                        }
                        ++mean_vector[ bmu[0][i][0].i - 1 ].num;
                        group_in[bmu[0][i][0].i][bmu[0][i][1].i] = 1;
                }
        };
        
        // Calculates the mean for each group
        for (i=0; i<m; i++)
                for (k=1; k<=d; k++ )
                        mean_vector[i].mean[k] /= mean_vector[i].num;

        // Decides for each node in what group it will be allocated
        int min_index;
        for (i=1; i<=m; i++ ) {
                min = 100000000; min_index = -1;
                for (j=1; j<=m; j++ )
                        if (group_in[i][j] == 1) {                                                              
                                dist = 0;
                                for (k=1; k<= d; k++) {
                                        diff = mean_vector[j-1].mean[k] - codebook[i][k]; 
                                        dist += diff*diff;
                                }                               
                                if ( dist < min ) {
                                        if ( min_index > 0 ) 
                                          group_in[i][min_index] = 0;
                                        min = dist;
                                    min_index = j;                                      
                                }
                                else
                                        group_in[i][j] = 0;
                        }
        }
        //printmatrix( group_in, 1, m, 1, m );

        // Initializes temporary variables              
        TMatrix  mean_tmp = create_matrix(1,m,1,d);
        for (i=1;i<=m;i++) for (j=1;j<=d;j++) mean_tmp[i][j] = 0;
        TVector  num_tmp  = create_vector(1, m );
        for (i=1;i<=m;i++) num_tmp[i] = 0;

        // Re-calculates the mean vector, considering the new groups formed
        for (i=1; i<=m; i++) {
                //cout << endl << "Grupo " << i << ":";
                for (j=1; j<=m; j++) {
                        if ( group_in[j][i] == 1 ) {
                                //cout << j << " ";                             
                                ++num_tmp[i];
                                for (k=1; k<=d; k++)                                    
                                        mean_tmp[i][k] += codebook[j][k];                               
                        }
                }
        }
        for (i=1; i<=m; i++)
                if ( num_tmp[i] > 0 )
                        for (k=1; k<=d; k++)
                                mean_tmp[i][k] /= num_tmp[i];

        //printmatrix( mean_tmp, 1,m,1,d);                       
        
        // Create the group distance matrix (group_dist[1..m][1..m])
        TMatrix group_dist = create_matrix(1,m,1,m);
        TMatrix distancia = create_matrix(1,m,1,m);
        for (i=1; i<=m; i++)
                for (j=i; j<=m; j++) {
                        dist = 0;
                        for (k=1; k<= d; k++) {
                                diff = mean_tmp[i][k] - mean_tmp[j][k]; 
                                dist += diff*diff;
                        }                       
                        distancia[i][j] = distancia[j][i] = dist;
                        if (( dist <= limit ) && (i != j) && (isActive(mean_tmp,j,d)) && (isActive(mean_tmp,i,d)))
                           group_dist[i][j] = group_dist[j][i] = 1;
                        else
                           group_dist[i][j] = group_dist[j][i] = 0;
                }

        //printmatrix( distancia,1,m,1,m);

        //printmatrix( group_dist,1,m,1,m);

        group( group_dist, mean_tmp, group_in );

        return 0;
};

bool 
TopolSegmentation::isActive( TMatrix mean_vector, int index, int d ) {
        int k; 
        for (k=1; k<=d; k++) if ( mean_vector[index][k] != 0.0 ) return 1;
        return 0;
};

bool 
TopolSegmentation::element_in( TVecCluster vec1, TVecCluster vec2 ) {
        TVecCluster::iterator iv1, iv2;
        for (iv1 = vec1.begin(); iv1 < vec1.end(); iv1++ ) 
                for (iv2 = vec2.begin(); iv2 < vec2.end(); iv2++ )
                        if ( *iv1 == *iv2 )
                                return 1;
        return 0;       
}

void 
TopolSegmentation::vector_copy( TVecCluster & vec1, TVecCluster vec2 ) {        
        
        TVecCluster::iterator iv1 = vec1.begin();
        TVecCluster::iterator iv2 = vec2.begin();               
        int count = 0; int i;

        while (iv2 < vec2.end()) {
                if ( *iv2 > *iv1 ) {            
                        ++iv1; ++count; }
                else
                        if ( *iv2 == *iv1 ) 
                                ++iv2;
                        else
                                if ( *iv2 < *iv1 ) {
                                        vec1.push_back( *iv2 );
                                        ++iv2;
                                        iv1 = vec1.begin();
                                        for(i=1; i<=count; i++) ++iv1; 
                                }
                if ( iv1 == vec1.end() )
                        while ( iv2 < vec2.end() ) {
                                if ( *iv2 != *iv1 )
                                        vec1.push_back( *iv2 );                                 
                                ++iv2;
                        }
        };
}


void 
TopolSegmentation::group( TMatrix group_dist,TMatrix mean_vector, TMatrix group_in ) {

        TCluster cluster;
        TCluster::iterator ic;
        TVecCluster vec_cluster;
        TVecCluster::iterator iv;
        int yet_included;
        int i, j, l;
        int m = netParams.getMapcode()->getMapSize();
        int d = netParams.getData()->getDimension();
        int* dimensions = netParams.getMapcode()->getDimensions();

        cluster.clear();
        TVecCluster tmpvec;
        TVecCluster ptrvec;
        for (j=1; j<=m; j++) {
          if (isActive( mean_vector, j, d )) {
                vec_cluster.clear();
                vec_cluster.push_back( j );
                for (l=j; l<=m; l++)
                        if ( group_dist[l][j] == 1 )
                                vec_cluster.push_back( l );
                sort( vec_cluster.begin(), vec_cluster.end() ); 
                if (cluster.empty()) 
                        cluster.push_back( vec_cluster );               
                else
                {
                        TCluster::iterator pointer = cluster.begin();
                        yet_included = 0;

                        for (ic=cluster.begin(); ic < cluster.end(); ic++) {
                                tmpvec.clear();
                                tmpvec = *ic;
                                if ( yet_included == 0 ) {
                                        if ( element_in( vec_cluster, tmpvec ) ){
                                                vector_copy( tmpvec, vec_cluster );
                                                sort( tmpvec.begin(), tmpvec.end() );
                                                *ic = tmpvec;
                                                yet_included = 1; pointer = ic;
                                        }
                                }
                                else {
                                        ptrvec = *pointer;
                                        if (element_in( ptrvec, tmpvec )) {
                                                vector_copy( tmpvec, ptrvec );
                                                sort( tmpvec.begin(), tmpvec.end() );
                                                *ic = tmpvec;
                                                pointer->clear();
                                                pointer = ic;
                                        }
                                }
                        }
                        if ( yet_included == 0 )
                                cluster.push_back( vec_cluster );
                }
          }
        }

        int label = 0; int x, y;
        TMatrix cluster_label = create_matrix(1,dimensions[1],1,dimensions[0]);
        for (i=1; i<= dimensions[1]; i++) for (j=1; j<= dimensions[0]; j++)
                cluster_label[i][j] = 0;
        
        for (ic=cluster.begin(); ic < cluster.end(); ic++) {
                tmpvec = *ic;           
                //if (!ic->end()) ++label; 
                if (tmpvec.begin() != tmpvec.end()) ++label;
                //cout << "Novo grupo" << endl;
                for (iv=tmpvec.begin(); iv < tmpvec.end(); iv++ ) {
                        //cout << endl << *iv << ": ";
                        for (i=1; i<=m; i++)
                                if ( group_in[i][*iv] == 1 ) {
                                        //cout << " " << i << " ";
                                        x = getLearningAlgorithm()->getTopology()->Coord( i, 1, dimensions );
                                        y = getLearningAlgorithm()->getTopology()->Coord( i, 2, dimensions );
                                        cluster_label[y+1][x+1] = label;
                                }
                }
        }

        netParams.getMapcode()->setClusterLabel( cluster_label );

}

#endif

---