~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina5/tina-libs/tina/sys/sysGph_cliques.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /**********
  2  * 
  3  * Copyright (c) 2003, Division of Imaging Science and Biomedical Engineering,
  4  * University of Manchester, UK.  All rights reserved.
  5  * 
  6  * Redistribution and use in source and binary forms, with or without modification, 
  7  * are permitted provided that the following conditions are met:
  8  * 
  9  *   . Redistributions of source code must retain the above copyright notice, 
 10  *     this list of conditions and the following disclaimer.
 11  *    
 12  *   . Redistributions in binary form must reproduce the above copyright notice,
 13  *     this list of conditions and the following disclaimer in the documentation 
 14  *     and/or other materials provided with the distribution.
 15  * 
 16  *   . Neither the name of the University of Manchester nor the names of its
 17  *     contributors may be used to endorse or promote products derived from this 
 18  *     software without specific prior written permission.
 19  * 
 20  * 
 21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 22  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 25  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 31  * POSSIBILITY OF SUCH DAMAGE.
 32  *
 33  **********
 34  * 
 35  * Program :    TINA
 36  * File    :  $Source: /home/tina/cvs/tina-libs/tina/sys/sysGph_cliques.c,v $
 37  * Date    :  $Date: 2003/09/22 16:09:02 $
 38  * Version :  $Revision: 1.4 $
 39  * CVS Id  :  $Id: sysGph_cliques.c,v 1.4 2003/09/22 16:09:02 tony Exp $
 40 */
 41 /**
 42  *  @file  Clique finding in generic graph structures, used specifically in the 
 43  *  wireframe model matcher.
 44  *
 45  *********
 46 */
 47 
 48 #include "sysGph_cliques.h"
 49 
 50 #if HAVE_CONFIG_H
 51   #include <config.h>
 52 #endif
 53 
 54 #include <stdio.h>
 55 #include <tina/sys/sys_GphDef.h>
 56 #include <tina/sys/sys_LstDef.h>
 57 #include <tina/sys/sys_MemDef.h>
 58 #include <tina/sys/sysLst_list.h>
 59 #include <tina/sys/sysMem_ralloc.h>
 60 #include <tina/sys/sysGph_graph.h>
 61 
 62 
 63 static Viols_node *vn_alloc(Graph_node * gn)
 64 {
 65         Viols_node *vn;
 66 
 67         if (gn == NULL)
 68                 return (NULL);
 69 
 70         vn = ts_ralloc(Viols_node);
 71         vn->gn = gn;
 72         vn->status = vn->label = 0;
 73         vn->viols = NULL;
 74         return (vn);
 75 }
 76 
 77 static Viols_node *choose_viols(Viols_node * vn)
 78 {
 79         return ((vn == NULL || vn->gn->status) ? NULL : vn);
 80 }
 81 
 82 static void set_violations(List * graph_list, List * viols_list)
 83 {
 84         List *lptr;
 85 
 86         if (viols_list == NULL)
 87                 return;
 88 
 89         graph_list_set_status(graph_list, 0);
 90 
 91         for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
 92 
 93         {
 94                 Viols_node *vn;
 95 
 96                 vn = (Viols_node *) lptr->to;   /* violation node */
 97                 graph_list_set_status(vn->gn->cons, 1);
 98                 vn->viols = list_copy(lptr->next, (void *(*)()) choose_viols, NULL);
 99                 graph_list_set_status(vn->gn->cons, 0);
100         }
101 }
102 
103 static int setviols(List * viols_list, int label)
104 {
105         int count = 0;
106         List *lptr;
107 
108         for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
109 
110         {
111                 Viols_node *vn = (Viols_node *) lptr->to;
112 
113                 if (!vn->label)
114 
115                 {                                                                                                               /* not currently set */
116                         vn->label = label;
117                         ++count;
118                 }
119         }
120         return (count);
121 }
122 
123 static void resetviols(List * viols_list, int label)
124 {
125         List *lptr;
126 
127         for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
128 
129         {
130                 Viols_node *vn = (Viols_node *) lptr->to;
131 
132                 if (vn->label == label)
133                         vn->label = 0;
134         }
135 }
136 
137 static int check_viols(List * viols_list)
138 {
139         List *lptr;
140 
141         for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
142 
143         {
144                 Viols_node *vn = (Viols_node *) lptr->to;
145 
146                 if (!vn->label)
147                         return (1);
148         }
149         return (0);
150 }
151 
152 static Graph_node *vn_pick_gn(Viols_node * vn)
153 {
154         return ((vn == NULL || vn->label) ? NULL : vn->gn);
155 }
156 
157 static List *clique(List * viols_list)
158 {
159         List *lptr;
160 
161         for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
162 
163         {
164                 Viols_node *vn = (Viols_node *) lptr->to;
165 
166                 if (vn->status && !check_viols(vn->viols))
167                         return (NULL);                                          /* unnecessary voluntary exclusion */
168         }
169 
170         return (list_copy(viols_list, (void *(*)()) vn_pick_gn, NULL));
171 }
172 
173 static List *cliques(List * all, List * current, float tot, int label,
174                                                                                  float thres)
175 {
176         Viols_node *vn;
177 
178         if (current == NULL)
179 
180         {
181                 List *new_clique;
182 
183                 if (tot > thres && (new_clique = clique(all)) != NULL)
184                         return (link_alloc((void *) new_clique, all->type));
185 
186                 else
187                         return (NULL);
188         }
189         vn = (Viols_node *) current->to;
190 
191         if (vn->gn->bounded && tot + vn->gn->bound < thres)
192                 return (NULL);
193 
194         if (!vn->label)
195 
196         {                                                                                                                       /* not excluded */
197                 if (setviols(vn->viols, label))
198 
199                 {
200                         List *list1;
201                         List *list2;
202 
203                         list1 =
204                                         cliques(all, current->next, tot + vn->gn->value, label + 1,
205                                                                         thres);
206                         resetviols(vn->viols, label);
207                         vn->label = label;
208                         vn->status = 1;
209                         list2 = cliques(all, current->next, tot, label + 1, thres);
210                         vn->label = vn->status = 0;
211                         return (list_append(list1, list2));
212                 }
213                 return (cliques
214                                                 (all, current->next, tot + vn->gn->value, label + 1, thres));
215         }
216         return (cliques(all, current->next, tot, label + 1, thres));
217 }
218 
219 static void select_clique(List * viols_list)
220 {
221         List *lptr;
222 
223         for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
224 
225         {
226                 Viols_node *vn = (Viols_node *) lptr->to;
227 
228                 vn->gn->status = !(vn->label);
229         }
230 }
231 
232 static float maxclique(List * all, List * current, float tot, int label,
233                                                                                          float maxc)
234 {
235         Viols_node *vn;
236 
237         if (current == NULL)
238 
239         {
240                 if (tot > maxc)
241 
242                 {
243                         select_clique(all);
244                         maxc = tot;
245                 }
246                 return (maxc);
247         }
248         vn = (Viols_node *) current->to;
249 
250         if (vn->gn->bounded == true && tot + vn->gn->bound < maxc)
251                 return (maxc);
252 
253         if (!vn->label)
254 
255         {                                                                                                                       /* not excluded */
256                 if (setviols(vn->viols, label))
257 
258                 {
259                         maxc =
260                                         maxclique(all, current->next, tot + vn->gn->value, label + 1,
261                                                                                 maxc);
262                         resetviols(vn->viols, label);
263                         vn->label = label;
264                         maxc = maxclique(all, current->next, tot, label + 1, maxc);
265                         vn->label = 0;
266                 } else
267                         maxc =
268                                         maxclique(all, current->next, tot + vn->gn->value, label + 1,
269                                                                                 maxc);
270         } else
271                 maxc = maxclique(all, current->next, tot, label + 1, maxc);
272         return (maxc);
273 }
274 
275 List *cliques_get(List * graph_list, int csize) /* find all cliques >
276                                                                                                                                                                                                  * 
277                                                                                                                                                                                                  * * * csize */
278 /* list of graph nodes */
279 {
280         List *viols_list;                                                       /* a parallel list structure */
281         List *clique_list;
282 
283         viols_list = list_copy(graph_list, (void *(*)()) vn_alloc, NULL);
284         set_violations(graph_list, viols_list);
285         clique_list =
286                         cliques(viols_list, viols_list, (float) 0.0, 1, (float) csize);
287         list_rm(viols_list, rfree);
288         return (clique_list);
289 }
290 
291 float max_clique_get(List * graph_list)
292 /* list of graph nodes */
293 {
294         List *viols_list;                                                       /* a parallel list structure */
295         float maxc;
296 
297         viols_list = list_copy(graph_list, (void *(*)()) vn_alloc, NULL);
298         set_violations(graph_list, viols_list);
299         maxc = maxclique(viols_list, viols_list, (float) 0.0, 1, (float) 0.0);
300         list_rm(viols_list, rfree);
301         return (maxc);
302 }
303 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.