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