1 /*
2 * This file is part of the RingDecomposerLib, licensed
3 * under BSD New license (see LICENSE in the root directory).
4 * Copyright (c) 2016
5 * University of Hamburg, ZBH - Center for Bioinformatics
6 * Niek Andresen, Florian Flachsenberg, Matthias Rarey
7 *
8 * Please cite:
9 *
10 * Kolodzik, A.; Urbaczek, S.; Rarey, M.
11 * Unique Ring Families: A Chemically Meaningful Description
12 * of Molecular Ring Topologies.
13 * J. Chem. Inf. Model., 2012, 52 (8), pp 2013-2021
14 *
15 * Flachsenberg, F.; Andresen, N.; Rarey, M.
16 * RingDecomposerLib: An Open-Source Implementation of
17 * Unique Ring Families and Other Cycle Bases.
18 * J. Chem. Inf. Model., 2017, 57 (2), pp 122-126
19 */
20
21 #include "RDLgraph.h"
22
23 #include <assert.h>
24 #include <limits.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27
28 #include "RDLutility.h"
29
30 /** initializes a new graph with the value |V| and the array degree, then
31 allocates enough space for 'adjList', so that they can be filled.
32 E is set to 0, edges are added later.*/
RDL_initGraph(RDL_graph * gra,unsigned V,unsigned * degree,char owns_edges)33 static void RDL_initGraph(RDL_graph *gra, unsigned V, unsigned *degree, char owns_edges)
34 {
35 unsigned i;
36 RDL_edge **adjList;
37
38 gra->V = V;
39 gra->E = 0;
40 gra->degree = degree;
41
42 adjList = malloc(V * sizeof(*adjList));
43 for(i=0; i<V; ++i)
44 {
45 if(degree[i] > 0)
46 {
47 adjList[i] = malloc(degree[i] * sizeof(**adjList));
48 }
49 }
50 gra->adjList = adjList;
51
52 if (owns_edges) {
53 gra->edgesAlloced = 64;
54 gra->edges = malloc(gra->edgesAlloced * sizeof(*gra->edges));
55 }
56 else {
57 gra->edgesAlloced = 0;
58 gra->edges = NULL;
59 }
60 }
61
RDL_DFSvisit(const RDL_graph * gra,unsigned vertex,char * visited)62 static void RDL_DFSvisit(const RDL_graph *gra, unsigned vertex, char *visited)
63 {
64 unsigned i,j;
65 for(i=0; i<gra->degree[vertex]; ++i)
66 {
67 j = gra->adjList[vertex][i][0];
68 if(visited[j] == 0)
69 {
70 visited[j] = 1;
71 RDL_DFSvisit(gra,j,visited);
72 }
73 }
74 }
75
76 /** returns 1 if the graph is connected, 0 otherwise. uses DFS */
RDL_checkGraphConnected(const RDL_graph * gra)77 char RDL_checkGraphConnected(const RDL_graph *gra)
78 {
79 unsigned i;
80 char *visited;
81 char result;
82 result = 1;
83 visited = malloc(gra->V * sizeof(*visited));
84 visited[0] = 1; /*start vertex*/
85 for(i=1; i<gra->V; ++i)
86 {
87 visited[i] = 0; /*unvisited*/
88 }
89 RDL_DFSvisit(gra, 0, visited);
90 for(i=0; i<gra->V; ++i)
91 {
92 if(visited[i] == 0) /*one was unvisited*/
93 {
94 result = 0;
95 break;
96 }
97 }
98
99 free(visited);
100 return result;
101 }
102
103 /* if nodes are adjacent */
RDL_isAdj(const RDL_graph * graph,unsigned i,unsigned j)104 int RDL_isAdj(const RDL_graph *graph, unsigned i, unsigned j)
105 {
106 unsigned idx;
107 for(idx=0; idx<graph->degree[i]; ++idx)
108 {
109 if(graph->adjList[i][idx][0] == j)
110 {
111 return 1;
112 }
113 }
114 return 0;
115 }
116
RDL_deleteGraph(RDL_graph * gra)117 void RDL_deleteGraph(RDL_graph *gra)
118 {
119 unsigned i;
120 assert(gra != NULL);
121 if(gra->edges)
122 {
123 for(i=0; i<gra->E; ++i)
124 {
125 free(gra->edges[i]);
126 }
127 free(gra->edges);
128 }
129 for(i=0; i<gra->V; ++i)
130 {
131 if(gra->degree[i] > 0)
132 {
133 free(gra->adjList[i]);
134 }
135 }
136 free(gra->adjList);
137 free(gra->degree);
138 free(gra);
139 }
140
RDL_printGraph(const RDL_graph * graph)141 void RDL_printGraph(const RDL_graph *graph)
142 {
143 unsigned i,j;
144
145 printf("|V|=%d, |E|=%d\n",graph->V,graph->E);
146 for(i=0; i<graph->V; ++i)
147 {
148 printf("%d: ",i);
149 for(j=0; j<graph->degree[i]; ++j)
150 {
151 printf("%d ",graph->adjList[i][j][0]);
152 }
153 printf("\n");
154 }
155 if(graph->edges)/*undirected*/
156 {
157 printf("edges:\n");
158 for(i=0; i<graph->E; ++i)
159 {
160 printf("%d: [%d,%d]\n", i, graph->edges[i][0], graph->edges[i][1]);
161 }
162 }
163 }
164
RDL_initNewGraph_g(unsigned V,char owns_edges)165 RDL_graph *RDL_initNewGraph_g(unsigned V, char owns_edges)
166 {
167 RDL_graph *graph = malloc(sizeof(*graph));
168 unsigned *degree;
169 unsigned i;
170 degree = malloc(V * sizeof(*degree));
171 for(i=0; i<V; ++i)
172 {
173 degree[i] = 0;
174 }
175 RDL_initGraph(graph,V,degree,owns_edges);
176
177 return graph;
178 }
179
RDL_addEdge(RDL_graph * gra,unsigned from,unsigned to)180 void RDL_addEdge(RDL_graph *gra, unsigned from, unsigned to)
181 {
182 unsigned i;
183
184 /* loops */
185 if (from == to) {
186 return;
187 }
188
189 for(i=0; i<gra->degree[from]; ++i) {
190 if(gra->adjList[from][i][0] == to) {
191 /*edge already exists*/
192 return;
193 }
194 }
195 ++gra->E;
196 ++gra->degree[from];
197 if(gra->degree[from] == 1)/*was 0, has never been initialized*/
198 {
199 gra->adjList[from] = malloc(gra->degree[from] * sizeof(*gra->adjList[from]));
200 }
201 else
202 {
203 gra->adjList[from] = realloc(gra->adjList[from], gra->degree[from] *
204 sizeof(*gra->adjList[from]));
205 }
206 gra->adjList[from][ gra->degree[from]-1 ][0] = to;
207 }
208
RDL_addToEdgeArray(RDL_graph * gra,unsigned from,unsigned to)209 static unsigned RDL_addToEdgeArray(RDL_graph *gra, unsigned from, unsigned to)
210 {
211 unsigned temp;
212 if(from > to)
213 {
214 temp = from;
215 from = to;
216 to = temp;
217 }
218 if(gra->E == gra->edgesAlloced)
219 {
220 gra->edgesAlloced *= 2;
221 gra->edges = realloc(gra->edges, gra->edgesAlloced * sizeof(*gra->edges));
222 }
223 gra->edges[gra->E-1] = malloc(2 * sizeof(**gra->edges));
224 gra->edges[gra->E-1][0] = from;
225 gra->edges[gra->E-1][1] = to;
226
227 return gra->E-1;
228 }
229
RDL_addUEdge_g(RDL_graph * gra,unsigned from,unsigned to)230 unsigned RDL_addUEdge_g(RDL_graph *gra, unsigned from, unsigned to)
231 {
232 unsigned edge_id, i;
233
234 if(from >= gra->V || to >= gra->V) {
235 RDL_outputFunc(RDL_ERROR, "Tried to add an edge with atoms not in range.\n");
236 RDL_outputFunc(RDL_ERROR, "edge (%u,%u) can not be added to graph with %u atoms.\n",
237 from, to, gra->V);
238 return RDL_INVALID_RESULT;
239 }
240
241 if (from == to) {
242 RDL_outputFunc(RDL_WARNING, "Adding a loop is not allowed, node %u\n", from);
243 return RDL_INVALID_RESULT;
244 }
245
246 for(i=0; i<gra->degree[from]; ++i) {
247 if(gra->adjList[from][i][0] == to) {
248 /*edge already exists*/
249 return RDL_DUPLICATE_EDGE;
250 }
251 }
252 RDL_addEdge(gra, from, to);
253 RDL_addEdge(gra, to, from);
254 --gra->E; /*was incremented twice*/
255
256 edge_id = RDL_addToEdgeArray(gra, from, to);
257
258 gra->adjList[from][gra->degree[from]-1][1] = edge_id;
259 gra->adjList[to][gra->degree[to]-1][1] = edge_id;
260
261 return edge_id;
262 }
263
RDL_edgeId(const RDL_graph * gra,unsigned from,unsigned to)264 unsigned RDL_edgeId(const RDL_graph *gra, unsigned from, unsigned to)
265 {
266 unsigned j, edge;
267
268 if(from > to) {
269 /*swap order to make from < to*/
270 edge = to;
271 to = from;
272 from = edge;
273 }
274
275 edge = RDL_INVALID_RESULT;
276
277 for(j=0; j<gra->degree[from]; ++j) {
278 if(gra->adjList[from][j][0] == to) {
279 edge = gra->adjList[from][j][1];
280 break;
281 }
282 }
283
284 return edge;
285 }
286