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

Linux Cross Reference
Tina4/src/sys/graph/cliques.c

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

  1 /**@(#)Clique finding in generic graph structures

  2  * cliques.c

  3  */
  4 
  5 #include <stdio.h>
  6 #include <tina/sys.h>
  7 #include <tina/graph.h>
  8 #include <tina/sysfuncs.h>
  9 
 10 static Viols_node *vn_alloc(Graph_node * gn)
 11 {
 12     Viols_node *vn;
 13 
 14     if (gn == NULL)
 15         return (NULL);
 16 
 17     vn = ts_ralloc(Viols_node);
 18     vn->gn = gn;
 19     vn->status = vn->label = 0;
 20     vn->viols = NULL;
 21     return (vn);
 22 }
 23 
 24 static Viols_node *choose_viols(Viols_node * vn)
 25 {
 26     return ((vn == NULL || vn->gn->status) ? NULL : vn);
 27 }
 28 
 29 static void set_violations(List * graph_list, List * viols_list)
 30 {
 31     List   *lptr;
 32 
 33     if (viols_list == NULL)
 34         return;
 35 
 36     graph_list_set_status(graph_list, 0);
 37 
 38     for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
 39     {
 40         Viols_node *vn;
 41 
 42         vn = (Viols_node *) lptr->to;   /* violation node */
 43         graph_list_set_status(vn->gn->cons, 1);
 44         vn->viols = list_copy(lptr->next, (void *(*) ()) choose_viols, NULL);
 45         graph_list_set_status(vn->gn->cons, 0);
 46     }
 47 }
 48 
 49 static int setviols(List * viols_list, int label)
 50 {
 51     int     count = 0;
 52     List   *lptr;
 53 
 54     for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
 55     {
 56         Viols_node *vn = (Viols_node *) lptr->to;
 57 
 58         if (!vn->label)
 59         {                       /* not currently set */
 60             vn->label = label;
 61             ++count;
 62         }
 63     }
 64     return (count);
 65 }
 66 
 67 static void resetviols(List * viols_list, int label)
 68 {
 69     List   *lptr;
 70 
 71     for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
 72     {
 73         Viols_node *vn = (Viols_node *) lptr->to;
 74 
 75         if (vn->label == label)
 76             vn->label = 0;
 77     }
 78 }
 79 
 80 static int check_viols(List * viols_list)
 81 {
 82     List   *lptr;
 83 
 84     for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
 85     {
 86         Viols_node *vn = (Viols_node *) lptr->to;
 87 
 88         if (!vn->label)
 89             return (1);
 90     }
 91     return (0);
 92 }
 93 
 94 static Graph_node *vn_pick_gn(Viols_node * vn)
 95 {
 96     return ((vn == NULL || vn->label) ? NULL : vn->gn);
 97 }
 98 
 99 static List *clique(List * viols_list)
100 {
101     List   *lptr;
102 
103     for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
104     {
105         Viols_node *vn = (Viols_node *) lptr->to;
106 
107         if (vn->status && !check_viols(vn->viols))
108             return (NULL);      /* unnecessary voluntary exclusion */
109     }
110 
111     return (list_copy(viols_list, (void *(*) ()) vn_pick_gn, NULL));
112 }
113 
114 static List *cliques(List * all, List * current, float tot, int label, float thres)
115 {
116     Viols_node *vn;
117 
118     if (current == NULL)
119     {
120         List   *new_clique;
121 
122         if (tot > thres && (new_clique = clique(all)) != NULL)
123             return (link_alloc((void *) new_clique, all->type));
124         else
125             return (NULL);
126     }
127     vn = (Viols_node *) current->to;
128 
129     if (vn->gn->bounded && tot + vn->gn->bound < thres)
130         return (NULL);
131 
132     if (!vn->label)
133     {                           /* not excluded */
134         if (setviols(vn->viols, label))
135         {
136             List   *list1;
137             List   *list2;
138 
139             list1 = cliques(all, current->next, tot + vn->gn->value, label + 1, thres);
140             resetviols(vn->viols, label);
141             vn->label = label;
142             vn->status = 1;
143             list2 = cliques(all, current->next, tot, label + 1, thres);
144             vn->label = vn->status = 0;
145             return (list_append(list1, list2));
146         }
147         return (cliques(all, current->next, tot + vn->gn->value, label + 1, thres));
148     }
149     return (cliques(all, current->next, tot, label + 1, thres));
150 }
151 
152 static void select_clique(List * viols_list)
153 {
154     List   *lptr;
155 
156     for (lptr = viols_list; lptr != NULL; lptr = lptr->next)
157     {
158         Viols_node *vn = (Viols_node *) lptr->to;
159 
160         vn->gn->status = !(vn->label);
161     }
162 }
163 
164 static float maxclique(List * all, List * current, float tot, int label, float maxc)
165 {
166     Viols_node *vn;
167 
168     if (current == NULL)
169     {
170         if (tot > maxc)
171         {
172             select_clique(all);
173             maxc = tot;
174         }
175         return (maxc);
176     }
177     vn = (Viols_node *) current->to;
178 
179     if (vn->gn->bounded == true && tot + vn->gn->bound < maxc)
180         return (maxc);
181 
182     if (!vn->label)
183     {                           /* not excluded */
184         if (setviols(vn->viols, label))
185         {
186             maxc = maxclique(all, current->next, tot + vn->gn->value, label + 1, maxc);
187             resetviols(vn->viols, label);
188             vn->label = label;
189             maxc = maxclique(all, current->next, tot, label + 1, maxc);
190             vn->label = 0;
191         } else
192             maxc = maxclique(all, current->next, tot + vn->gn->value, label + 1, maxc);
193     } else
194         maxc = maxclique(all, current->next, tot, label + 1, maxc);
195     return (maxc);
196 }
197 
198 List   *cliques_get(List * graph_list, int csize)       /* find all cliques >

199                                                          * csize */
200 /* list of graph nodes */
201 
202 {
203     List   *viols_list;         /* a parallel list structure */
204     List   *clique_list;
205 
206     viols_list = list_copy(graph_list, (void *(*) ()) vn_alloc, NULL);
207     set_violations(graph_list, viols_list);
208     clique_list = cliques(viols_list, viols_list, (float) 0.0, 1, (float) csize);
209     list_rm(viols_list, rfree);
210     return (clique_list);
211 }
212 
213 float   max_clique_get(List * graph_list)
214 /* list of graph nodes */
215 {
216     List   *viols_list;         /* a parallel list structure */
217     float   maxc;
218 
219     viols_list = list_copy(graph_list, (void *(*) ()) vn_alloc, NULL);
220     set_violations(graph_list, viols_list);
221     maxc = maxclique(viols_list, viols_list, (float) 0.0, 1, (float) 0.0);
222     list_rm(viols_list, rfree);
223     return (maxc);
224 }
225 

~ [ 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.