routbsma.c

一个linux下的各种组播路由算法编程

class kthPath {

public:
  kthPath(double c, double d, int *in, int *not, int *p, kthPath *n);
  ~kthPath();
  double cost;
  double delay;
  int *inP;
  int *notP;
  int *pth;
  kthPath *next;
};

kthPath::kthPath(double c, double d, int *in, int *not, int *p, kthPath *n) {

  cost = c;
  delay = d;
  next = n;
  inP = in;
  notP = not;
  pth = p;
};

kthPath::~kthPath() {

  delete [] inP;
  delete [] notP;
  delete [] pth;
};
  
void TheNodeList::condDijkstra(int from, int to, int *tree1, int *tree2,
int *inPath, int *notInPath, kthPath **pl, double *c_matrix,  
double *d_matrix, int h) {

  int i, j, k;
  int *tree = new int[num+1];
  *tree = from;
  *(tree + 1) = INT_MAX;
  int *via = new int[num+1];
  *via = INT_MAX;
  int *hops = new int[num+1];
  *hops = h;
  double *cost = new double[num+1];
  *cost = 0;
  double *delay = new double[num+1];
  *delay = 0;

  i = 0;
  int tmp1 = *inPath;
  while (tmp1 != INT_MAX) {
    *(tree + i + 1) = tmp1;
    if (i == 0) *(via + 1) = from;
    else *(via + i + 1) = *(inPath + i - 1);
    *(hops + i + 1) = h + i + 1;
    *(delay + i + 1) = *(delay + i) + *(d_matrix + (*(tree + i) * num) + tmp1);
    switch (obj) {
    case PLAIN:
      *(cost + i + 1) = *(cost + i) + *(c_matrix + (*(tree+i) * num) + tmp1); 
      break;
    case MULT:
      *(cost + i + 1)  = *(cost + i) + *(c_matrix + (*(tree+i) * num) + tmp1) *
      (*(hops + i) + 1);
      break;
    case ADD:
      *(cost + i + 1)  = *(cost + i) + *(c_matrix + (*(tree+i) * num) + tmp1) +
      *(hops + i) * ALPHA;
      break;
    };     
    i++;
    tmp1 = *(inPath + i);
  };
  *(tree + i + 1) = INT_MAX;
  int srceI = i;

  double bestCost, bestDelay;
  int bestDest, bestVia, bestHop;

  int done = False;
  while (done == False) {

    i = srceI;
    tmp1 = *(tree + i);     //for each node already in the tree
    bestCost = DBL_MAX;     //infinity

    while (tmp1 != INT_MAX) {
      for (j = 0; j < num; j++) {
         int better = False;
         switch (obj) {
	 case PLAIN:
	   if ((*(cost + i) + *(c_matrix + (tmp1 * num) + j)) < bestCost) 
	     better = True;
	   break;
	 case MULT:
	   if ((*(cost + i) + *(c_matrix + (tmp1 * num) + j) * 
	       (*(hops + i) + 1)) < bestCost) better = True;
	   break;
	 case ADD:
	   if ((*(cost + i) + *(c_matrix + (tmp1 * num) + j) + 
	       *(hops + i) * ALPHA) < bestCost) better = True;
	   break;
	 };     

	 //if the cost of that adjacent node is less than the best 
	 //cost so far
	 if (better == True) {
	   k = 0;
	   int tmp2 = *tree1;
	   int found = False;
	   while ((tmp2 != INT_MAX) && (found == False)) {
	     //check if that adjacent node is already in the tree
	     if (tmp2 == j) found = True;
	     else {
	       k++;
	       tmp2 = *(tree1 + k);
	     };
	   };
           
	   if (found == False) {
	     k = 0;
	     tmp2 = *tree2;
	     while ((tmp2 != INT_MAX) && (found == False)) {
	       if ((tmp2 == j) && (tmp2 != to)) found = True;
	       else {
	         k++;
		 tmp2 = *(tree2 + k);
	       };
	     };
	   };
	     
	   if (found == False) {
	     k = 0;
	     tmp2 = *tree;
	     while ((tmp2 != INT_MAX) && (found == False)) {
	       if (tmp2 == j) found = True;
	       else {
	         k++;
		 tmp2 = *(tree + k);
	       };
	     };
	   };

	   if (found == False) {
	     k = 0;
	     tmp2 = *notInPath;
	     while ((tmp2 != INT_MAX) && (found == False)) {
	       if ((tmp2 == tmp1) && (*(notInPath + k + 1) == j)) found = True;
	       else {
	         k += 2;
		 tmp2 = *(notInPath + k);
	       };
	     };
	   };

	   if (found == False) {
	     //if not update the bestCost ...etc.
	     switch (obj) {
	     case PLAIN:
	       bestCost = *(cost + i) + *(c_matrix + (tmp1 * num) + j); 
	       break;
	     case MULT:
	       bestCost = *(cost + i) + *(c_matrix + (tmp1 * num) + j) * 
	       (*(hops + i) + 1);
	       break;
	     case ADD:
	       bestCost = *(cost + i) + *(c_matrix + (tmp1 * num) + j) + 
	       *(hops + i) * ALPHA;
	       break;
	     };     
	     bestDest = j;
	     bestVia = tmp1;
	     bestHop = *(hops + i) + 1;
	     bestDelay = *(delay + i) + *(d_matrix + (tmp1 * num) + j);
	   };
	 };
       };
       i++;
       tmp1 = *(tree + i); //repeat for all nodes already in the tree
     };

     if (bestCost == DBL_MAX) {
       delete [] cost;
       delete [] delay;
       delete [] via;
       delete [] tree;
       delete [] hops;
       delete [] inPath;
       delete [] notInPath;
       return;
     }
     else {
       *(tree + i) = bestDest;
       *(tree + i + 1) = INT_MAX;
       *(via + i) = bestVia;
       *(delay + i) = bestDelay;
       *(cost + i) = bestCost;
       *(hops + i) = bestHop;
       //Check if the tree contains all group members
       if (bestDest == to) done = True;
     };
  };

  int *p = new int[num+1];
  j = *(hops + i) + 1 - h;
  *(p + j) = INT_MAX;
  j--;
  *(p + j) = *(tree + i);
  j--;
  k = *(via + i);
  while (j >= 0) {
    i = 0;
    while(*(tree + i) != k) i++;
    *(p + j) = *(tree + i);
    j--;
    k = *(via + i);
  };
  
  kthPath *kthp = new kthPath(bestCost, bestDelay, inPath, notInPath, p,
                              *pl);
  *pl = kthp;
  delete [] cost;
  delete [] delay;
  delete [] via;
  delete [] tree;
  delete [] hops;
};

kthPath *TheNodeList::kthShortest(int from, int to, double dBound, 
double cBound, int *tree1, int *tree2, double *c_matrix, 
double *d_matrix, int h) {

  int i, j, k;
  int gDegree = (int)graphDegree() + 1;
  int *inPath = new int[num+1];
  *inPath = INT_MAX;;
  int *notInPath = new int[num*gDegree+1];
  *notInPath = INT_MAX;
  kthPath **pl = new kthPath*;
  *pl = NULL;
  int *pth;
  condDijkstra(from, to, tree1, tree2, inPath, notInPath, pl, c_matrix,
               d_matrix, h);

  kthPath *kthp = *pl;
  if ((kthp != NULL) && (kthp->cost < cBound)) {
    kthPath *tmp, *prev;
    int done = False;
    while (done == False) {
      double minCost = DBL_MAX;
      tmp = *pl;
      prev = NULL;
      kthPath *kthprev = NULL;
      kthp = NULL;
      while (tmp != NULL) {
        if (tmp->cost < minCost) {
          kthp = tmp;
	  kthprev = prev;
	};
	prev = tmp;
	tmp = tmp->next;
      };

      if (kthp != NULL) {
        if (kthprev != NULL)
	  kthprev->next = kthp->next;
        else *pl = kthp->next;
	if (kthp->cost < cBound) {
	  if (kthp->delay < dBound) done = True;
	  else {
	    inPath = kthp->inP;
	    notInPath = kthp->notP;
	    pth = kthp->pth;
	    i = 0;
	    while (*(inPath + i) != INT_MAX) i++;
	    while (*(pth + i) != to) {
              int last = *(pth + i);
	      int *inP = new int[num+1];
              if (i != 0) {
	        j = 0;
                while (*(pth + j + 1) != last) {
	          *(inP + j) = *(pth + j + 1);
	          j++;
	        };
	        *(inP + j) = *(pth + j + 1);
	        *(inP + j + 1) = INT_MAX;
	      }
              else *inP = INT_MAX;
	      int *notInP = new int[gDegree*num+1];
	      k = 0;
	      while (*(notInPath + k) != INT_MAX) {
	        *(notInP + k) = *(notInPath + k);
		k++;
	      };
              if (i != 0) {
		*(notInP + k) = *(pth + j + 1);
		*(notInP + k + 1) = *(pth + j + 2);
	      }
              else {
		*(notInP + k) = *pth;
		*(notInP + k + 1) = *(pth + 1);
	      };		
	      *(notInP + k + 2) = INT_MAX;
	      condDijkstra(from, to, tree1, tree2, inP, notInP, pl,
	                   c_matrix, d_matrix, h);
	      i++;
	    };
	    delete kthp;
	  };
	}
	else done = True;
      }
      else done = True;
    };

    tmp = *pl;
    prev = NULL;
    while (tmp != NULL) {
      prev = tmp->next;
      delete tmp;
      tmp = prev;
    };
    delete pl;
    if (kthp != NULL) { 
      if ((kthp->cost < cBound) && (kthp->delay < dBound)) return(kthp);
      else {
	delete kthp;
	return(NULL);
      };
    } else return(NULL);
  }
  else {
    kthPath *tmp, *prev;
    tmp = *pl;
    prev = NULL;
    while (tmp != NULL) {
      prev = tmp->next;
      delete tmp;
      tmp = prev;
    };
    delete pl;
    delete [] inPath;
    delete [] notInPath;
    return(NULL);
  };
};

void TheNodeList::BSMAInfo(Node *source, int addr, Node *current, 
                          double *delay, double *cost, int *hops, int *via,
			  double *d_matrix, double *c_matrix, int &seCount,
			  int *from, int *to, double *seCost, double &c,
			  MCGroup *group) {

  RoutingTableEntry *rout = current->routingTable();
  int found = False;
  while ((rout != NULL) && (found == False)) {
    if ((rout->address() == addr) && (rout->source() == source)) 
      found = True;
    else rout = rout->next();
  };

  NodeListEntry *tmpm = group->headm();
  while ((tmpm != NULL) && (tmpm->nodePtr() != current)) 
    tmpm = tmpm->next();
  
  int curr = current->name();
  NodeListEntry *tmp = rout->children();
  int j = 0;
  while (tmp != NULL) {
    tmp = tmp->next();
    j++;
  };

  if ((((j > 1) || (tmpm != NULL)) && (source != current)) || (j == 0)) {
    *(to + seCount) = curr;
    *(seCost + seCount) = c;
    if (j != 0) seCount++;
  };
  
  tmp = rout->children();
  while (tmp != NULL) {
    int nme = tmp->nodePtr()->name();
    *(delay + nme) = *(delay + curr) + *(d_matrix + (curr*num) + nme);
    *(hops + nme) = *(hops + curr) + 1;
    *(via + nme) = curr;
    double tmpc;
    switch (obj) {
    case PLAIN:
      tmpc = *(c_matrix + (curr*num) + nme);
      break;
    case MULT:
      tmpc = *(c_matrix + (curr*num) + nme) * (*(hops + curr) + 1);
      break;
    case ADD:
      tmpc = *(c_matrix + (curr*num) + nme) + *(hops + curr) * ALPHA;
      break;
    };
    *(cost + nme) = *(cost + curr) + tmpc;
    if ((j > 1) || (tmpm != NULL) || (current == source)) {
      *(from + seCount) = curr;
      c =  tmpc;