Context Navigation

trees.c @ 72

Last change on this file since 72 was 72, checked in by (none), 14 years ago

File size: 13.0 KB

Rev	Line
[26]	1	/*************************************************************************/
	2	/* */
	3	/* Routines for displaying, building, saving and restoring trees */
	4	/* ------------------------------------------------------------- */
	5	/* */
	6	/*************************************************************************/
	7
	8	#include "defns.i"
	9	#include "types.i"
	10	#include "extern.i"
	11
	12	#define Tab "\| "
	13	#define TabSize 4
	14	#define Width 80 /* approx max width of printed trees */
	15
[72]	16	/* If lines look like getting too long while a tree is being
	17	printed, subtrees are broken off and printed separately after
	18	the main tree is finished */
[26]	19
[72]	20	short Subtree; /* highest subtree to be printed */
	21	Tree Subdef[100]; /* pointers to subtrees */
[26]	22
[72]	23	FILE TRf = 0, fopen(); /* file pointer for tree i/o */
	24	char Fn[500]; /* file name */
[26]	25
	26	/*************************************************************************/
	27	/* */
	28	/* Display entire decision tree T */
	29	/* */
	30	/*************************************************************************/
	31
[72]	32	PrintTree(T)
	33	/* ---------- */
	34	Tree T; {
	35	short s;
[26]	36
[72]	37	Subtree = 0;
	38	printf("Decision Tree:\n");
	39	Show(T, 0);
	40	printf("\n");
[26]	41
[72]	42	ForEach(s, 1, Subtree) {
	43	printf("\n\nSubtree [S%d]\n", s);
	44	Show(Subdef[s], 0);
	45	printf("\n");
	46	}
[26]	47	printf("\n");
	48	}
	49
	50	/*************************************************************************/
	51	/* */
	52	/* Display the tree T with offset Sh */
	53	/* */
	54	/*************************************************************************/
	55
[72]	56	Show(T, Sh)
	57	/* ---- */
	58	Tree T;short Sh; {
	59	DiscrValue v, MaxV;
	60	short MaxLine();
[26]	61
[72]	62	if (T->NodeType) {
	63	/* See whether separate subtree needed */
[26]	64
[72]	65	if (T != Nil && Sh && Sh * TabSize + MaxLine(T) > Width) {
	66	if (Subtree < 99) {
	67	Subdef[++Subtree] = T;
	68	printf("[S%d]", Subtree);
	69	} else {
	70	printf("[S??]");
	71	}
	72	} else {
	73	MaxV = T->Forks;
[26]	74
[72]	75	/* Print simple cases first */
[26]	76
[72]	77	ForEach(v, 1, MaxV) {
	78	if (!T->Branch[v]->NodeType) {
	79	ShowBranch(Sh, T, v);
	80	}
	81	}
[26]	82
[72]	83	/* Print subtrees */
[26]	84
[72]	85	ForEach(v, 1, MaxV) {
	86	if (T->Branch[v]->NodeType) {
	87	ShowBranch(Sh, T, v);
	88	}
	89	}
[26]	90	}
[72]	91	} else {
	92	printf(" %s (%.1f", ClassName[T->Leaf], T->Items);
	93	if (T->Errors > 0)
	94	printf("/%.1f", T->Errors);
	95	printf(")");
[26]	96	}
	97	}
	98
	99	/*************************************************************************/
	100	/* */
	101	/* Print a node T with offset Sh, branch value v, and continue */
	102	/* */
	103	/*************************************************************************/
	104
[72]	105	ShowBranch(Sh, T, v)
	106	/* ----------- */
	107	short Sh;Tree T;DiscrValue v; {
	108	DiscrValue Pv, Last;
	109	Attribute Att;
	110	Boolean FirstValue;
	111	short TextWidth, Skip, Values = 0, i;
[26]	112
[72]	113	Att = T->Tested;
[26]	114
[72]	115	switch (T->NodeType) {
[26]	116	case BrDiscr:
	117
[72]	118	Indent(Sh, Tab);
[26]	119
[72]	120	printf("%s = %s:", AttName[Att], AttValName[Att][v]);
	121	break;
[26]	122
	123	case ThreshContin:
	124
[72]	125	Indent(Sh, Tab);
[26]	126
[72]	127	printf("%s %s %g ", AttName[Att], (v == 1 ? "<=" : ">"), T->Cut);
[26]	128
[72]	129	if (T->Lower != T->Upper) {
	130	printf("[%g,%g]", T->Lower, T->Upper);
	131	}
[26]	132
[72]	133	printf(":");
	134	break;
[26]	135
	136	case BrSubset:
	137
[72]	138	/* Count values at this branch */
[26]	139
[72]	140	ForEach(Pv, 1, MaxAttVal[Att]) {
	141	if (In(Pv, T->Subset[v])) {
	142	Last = Pv;
	143	Values++;
	144	}
[26]	145	}
[72]	146	if (!Values)
	147	return;
[26]	148
[72]	149	Indent(Sh, Tab);
[26]	150
[72]	151	if (Values == 1) {
	152	printf("%s = %s:", AttName[Att], AttValName[Att][Last]);
	153	break;
	154	}
[26]	155
[72]	156	printf("%s in {", AttName[Att]);
	157	FirstValue = true;
	158	Skip = TextWidth = strlen(AttName[Att]) + 5;
[26]	159
[72]	160	ForEach(Pv, 1, MaxAttVal[Att]) {
	161	if (In(Pv, T->Subset[v])) {
	162	if (!FirstValue && TextWidth + strlen(AttValName[Att][Pv]) + 11
	163	> Width) {
	164	Indent(Sh, Tab);
	165	ForEach(i, 1, Skip)
	166	putchar(' ');
[26]	167
[72]	168	TextWidth = Skip;
	169	FirstValue = true;
	170	}
[26]	171
[72]	172	printf("%s%c", AttValName[Att][Pv], Pv == Last ? '}' : ',');
	173	TextWidth += strlen(AttValName[Att][Pv]) + 1;
	174	FirstValue = false;
	175	}
[26]	176	}
[72]	177	putchar(':');
	178	}
[26]	179
[72]	180	Show(T->Branch[v], Sh + 1);
[26]	181	}
	182
	183	/*************************************************************************/
	184	/* */
	185	/* Find the maximum single line size for non-leaf subtree St. */
	186	/* The line format is */
	187	/* <attribute> <> X.xx:[ <class (<Items>)], or */
	188	/* <attribute> = <DVal>:[ <class> (<Items>)] */
	189	/* */
	190	/*************************************************************************/
	191
	192	short MaxLine(St)
[72]	193	/* -------- */
	194	Tree St; {
	195	Attribute a;
	196	DiscrValue v, MaxV, Next;
	197	short Ll, MaxLl = 0;
[26]	198
[72]	199	a = St->Tested;
[26]	200
[72]	201	MaxV = St->Forks;
	202	ForEach(v, 1, MaxV) {
	203	Ll = (St->NodeType == 2 ? 4 : strlen(AttValName[a][v])) + 1;
[26]	204
[72]	205	/* Find the appropriate branch */
[26]	206
[72]	207	Next = v;
[26]	208
[72]	209	if (!St->Branch[Next]->NodeType) {
	210	Ll += strlen(ClassName[St->Branch[Next]->Leaf]) + 6;
	211	}
	212	MaxLl = Max(MaxLl, Ll);
[26]	213	}
	214
[72]	215	return strlen(AttName[a]) + 4 + MaxLl;
[26]	216	}
	217
	218	/*************************************************************************/
	219	/* */
	220	/* Indent Sh columns */
	221	/* */
	222	/*************************************************************************/
	223
[72]	224	Indent(Sh, Mark)
	225	/* ------ */
	226	short Sh;char *Mark; {
	227	printf("\n");
	228	while (Sh--)
	229	printf("%s", Mark);
[26]	230	}
	231
	232	/*************************************************************************/
	233	/* */
	234	/* Save entire decision tree T in file with extension Extension */
	235	/* */
	236	/*************************************************************************/
	237
[72]	238	SaveTree(T, Extension)
	239	/* --------- */
	240	Tree T;String Extension; {
	241	static char *LastExt = "";
[26]	242
[72]	243	if (strcmp(LastExt, Extension)) {
	244	LastExt = Extension;
[26]	245
[72]	246	if (TRf)
	247	fclose(TRf);
[26]	248
[72]	249	strcpy(Fn, FileName);
	250	strcat(Fn, Extension);
	251	if (!(TRf = fopen(Fn, "w")))
	252	Error(0, Fn, " for writing");
	253	}
[26]	254
[72]	255	putc('\n', TRf);
	256	OutTree(T);
[26]	257
[72]	258	SaveDiscreteNames();
[26]	259	}
	260
	261	/*************************************************************************/
	262	/* */
	263	/* Save tree T as characters */
	264	/* */
	265	/*************************************************************************/
	266
[72]	267	OutTree(T)
	268	/* -------- */
	269	Tree T; {
	270	DiscrValue v;
	271	int Bytes;
[26]	272
[72]	273	StreamOut((char *) &T->NodeType, sizeof(short));
	274	StreamOut((char *) &T->Leaf, sizeof(ClassNo));
	275	StreamOut((char *) &T->Items, sizeof(ItemCount));
	276	StreamOut((char *) &T->Errors, sizeof(ItemCount));
	277	StreamOut((char ) T->ClassDist, (MaxClass + 1) sizeof(ItemCount));
[26]	278
[72]	279	if (T->NodeType) {
	280	StreamOut((char *) &T->Tested, sizeof(Attribute));
	281	StreamOut((char *) &T->Forks, sizeof(short));
[26]	282
[72]	283	switch (T->NodeType) {
	284	case BrDiscr:
	285	break;
[26]	286
[72]	287	case ThreshContin:
	288	StreamOut((char *) &T->Cut, sizeof(float));
	289	StreamOut((char *) &T->Lower, sizeof(float));
	290	StreamOut((char *) &T->Upper, sizeof(float));
	291	break;
[26]	292
[72]	293	case BrSubset:
	294	Bytes = (MaxAttVal[T->Tested] >> 3) + 1;
	295	ForEach(v, 1, T->Forks) {
	296	StreamOut((char *) T->Subset[v], Bytes);
	297	}
	298	break;
	299	}
[26]	300
[72]	301	ForEach(v, 1, T->Forks) {
	302	OutTree(T->Branch[v]);
[26]	303	}
	304	}
	305	}
	306
	307	/*************************************************************************/
	308	/* */
	309	/* Retrieve entire decision tree with extension Extension */
	310	/* */
	311	/*************************************************************************/
	312
	313	Tree GetTree(Extension)
[72]	314	/* -------- */
	315	String Extension; {
	316	Tree Hold, InTree();
	317	static char *LastExt = "";
[26]	318
[72]	319	if (strcmp(LastExt, Extension)) {
	320	LastExt = Extension;
[26]	321
[72]	322	if (TRf)
	323	fclose(TRf);
[26]	324
[72]	325	strcpy(Fn, FileName);
	326	strcat(Fn, Extension);
	327	if (!(TRf = fopen(Fn, "r")))
	328	Error(0, Fn, "");
	329	}
[26]	330
[72]	331	if (!TRf \|\| getc(TRf) == EOF)
	332	return Nil;
[26]	333
[72]	334	Hold = InTree();
[26]	335
[72]	336	RecoverDiscreteNames();
[26]	337
[72]	338	return Hold;
[26]	339	}
	340
	341	/*************************************************************************/
	342	/* */
	343	/* Retrieve tree from saved characters */
	344	/* */
	345	/*************************************************************************/
	346
	347	Tree InTree()
	348	/* ------- */
	349	{
[72]	350	Tree T;
	351	DiscrValue v;
	352	int Bytes;
[26]	353
[72]	354	T = (Tree) malloc(sizeof(TreeRec));
[26]	355
[72]	356	StreamIn((char *) &T->NodeType, sizeof(short));
	357	StreamIn((char *) &T->Leaf, sizeof(ClassNo));
	358	StreamIn((char *) &T->Items, sizeof(ItemCount));
	359	StreamIn((char *) &T->Errors, sizeof(ItemCount));
[26]	360
[72]	361	T->ClassDist = (ItemCount *) calloc(MaxClass + 1, sizeof(ItemCount));
	362	StreamIn((char ) T->ClassDist, (MaxClass + 1) sizeof(ItemCount));
[26]	363
[72]	364	if (T->NodeType) {
	365	StreamIn((char *) &T->Tested, sizeof(Attribute));
	366	StreamIn((char *) &T->Forks, sizeof(short));
[26]	367
[72]	368	switch (T->NodeType) {
	369	case BrDiscr:
	370	break;
[26]	371
[72]	372	case ThreshContin:
	373	StreamIn((char *) &T->Cut, sizeof(float));
	374	StreamIn((char *) &T->Lower, sizeof(float));
	375	StreamIn((char *) &T->Upper, sizeof(float));
	376	break;
[26]	377
[72]	378	case BrSubset:
	379	T->Subset = (Set *) calloc(T->Forks + 1, sizeof(Set));
[26]	380
[72]	381	Bytes = (MaxAttVal[T->Tested] >> 3) + 1;
	382	ForEach(v, 1, T->Forks) {
	383	T->Subset[v] = (Set) malloc(Bytes);
	384	StreamIn((char *) T->Subset[v], Bytes);
	385	}
[26]	386	}
	387
[72]	388	T->Branch = (Tree *) calloc(T->Forks + 1, sizeof(Tree));
	389	ForEach(v, 1, T->Forks) {
	390	T->Branch[v] = InTree();
	391	}
[26]	392	}
	393
[72]	394	return T;
[26]	395	}
	396
	397	/*************************************************************************/
	398	/* */
	399	/* Stream characters to/from file TRf from/to an address */
	400	/* */
	401	/*************************************************************************/
	402
[72]	403	StreamOut(s, n)
	404	/* --------- */
	405	String s;int n; {
	406	while (n--)
	407	putc(*s++, TRf);
[26]	408	}
	409
[72]	410	StreamIn(s, n)
	411	/* --------- */
	412	String s;int n; {
	413	while (n--)
	414	*s++ = getc(TRf);
[26]	415	}
	416
	417	/*************************************************************************/
	418	/* */
	419	/* Free up space taken up by tree Node */
	420	/* */
	421	/*************************************************************************/
	422
[72]	423	ReleaseTree(Node)
	424	/* ------- */
	425	Tree Node; {
	426	DiscrValue v;
[26]	427
[72]	428	if (Node->NodeType) {
	429	ForEach(v, 1, Node->Forks) {
	430	ReleaseTree(Node->Branch[v]);
	431	}
[26]	432
[72]	433	cfree(Node->Branch);
[26]	434
[72]	435	if (Node->NodeType == BrSubset) {
	436	cfree(Node->Subset);
	437	}
[26]	438
	439	}
	440
[72]	441	cfree(Node->ClassDist);
	442	cfree(Node);
[26]	443	}
	444
	445	/*************************************************************************/
	446	/* */
	447	/* Construct a leaf in a given node */
	448	/* */
	449	/*************************************************************************/
	450
	451	Tree Leaf(ClassFreq, NodeClass, Cases, Errors)
[72]	452	/* ---- */
	453	ItemCount *ClassFreq;ClassNo NodeClass;ItemCount Cases, Errors; {
	454	Tree Node;
[26]	455
[72]	456	Node = (Tree) calloc(1, sizeof(TreeRec));
[26]	457
[72]	458	Node->ClassDist = (ItemCount *) calloc(MaxClass + 1, sizeof(ItemCount));
	459	memcpy(Node->ClassDist, ClassFreq, (MaxClass + 1) * sizeof(ItemCount));
[26]	460
[72]	461	Node->NodeType = 0;
	462	Node->Leaf = NodeClass;
	463	Node->Items = Cases;
	464	Node->Errors = Errors;
	465
	466	return Node;
[26]	467	}
	468
	469	/*************************************************************************/
	470	/* */
	471	/* Insert branches in a node */
	472	/* */
	473	/*************************************************************************/
	474
[72]	475	Sprout(Node, Branches)
	476	/* ------ */
	477	Tree Node;DiscrValue Branches; {
	478	Node->Forks = Branches;
[26]	479
[72]	480	Node->Branch = (Tree *) calloc(Branches + 1, sizeof(Tree));
[26]	481	}
	482
	483	/*************************************************************************/
	484	/* */
	485	/* Count the nodes in a tree */
	486	/* */
	487	/*************************************************************************/
	488
[72]	489	TreeSize(Node)
	490	/* -------- */
	491	Tree Node; {
	492	int Sum = 0;
	493	DiscrValue v;
[26]	494
[72]	495	if (Node->NodeType) {
	496	ForEach(v, 1, Node->Forks) {
	497	Sum += TreeSize(Node->Branch[v]);
	498	}
[26]	499	}
	500
[72]	501	return Sum + 1;
[26]	502	}
	503
	504	/*************************************************************************/
	505	/* */
	506	/* Return a copy of tree T */
	507	/* */
	508	/*************************************************************************/
	509
	510	Tree CopyTree(T)
[72]	511	/* --------- */
	512	Tree T; {
	513	DiscrValue v;
	514	Tree New;
[26]	515
[72]	516	New = (Tree) malloc(sizeof(TreeRec));
	517	memcpy(New, T, sizeof(TreeRec));
[26]	518
[72]	519	New->ClassDist = (ItemCount *) calloc(MaxClass + 1, sizeof(ItemCount));
	520	memcpy(New->ClassDist, T->ClassDist, (MaxClass + 1) * sizeof(ItemCount));
[26]	521
[72]	522	if (T->NodeType) {
	523	New->Branch = (Tree *) calloc(T->Forks + 1, sizeof(Tree));
	524	ForEach(v, 1, T->Forks) {
	525	New->Branch[v] = CopyTree(T->Branch[v]);
	526	}
[26]	527	}
	528
[72]	529	return New;
[26]	530	}
	531
	532	/*************************************************************************/
	533	/* */
	534	/* Save attribute values read with "discrete N" */
	535	/* */
	536	/*************************************************************************/
	537
[72]	538	SaveDiscreteNames()
[26]	539	/* ----------------- */
	540	{
[72]	541	Attribute Att;
	542	DiscrValue v;
	543	int Length;
[26]	544
[72]	545	ForEach(Att, 0, MaxAtt) {
	546	if (SpecialStatus[Att] != DISCRETE)
	547	continue;
[26]	548
[72]	549	StreamOut((char *) &MaxAttVal[Att], sizeof(int));
[26]	550
[72]	551	ForEach(v, 1, MaxAttVal[Att]) {
	552	Length = strlen(AttValName[Att][v]) + 1;
[26]	553
[72]	554	StreamOut((char *) &Length, sizeof(int));
	555	StreamOut((char *) AttValName[Att][v], Length);
	556	}
[26]	557	}
	558	}
	559
	560	/*************************************************************************/
	561	/* */
	562	/* Recover attribute values read with "discrete N" */
	563	/* */
	564	/*************************************************************************/
	565
[72]	566	RecoverDiscreteNames()
[26]	567	/* -------------------- */
	568	{
[72]	569	Attribute Att;
	570	DiscrValue v;
	571	int Length;
[26]	572
[72]	573	ForEach(Att, 0, MaxAtt) {
	574	if (SpecialStatus[Att] != DISCRETE)
	575	continue;
[26]	576
[72]	577	StreamIn(&MaxAttVal[Att], sizeof(int));
[26]	578
[72]	579	ForEach(v, 1, MaxAttVal[Att]) {
	580	StreamIn(&Length, sizeof(int));
[26]	581
[72]	582	AttValName[Att][v] = (char *) malloc(Length);
	583	StreamIn(AttValName[Att][v], Length);
	584	}
[26]	585	}
	586	}

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: proiecte/Parallel-DT/R8/Src/trees.c @ 72

Download in other formats: