hyper.c

数据挖掘中的一算法 ines算法 c下实现的。适合初学习数据挖掘者借鉴

  c = ht->comps;                /* get the connected components */
  for (p1 = hedge->nodes +(k = hedge->size); --k >= 0; ) {
    r = i = *--p1;              /* traverse the hyperedge nodes */
    while (c[r].id != r) r = c[r].id;
    c[i].id = r;                /* flatten the references */
    if ((c[r].cnt > 0)          /* if node is still unmarked */
    &&  ((r != i) || (c[r].cnt > 1)))    /* and not isolated */
      c[r].cnt = -c[r].cnt;     /* init. the repres. node markers */
  }                             /* (abuse connected comp. counters) */
  for (he = ht->hedges +(i = ht->hecnt); --i >= 0; ) {
    n  = (*--he)->size;         /* traverse existing hyperedges and */
    p2 = (*he)->nodes +n;       /* find the representative node */
    r  = *--p2; while (c[r].id != r) r = c[r].id;
    c[*p2].id = r;              /* flatten the reference and */
    if (c[r].cnt > 0)           /* if the connected component already */
      continue;                 /* passed the test, skip hyperedge */
    for (p1 = hedge->nodes +(k = hedge->size); --k >= 0; ) {
      if (c[*--p1].id != r)     /* traverse nodes from the */
        continue;               /* same connected component */
      while ((*p2 > *p1) && (--n > 0))
        p2--;                   /* search each node of the hyperedge */
      if (*p2 != *p1) break;    /* if not found, abort the loop */
    }                       
    if (k < 0)                  /* if all nodes have been found, */ 
      c[r].cnt = -c[r].cnt;     /* unmark the representative node */
  }                             /* (connected comp. passed the test) */
  i = 0;                        /* default: successful test */
  for (p1 = hedge->nodes +(k = hedge->size); --k >= 0; ) {
    r = c[*--p1].id;            /* traverse nodes of the hyperedge */
    n = c[r].cnt;               /* and get the representative nodes */
    if (n < 0) {                /* if a component did not pass the */
      c[r].cnt = -n; i = -1; }  /* test, clear the node marker and */
  }                             /* set the test result to 'failure' */
  return i;                     /* return the result of the test */
}  /* he_check() */

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

HTREE* ht_create (int nodecnt)
{                               /* --- create a hypertree */
  int   i;                      /* loop variable */
  HTREE *ht;                    /* created hypertree */
  HCOMP *c;                     /* to traverse connected components */

  assert(nodecnt > 0);          /* check the function argument */
  ht = (HTREE*)malloc(sizeof(HTREE) +(2*nodecnt-1) *sizeof(HEDGE*));
  if (!ht) return NULL;         /* allocate the base structure */
  ht->hecnt   = 0;              /* and initialize it */
  ht->buf     = ht->hedges +nodecnt;
  ht->comps   = c = (HCOMP*)malloc(nodecnt *sizeof(HCOMP));
  ht->nodes   =     (int*)  malloc(nodecnt *sizeof(int));
  if (!c || !ht->nodes) { ht_delete(ht); return NULL; }
  ht->nodecnt = nodecnt;        /* allocate and init. the vectors */
  ht->flags   = HT_CONSEQ | ((nodecnt < 2) ? HT_FULL : 0);
  for (c += i = nodecnt; --i >= 0; ) {
    (--c)->id = i; c->cnt = 1;} /* initialize connected components */
  return ht;                    /* return the created hypertree */
}  /* ht_create() */

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

void ht_delete (HTREE *ht)
{                               /* --- delete a hypertree */
  int   i;                      /* loop variable */
  HEDGE **hedge;                /* to traverse hyperedges */

  assert(ht);                   /* check the function argument */
  for (hedge = ht->hedges +(i = ht->hecnt); --i >= 0; )
    free(*--hedge);             /* delete all hyperedges */
  if (ht->nodes) free(ht->nodes);
  if (ht->comps) free(ht->comps);
  free(ht);                     /* delete vectors and base structure */
}  /* ht_delete() */

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

HTREE* ht_dup (HTREE *ht)
{                               /* --- duplicate hypertree */
  int   i;                      /* loop variable */
  HTREE *dup;                   /* duplicate of hypertree */
  HEDGE **s, **d;               /* to traverse hyperedges */
  HCOMP *cs, *cd;               /* to traverse connected components */

  assert(ht);                   /* check the function argument */
  dup = ht_create(ht->nodecnt); /* create a hypertree */
  if (!dup) return NULL;        /* with the same number of nodes */
  dup->flags = ht->flags;       /* and copy the fields */
  s = ht->hedges;  cs = ht->comps;
  d = dup->hedges; cd = dup->comps;
  for (i = ht->hecnt; --i >= 0; ) {
    *d = he_dup(*s++);          /* traverse the hyperedges */
    if (!*d++) { ht_delete(dup); return NULL; }
    dup->hecnt++;               /* copy and count the hyperedges */
    *cd++ = *cs++;              /* copy the connected component */
  }                             /* information */
  return dup;                   /* return the created duplicate */
}  /* ht_dup() */

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

int ht_headd (HTREE *ht, int size, int *nodes)
{                               /* --- add a hyperedge to a hypertree */
  HEDGE *hedge;                 /* created hyperedge */
  int   *d;                     /* to traverse the nodes */

  assert(ht && (size > 1) && nodes);  /* check the function arguments */
  if (ht->flags & HT_FULL)      /* if the hypertree is already fully */
    return -2;                  /* connected, abort the function */
  hedge = (HEDGE*)malloc(sizeof(HEDGE) +(size-1) *sizeof(int));
  if (!hedge) return -1;        /* create a hyperedge and */
  hedge->size = size;           /* note the number of nodes */
  for (d = hedge->nodes; --size >= 0; )
    *d++ = *nodes++;            /* copy the node identifiers */
  return he_add(ht, hedge);     /* add the hyperedge to the hypertree */
}  /* ht_headd() */

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

int ht_reduce (HTREE *ht)
{                               /* --- Graham reduction */
  int   si, di, k;              /* loop variables */
  int   n, rem;                 /* number of left/removed hyperedges */
  int   subset;                 /* subset flags (result of he_subset) */
  HEDGE **d, **s, **r;          /* to traverse the hyperedges */
  int   *p;                     /* to traverse the node identifiers */
  int   *marks;                 /* number of hyperedges per node -1 */

  assert(ht);                   /* check the function argument */
  if (ht->flags & HT_CONSEQ)    /* check for a valid */
    return 0;                   /* construction sequence */

  /* --- set up node markers --- */
  marks = ht->nodes;            /* get the marker vector */
  for (p = marks +(k = ht->nodecnt); --k >= 0; )
    *--p = -1;                  /* initialize hyperedge counters */
  for (s = ht->hedges +(si = ht->hecnt); --si >= 0; ) {
    p = (*--s)->nodes;          /* traverse the hyperedges */
    for (p += k = (*s)->size; --k >= 0; )
      marks[*--p]++;            /* traverse the nodes and count */
  }                             /* the hyperedge for each node */
  /* Here it is marks[i] = n if there are n+1 hyperedges containing */
  /* the node with the identifier i. Therefore marks[i] indicates   */
  /* whether the node is to be checked in the hyperedge subsumption */
  /* test (marks[i] > 0) or not (marks[i] <= 0).                    */

  /* --- Graham reduction --- */
  r = ht->buf;                  /* get buffer for removed hyperedges */
  for (n = ht->hecnt; n > 1; n -= rem) {
    rem = 0;                    /* init. number of removed hyperedges */
    for (s = ht->hedges +(si = n); --si > 0; ) {
      if (!*--s) continue;      /* traverse remaining hyperedges */
      for (d = ht->hedges +(di = si); --di >= 0; ) {
        if (!*--d) continue;    /* traverse remaining hyperedges */
        subset = he_subset(*s, *d, marks);
        if (!subset) continue;  /* if one hyperedge is contained */
        if (subset & 1) d = s;  /* in the other, it can be removed */
        for (p = (*d)->nodes +(k = (*d)->size); --k >= 0; )
          marks[*--p]--;        /* remove the nodes from the markers */
        *r++ = *d;              /* copy the hyperedge to the buffer */
        *d   = NULL; rem++;     /* and remove it from the vector */
        if (subset & 1) break;  /* if the source has been removed, */
      }                         /* abort the inner loop */
    }                           /* if no hyperedges were removed, */
    if (rem <= 0) break;        /* the reduction failed, so abort */
    s = d = ht->hedges;         /* traverse the hyperedge vector */
    for (k = n; --k >= 0; s++)  /* and expunge the deleted entries */
      if (*s) *d++ = *s;        /* (collect the remaining hyperedges */
  }                             /* at the beginning of the vector) */

  /* --- copy back removed hyperedges --- */
  for (d = ht->hedges +n, k = ht->hecnt -n; --k >= 0; )
    *d++ = *--r;                /* copy hyperedges in reverse order */
  /* If the reduction succeeded, the hyperedges are ordered */
  /* in such a way that they form a construction sequence.  */
  if (n <= 1) ht->flags |= HT_CONSEQ;
  return (n > 1) ? -1 : 0;      /* set the construction sequence flag */
}  /* ht_reduce() */            /* and return the reduction result */

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

int ht_fill (HTREE *ht, int maxsz, double randfn (void))
{                               /* --- fill with random hyperedges */
  int   size;                   /* size of current hyperedge */
  HEDGE *hedge;                 /* current hyperedge */
  int   r;                      /* result of adding a hyperedge */

  assert(ht && (maxsz > 1));    /* check the function arguments */
  if (ht->flags & HT_FULL)      /* if the hypertree is already fully */
    return 0;                   /* connected, abort the function */
  do {                          /* hyperedge adding loop */
    size = (int)(randfn() *(maxsz-1)) +2;
    if (size > maxsz) size = maxsz;
    if (size < 2)     size = 2; /* choose a size at random */
    hedge = he_rand(ht, size, randfn);
    if (!hedge) return -1;      /* generate a random hyperedge */
    r = he_add(ht, hedge);      /* and add it to the hypertree */
    if (r < 0) { free(hedge); return -1; }
  } while (r <= 0);             /* while not fully connected */
  ht->flags |= HT_FULL;         /* set the fully connected flag */
  return 0;                     /* return 'ok' */
}  /* ht_fill() */

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

HTREE* ht_modify (HTREE *ht, int maxsz, double keep,
                  double randfn (void))
{                               /* --- create modified hypertree */
  int   i, k, n;                /* loop variables, buffers */
  HTREE *mod;                   /* created modified hypertree */
  HEDGE **s, **d, *hedge;       /* to traverse hyperedges */

  assert(ht && (maxsz >= 0));   /* check the function arguments */
  mod = ht_create(ht->nodecnt); /* create a hypertree */
  if (!mod)
    return NULL;        /* with the same number of nodes */
  d = ht->buf +(i = n = ht->hecnt);
  s = ht->hedges +i;            /* traverse the hyperedges and */
  while (--i >= 0) *--d = *--s; /* copy the hyperedge pointers */
  k = (int)(keep *n);           /* compute the number */
  if (k >= n) k = n-1;          /* of hyperedges to keep */
  if (k <  0) k = 0;            /* (it must be 0 <= k < n) */
  while ((n > 0) && (k > 0)) {  /* select random hyperedges */
    i = (int)(randfn() *n);     /* compute a random index and */
    if (i >= n) i = n-1;        /* check and adapt its range */
    if (i <  0) i = 0;          /* (it must be 0 <= i <= n) */
    hedge = d[i];               /* select a random hyperedge and */
    d[i]  = d[--n];             /* fill the gap with the last h.e. */
    if (he_check(mod, hedge) != 0)
      continue;                 /* check whether it can be added */
    hedge = he_dup(hedge);      /* copy selected hyperedge */
    if (!hedge) {
      ht_delete(mod); return NULL; }
    if (he_add(mod, hedge) < 0) {
      free(hedge); ht_delete(mod); return NULL; }
    k--;                        /* add the copied hyperedge and */
  }                             /* decrement the hyperedge counter */
  if (ht_fill(mod, maxsz, randfn) < 0) {
    ht_delete(mod); return NULL; }  /* fill with random hyperedges */
  return mod;                   /* return the created hypertree */
}  /* ht_modify() */

/*--------------------------------------------------------------------*/
#ifndef NDEBUG

void ht_show (HTREE *ht)
{                               /* --- show a hypertree */
  int   i, k;                   /* loop variables */
  HEDGE **hedge;                /* to traverse the hyperedges */
  int   *p;                     /* to traverse the nodes */

  assert(ht);                   /* check the function argument */
  for (hedge = ht->hedges, i = ht->hecnt; --i >= 0; hedge++) {
    printf("(");                /* traverse the hyperedges and */
    p = (*hedge)->nodes;        /* the nodes of each hyperedge */
    for (k = (*hedge)->size; --k >= 0; p++)
      printf("%d%s", *p, (k > 0) ? "," : ")\n");
  }                             /* print the nodes of a hyperedge */
}  /* ht_show() */

#endif