graph.java

用applet实现很多应用小程序

package prefuse.data;

import java.util.Iterator;

import prefuse.data.column.Column;
import prefuse.data.event.ColumnListener;
import prefuse.data.event.EventConstants;
import prefuse.data.event.GraphListener;
import prefuse.data.event.TableListener;
import prefuse.data.expression.Predicate;
import prefuse.data.tuple.CompositeTupleSet;
import prefuse.data.tuple.TableEdge;
import prefuse.data.tuple.TableNode;
import prefuse.data.tuple.TupleManager;
import prefuse.data.tuple.TupleSet;
import prefuse.data.util.Index;
import prefuse.data.util.NeighborIterator;
import prefuse.util.PrefuseConfig;
import prefuse.util.TypeLib;
import prefuse.util.collections.CompositeIntIterator;
import prefuse.util.collections.CompositeIterator;
import prefuse.util.collections.CopyOnWriteArrayList;
import prefuse.util.collections.IntArrayIterator;
import prefuse.util.collections.IntIterator;

/**
 * <p>A Graph models a network of nodes connected by a collection of edges.
 * Both nodes and edges can have any number of associated data fields.
 * Additionally, edges are either directed or undirected, indicating a
 * possible directionality of the connection. Each edge has both a source
 * node and a target node, for a directed edge this indicates the
 * directionality, for an undirected edge this is just an artifact
 * of the order in which the nodes were specified when added to the graph.
 * </p>
 * 
 * <p>Both nodes and edges are represented by backing data {@link Table}
 * instances storing the data attributes. For edges, this table must
 * also contain a source node field and a target node field. The default
 * column name for these fields are {@link #DEFAULT_SOURCE_KEY} and
 * {@link #DEFAULT_TARGET_KEY}, but these can be configured by the graph
 * constructor. These columns should be integer valued, and contain
 * either the row number for a corresponding node in the node table,
 * or another unique identifier for a node. In this second case, the
 * unique identifier must be included as a data field in the node
 * table. This name of this column can be configured using the appropriate
 * graph constructor. The default column name for this field is
 * {@link #DEFAULT_NODE_KEY}, which by default evaluates to null,
 * indicating that no special node key should be used, just the direct
 * node table row numbers. Though the source, target, and node key
 * values completely specify the graph linkage structure, to make
 * graph operations more efficient an additional table is maintained
 * internally by the Graph class, storing node indegree and outdegree
 * counts and adjacency lists for the inlinks and outlinks for all nodes.</p>
 * 
 * <p>Graph nodes and edges can be accessed by application code by either
 * using the row numbers of the node and edge tables, which provide unique ids
 * for each, or using the {@link prefuse.data.Node} and
 * {@link prefuse.data.Edge} classes --
 * {@link prefuse.data.Tuple} instances that provide
 * object-oriented access to both node or edge data values and the
 * backing graph structure. Node and Edge tuples are maintained by
 * special TupleManager instances contained within this Graph. By default, they
 * are not accessible from the backing node or edge tables directly. The reason
 * for this is that these tables might be used in multiple graphs
 * simultaneously. For example, a node data table could be used in a number of
 * different graphs, exploring different possible linkages between those node.
 * In short, use this Graph instance to request iterators over Node or
 * Edge tuples, not the backing data tables.</p>
 * 
 * <p>All Graph instances also support an internally generated
 * spanning tree, provided by the {@link #getSpanningTree()} or
 * {@link #getSpanningTree(Node)} methods. This is particularly
 * useful in visualization contexts that use an underlying tree structure
 * to compute a graph layout.</p>
 * 
 * @author <a href="http://jheer.org">jeffrey heer</a>
 */
public class Graph extends CompositeTupleSet {
    
    /** Indicates incoming edges (inlinks) */
    public static final int INEDGES    = 0;
    /** Indicates outgoing edges (outlinks) */
    public static final int OUTEDGES   = 1;
    /** Indicates all edges, regardless of direction */
    public static final int UNDIRECTED = 2;
    
    /** Default data field used to uniquely identify a node */
    public static final String DEFAULT_NODE_KEY 
        = PrefuseConfig.get("data.graph.nodeKey");
    /** Default data field used to denote the source node in an edge table */
    public static final String DEFAULT_SOURCE_KEY 
        = PrefuseConfig.get("data.graph.sourceKey");
    /** Default data field used to denote the target node in an edge table */
    public static final String DEFAULT_TARGET_KEY 
        = PrefuseConfig.get("data.graph.targetKey"); 
    /** Data group name to identify the nodes of this graph */
    public static final String NODES 
        = PrefuseConfig.get("data.graph.nodeGroup");
    /** Data group name to identify the edges of this graph */
    public static final String EDGES 
        = PrefuseConfig.get("data.graph.edgeGroup");
    
    // -- auxiliary data structures -----
    
    /** Table containing the adjacency lists for the graph */
    protected Table m_links;
    /** TupleManager for managing Node tuple instances */
    protected TupleManager m_nodeTuples;
    /** TupleManager for managing Edge tuple instances */
    protected TupleManager m_edgeTuples;
    
    /** Indicates if this graph is directed or undirected */
    protected boolean      m_directed = false;
    /** The spanning tree over this graph */
    protected SpanningTree m_spanning = null;
    
    /** The node key field (for the Node table) */
    protected String m_nkey;
    /** The source node key field (for the Edge table) */
    protected String m_skey;
    /** The target node key field (for the Edge table) */
    protected String m_tkey;
    /** Reference to an index over the node key field */
    protected Index m_nidx;
    /** Indicates if the key values are of type long */
    protected boolean m_longKey = false;
    /** Update listener */
    private Listener m_listener;
    /** Listener list */
    private CopyOnWriteArrayList m_listeners = new CopyOnWriteArrayList();
    
    // ------------------------------------------------------------------------
    // Constructors
    
    /**
     * Creates a new, empty undirected Graph.
     */
    public Graph() {
        this(false);
    }
    
    /**
     * Creates a new, empty Graph.
     * @param directed true for directed edges, false for undirected
     */
    public Graph(boolean directed) {
        this(new Table(), directed);
    }

    /**
     * Create a new Graph using the provided table of node data and
     * an empty set of edges.
     * @param nodes the backing table to use for node data.
     * Node instances of this graph will get their data from this table.
     * @param directed true for directed edges, false for undirected
     */
    public Graph(Table nodes, boolean directed) {
        this(nodes, directed, DEFAULT_NODE_KEY,
                DEFAULT_SOURCE_KEY, DEFAULT_TARGET_KEY);
    }
 
    /**
     * Create a new Graph using the provided table of node data and
     * an empty set of edges.
     * @param nodes the backing table to use for node data.
     * Node instances of this graph will get their data from this table.
     * @param directed true for directed edges, false for undirected
     * @param nodeKey data field used to uniquely identify a node. If this
     * field is null, the node table row numbers will be used
     * @param sourceKey data field used to denote the source node in an edge
     * table
     * @param targetKey data field used to denote the target node in an edge
     * table
     */
    public Graph(Table nodes, boolean directed, String nodeKey,
            String sourceKey, String targetKey) {
        Table edges = new Table();
        edges.addColumn(sourceKey, int.class, new Integer(-1));
        edges.addColumn(targetKey, int.class, new Integer(-1));
        init(nodes, edges, directed, nodeKey, sourceKey, targetKey);
    }
    
    /**
     * Create a new Graph, using node table row numbers to uniquely
     * identify nodes in the edge table's source and target fields.
     * @param nodes the backing table to use for node data.
     * Node instances of this graph will get their data from this table.
     * @param edges the backing table to use for edge data.
     * Edge instances of this graph will get their data from this table.
     * @param directed true for directed edges, false for undirected
     */
    public Graph(Table nodes, Table edges, boolean directed) {
        this(nodes, edges, directed,
            DEFAULT_NODE_KEY, DEFAULT_SOURCE_KEY, DEFAULT_TARGET_KEY);
    }
    
    /**
     * Create a new Graph, using node table row numbers to uniquely
     * identify nodes in the edge table's source and target fields.
     * @param nodes the backing table to use for node data.
     * Node instances of this graph will get their data from this table.
     * @param edges the backing table to use for edge data.
     * Edge instances of this graph will get their data from this table.
     * @param directed true for directed edges, false for undirected
     * @param sourceKey data field used to denote the source node in an edge
     * table
     * @param targetKey data field used to denote the target node in an edge
     * table
     */
    public Graph(Table nodes, Table edges, boolean directed,
            String sourceKey, String targetKey)
    {
        init(nodes, edges, directed, DEFAULT_NODE_KEY, sourceKey, targetKey);
    }
    
    /**
     * Create a new Graph.
     * @param nodes the backing table to use for node data.
     * Node instances of this graph will get their data from this table.
     * @param edges the backing table to use for edge data.
     * Edge instances of this graph will get their data from this table.
     * @param directed true for directed edges, false for undirected
     * @param nodeKey data field used to uniquely identify a node. If this
     * field is null, the node table row numbers will be used
     * @param sourceKey data field used to denote the source node in an edge
     * table
     * @param targetKey data field used to denote the target node in an edge
     * table
     */
    public Graph(Table nodes, Table edges, boolean directed,
            String nodeKey, String sourceKey, String targetKey)
    {
        init(nodes, edges, directed, nodeKey, sourceKey, targetKey);
    }
    
    // ------------------------------------------------------------------------
    // Initialization
    
    /**
     * Initialize this Graph instance.
     * @param nodes the node table
     * @param edges the edge table
     * @param directed the edge directionality
     * @param nodeKey data field used to uniquely identify a node
     * @param sourceKey data field used to denote the source node in an edge
     * table
     * @param targetKey data field used to denote the target node in an edge
     * table
     */
    protected void init(Table nodes, Table edges, boolean directed, 
            String nodeKey, String sourceKey, String targetKey)
    {
        // sanity check
        if ( (nodeKey!=null && 
              !TypeLib.isIntegerType(nodes.getColumnType(nodeKey)))  ||
              !TypeLib.isIntegerType(edges.getColumnType(sourceKey)) ||
              !TypeLib.isIntegerType(edges.getColumnType(targetKey)) )
        {
            throw new IllegalArgumentException(
                "Incompatible column types for graph keys");
        }
        
        removeAllSets();
        super.addSet(EDGES, edges);
        super.addSet(NODES, nodes);
        
        m_directed = directed;
        
        // INVARIANT: these three should all reference the same type
        // currently limited to int
        m_nkey = nodeKey;
        m_skey = sourceKey;
        m_tkey = targetKey;
        
        // set up indices
        if ( nodeKey != null ) {
            if ( nodes.getColumnType(nodeKey) == long.class )
                m_longKey = true;
            nodes.index(nodeKey);
            m_nidx = nodes.getIndex(nodeKey);
        }
        
        // set up tuple manager
        if ( m_nodeTuples == null )
            m_nodeTuples = new TupleManager(nodes, this, TableNode.class);
        m_edgeTuples = new TupleManager(edges, this, TableEdge.class);
        
        // set up node attribute optimization
        initLinkTable();
        
        // set up listening
        if ( m_listener == null )
            m_listener = new Listener();
        nodes.addTableListener(m_listener);
        edges.addTableListener(m_listener);
        m_listener.setEdgeTable(edges);
    }
    
    /**
     * Set the tuple managers used to manage the Node and Edge tuples of this
     * Graph.
     * @param ntm the TupleManager to use for nodes
     * @param etm the TupleManager to use for edges
     */
    public void setTupleManagers(TupleManager ntm, TupleManager etm) {
        if ( !Node.class.isAssignableFrom(ntm.getTupleType()) )
            throw new IllegalArgumentException("The provided node " +
                "TupleManager must generate tuples that implement " +
                "the Node interface.");
        if ( !Edge.class.isAssignableFrom(etm.getTupleType()) )
            throw new IllegalArgumentException("The provided edge " +
                "TupleManager must generate tuples that implement " +
                "the Edge interface.");
        m_nodeTuples = ntm;
        m_edgeTuples = etm;
    }
    
    /**
     * Dispose of this graph. Unregisters this graph as a listener to its
     * included tables.
     */
    public void dispose() {
        getNodeTable().removeTableListener(m_listener);
        getEdgeTable().removeTableListener(m_listener);
    }
    
    /**
     * Updates this graph to use a different edge structure for the same nodes.
     * All other settings will remain the same (e.g., directionality, keys)
     * @param edges the new edge table.
     */
    public void setEdgeTable(Table edges) {
        Table oldEdges = getEdgeTable();
        oldEdges.removeTableListener(m_listener);
        m_edgeTuples.invalidateAll();
        m_links.clear();
        
        init(getNodeTable(), edges, m_directed, m_nkey, m_skey, m_tkey);
    }
    
    // ------------------------------------------------------------------------
    // Data Access Optimization
    
    /**
     * Initialize the link table, which holds adjacency lists for this graph.
     */
    protected void initLinkTable() {
        // set up cache of node data
        m_links = createLinkTable();
                
        IntIterator edges = getEdgeTable().rows();
        while ( edges.hasNext() ) {
            updateDegrees(edges.nextInt(), 1);
        }