Array graph
"arraygraph.h"
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #ifndef _GRAPH_ADJACENCY_MATRIX_ #define _GRAPH_ADJACENCY_MATRIX_ struct Array_Graph_Type { int Maximum_Vertex_Count; int Current_Vertex_Count; int Graph_Type; int** Double_Pointer_Adjacency_Edge; int* Pointer_Vertex; }; struct Array_Graph_Type* Create_Array_Graph(int Maximum_Number_Of_Vertex, int Graph_Type); void Delete_Array_Graph(struct Array_Graph_Type* Pointer_Graph); int Add_Vertex_Array_Graph(struct Array_Graph_Type* Pointer_Graph, int Vertex_Index); int Add_Edge_Array_Graph(struct Array_Graph_Type* Pointer_Graph, int From_Vertex_Index, int To_Vertex_Index, int weight); int Check_Vertex_Valid(struct Array_Graph_Type* Pointer_Graph, int Vertex_Index); void Display_Array_Graph(struct Array_Graph_Type* Pointer_Graph); #endif // !_GRAPH_ADJACENCY_MATRIX_ #ifndef _COMMON_GRAPH_DEFAULT_ #define _COMMON_GRAPH_DEFAULT_ #define USED 1 #define NOT_USED 0 #define SUCCESS 1 #define FAIL 0 #define TRUE 1 #define FALSE 0 #define GRAPH_UNDIRECTED 1 #define GRAPH_DIRECTED 2 #endif // !_COMMON_GRAPH_DEFAULT_ | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 | #include <stdio.h> #include <stdlib.h> #include <string.h> #include "arraygraph.h" struct Array_Graph_Type* Create_Array_Graph(int Maximum_Number_Of_Vertex, int Graph_Type) { if (Maximum_Number_Of_Vertex < 1) { printf("Error! The maximum number of vertex must be greater then zero. Create_Array_Graph()\n"); return NULL; } struct Array_Graph_Type* Pointer_Return = (struct Array_Graph_Type*)malloc(1 * sizeof(struct Array_Graph_Type)); if ((struct Array_Graph_Type*)Pointer_Return == NULL) { printf("Error! Dynamic memory allocation failed(1). Create_Array_Graph()\n"); return NULL; } (void*)memset((struct Array_Graph_Type*)Pointer_Return, 0, 1 * sizeof(struct Array_Graph_Type)); Pointer_Return->Graph_Type = Graph_Type; Pointer_Return->Maximum_Vertex_Count = Maximum_Number_Of_Vertex; Pointer_Return->Pointer_Vertex = (int*)malloc(Maximum_Number_Of_Vertex * sizeof(int)); if (Pointer_Return->Pointer_Vertex == NULL) { printf("Error! Dynamic memory allocation failed(2). Create_Array_Graph()\n"); if ((struct Array_Graph_Type*) Pointer_Return != NULL) free((struct Array_Graph_Type*)Pointer_Return); return NULL; } (void*)memset(Pointer_Return->Pointer_Vertex, NOT_USED, Maximum_Number_Of_Vertex * sizeof(int)); Pointer_Return->Double_Pointer_Adjacency_Edge = (int**)malloc(Maximum_Number_Of_Vertex * sizeof(int*)); if (Pointer_Return->Double_Pointer_Adjacency_Edge == NULL) { printf("Error! Dynamic memory allocation failed(3). Create_Array_Graph()\n"); if (Pointer_Return->Pointer_Vertex != NULL) free(Pointer_Return->Pointer_Vertex); if ((struct Array_Graph_Type*)Pointer_Return != NULL) free((struct Array_Graph_Type*)Pointer_Return); return NULL; } (void*)memset(Pointer_Return->Double_Pointer_Adjacency_Edge, 0, Maximum_Number_Of_Vertex * sizeof(int*)); int index = 0; for (index = 0; index < Maximum_Number_Of_Vertex; index++) { *(Pointer_Return->Double_Pointer_Adjacency_Edge + index) = (int*)malloc(Maximum_Number_Of_Vertex * sizeof(int)); if (*(Pointer_Return->Double_Pointer_Adjacency_Edge + index) == NULL) { printf("Error! Dynamic memory allocation failed(4). Create_Array_Graph()\n"); int Index_02 = 0; for (Index_02 = 0; Index_02 < index - 1; Index_02++) { if (*(Pointer_Return->Double_Pointer_Adjacency_Edge + Index_02) != NULL) free(*(Pointer_Return->Double_Pointer_Adjacency_Edge + Index_02)); } if (Pointer_Return->Double_Pointer_Adjacency_Edge != NULL) free(Pointer_Return->Double_Pointer_Adjacency_Edge); if (Pointer_Return->Pointer_Vertex != NULL) free(Pointer_Return->Pointer_Vertex); if ((struct Array_Graph_Type*)Pointer_Return != NULL) free((struct Array_Graph_Type*)Pointer_Return); return NULL; } (void*)memset(*(Pointer_Return->Double_Pointer_Adjacency_Edge + index), 0, Maximum_Number_Of_Vertex * sizeof(int)); } return (struct Array_Graph_Type*)Pointer_Return; } void Delete_Array_Graph(struct Array_Graph_Type* Pointer_Graph) { if ((struct Array_Graph_Type*)Pointer_Graph == NULL) return; int index = 0; for (index = 0; index < Pointer_Graph->Maximum_Vertex_Count; index++) { if (*(Pointer_Graph->Double_Pointer_Adjacency_Edge + index) != NULL) free(*(Pointer_Graph->Double_Pointer_Adjacency_Edge + index)); } if (Pointer_Graph->Double_Pointer_Adjacency_Edge != NULL) free(Pointer_Graph->Double_Pointer_Adjacency_Edge); if (Pointer_Graph->Pointer_Vertex != NULL) free(Pointer_Graph->Pointer_Vertex); if ((struct Array_Graph_Type*)Pointer_Graph != NULL) free((struct Array_Graph_Type*)Pointer_Graph); return; } int Add_Vertex_Array_Graph(struct Array_Graph_Type* Pointer_Graph, int Vertex_Index) { if ((struct Array_Graph_Type*)Pointer_Graph == NULL) { printf("Error! The array graph is null. Add_Vertex_Array_Graph()\n"); return FAIL; } else if (!(Vertex_Index < Pointer_Graph->Maximum_Vertex_Count)) { printf("Error! Maximum number of node was overflow. [%d] Add_Vertex_Array_Graph()\n", Pointer_Graph->Current_Vertex_Count); return FAIL; } else if (*(Pointer_Graph->Pointer_Vertex + Vertex_Index)) { printf("Error! already existing node [%d]. Add_Vertex_Array__Graph()\n", Vertex_Index); return FAIL; } *(Pointer_Graph->Pointer_Vertex + Vertex_Index) = USED; Pointer_Graph->Current_Vertex_Count++; return SUCCESS; } int Add_Edge_Array_Graph(struct Array_Graph_Type* Pointer_Graph, int From_Vertex_Index, int To_Vertex_Index, int weight) { if ((struct Array_Graph_Type*)Pointer_Graph == NULL) { printf("Error! The array graph is null. Add_Dege_Array_Graph()\n"); return FAIL; } if (!Check_Vertex_Valid((struct Array_Graph_Type*)Pointer_Graph, From_Vertex_Index)) return FAIL; else if (!Check_Vertex_Valid((struct Array_Graph_Type*)Pointer_Graph, To_Vertex_Index)) return FAIL; *(*(Pointer_Graph->Double_Pointer_Adjacency_Edge + From_Vertex_Index) + To_Vertex_Index) = weight; if (Pointer_Graph->Graph_Type == GRAPH_UNDIRECTED) *(*(Pointer_Graph->Double_Pointer_Adjacency_Edge + To_Vertex_Index) + From_Vertex_Index) = weight; return SUCCESS; } int Check_Vertex_Valid(struct Array_Graph_Type* Pointer_Graph, int Vertex_Index) { if (Vertex_Index >= Pointer_Graph->Maximum_Vertex_Count || *(Pointer_Graph->Pointer_Vertex + Vertex_Index) == NOT_USED) { printf("Error! Node information [%d]\n", Vertex_Index); return FAIL; } return SUCCESS; } void Display_Array_Graph(struct Array_Graph_Type* Pointer_Graph) { if ((struct Array_Graph_Type*)Pointer_Graph == NULL) return; int row = 0, column = 0; for (column = 0; column < Pointer_Graph->Maximum_Vertex_Count; column++) { for (row = 0; row < Pointer_Graph->Maximum_Vertex_Count; row++) { printf("%d ", *(*(Pointer_Graph->Double_Pointer_Adjacency_Edge + column) + row)); } printf("\n"); } return; } | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include <stdio.h> #include "arraygraph.h" #define GRAPH_SIZE 6 int main(int argc, char** argv) { typedef struct Array_Graph_Type Array_Graph; Array_Graph* Pointer_Graph_01 = (Array_Graph*)Create_Array_Graph(GRAPH_SIZE, GRAPH_UNDIRECTED); if ((Array_Graph*)Pointer_Graph_01 == NULL) return -1; Array_Graph* Pointer_Graph_02 = (Array_Graph*)Create_Array_Graph(GRAPH_SIZE, GRAPH_DIRECTED); if ((Array_Graph*)Pointer_Graph_02 == NULL) return -1; Array_Graph* Pointer_Graph_03 = (Array_Graph*)Create_Array_Graph(GRAPH_SIZE, GRAPH_DIRECTED); if ((Array_Graph*)Pointer_Graph_03 == NULL) return -1; int index = 0; for (index = 0; index < GRAPH_SIZE; index++) { Add_Vertex_Array_Graph((Array_Graph*)Pointer_Graph_01, index); Add_Vertex_Array_Graph((Array_Graph*)Pointer_Graph_02, index); Add_Vertex_Array_Graph((Array_Graph*)Pointer_Graph_03, index); } // add edge Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_01, 0, 1, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_01, 0, 2, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_01, 1, 2, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_01, 2, 3, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_01, 3, 4, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_01, 3, 5, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_01, 4, 5, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_02, 0, 1, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_02, 1, 2, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_02, 2, 0, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_02, 2, 1, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_02, 2, 3, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_02, 3, 2, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_02, 3, 4, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_02, 4, 5, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_02, 5, 3, USED); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_03, 00, 01, 04); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_03, 01, 02, 01); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_03, 02, 00, 02); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_03, 02, 01, 03); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_03, 02, 03, 02); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_03, 03, 02, 01); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_03, 03, 04, 01); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_03, 04, 05, 01); Add_Edge_Array_Graph((Array_Graph*)Pointer_Graph_03, 05, 03, 02); // display graph printf("Non-directional graph\n"); Display_Array_Graph((Array_Graph*)Pointer_Graph_01); printf("\n\n"); printf("Directional graph\n"); Display_Array_Graph((Array_Graph*)Pointer_Graph_02); printf("\n\n"); printf("Directional weight graph\n"); Display_Array_Graph((Array_Graph*)Pointer_Graph_03); // free graph Delete_Array_Graph((Array_Graph*)Pointer_Graph_01); (Array_Graph*)Pointer_Graph_01 = NULL; Delete_Array_Graph((Array_Graph*)Pointer_Graph_02); (Array_Graph*)Pointer_Graph_02 = NULL; Delete_Array_Graph((Array_Graph*)Pointer_Graph_03); (Array_Graph*)Pointer_Graph_03 = NULL; return 0; } | cs |
0 개의 댓글:
댓글 쓰기