graph.cpp

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

    return;

  if (s == n)
    {
      n->ssp_tree[n->index].level = 0;
      return;
    }
  Node *pt_of_n = s->ssp_tree[n->index].parent;
  assert(pt_of_n != NULL);
  if (s->ssp_tree[pt_of_n->index].level < 0) // This would be true initally.
    assign_ssp_level_from_parent(g,s,pt_of_n);
  s->ssp_tree[n->index].level = s->ssp_tree[pt_of_n->index].level + 1;

  return;
}

  
// Delete the SSP tree
void delete_ssp_tree (Graph *g, Node *s)
{
  if (!(s->ssp_computed))
    return;
  for (int i = 0; i < g->num_nodes; i++)
    delete [] s->ssp_tree[i].children;
  delete [] s->ssp_tree;
  s->ssp_computed = false;
  fprintf (stdout, "SSP tree deleted for node %d\n", s->id);
  return;
}

// Output the SSP tree
void out_ssp_tree (Graph *g, Node *s)
{
 if (!(s->ssp_computed))
   {
     fprintf(stdout,"SSP not computed\n");
     return;
   }

 fprintf (stdout, "SSP Tree of %d\n", s->id);
 for (int i = 0; i < g->num_nodes; i++)
   {
     fprintf (stdout, "Node %d :: Level %d :: ", g->node_list[i]->id,s->ssp_tree[i].level);
     if (g->node_list[i]->has_member)
       fprintf (stdout,"Member %d :: ",g->node_list[i]->member_id);
     else
       fprintf (stdout,"No Member :: ");

     if (s->ssp_tree[i].parent != NULL)
       fprintf (stdout, "Parent  %d :: ", s->ssp_tree[i].parent->id);
     else
       fprintf (stdout, "Parent  NULL :: ");
     fprintf (stdout, "Num Children %d :: Children ", s->ssp_tree[i].num_children);
     for (int j = 0; j < s->ssp_tree[i].num_children; j++)
       fprintf (stdout,"%d ",s->ssp_tree[i].children[j]->id);
     fprintf (stdout,"\n");
   }
 fprintf (stdout, "Tree display complete\n");
 return;
}

// Arbitrarily assigns cnt mcast group members to the nodes.
void assign_random_members (Graph *g, int cnt)
{
  int num_free_nodes; // Nodes that dont have members assigned
  int locate_free_index; // Finds the next index position of the nodes as required
  // by new_member_index
  int new_member_index; // The next member position (ignoring the ones that are
  // already been assigned.

  if (cnt > g->num_nodes)
    {
      fprintf (stderr, "Too many members : %d, should be upto %d\n",cnt,g->num_nodes);
      return;
    }
  num_free_nodes = g->num_nodes;
  for (int i = 0; i < cnt; i++)
    {
      new_member_index = rand() % num_free_nodes;
      locate_free_index = 0;
      for (int j = 0; j < g->num_nodes; j++)
	{
	  Node *n = g->node_list[j];
	  if (!(n->has_member))
	    {
	     if (locate_free_index == new_member_index)
	      {
	       n->has_member = true;
	       n->member_id = i;
	       num_free_nodes --;
	       break;
	      }
	     else
	      locate_free_index ++;
	    }
	}
    }
  return;
}

// Assign the members as specified.
void assign_specific_members_and_source (Graph *g, char *file_name)
{
  FILE *fp = fopen(file_name,"r");
  char str[MAX_STR_LEN];
  int cnt;
  int node_id, member_id;

  if (fp == NULL)
    {
      fprintf (stderr,"Could not open file : %s\n",file_name);
      return;
    }

  fgets(str,MAX_STR_LEN,fp); // Comment line
  fgets(str,MAX_STR_LEN,fp); // Has the number of members
  sscanf (str,"%d",&cnt);
  fgets(str,MAX_STR_LEN,fp); // Comment line
  
  for (int i = 0; i < cnt; i++)
    {
      fgets(str,MAX_STR_LEN,fp); // Has <node_id member_id>
      sscanf(str,"%d %d",&node_id, &member_id);
      for (int j = 0; j < g->num_nodes; j++)
	{
	  Node *n = g->node_list[j];
	  if (n->id == node_id)
	    {
	      assert(!(n->has_member));
	      n->has_member = true;
	      n->member_id = member_id;
	      break;
	    }
	}
    }

  fgets(str,MAX_STR_LEN,fp); // Blank line
  fgets(str,MAX_STR_LEN,fp); // Comment line
  fgets(str,MAX_STR_LEN,fp);

  sscanf(str,"%d",&node_id); // This contains the source
  choose_specific_source(g,node_id);

  fclose(fp);
  return;
}

// Outputs the group members in the given file_name
void output_group_members (Graph *g, char *file_name)
{
  FILE *fp = fopen(file_name,"w");
  int node_id, member_id;
  int count = 0;

  if (fp == NULL)
    {
      fprintf (stderr,"Could not open file : %s\n",file_name);
      return;
    }

  fprintf (fp,"Multicast group members\nNode-id Member-id\n");
  for (int i = 0; i < g->num_nodes; i++)
    {
      Node *n = g->node_list[i];
      if (n->has_member)
	{
	  count ++;
	  fprintf (fp,"%d %d\n",n->id,n->member_id);
	}
    }

  fprintf (fp,"Number of members : %d\n",count);
  fprintf (fp,"\n Source node : %d\n",g->src->id);
  fclose(fp);
  return;
}
 
// Chooses a source arbitarily from the mcast members, of which there are cnt.
Node *choose_random_source (Graph *g, int cnt)
{
 int ndx = rand() % cnt;
 int pos = 0;

 for (int i = 0; i < g->num_nodes; i++)
   {
     Node *n = g->node_list[i];
     if (n->has_member)
       {
        if (pos == ndx)
	  {
	    g->src = n;
	    return n;
	  }
	else
	  pos ++;
       }
   }
 return NULL;
}

// Chooses a specific node to be the source.
Node *choose_specific_source (Graph *g, int node_id)
{
 for (int i = 0; i < g->num_nodes; i++)
   {
     Node *n = g->node_list[i];
     if (n->id == node_id)
       if (n->has_member == true)
         {
	  g->src = n;
	  return n;
	 }
   }
 return NULL;
}

// Computes the SSP for all members in the graph
void compute_ssp_members (Graph *g)
{
  for (int i = 0; i < g->num_nodes; i++)
    if (g->node_list[i]->has_member)
      dijkstra_ssp(g,g->node_list[i]);
      //bellman_ford_ssp(g,g->node_list[i]);
  return;
}

// Returns the node which is the member parent of the given node n.
Node *locate_member_parent (Graph *g, Node *n)
{
 assert(n->has_member);
 assert (g->src->ssp_computed);

 // Start with the immediate parent.
 Node *p = g->src->ssp_tree[n->index].parent;

 while (p != NULL)
   {
     // If this ancestor has a member, then this is the first such
     // ancestor. So it must be the parent.
     if (p->has_member)
       return p;
     // Else go to the next higher ancestor and repeat.
     Node *new_p = g->src->ssp_tree[p->index].parent;
     if (new_p == NULL)
       assert(p == g->src);
     p = new_p;
   }
 return g->src;
}

// Outputs to stdout, the shortest path from x -> y as per SSP of x
void output_x_to_y_path (Graph *g, Node *x, Node *y)
{
  int *ancestor_list;

  if (!(x->ssp_computed))
      {
	fprintf (stdout, "SSP of node %d was not computed\n",x->id);
	bellman_ford_ssp(g,x);
      }

  int i = x->ssp_tree[y->index].level;
  ancestor_list = new int [ i + 1];
  ancestor_list[i] = y->id;


  Node *p = x->ssp_tree[y->index].parent;

  fprintf (stdout,"Output of path from %d to %d\n",x->id,y->id);
  while (p != NULL)
    {
      i--;
      if (i < 0)
	fprintf (stderr,"Problem : level and number of ancestors dont match\n");
      else
	ancestor_list[i] = p->id;
      Node *new_p = x->ssp_tree[p->index].parent;
      if (new_p == NULL)
	assert(p == x);
      p = new_p;
    }

  if (i > 0)
    fprintf (stdout,"Valid ancestors start from pos : %d\n",i);
  for (int j = 0; j < x->ssp_tree[y->index].level; j++)
      fprintf (stdout, "%d=> %d\n", j, ancestor_list[j]);

  return;
}
  

// Outputs the possibility of errors
void output_parent_errors (Graph *g, char *file_name)
{
  FILE *fp = fopen(file_name,"w");
  if (fp == NULL)
    {
      fprintf (stderr,"Could not open file : %s\n", file_name);
      return;
    }

  Node *s = g->src; // The source node.
  int count = 0;
  int total_members_lower_level_mistake = 0;
  int total_members_same_level_mistake = 0;

  for (int i = 0; i < g->num_nodes; i++)
    {
      Node *n = g->node_list[i];
      if (n == s)
	continue; // No need to check for the source
      if (!(n->has_member))
	continue;

      count ++;
      // For each member compute the error
      assert(n->ssp_computed);
      // Here, n stands for this node, p is the correct member parent
      // and s is source
      int s_n_ttl = s->ssp_tree[i].level; // TTL(s,n)
      Node *p = locate_member_parent(g,n);
      int s_p_ttl = s->ssp_tree[p->index].level; // TTL(s,p)

      assert(p->ssp_computed); // Need this for TTL(p,n)
      int p_n_ttl = p->ssp_tree[n->index].level; // TTL(p,n)

      if (s_p_ttl + p_n_ttl != s_n_ttl) // This is an error, the assert fails
	{
	  fprintf (stderr,"Assert going to fail for node %d, parent %d and source %d\n", n->id, p->id, s->id);
	  fprintf (stderr, "TTL(s,p) : %d, TTL(p,n) : %d, TTL(s,n) : %d\n", s_p_ttl, p_n_ttl, s_n_ttl);
	  output_x_to_y_path(g,s,p);
	  output_x_to_y_path(g,p,n);
	  output_x_to_y_path(g,s,n);
	}
      assert(s_p_ttl + p_n_ttl == s_n_ttl);

      fprintf (fp, "Node %d : [P - %d] : ",n->id, p->id);
      int same_level_mistake = 0; // Mistake with a member at same level
      // as parent
      int lower_level_mistake = 0; // Mistake with a member closer than parent
      for (int j = 0; j < g->num_nodes; j++)
	{
	  Node *t = g->node_list[j];
	  if (!(t->has_member))
	    continue;
	  int s_t_ttl = s->ssp_tree[t->index].level;
	  if (s_t_ttl < s_p_ttl)
	    continue; // There is no mistake possible if this node is higher
	  // up in the tree than the parent

	  int t_n_ttl = t->ssp_tree[n->index].level;
	  if (s_t_ttl + t_n_ttl != s_n_ttl)
	    continue; // No mistake possible here either

	  assert(s_t_ttl + t_n_ttl == s_n_ttl); // Can't have less
	  if ((s_t_ttl == s_p_ttl) && (t != p)) 
	    {
	      // Then this is a same level mistake (ie. same level as parent)
	      same_level_mistake ++;
	      fprintf (fp,"(S - %d) ",t->id);
	    }

	  if ((s_t_ttl > s_p_ttl) && (t != n))
	    {
	      assert (t != n);
	      lower_level_mistake ++;
	      fprintf (fp, "(L - %d) ",t->id);
	    }
	}
      fprintf (fp,"\n\tSame level : %d\tLower level : %d\n", same_level_mistake, lower_level_mistake);

      // Compute member count for mistakes for the entire tree
      if (lower_level_mistake > 0)
	total_members_lower_level_mistake ++;
      else if (same_level_mistake > 0)
	total_members_same_level_mistake ++;
	
    }

  fprintf (fp,"Num nodes : %d\tNum members : %d\n",g->num_nodes, count);
  fprintf (fp, "Members lower level mistake : %d\n",total_members_lower_level_mistake);
  fprintf (fp, "Members same level mistake : %d (does not include the members who have already made the lower level mistake)\n",total_members_same_level_mistake);
  fclose(fp);
  return;
}

int main(int argc, char **argv)
{
  Graph *g;
  struct timeval tp;
  struct timezone tzp;

  // Init the random number generator
  gettimeofday(&tp,&tzp);
  srand((int)(tp.tv_usec));

 if (argc != 4) 
   {
     fprintf(stderr,"Not enough arguments\n");
     fprintf(stderr, "Format : %s <graph_specs_file> <test_output_file> <myns_output_file>\n",argv[0]);
     fprintf (stderr, "\t graph_specs_file : GT-ITM .alt file for the topology\n");
     fprintf (stderr, "\t test_output_file : Echoes the .alt file\n");
     fprintf (stderr, "\t myns_output_file : Output in myns format\n");
     return -1;
   }

 g = read_graph(argv[1],1);
 if (g == NULL)
   {
     fprintf (stderr, "Could not create graph\n");
     return -1;
   }
 if (strcmp(argv[2],"-") != 0)
   output_graph(g,argv[2]);
 write_graph_in_myns_format(g,argv[3]);

 /*
 if (strcmp(argv[3],"NULL") != 0)
     assign_specific_members_and_source(g,argv[3]);
 else
   {
     int count;
     sscanf(argv[6],"%d",&count);
     assign_random_members(g,count);
     Node *src = choose_random_source(g,count);
     output_group_members(g,argv[4]);
     fprintf (stdout,"Chosen source node : %d\n",src->id);
   }

 dijkstra_ssp(g,g->node_list[0]);
 out_ssp_tree(g,g->node_list[0]);
 delete_ssp_tree(g,g->node_list[0]);
 return 1;
 compute_ssp_members(g);
 output_parent_errors(g,argv[5]);
 */

 delete_graph(g);
 return 1;
}