graph.c

#include #include

typedef enum {FALSE, TRUE} bool; #define MAXV 100 typedef struct edgenode { int y; int weight; struct edgenode *next; } edgenodeT;

typedef struct { edgenodeT *edges[MAXV+1]; int degree[MAXV+1]; int nvertices; int nedges; // number of directed edges.... bool directed; } graphT;

void initialize_graph(graphT *g, bool directed); void read_graph(graphT *g, char *filename); void insert_edge(graphT *g, int x, int y, int w); void print_graph(graphT *g, char *name); void free_graph(graphT *g); graphT *copy_graph(graphT *g); // put prototypes for other functions here....

int main(int argc, char *argv[]) { graphT *myg1=NULL, *myg2=NULL; if(argc

// first implement copy_graph function and call it here myg2 = copy_graph(myg1); print_graph(myg2, "myg2");

// NOW in a loop get commands and // call related functions to perform them...

free_graph(myg1); }

void initialize_graph(graphT *g, bool directed) { int i; g->nvertices = 0; g->nedges = 0; g->directed = directed; for (i=1; iedges[i] = NULL; for (i=1; idegree[i] = 0; }

void read_graph(graphT *g, char *filename) { int i; int n, m, dir; int x, y, w; FILE *fp; if((fp=fopen(filename,"r"))==NULL){ fprintf(stderr, "Cannot open the graph file"); exit(-1); } fscanf(fp,%d %d %d, &n, &m, &dir); g->nvertices = n; g->nedges = 0; // insert function will increase it; g->directed = dir; for (i=1; i

void insert_edge(graphT *g, int x, int y, int w) { edgenodeT *pe; pe = malloc(sizeof(edgenodeT)); // check if NULL pe->weight = w; pe->y = y;

// YOU MUST MODIFY THIS FUNCTION SO IT WILL KEEP LINK LIST SORTED // W.R.T. NEIGHBOR IDs.

pe->next = g->edges[x]; g->edges[x] = pe; g->degree[x]++; g->nedges++; }

void print_graph(graphT *g, char *name) { edgenodeT *pe; int i; if(!g) return; printf("Graph Name: %s ", name); for(i=1; invertices; i++) { printf("Node %d: ", i); pe = g->edges[i]; while(pe){ // printf(" %d", pe->y); printf(" %d(w=%d),", pe->y, pe->weight); pe = pe->next; } printf(" "); } }

void free_graph(graphT *g) { edgenodeT *pe, *olde; int i; for(i=1; invertices; i++) { pe = g->edges[i]; while(pe){ olde = pe; pe = pe->next; free(olde); } } free(g); } graphT *copy_graph(graphT *g) { graphT *newg;

// I simply return the same graph as a copy // but you really need to dynamically create // another copy of the given graph

newg = g; return newg; }

(Graphs - graph functions) You are given the basic code that we implemented in the slides to create/read/print graphs. First copy/paste it into a file say graph.c and compile/run it. gcc graph.c -o graph >./graph graph filename For sample graphs, again copy/paste the below graph data into a file undirectedgraphl.txt and directedgraphl.txt then run your program as ./graph undirectedgraphl.txt ./graph directedgraphl.txt directedgraphl.txt 6 8 1 1 2 3 2 3 1 3 1 6 3 5 2 4 2 5 4 5 3 4 6 6 5 6 1 undirectedgraph1.txt 6 8 0 1 2 3 1 3 6 2 3 1 3 5 2 4 5 3 4 6 6 5 6 1 After studying and understanding the given code, first modify insert_ edge ) function so that it can keep the link list sorted w.r.t. neighbor IDs. Second implement graph_copy) to create a copy of the given graph. User will call the original graph as mygl and the copy as myg2, for which we use the same pointer names in the program. Now extend the main function so that it can asks user to enter various commands in a loop and performs these commands on the related graphs. Accordingly you also need to implement those functions and call them. Finally when ending the main function, make sure you free the graphs see more explanations that are at the end of this handout (Graphs - graph functions) You are given the basic code that we implemented in the slides to create/read/print graphs. First copy/paste it into a file say graph.c and compile/run it. gcc graph.c -o graph >./graph graph filename For sample graphs, again copy/paste the below graph data into a file undirectedgraphl.txt and directedgraphl.txt then run your program as ./graph undirectedgraphl.txt ./graph directedgraphl.txt directedgraphl.txt 6 8 1 1 2 3 2 3 1 3 1 6 3 5 2 4 2 5 4 5 3 4 6 6 5 6 1 undirectedgraph1.txt 6 8 0 1 2 3 1 3 6 2 3 1 3 5 2 4 5 3 4 6 6 5 6 1 After studying and understanding the given code, first modify insert_ edge ) function so that it can keep the link list sorted w.r.t. neighbor IDs. Second implement graph_copy) to create a copy of the given graph. User will call the original graph as mygl and the copy as myg2, for which we use the same pointer names in the program. Now extend the main function so that it can asks user to enter various commands in a loop and performs these commands on the related graphs. Accordingly you also need to implement those functions and call them. Finally when ending the main function, make sure you free the graphs see more explanations that are at the end of this handout