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