graph.cpp

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

#include <stdio.h>
#include <assert.h>
#include <limits.h>
#include <sys/time.h>
#include <stdlib.h>
#include "llheap.h"
#include "graph.h"

 // Initialize a graph
Graph *init_graph (int gid, int num_nodes, int num_edges)
  {
    Graph *g = new Graph;
    g->id = gid;
    g->num_nodes = num_nodes;
    g->num_edges = num_edges;
    g->curr_num_nodes = 0;
    g->curr_num_edges = 0;
    g->node_list = new Node* [num_nodes];
    g->edge_list = new Edge* [num_edges];

    g->src = NULL;

    return g;
  }

 // Init a node
void init_node (Node *n, int index, int id, int xpos, int ypos)
  {
    assert(n != NULL);
    n->index = index;
    n->id = id;
    n->xpos = xpos;
    n->ypos = ypos;
    n->adj_count = 0;
    n->curr_adj_count = 0;
    n->ssp_computed = false;
    n->has_member = false;
    return;
  }

 // Init an edge
void init_edge (Edge *e, int index, int id, Node *node1, Node *node2, int wt)
  {
    assert(e != NULL);
    e->index = index;
    e->id = id;
    e->node1 = node1;
    e->node2 = node2;
    e->wt = wt;
    return;
  }

 // Add a node to a graph, with the given node id
void add_node (Graph *g, int index, int node_id, int xpos, int ypos)
  {
    assert(g != NULL);
    assert(g->curr_num_nodes < g->num_nodes);

    g->node_list[g->curr_num_nodes] = new Node;
    init_node(g->node_list[g->curr_num_nodes],index,node_id,xpos,ypos);
    g->curr_num_nodes ++;
    return;
  }

 // Returns pointer to the node structure with the matching node id.
 // No node in the node_list of the graph should be NULL.
Node *locate_node (Graph *g, int node_id)
  {
    assert(g != NULL);
    for (int i = 0; i < g->num_nodes; i++)
	if (g->node_list[i]->id == node_id)
		return g->node_list[i];
    return NULL;
  }

 // This routine should be called after all the nodes of the graph has
 // structures malloc-ed for them.
 // In the process also calculates the size of the adj list of each
 // node.
void add_edge (Graph *g, int index, int edge_id, int node1_id, int node2_id, int wt)
  {
    Node *node1, *node2;

    assert(g != NULL);
    assert(g->curr_num_edges < g->num_edges);
    g->edge_list[g->curr_num_edges] = new Edge;
    node1 = locate_node(g,node1_id);
    node2 = locate_node(g,node2_id);

    assert((node1 != NULL) && (node2 != NULL));

    node1->adj_count ++;
    node2->adj_count ++;
    init_edge(g->edge_list[g->curr_num_edges],index,edge_id,node1,node2,wt);
    g->curr_num_edges ++;
    return;
  }

 // Assign adj list for nodes -- puts the relevant Edge* in the adj_list of
 // the nodes.
void assign_adj_list (Graph *g)
  {
    assert (g != NULL);
    for (int i = 0; i < g->num_nodes; i++)
      {
	Node *n = g->node_list[i];
	n->adj_list = new Edge* [n->adj_count];
      }

    for (int j = 0; j < g->num_edges; j++)
      {
	Edge *e = g->edge_list[j];
	e->node1->adj_list[e->node1->curr_adj_count] = e;
	e->node2->adj_list[e->node2->curr_adj_count] = e;
	e->node1->curr_adj_count ++;
	e->node2->curr_adj_count ++;
      }

    return;
  }

// Reads the graph from the file named.
Graph* read_graph (char *file_name, int graph_id)
  {
    char str[MAX_STR_LEN];
    FILE *fp = fopen(file_name,"r");
    int num_nodes, num_edges;
    Graph *g;
    int node_id, node_xpos, node_ypos;
    int node1_id, node2_id, wt;

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

    fgets(str,MAX_STR_LEN,fp);// This is a comment line.
    fgets(str,MAX_STR_LEN,fp);
    sscanf(str,"%d %d",&num_nodes, &num_edges);
    num_edges /= 2; // gt-itm graphs gives the sum of degrees, which is
                    // which is twice the sum of all the edges
    fgets(str,MAX_STR_LEN,fp); // Blank line
    fgets(str,MAX_STR_LEN,fp); // Comment line

    g = init_graph(graph_id,num_nodes,num_edges);
    for (int i = 0; i < num_nodes; i++)
      {
	fgets(str,MAX_STR_LEN,fp);
	sscanf(str,"%d %*s %d %d",&node_id,&node_xpos,&node_ypos);
	add_node(g,i,node_id,node_xpos,node_ypos);
      }

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

    for (int j = 0; j < num_edges; j++)
      {
	fgets(str,MAX_STR_LEN,fp);
	sscanf(str,"%d %d %d",&node1_id,&node2_id,&wt);
	add_edge(g,j,j,node1_id,node2_id,wt);
      }
    assign_adj_list(g);

    fprintf (stdout, "Created the graph from file : %s\n",file_name);
    fclose(fp);
    return g;
  }

// Output a graph specs into the filename specified
void output_graph (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;
      }

    fprintf(fp,"GRAPH #nodes #edges\n");
    fprintf(fp,"%d %d\n\n",g->num_nodes,g->num_edges);

    fprintf(fp,"VERTICES (index xpos ypos neighbor-count : dest-nodes)\n");
    for (int i = 0; i < g->num_nodes; i++)
      {
       Node *n = g->node_list[i];
       fprintf(fp,"%d %d %d %d : ",n->id,n->xpos,n->ypos,n->adj_count);
       for (int k = 0; k < n->adj_count; k++)
	 {
	   if (n->adj_list[k]->node1 == n)
	     fprintf(fp,"%d ",n->adj_list[k]->node2->id);
	   else
	     fprintf(fp,"%d ",n->adj_list[k]->node1->id);
	 }
       fprintf(fp,"\n");
      }

    fprintf(fp,"\nEDGES (from-node to-node length)\n");
    for (int j = 0; j < g->num_edges; j++)
      {
	Edge *e = g->edge_list[j];
	fprintf (fp,"%d %d %d\n",e->node1->id,e->node2->id,e->wt);
      }

    fclose(fp);
    fprintf (stdout, "Wrote the graph to file : %s\n",file_name);
    return;
 }

void write_graph_in_myns_format (Graph *g, char * filename) {

  FILE *fp = fopen(filename,"w");
  if (fp == NULL)
    {
     fprintf(stderr,"Could not open file : %s\n",filename);
     return;
    }

  fprintf (fp,"nodecount %d;\n\n", g->num_nodes);
  for (int i = 0; i < g->num_edges; i++) {

    fprintf (fp,"edge %d %d %8.3f;\n", g->edge_list[i]->node1->id,  g->edge_list[i]->node2->id, ((double)(g->edge_list[i]->wt)) / SCALE_FACTOR);
  }
  fclose(fp);
  return;
}

// Delete the graph
void delete_graph (Graph *g)
{
  for (int i = 0; i < g->num_nodes; i++)
    {
      Node *n = g->node_list[i];
      if (n->ssp_computed)
	delete_ssp_tree(g,n);
      delete [] n->adj_list;
      delete n;
    }

  for (int j = 0; j < g->num_edges; j++)
    delete g->edge_list[j];

  delete g->node_list;
  delete g->edge_list;

  fprintf (stdout, "Deleted the graph : %d\n",g->id);
  delete g;
  return;
}
      
// Initialize for shortest path algo rooted at a source, s
void init_shortest_path (Graph *g, Node *s)
{
  assert(g != NULL);

  delete_ssp_tree(g,s);

  for (int i = 0; i < g->num_nodes; i++)
    {
      Node *n = g->node_list[i];
      if (i == s->index)
	s->ssp_d = 0;
      else
	n->ssp_d = INT_MAX/2;
      n->ssp_parent = NULL;
      n->ssp_num_children = 0;
      n->curr_ssp_num_children = 0;
    }
  return;
}

// Relax routine of Cormen et al book (pg. 520)
void shortest_path_relax (Node *u, Node*v, Edge *uv)
{
  //assert( ((uv->node1 == u) && (uv->node2 == v)) ||
  //	  ((uv->node2 == u) && (uv->node1 == v)) );

  // Changing the following from path weights to hop count
  // ie. uv->wt == 1
  //if (v->ssp_d > (u->ssp_d + uv->wt))
  if (v->ssp_d > (u->ssp_d + 1))
    {
      //v->ssp_d = u->ssp_d + uv->wt;
      v->ssp_d = u->ssp_d + 1;
      v->ssp_parent = u;
    }
  return;
}

// Perform the Dijkstra's single source shortest path algo
// Cormen et al. Page 527
void dijkstra_ssp (Graph *g, Node *s)
{
  if (s->ssp_computed)
    return;
  init_shortest_path(g,s);

  LLHeap *h;
  // Position *Pos = new Position [g->num_nodes];

  h = init_heap(g->num_nodes);
  for (int i = 0; i < g->num_nodes; i++)
      insert(h,g->node_list[i]->ssp_d);
      
  while (!is_empty(h))
    {
      int min_sspd;
      int min_index = delete_min(h,min_sspd);
      assert (min_index >= 0);
      for (int j = 0; j < g->node_list[min_index]->adj_count; j++)
	{
	  Edge *e = g->node_list[min_index]->adj_list[j];
	  Node *this_node, *other_node;
	  if (e->node1 == g->node_list[min_index])
	    {
	      this_node = e->node1;
	      other_node = e->node2;
	    }
	  else
	    {
	      this_node = e->node2;
	      other_node = e->node1;
	    }
	  if (heap_check_valid(h,other_node->index))
	    {
	      shortest_path_relax(this_node,other_node,e);
	      change_key(h,other_node->index,other_node->ssp_d);
	    }
	}
    }
  delete_heap(h);

  s->ssp_tree = new SSP [g->num_nodes];

  // Copy the parent info into the SSP structure and also compute the
  // number of children of each node.
  for (int k = 0; k < g->num_nodes; k++)
    {
      s->ssp_tree[k].level = -1; //Init the level field
      s->ssp_tree[k].parent = g->node_list[k]->ssp_parent;
      if (g->node_list[k]->ssp_parent != NULL)
	g->node_list[k]->ssp_parent->ssp_num_children ++;
    }

  for (int m = 0; m < g->num_nodes; m++)
    {
      Node *n = g->node_list[m];
      n->ssp_children = new Node* [n->ssp_num_children];
    }

  for (int q = 0; q < g->num_nodes; q++)
    {
      Node *sp = g->node_list[q]->ssp_parent;
      if (sp != NULL)
	{
	  sp->ssp_children[sp->curr_ssp_num_children] = g->node_list[q];
	  sp->curr_ssp_num_children ++;
	}
    }

  for (int p = 0; p < g->num_nodes; p++)
    {
      s->ssp_tree[p].children = g->node_list[p]->ssp_children;
      s->ssp_tree[p].num_children = g->node_list[p]->ssp_num_children;
    }

  assign_ssp_level(g,s);
  s->ssp_computed = true;
  fprintf (stdout,"Created the shortest path tree sourced at : %d\n", s->id);
  return;
}

// Performs the Bellman Ford single source shortest path algo
// Uses the algo mentioned in Cormen et al.
void bellman_ford_ssp (Graph *g, Node *s)
{

  if (s->ssp_computed)
    return;

  init_shortest_path(g,s);
  for (int i = 0; i < g->num_nodes - 1; i++)
    for (int j = 0; j < g->num_edges; j++)
      {
       Edge *e = g->edge_list[j];
       shortest_path_relax(e->node1,e->node2,e);
       shortest_path_relax(e->node2,e->node1,e);
      }

  s->ssp_tree = new SSP [g->num_nodes];

  // Copy the parent info into the SSP structure and also compute the
  // number of children of each node.
  for (int k = 0; k < g->num_nodes; k++)
    {
      s->ssp_tree[k].level = -1; //Init the level field
      s->ssp_tree[k].parent = g->node_list[k]->ssp_parent;
      if (g->node_list[k]->ssp_parent != NULL)
	g->node_list[k]->ssp_parent->ssp_num_children ++;
    }

  for (int m = 0; m < g->num_nodes; m++)
    {
      Node *n = g->node_list[m];
      n->ssp_children = new Node* [n->ssp_num_children];
    }

  for (int q = 0; q < g->num_nodes; q++)
    {
      Node *sp = g->node_list[q]->ssp_parent;
      if (sp != NULL)
	{
	  sp->ssp_children[sp->curr_ssp_num_children] = g->node_list[q];
	  sp->curr_ssp_num_children ++;
	}
    }

  for (int p = 0; p < g->num_nodes; p++)
    {
      s->ssp_tree[p].children = g->node_list[p]->ssp_children;
      s->ssp_tree[p].num_children = g->node_list[p]->ssp_num_children;
    }

  assign_ssp_level(g,s);
  s->ssp_computed = true;
  fprintf (stdout,"Created the shortest path tree sourced at : %d\n", s->id);
  return;
}

// Assigns the SSP tree levels for all nodes
void assign_ssp_level (Graph *g, Node *s)
{
 for (int i = 0; i < g->num_nodes; i++)
   assign_ssp_level_from_parent(g,s,g->node_list[i]);
 return;
}

// Assigns the SSP tree levels in the tree, by first assigning the SSP tree level
// for the parent. s : is the source node, and n is the node whose level is being
// assigned.
void assign_ssp_level_from_parent (Graph *g, Node *s, Node *n)
{
  if (s->ssp_tree[n->index].level > 0) // This means the level is already assigned.