FrontISTR 5.2.0
Large-scale structural analysis program with finit element method
Loading...
Searching...
No Matches
hecmw_graph.c
Go to the documentation of this file.
1/*****************************************************************************
2 * Copyright (c) 2019 FrontISTR Commons
3 * This software is released under the MIT License, see LICENSE.txt
4 *****************************************************************************/
13#include "hecmw_graph.h"
14#include "hecmw_varray_int.h"
15#include "hecmw_malloc.h"
16#include "hecmw_config.h"
17#include "hecmw_util.h"
18#include <stdio.h>
19#include <errno.h>
20
21/*********************************
22 * Prototype of static functions *
23 *********************************/
24
27static void clear(struct hecmw_graph *graph
28 );
29
35static int find_edge(const struct hecmw_graph *graph,
36 int vert1,
37 int vert2,
38 int *idx
39 );
40
46static int add_edge_one_way(struct hecmw_graph *graph,
47 int vert1,
48 int vert2
49 );
50
51/**********************************
52 * Definition of public functions *
53 **********************************/
54
55int HECMW_graph_init(struct hecmw_graph *graph) {
56 graph->m_num_vertex = 0;
57 graph->m_num_edge = 0;
58 graph->m_edge_index =
59 (struct hecmw_varray_int *)HECMW_malloc(sizeof(struct hecmw_varray_int));
60 graph->m_edge_item =
61 (struct hecmw_varray_int *)HECMW_malloc(sizeof(struct hecmw_varray_int));
62 if (graph->m_edge_index == NULL || graph->m_edge_item == NULL) {
63 HECMW_set_error(errno, "");
64 return HECMW_ERROR;
65 }
68 return HECMW_SUCCESS;
69 graph->is_ref = 0;
70 return HECMW_ERROR;
71}
72
73int HECMW_graph_init_with_arrays(struct hecmw_graph *graph, int num_vertex,
74 int *edge_index, int *edge_item) {
75 graph->m_num_vertex = num_vertex;
76 graph->m_num_edge = edge_index[num_vertex];
77 graph->m_edge_index =
78 (struct hecmw_varray_int *)HECMW_malloc(sizeof(struct hecmw_varray_int));
79 graph->m_edge_item =
80 (struct hecmw_varray_int *)HECMW_malloc(sizeof(struct hecmw_varray_int));
81 if (graph->m_edge_index == NULL || graph->m_edge_item == NULL) {
82 HECMW_set_error(errno, "");
83 return HECMW_ERROR;
84 }
85 graph->m_edge_index->n_val = num_vertex + 1;
86 graph->m_edge_index->max_val = num_vertex + 1;
87 graph->m_edge_index->vals = edge_index;
88
89 graph->m_edge_item->n_val = graph->m_num_edge;
90 graph->m_edge_item->max_val = graph->m_num_edge;
91 graph->m_edge_item->vals = edge_item;
92
93 graph->is_ref = 1;
94 return HECMW_SUCCESS;
95}
96
97void HECMW_graph_finalize(struct hecmw_graph *graph) {
98 if (!graph->is_ref) {
101 }
102 HECMW_free(graph->m_edge_index);
103 HECMW_free(graph->m_edge_item);
104}
105
106void HECMW_graph_setNumVertex(struct hecmw_graph *graph, int num_vertex) {
107 HECMW_assert(!graph->is_ref);
108
109 graph->m_num_vertex = num_vertex;
110 HECMW_varray_int_resize(graph->m_edge_index, num_vertex + 1);
111 HECMW_varray_int_assign(graph->m_edge_index, 0, num_vertex + 1, 0);
112}
113
114int HECMW_graph_addEdge(struct hecmw_graph *graph, int vert1, int vert2) {
115 HECMW_assert(!graph->is_ref);
116
117 if (add_edge_one_way(graph, vert1, vert2) == HECMW_SUCCESS &&
118 add_edge_one_way(graph, vert2, vert1) == HECMW_SUCCESS)
119 return HECMW_SUCCESS;
120 return HECMW_ERROR;
121}
122
123void HECMW_graph_print(const struct hecmw_graph *graph, FILE *fp) {
124 const int *edge_index = HECMW_varray_int_get_cv(graph->m_edge_index);
125 const int *edge_item = HECMW_varray_int_get_cv(graph->m_edge_item);
126 int i, j;
127 int idx_start, idx_end;
128
129 fprintf(fp, "num_vertex = %d\n", graph->m_num_vertex);
130 fprintf(fp, "num_edge = %d\n", graph->m_num_edge);
131
132 for (i = 0; i < graph->m_num_vertex; i++) {
133 fprintf(fp, "%d: ", i);
134
135 idx_start = edge_index[i];
136 idx_end = edge_index[i + 1];
137 for (j = idx_start; j < idx_end; j++) {
138 fprintf(fp, " %d", edge_item[j]);
139 }
140 fprintf(fp, "\n");
141 }
142}
143
144int HECMW_graph_getNumVertex(const struct hecmw_graph *graph) {
145 return graph->m_num_vertex;
146}
147
148int HECMW_graph_getNumEdge(const struct hecmw_graph *graph) {
149 return graph->m_num_edge;
150}
151
152const int *HECMW_graph_getEdgeIndex(const struct hecmw_graph *graph) {
154}
155
156const int *HECMW_graph_getEdgeItem(const struct hecmw_graph *graph) {
158}
159
161 const struct hecmw_graph *refgraph, int num_part,
162 const int *parttab) {
163 const int *ref_edge_index = HECMW_varray_int_get_cv(refgraph->m_edge_index);
164 const int *ref_edge_item = HECMW_varray_int_get_cv(refgraph->m_edge_item);
165 int i, j, jj;
166 int i_part, j_part;
167 int start, end;
168 int retval;
169
170 struct hecmw_varray_int *lists;
171 size_t n_edge;
172 int *edge_index;
173 int *edge_item;
174
175 lists = (struct hecmw_varray_int *)HECMW_malloc(
176 sizeof(struct hecmw_varray_int) * num_part);
177 if (lists == NULL) {
178 HECMW_set_error(errno, "");
179 return HECMW_ERROR;
180 }
181 for (i = 0; i < num_part; i++) {
182 retval = HECMW_varray_int_init(lists + i);
183 if (retval != HECMW_SUCCESS) goto error;
184 }
185
186 for (i = 0; i < HECMW_graph_getNumVertex(refgraph); i++) {
187 i_part = parttab[i];
188 start = ref_edge_index[i];
189 end = ref_edge_index[i + 1];
190 for (j = start; j < end; j++) {
191 jj = ref_edge_item[j];
192 j_part = parttab[jj];
193 if (i_part == j_part) continue;
194 retval = HECMW_varray_int_append(lists + i_part, j_part);
195 if (retval != HECMW_SUCCESS) goto error;
196 retval = HECMW_varray_int_append(lists + j_part, i_part);
197 if (retval != HECMW_SUCCESS) goto error;
198 }
199 }
200
201 clear(graph);
202 HECMW_graph_setNumVertex(graph, num_part);
203 edge_index = HECMW_varray_int_get_v(graph->m_edge_index);
204
205 edge_index[0] = 0;
206 for (i = 0; i < num_part; i++) {
207 HECMW_varray_int_sort(lists + i);
208 HECMW_varray_int_uniq(lists + i);
209 n_edge = HECMW_varray_int_nval(lists + i);
210 edge_index[i + 1] = edge_index[i] + n_edge;
211 }
212 graph->m_num_edge = edge_index[num_part];
214 edge_item = HECMW_varray_int_get_v(graph->m_edge_item);
215 for (i = 0; i < num_part; i++) {
216 start = edge_index[i];
217 n_edge = HECMW_varray_int_nval(lists + i);
218 for (j = 0; j < n_edge; j++) {
219 edge_item[start + j] = HECMW_varray_int_get(lists + i, j);
220 }
221 }
222
223 for (i = 0; i < num_part; i++) {
224 HECMW_varray_int_finalize(lists + i);
225 }
226 HECMW_free(lists);
227 return HECMW_SUCCESS;
228
229error:
230 if (lists) {
231 for (i = 0; i < num_part; i++) {
232 HECMW_varray_int_finalize(lists + i);
233 }
234 HECMW_free(lists);
235 }
236 return HECMW_ERROR;
237}
238
239/***********************************
240 * Definition of private functions *
241 ***********************************/
242
243void clear(struct hecmw_graph *graph) {
244 graph->m_num_vertex = 0;
245 graph->m_num_edge = 0;
248 graph->is_ref = 0;
249}
250
251int find_edge(const struct hecmw_graph *graph, int vert1, int vert2, int *idx) {
252 const int *edge_index = HECMW_varray_int_get_cv(graph->m_edge_index);
253 const int *edge_item = HECMW_varray_int_get_cv(graph->m_edge_item);
254 int idx_start, idx_end;
255 int i;
256
257 idx_start = edge_index[vert1];
258 idx_end = edge_index[vert1 + 1];
259 for (i = idx_start; i < idx_end; i++) {
260 if (edge_item[i] == vert2) {
261 if (idx) *idx = i;
262 return 1;
263 }
264 }
265 return 0;
266}
267
268int add_edge_one_way(struct hecmw_graph *graph, int vert1, int vert2) {
269 int *edge_index = HECMW_varray_int_get_v(graph->m_edge_index);
270 int idx;
271 int i;
272 int retval;
273
274 HECMW_assert(!graph->is_ref);
275
276 if (find_edge(graph, vert1, vert2, &idx)) {
277 return HECMW_SUCCESS;
278 }
279 /* insert vert2 into m_edge_item */
280 /* place to insert: m_edge_inidex[vert1 + 1] */
281 retval =
282 HECMW_varray_int_insert(graph->m_edge_item, edge_index[vert1 + 1], vert2);
283 if (retval != HECMW_SUCCESS) {
284 return HECMW_ERROR;
285 }
286
287 /* increment m_edge_index[vert1 + 1 .. n_num_vertex] */
288 for (i = vert1 + 1; i <= graph->m_num_vertex; i++) {
289 edge_index[i] += 1;
290 }
291 graph->m_num_edge++;
292 return HECMW_SUCCESS;
293}
#define HECMW_ERROR
Definition: hecmw_config.h:66
#define HECMW_SUCCESS
Definition: hecmw_config.h:64
int HECMW_set_error(int errorno, const char *fmt,...)
Definition: hecmw_error.c:37
int HECMW_graph_degeneGraph(struct hecmw_graph *graph, const struct hecmw_graph *refgraph, int num_part, const int *parttab)
Definition: hecmw_graph.c:160
const int * HECMW_graph_getEdgeIndex(const struct hecmw_graph *graph)
Definition: hecmw_graph.c:152
const int * HECMW_graph_getEdgeItem(const struct hecmw_graph *graph)
Definition: hecmw_graph.c:156
int HECMW_graph_getNumEdge(const struct hecmw_graph *graph)
Definition: hecmw_graph.c:148
int HECMW_graph_addEdge(struct hecmw_graph *graph, int vert1, int vert2)
Definition: hecmw_graph.c:114
int HECMW_graph_getNumVertex(const struct hecmw_graph *graph)
Definition: hecmw_graph.c:144
void HECMW_graph_print(const struct hecmw_graph *graph, FILE *fp)
Definition: hecmw_graph.c:123
void HECMW_graph_finalize(struct hecmw_graph *graph)
Definition: hecmw_graph.c:97
void HECMW_graph_setNumVertex(struct hecmw_graph *graph, int num_vertex)
Definition: hecmw_graph.c:106
int HECMW_graph_init_with_arrays(struct hecmw_graph *graph, int num_vertex, int *edge_index, int *edge_item)
Definition: hecmw_graph.c:73
int HECMW_graph_init(struct hecmw_graph *graph)
Definition: hecmw_graph.c:55
Graph utility.
#define NULL
#define HECMW_free(ptr)
Definition: hecmw_malloc.h:24
#define HECMW_malloc(size)
Definition: hecmw_malloc.h:20
#define HECMW_assert(cond)
Definition: hecmw_util.h:40
size_t HECMW_varray_int_nval(const struct hecmw_varray_int *varray)
size_t HECMW_varray_int_uniq(struct hecmw_varray_int *varray)
const int * HECMW_varray_int_get_cv(const struct hecmw_varray_int *varray)
void HECMW_varray_int_sort(struct hecmw_varray_int *varray)
int HECMW_varray_int_insert(struct hecmw_varray_int *varray, size_t index, int val)
int * HECMW_varray_int_get_v(struct hecmw_varray_int *varray)
int HECMW_varray_int_get(const struct hecmw_varray_int *varray, size_t index)
int HECMW_varray_int_init(struct hecmw_varray_int *varray)
int HECMW_varray_int_assign(struct hecmw_varray_int *varray, size_t begin, size_t end, int val)
void HECMW_varray_int_finalize(struct hecmw_varray_int *varray)
int HECMW_varray_int_append(struct hecmw_varray_int *varray, int value)
int HECMW_varray_int_resize(struct hecmw_varray_int *varray, size_t len)
int m_num_vertex
Definition: hecmw_graph.h:24
int m_num_edge
Definition: hecmw_graph.h:25
struct hecmw_varray_int * m_edge_item
Definition: hecmw_graph.h:28
struct hecmw_varray_int * m_edge_index
Definition: hecmw_graph.h:26