strongness.cpp

clustering for ns-2 simulation

#include "strongness.h"
#include "verifier.h"

//
// Calcola la strongness di un grafo conoscendo i nodi eliminabili
// (che possono essere ad esempio i nodi del backbone oppure tutti
// i nodi).
// La strongness si ottiene eliminando a caso uno dei nodi eliminabili
// e verificando che il grafo ottenuto sia ancora connesso.
// E'il chiamante che si deve occupare di definire il grafo correttamente
// per esempio passando il grafo indotto dal backbone.
//
void strongness(Graph & graph, NodeList & selectable, int & nodes_backbone, int & nodes_all)
{
	Graph backbone;
	
	if (selectable.size() == 0)
		return;
	
	int node = random_node(selectable);
	if (node == -1)
		return;
	
	induce_on_backbone_light(graph, selectable, backbone);
	if (connected(backbone) == 0)
		return;
	
	nodes_backbone++;
	
	if (unselected_near_selected(graph, selectable) != 0)
		nodes_all++;
		
	// Memorizza i link perduti.
	NodeList neighbors(graph[node]);
	
	// Elimina il nodo dal grafo e dai nodi selezionabili.
	cancelNode(node, graph);
	selectable.erase(node);
	
	// Calcola la strongness sul grafo rimasto.
	strongness(graph, selectable, nodes_backbone, nodes_all);
	
	// Ricostruisce il grafo.
	for (NodeList::iterator n = neighbors.begin(); n != neighbors.end(); n++)
		connect(*n, node, graph);
	
	selectable.insert(node);
}

int random_node(NodeList & nodes)
{
	if (nodes.size() == 0)
		return -1;
	
	NodeList::iterator choosen = nodes.begin();
    int node = rand() % nodes.size();
	for (int i = 0; i < node; i++)
		choosen++;
	
	return (*choosen);
}

//
// Calcola la debolezza di un grafo ovvero il numero medio di nodi che si
// devono togliere (scegliendoli in maniera casuale) per sconnettere il grafo.
// Questo test misura la bonta' e la ridondanza di un backbone.
// Il grafo passato e'il solo backbone, e la lista dei nodi e'quella
// di tutti i nodi del grafo.
//
void average_strongness(Graph & graph, set<int> & nodes, int trial, double & nodes_backbone, double & nodes_all)
{
	// Inizializza il seme random.
	
	// sranddev();
	// srand(time(NULL));

	nodes_backbone = 0.0;
	nodes_all = 0.0;
	
	int backbone, all;
	
	int i;
    for (i = 0; i < trial; i++) {
		backbone = all = 0;
		strongness(graph, nodes, backbone, all); 
		nodes_backbone += backbone;
		nodes_all += all;
	}
	
    nodes_backbone /= (double)trial;
    nodes_all /= (double)trial;
	
	cout << "[ B = " << nodes_backbone << ", G = " << nodes_all << " ]" << endl;
}