csparsifierutility.cc

clustering for ns-2 simulation

/**
 * Copyright (c) 2006 Michele Mastrogiovanni.
 *
 *   Licensed under the Apache License, Version 2.0 (the "License");
 *   you may not use this file except in compliance with the License.
 *   You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 *   Unless required by applicable law or agreed to in writing, software
 *   distributed under the License is distributed on an "AS IS" BASIS,
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *   See the License for the specific language governing permissions and
 *   limitations under the License.
 *
 */
 
#include "CSparsifierUtility.h"
#include <algorithm>

static class CSparsifierUtilityClass : public TclClass {
public:
    CSparsifierUtilityClass() : TclClass("Utility/CSPARSIFIER") {}
    TclObject* create(int , const char*const* ) {
        return(new CSparsifierUtility());
    }
} class_c_sparsifier_utility;

void
CSparsifierUtility::dump()
{
	// Utility::dump();
	
	cerr << "Mancano: ";
	for (int i = 0; i < 50; i++) {
		if (neighbors[i].size() == 0)
			cerr << i << "  ";
	}
	cerr << endl;
	cerr << "Tempo Medio di convergenza sparsificatore: " << time << endl;
	cerr << "Topologia sparsificata di " << neighbors.size() << " nodi" << endl;
	
    // Marca tutti i nodi come non visitati:
    // 0: non visitato
    // 1: visitato
    vector<unsigned int> color(neighbors.size(), 0);
	
    // Marca il primo nodo come visitato
    unsigned int visited = 0;
	
    // Effettua una visita in profondita'
    DFS(0, color, visited);
	
    // Verifica che il numero dei nodi visitati sia pari al numero
    // di nodi del grafo.  
    if (visited == neighbors.size())
		cerr << "Topologia Connessa" << endl;
	else
		cerr << "Topologia NON Connessa" << endl;
}

void 
CSparsifierUtility::DFS(int node, vector<unsigned int> & colors, unsigned int & visited)
{
    // Colora il nodo di grigio
    colors[node] = 1;
  
    for(set<int>::iterator neighbor = neighbors[node].begin(); 
        neighbor != neighbors[node].end(); 
        neighbor++ )
        // Se il nodo non e' stato ancora colorato
        if (colors[*neighbor] == 0)
            // Effettua la ricerca il profondita' a partire da quel nodo
            DFS(*neighbor, colors, visited);
  
    // Colora il nodo di nero
    colors[node] = 2;
  
    visited++;
}

void 
CSparsifierUtility::setNeighbors(NodeAddress node, NodeList & neigh)
{
	neighbors[node] = neigh;
}