1:
2:/*
3: * $Id: concept.c,v 1.1 2002/10/15 10:06:44 koschke Exp $
4: *
5: * CONCEPTS
6: * Copyright (C) 1994 Technical University of Braunschweig, Germany
7: * Written by Christian Lindig (lindig@ips.cs.tu-bs.de)
8: *
9: * This program is free software; you can redistribute it and/or modify
10: * it under the terms of the GNU General Public License as published by
11: * the Free Software Foundation; either version 2 of the License, or
12: * (at your option) any later version.
13: *
14: * This program is distributed in the hope that it will be useful,
15: * but WITHOUT ANY WARRANTY; without even the implied warranty of
16: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17: * GNU General Public License for more details.
18: *
19: * You should have received a copy of the GNU General Public License
20: * along with this program; if not, write to the Free Software
21: * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22: *
23: *
24: * Functions for calculating concepts from a relation.
25: */
26:
27:#include "config.h"
28:#include <stdio.h>
29:#if defined(STDC_HEADERS) || defined(HAVE_STDLIB_H)
30:# include <stdlib.h>
31:#endif
32:#ifdef DBMALLOC
33:# include <malloc.h>
34:#endif
35:
36:#include "defines.h"
37:#include "panic.h"
38:#include "list.h"
39:#include "set.h"
40:#include "relation.h"
41:#include "concept.h"
42:
43:/* requires: ListDelete ListGetValue ListInit ListNewEntry
44: ListSetValue RelAtr RelObj SetAdd SetCopy SetDelete SetFirst
45: SetFull SetInit SetIntersect SetJoin SetLe SetMember SetMinus
46: SetNew SetNext SetPrint SetRemove SetSubset free malloc panic
47: printf */
48:
49:
50:/*
51: * ConceptExtent
52: *
53: * from a Set of attributes calculate the extent - a Set of objects -
54: * with respect to a given relation of objects and attributes.
55: * <result> must be of the right size, i.e. context->maxobj and must
56: * be initalized (using SetNew()). The extent of a set of attributes
57: * is the set of objects they have in common. A better name would have
58: * been ConceptCommonAtr or similar */
59:
60:static VOID
61:ConceptExtent (result,attrib,context)
62:
63: Set *result,*attrib;
64: Relation *context;
65:{
66: int a ; /* attribute */
67: Set *obj ; /* objects related to given attrib */
68:
69: if (context->maxobj != result->size ||
70: context->maxatr != attrib->size) {
71: panic ("Size mismatch in %s:%i",__FILE__,__LINE__) ;
72: }
73:
74: SetFull (result) ; /* all obj present before intersect */
75:
76: /* visit all attributes and intersect the related object sets */
77:
78: a = SetFirst (attrib) ;
79: while (a != -1) {
80: /* intersect the object sets from the attributes given
81: in attrib */
82: obj = RelAtr(context,a) ; /* obj related to attrib a */
83: SetIntersect (result,obj,result); /* intersect sets */
84: a = SetNext(attrib,a) ; /* visit next attrib */
85:
86: }
87:}
88:
89:/*
90: * ConceptIntent
91: *
92: * From a Set of objects calculate the intent - a Set of attributes -
93: * with respect to a given relation. The resulting Set of attributes
94: * must be oft the right size and must be initialized (using
95: * SetNew())! The intent is the set of attributes the objects have in
96: * common. The name is misleading */
97:
98:VOID
99:ConceptIntent (result,obj,context)
100:
101: Set *result,*obj;
102: Relation *context;
103:{
104: int o ; /* object of intreset */
105: Set *atr ; /* set of attributes */
106:
107: if (context->maxatr != result->size ||
108: context->maxobj != obj->size) {
109: panic ("Size mismatch in %s:%i",__FILE__,__LINE__) ;
110: }
111:
112: SetFull (result) ; /* all attributes present */
113:
114: o = SetFirst (obj) ; /* visit all objects and intersect attrs */
115: while (o != -1) {
116:
117: atr = RelObj(context,o) ; /* attr related to obj o */
118: SetIntersect (result,atr,result);
119: o = SetNext(obj,o) ; /* next object */
120: }
121:}
122:
123:/*
124: * ConceptCExtent
125: *
126: * From a set of objects calculate the closed extent:
127: * close_extent=extent(intent(obj)) - a set of objects with respect
128: * to a given relation. The result will be stored in <result>. To a
129: * closed extent there also exists a set of attributes which is stored
130: * in <atr>. <result> and <atr> together form a concept. The Sets
131: * <result> and <atr> must be of the right size and must be existent
132: * (SetNew()). */
133:
134:static VOID
135:ConceptCExtent (result,obj,atr,context)
136:
137: Set *result,*obj,*atr;
138: Relation *context ;
139:{
140:
141: if (obj->size != result->size ||
142: obj->size != context->maxobj ||
143: atr->size != context->maxatr) {
144: panic ("Size mismatch in %s:%i",__FILE__,__LINE__) ;
145: }
146: ConceptIntent (atr,obj,context) ;
147: ConceptExtent (result,atr,context);
148:}
149:
150:
151:/*
152: * ConceptFirstExtent
153: *
154: * Calculate the first concept (closed extent) from with respect to a
155: * given relation <context> and store it to <result> - a Set of
156: * objects. The corresponding Set of attributes will be stored in
157: * <atr>. returns 1 (for convienience) because there allways exists a
158: * first concept */
159:
160:static int
161:ConceptFirstExtent (result,atr,context)
162:
163: Set *result,*atr;
164: Relation *context;
165:
166:{
167: Set objects ;
168:
169: if (result->size != context->maxobj ||
170: atr->size != context->maxatr) {
171: panic ("Size mismatch in %s:%i",__FILE__,__LINE__) ;
172: }
173:
174: SetNew (&objects,context->maxobj) ;
175: /*
176: * object is empty - the first concept has an empty object.
177: */
178: ConceptCExtent (result,&objects,atr,context);
179: SetDelete(&objects);
180: return 1;
181:}
182:
183:/*
184: * ConceptNextExtent
185: *
186: * from a set of given objects <old> calculate the next concept
187: * consisting of a set of objects <new> and a set of attributes <atr>
188: * with respect to <context>. <new> and <atr> must be of the right size.
189: *
190: * This function implements Ganter's algorithm to compute the next
191: * intent as presented in : B. Ganther, R. Wille, K.E. Wolff (Eds.),
192: * Beitraege zur Begriffsanalyse (Contributions to Concept Analysis),
193: * 1987,BI-Wissenschafts-Verlag, Mannheim, Germany
194: *
195: *
196: * Returns 1 if a next <new>,<atr> pair was found, 0 otherwise */
197:
198:static int
199:ConceptNextExtent (old,new,atr,context)
200:
201: Set *old,*new,*atr;
202: Relation *context ;
203:
204:{
205: Set objects; /* holds candidate for next concept */
206: int found ; /* candidate found? */
207: int o ; /* object */
208:
209: if (old->size != new->size ||
210: old->size != context->maxobj ||
211: atr->size != context->maxatr) {
212: panic ("Size mismatch in %s:%i",__FILE__,__LINE__) ;
213: }
214:
215: found = 0 ;
216: o = context->maxobj - 1 ; /* start with highest object */
217:
218: SetInit(&objects); /* remember <old> in objects */
219: SetCopy(old,&objects);
220:
221: while (!found && (o>=0)) {
222: if (!SetMember(&objects,o)) {
223: SetAdd(&objects,o);
224: ConceptCExtent(new,&objects,atr,context);
225: found = SetLe (&objects,new,o);
226: }
227: SetRemove(&objects,o);
228: o-- ; /* check next object */
229: }
230: SetDelete (&objects); /* delete candidate */
231: return found ;
232:}
233:
234:/*
235: * ConceptInit
236: *
237: * initialize a Concept structure which will be derived from the
238: * relation <rel>. */
239:
240:VOID
241:ConceptInit (c,rel)
242:
243: Concept *c;
244: Relation *rel;
245:
246:{
247: SetNew(&c->objects, rel->maxobj);
248: SetNew(&c->attributes, rel->maxatr);
249:
250: SetInit (&c->obj);
251: SetInit (&c->atr);
252:
253: SetInit(&c->subconcepts); /* size not known yet */
254: SetInit(&c->closure); /* size not known yet */
255:
256: SetInit(&c->superclos); /* size unknown */
257:}
258:
259:/*
260: * ConceptDelete
261: *
262: * Remove a concept from memory. Does not free the struct <c> itself. */
263:
264:VOID
265:ConceptDelete (c)
266:
267: Concept *c;
268:{
269: SetDelete(&c->objects);
270: SetDelete(&c->attributes);
271:
272: SetDelete(&c->obj);
273: SetDelete(&c->atr);
274:
275: SetDelete(&c->subconcepts);
276: SetDelete(&c->closure);
277: SetDelete(&c->superclos);
278:}
279:
280:
281:/*
282: * ConceptPrint
283: * prints out a concept - just for debugging
284: */
285:
286:VOID
287:ConceptPrint (c)
288:
289: Concept *c;
290:{
291: printf ("\nconcept-objects:\n");
292: SetPrint (&c->objects);
293: printf ("\nconcept-attributes:\n");
294: SetPrint (&c->attributes);
295:
296: printf ("\nconcept-obj:\n");
297: SetPrint (&c->obj);
298: printf ("\nconcept-atr:\n");
299: SetPrint (&c->atr);
300:
301: printf ("\nconcept-subconcepts:\n");
302: SetPrint (&c->subconcepts);
303: printf ("\nconcept-closure:\n");
304: SetPrint (&c->closure);
305:
306: printf ("\nconcept-super-closure:\n");
307: SetPrint (&c->superclos);
308:
309: printf ("\n");
310:}
311:
312:/*
313: * ConceptArrayInit
314: *
315: * set an ConceptArray to defined values. Once all concepts have been
316: * calculated it's possible to store them in a ConceptArray */
317:
318:VOID
319:ConceptArrayInit (array)
320:
321: ConceptArray *array ;
322:
323:{
324: array->size = 0;
325: array->concepts = (Concept**) NULL ;
326:
327:}
328:
329:/*
330: * ConceptArrayDelete
331: *
332: * free all memory associated with an ConceptArray */
333:
334:VOID
335:ConceptArrayDelete (array)
336:
337: ConceptArray *array ;
338:
339:{
340: int i;
341:
342: if (array->size == 0 || !array->concepts) {
343: panic ("empty array in %s:%i",__FILE__,__LINE__) ;
344: }
345: for (i=0;i<array->size;i++) {
346: ConceptDelete(array->concepts[i]);
347: free ((char*)array->concepts[i]); /* free Concept struct */
348: }
349: free ((char*) array->concepts); /* free pointer array */
350: array->concepts = (Concept**) NULL ;
351:
352:}
353:
354:/*
355: * ConceptLattice
356: *
357: * calculate a concept lattice from a given relation. All concepts are
358: * stored in a ConceptArray <lattice>. Because the cumber of concepts
359: * is not known in advance they are internally stored in a list before
360: * the array is built.
361: *
362: * The concept lattice is returned as an array of concepts which are
363: * ordered in this way: the top has index 0, the bottom the greates
364: * index. In general a subconcept has a higher index than all its
365: * superconcepts */
366:
367:VOID
368:ConceptLattice (rel,lattice)
369:
370: Relation *rel;
371: ConceptArray *lattice;
372:
373:{
374: int more ; /* flag */
375: List list ; /* will be list of Concepts */
376: ListEntry *entry; /* list entry to hold concept */
377: Concept *prev,*new; /* previos and actual concept */
378: Concept **array, **tmp ;
379:
380: ListInit (&list);
381: prev = (Concept*) malloc (sizeof(Concept));
382: if (!prev) {
383: panic ("malloc failed in %s:%i",__FILE__,__LINE__) ;
384: }
385:
386: ConceptInit (prev,rel); /* initialize */
387: ConceptFirstExtent (&prev->objects,&prev->attributes,rel);
388: do {
389: /* enter to list */
390: entry = ListNewEntry (&list);
391: ListSetValue(entry,(char*)prev);
392:
393: /* calculate next concept */
394:
395: new = (Concept*) malloc (sizeof(Concept));
396: if (!new) {
397: panic ("malloc failed in %s:%i",__FILE__,__LINE__) ;
398: }
399: ConceptInit (new,rel);
400: more = ConceptNextExtent(&prev->objects, &new->objects,
401: &new->attributes, rel);
402: prev = new ;
403: } while (more) ;
404:
405: /* we malloced one Concept too often - the data computed by the
406: last ConceptNextExtent call is garbage */
407:
408: ConceptDelete (new); /* not needed - stuff from ConceptInit()*/
409: free ((char*)new); /* not needed - Concept struct */
410:
411: /* now all concepts are stored in list - we will now build up
412: an array of concepts and can throw away the list (not its
413: contents) */
414:
415: /* new will point now to a an array of Concept pointers */
416:
417: array = (Concept**) malloc (sizeof (Concept*) * list.entries);
418: if (!array) {
419: panic ("malloc failed in %s:%i",__FILE__,__LINE__) ;
420: }
421:
422: /* enter all concept pointers to the array - the list may be
423: freed afterwards */
424:
425: tmp = array ;
426: entry = list.first ;
427: while (entry) {
428: /* lint complains: warning: possible pointer alignment
429: * problem, but I can't see why */
430:
431: *(tmp++) = (Concept*) ListGetValue (entry);
432: entry = entry->next ;
433: }
434:
435: lattice->size = list.entries ;
436: lattice->concepts = array ;
437:
438: ListDelete(&list); /* removes list, but not client data */
439:
440: /* all raw data is now stored in <lattice>, we just need to
441: calculate the sub-concept relation. This is done in the
442: next call. */
443:
444: ConceptSubconcepts (lattice);
445:
446:}
447:
448:/*
449: * ConceptNumber
450: *
451: * calculate the number of concepts from a context (really a relation)
452: * and return it */
453:
454:int
455:ConceptNumber (rel)
456:
457: Relation *rel;
458:
459:{
460: int more ; /* flag */
461: int count ; /* number of concepts */
462: Concept c1,c2; /* previos and actual concept */
463: Concept *prev,*new;
464:
465: count = 0; /* number of concepts */
466:
467: ConceptInit (&c1,rel); /* initialize */
468: ConceptInit (&c2,rel);
469: prev = &c1;
470: new = &c2;
471:
472: ConceptFirstExtent (&prev->objects,&prev->attributes,rel);
473: count++ ;
474:
475: do {
476: more = ConceptNextExtent(&prev->objects, &new->objects,
477: &new->attributes, rel);
478: count++;
479: /* new becomes old */
480: if (prev == &c1) {
481: prev = &c2 ;
482: new = &c1 ;
483: } else {
484: prev = &c1;
485: new = &c2;
486: }
487: } while (more) ;
488:
489: /* data computed by the last ConceptNextExtent call is garbage */
490:
491: count--;
492: ConceptDelete (&c1); /* not needed - stuff from ConceptInit()*/
493: ConceptDelete (&c2);
494:
495: return count;
496:}
497:
498:/*
499: * ConceptSubconcepts
500: *
501: * takes a ConceptArray struct with raw concept data and computes the
502: * sub-concept relation on it. The result is also filled into the
503: * ConceptArray. */
504:
505:VOID
506:ConceptSubconcepts (array)
507:
508: ConceptArray *array ;
509:
510:{
511: int i,top,actual;
512:
513: /*
514: * first create for each Concept and array for closure and
515: * subconcepts (of size array->size) */
516:
517: for (i=0;i<array->size;i++) {
518:
519: SetNew(&array->concepts[i]->subconcepts, array->size);
520: SetNew(&array->concepts[i]->closure, array->size);
521: SetNew(&array->concepts[i]->superclos, array->size);
522:
523: SetCopy(&array->concepts[i]->objects,
524: &array->concepts[i]->obj);
525: SetCopy(&array->concepts[i]->attributes,
526: &array->concepts[i]->atr);
527:
528: }
529:
530: for (top=array->size-1;top>=0;top--) {
531:
532: /* each concepts is subconcept of itself (reflexsive) */
533: SetAdd(&array->concepts[top]->closure,top);
534: /* this is also true for super concepts */
535: SetAdd(&array->concepts[top]->superclos, top);
536:
537: for(actual=top+1;actual<array->size;actual++) {
538:
539: if(SetSubset(&array->concepts[top]->objects,
540: &array->concepts[actual]->objects)) {
541:
542: /* actual is a subconcept of top but
543: necessary not a direct subconcept -
544: so top belongs to the closure
545: of superconcepts of actual */
546:
547: SetAdd(&array->concepts[actual]->superclos,
548: top);
549:
550: /* remove the objects of actual from top */
551:
552: SetMinus(&array->concepts[top]->obj,
553: &array->concepts[actual]->objects,
554: &array->concepts[top]->obj);
555:
556: /* remove the attributes of top from actual */
557:
558: SetMinus(&array->concepts[actual]->atr,
559: &array->concepts[top]->attributes,
560: &array->concepts[actual]->atr);
561:
562: if (!SetMember(&array->concepts[top]->closure,
563: actual)) {
564:
565: /* actual is direct(!) subconcept
566: of top */
567:
568: SetAdd(&array->concepts[top]
569: ->subconcepts,actual);
570: SetAdd(&array->concepts[top]
571: ->closure,actual);
572: SetJoin(&array->concepts[top]
573: ->closure,
574: &array->concepts[actual]
575: ->closure,
576: &array->concepts[top]
577: ->closure);
578: } /* if (!SetMember()) */
579: } /* if (SetSubset()) */
580: }
581: }
582:}
583:
back ...