#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;}