hyper.c

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

/*----------------------------------------------------------------------
  File    : hyper.c
  Contents: hypertree management for simulated annealing
  Author  : Christian Borgelt
  History : 30.03.1997 file created as sian.c
            28.12.1999 redesign completed
            17.03.2002 hypertree functions made a separate module
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "vecops.h"
#include "hyper.h"

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define HT_FULL       1         /* hypertree is fully connected */
#define HT_CONSEQ     2         /* construction sequence is valid */

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

static void _nodesort (int *nodes, int cnt)
{                               /* --- sort node identifiers */
  int i, t;                     /* loop variable and exchange buffer */
  int *p;                       /* to traverse the node identifiers */

  assert(nodes && (cnt >= 0));  /* check the function arguments */
  if (cnt <= 1) return;         /* sort only more than one identifier */
  for (p = nodes, i = cnt; --i > 0; )  /* find the smallest node */
    if (nodes[i] < *p) p = nodes +i;   /* identifier and swap it */
  t = *nodes; *nodes = *p; *p = t;     /* to front as a sentinel */
  for (i = 0; ++i < cnt; ) {    /* insertion sort with sentinel */
    p = nodes +i; t = *p;       /* note the identifier to insert */
    while (*--p > t) p[1] = *p; /* shift right greater identifiers */
    p[1] = t;                   /* store the identifier to insert */
  }                             /* in the place thus found */
}  /* _nodesort() */

/*----------------------------------------------------------------------
Since the number of nodes in a hyperedge will usually be very small
(and definitely <= 32), insertion sort is more efficient than quicksort.
----------------------------------------------------------------------*/

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

static int he_cmp (const void *p1, const void *p2, void *data)
{                               /* --- compare two hyperedges */
  int r1, r2;                   /* representative nodes */

  r1 = ((HCOMP*)data)[((const HEDGE*)p1)->nodes[0]].id;
  r2 = ((HCOMP*)data)[((const HEDGE*)p2)->nodes[0]].id;
  if (r1 < r2) return -1;       /* return the sign of the difference */
  return (r1 > r2) ? 1 : 0;     /* of the identifiers of the */
}  /* he_cmp() */               /* representative nodes */

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

static HEDGE* he_rand (HTREE *ht, int size, double randfn (void))
{                               /* --- generate a random hyperedge */
  int   i, k, n, r;             /* loop variables, buffers */
  HEDGE *hedge;                 /* created hyperedge */
  HEDGE **hes, **hed;           /* to traverse the hyperedges */
  HCOMP *c;                     /* to traverse connected components */
  int   *s, *d, *nodes;         /* to traverse node identifiers */

  assert(ht && (size >= 2));    /* check the function arguments */
  if (ht->flags & HT_FULL)      /* if the hypertree is full, */
    return NULL;                /* abort the function */

  /* --- collect isolated nodes --- */
  c     = ht->comps;            /* get connected components and */
  nodes = d = ht->nodes;        /* the node identifier buffer */
  for (i = ht->nodecnt; --i >= 0; ) {
    r = c[i].id;                /* traverse all nodes */
    if ((r == i) && (c[i].cnt <= 1))
      *d++ = i;                 /* if the node is in no hyperedge, */
    else {                      /* note its identifier, otherwise */
      while (r != c[r].id) r = c[r].id;
      c[i].id = r;              /* find the representative node */
    }                           /* and note its identifier */
  }                             /* (flatten the references) */

  /* --- choose one hyperedge per connected component --- */
  hes = ht->hedges +(i = ht->hecnt);
  hed = ht->buf    + i;         /* copy the hyperedge pointers */
  while (--i >= 0) *--hed = *--hes; /* and sort the hyperedges */
  v_sort(hed, ht->hecnt, he_cmp, ht->comps);
  for (k = ht->hecnt; k > 0; k -= n) {
    s = (*hed)->nodes;          /* traverse the hyperedge groups */
    r = c[*s].id;               /* (i.e., the connected components) */
    for (hes = hed, n = 0; ++n < k; )
      if (c[(*++hes)->nodes[0]].id != r)
        break;                  /* count hyperedges with same rep. */
    i = (int)(randfn() *n);     /* compute a random vector index */
    if (i >= n) i = n-1;        /* in the range { 0, ..., n-1 } */
    if (i <  0) i = 0;          /* (select a random hyperedge) */
    hed += i;                   /* get the selected hyperedge */
    r = (*hed)->size;           /* and the number of nodes in it */
    for (s = (*hed)->nodes +(i = r); --i >= 0; )
      d[i] = *--s;              /* copy all nodes of the hyperedge */
    i = (int)(randfn() *r);     /* compute a random vector index */
    if (i >= r) i = r-1;        /* in the range { 0, ..., r-1 } */
    if (i <  0) i = 0;          /* (select a random node) */
    d[i] = d[--r]; d += r;      /* delete the selected node */
    hed = hes;                  /* (one node must be excluded), */
  }                             /* then go to next hyperedge group */

  /* --- create a new hyperedge --- */
  n = (int)(d -nodes);          /* get number of selectable nodes */
  if (size > n) size = n;       /* and adapt the hyperedge size */
  hedge = (HEDGE*)malloc(sizeof(HEDGE) +(size-1) *sizeof(int));
  if (!hedge) return NULL;      /* allocate a memory block and */
  hedge->size = size;           /* initialize the structure */

  /* --- select nodes of new hyperedge --- */
  for (d = hedge->nodes +(k = size); --k > 0; ) {
    i = (int)(randfn() *n);     /* compute a random vector index */
    if (i >= n) i = n-1;        /* in the range { 0, ..., n-1 } */
    if (i <  0) i = 0;          /* (select a random node) */
    *--d     = nodes[i];        /* get the identifier at the index */
    nodes[i] = nodes[--n];      /* and replace it by the last id. */
  }                             /* (compact identifier list) */
  s = hedge->nodes +size;       /* get a representative node and */
  r = c[*--s].id;               /* if it is possible that only nodes */
  if (c[r].cnt > 2) {           /* from one component get selected, */
    for (k = size-1; --k > 0; ) /* traverse the selected nodes and */
      if (c[*--s].id != r)      /* check for same representative node */
        break;                  /* if another is found, abort loop */
    if (k <= 0) {               /* if there is only one component */
      d = s = nodes;            /* traverse the remaining selectable */ 
      for (k = n; --k >= 0; s++)/* nodes and delete those that are */
        if (c[*s].id != r) *d++ = *s;         /* in this component */
      n = (int)(d -nodes);      /* (enforce two connected components) */
      assert(n > 0);            /* compute new number of selectable */
    }                           /* nodes and check this number */
  }
  i = (int)(randfn() *n);       /* compute a random vector index */
  if (i >= n) i = n-1;          /* in the range { 0, ..., n-1 } */
  if (i <  0) i = 0;            /* (select a random node) */
  hedge->nodes[0] = nodes[i];   /* get the identifier at the index */
  _nodesort(hedge->nodes, hedge->size);
  return hedge;                 /* sort the selected nodes and */
}  /* he_rand() */              /* return the created hyperedge */

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

static HEDGE* he_dup (HEDGE *hedge)
{                               /* --- duplicate hyperedge */
  int   i;                      /* loop variable */
  HEDGE *dup;                   /* created duplicate */
  int   *s, *d;                 /* to traverse the node identifiers */

  assert(hedge);                /* check the function argument */
  dup = (HEDGE*)malloc(sizeof(HEDGE) +(hedge->size-1) *sizeof(int));
  if (!dup) return NULL;        /* allocate a memory block and */
  dup->size = hedge->size;      /* initialize the structure */
  s = hedge->nodes +(i = hedge->size);
  d = dup->nodes   + i;         /* traverse the node identifiers and */
  while (--i >= 0) *--d = *--s; /* copy them to the new hyperedge */
  return dup;                   /* return the created duplicate */
}  /* he_dup() */

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

static int he_add (HTREE *ht, HEDGE *hedge)
{                               /* --- add a hyperedge to a hypertree */
  int   i, k, n, r;             /* loop variables, buffers */
  HCOMP *c;                     /* vector of connected comp. info */
  int   *ids;                   /* representing node identifiers */
  int   *s, *d;                 /* to traverse node identifiers */

  assert(ht && hedge);          /* check the function arguments */
  if (ht->flags & HT_FULL)      /* if the hypertree is already fully */
    return -1;                  /* connected, abort the function */

  /* --- determine representative nodes --- */
  c   = ht->comps;              /* get connected components info */
  ids = d = ht->nodes;          /* and pointer to buffer */
  for (s = hedge->nodes +(i = hedge->size); --i >= 0; ) {
    r = *--s;                   /* traverse the node identifiers */
    while (c[r].id != r) r = c[r].id;
    *d++ = c[*s].id = r;        /* for each node determine */
  }                             /* the representative node */
  _nodesort(ids, hedge->size);  /* sort the node identifiers */
  for (s = d = ids, i = hedge->size; --i > 0; )
    if (*++s != *d) *++d = *s;  /* remove duplicate identifiers and */
  n = (int)(++d -ids);          /* get number of connected components */
  if (n < 2) return -2;         /* check for more than one component */

  /* --- add the hyperedge to the hypertree --- */
  ht->hedges[ht->hecnt++] = hedge;
  ht->flags &= ~HT_CONSEQ;      /* clear the construction seq. flag */

  /* --- update connected components --- */
  k = 0; r = *ids;              /* traverse representative nodes */
  for (s = ids +(i = n); --i >= 0; ) {
    if (c[*--s].cnt > c[r].cnt) r = *s;
    k += c[*s].cnt;             /* find best new representative */
  }                             /* and sum represented nodes */
  for (s = ids +(i = n); --i >= 0; )
    c[*--s].id = r;             /* set id of new representative node */
  c[r].cnt = k;                 /* and number of represented nodes */
  if (k >= ht->nodecnt) {       /* if all nodes are in one component, */
    ht->flags |= HT_FULL; return 1; }          /* set the `full' flag */
  return 0;                     /* return the state of the hypertree */
}  /* he_add() */

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

static int he_subset (HEDGE *he1, HEDGE *he2, int *marks)
{                               /* --- check for node set subsumption */
  int n1,  n2;                  /* loop variables/vector indices */
  int *p1, *p2;                 /* to traverse the node identifiers */
  int r = 3;                    /* return code */

  assert(he1 && he2);           /* check the function arguments */
  p1 = he1->nodes +(n1 = he1->size) -1;
  p2 = he2->nodes +(n2 = he2->size) -1;
  if ((n1 > 0) && (n2 > 0)) {   /* if neither hyperedge is empty */
    while (r != 0) {            /* while subsumption is possible */
      if (marks) {              /* if a marker vector is given */
        while (marks[*p1] <= 0) { if (--n1 <= 0) goto term; --p1; }
        while (marks[*p2] <= 0) { if (--n2 <= 0) goto term; --p2; }
      }                         /* skip unmarked nodes */
      while (*p1 >  *p2) { r &= ~1; if (--n1 <= 0) goto term; --p1; }
      while (*p1 <  *p2) { r &= ~2; if (--n2 <= 0) goto term; --p2; }
      while (*p1 == *p2) { --p1; --p2; --n1; --n2;
        if ((n1 <= 0) || (n2 <= 0)) goto term; }
    }                           /* if in either hyperedge there is a */
  }                             /* node not contained in the other */
  term:                         /* clear the corresp. subset flag */
  if (r == 0) return 0;         /* if subsumption is imposs., abort */
  if (!marks) {                 /* if no marker vector is given, */
    if (n1 > 0) r &= ~1;        /* simply check whether */
    if (n2 > 0) r &= ~2; }      /* there are remaining nodes */
  else {                        /* if a marker vector is given */
    while (--n1 >= 0) { if (marks[*p1--] > 0) { r &= ~1; break; } }
    while (--n2 >= 0) { if (marks[*p2--] > 0) { r &= ~2; break; } }
  }                             /* check markers of the rem. nodes */
  return r;                     /* return subsumption flags */
}  /* he_subset() */

/*----------------------------------------------------------------------
The above function presupposes that the node identifiers are sorted
in ascending order (this is ensured with the function nodesort).
In the return code bit 0 is set if he1 \subseteq he2 and bit 1 is
set if he2 \subseteq he1. If he1 = he2, then both bits are set.
----------------------------------------------------------------------*/

static int he_check (HTREE *ht, HEDGE *hedge)
{                               /* --- check hyperedge */
  int   i, k, n, r;             /* loop variables, buffers */
  HEDGE **he;                   /* to traverse hyperedges */
  HCOMP *c;                     /* vector of connected components */
  int   *p1, *p2;               /* to traverse node identifiers */

  assert(hedge && ht);          /* check the function arguments */
  if (ht->flags & HT_FULL)      /* if the hypertree is already fully */
    return -1;                  /* connected, abort the function */