dtr.c

it is tree Dtree algorithm. so see it. it is in c++

/*----------------------------------------------------------------------
  File    : dtr.c
  Contents: decision and regression tree rule extraction
  Authors : Christian Borgelt
  History : 26.05.1998 file created
            23.06.1998 adapted to modified attset functions
            03.09.1998 interpretation of option -e changed
            17.04.1999 simplified using the new module 'io'
            18.12.2000 extended to regression trees
            23.07.2001 adapted to modified module scan
            06.07.2002 adapted to modified module rules (RS_INFO)
            16.08.2003 slight changes in error message output
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <assert.h>
#ifndef SC_SCAN
#define SC_SCAN
#endif
#include "scan.h"
#ifndef AS_PARSE
#define AS_PARSE
#endif
#ifndef DT_PARSE
#define DT_PARSE
#endif
#ifndef DT_RULES
#define DT_RULES
#endif
#ifndef RS_DESC
#define RS_DESC
#endif
#include "io.h"
#include "dtree.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define PRGNAME     "dtr"
#define DESCRIPTION "decision and regression tree rule extraction"
#define VERSION     "version 2.5 (2004.08.12)         " \
                    "(c) 1998-2004   Christian Borgelt"

/* --- error codes --- */
#define OK            0         /* no error */
#define E_NONE        0         /* no error */
#define E_NOMEM     (-1)        /* not enough memory */
#define E_FOPEN     (-2)        /* cannot open file */
#define E_FREAD     (-3)        /* read error on file */
#define E_FWRITE    (-4)        /* write error on file */
#define E_OPTION    (-5)        /* unknown option */
#define E_OPTARG    (-6)        /* missing option argument */
#define E_ARGCNT    (-7)        /* wrong number of arguments */
#define E_STDIN     (-8)        /* double assignment of stdin */
#define E_PARSE     (-9)        /* parse error */
#define E_UNKNOWN  (-10)        /* unknown error */

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
const char *errmsgs[] = {       /* error messages */
  /* E_NONE      0 */  "no error\n",
  /* E_NOMEM    -1 */  "not enough memory\n",
  /* E_FOPEN    -2 */  "cannot open file %s\n",
  /* E_FREAD    -3 */  "read error on file %s\n",
  /* E_FWRITE   -4 */  "write error on file %s\n",
  /* E_OPTION   -5 */  "unknown option -%c\n",
  /* E_OPTARG   -6 */  "missing option argument\n",
  /* E_ARGCNT   -7 */  "wrong number of arguments\n",
  /* E_STDIN    -8 */  "double assignment of standard input\n",
  /* E_PARSE    -9 */  "parse error(s) on file %s\n",
  /* E_UNKNOWN -10 */  "unknown error\n"
};

/*----------------------------------------------------------------------
  Global Variables
----------------------------------------------------------------------*/
const  char    *prgname = NULL; /* program name for error messages */
static SCAN    *scan    = NULL; /* scanner */
static DTREE   *dtree   = NULL; /* decision/regression tree */
static ATTSET  *attset  = NULL; /* attribute set */
static RULESET *ruleset = NULL; /* extracted rule set */
static FILE    *out     = NULL; /* output file */

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/

static void error (int code, ...)
{                               /* --- print error message */
  va_list    args;              /* list of variable arguments */
  const char *msg;              /* error message */

  if (code < E_UNKNOWN) code = E_UNKNOWN;
  if (code < 0) {               /* if to report an error, */
    msg = errmsgs[-code];       /* get the error message */
    if (!msg) msg = errmsgs[-E_UNKNOWN];
    fprintf(stderr, "\n%s: ", prgname);
    va_start(args, code);       /* get variable arguments */
    vfprintf(stderr, msg, args);/* print the error message */
    va_end(args);               /* end argument evaluation */
  }
  #ifndef NDEBUG
  if (ruleset) rs_delete(ruleset, 0);
  if (dtree)   dt_delete(dtree, 0);
  if (attset)  as_delete(attset);  /* clean up memory */
  if (scan)    sc_delete(scan);    /* and close file */
  if (out && (out != stdout)) fclose(out);
  #endif
  #ifdef STORAGE
  showmem("at end of program"); /* check memory usage */
  #endif
  exit(code);                   /* abort the program */
}  /* error() */

/*--------------------------------------------------------------------*/

static int rulecmp (const RULE *r1, const RULE *r2, void *data)
{                               /* --- compare two rules */
  int c1 = r_headval(r1)->i;    /* get the classes */
  int c2 = r_headval(r2)->i;    /* of the two rules */
  if (c1 < c2) return -1;       /* and compare them */
  return (c1 > c2) ? 1 : 0;     /* return sign of their difference */
}  /* rulecmp() */

/*--------------------------------------------------------------------*/

int main (int argc, char* argv[])
{                               /* --- main function */
  int  i, k = 0;                /* loop variables, counter */
  char *s;                      /* to traverse options */
  char **optarg = NULL;         /* option argument */
  char *fn_dt   = NULL;         /* name of dec./reg. tree file */
  char *fn_rs   = NULL;         /* name of rule set file */
  int  maxlen   = 0;            /* maximal output line length */
  int  flags = RS_TITLE|RS_INFO;/* rule set description flags */

  prgname = argv[0];            /* get program name for error msgs. */

  /* --- print startup/usage message --- */
  if (argc > 1) {               /* if arguments are given */
    fprintf(stderr, "%s - %s\n", argv[0], DESCRIPTION);
    fprintf(stderr, VERSION); } /* print a startup message */
  else {                        /* if no argument is given */
    printf("usage: %s [options] dtfile rsfile\n", argv[0]);
    printf("%s\n", DESCRIPTION);
    printf("%s\n", VERSION);
    printf("-s       print support    of a rule\n");
    printf("-c       print confidence of a rule\n");
    printf("-d       print only one condition per line\n");
    printf("-l#      output line length (default: no limit)\n");
    printf("dtfile   file containing decision/regression "
                    "tree description\n");
    printf("rsfile   file to write rule set description to\n");
    return 0;                   /* print usage message */
  }                             /* and abort program */

  /* --- evaluate arguments --- */
  for (i = 1; i < argc; i++) {  /* traverse arguments */
    s = argv[i];                /* get option argument */
    if (optarg) { *optarg = s; optarg = NULL; continue; }
    if ((*s == '-') && *++s) {  /* -- if argument is an option */
      while (1) {               /* traverse characters */
        switch (*s++) {         /* evaluate option */
          case 's': flags |= RS_SUPP;               break;
          case 'c': flags |= RS_CONF;               break;
          case 'd': flags |= RS_CONDLN;             break;
          case 'l': maxlen = (int)strtol(s, &s, 0); break;
          default : error(E_OPTION, *--s);          break;
        }                       /* set option variables */
        if (!*s) break;         /* if at end of string, abort loop */
        if (optarg) { *optarg = s; optarg = NULL; break; }
      } }                       /* get option argument */
    else {                      /* if argument is no option */
      switch (k++) {            /* evaluate non-option */
        case  0: fn_dt = s;       break;
        case  1: fn_rs = s;       break;
        default: error(E_ARGCNT); break;
      }                         /* note filenames */
    }
  }
  if (optarg) error(E_OPTARG);  /* check option argument */
  if (k != 2) error(E_ARGCNT);  /* check number of arguments */

  /* --- read decision/regression tree --- */
  scan = sc_create(fn_dt);      /* create a scanner */
  if (!scan) error((!fn_dt || !*fn_dt) ? E_NOMEM : E_FOPEN, fn_dt);
  attset = as_create("domains", att_delete);
  if (!attset) error(E_NOMEM);  /* create an attribute set */
  fprintf(stderr, "\nreading %s ... ", sc_fname(scan));
  if ((sc_nexter(scan)   <  0)  /* start scanning (get first token) */
  ||  (as_parse(attset, scan, AT_ALL) != 0)
  ||  (as_attcnt(attset) <= 0)) /* parse attribute set */
    error(E_PARSE, sc_fname(scan));
  dtree = dt_parse(attset,scan);/* parse the decision tree */
  if (!dtree || !sc_eof(scan)) error(E_PARSE, fn_dt);
  sc_delete(scan); scan = NULL; /* delete the scanner */
  fprintf(stderr, "[%d attribute(s)/%d node(s)/%d level(s)] done.\n",
          as_attcnt(attset), dt_size(dtree), dt_height(dtree));

  /* --- extract and write rule set --- */
  if (fn_rs && *fn_rs)          /* if an output file name is given, */
    out = fopen(fn_rs, "w");    /* open output file for writing */
  else {                        /* if no output file name is given, */
    out = stdout; fn_rs = "<stdout>"; }     /* write to std. output */
  fprintf(stderr, "writing %s ... ", fn_rs);
  if (!out) error(E_FOPEN, fn_rs);
  if (as_desc(attset, out, AS_TITLE|AS_MARKED, maxlen) != 0)
    error(E_FWRITE, fn_rs);     /* describe attribute domains */
  fputc('\n', out);             /* leave one line empty */
  ruleset = dt_rules(dtree);    /* extract a rule set from the */
  if (!ruleset) error(E_NOMEM); /* decision/regression tree */
  for (i = rs_rulecnt(ruleset); --i >= 0; )
    r_condsort(rs_rule(ruleset, i)); /* sort the conditions */
  rs_sort(ruleset, rulecmp, NULL);   /* and the rules */
  if (rs_desc(ruleset, out, flags, maxlen) != 0)
    error(E_FWRITE, fn_rs);     /* describe the ruleset */
  if (out != stdout) {          /* if not written to standard output, */
    i = fclose(out); out = NULL;/* close the output file */
    if (i != 0) error(E_FWRITE, fn_rs);
  }                             /* print a success message */
  fprintf(stderr, "[%d rule(s)] done.\n", rs_rulecnt(ruleset));

  /* --- clean up --- */
  #ifndef NDEBUG
  rs_delete(ruleset, 0);        /* delete rule set, */
  dt_delete(dtree, 1);          /* dec./reg. tree, and attribute set */
  #endif
  #ifdef STORAGE
  showmem("at end of program"); /* check memory usage */
  #endif
  return 0;                     /* return 'ok' */
}  /* main() */