graph.java

用applet实现很多应用小程序

    }
    
    /**
     * Instantiate and return the link table.
     * @return the created link table
     */
    protected Table createLinkTable() {
        return LINKS_SCHEMA.instantiate(getNodeTable().getMaximumRow()+1);
    }
    
    /**
     * Internal method for updating the linkage of this graph.
     * @param e the edge id for the updated link
     * @param incr the increment value, 1 for an added link,
     * -1 for a removed link
     */
    protected void updateDegrees(int e, int incr) {
        if ( !getEdgeTable().isValidRow(e) ) return;
        int s = getSourceNode(e);
        int t = getTargetNode(e);
        if ( s < 0 || t < 0 ) return;
        updateDegrees(e, s, t, incr);
        if ( incr < 0 ) {
            m_edgeTuples.invalidate(e);
        }
    }
    
    /**
     * Internal method for updating the linkage of this graph.
     * @param e the edge id for the updated link
     * @param s the source node id for the updated link
     * @param t the target node id for the updated link
     * @param incr the increment value, 1 for an added link,
     * -1 for a removed link
     */
    protected void updateDegrees(int e, int s, int t, int incr) {
        int od = m_links.getInt(s, OUTDEGREE);
        int id = m_links.getInt(t, INDEGREE);
        // update adjacency lists
        if ( incr > 0 ) {
            // add links
            addLink(OUTLINKS, od, s, e);
            addLink(INLINKS, id, t, e);
        } else if ( incr < 0 ) {
            // remove links
            remLink(OUTLINKS, od, s, e);
            remLink(INLINKS, id, t, e);
        }
        // update degree counts
        m_links.setInt(s, OUTDEGREE, od+incr);
        m_links.setInt(t, INDEGREE, id+incr);
        // link structure changed, invalidate spanning tree
        m_spanning = null;
    }
    
    /**
     * Internal method for adding a link to an adjacency list
     * @param field which adjacency list (inlinks or outlinks) to use
     * @param len the length of the adjacency list
     * @param n the node id of the adjacency list to use
     * @param e the edge to add to the list
     */
    protected void addLink(String field, int len, int n, int e) {
        int[] array = (int[])m_links.get(n, field);
        if ( array == null ) {
            array = new int[] {e};
            m_links.set(n, field, array);
            return;
        } else if ( len == array.length ) {
            int[] narray = new int[Math.max(3*array.length/2, len+1)];
            System.arraycopy(array, 0, narray, 0, array.length);
            array = narray;
            m_links.set(n, field, array);
        }
        array[len] = e;
    }
    
    /**
     * Internal method for removing a link from an adjacency list
     * @param field which adjacency list (inlinks or outlinks) to use
     * @param len the length of the adjacency list
     * @param n the node id of the adjacency list to use
     * @param e the edge to remove from the list
     * @return true if the link was removed successfully, false otherwise
     */
    protected boolean remLink(String field, int len, int n, int e) {
        int[] array = (int[])m_links.get(n, field);
        for ( int i=0; i<len; ++i ) {
            if ( array[i] == e ) {
                System.arraycopy(array, i+1, array, i, len-i-1);
                return true;
            }
        }
        return false;
    }
    
    /**
     * Update the link table to accomodate an inserted or deleted node
     * @param r the node id, also the row number into the link table
     * @param added indicates if a node was added or removed
     */
    protected void updateNodeData(int r, boolean added) {
        if ( added ) {
            m_links.addRow();
        } else {
            m_nodeTuples.invalidate(r);
            m_links.removeRow(r);
        }
    }
    
    // ------------------------------------------------------------------------
    // Key Transforms
    
    /**
     * Get the data field used to uniquely identify a node
     * @return the data field used to uniquely identify a node
     */
    public String getNodeKeyField() {
        return m_nkey;
    }
    
    /**
     * Get the data field used to denote the source node in an edge table.
     * @return the data field used to denote the source node in an edge table.
     */
    public String getEdgeSourceField() {
        return m_skey;
    }
    
    /**
     * Get the data field used to denote the target node in an edge table.
     * @return the data field used to denote the target node in an edge table.
     */
    public String getEdgeTargetField() {
        return m_tkey;
    }
    
    /**
     * Given a node id (a row number in the node table), get the value of
     * the node key field.
     * @param node the node id
     * @return the value of the node key field for the given node
     */
    public long getKey(int node) {
        return m_nkey == null ? node : getNodeTable().getLong(node, m_nkey);
    }
    
    /**
     * Given a value of the node key field, get the node id (the row number
     * in the node table).
     * @param key a node key field value
     * @return the node id (the row number in the node table)
     */
    public int getNodeIndex(long key) {
        if ( m_nidx == null ) {
            return (int)key;
        } else {
            int idx = m_longKey ? m_nidx.get(key) : m_nidx.get((int)key);
            return idx<0 ? -1 : idx;
        }
    }
    
    // ------------------------------------------------------------------------
    // Graph Mutators
    
    /**
     * Add row to the node table, thereby adding a node to the graph.
     * @return  the node id (node table row number) of the added node
     */
    public int addNodeRow() {
        return getNodeTable().addRow();
    }
    
    /**
     * Add a new node to the graph.
     * @return the new Node instance
     */
    public Node addNode() {
        int nrow = addNodeRow();
        return (Node)m_nodeTuples.getTuple(nrow);
    }
    
    /**
     * Add an edge to the graph. Both multiple edges between two nodes
     * and edges from a node to itself are allowed.
     * @param s the source node id
     * @param t the target node id
     * @return the edge id (edge table row number) of the added edge
     */
    public int addEdge(int s, int t) {
        // get keys for the nodes
        long key1 = getKey(s);
        long key2 = getKey(t);
        
        // add edge row, set source/target fields
        Table edges = getEdgeTable();
        int r = edges.addRow();
        if ( m_longKey ) {
            edges.setLong(r, m_skey, key1);
            edges.setLong(r, m_tkey, key2);
        } else {
            edges.setInt(r, m_skey, (int)key1);
            edges.setInt(r, m_tkey, (int)key2);
        }
        return r;
    }
    
    /**
     * Add an edge to the graph.
     * @param s the source Node
     * @param t the target Node
     * @return the new Edge instance
     */
    public Edge addEdge(Node s, Node t) {
        nodeCheck(s, true);
        nodeCheck(t, true);
        int e = addEdge(s.getRow(), t.getRow());
        return getEdge(e);
    }
    
    /**
     * Remove a node from the graph, also removing all incident edges.
     * @param node the node id (node table row number) of the node to remove
     * @return true if the node was successfully removed, false if the
     * node id was not found or was not valid
     */
    public boolean removeNode(int node) {
        Table nodeTable = getNodeTable();
        if ( nodeTable.isValidRow(node) ) {
            int id = getInDegree(node);
            if ( id > 0 ) {
                int[] links = (int[])m_links.get(node, INLINKS);
                for ( int i=id; --i>=0; )
                    removeEdge(links[i]);
            }
            int od = getOutDegree(node);
            if ( od > 0 ) {
                int[] links = (int[])m_links.get(node, OUTLINKS);
                for ( int i=od; --i>=0; )
                    removeEdge(links[i]);
            }
        }
        return nodeTable.removeRow(node);
    }
    
    /**
     * Remove a node from the graph, also removing all incident edges.
     * @param n the Node to remove from the graph
     * @return true if the node was successfully removed, false if the
     * node was not found in this graph
     */
    public boolean removeNode(Node n) {
        nodeCheck(n, true);
        return removeNode(n.getRow());
    }
    
    /**
     * Remove an edge from the graph.
     * @param edge the edge id (edge table row number) of the edge to remove
     * @return true if the edge was successfully removed, false if the
     * edge was not found or was not valid
     */
    public boolean removeEdge(int edge) {
        return getEdgeTable().removeRow(edge);
    }
    
    /**
     * Remove an edge from the graph.
     * @param e the Edge to remove from the graph
     * @return true if the edge was successfully removed, false if the
     * edge was not found in this graph
     */
    public boolean removeEdge(Edge e) {
        edgeCheck(e, true);
        return removeEdge(e.getRow());
    }
    
    /**
     * Internal method for clearing the edge table, removing all edges.
     */
    protected void clearEdges() {
        getEdgeTable().clear();
    }
    
    // ------------------------------------------------------------------------
    // Node Accessor Methods
    
    /**
     * Internal method for checking the validity of a node.
     * @param n the Node to check for validity
     * @param throwException true if this method should throw an Exception
     * when an invalid node is encountered
     * @return true is the node is valid, false if invalid
     */
    protected boolean nodeCheck(Node n, boolean throwException) {
        if ( !n.isValid() ) {
            if ( throwException ) {
                throw new IllegalArgumentException(
                    "Node must be valid.");
            }
            return false;
        }
        Graph ng = n.getGraph();
        if ( ng != this && ng.m_spanning != this ) {
            if ( throwException ) {
                throw new IllegalArgumentException(
                    "Node must be part of this Graph.");
            }
            return false;
        }
        return true;
    }
    
    /**
     * Get the collection of nodes as a TupleSet. Returns the same result as
     * {@link CompositeTupleSet#getSet(String)} using
     * {@link #NODES} as the parameter.
     * @return the nodes of this graph as a TupleSet instance
     */
    public TupleSet getNodes() {
        return getSet(NODES);
    }
    
    /**
     * Get the backing node table.
     * @return the table of node values
     */
    public Table getNodeTable() {
        return (Table)getSet(NODES);
    }
    
    /**
     * Get the number of nodes in this graph.
     * @return the number of nodes
     */
    public int getNodeCount() {
        return getNodeTable().getRowCount();
    }
    
    /**
     * Get the Node tuple instance corresponding to a node id.
     * @param n a node id (node table row number)
     * @return the Node instance corresponding to the node id
     */
    public Node getNode(int n) {
        return (Node)m_nodeTuples.getTuple(n);
    }
    
    /**
     * Get the Node tuple corresponding to the input node key field value.
     * The node key field is used to find the node id (node table row number),
     * which is then used to retrieve the Node tuple.
     * @param key a node key field value
     * @return the requested Node instance