node.java.x

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

  void drawEdges(GraphicsInfo gi)
  {
    if (!isHidden())
      {
	Graphics g = gi.g;
	g.setColor (color());
	for (Enumeration ei = outEdges(); ei.hasMoreElements();)
	  {
	    Edge e = (Edge)(ei.nextElement());
	    e.draw (gi);
	  }

	// Draw edges from the inner components, if any
	for (Enumeration e = children(); e.hasMoreElements(); )
	  {
	    Node child = (Node)(e.nextElement());
	    child.drawEdges(gi);
	  }
      }
  }
  

  /**
   * Compute the size of this node, given its current label and nested
   * components.  The result is stored in the node's <code>nodeSize</code> data
   * member.
   *  @param gi Graphics context information
   */
  void computeSize(GraphicsInfo gi)
  {
    nodeSize.width = gi.textOffset.width;
    nodeSize.height = gi.textOffset.height;

    if (text != null && text.length() > 0)
      {
	gi.g.setFont(gi.font);
	FontMetrics fm = gi.g.getFontMetrics();
	stringWidth = fm.stringWidth(fullText);
	nodeSize.width += stringWidth + gi.textOffset.width;
	nodeSize.height += fm.getAscent() + gi.textOffset.height;
      }

    if (vertical)
      {
	for (Enumeration e = children(); e.hasMoreElements(); )
	  {
	    Node child = (Node)(e.nextElement());
	    child.computeSize(gi);
	    if (child.oldPosition == null)
	      child.oldPosition = new Point();

	    child.oldPosition.x = gi.textOffset.width;
	    child.oldPosition.y = nodeSize.height;
	    nodeSize.height += child.nodeSize.height + gi.textOffset.height;
	    nodeSize.width = Math.max
	      (nodeSize.width,
	       child.nodeSize.width+2*gi.textOffset.width);
	  }
      }
    else
      {
	int componentWidth = gi.textOffset.width;
	int componentHeight = 0;
	for (Enumeration e = children(); e.hasMoreElements(); )
	  {
	    Node child = (Node)(e.nextElement());
	    child.computeSize(gi);
	    if (child.oldPosition == null)
	      child.oldPosition = new Point();

	    child.oldPosition.x = componentWidth;
	    child.oldPosition.y = nodeSize.height;
	    componentWidth += child.nodeSize.width + gi.textOffset.width;
	    componentHeight = Math.max
	      (componentHeight, child.nodeSize.height);
	  }
	if (componentHeight > 0)
	  {
	    nodeSize.height += componentHeight + gi.textOffset.height;
	    nodeSize.width = Math.max(nodeSize.width,
				      componentWidth+2*gi.textOffset.width);
	  }
      }
  }


  /**
   * Used in repositioning nodes, this function computes a penalty score
   * based on how far the edges into and out of the node are bent away
   * from their "ideal" angle and on how much their length differs from
   * a given target length.
   *   @param targetLength  The desired length for all edges
   *   @return The penalty value
   */
  private double edgeScore(double targetLength)
  {
    Debug.show (Debug.edgeScore, "edgeScore ", ID());
    double score = 0.0;
    for (Enumeration ei = outEdges(); ei.hasMoreElements();)
      {
	Edge e = (Edge)(ei.nextElement());
	score += e.positionScore(targetLength);
	if (e.destination != null)
	  {
	  Debug.show (Debug.edgeScore, "  dest: ", + e.destination.ID());
	  Debug.show (Debug.edgeScore, "  score: ", score);
	  }
	else
	  Debug.show (Debug.edgeScore, "  score: ", score);
      }
    for (Enumeration ei = inEdges(); ei.hasMoreElements();)
      {
	Edge e = (Edge)(ei.nextElement());
	score += e.positionScore(targetLength);
	if (e.destination != null)
	  Debug.show (Debug.edgeScore, "  dest: ", e.destination.ID());
	Debug.show (Debug.edgeScore, "  score: ", score);
      }
    return score;
  }


  /**
   *  Checks to see if this node overlaps another.
   *
   *  @param n any node
   *  @return true if this node overlaps n
   */
  private boolean overlaps (Node n)
  {
    if ((n.currentPosition.y + n.nodeSize.height < currentPosition.y)
	|| (n.currentPosition.y > currentPosition.y + n.nodeSize.height)
	|| (n.currentPosition.x + n.nodeSize.width < currentPosition.x)
	|| (n.currentPosition.x > currentPosition.x + n.nodeSize.width))
      return false;
    else
      return true;
  }
  

  
  /**
   * Used in repositioning nodes, this function computes a penalty score
   * based on the edge score and the number of nodes overlapping this one.
   *
   *   @see edgeScore
   *
   *   @param targetLength  The desired length for all edges
   *   @return The penalty value
   */
  private double positionScore(double targetLength)
  {
    // Nodes that are less than this number of "body lengths" away
    // from each other are subject to a "repulsion penalty" to push them
    // apart.
    final int repulsionSensitivity = 3;
    final double repulsionStrength = 15.0;

    Debug.show (Debug.positionScore, "positionScore ", ID());
    double repulsionPenalty = 1.0;
    int s1 = (nodeSize.width + nodeSize.height) / 2;

    if (targetLength < (double)s1)
      targetLength = (double)s1;

    Point currentPos = position();
    
    for (Enumeration e = parent().children(); e.hasMoreElements(); )
      {
	Node n = (Node)(e.nextElement());
	if (n != this) {
	  Point nCurrentPos = n.position();
	  int dx = Math.abs(currentPos.x + nodeSize.width/2 -
			    nCurrentPos.x - n.nodeSize.width/2);
	  int dy = Math.abs(currentPos.y + nodeSize.height/2 -
			    nCurrentPos.y - n.nodeSize.height/2);
	  int s2 = (n.nodeSize.width + n.nodeSize.height) / 2;
	  int limit = repulsionSensitivity * (s1 + s2);
	  
	  if (dx + dy < limit)
	    {
	      double p = 1.0 - ((double)(dx + dy)) / ((double)limit);
	      repulsionPenalty += /* repulsionStrength * */ p * p;
	    }
	}
      }
    
    Debug.show (Debug.positionScore,
		"  repulsion penalty: ", repulsionPenalty);
    double score = (1.0 + edgeScore(targetLength)) * repulsionPenalty;

    for (Enumeration e = children(); e.hasMoreElements(); )
      {
	Node child = (Node)(e.nextElement());
	score += child.positionScore (targetLength);
      }
    return score;
  }


  /**
   * Used in repositioning nodes, this function computes a penalty score
   * based on the edge score and the number of nodes overlapping this one.
   * 
   *   @see edgeScore
   *
   *   @param targetLength  The desired length for all edges
   *   @param pos           The node's currentPosition is set to this before
   *                        evaluating the score.
   *   @return The penalty value
   */
  private double positionScore(double targetLength, Point pos)
  {
    currentPosition = pos;
    return positionScore (targetLength);
  }

  
  /**
   * Aids in computing the average length of all edges in the graph.
   *  @return The sum of the lengths of all edges emanating from this node
   *   and the number of non-zero-length outgoing edges.
   */
  PartialSum tallyEdgeLengths()
  {
    PartialSum p = new PartialSum();
    p.nEdges = 0;
    p.sumOfLengths = 0.0;
    for (Enumeration ei = outEdges.edges(); ei.hasMoreElements();)
      {
	Edge e = (Edge)(ei.nextElement());
	if ((this != e.destination) && (e.destination != null))
	  {
	    p.sumOfLengths += e.length();
	    ++p.nEdges;
	  }
      }

    for (Enumeration e = children(); e.hasMoreElements(); )
      {
	Node child = (Node)(e.nextElement());
	PartialSum pInner = child.tallyEdgeLengths();
	p.sumOfLengths += pInner.sumOfLengths;
	p.nEdges += p.nEdges;
      }

    return p;
  }


  /**
   *  Find the best position to place this node along a specified
   *  line segment.
   *
   *  @param targetLength  Desired average length for all edges.
   *  @param endpoint1  One endpoint of the line segment.
   *  @param endpoint2  The other endpoint.
   *  @return The point along the line segment from <code>endpoint1</code>
   *    to <code>endpoint2</code> that minimizes the node's position score.
   *
   *  @see positionScore
   */
  private Point optimalPosition (double targetLength,
				 Point endpoint1,
				 Point endpoint2)
  {
    Point savedCurrentPosition = currentPosition;

    Point p1 = new Point(endpoint1);
    Point p3 = new Point(endpoint2);
    Point p2 = new Point((p1.x + p3.x)/2, (p1.y + p3.y)/2);
    double s1 = positionScore (targetLength, p1);
    double s2 = positionScore (targetLength, p2);
    double s3 = positionScore (targetLength, p3);
    

    Point ptmp;
    double stmp;

    // Stage 1: binary search until the middle point has a smaller score
    //  than either endpoint.
    while ((s2 >= s1 || s2 >= s3)
	   && (p2.x != p3.x || p2.y != p3.y)
	   && (p2.x != p1.x || p2.y != p1.y))
      {
	Debug.show (Debug.reposition, "binary search: p1 ", p1);
	Debug.show (Debug.reposition, "             : p2 ", p2);
	Debug.show (Debug.reposition, "             : p3 ", p3);
	Debug.show (Debug.reposition, "             : s1 ", s1);
	Debug.show (Debug.reposition, "             : s2 ", s2);
	Debug.show (Debug.reposition, "             : s3 ", s3);
	
	if (s1 > s3)
	  {
	    ptmp = p1;
	    p1 = p2;
	    s1 = s2;
	    p2 = ptmp;
	  }
	else
	  {
	    ptmp = p3;
	    p3 = p2;
	    s3 = s2;
	    p2 = ptmp;
	  }
	p2.x = (p1.x + p3.x) / 2;
	p2.y = (p1.y + p3.y) / 2;
	s2 = positionScore (targetLength, p2);
      }

    // Stage 2: valley search
    Point p4 = p3;
    p3 = new Point ((p2.x + p4.x)/2, (p2.y + p4.y)/2);
    double s4 = s3;
    s3 = positionScore (targetLength, p3);

    int d12 = 5;
    int d24 = 0;

    while (d12 + d24 > 4)
      {
	Debug.show (Debug.reposition, "valley search: p1 ", p1);
	Debug.show (Debug.reposition, "             : p2 ", p2);
	Debug.show (Debug.reposition, "             : p3 ", p3);
	Debug.show (Debug.reposition, "             : p4 ", p4);
	Debug.show (Debug.reposition, "             : s1 ", s1);
	Debug.show (Debug.reposition, "             : s2 ", s2);
	Debug.show (Debug.reposition, "             : s3 ", s3);
	Debug.show (Debug.reposition, "             : s4 ", s4);
	if (s2 < s3)
	  {
	    // Keep points p1, p2, p3
	    ptmp = p4;
	    p4 = p3;
	    s4 = s3;
	  }
	else
	  {
	    // Keep points p2, p3, p4
	    ptmp = p1;
	    p1 = p2;
	    p2 = p3;

	    s1 = s2;
	    s2 = s3;
	  }

	// Points p1, p2, p4 are in order, (p3 is garbage)
	// Choose a point midway in the larger of the p1..p2 and p2..p4
	//  ranges.
	d12 = Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
	d24 = Math.abs(p2.x - p4.x) + Math.abs(p2.y - p4.y);
	if (d12 < d24)
	  {
	    // new point is between p2 and p4
	    p3 = ptmp;
	    p3.x = (p2.x + p4.x) / 2;
	    p3.y = (p2.y + p4.y) / 2;
	    s3 = positionScore (targetLength, p3);
	  }
	else
	  {
	    // new point is between p1 and p2
	    p3 = p2;
	    s3 = s2;
	    p2 = ptmp;
	    p2.x = (p1.x + p3.x) / 2;
	    p2.y = (p1.y + p3.y) / 2;
	    s2 = positionScore (targetLength, p2);
	  }
      }

    currentPosition = savedCurrentPosition;
    return p2;
  }
  

				 

  /**
   * Add a nested component of this node.
   *  @param vn Node to add
   */
  public void addComponent (Node vn)
  {
    vn.isolate();
    vn.oldPosition = vn.currentPosition = vn.newPosition = null;
    super.add (vn);
  }

  /**
   * Remove a nested component of this node.
   *  @param vn Node to remove
   *  @return True if vn was a component of this node (in which case it has
   *    been removed). False if it was not (in which case nothing was done).
   */
  boolean removeComponent (Node vn)
  {
    if (vn.parent() == this)
      {
	vn.isolate();
	vn.oldPosition = vn.currentPosition = vn.newPosition = null;
	return true;
      }
    else
      return false;
  }

  /**
   * Highlight this node by changing it to a contrasting color.
   */
  public void highlight() 
  {
    highlight (new Color(0xffffffff - normalColor.getRGB()));
  }

  /**
   * Highlight this node by changing it to a given color.
   *  @param c the new color
   */
  public void highlight(Color c) 
  {
    currentColor = new Color(c.getRGB());
  }
  
  /**
   * Cancel any previous highlighting of this node, restoring its normal
   * color.
   */
  public void unHighlight() 
  {
    currentColor = normalColor;
  }

  /**
   *  What is the current color of this node? (May include highlighting).
   *    @return the color
   */
  public Color color() 
  {
    return currentColor;
  }


  /**
   *  Change the normal ("permanent") color of this node.
   *    @param v   the color
   */
  public void setColor(Color v) 
  {
    if (currentColor == normalColor)
      currentColor = v;
    normalColor = v;
  }


  /**
   *  Make this node invisible.  
   */
  public void hide()
  {
    hidden = true;
  }

  /**
   *  Is this node invisible?
   */
  public boolean isHidden()
  {
    return hidden;
  }