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