verifier.cpp

clustering for ns-2 simulation

#include "verifier.h"
#include "shortest_path.h"

//
// Ripara la scelta dei clusterHeads: assegna il clusterHead piu'grande 
// ai nodi che non sono clusterHead. Nodi che non hanno un clusterHead vicino
// impostano il clusterHead a -1 (non posseduto).
//
/*
void repair_cluster_heads(Graph & graph, map<int, int> & clusterHeads)
 {
	for (Graph::iterator i = graph.begin(); i != graph.end(); i++) {
		if (clusterHeads[i->first] != (i->first)) {
			int max = -1;
			for (set<int>::iterator n = (i->second).begin(); n != (i->second).end(); n++)
				if (clusterHeads[*n] == (*n) && (*n) > max)
					max = (*n);
		}
	}
 }
 */

//
// Verifica che ogni nodo bianco sia adiacente ad almeno un clusterHead
//
/*
int verify_white_node_connection(Graph & graph, map<int, int> & clusterHeads)
 {
	//
	// Verifica che ogni nodo bianco abbia almeno un vicino clusterHead.
	//
	for (map<int, set<int> >::iterator n = graph.begin(); n != graph.end(); n++) {
		if (clusterHeads[n->first] != (n->first)) {
			int valid = 0;
			for (set<int>::iterator i = (n->second).begin(); i != (n->second).end(); i++)
				if (clusterHeads[*i] == (*i)) {
					valid = 1;
					break;
				}
					if (valid == 0)
						return 0;
		}
	}
	
	return 1;
 }
 */

//
// Verifica che la topologia indotta dai nodi neri sia connessa.
//
int verify_backbone_connection(Graph & graph, NodeList & backbone)
{
	Graph induced;
	induce_on_backbone(graph, backbone, induced);
	return connected(induced);
}

//
// Dati i nodi del backbone induce un grafo costituito dal grafo indotto
// dai nodi del backbone sul grafo di partenza più un link che va da un nodo
// del backbone al nodo del backbone più grande.
// 
void graph_to_backbone(Graph & graph, NodeList & backbone, Graph & induced)
{
	induced.clear();
	
	for (Graph::iterator n = graph.begin(); n != graph.end(); n++) {
		if (backbone.find(n->first) == backbone.end()) {
			// Se il nodo NON è del backbone
			// Diventa adiacente al vicino del backbone di peso maggiore
			// (se esiste).
			for (NodeList::iterator neighbor = n->second.begin(); neighbor != n->second.end(); neighbor++)
				if (backbone.find(*neighbor) != backbone.end())
					connect(*neighbor, n->first, induced);
		}
		else {
			// Se il nodo è del backbone
			for (NodeList::iterator neighbor = n->second.begin(); neighbor != n->second.end(); neighbor++)
				if (backbone.find(*neighbor) != backbone.end())
					connect(*neighbor, n->first, induced);
		}
	}
}

//
// Induce un grafo sulla topologia dei nodi neri.
//
void induce_on_backbone(Graph & graph, NodeList & backbone, Graph & induced) 
{
	// print(graph);
	
	/**
	 * Create a new graph ("induced_tmp") from "graph" erasing white nodes.
	 */
	Graph induced_tmp = graph;
	for (Graph::iterator n = graph.begin(); n != graph.end(); n++)
		if (find(backbone.begin(), backbone.end(), n->first) == backbone.end())
			cancelNode(n->first, induced_tmp);
	
	// cout << "Inducted Graph: " << endl;
	// print(induced_tmp);
	
	/**
	 * Rename graph nodes from 0 to "induced_tmp.size()" - 1
	 */
	map<int, int> mappa;
	int counter = 0;
	for (Graph::iterator n = induced_tmp.begin(); n != induced_tmp.end(); n++) {
		mappa[n->first] = counter;
		counter++;
		// cout << (n->first) << " --> " << (counter - 1) << endl;
	}

	/**
	 * Create last graph with nodes from 0 to size() - 1.
	 */
	induced.clear();
	for (Graph::iterator n = induced_tmp.begin(); n != induced_tmp.end(); n++)
		for (NodeList::iterator nn = n->second.begin(); nn != n->second.end(); nn++)
			induced[mappa[n->first]].insert(mappa[*nn]);
	
	/*
	backbone.clear();
	for (Graph::iterator n = induced_tmp.begin(); n != induced_tmp.end(); n++)
		backbone.insert(n->first);
	*/
	
	// cout << "------------------------------" << endl;
	
	// print(induced);

}

//
// Induce un grafo sulla topologia dei nodi neri senza rinumerare i nodi.
//
void induce_on_backbone_light(Graph & graph, NodeList & backbone, Graph & induced) 
{
	induced = graph;

	for (Graph::iterator n = graph.begin(); n != graph.end(); n++)
		if (find(backbone.begin(), backbone.end(), n->first) == backbone.end())
			cancelNode(n->first, induced);
}

//
// Verifica se un grafo e'connesso
//
int connected(Graph & graph)
{
	map<int, int> colors;
	
	for (Graph::iterator n = graph.begin(); n != graph.end(); n++)
		colors[n->first] = 0;
	
	// Verifica che la topologia indotta sui nodi neri sia connessa.
	unsigned int visited = 0;
	
	DFS((graph.begin())->first, graph, colors, visited, 0);
	
	return (visited == graph.size()) ? 1 : 0;
}

//
// Ricerca in profondità.
//
void DFS(int node, Graph & graph, map<int, int> & colors, unsigned int & visited, int level)
{
	//
    // Colora il nodo di grigio
	//
    colors[node] = 1;
	
    for(set<int>::iterator neighbor = graph[node].begin(); 
        neighbor != graph[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, graph, colors, visited, level + 1);
		}
			
			//
			// Colora il nodo di nero
			//
			colors[node] = 2;
	
	//
	// Incrementa il numero di nodi visitati.
	//
    visited++;
}

int unselected_near_selected(Graph & graph, NodeList & backbone)
{
	for (Graph::iterator n = graph.begin(); n != graph.end(); n++) {
		if (backbone.find(n->first) == backbone.end()) {
			bool ok = false;
			for (NodeList::iterator nn = n->second.begin(); nn != n->second.end(); nn++) {
				if (backbone.find(*nn) != backbone.end()) {
					ok = true;
					break;
				}
			}
			if (!ok)
				return 0;
		}
	}
	return 1;
}