spacepaste

Paste details

reply | raw

  1.  
  2. /*graph.h*/
  4. typedef enum {UNDIRECTED=0,DIRECTED} graph_type_e;
  6. /* Adjacency list node*/
  7. typedef struct adjlist_node
  8. {
  9. int vertex; /*Index to adjacency list array*/
  10. struct adjlist_node *next; /*Pointer to the next node*/
  11. }adjlist_node_t, *adjlist_node_p;
  13. /* Adjacency list */
  14. typedef struct adjlist
  15. {
  16. int num_members; /*number of members in the list (for future use)*/
  17. adjlist_node_t *head; /*head of the adjacency linked list*/
  18. }adjlist_t, *adjlist_p;
  20. /* Graph structure. A graph is an array of adjacency lists.
  21. Size of array will be number of vertices in graph*/
  22. typedef struct graph
  23. {
  24. graph_type_e type; /*Directed or undirected graph */
  25. int num_vertices; /*Number of vertices*/
  26. adjlist_p adjListArr; /*Adjacency lists' array*/
  27. }graph_t, *graph_p;
  29. /* Exit function to handle fatal errors*/
  30. void err_exit(char* msg)
  31. {
  32. printf("[Fatal Error]: %s \nExiting...\n", msg);
  33. exit(1);
  34. }
  38. /*graph.c*/
  39. #include <stdio.h>
  40. #include <stdlib.h>
  41. // #include "graph.h"
  43. /* Function to create an adjacency list node*/
  44. adjlist_node_p createNode(int v)
  45. {
  46. adjlist_node_p newNode = (adjlist_node_p)malloc(sizeof(adjlist_node_t));
  47. if(!newNode)
  48. err_exit("Unable to allocate memory for new node");
  50. newNode->vertex = v;
  51. newNode->next = NULL;
  53. return newNode;
  54. }
  56. /* Function to create a graph with n vertices; Creates both directed and undirected graphs*/
  57. graph_p createGraph(int n, graph_type_e type)
  58. {
  59. int i;
  60. graph_p graph = (graph_p)malloc(sizeof(graph_t));
  61. if(!graph)
  62. err_exit("Unable to allocate memory for graph");
  63. graph->num_vertices = n;
  64. graph->type = type;
  66. /* Create an array of adjacency lists*/
  67. graph->adjListArr = (adjlist_p)malloc(n * sizeof(adjlist_t));
  68. if(!graph->adjListArr)
  69. err_exit("Unable to allocate memory for adjacency list array");
  71. for(i = 0; i < n; i++)
  72. {
  73. graph->adjListArr[i].head = NULL;
  74. graph->adjListArr[i].num_members = 0;
  75. }
  77. return graph;
  78. }
  80. /*Destroys the graph*/
  81. void destroyGraph(graph_p graph)
  82. {
  83. if(graph)
  84. {
  85. if(graph->adjListArr)
  86. {
  87. int v;
  88. /*Free up the nodes*/
  89. for (v = 0; v < graph->num_vertices; v++)
  90. {
  91. adjlist_node_p adjListPtr = graph->adjListArr[v].head;
  92. while (adjListPtr)
  93. {
  94. adjlist_node_p tmp = adjListPtr;
  95. adjListPtr = adjListPtr->next;
  96. free(tmp);
  97. }
  98. }
  99. /*Free the adjacency list array*/
  100. free(graph->adjListArr);
  101. }
  102. /*Free the graph*/
  103. free(graph);
  104. }
  105. }
  107. /* Adds an edge to a graph*/
  108. void addEdge(graph_t *graph, int src, int dest)
  109. {
  110. /* Add an edge from src to dst in the adjacency list*/
  111. adjlist_node_p newNode = createNode(dest);
  112. newNode->next = graph->adjListArr[src].head;
  113. graph->adjListArr[src].head = newNode;
  114. graph->adjListArr[src].num_members++;
  116. if(graph->type == UNDIRECTED)
  117. {
  118. /* Add an edge from dest to src also*/
  119. newNode = createNode(src);
  120. newNode->next = graph->adjListArr[dest].head;
  121. graph->adjListArr[dest].head = newNode;
  122. graph->adjListArr[dest].num_members++;
  123. }
  124. }
  126. /* Function to print the adjacency list of graph*/
  127. void displayGraph(graph_p graph)
  128. {
  129. int i;
  130. for (i = 0; i < graph->num_vertices; i++)
  131. {
  132. adjlist_node_p adjListPtr = graph->adjListArr[i].head;
  133. printf("\n%d: ", i);
  134. while (adjListPtr)
  135. {
  136. printf("%d->", adjListPtr->vertex);
  137. adjListPtr = adjListPtr->next;
  138. }
  139. printf("NULL\n");
  140. }
  141. }
  143. int main()
  144. {
  145. graph_p undir_graph = createGraph(5, UNDIRECTED);
  146. graph_p dir_graph = createGraph(5, DIRECTED);
  147. addEdge(undir_graph, 0, 1);
  148. addEdge(undir_graph, 0, 4);
  149. addEdge(undir_graph, 1, 2);
  150. addEdge(undir_graph, 1, 3);
  151. addEdge(undir_graph, 1, 4);
  152. addEdge(undir_graph, 2, 3);
  153. addEdge(undir_graph, 3, 4);
  155. addEdge(dir_graph, 0, 1);
  156. addEdge(dir_graph, 0, 4);
  157. addEdge(dir_graph, 1, 2);
  158. addEdge(dir_graph, 1, 3);
  159. addEdge(dir_graph, 1, 4);
  160. addEdge(dir_graph, 2, 3);
  161. addEdge(dir_graph, 3, 4);
  163. printf("\nUNDIRECTED GRAPH");
  164. displayGraph(undir_graph);
  165. destroyGraph(undir_graph);
  167. printf("\nDIRECTED GRAPH");
  168. displayGraph(dir_graph);
  169. destroyGraph(dir_graph);
  171. return 0;
  172. }
  173.  
Powered by spacepaste. Paste removal.