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