graph.java

用applet实现很多应用小程序

     * Get an iterator over all out-linking neighbor nodes for the given Node.
     * @param n a Node in the graph
     * @return an iterator over all Nodes pointed to by the input source node
     */
    public Iterator outNeighbors(Node n) {
        return new NeighborIterator(n, outEdges(n));
    }
    
    /**
     * Get an iterator over all edges in the graph.
     * @return an iterator over Edge instances
     */
    public Iterator edges() {
        return m_edgeTuples.iterator(edgeRows());
    }
    
    /**
     * Get an iterator over all Edges connected to the given Node in the graph.
     * @param node a Node in the graph
     * @return an iterator over all Edges connected to the input node
     */
    public Iterator edges(Node node) {
        nodeCheck(node, true);
        return m_edgeTuples.iterator(edgeRows(node.getRow(), UNDIRECTED)); 
    }
    
    /**
     * Get an iterator over all in-linking edges to the given Node.
     * @param node a Node in the graph
     * @return an iterator over all in-linking edges to the input target node
     */
    public Iterator inEdges(Node node) {
        nodeCheck(node, true);
        return m_edgeTuples.iterator(inEdgeRows(node.getRow()));
    }

    /**
     * Get an iterator over all out-linking edges from the given Node.
     * @param node a Node in the graph
     * @return an iterator over all out-linking edges from the input source
     * node
     */
    public Iterator outEdges(Node node) {
        nodeCheck(node, true);
        return m_edgeTuples.iterator(outEdgeRows(node.getRow()));
    }
    
    // ------------------------------------------------------------------------
    // TupleSet Interface

    /**
     * Clear this graph, removing all nodes and edges.
     * @see prefuse.data.tuple.TupleSet#clear()
     */
    public void clear() {
        m_nodeTuples.invalidateAll();
        m_edgeTuples.invalidateAll();
        super.clear();
        m_links.clear();
    }
    
    /**
     * If the given tuple is a Node or Edge in this graph, remove it.
     * @see prefuse.data.tuple.TupleSet#removeTuple(prefuse.data.Tuple)
     */
    public boolean removeTuple(Tuple t) {
        // TODO: check underlying table tuples as well?
        if ( t instanceof Node ) {
            return removeNode((Node)t);
        } else if ( t instanceof Edge ) {
            return removeEdge((Edge)t);
        } else {
            throw new IllegalArgumentException(
                    "Input tuple must be part of this graph");
        }
    }

    /**
     * Get a filtered iterator over the edges and nodes of this graph.
     * @see prefuse.data.tuple.TupleSet#tuples(prefuse.data.expression.Predicate)
     */
    public Iterator tuples(Predicate filter) {
        if ( filter == null ) {
            return tuples();
        } else {
            return new CompositeIterator(
                    m_edgeTuples.iterator(getEdgeTable().rows(filter)),
                    m_nodeTuples.iterator(getNodeTable().rows(filter)));
        }
    }
    
    /**
     * Get an iterator over all the edges and nodes of this graph. The iterator
     * will return all edges first, then all nodes.
     * @see prefuse.data.tuple.TupleSet#tuples()
     */
    public Iterator tuples() {
        return new CompositeIterator(edges(), nodes());
    }    
    
    // ------------------------------------------------------------------------
    // Spanning Tree Methods
    
    /**
     * Return the current spanning tree over this graph. If no spanning tree
     * has been constructed, a SpanningTree rooted at the first valid node
     * found in the node table will be generated.
     * 
     * Spanning trees are generated using an unweighted breadth first search
     * over the graph structure.
     * 
     * @return a spanning tree over this graph
     * @see #getSpanningTree(Node)
     * @see #clearSpanningTree()
     */
    public Tree getSpanningTree() {
        if ( m_spanning == null )
            return getSpanningTree((Node)nodes().next());
        else
            return m_spanning;
    }

    /**
     * Returns a spanning tree rooted at the specified node. If the current
     * spanning tree is alrady rooted at the given node, it is simply
     * returned. Otherwise, the tree is reconstructed at the new root and
     * made the current spanning tree for this Graph instance.
     * 
     * Spanning trees are generated using an unweighted breadth first search
     * over the graph structure.
     * 
     * @param root the node at which to root the spanning tree.
     * @return a spanning tree over this graph, rooted at the given root
     * @see #getSpanningTree()
     * @see #clearSpanningTree()
     */
    public Tree getSpanningTree(Node root) {
        nodeCheck(root, true);
        if ( m_spanning == null ) {
            m_spanning = new SpanningTree(this, root);
        } else if ( m_spanning.getRoot() != root ) {
            m_spanning.buildSpanningTree(root);
        }
        return m_spanning;
    }
    
    /**
     * Clear the internally stored spanning tree. Any new calls to a
     * getSpanningTree() method will generate a new spanning tree 
     * instance as needed.
     * 
     * This method is primarily useful for subclasses.
     * For example, calling this method on a Tree instance will revert the
     * state to the original rooted tree such that a sbusequent call to
     * getSpanningTree() will return the backing Tree itself.
     * @see #getSpanningTree()
     * @see #getSpanningTree(Node)
     * @see Tree#getSpanningTree(Node)
     */
    public void clearSpanningTree() {
        m_spanning = null;
    }
    
    // ------------------------------------------------------------------------
    // Graph Listeners
    
    /**
     * Add a listener to be notified of changes to the graph.
     * @param listnr the listener to add
     */
    public void addGraphModelListener(GraphListener listnr) {
        if ( !m_listeners.contains(listnr) )
            m_listeners.add(listnr);
    }

    /**
     * Remove a listener from this graph.
     * @param listnr the listener to remove
     */
    public void removeGraphModelListener(GraphListener listnr) {
        m_listeners.remove(listnr);
    }
    
    /**
     * Removes all listeners on this graph
     */
    public void removeAllGraphModelListeners() {
    	m_listeners.clear();
    }
    
    /**
     * Fire a graph change event
     * @param t the backing table where the change occurred (either a
     * node table or an edge table)
     * @param first the first modified table row
     * @param last the last (inclusive) modified table row
     * @param col the number of the column modified, or
     * {@link prefuse.data.event.EventConstants#ALL_COLUMNS} for operations
     * affecting all columns
     * @param type the type of modification, one of
     * {@link prefuse.data.event.EventConstants#INSERT},
     * {@link prefuse.data.event.EventConstants#DELETE}, or
     * {@link prefuse.data.event.EventConstants#UPDATE}.
     */
    protected void fireGraphEvent(Table t, 
            int first, int last, int col, int type)
    {
        String table = (t==getNodeTable() ? NODES : EDGES);
        
        if ( type != EventConstants.UPDATE ) {
            // fire event to all tuple set listeners
            fireTupleEvent(t, first, last, type);
        }
        
        if ( !m_listeners.isEmpty() ) {            
            // fire event to all listeners
            Object[] lstnrs = m_listeners.getArray();
            for ( int i=0; i<lstnrs.length; ++i ) {
                ((GraphListener)lstnrs[i]).graphChanged(
                        this, table, first, last, col, type);
            }
        }
    }

    // ------------------------------------------------------------------------
    // Table and Column Listener
    
    /**
     * Listener class for tracking updates from node and edge tables,
     * and their columns that determine the graph linkage structure.
     */
    protected class Listener implements TableListener, ColumnListener {

        private Table m_edges;
        private Column m_scol, m_tcol;
        private int m_sidx, m_tidx;
        
        public void setEdgeTable(Table edges) {
            // remove any previous listeners
            if ( m_scol != null ) m_scol.removeColumnListener(this);
            if ( m_tcol != null ) m_tcol.removeColumnListener(this);
            m_scol = m_tcol = null;
            m_sidx = m_tidx = -1;
            
            m_edges = edges;
            
            // register listeners
            if ( m_edges != null ) {
                m_sidx = edges.getColumnNumber(m_skey);
                m_tidx = edges.getColumnNumber(m_tkey);
                m_scol = edges.getColumn(m_sidx);
                m_tcol = edges.getColumn(m_tidx);
                m_scol.addColumnListener(this);
                m_tcol.addColumnListener(this);
            }
        }
        
        public void tableChanged(Table t, int start, int end, int col, int type) {
            if ( !containsSet(t) )
                throw new IllegalStateException(
                     "Graph shouldn't be listening to an unrelated table");
            
            if ( type != EventConstants.UPDATE ) {
                if ( t == getNodeTable() ) {
                    // update the linkage structure table
                    if ( col == EventConstants.ALL_COLUMNS ) {
                        boolean added = type==EventConstants.INSERT;
                        for ( int r=start; r<=end; ++r )
                            updateNodeData(r, added);
                    }
                } else {
                    // update the linkage structure table
                    if ( col == EventConstants.ALL_COLUMNS ) {
                        boolean added = type==EventConstants.INSERT;
                        for ( int r=start; r<=end; ++r )
                            updateDegrees(start, added?1:-1);
                    }
                }
                // clear the spanning tree reference
                m_spanning = null;
            }
            fireGraphEvent(t, start, end, col, type);
        }

        public void columnChanged(Column src, int idx, int prev) {
            columnChanged(src, idx, (long)prev);
        }

        public void columnChanged(Column src, int idx, long prev) {
            if ( src==m_scol || src==m_tcol ) {
                boolean isSrc = src==m_scol;
                int e = m_edges.getTableRow(idx, isSrc?m_sidx:m_tidx);
                if ( e == -1 )
                    return; // edge not in this graph
                int s = getSourceNode(e);
                int t = getTargetNode(e);
                int p = getNodeIndex(prev);
                if ( p > -1 && ((isSrc && t > -1) || (!isSrc && s > -1)) )
                    updateDegrees(e, isSrc?p:s, isSrc?t:p, -1);
                if ( s > -1 && t > -1 )
                    updateDegrees(e, s, t, 1);
            } else {
                throw new IllegalStateException();
            }
        }
        
        public void columnChanged(Column src, int type, int start, int end) {
            // should never be called
            throw new IllegalStateException();
        }
        public void columnChanged(Column src, int idx, float prev) {
            // should never be called
            throw new IllegalStateException();
        }
        public void columnChanged(Column src, int idx, double prev) {
            // should never be called
            throw new IllegalStateException();
        }
        public void columnChanged(Column src, int idx, boolean prev) {
            // should never be called
            throw new IllegalStateException();
        }
        public void columnChanged(Column src, int idx, Object prev) {
            // should never be called
            throw new IllegalStateException();
        }   
    } // end of inner class Listener
    
    
    // ------------------------------------------------------------------------
    // Graph Linkage Schema
    
    /** In-degree data field for the links table */
    protected static final String INDEGREE  = "_indegree";
    /** Out-degree data field for the links table */
    protected static final String OUTDEGREE = "_outdegree";
    /** In-links adjacency list data field for the links table */
    protected static final String INLINKS   = "_inlinks";
    /** Out-links adjacency list data field for the links table */
    protected static final String OUTLINKS  = "_outlinks";
    /** Schema used for the internal graph linkage table */
    protected static final Schema LINKS_SCHEMA = new Schema();
    static {
        Integer defaultValue = new Integer(0);
        LINKS_SCHEMA.addColumn(INDEGREE,  int.class, defaultValue);
        LINKS_SCHEMA.addColumn(OUTDEGREE, int.class, defaultValue);
        LINKS_SCHEMA.addColumn(INLINKS,   int[].class);
        LINKS_SCHEMA.addColumn(OUTLINKS,  int[].class);
        LINKS_SCHEMA.lockSchema();
    }
    
} // end of class Graph