graph-alg.cc

模拟器提供了一个简单易用的平台

static char rcsid [] = "$Id: graph-alg.cc,v 1.1 2001/08/07 22:06:46 suman Exp suman $";

/*
 * $Log: graph-alg.cc,v $
 * Revision 1.1  2001/08/07 22:06:46  suman
 * Initial revision
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include "graph-alg.h"

/*
 * File: graph-alg.cc
 * Author: Suman Banerjee <[e-mail]>
 * Date: July 31, 2001
 * Terms: GPL
 *
 * myns simulator
 */

#undef LOG_GRAPH_ECHO

/*
void usage (char *s) {

  printf ("Format : %s <filename>\n", s);
  printf ("File Format : \n");
  printf ("<num-nodes> <num-edges>\n");
  printf ("<node-src> <node-dst> <wt>        [for each directed edge]\n");
  return;
}
*/

int read_graph (char *filename, double **W) {

  FILE *fp = fopen (filename,"r");
  if (fp == NULL) {
    printf ("Could not open %s\n", filename);
    exit(-1);
  }

  int nodes, edges;
  fscanf (fp, "%d %d", &nodes, &edges);
  *W = new double [nodes * nodes];

  for (int j = 0; j < nodes * nodes; j++) {
    if (( j % nodes) == (j / nodes))
      (*W)[j] = 0.0;
    else
      (*W)[j] = LARGE_DOUBLE;
  }

  for (int i = 0; i < edges; i++) {
    int n1, n2;
    double wt;
    fscanf(fp, "%d %d %lf", &n1, &n2, &wt);
#ifdef LOG_GRAPH_ECHO
    printf ("[echo] Read edge : %d %d %8.3f\n", n1, n2, wt);
#endif // LOG_GRAPH_ECHO
    if ((n1 >= nodes) || (n2 >= nodes) || (n1 < 0) || (n2 < 0)) {
      printf ("Illegal edge : < %d %d >\n", n2,n2);
      exit(-1);
    }
    (*W)[n1*nodes+n2] = wt;
  }
  fclose(fp);
  return nodes;
}

/* There are count vertices (numbered 0 to count-1) */
/* Cost of edge between i and j is given at W[i*count + j] */
/* Returns the cost matrix : D and the next hop info : NH */
void floyd_warshall_all_pair (int count, double *W, double *D, int *NH) {

  int *pred = new int [count * count];
/* Initialize the weight and the predecssor matrices */
  for (int a = 0; a < count * count; a++) {
    D[a] = W[a];
    int x = a / count;
    int y = a % count;
    if ((x == y) || (W[a] == LARGE_DOUBLE))
      pred[a] = -1;
    else
      pred[a] = x;
  }

  for (int k = 0; k < count; k++)
    for (int i = 0; i < count; i++)
      for (int j = 0; j < count; j++) {

        double new_cost = D[i*count+k] + D[k*count+j];
        if (D[i*count+j] > new_cost) {
	  D[i*count+j] = new_cost;
	  pred[i*count+j] = pred[k*count+j];
	}
      }
        

/* Now find the next hop vertex for each pair */
  for (int i = 0; i < count; i++)
    for (int j = 0; j < count; j++) {

      int this_hop = j;
      int next_hop = -1;
      
      while (this_hop != i) {
        next_hop = this_hop;
        this_hop = pred[i*count+this_hop];
      }
      NH[i*count+j] = next_hop;
    }

  delete [] pred;

  return;
}

void display_all_pair_paths (int count, double *D, int *NH) {

  printf ("[echo] All pair shortest path info : < src dst > next-hop cost\n");

  for (int i = 0; i < count; i++)
    for (int j = 0; j < count; j++)
      printf ("[echo] < %d %d > %8.5f %d\n", i, j, D[i*count+j], NH[i*count+j]);
  return;
}

/*

int main (int argc, char **argv) {

  if (argc != 2) {
    usage(argv[0]);
    exit(-1);
  }

  double *W;
  int count = read_graph (argv[1],&W);

  double *D = new double [count * count];
  int *NH = new int [count * count];

  floyd_warshall_all_pair(count,W,D,NH);
  display_all_pair_paths(count,D,NH);

  delete [] W;
  delete [] D;
  delete [] NH;
  return 1;
}

*/