node2.c

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

void TheNodeList::removeNode(NodeListEntry *n) {

   //First remove the node from any MC group
   MCGroup *tmp = groupsHd;
   while (tmp != NULL) {
      tmp->removeMember(n->nodePtr());
      tmp = tmp->next();
   };

   //Delete subtrees starting at this node
   //remove that node from any routing table entry at adjacent nodes
   AdjacencyListEntry *adj = n->nodePtr()->adjacentNodes();
   RoutingTableEntry *rout2;
   int found = False;
   while ((adj != NULL) && (found == False)) {
         int i;
         for (i = 0; i < PRIORITYLEVELS; i++) {
               while (adj->nodePtr()->removeSource(0, i, n->nodePtr()->name()) 
                                                       == True) srceCount--; 
         };
         rout2 = adj->nodePtr()->routingTable();
         while (rout2 != NULL) {
            rout2->removeDestination(n->nodePtr());
            rout2 = rout2->next();
         };
         adj = adj->next();
   };

   RoutingTableEntry *rout = n->nodePtr()->routingTable();
   while (rout != NULL) {
      removeSubtree(rout->source(), rout->address(), n->nodePtr());
      rout = rout->next();
   };

   //remove all sources at that node
   SourceList *s1 = n->nodePtr()->sourceList();
   SourceList *s2;
   while (s1 != NULL) {
       s2 = s1->next();
       delete s1;
       s1 = s2;
       srceCount--;
   };

   //Delete the node itself
   if (n->previous() != NULL)  n->previous()->next(n->next());
   else nodeListHd = n->next();
   if (n->next() != NULL) n->next()->previous(n->previous());
   else nodeListTl = n->previous();
   delete n->nodePtr();         // remove the node
   delete n;                    // remove the node list entry
   num--;
};

int TheNodeList::addLink(NodeListEntry *n1, NodeListEntry *n2) {

   int   s = n1->nodePtr()->addNeighbor(n2->nodePtr(), defaultCapacity);
         s = n2->nodePtr()->addNeighbor(n1->nodePtr(), defaultCapacity);
   return(s);
};

int TheNodeList::removeLink(NodeListEntry *n1, NodeListEntry *n2) {

   //First remove any subtrees rooted at this link
   RoutingTableEntry *rout = n1->nodePtr()->routingTable();
   while (rout != NULL) {
      RoutingTableEntry *rout2;
      int found = False;
      rout2 = n2->nodePtr()->routingTable();
      while ((rout2 != NULL) && (found == False)) {
          if ((rout2->address() == rout->address()) && 
              (rout2->source() == rout->source())) {
              NodeListEntry *tmp = rout2->children();
              while ((tmp != NULL) && (found == False)) {
                   if (tmp->nodePtr() == n1->nodePtr()) {
                      found = True;
                      removeSubtree(rout->source(), rout->address(), 
                                           n1->nodePtr());
                   }
                   else tmp = tmp->next();
              };
              if (found == False) {
                tmp = rout->children();
                while ((tmp != NULL) && (found == False)) {
                     if (tmp->nodePtr() == n2->nodePtr()) {
                        found = True;
                        removeSubtree(rout->source(), rout->address(), 
                                             n2->nodePtr());
                     }
                     else tmp = tmp->next();
                };
              };
              if (found == False) rout2 = rout2->next();
          }
          else rout2 = rout2->next();
      };
      rout = rout->next();
   };

   //remove any tree link on the link to be removed
   int i;
   for (i = 0; i < PRIORITYLEVELS; i++) {
       while (n1->nodePtr()->removeSource(0, i, n2->nodePtr()->name()) 
                                                 == True) srceCount--; 
   };
   RoutingTableEntry *rout3 = n1->nodePtr()->routingTable();
   while (rout3 != NULL) {
      rout3->removeDestination(n2->nodePtr());
      rout3 = rout3->next();
   };

   for (i = 0; i < PRIORITYLEVELS; i++) {
       while (n2->nodePtr()->removeSource(0, i, n1->nodePtr()->name()) 
                                                 == True) srceCount--; 
   };
   rout3 = n2->nodePtr()->routingTable();
   while (rout3 != NULL) {
      rout3->removeDestination(n1->nodePtr());
      rout3 = rout3->next();
   };

   //Now remove the link itself
   int s = n1->nodePtr()->removeNeighbor(n2->nodePtr());
         s = n2->nodePtr()->removeNeighbor(n1->nodePtr());
   return(s);
};

double TheNodeList::distance(Node *n, Node *m) {

   return(sqrt((n->X() - m->X()) * 
               (n->X() - m->X()) +
               (n->Y() - m->Y()) * 
               (n->Y() - m->Y())));
};

double TheNodeList::edgeProb(double alpha, double beta, double L, double d) {

   return(beta * exp( - d / (L * alpha)));
};
   

void TheNodeList::depth1stSearch(Node *n, int *mark) {

   AdjacencyListEntry *adj;

   *(mark + n->name()) = 1;
   adj = n->adjacentNodes();
   while (adj != NULL) {
      if (*(mark + adj->nodePtr()->name()) == 0) {
           depth1stSearch(adj->nodePtr(), mark); 
      };
      adj = adj->next();
   };
};

void TheNodeList::deleteGraph() {

   Node *tmp1;
   NodeListEntry *tmp2, *tmp3;

   tmp3 = nodeListHd;
   while (tmp3 != NULL) {
      tmp2 = tmp3->next();
      tmp1 = tmp3->nodePtr();
      delete tmp1;
      delete tmp3;
      tmp3 = tmp2;
   };
   nodeListHd = nodeListTl = NULL;
   maxName = 0;
   num = 0;

   while (groupsHd != NULL) removeMCGroup(groupsHd->address());
   srceCount = 0;
};

void TheNodeList::deleteLinks() {

   Node *tmp1;
   NodeListEntry *tmp3;

   while (groupsHd != NULL) removeMCGroup(groupsHd->address());
   srceCount = 0;
   removeBackgroundTrafficSources();

   tmp3 = nodeListHd;
   while (tmp3 != NULL) {
      tmp1 = tmp3->nodePtr();
      AdjacencyListEntry *adj1, *adj2;

      adj1 = tmp3->nodePtr()->adjacentNodes();
      while (adj1 != NULL) {
         adj2 = adj1->next();
         delete adj1;
         adj1 = adj2;
      };

      tmp3->nodePtr()->adjacentNodes(NULL);
      tmp3->nodePtr()->routingTable(NULL);
      tmp3->nodePtr()->sourceList(NULL);
      tmp3 = tmp3->next();
   };

};

NodeListEntry *TheNodeList::randomGraphGenerator(int n, float alpha, 
			    float beta, float nodeDegree) {
  
  int  i;
  Node *tmp1;
  NodeListEntry *tmp2, *tmp3;
  TheNodeList N;
  double L, d;
  float  degree;
  int    links = 0;
  
  deleteGraph();
  
  maxName = 0;
  
  nodeListHd = nodeListTl = NULL;
  
  // Create a list of n nodes at random locations.
    
  for (i = 0; i < n; i++) {
    tmp1 = new Node;
    tmp1->X(ran());
    tmp1->Y(ran() * RATIO);
    
    tmp2 = new NodeListEntry;
    tmp2->nodePtr(tmp1);
    addNode(tmp2);
  };  
  
  // Calculate the longest distance between any two nodes

  L = 0.0;
  tmp3 = nodeListHd;   
  while (tmp3 != NULL) {
    tmp2 = tmp3->next();
    while (tmp2 != NULL) {
      d = distance(tmp3->nodePtr(), tmp2->nodePtr());
      if (d > L) L = d;
      tmp2 = tmp2->next();
    };
    tmp3 = tmp3->next();
  };
  
  // Create links between the nodes  

  double p1, p2;
  int n1, n2;
  Node *nd1, *nd2;
  int *connected = new int[n];
  for (i = 0; i < n; i++) *(connected + i) = 0;
  n1 = 0;
  nd1 = nodeOf(n1);

  while (links < 2) {
    n2 = (int)(ran() * n);
    if (n2 != n1) {
      nd2 = nodeOf(n2);
      AdjacencyListEntry *adj = nd1->adjacentNodes();
      int found = False;
      while ((adj != NULL) && (found == False)) {
	if (adj->nodePtr() == nd2) found = True;
	else adj = adj->next();
      };
      if (found == False) {
	d = distance(nd1, nd2);
	p1 = edgeProb(alpha, beta, L, d);
	p2 = ran();
	if (p2 <= p1) { 
	  //an edge exists;
	  links++;
	  nd1->addNeighbor(nd2, defaultCapacity);
	  nd2->addNeighbor(nd1, defaultCapacity);
	  *(connected + n2) = 1;
	};
      };
    };
  };
  *connected = 2;

  int j, quit = False;
  j = 0;
  while (quit == False) {
    quit = True;
    for (i = 0; i < n; i++) {
      n1 = i;
      nd1 = nodeOf(n1);
      int conn = False;
      if (*(connected + n1) < 1) {
	while ((j < n) && (conn == False)) {
	  n2 = j;
	  if ((n2 != n1) && (*(connected + n2) >= 1)) {
	    nd2 = nodeOf(n2);
	    d = distance(nd1, nd2);
	    p1 = edgeProb(alpha, beta, L, d);
	    p2 = ran();
	    if (p2 <= p1) { 
	      //an edge exists;
	      links++;
	      nd1->addNeighbor(nd2, defaultCapacity);
	      nd2->addNeighbor(nd1, defaultCapacity);
	      *(connected + n1) = 1;
	      *(connected + n2) += 1;
	      conn = True;
	    };
	  };
	  j++;
	  if (j == n) j = 0;
	};
      };
      if (conn == True) quit = False;
	  
      if (*(connected + n1) == 1) {
	while ((j < n) && (conn == False)) {
	  n2 = j;
	  if (n2 != n1) {
	    nd2 = nodeOf(n2);
	    AdjacencyListEntry *adj = nd1->adjacentNodes();
	    int found = False;
	    while ((adj != NULL) && (found == False)) {
	      if (adj->nodePtr() == nd2) found = True;
	      else adj = adj->next();
	    };
	    if (found == False) {
	      d = distance(nd1, nd2);
	      p1 = edgeProb(alpha, beta, L, d);
	      p2 = ran();
	      if (p2 <= p1) { 
		//an edge exists;
		links++;
		nd1->addNeighbor(nd2, defaultCapacity);
		nd2->addNeighbor(nd1, defaultCapacity);
		*(connected + n1) = 2;
		*(connected + n2) += 1;
		conn = True;
	      };
	    };
	  };
	  j++;
	  if (j == n) j = 0;
	};
      };
      if (conn == True) quit = False;
    };
  };

  while ((2 * links / (float)n) < nodeDegree) {
    n1 = (int)(ran() * n);
    n2 = (int)(ran() * n);
    if (n1 != n2) {
      nd1 = nodeOf(n1);
      nd2 = nodeOf(n2);
      AdjacencyListEntry *adj = nd1->adjacentNodes();
      int found = False;
      while ((adj != NULL) && (found == False)) {
	if (adj->nodePtr() == nd2) found = True;
	else adj = adj->next();
      };
      if (found == False) {
	d = distance(nd1, nd2);
	p1 = edgeProb(alpha, beta, L, d);
	p2 = ran();
	if (p2 <= p1) { 
	  //an edge exists;
	  links++;
	  nd1->addNeighbor(nd2, defaultCapacity);
	  nd2->addNeighbor(nd1, defaultCapacity);
	};
      };
    };
  };
  degree = 2 * links / (float)n;
  num = n;
  return(nodeListHd);
};

NodeListEntry *TheNodeList::randomLinkGenerator(float alpha, 
                                           float beta, float nodeDegree) {

  int  i;
  Node *tmp1;
  NodeListEntry *tmp2, *tmp3;
  TheNodeList N;
  double L, d;
  float  degree;
  int    links = 0;
  
  deleteLinks();
  
  // Calculate the longest distance between any two nodes;

  L = 0.0;
  tmp3 = nodeListHd;   
  while (tmp3 != NULL) {
    tmp2 = tmp3->next();
    while (tmp2 != NULL) {
      d = distance(tmp3->nodePtr(), tmp2->nodePtr());
      if (d > L) L = d;
      tmp2 = tmp2->next();
    };
    tmp3 = tmp3->next();
  };
  
  // Create links between the nodes;
  
  double p1, p2;
  int n1, n2;