1:/*
  2: * $Id: arrow.c,v 1.1 2002/10/15 10:06:43 koschke Exp $
  3: *
  4: * CONCEPTS
  5: * Copyright (C) 1994 Technical University of Braunschweig, Germany
  6: * Written by Christian Lindig (lindig@ips.cs.tu-bs.de)
  7: * 
  8: * This program is free software; you can redistribute it and/or modify
  9: * it under the terms of the GNU General Public License as published by
 10: * the Free Software Foundation; either version 2 of the License, or
 11: * (at your option) any later version.
 12: * 
 13: * This program is distributed in the hope that it will be useful,
 14: * but WITHOUT ANY WARRANTY; without even the implied warranty of
 15: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 16: * GNU General Public License for more details.
 17: * 
 18: * You should have received a copy of the GNU General Public License
 19: * along with this program; if not, write to the Free Software
 20: * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 21: *
 22: * Provides cocnept lattice operations as join and meet and determies
 23: * if object and attributes are arrow related.  */
 24:
 25:#include "config.h"
 26:
 27:#if defined(STDC_HEADERS) || defined(HAVE_STDLIB_H)
 28:#  include <stdlib.h>
 29:#endif
 30:
 31:#ifdef DBMALLOC
 32:#  include <malloc.h>
 33:#endif
 34:
 35:#if STDC_HEADERS || defined(HAVE_STRING_H)
 36:#  include <string.h>
 37:#else
 38:#  ifndef HAVE_MEMCPY
 39:#    define memcpy(d, s, n) bcopy ((s), (d), (n))
 40:#    define memmove(d, s, n) bcopy ((s), (d), (n))
 41:#  endif
 42:#endif
 43:
 44:#include "defines.h"
 45:#include "panic.h"
 46:#include "list.h"
 47:#include "hash.h"
 48:#include "set.h"
 49:#include "relation.h"
 50:#include "concept.h"
 51:#include "context.h"
 52:#include "arrow.h"
 53:
 54:/*
 55: * internal prototypes
 56: */
 57:
 58:static VOID ArrowMaps _ANSI_ARGS_ ((ContextLattice * lattice, 
 59:				    int **objmap, int **atrmap)); 
 60:static int ArrowFindMeet _ANSI_ARGS_ ((Set * key, Concept ** concept));
 61:static int ArrowFindJoin _ANSI_ARGS_ ((Set * key, Concept ** concept));
 62:static int ArrowCmpAtrConcepts _ANSI_ARGS_ ((Concept ** x, Concept ** y));
 63:static Concept *ArrowMeet _ANSI_ARGS_ ((Concept ** concepts, int n, 
 64:					Concept * x, Concept * y));
 65:static Concept *ArrowJoin _ANSI_ARGS_ ((Concept ** concepts, int n, 
 66:					Concept * x, Concept * y));
 67:static Concept *ArrowMeetConcepts _ANSI_ARGS_ ((Concept ** set, int m, 
 68:						Concept ** concepts, int n));
 69:static Concept *ArrowJoinConcepts _ANSI_ARGS_ ((Concept ** set, int m, 
 70:						Concept ** concepts, int n));
 71:static Concept **ArrowSortConcepts _ANSI_ARGS_ ((Concept ** concepts, int n));
 72:static Concept **ArrowCreateArray _ANSI_ARGS_ ((Concept ** concepts, 
 73:						Set * set, int *n));
 74:static Concept *ArrowJoinSubconcepts _ANSI_ARGS_ ((Concept ** concepts, 
 75:						   Concept ** sorted, 
 76:						   int n, int concept));
 77:static Concept *ArrowMeetSuperconcepts _ANSI_ARGS_ ((Concept ** concepts, 
 78:						     int n, int concept));
 79:
 80:/*
 81: * ArrowMaps
 82: *
 83: * calculate maps from attributes to concepts and objects to
 84: * concepts. Each map is an array of integers and will be stored in
 85: * <objmap> and <atrmap>; the x-th integer is the concept which
 86: * introduced attribute x and object x resp. The caller is responsible
 87: * for free()'ing the maps. The atrmap consists of lattice->atr
 88: * entries, the objmap of lattice->obj entries.
 89: * */
 90:
 91:static VOID
 92:ArrowMaps (lattice, objmap, atrmap) 
 93:
 94:	ContextLattice *lattice; 
 95:	int **objmap, **atrmap;	/* place maps here */
 96:
 97:{
 98:	int attribute ;		/* attribute from concept */
 99:	int object;		/* object introduced by concept */
100:	int c;			/* index of actual concept */
101:
102:	*atrmap = (int*) malloc (sizeof (int) * lattice->atr);
103:	if (!*atrmap) {
104:		panic ("malloc failed in %s:%i",__FILE__,__LINE__);
105:	}
106:	*objmap = (int*) malloc (sizeof (int) * lattice->obj);
107:	if (!*objmap) {
108:		panic ("malloc failed in %s:%i",__FILE__,__LINE__);
109:	}
110:
111:	/* traverse all concepts. Member atr/obj of a Concept contains all
112:	   attributes/objects introduced by that concept. */
113:
114:	for (c=0;c < lattice->conc; c++) {
115:		attribute = SetFirst (&lattice->concepts[c]->atr);
116:		/* enter all attributs to map */
117:		while (attribute != -1) {
118:			(*atrmap)[attribute] = c;
119:			attribute = SetNext(&lattice->concepts[c]->atr, 
120:					    attribute); 
121:		}
122:		object = SetFirst (&lattice->concepts[c]->obj);
123:		/* enter all objects to map */
124:		while (object != -1) {
125:			(*objmap)[object] = c;
126:			object = SetNext(&lattice->concepts[c]->obj, 
127:					    object); 
128:		}
129:	}
130:}
131:
132:/*
133: * ArrowFindMeet
134: */
135:
136:static int 
137:ArrowFindMeet (key,concept)
138:
139:	Set *key;
140:	Concept **concept;
141:
142:{
143:	return -SetLectical(key,&(*concept)->objects);
144:}
145:
146:/*
147: * ArrowFindJoin
148: */
149:
150:static int 
151:ArrowFindJoin (key,concept)
152:
153:	Set *key;
154:	Concept **concept;
155:
156:{
157:	return -SetLectical(key,&(*concept)->attributes);
158:}
159:
160:#if 0				/* not needed - lattice->objects is in
161:				 the right order */
162:/*
163: * ArrowCmpObjConcepts
164: */
165:
166:static int 
167:ArrowCmpObjConcepts  (x,y)
168:
169:	Concept **x,**y;
170:
171:{
172:	return -SetLectical(&(*x)->objects,&(*y)->objects);
173:}
174:
175:#endif
176:
177:/*
178: * ArrowCmpAtrConcepts
179: */
180:
181:static int 
182:ArrowCmpAtrConcepts (x,y)
183:
184:	Concept **x,**y;
185:
186:{
187:	return -SetLectical(&(*x)->attributes,&(*y)->attributes);
188:}
189:
190:
191:/*
192: * ArrowMeet meet two concepts and return the the meet. The list of
193: * concepts supplied by <concepts> must be lectically ordered by the
194: * concepts object sets */
195:
196:static Concept *
197:ArrowMeet (concepts,n,x,y)
198:	Concept **concepts;	/* ordered concepts */
199:	int n;			/* number of concepts */
200:	Concept *x,*y;		/* concepts to meet */
201:
202:{
203:
204:	/* The intersection of two object sets is unique within the
205:	   lattice and determines the meet. We intersect the object
206:	   sets of a and y and bsearch the result within lattice */
207:
208:	Set objects;		/* intersect */
209:	Concept **meet;		/* meet */
210:	
211:	if (n == 0) { /* just paranoia */
212:		panic ("Empty Lattice %s:%i",__FILE__,__LINE__);
213:	}
214:	
215:	/* get the right set size from concept 0 */
216:	SetNew (&objects, concepts[0]->objects.size);
217:	SetIntersect (&x->objects, &y->objects, &objects);
218:	/* objects is unique - we have to find it */
219:
220:	meet = (Concept**) 
221:		bsearch ((char*)&objects,
222:			 (char*)concepts,
223:			 n,
224:			 sizeof(Concept*),
225:			 (int (*)_ANSI_ARGS_((const void *,const void *))) 
226:			 ArrowFindMeet);
227:
228:	if (!meet) {
229:		panic ("Meet not found %s:%i:",__FILE__,__LINE__);
230:	}
231:
232:	return *meet;
233:}
234:
235:/*
236: * ArrowJoin join two concepts and return the the join. The list of
237: * concepts supplied by <concepts> must be lectically ordered by the
238: * concepts attribute sets */
239:
240:static Concept *
241:ArrowJoin (concepts,n,x,y)
242:	Concept **concepts;	/* ordered concepts */
243:	int n;			/* number of concepts */
244:	Concept *x,*y;		/* concepts to join */
245:
246:{
247:
248:	/* The intersection of two attribute sets is unique within the
249:	   lattice and determines the join. We intersect the attribute
250:	   sets of a and y and bsearch the result within lattice */
251:
252:	Set attributes;		/* intersect */
253:	Concept **join;		/* join */
254:
255:	if (n == 0) { /* just paranoia */
256:		panic ("Empty Lattice %s:%i",__FILE__,__LINE__);
257:	}
258:	
259:	/* get the right set size from concept 0 */
260:	SetNew (&attributes, concepts[0]->attributes.size);
261:	SetIntersect (&x->attributes, &y->attributes, &attributes);
262:	/* attributes is unique - we have to find it */
263:
264:	join = (Concept**) 
265:		bsearch ((char*)&attributes,
266:			 (char*)concepts,
267:			 n,
268:			 sizeof(Concept*),
269:			 (int (*)_ANSI_ARGS_((const void *,const void *))) 
270:			 ArrowFindJoin);
271:
272:	if (!join) {
273:		panic ("Join not found %s:%i:",__FILE__,__LINE__);
274:	}
275:
276:	return *join;
277:}
278:
279:
280:/*
281: * ArrowMeetConcepts meet a set of concepts and return the meet from a
282: * the set of all concepts. The set of all concepts must be lectically
283: * ordered by the concepts object sets.
284: */
285: 
286:
287:static Concept*
288:ArrowMeetConcepts (set,m,concepts,n)
289:
290:	Concept **set;		/* concepts to meet */
291:	int m;			/* size of set */
292:	Concept **concepts;	/* all concepts */
293:	int n;			/* number of all concepts */
294:
295:{
296:	Concept **meet;		/* actual meet */
297:	int c;			/* concept from concepts Set */
298:	Set objects;		/* intersect */
299:
300:	
301:	if (m == 0) { /* top */
302:		return concepts[0]; /* == *(concepts[0]) */
303:	}
304:	
305:	SetCopy (&set[0]->objects,&objects); /* creates objects! */
306:	for (c=1;c<m;c++) {
307:		SetIntersect (&set[c]->objects, &objects, &objects);
308:	}
309:	/* objects is unique - we have to find it */
310:	
311:	meet = (Concept**) 
312:		bsearch ((char*)&objects,
313:			 (char*)concepts,
314:			 n,
315:			 sizeof(Concept*),
316:			 (int (*)_ANSI_ARGS_((const void *,const void *))) 
317:			 ArrowFindMeet);
318:
319:	if (!meet) {
320:		panic ("Meet not found %s:%i:",__FILE__,__LINE__);
321:	}
322:	
323:	SetDelete(&objects);
324:	return *meet;
325:}
326:
327:
328:/*
329: * ArrowJoinConcepts join a set of concepts and return the join from a
330: * the set of all concepts. The set of all concepts must be lectically
331: * ordered by the concepts attribute sets.
332: */
333: 
334:
335:static Concept*
336:ArrowJoinConcepts (set,m,concepts,n)
337:
338:	Concept **set;		/* concepts to join */
339:	int m;			/* size of set */
340:	Concept **concepts;	/* all concepts */
341:	int n;			/* number of all concepts */
342:
343:{
344:	Concept **join;		/* actual join */
345:	int c;			/* concept from concepts Set */
346:	Set attributes;		/* intersect */
347:
348:	
349:	if (m == 0) { /* bottom */
350:		return concepts[n-1]; /* == *(concepts[n-1]) */
351:	}
352:	
353:	SetCopy (&set[0]->attributes,&attributes); /* creates attributes! */
354:	for (c=1;c<m;c++) {
355:		SetIntersect (&set[c]->attributes, &attributes, &attributes);
356:	}
357:	/* attributes is unique - we have to find it */
358:	
359:	join = (Concept**) bsearch 
360:		((char*)&attributes,
361:		 (char*)concepts,
362:		 n,
363:		 sizeof(Concept*),
364:		 (int (*)_ANSI_ARGS_((const void *,const void *))) 
365:		 ArrowFindJoin);
366:
367:	if (!join) {
368:		panic ("Join not found %s:%i:",__FILE__,__LINE__);
369:	}
370:
371:	SetDelete(&attributes);
372:	return *join;
373:}
374:
375:/*
376: * ArrowSortConcepts creates a sorted list of concepts. The order is
377: * determined by the lectically ordering of the concept's attribute
378: * sets. The initial table is first copied and sorted afterwards. */
379:
380:static Concept **
381:ArrowSortConcepts (concepts,n)
382:	Concept **concepts;	/* concept array */
383:	int n;			/* size */
384:
385:{
386:	Concept **tab;
387:	tab = (Concept**) malloc (sizeof(Concept*) * n);
388:	if (!tab) {
389:		panic ("Malloc failed in %s:%i",__FILE__,__LINE__);
390:	}
391:	/* copy table and sort it */
392:	memcpy ((char*)tab,(char*)concepts,sizeof(Concept*) * n);
393:	qsort(tab,n,sizeof(Concept*),
394:	      (int(*)_ANSI_ARGS_((const void *, const void *)))
395:	      ArrowCmpAtrConcepts);
396:	return tab;
397:}
398:
399:/*
400: * ArrowCreateArray given an array of Concept pointers and a set of
401: * indices create a new array of pointers containing only pointers of
402: * concepts mentioned in the set. The size of the array is returned in
403: * n. if n==0 no array will be created and NULL returned instead*/
404:
405:static Concept **
406:ArrowCreateArray (concepts,set,n)
407:	Concept **concepts;
408:	Set *set;
409:	int *n;
410:
411:{
412:	Concept **tab;
413:	int s,c;
414:
415:	if (0 == set->size) {
416:		return (Concept**) NULL;
417:	}
418:	tab = (Concept**) malloc (sizeof(Concept*) * set->size);
419:	if (!tab) {
420:		panic ("Malloc failed in %s:%i",__FILE__,__LINE__);
421:	}
422:
423:	c = 0;
424:	s = SetFirst (set);
425:	while (-1 != s) {
426:		tab[c++] = concepts[s];
427:		s = SetNext(set,s);
428:	}
429:	*n = c;
430:	return tab;
431:}
432:
433:/*
434: * ArrowJoinSubconcepts
435: * determines the join of all true subconcepts from a given concept
436: */
437:
438:static Concept *
439:ArrowJoinSubconcepts (concepts,sorted,n,concept)
440:
441:	Concept **concepts;	/* array of concepts */
442:	Concept **sorted;	/* sorted array of concepts */
443:	int n;			/* size of array */
444:	int concept;		/* index into concepts */
445:
446:{
447:	Set subconcepts;
448:	Concept **set;		/* array of concepts to join*/
449:	int setsize;		/* size of array */
450:	Concept *join;		/* computed join */
451:
452:	/* determine subconcepts - remove concept from the
453:	   set of subconcepts */
454:
455:	SetCopy (&concepts[concept]->closure, &subconcepts);
456:	SetRemove(&subconcepts,concept);
457:
458:	set = ArrowCreateArray(concepts,&subconcepts,&setsize); 
459:	/* ArrowJoinConcepts needs the sorted array of concepts!! */
460:	join = ArrowJoinConcepts(set,setsize,sorted,n);
461:
462:	if (!join) {
463:		panic ("Join not found %s:%i:",__FILE__,__LINE__);
464:	}
465:
466:	free ((char*) set);
467:	SetDelete (&subconcepts);
468:
469:	return join;
470:
471:}
472:
473:/*
474: * ArrowMeetSuperconcepts
475: * determines the meet of all true superconcepts of a given concepts
476: */
477:
478:static Concept *
479:ArrowMeetSuperconcepts (concepts,n,concept)
480:	Concept **concepts;	/* sorted list of all concepts */
481:	int n;			/* number of all concepts */
482:	int concept;		
483:
484:{
485:
486:	Set superconcepts;
487:	Concept **set;		/* array of concepts to meet*/
488:	int setsize;		/* size of array */
489:	Concept *meet;		/* computed join */
490:
491:	/* determine subconcepts - remove concept from the
492:	   set of subconcepts */
493:
494:	SetCopy (&concepts[concept]->superclos, &superconcepts);
495:	SetRemove(&superconcepts,concept);
496:
497:	set = ArrowCreateArray(concepts,&superconcepts,&setsize); 
498:	/* ArrowMeetConcepts needs the sorted array of concepts!! */
499:	meet = ArrowMeetConcepts(set,setsize,concepts,n);
500:
501:	if (!meet) {
502:		panic ("Meet not found %s:%i:",__FILE__,__LINE__);
503:	}
504:
505:	free ((char*) set);
506:	SetDelete (&superconcepts);
507:
508:	return meet;
509:}
510:
511:
512:/*
513: * ArrowUpDown the arrow-up and arrow-down relation from a context by
514: * utilizing the concept lattice of that context. Creates new
515: * relations up and down to store the result; old contents will be
516: * lost. */
517:
518:/* ATTENTION: the Relation functions usually take arguments in the 
519:   order ATTRIBUTE, OBJECT ! */
520:
521:VOID
522:ArrowUpDown (context, lattice, uprel, downrel)
523:
524:	Context *context;
525:	ContextLattice *lattice;
526:	Relation *uprel,*downrel;	/* results stored here */
527:
528:{
529:	int *objmap, *atrmap;	/* maps from obj/atr -> introducing conc. */
530:	int obj,atr;		/* indexes */
531:	Concept *join,*meet;
532:	Concept **concepts;	/* sorted list of concepts */
533:	int up,down;
534:
535:	/* create relations of the appropriate size */
536:	RelNew (downrel,lattice->atr, lattice->obj);
537:	RelNew (uprel,lattice->atr,lattice->obj);
538:	
539:	/* calculate maps for introducing concepts */
540:	ArrowMaps (lattice,&objmap,&atrmap);
541:
542:	/* create sorted array of concepts for join */
543:	concepts = ArrowSortConcepts(lattice->concepts,lattice->conc);
544:
545:	/* compute down array relation */
546:
547:	for (obj=0;obj<lattice->obj;obj++) {
548:		/* join all subconcepts of objmap[obj] */
549:		join = ArrowJoinSubconcepts(lattice->concepts,
550:					    concepts,
551:					    lattice->conc,
552:					    objmap[obj]);
553:
554:		for(atr=0;atr<lattice->atr;atr++) {
555:			/* only unrelated pairs can be arrow related */
556:			if (ContextRelated(context,lattice->objects[obj],
557:					   lattice->attributes[atr])) {
558:				RelUnrelate(downrel,atr,obj);
559:				continue ;
560:			} else if (join == lattice->concepts[objmap[obj]]) {
561:				RelUnrelate(downrel,atr,obj);
562:				continue ;
563:			}
564:
565:			meet = ArrowMeet(lattice->concepts,
566:					 lattice->conc,
567:					 lattice->concepts[objmap[obj]],
568:					 lattice->concepts[atrmap[atr]]);
569:			/* join != lattice->concepts[objmap[obj]] 
570:			   checked above */
571:			down = ( meet == join ) ;
572:			if (down) 
573:				RelRelate(downrel,atr,obj);
574:			else
575:				RelUnrelate(downrel,atr,obj);
576:		}
577:	}
578:
579:	/* compute up array relation */
580:
581:	for (atr=0;atr < lattice->atr;atr++) {
582:		/* meet all superconcepts of atrmap[atr] */
583:		meet = ArrowMeetSuperconcepts (lattice->concepts,
584:					       lattice->conc,atrmap[atr]);
585:		for (obj=0;obj<lattice->obj;obj++) {
586:			/* only unrelated pairs can be arrow related */
587:			if (ContextRelated(context,lattice->objects[obj],
588:					   lattice->attributes[atr])) {
589:				RelUnrelate(uprel,atr,obj);
590:				continue ;
591:			} else if (meet == lattice->concepts[atrmap[atr]]) {
592:				RelUnrelate(uprel,atr,obj);
593:				continue ;
594:			}
595:			/* join need differently sorted concepts! */
596:			join = ArrowJoin(concepts, lattice->conc,
597:					 lattice->concepts[atrmap[atr]],
598:					 lattice->concepts[objmap[obj]]);
599:			up = ( meet == join );
600:			if (up) 
601:				RelRelate(uprel,atr,obj);
602:			else
603:				RelUnrelate(uprel,atr,obj);
604:		}
605:	}
606:	
607:	free((char*)concepts);
608:	free((char*)atrmap);
609:	free((char*)objmap);
610:}
611:	
612:	



back ...