verifier.h

clustering for ns-2 simulation

/*
* Questo file contiene le funzioni necessarie a verificare l'integrita'
 * di un risultato di un algoritmo di clustering.
 */
#ifndef _VERIFIER_H_
#define _VERIFIER_H_


#include <algorithm>
#include <iostream>
#include <map>
#include <set>

#include "graph.h"

using namespace std;

//
// Verifica che ogni nodo non del backbone sia adiacente
// ad un nodo del backbone.
//
int unselected_near_selected(Graph & graph, NodeList & backbone);


//
// Verifica che la topologia indotta dai nodi neri sia connessa.
//
int verify_backbone_connection(Graph & graph, NodeList & backbone);

//
// 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);

//
// Induce un grafo sulla topologia dei nodi neri e rinomina i nodi
// in modo crescente da 0 a (|backbone| - 1).
//
void induce_on_backbone(Graph & graph, NodeList & backbone, Graph & inducted);

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

//
// Verifica se un grafo e'connesso
//
int connected(Graph & graph);

//
// Ricerca in profondità.
//
void DFS(int node, Graph & graph, map<int, int> & colors, unsigned int & visited, int level);

#endif