graph.h

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

#ifndef _GRAPH_H_
#define _GRAPH_H_

#define MAX_STR_LEN 1024

#define SCALE_FACTOR 1000.0

// Currently assuming that node coords and the wts are ints

struct Node;

struct Edge {
  int index; // Index of the edge in the edge list of the graph
  int id;
  Node *node1;
  Node *node2;
  int wt;

};

struct SSP;

struct Node {
  int index; // Index of the node in the node list of the graph
  int id;
  int xpos;
  int ypos;
  int adj_count;
  int curr_adj_count;   // Used to add edges in the adj_list
  Edge **adj_list;

  int ssp_d; // The value used by source shortest path algo
  Node *ssp_parent; // Parent pointer assigned by source shortest path algo
  int ssp_num_children; // Number of children in the source shortest path tree
  int curr_ssp_num_children; // Keeps a running count of the children
  Node **ssp_children;
  bool ssp_computed;

  SSP *ssp_tree;

  bool has_member; // Whether this node has a member of the mcast tree
  int member_id; // The id of the member, if the previous is true
};

struct Graph {
  int id;
  int num_nodes;
  int curr_num_nodes;   // Used to add nodes in node_list
  int num_edges;
  int curr_num_edges;   // Used to add edges in edge_list
  Node **node_list;
  Edge **edge_list;

  Node *src; // Which node in the graph is the source
};

// The Shortest Path Tree entry. The tree is stored as an array of these
// in the source node.
struct SSP {
  int level; // Level in the tree
  Node *parent; // Parent in the tree
  int num_children;
  Node **children;
};

// Functions
// Graph init-ing functions
Graph *init_graph (int gid, int num_nodes, int num_edges);
void init_node (Node *n, int index, int id, int xpos, int ypos);
void init_edge (Edge *e, int index, int id, Node *node1, Node *node2, int wt);
void add_node (Graph *g, int index, int node_id, int xpos, int ypos);
Node *locate_node (Graph *g, int node_id);
void add_edge (Graph *g, int index, int edge_id, int node1_id, int node2_id, int
 wt);
void assign_adj_list (Graph *g);
Graph* read_graph (char *file_name, int graph_id);
void output_graph (Graph *g, char *file_name);
void delete_graph (Graph *g);

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

// SSP comuptation
void init_shortest_path (Graph *g, Node *s);
void shortest_path_relax (Node *u, Node*v, Edge *uv);
void bellman_ford_ssp (Graph *g, Node *s);
void assign_ssp_level (Graph *g, Node *s);
void assign_ssp_level_from_parent (Graph *g, Node *s, Node *n);
void delete_ssp_tree (Graph *g, Node *s);
void out_ssp_tree (Graph *g, Node *s);
void output_x_to_y_path (Graph *g, Node *x, Node *y);

void assign_ssp_level (Graph *g, Node *s);
void assign_ssp_level_from_parent (Graph *g, Node *s, Node *n);

// Assigning members and source of the mcast group
void assign_random_members (Graph *g, int cnt);
void assign_specific_members_and_source (Graph *g, char *file_name);
void output_group_members (Graph *g, char *file_name);
Node *choose_random_source (Graph *g, int cnt);
Node *choose_specific_source (Graph *g, int node_id);

// Generic error analysis routines
Node *locate_member_parent (Graph *g, Node *n);
void output_parent_errors (Graph *g, char *file_name);

#endif _GRAPH_H_