graph.java

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

package edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph;

import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Point;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Observer;
import java.util.Vector;

import edu.odu.cs.zeil.AlgAE.Debug;

import edu.odu.cs.zeil.AlgAE.Client.Displayer;
import edu.odu.cs.zeil.AlgAE.Client.GraphicsInfo;
import edu.odu.cs.zeil.AlgAE.Client.MessageDispatcher;

import edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph.Edge;
import edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph.Node;
import edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph.IDTree;
import edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph.PartialSum;

/**
 * Collection of labelled nodes and edges that can be drawn.
 */
public class Graph extends IDTree implements Displayer
{
  /**
   *  Used to locate nodes via their ID's.
   */
  private Hashtable contentsByID;
  private MessageDispatcher dispatcher;
  
  /**
   * Prepare an empty graph.
   * @param g  Graphics context in which this graph will be drawn
   */
  public Graph(MessageDispatcher mDispatcher)
  {
    super ("-1");
    contentsByID = new Hashtable();
    dispatcher = mDispatcher;
    dispatcher.setDisplayer (this);
  }

  /**
   * Adds a node to the graph.
   * @param n  The node to be added. If already a component of some other
   *   graph or of some other node, it is first removed from there.
   */
  public void addNode (Node n) 
  {
    if (n.parent() != null)
	n.isolate();
    add (n);
    contentsByID.put(n.ID(), n);
  }


  /**
   * Removes a node from the graph.  All edges to/from the node are removed
   * as well.
   * @param n  The node to be removed.
   */
  public void remove (Node n) 
  {
    n.isolate();
    n.clearOutEdges();
    n.clearInEdges();
    contentsByID.remove (n.ID());
  }
  

  /**
   * Removes all unmarked nodes from the graph, and unmark the nodes
   * that are retained.
   */
  public void removeUnmarkedNodes () 
  {
    Vector removeThese = new Vector();
    
    boolean again = true;
    while (again) {
	again = false;
	for (Enumeration e = nodes(); e.hasMoreElements();) {
	    Node n = (Node)e.nextElement();
	    if (!n.getMarked())
		{
		    again = again || n.children().hasMoreElements();
		    n.clearComponents();
		}
	}
    }
    
    for (Enumeration e = nodes(); e.hasMoreElements();) {
      Node n = (Node)e.nextElement();
      if (!n.getMarked())
	removeThese.addElement (n);
      else
	n.setMarked (false);
    }

    for (Enumeration e = removeThese.elements(); e.hasMoreElements();) {
      Node n = (Node)e.nextElement();
      remove (n);
    }
  }
  

  /**
   * Unmarks all nodes.
   */
  public void unmarkNodes () 
  {
    for (Enumeration e = nodes(); e.hasMoreElements();) {
      Node n = (Node)e.nextElement();
      n.setMarked (false);
    }
  }


  /**
   * Find the node with the given ID
   *
   *   @param id Identifier to search for
   *   @return Return the node, if any, with that ID. If no such node exists,
   *           return null.
   */
  private IDTree get (String id)
  {
    return (IDTree)contentsByID.get(id);
  }


  /**
   * Given an ID, find the node with that ID.
   *  @param id The ID to look for.
   *  @return The node, if it exists.  Null, if no node with that ID exists.
   */
  public Node findNode (String id)
  {
    return (Node)get(id);
  }

  /**
   * Permits enumeration of all nodes in the graph that are not nested
   * components of another node.
   */
  public Enumeration nodes() 
  {
    return children();
  }

  /**
   * If an incremental movement is in progress, it is halted and all nodes
   * are moved to their last apparent position. If no incremental movement
   * is in effect, then this call does nothing.
   */
  public void freeze() 
  {
    for (Enumeration e = nodes(); e.hasMoreElements();) {
      Node n = (Node)e.nextElement();
      n.freeze();
    }
  }



  /**
   * Compute the size of all nodes.
   */
  public void computeSizes(GraphicsInfo graphicsInfo) 
  {
    Enumeration e;
    for (e = nodes(); e.hasMoreElements();)
	{
	    Node n = (Node)e.nextElement();
	    n.computeSize(graphicsInfo);
	}
  }


  /**
   * Shift and rescale the entire graph to fit within the visible canvas.
   * If <code>force</code> is false, then the graph is altered only if
   * one or more nodes are found to lie outside the bounds of the canvas.
   */
  public void recenter(boolean force, GraphicsInfo graphicsInfo) 
  {
    graphicsInfo.openGraphics();
    doRecenter (force, graphicsInfo);
    graphicsInfo.closeGraphics(false);
  }
  
  private void doRecenter(boolean force, GraphicsInfo graphicsInfo) 
  {
    // graphicsInfo.canvasSize = graphicsInfo.canvas.getSize();
    Point upperLeftBound = new Point();
    Point lowerRightBound = new Point();
    int nodeCount  = 0;

    Debug.show (Debug.recenter, "Entering Graph.recenter()");
    
    // Find the bounding rectangle containing all nodes
    computeSizes(graphicsInfo);

    Enumeration e;
    for (e = nodes(); e.hasMoreElements();)
	{
	    Node n = (Node)e.nextElement();
	    chooseInitialPosition (n, graphicsInfo);
	    Debug.show (Debug.recenter, "recenter Node id", n.ID());
	    Point pos = n.position();
	    Dimension sz = n.size();
	    Debug.show (Debug.recenter && (pos != null), "recenter Node pos", pos);
	    Debug.show (Debug.recenter, "recenter Node size", sz);
	    Point ulCorner = new Point();
	    Point lrCorner = new Point();
	    ulCorner.x = pos.x;
	    ulCorner.y = pos.y;
	    lrCorner.x = pos.x + sz.width;
	    lrCorner.y = pos.y + sz.height;
	    if (nodeCount == 0)
		{
		    upperLeftBound.x = ulCorner.x;
		    upperLeftBound.y = ulCorner.y;
		    lowerRightBound.x = lrCorner.x;
		    lowerRightBound.y = lrCorner.y;
		}
	    else
		{
		    upperLeftBound.x = Math.min(ulCorner.x, upperLeftBound.x);
		    upperLeftBound.y = Math.min(ulCorner.y, upperLeftBound.y);
		    lowerRightBound.x = Math.max(lrCorner.x, lowerRightBound.x);
		    lowerRightBound.y = Math.max(lrCorner.y, lowerRightBound.y);
		}
	    ++nodeCount;
	}
    
    Dimension canvasSize = graphicsInfo.getCanvasSize();
    Dimension textOffset = graphicsInfo.getTextOffset();
    
    Debug.show (Debug.recenter, "Graph.recenter: number of nodes: ",
		nodeCount);
    Debug.show (Debug.recenter, "              : upperLeft: ", upperLeftBound);
    Debug.show (Debug.recenter, "              : lowerRight: ",
		lowerRightBound);
    Debug.show (Debug.recenter, "  canvasSize: ", canvasSize);
    Debug.show (Debug.recenter, "  textOffset: ", textOffset);
    
    int inset = textOffset.width;
    if (nodeCount > 0 &&
	(force || upperLeftBound.x < inset || upperLeftBound.y < inset
	 || (lowerRightBound.x + inset > canvasSize.width)
	 || (lowerRightBound.y + inset > canvasSize.height)))
	{
	    // Translate all nodes so that the upper-leftmost node is near the
	    // upper left corner of the canvas.
	    int dx = 2*textOffset.width - upperLeftBound.x;
	    int dy = 2*textOffset.height - upperLeftBound.y;
	    Debug.show (Debug.recenter, "              : translation.x: ", dx);
	    Debug.show (Debug.recenter, "              : translation.y: ", dy);
	    
	    // Do the actual translation
	    for (e = nodes(); e.hasMoreElements();)
		{
		    Node n = (Node)e.nextElement();
		    n.translate (dx, dy);
		}
		
	    lowerRightBound.x += dx;		
	    upperLeftBound.x += dx;		
	    lowerRightBound.y += dy;		
	    upperLeftBound.y += dy;		

    	    // Scale all node positions to nearly fill the canvas.
	    if (nodeCount > 1)
	      {
		int d = canvasSize.width -
		    4*textOffset.width;
		if (d <= 0)
		    d = Math.max(canvasSize.width, 1);
		double sx = ((double)(d)) / (double)(lowerRightBound.x - upperLeftBound.x);
		
		d = canvasSize.height -
		    4*textOffset.height;
		if (d <= 0)
		    d = Math.max(canvasSize.height, 1);
		double sy = ((double)(d)) / (double)(lowerRightBound.y - upperLeftBound.y);
		
		Debug.show (Debug.recenter, "              : scale.x: ",  sx);
		Debug.show (Debug.recenter, "              : scale.y: ",  sy);
	    
		// Do the actual scaling.
		for (e = nodes(); e.hasMoreElements();)
		  {
		    Node n = (Node)e.nextElement();
			n.scale (sx, sy);
		  }
		  
	      }   
	}
    Debug.show (Debug.recenter, "Leaving Graph.recenter()");
  }
  
  
  
    
    

  /**
   * Attempt to find more visually pleasing positions for all nodes.
   */
  public void reposition(GraphicsInfo graphicsInfo) 
  {
    double lengthSum = 0.0;
    int edgeCount = 0;

    graphicsInfo.openGraphics();

    computeSizes(graphicsInfo);

    Enumeration e;
    for (e = nodes(); e.hasMoreElements();) {
      Node n = (Node)e.nextElement();
      chooseInitialPosition (n, graphicsInfo);
    }
      
    for (e = nodes(); e.hasMoreElements();) {
      Node n = (Node)e.nextElement();
      n.beginPositioning();
      PartialSum p = n.tallyEdgeLengths();
      lengthSum += p.sumOfLengths;
      edgeCount += p.nEdges;
    }
  
    double targetLength;
    if (edgeCount > 0)
      targetLength = lengthSum / edgeCount;
    else
      targetLength = 25;

    
    for (int effort = 0; effort < graphicsInfo.repositionEffort; ++effort)
      {
	for (e = nodes(); e.hasMoreElements();) {
	  Node n = (Node)e.nextElement();
	  n.reposition(graphicsInfo, this, targetLength);
	}
      }
    doRecenter(false, graphicsInfo);
    
    for (e = nodes(); e.hasMoreElements();) {
      Node n = (Node)e.nextElement();
      n.endPositioning ();
    }
    
    graphicsInfo.closeGraphics(false);
    dispatcher.requestDisplay();
  }
  


  
  /**
   *  Choose an initial position for this node and for its components
   */
  void chooseInitialPosition (Node n, GraphicsInfo graphicsInfo)
  {
    if (n.position() == null) {
      //      n.chooseInitialPosition(graphicsInfo, this);
      n.reposition(graphicsInfo, this, 2*graphicsInfo.getTextOffset().width);
      for (Enumeration e = n.children(); e.hasMoreElements();) {
	Node child = (Node)e.nextElement();	
	chooseInitialPosition (child, graphicsInfo);
      }
    }
  }
  
  /**
   *  Open a graphics context and draw the entire graph to it.
   */
  public void display (GraphicsInfo graphicsInfo) 
  {
    synchronized (dispatcher) {
      if (graphicsInfo.getCanvas().isShowing())
	{
	  graphicsInfo.openGraphics();

	  Debug.show (Debug.graphDraw, "Starting to draw nodes");
	  // First, draw the nodes
	  Enumeration e;
	  for (e = nodes(); e.hasMoreElements();) {
	      Node n = (Node)e.nextElement();
	      chooseInitialPosition (n, graphicsInfo);
	      n.incrementPosition(graphicsInfo);
	      n.draw(graphicsInfo);
	  }
    

	  Debug.show (Debug.graphDraw, "Starting to draw edges");
	  // Then, draw the edges
	  // (This is done as a separate step after drawing all nodes
	  // simply because I think it looks better to have edges crossing
	  // over nodes than vice-versa.)
	  for (e = nodes(); e.hasMoreElements();) {
	      Node n = (Node)e.nextElement();
	      n.drawEdges(graphicsInfo);
	  }
	  Debug.show (Debug.graphDraw, "Done drawing edges");
	  
	  graphicsInfo.closeGraphics (true);
	}
    }
  }



}