Added get_pairwise_hop_count(double **distance) function.
authorTarun Agarwal <tagarwal@uiuc.edu>
Fri, 22 Apr 2005 23:53:09 +0000 (23:53 +0000)
committerTarun Agarwal <tagarwal@uiuc.edu>
Fri, 22 Apr 2005 23:53:09 +0000 (23:53 +0000)
src/conv-ldb/topology.C
src/conv-ldb/topology.h

index ae49ef1273acf03c70ef28652cc9b9ec9a2967dc..9b6f95fc78404fe7d6325d77749265d8631e720c 100644 (file)
@@ -81,6 +81,60 @@ double LBTopology::per_hop_delay(int last_hop)
                return HOP_LINK_DELAY;
 }
 
+void LBTopology::get_pairwise_hop_count(double  **distance)
+{
+  struct queueNode
+  {
+    int index;
+    int dist;
+    queueNode *next;
+    queueNode(int i,int d)
+    {
+      index=i;
+      dist=d;
+      next=NULL;
+    }
+  };
+  
+  bool *visited=new bool[npes];
+  int *neigh=new int[max_neighbors()];
+  int num_neighbors;
+
+  for(int i=0;i<npes;i++)
+  {
+    //Init data structures for BFS from i-th proc
+    for(int j=0;j<npes;j++)
+      visited[j]=false;
+
+    queueNode *q=new queueNode(i,0);
+    queueNode *last=q;
+    distance[i][i]=0;
+    visited[i]=true;
+
+    // Perform BFS until queue is empty
+    while(q)
+    { 
+      neighbors(q->index,neigh,num_neighbors);
+      for(int j=0;j<num_neighbors;j++)
+      {
+        if(!visited[neigh[j]])
+        {
+          visited[neigh[j]]=true;
+          distance[i][neigh[j]]=q->dist+1;
+          queueNode *qnew=new queueNode(neigh[j],q->dist+1);
+          last->next=qnew;
+          last=last->next;
+        }
+      }
+      queueNode *qtemp=q;
+      q=q->next;
+      delete qtemp;
+    }
+  }
+  delete[] visited;
+  delete[] neigh;
+}
+
 //smp - assume 1,2,3 or 4 processors per node
 
 template <int ppn>
index e84d73f2f486ba974f3497fe6ac852c7b3190ab2..daeb2b07ecf7d803e3565b5b161000c36f81836c 100644 (file)
@@ -36,6 +36,7 @@ public:
   virtual int get_hop_count(int src,int dest);
   virtual int rec_hop_count(int src,int dest,int max_neigh,int count,int *visited_srcs);
   virtual double per_hop_delay(int last_hop);
+  virtual void get_pairwise_hop_count(double **dist);
 };
 
 #define LBTOPO_MACRO(x) \