graphlayout.java

一个用java语言编写的网络爬虫程序

/*
 * WebSPHINX web crawling toolkit
 * Copyright (C) 1998,1999 Carnegie Mellon University 
 * 
 * This library is free software; you can redistribute it
 * and/or modify it under the terms of the GNU Library
 * General Public License as published by the Free Software 
 * Foundation, version 2.
 *
 * WebSPHINX homepage: http://www.cs.cmu.edu/~rcm/websphinx/
 */
package websphinx.util; // but no dependencies on websphinx.workbench!

// Daniel Tunkelang's graph-drawing packages
import graph.*; 
import gd.*;

import java.util.*;
import java.awt.*;
import java.awt.image.ImageObserver;

public class GraphLayout extends Canvas implements Runnable, ImageObserver {

    Graph graph;   // graph to display

    double restLength = 50;       // default rest length of an edge
    double springConstant = 100;  // attraction between connected nodes
    double nodeCharge = 10000;    // repulsion between any pair of nodes

    GDAlgorithm algorithm;     // algorithm used for automatic graph layout

    boolean running = false;   // is repaint thread running?
    boolean automaticLayout = true; // is automatic graph layout enabled?
    double threshold = 100;    // if an iteration shows less "improvement" than
                               // this threshold, stop iterating
    boolean quiescent = true;  // is the graph stable?
    boolean dirty = true;      // do we need to repaint?

    int interval = 100;        // milliseconds between repaints
    int iterations = 3;        // number of layout iterations per repaint

    Color nodeColor = Color.pink;   // default background color for a node
                                    // (node label text is in Foreground color)
    Color edgeColor = Color.black;  // default color of an edge line 
    Color tipColor = Color.yellow;  // background color of a popup tip

    //RenderedNode selectedNode = null;   // currently selected node, or null
    //RenderedEdge selectedEdge = null;   // currently selected edge, or null
        // invariant: selectedNode==null || selectedEdge == null

    Object tipObject = null;       // node or edge currently under mouse, or null
    MultiLineString tip = null;    // tip string displayed for tipObject, or null
    int tipX, tipY, tipWidth, tipHeight;    // bounding box of tip

    GraphLayoutControlPanel controlPanel;

    /**
     * Make a GraphLayout.
     */
    public GraphLayout () {
        graph = new Graph ();
        resetAlgorithm ();
        start ();
    }
    
    /**
     * Erase the graph.
     */
    public synchronized void clear () {
        graph = new Graph ();
        changedGraph ();
    }

    /**
     * Get the graph.
     */
    public synchronized Graph getGraph () {
        return graph;
    }

    /**
     * Set the graph.
     */
    public synchronized void setGraph (Graph graph) {
        this.graph = graph;
        //selectedNode = null;
        //selectedEdge = null;
        tipObject = null;
        tip = null;
        changedGraph ();
    }

    /**
     * Get the graph-drawing algorithm in use.
     */
    public synchronized GDAlgorithm getAlgorithm () {
        return algorithm;
    }

    /**
     * Set the graph-drawing algorithm.
     */
    public synchronized void setAlgorithm (GDAlgorithm algorithm) {
        this.algorithm = algorithm;
        changedGraph ();
    }

    synchronized void resetAlgorithm () {
        algorithm = new AllPairsAlgorithm (springConstant, nodeCharge);
        changedGraph ();
    }

    /**
     * Get the default rest length for new edges.
     */
    public synchronized double getRestLength () {
        return restLength;
    }

    /**
     * Set the default rest length for new edges.
     */
    public synchronized void setRestLength (double restLength) {
        this.restLength = restLength;
        changedGraph ();
    }

    /**
     * Get the spring constant.
     */
    public synchronized double getSpringConstant () {
        return springConstant;
    }

    /**
     * Set the spring constant.
     */
    public synchronized void setSpringConstant (double springConstant) {
        this.springConstant = springConstant;
        resetAlgorithm ();
    }

    /**
     * Get the node charge.
     */
    public synchronized double getNodeCharge () {
        return nodeCharge;
    }

    /**
     * Set the node charge.
     */
    public synchronized void setNodeCharge (double nodeCharge) {
        this.nodeCharge = nodeCharge;
        resetAlgorithm ();
    }

    /**
     * Get the refresh interval (measured in seconds).
     */
    public synchronized int getInterval () {
        return interval;
    }

    /**
     * Set the refresh interval (in seconds).
     */
    public synchronized void setInterval (int interval) {
        this.interval = interval;
    }

    /**
     * Get the layout algorithm iterations per refresh.
     */
    public synchronized int getIterations () {
        return iterations;
    }

    /**
     * Set the layout algorithm iterations per refresh.
     */
    public synchronized void setIterations (int iterations) {
        this.iterations = iterations;
    }

    /**
     * Test whether the graph is laid out automatically.
     */
    public synchronized boolean getAutomaticLayout () {
        return automaticLayout;
    }

    /**
     * Set whether the graph is laid out automatically.
     */
    public synchronized void setAutomaticLayout (boolean f) {
        automaticLayout = f;
        quiescent = !automaticLayout;
        if (controlPanel != null)
            controlPanel.automatic.setState (automaticLayout);
    }

    /**
     * Test whether the graph is quiescent (not changing in the background).
     */
    public synchronized boolean getQuiescent () {
        return quiescent;
    }

    /**
     * Test whether the graph layout thread is running in the background
     */
    public synchronized boolean getRunning () {
        return running;
    }

    /**
     * Get the threshold.
     */
    public synchronized double getThreshold () {
        return threshold;
    }

    /**
     * Set the threshold.
     */
    public synchronized void setThreshold (double threshold) {
        this.threshold = threshold;
        changedGraph ();
    }

    /**
     * Get the node background color.
     */
    public synchronized Color getNodeColor () {
        return nodeColor;
    }

    /**
     * Set the node background color.
     */
    public synchronized void setNodeColor (Color nodeColor) {
        this.nodeColor = nodeColor;
    }

    /**
     * Get the edge color.
     */
    public synchronized Color getEdgeColor () {
        return edgeColor;
    }

    /**
     * Set the edge color.
     */
    public synchronized void setEdgeColor (Color edgeColor) {
        this.edgeColor = edgeColor;
    }

    /**
     * Get the popup tip color.
     */
    public synchronized Color getTipColor () {
        return tipColor;
    }

    /**
     * Set the popup tip color.
     */
    public synchronized void setTipColor (Color tipColor) {
        this.tipColor = tipColor;
    }

    /**
     * Get node currently under the mouse pointer, or null if no node is under the mouse.
     */
    public synchronized RenderedNode getSelectedNode () {
        return tipObject instanceof RenderedNode 
            ? (RenderedNode)tipObject
            : null;
    }

    /**
     * Get edge currently under the mouse pointer, or null if no edge is under the mouse.
     */
    public synchronized RenderedEdge getSelectedEdge () {
        return tipObject instanceof RenderedEdge 
            ? (RenderedEdge)tipObject
            : null;
    }

    /**
     * Add a node.
     */
    public synchronized void addNode (RenderedNode node) {
        graph.addNode (node);
        graph.placeNode (node, node.x, node.y);
        changedGraph ();
    }

    /**
     * Add an edge.
     */
    public synchronized void addEdge (RenderedEdge edge) {
        if (edge.restLength == 0)
            edge.restLength = restLength;
        graph.addEdge (edge);
        changedGraph ();
    }

    /**
     * Remove a node.
     */
    public synchronized void removeNode (RenderedNode node) {
        graph.removeNode (node);
        changedGraph ();
    }

    /**
     * Remove an edge.
     */
    public synchronized void removeEdge (RenderedEdge edge) {
        graph.removeEdge (edge);
        changedGraph ();
    }

    /**
     * Handle a loaded image.
     */
    public synchronized boolean imageUpdate(Image  img,
                                  int infoflags,
                                  int x,
                                  int y,
                                  int width,
                                  int height) {
        if ((infoflags & (ImageObserver.WIDTH | ImageObserver.HEIGHT)) != 0) {
            for (int i=0; i<graph.sizeNodes; ++i) {
                RenderedNode n = (RenderedNode)graph.nodes[i];
                if (n.icon == img) {
                    n.width = width;
                    n.height = height;
                    changedGraph ();
                }
            }
        }
        return super.imageUpdate (img, infoflags, x, y, width, height);
    }

    /*
     * Background thread
     *
     */

    Thread iterator;

    /**
     * Start automatic graph layout (in the background).
     */
    public synchronized void start () {
        if (!running) {
            running = true;            
            iterator = new Thread (this, "GraphListener");
            iterator.setDaemon (true);
            iterator.setPriority (Thread.MIN_PRIORITY);
            iterator.start ();
        }
    }

    /**
     * Stop automatic graph layout.
     */
    public synchronized void stop () {        
        if (running) {
            running = false;
            notify ();
            iterator = null;
        }
    }

    /**
     * The body of the background thread.  Clients should not call this
     * method.
     */
    final static int MULTIPLIER = 2;
    public synchronized void run () {
        quiescent = false;
        while (running) {
            long start = System.currentTimeMillis ();

            if (automaticLayout && !quiescent) {
                for (int i=0; i < iterations; ++i) {
                    double improvement = algorithm.improveGraph (graph);
                    dirty = true;
                    if (improvement <= threshold * graph.sizeNodes) {
                        quiescent = true;
                        break;
                    }
                }
            }

            if (dirty)
                super.repaint ();

            /*int r = (int) (System.currentTimeMillis() - start);
            int w = Math.max (interval, r * MULTIPLIER);
            System.out.println ("ran " + r + " msec, now waiting " + w + " msec");
            */

            try {
                wait (interval);
            } catch (InterruptedException e) {
            }
        }
        quiescent = true;
    }

    /**
     * Notify background thread that the graph has changed.
     */
    public synchronized void changedGraph () {
        if (automaticLayout)
            quiescent = false;
        repaint ();
    }

    /**
     * Notify background thread that the view has changed.
     */
    public synchronized void repaint () {
        if (!running)
            super.repaint ();
        else
            dirty = true;
    }

    /**
     * Show control panel for changing graph layout parameters.
     */
    public void showControlPanel () {
        if (controlPanel == null)
            controlPanel = new GraphLayoutControlPanel (this);
        controlPanel.show ();
    }

    protected void finalize () throws Throwable {
        super.finalize ();
        if (controlPanel != null) {
            controlPanel.dispose();
            controlPanel = null;
        }
    }

    /*
     * Scale coordinates from graph to screen.
     */
    double originX = 0.0, originY = 0.0;
    double scaleX = 1.0, scaleY = 1.0;

    private void scaleGraph () {
        Dimension d = size ();
        double halfScreenWidth = d.width/2.0;
        double halfScreenHeight = d.height/2.0;
        
        double sX = 1.0, sY = 1.0;
        for (int i=0; i < graph.sizeNodes; ++i) {
            RenderedNode n = (RenderedNode)graph.nodes[i];
            sX = Math.min(sX, (halfScreenWidth - n.width/2.0)/(Math.abs(n.x)+1));
            sY = Math.min(sY, (halfScreenHeight - n.height/2.0)/(Math.abs(n.y)+1));
        }
        
        double oX = halfScreenWidth;
        double oY = halfScreenHeight;
        
        for (int i=0; i < graph.sizeNodes; ++i) {
            RenderedNode n = (RenderedNode)graph.nodes[i];
            n.screenX = (int)(n.x*sX + oX);
            n.screenY = (int)(n.y*sY + oY);
        }

        // save the translation for use in placeNodeOnScreen
        originX = oX;
        originY = oY;
        scaleX = sX;
        scaleY = sY;
    }

    public synchronized void placeNodeOnScreen (RenderedNode n, int x, int y) {
        graph.placeNode (n, (x - originX)/scaleX, (y - originY)/scaleY);
        n.screenX = x;
        n.screenY = y;
    }