shortest_path.cpp

clustering for ns-2 simulation

/*
 *  shortest_path.cpp
 *  Analyzers
 *
 *  Created by Michele Mastrogiovanni on 05/11/04.
 *  Copyright 2004 __MyCompanyName__. All rights reserved.
 *
 */

#include "shortest_path.h"

//---------------------------------------------------------------------
// Stampa una matrice.
//---------------------------------------------------------------------
void print(matrix<int> & m) {
	for (int x = 0; x < m.cols(); x++) {
		for (int y = 0; y < m.rows(); y++)
			printf("%d ", m[y][x]);
		printf("\n");
	}
	printf("\n");
}

void print(Graph & graph)
{
	for (Graph::iterator n = graph.begin(); n != graph.end(); n++) {
		cout << n->first << " - ";
		for (NodeList::iterator nn = (n->second).begin(); nn != (n->second).end(); nn++)
			cout << (*nn) << " ";
		cout << endl;
	}
}

//---------------------------------------------------------------------
// Trasforma un grafo in una matrice di adiacenza.
// 1) Topologia da trasformare
// 2) Correspondande: ID topologia ---> ID matrice
// Ci si basa sull'assunto che il grafo abbia nodi
// con nomi da 0 a graph.size() - 1
//---------------------------------------------------------------------
void topologyToMatrix(Graph & graph, matrix<int> & matrice) {
	
	int count = graph.size();
	for (int i = 0; i < count; i++)
		matrice[i][i] = 0;
	
	/*
	map<int, int> mappa;
	
	int nodes = 1;
	int n1, n2;
	*/
	
	for (Graph::iterator i = graph.begin(); i != graph.end(); i++)
		for (NodeList::iterator n = (i->second).begin(); n != (i->second).end(); n++)
			matrice[i->first][*n] = 1;

	/*
			n1 = mappa[i->first];
			n2 = mappa[*n];
			if (n1 == 0) {
				mappa[i->first] = nodes++;
				n1 = nodes - 1;
				// cout << "New Node: " << i->first << " -> " << (n1 - 1) << endl;
			}
			if (n2 == 0) {
				mappa[*n] = nodes++;
				n2 = nodes - 1;
				// cout << "New Node: " << (*n) << " -> " << (n2 - 1) << endl;
			}
			
			matrice[n1 - 1][n2 - 1] = 1;
			matrice[n2 - 1][n1 - 1] = 1;
		}
	}
	*/
}

//---------------------------------------------------------------------
// Floyd-Warshall
//---------------------------------------------------------------------
void FW( int n, matrix< int > &fw ) {
	
	matrix< int > t( n, n );
	t = fw;
	
	for( int k = 0; k < n; k++ ) {
		for( int i = 0; i < n; i++ )
			for( int j = 0; j < n; j++ )
				fw[ i ][ j ] = min( t[ i ][ j ], t[ i ][ k ] + t[ k ][ j ] );
		t = fw;
	}
	
}

//---------------------------------------------------------------------
// Calcola lo shortest path medio dato un grafo.
//---------------------------------------------------------------------
void shortest_path(Graph & graph, Measure & sp) {
	
	int count = graph.size();
	matrix<int> matrice(count, count, (count + 1));

	// cout << endl;
	// print(graph);
	
	topologyToMatrix(graph, matrice);
	
	FW(count, matrice);

	// cout << endl;
	// print(matrice);
	
	for (int x = 0; x < count; x++)
		for (int y = x + 1; y < count; y++)
			sp.addMeasure(matrice[x][y]);
	
	// cout << "Shortest Path Calc: " << endl;
	// cout << "Tot = " << tot << endl;
	// cout << "Elements = " << elements << endl;
	
}

//---------------------------------------------------------------------
// Calcola lo shortest path medio dato un grafo e un backbone.
//---------------------------------------------------------------------
void shortest_path(Graph & graph, NodeList & backbone, Measure & sp)
{
	Graph inducted;
	induce_on_backbone(graph, backbone, inducted);
	// print(inducted);
	shortest_path(inducted, sp);
}