testsom.c

SOM-sd 是现在国外非常流行的一个神经网络的结构自组织特征映射算法

Description: 

Return value: 
******************************************************************************/
void MapGraph(struct Parameters parameters, int x, int y)
{
  int n;
  FLOAT qerr;
  struct Graph *graph;
  struct Node *node;
  struct Map *map;
  struct Winner winner;
  struct Hits{
    int gnum;
    int nnum;
    FLOAT err;
  } **hits;

  if (parameters.train == NULL)
    return;

  map = &parameters.map;

  /* Find the winners for all nodes */
  if (KstepEnabled)
    qerr = K_Step_Approximation(map, parameters.train, 1);
  else
    qerr = GetNodeCoordinates(map, parameters.train);
  fprintf(stderr, "Qerror:%f\n", qerr);

  if (x >= 0 && y >= 0){
    for (graph = parameters.train; graph != NULL; graph = graph->next){
      for (n = 0; n < graph->numnodes; n++){
	node = graph->nodes[n];
	if (x == node->x && y == node->y){
	  printf("%d %d %d %d\n", x, y, graph->gnum, node->nnum);
	  fprintf(stderr, "%s\n", graph->gname);
	}
      }
    }
  }
  else{
    hits = (struct Hits**)MyMalloc(map->ydim * sizeof(struct Hits*));
    for (y = 0; y < map->ydim; y++)
      hits[y] = (struct Hits*)MyCalloc(map->xdim, sizeof(struct Hits));

    for (y = 0; y < map->ydim; y++)
      for (x = 0; x < map->xdim; x++){
	hits[y][x].gnum = -1;
	hits[y][x].err = MAX_FLOAT;
      }

    for (graph = parameters.train; graph != NULL; graph = graph->next){
      for (n = 0; n < graph->numnodes; n++){
	node = graph->nodes[n];
	FindWinnerEucledian(map, node, graph, &winner);  //Find best match at location
	if (hits[node->y][node->x].err > winner.diff){
	  if (node->y != map->codes[winner.codeno].y && node->x != map->codes[winner.codeno].y)
	    fprintf(stderr, "Internal error\n");
	  hits[node->y][node->x].gnum = graph->gnum;
	  hits[node->y][node->x].nnum = node->nnum;
	  hits[node->y][node->x].err = winner.diff;
	}
      }
    }

    for (y = 0; y < map->ydim; y++)
      for (x = 0; x < map->xdim; x++)
	if (hits[y][x].gnum >= 0)
	  printf("%d %d %d %d\n", x, y, hits[y][x].gnum, hits[y][x].nnum);

    for (y = 0; y < map->ydim; y++)
      free(hits[y]);
    free(hits);
  }
}

/******************************************************************************
Description: 

Return value: 
******************************************************************************/
void VisualizeGraph(struct Parameters parameters)
{
  int nnum, gnum;
  int x, y, n;
  float scale = 200;
  int xpos, ypos;
  struct Graph *graph;
  struct Node *node;
  struct VMap vmap;

  if (KstepEnabled)
    K_Step_Approximation(&parameters.map, parameters.train, 1);
  else
    GetNodeCoordinates(&parameters.map, parameters.train);

  vmap = GetHits(parameters.map.xdim, parameters.map.ydim, parameters.train, LEAF | INTERMEDIATE | ROOT | QUIET);
  PrintXfigHeader(stdout);
  DrawMap(parameters.map, scale*10, &vmap);

  fscanf(stdin, "%d %d %d %d", &x, &y, &gnum, &nnum);
  while (!feof(stdin)){
    for (graph = parameters.train; graph != NULL && graph->gnum != gnum; graph = graph->next);
    if (graph != NULL){
      for (n = 0; n < graph->numnodes; n++){
	if (graph->nodes[n]->nnum == nnum)
	  break;
      }
      if (n == graph->numnodes){
	fprintf(stderr, "Node not found error\n");
	return;
      }
      node = graph->nodes[n];

      xpos = 2*x*scale*13/3;
      ypos = y*scale*13-scale*13/2;
      if (x % 2)
	ypos -= scale*13/2;

      DrawXfigGraphAt(stdout, graph, node, xpos, ypos, scale);
    }
    fscanf(stdin, "%d %d %d %d", &x, &y, &gnum, &nnum);
  }
}

/******************************************************************************
Description: 

Return value: 
******************************************************************************/
void VisualizeSubGraphs(struct Parameters parameters)
{
  int n, nnum, gnum;
  FLOAT qerr;
  int x, y;
  float scale = 200;
  int xpos, ypos;
  struct Graph *graph;
  struct Node *node;
  struct VMap vmap;

  /* Find the winners for all nodes */
  if (KstepEnabled)
    qerr = K_Step_Approximation(&parameters.map, parameters.train, 1);
  else
    qerr = GetNodeCoordinates(&parameters.map, parameters.train);
  fprintf(stderr, "Qerror:%f\n", qerr);

  vmap = GetHits(parameters.map.xdim, parameters.map.ydim, parameters.train, LEAF | INTERMEDIATE | ROOT);

  PrintXfigHeader(stdout);
  DrawMap(parameters.map, scale*10, &vmap);

  fscanf(stdin, "%d %d %d %d", &x, &y, &gnum, &nnum);
  while (!feof(stdin)){
    for (graph = parameters.train; graph != NULL && graph->gnum != gnum; graph = graph->next);
    if (graph != NULL){
      fprintf(stderr, "%s\n", graph->gname);
      for (n = 0; n < graph->numnodes; n++){
	node = graph->nodes[n];
	x = node->x;
	y = node->y;

	xpos = 2*x*scale*13/3;
	ypos = y*scale*13-scale*13/2;
	if (x % 2)
	  ypos -= scale*13/2;

	DrawXfigGraphAt(stdout, graph, node, xpos, ypos, scale);
      }
    }
    fscanf(stdin, "%d %d %d %d", &x, &y, &gnum, &nnum);
  }
}

/******************************************************************************
Description: 

Return value: 
******************************************************************************/
void VisualizeClustering(struct Parameters parameters)
{
  int nnum, gnum;
  int x, y, n;
  float scale = 200;
  int xpos, ypos;
  struct Graph *graph;
  struct Node *node;
  struct VMap vmap;

  if (KstepEnabled)
    K_Step_Approximation(&parameters.map, parameters.train, 1);
  else
    GetNodeCoordinates(&parameters.map, parameters.train);

  vmap = GetHits(parameters.map.xdim, parameters.map.ydim, parameters.train, LEAF | INTERMEDIATE | ROOT);

  GetClusterID(parameters.map, parameters.train, &vmap);

  PrintXfigHeader(stdout);
  DrawMap(parameters.map, scale*10, &vmap);

  fscanf(stdin, "%d %d %d %d", &x, &y, &gnum, &nnum);
  while (!feof(stdin)){
    for (graph = parameters.train; graph != NULL && graph->gnum != gnum; graph = graph->next);
    if (graph != NULL){
      for (n = 0; n < graph->numnodes; n++){
	if (graph->nodes[n]->nnum == nnum)
	  break;
      }
      if (n == graph->numnodes){
	fprintf(stderr, "Node not found error\n");
	return;
      }
      node = graph->nodes[n];

      xpos = 2*x*scale*13/3;
      ypos = y*scale*13-scale*13/2;
      if (x % 2)
	ypos -= scale*13/2;

      DrawXfigGraphAt(stdout, graph, node, xpos, ypos, scale);
    }
    fscanf(stdin, "%d %d %d %d", &x, &y, &gnum, &nnum);
  }
}


/******************************************************************************
Description: 

Return value: 
******************************************************************************/
char *GetStructID2(int FanOut, struct Node *node, char *StructID)
{
  int c;

  memmove(StructID+2, StructID, strlen(StructID)+1);
  StructID[0] = '(';
  StructID[1] = ')';

  for (c = 0; c < FanOut; c++){
    if (node->children[c] != NULL)
      GetStructID2(FanOut, node->children[c], StructID+1);
  }
  return NULL;
}

/******************************************************************************
Description: 

Return value: 
******************************************************************************/
char *GetStructID(int FanOut, struct Node *node, char *StructID)
{
  if (FanOut == 0)
    return NULL;
  else if (FanOut == 1){  //sequences
    sprintf(StructID, "(%d)", node->depth+1);
    return NULL;
  }
  else
    return GetStructID2(FanOut, node, StructID);
}

int comparStructID(const void *v1, const void *v2)
{
  struct AllHits *a1, *a2;

  a1 = (struct AllHits*)v1;
  a2 = (struct AllHits*)v2;

  return strcmp(a1->structID, a2->structID);
}

int comparsubStructID(const void *v1, const void *v2)
{
  struct AllHits *a1, *a2;

  a1 = (struct AllHits*)v1;
  a2 = (struct AllHits*)v2;

  return strcmp(a2->substructID, a1->substructID);
}

int comparFloat(const void *v1, const void *v2)
{
  return ((*((FLOAT*)v1)) > (*((FLOAT*)v2)));
}


/******************************************************************************
Description: 

Return value: 
******************************************************************************/
void AnalyseDataset(struct Parameters parameters)
{
  int i, j, n, r;
  int ni, nG, N;
  int nsub, nsdsub;
  char *buffer, *rbuf, *bigbuf;
  struct Graph *graph;
  struct Node *node;
  struct AllHits *harray;
  int minnodes, maxnodes;
  int V = 0, Vn = 0;
  FLOAT *labelval;
  int l, nl = 0, no, o, tmpo;
  int maxO = 0, minO, totalO;
  int olen;
  char *ctmp;
  int nlinks, yme;
  int roots, lroots;

  if (parameters.train == NULL){
    fprintf(stderr, "Error: No training set given.");
    return;
  }

  for (graph = parameters.train; graph != NULL; graph = graph->next){
    roots = 0;
    lroots = 0;
    for (n = 0; n < graph->numnodes; n++){
      node = graph->nodes[n];
      if (IsRoot(node)){
	roots++;
	if (strcmp(GetLabel(node->label), "*"))
	  lroots++;
      }
    }
    if (roots > 1 && lroots > 0 && roots != lroots){
      fprintf(stderr, "Graph %s has more than one root nodes where some of which are unlabelled.\n", graph->gname);
    }
    if (roots == 0){
      fprintf(stderr, "Graph %s has no root node.\n", graph->gname);
    }
  }

  N = 0;
  nG = 0;
  minnodes = INT_MAX;
  maxnodes = 0;
  for (graph = parameters.train; graph != NULL; graph = graph->next){
    if (maxnodes < graph->numnodes)
      maxnodes = graph->numnodes;
    if (minnodes > graph->numnodes)
      minnodes = graph->numnodes;
    nG++;
    for (n = 0; n < graph->numnodes; n++)
      N++;
  }

  fprintf(stderr, "Total number of graphs: %d\n", nG);
  fprintf(stderr, "Total number of nodes : %d\n", N);
  fprintf(stderr, "Size of graphs: min %d nodes, ", minnodes);
  fprintf(stderr, "max %d nodes, avg %.2f nodes\n", maxnodes, (float)N/nG);

  if (parameters.train->FanOut == 1){/* Sequences */
    buffer = MyCalloc((maxnodes*3+1), sizeof(char));
    bigbuf = MyCalloc(parameters.train->ldim * 12 + (maxnodes*3+1), sizeof(char));
  }
  else{
    buffer = MyCalloc((maxnodes*2+1), sizeof(char));
    bigbuf = MyCalloc(parameters.train->ldim * 12+ (maxnodes*2+1), sizeof(char));
  }
  harray = (struct AllHits*)MyCalloc(N, sizeof(struct AllHits));
  labelval = (FLOAT*)MyCalloc(N, sizeof(FLOAT));

  ni = 0;
  rbuf = NULL;
  olen = 0;
  nlinks = 0;
  totalO = 0;
  yme = 0;

  for (graph = parameters.train; graph != NULL; graph = graph->next){
    r = -1;
    for (n = 0; n < graph->numnodes; n++){
      if (IsRoot(graph->nodes[n])){
	r = n;
	break;
      }
    }
    if (r == -1){
      fprintf(stderr, "Error: There is a graph with no root node\n");
      exit(0);
    }

    memset(buffer, 0, olen);
    GetStructID(graph->FanOut, graph->nodes[r], buffer);
    olen = strlen(buffer);
    rbuf = memdup(buffer, olen+1);

    minO = INT_MAX;
    tmpo = 0;
    for (n = 0; n < graph->numnodes; n++){
      node = graph->nodes[n];
      harray[ni].graph = graph;
      harray[ni].node = node;
      harray[ni].structID = rbuf;
      memset(buffer, 0, olen);
      GetStructID(graph->FanOut, node, buffer);
      olen = strlen(buffer);
      harray[ni].substructID =(char*)memdup(buffer, olen+1);

      for (l = 0; l < graph->ldim; l++)
	labelval[ni] += node->points[l] * node->points[l];

      no = 0;
      for (o = 0; o < graph->FanOut; o++)
	if (node->children[o] != 0){
	  no++;
	  nlinks++;
	}
      if (tmpo < no)
	tmpo = no;

      ni++;
    }
    if (tmpo > 34)
      yme++;
    if (tmpo > maxO){
      maxO = tmpo;
      ctmp = graph->gname;
    }
    if (minO > tmpo){
      minO = tmpo;
    }
    totalO += tmpo;
  }
  nsub = 0;
  nsdsub = 0;
  if (ni > 0){
    qsort(harray, N, sizeof(struct AllHits), comparStructID);
    V=1;
    Vn = harray[0].graph->numnodes;
    for (i = 1; i < N; i++){
      if (strcmp(harray[i-1].structID, harray[i].structID)){
	Vn += harray[i].graph->numnodes;
	V++;
      }
      //      printf("%s\n", harray[i].structID);
    }
    qsort(harray, N, sizeof(struct AllHits), comparsubStructID);
    nsub = 1;
    for (i = 1; i < N; i++){
      if (strcmp(harray[i-1].substructID, harray[i].substructID))
	nsub++;
    }
    //    printf("#\n");

    for (i = 0; i < N; i++){
      *bigbuf = '\0';