computegng.java

关于自组织神经网络的一种新结构程序,并包含了其它几种神经网络的程序比较

	// left neighbor
	if (x > 0)
	  d1 = (grid[x-1][y].node.x - grid[x][y].node.x) *
	       (grid[x-1][y].node.x - grid[x][y].node.x) +
	       (grid[x-1][y].node.y - grid[x][y].node.y) *
	       (grid[x-1][y].node.y - grid[x][y].node.y);

	// upper neighbor
	if (y > 0)
	  d2 = (grid[x][y-1].node.x - grid[x][y].node.x) *
	       (grid[x][y-1].node.x - grid[x][y].node.x) +
	       (grid[x][y-1].node.y - grid[x][y].node.y) *
	       (grid[x][y-1].node.y - grid[x][y].node.y);

	// right neighbor
	if (x < grid_x - 1)
	  d3 = (grid[x+1][y].node.x - grid[x][y].node.x) *
	       (grid[x+1][y].node.x - grid[x][y].node.x) +
	       (grid[x+1][y].node.y - grid[x][y].node.y) *
	       (grid[x+1][y].node.y - grid[x][y].node.y);

	// lower neighbor
	if (y < grid_y - 1)
	  d4 = (grid[x][y+1].node.x - grid[x][y].node.x) *
	       (grid[x][y+1].node.x - grid[x][y].node.x) +
	       (grid[x][y+1].node.y - grid[x][y].node.y) *
	       (grid[x][y+1].node.y - grid[x][y].node.y);
	
	max = Math.max(d1, Math.max(d2, Math.max(d3, d4)));

	if (max == d1)
	  n = insertColumn(x - 1);
	else if (max == d2)
	  n = insertRow(y - 1);
	else if (max == d3)
	  n = insertColumn(x);
	else
	  n = insertRow(y);

	return n;
  }

  /**
   * Add a row into the grid. The new row will be placed after index y.
   * 
   * @param y          The row index
   * @return           The index of the last inserted node or -1
   */
  protected int insertRow(int y) {
    if ( (grid_y == MAX_GRID_Y) || (nnodes + grid_x > maxNodes) )
      return -1;

	int n = -1;
	int i, j;

	// Insert nodes for the new row
	for (i = 0; i < grid_x; i++) {
	  n = addNode(0,0);
	  nodes[n].x_grid = i;
	  nodes[n].y_grid = grid_y;
	  grid[i][grid_y] = new GridNodeGNG(n, nodes[n]);

	  // Add Edges
	  if (i != 0)
		addEdge(grid[i][grid_y].index, grid[i-1][grid_y].index);
	  addEdge(grid[i][grid_y].index, grid[i][grid_y-1].index);
	}

	// Now change the parameters (position)
	for (j = grid_y; j > y+1; j--) {
	  for (i = 0; i < grid_x; i++) {
		grid[i][j].node.x = grid[i][j-1].node.x;
		grid[i][j].node.y = grid[i][j-1].node.y;
	  }
	}

	for (i = 0; i < grid_x; i++) {
	  grid[i][y+1].node.x = (grid[i][y].node.x + grid[i][y+1].node.x)*0.5f;
	  grid[i][y+1].node.y = (grid[i][y].node.y + grid[i][y+1].node.y)*0.5f;
	  grid[i][y+1].node.inserted = true;
	}

	// Make the new row official
	grid_y++;

    return n;
  }

  /**
   * Add a column into the grid. The new column will be placed after index x.
   * 
   * @param x          The column index
   * @return           The index of the last inserted node or -1
   */
  protected int insertColumn(int x) {
    if ( (grid_x == MAX_GRID_X) || (nnodes + grid_y > maxNodes) )
      return -1;

	int n = -1;
	int i, j;

	// Insert nodes for the new Column
	for (j = 0; j < grid_y; j++) {
	  n = addNode(0,0);
	  nodes[n].x_grid = grid_x;
	  nodes[n].y_grid = j;
	  grid[grid_x][j] = new GridNodeGNG(n, nodes[n]);

	  // Add Edges
	  if (j != 0)
		addEdge(grid[grid_x][j].index, grid[grid_x][j-1].index);
	  addEdge(grid[grid_x][j].index, grid[grid_x-1][j].index);
	}

	// Now change the parameters (position)
	for (i = grid_x; i > x+1; i--) {
	  for (j = 0; j < grid_y; j++) {
		grid[i][j].node.x = grid[i-1][j].node.x;
		grid[i][j].node.y = grid[i-1][j].node.y;
	  }
	}

	for (j = 0; j < grid_y; j++) {
	  grid[x+1][j].node.x = (grid[x][j].node.x + grid[x+1][j].node.x)*0.5f;
	  grid[x+1][j].node.y = (grid[x][j].node.y + grid[x+1][j].node.y)*0.5f;
	  grid[x+1][j].node.inserted = true;
	}

	// Make the new row official
	grid_x++;

    return n;
  }

  /**
   * Sort the array of nodes. The result is in the <TT> vsite</TT>-array.
   *  The implemented sorting algorithm is heapsort.
   * 
   * @param n          The number of nodes to be sorted
   * @see ComputeGNG#vsites
   * @see ComputeGNG#reheapVoronoi
   */
  protected void sortSites(int n) {
    SiteVoronoi exchange;
	int i;

    // Initialize the sorted site array
    for (i = 1; i <= n; i++) {
      NodeGNG nd = nodes[i-1];
      SiteVoronoi sv = new SiteVoronoi();
      sv.coord.x = nd.x;
      sv.coord.y = nd.y;
      sv.sitenbr = i-1;
      sv.refcnt = 0;
      vsites[i] = sv;
    }
    nNodesChangedB = false;

    // Build a maximum heap
    for (i = n/2; i > 0; i--)
      reheapVoronoi(i, n);

    // Switch elements 1 and i then reheap
    for (i = n; i > 1; i--) {
      exchange = vsites[1];
      vsites[1] = vsites[i];
      vsites[i] = exchange;
      reheapVoronoi(1, i-1);
    }
  }

  /**
   * Build a maximum-heap. The result is in the <TT> vsite</TT>-array.
   * 
   * @param i          The start of the intervall
   * @param k          The end of the intervall
   * @see ComputeGNG#vsites
   * @see ComputeGNG#sortSites
   */
  protected void reheapVoronoi(int i, int k) {
    int j = i;
    int son;
    
    while (2*j <= k) {
      if (2*j+1 <= k)
		if ( (vsites[2*j].coord.y > vsites[2*j+1].coord.y) ||
			 (vsites[2*j].coord.y == vsites[2*j+1].coord.y &&
			  vsites[2*j].coord.x > vsites[2*j+1].coord.x) )
		  son = 2*j;
		else
		  son = 2*j + 1;
      else
		son = 2*j;

      if ( (vsites[j].coord.y < vsites[son].coord.y) ||
		   (vsites[j].coord.y == vsites[son].coord.y &&
			vsites[j].coord.x < vsites[son].coord.x) ) {
		SiteVoronoi exchange = vsites[j];
		vsites[j] = vsites[son];
		vsites[son] = exchange;
		j = son;
      } else
		return;
    }
  }

  /**
   * Build a minimum-heap.
   * 
   * @param i          The start of the intervall
   * @param k          The end of the intervall
   */
  protected void reheap_min(int i, int k) {
    int j = i;
    int son;
    
    while (2*j <= k) {
      if (2*j+1 <= k)
		if (nodes[snodes[2*j]].dist < nodes[snodes[2*j+1]].dist)
		  son = 2*j;
		else
		  son = 2*j + 1;
	  else
		son = 2*j;

      if (nodes[snodes[j]].dist > nodes[snodes[son]].dist) {
		int exchange = snodes[j];
		snodes[j] = snodes[son];
		snodes[son] = exchange;
		j = son;
      } else
		return;
    }
  }

  /**
   * Delete the given node.
   * 
   * @param n          The index of a node
   */
  protected void deleteNode(int n) {
    NodeGNG node = nodes[n];
    int num = node.numNeighbors();
	int i;

    for (i = 0; i < num; i++)
      deleteEdge(n, node.neighbor(0));

    nNodesChangedB = true;
    nnodes--;
    nodes[n] = nodes[nnodes];
    nodes[nnodes] = null;

    // Now rename all occurances of nodes[nnodes] to nodes[n]
    for (i = 0 ; i < nnodes ; i++)
      nodes[i].replaceNeighbor(nnodes, n);
    for (i = 0 ; i < nedges ; i++)
      edges[i].replace(nnodes, n);

    return;
  }

  /**
   * Connect two nodes or reset the age of their edge. 
   * 
   * @param from          The index of the first node
   * @param to            The index of the second node
   */
  protected void addEdge(int from, int to) {
    if (nnodes < 2)
      return;

    if (nodes[from].isNeighbor(to)) {
      // Find edge(from,to) and reset age
      int i = findEdge(from, to);

      if (i != -1)
		edges[i].age = 0;
      return;
    }

    if (nedges == MAX_EDGES)
      return;

    if ( (nodes[from].moreNeighbors()) && (nodes[to].moreNeighbors()) ) {
      nodes[to].addNeighbor(from);
      nodes[from].addNeighbor(to);
    } else
      return;
    
    // Add new edge
    EdgeGNG e = new EdgeGNG();
    e.from = from;
    e.to = to;
    edges[nedges] = e;
    nedges++;
  }

  /**
   * Disconnect two nodes.
   * 
   * @param from          The index of the first node
   * @param to            The index of the second node
   */
  protected void deleteEdge(int from, int to) {
    int i = findEdge(from, to);
    if (i != -1) {
      nodes[edges[i].from].deleteNeighbor(edges[i].to);
      nodes[edges[i].to].deleteNeighbor(edges[i].from);
      nedges--;
      edges[i] = edges[nedges];
      edges[nedges] = null;
    }
    return;
  }

  /**
   * Delete an edge.
   * 
   * @param from          The index of the edge
   */
  protected void deleteEdge(int edgeNr) {
    nodes[edges[edgeNr].from].deleteNeighbor(edges[edgeNr].to);
    nodes[edges[edgeNr].to].deleteNeighbor(edges[edgeNr].from);
    nedges--;
    edges[edgeNr] = edges[nedges];
    edges[nedges] = null;
  }