graph.java

java数据挖掘算法

    /** Copies the given graph into this graph.
     * @param G The graph to be copied.
     */    
    public void assign(Graph G){
        if (G != this){
            clear();
            undirected = G.undirected;
            copy_graph(G);
        }
    }
    
    /** Sets the node entry, does nothing.
     * @param v The node to be set.
     * @param s The new setting. */    
    public void set_node_entry(Node v, String s){
        //waiting on clear_node_entry		clear_node_entry(v.data);
        //obs		clear_node_entry(v->data[0]);
        //		if (node_type().compareTo("string") == 0)
        //obs		if (strcmp(node_type(),"string") == 0)
        //waiting on leda_copy			v.data = leda_copy(s);
        //obs			v->data[0] = leda_copy(s);
        //		else{
        //waiting for definition of istrstream			istrstream in(s.cstring());
        //			read_node_entry(in,v.data);
        //obs			read_node_entry(in,v->data[0]);
        //		}
    }
    
    /** Sets the edge entry, does nothing.
     * @param e The edge to be set.
     * @param s The new setting. */    
    public void set_edge_entry(Edge e, String s){
        //waiting on clear_edge_entry		clear_edge_entry(e.data);
        //obs		clear_edge_entry(e->data[0]);
        //		if (edge_type().compareTo("string") == 0)
        //obs		if (strcmp(edge_type(),"string") == 0)
        //waiting on leda_copy			e.data = leda_copy(s);
        //obs			e->data[0] = leda_copy(s);
        //		else{
        //waiting for definition of istrstream			istrstream in(s.cstring());
        //			read_edge_entry(in,e.data);
        //obs			read_edge_entry(in,e->data[0]);
        //		}
    }
    
    // virtual functions called before and after update operations
    // (e.g. useful for graph editors)
    
    // node handler							// called
    /** Function called before inserting a node.         */
    protected void pre_new_node_handler() {}		// before inserting a node
    /** Function called after inserting a node.
     * @param A The node added. */    
    protected void post_new_node_handler(Node A) {}	// after inserting node v
    /** Function called before deleting a node.
     * @param A Node deleted. */    
    protected void pre_del_node_handler(Node A) {}	// before deleting node v
    /** Function called after node deleted. */
    protected void post_del_node_handler() {}		// after deleting a node
    
    
    // edge handler
    /** Function called before a new edge is created.
     * @param A Source node.
     * @param B Target node.
     */    
    protected void pre_new_edge_handler(Node A, Node B) {}	// before creating (v,w)
    /** Function called after new edge is created.
     * @param E The new edge.
     */    
    protected void post_new_edge_handler(Edge E) {}			// after insertion of e
    
    /** Function called when edge is deleted.
     * @param E The edge deleted.
     */    
    protected void pre_del_edge_handler(Edge E) {}			// before deleteing edge e
    /** Function called after edge is deleted.
     * @param A Source node of edge.
     * @param B Target node of edge.
     */    
    protected void post_del_edge_handler(Node A, Node B) {}	// after deletion of (v,w)
    
    /** Function called before edge is moved.
     * @param E Edge moved.
     * @param A Edge's source node.
     * @param B Edge's target node.
     */    
    protected void pre_move_edge_handler(Edge E,Node A,Node B){}	// before moving e to (v,w)
    /** Function called after edge is moved.
     * @param E The edge moved.
     * @param A The edge's source node.
     * @param B The edge's target node.
     */    
    protected void post_move_edge_handler(Edge E,Node A,Node B){}	// after moved e from (v,w)
    
    /** Function called before edge is hidden.
     * @param E Edge to hide.
     */    
    protected void pre_hide_edge_handler(Edge E) {}          // before hiding edge e
    /** Function called after edge is hidden.
     * @param E Edge hidden.
     */    
    protected void post_hide_edge_handler(Edge E) {}         // after hiding edge e
    
    /** Function called before edge is restored.
     * @param E Edge to be restored.
     */    
    protected void pre_restore_edge_handler(Edge E) {}       // before restoring edge e
    /** Function called after edge is restored.
     * @param E Edge restored.
     */    
    protected void post_restore_edge_handler(Edge E) {}      // after restoring edge e
    
    
    // global handler
    /** Function called before entries are cleared.
     */    
    protected void pre_clear_handler()  {}                 // before deleting graph
    /** Function called after entries are cleared.
     */    
    protected void post_clear_handler() {}                 // after deleting graph
    
    
    /** Returns the number of nodes.
     * @return Number of nodes. */    
    public int number_of_nodes(){return v_list.size(); }
    /** Returns the number of edges.
     * @return Number of edges. */    
    public int number_of_edges(){return e_list.size(); }
    
    /** Returns a list of all nodes in this graph.
     * @return A list of nodes.
     */    
    public LinkedList all_nodes(){
        v_list_tmp.clear();
        for(ListIterator nodes = v_list.listIterator();
        nodes.hasNext();
        v_list_tmp.addLast(nodes.next()));
        return v_list_tmp;
    }
    
    /** Returns a list of all edges in this graph.
     * @return A list of edges.
     */    
    public LinkedList all_edges(){
        e_list_tmp.clear();
        for(ListIterator edges = e_list.listIterator();
        edges.hasNext();
        e_list_tmp.addLast(edges.next()));
        return e_list_tmp;
    }
    
    /** Returns a list of all faces in this graph.
     * @return A list of faces.
     */    
    public LinkedList all_faces(){
        f_list_tmp.clear();
        for(ListIterator faces = f_list.listIterator();
        faces.hasNext();
        f_list_tmp.addLast(faces.next()));
        return f_list_tmp;
    }
    
    /** Choose a random node.
     * @return A node.
     */    
    public Node choose_node(){
        int n = number_of_nodes();
        if (n == 0) return null;
        Random rand = new Random();
        int r = rand.nextInt(n);
        Node v = (Node)v_list.get(r);
        return v;
    }
    
    /** Choose random edge.
     * @return An edge.
     */    
    public Edge choose_edge(){
        int m = number_of_edges();
        if (m == 0) return null;
        Random rand = new Random();
        int r = rand.nextInt(m);
        Edge e = (Edge)e_list.get(r);
        return e;
    }
    
    /** Returns true if this graph is directed, false otherwise.
     * @return True if this graph is directed, false otherwise.
     */    
    public boolean is_directed(){ return !undirected; }
    /** Returns true if this graph is undirected, false otherwise.
     * @return True if this graph is undirected, false otherwise.
     */    
    public boolean is_undirected(){ return undirected; }
    /** Returns true if there are no nodes in this graph, false otherwise.
     * @return True if there are no nodes in this graph, false otherwise.
     */    
    public boolean empty(){ return v_list.size() == 0; }
    
    //entry used to return addresses to the data, but there are no addresses in java
    /** Returns the data stored in this graph object.
     * @param v The object whose information is requested.
     * @return The data stored in the given object.
     */    
    public Object entry(Node v){return v.data;}
    /** Returns the data stored in this graph object.
     * @param e The object whose information is requested.
     * @return The data stored in the given object.
     */    
    public Object entry(Edge e){return e.data;}
    /** Returns the data stored in this graph object.
     * @param f The object whose information is requested.
     * @return The data stored in the given object.
     */    
    public Object entry(Face f){return f.data;}
    
    //essentially the same as entry
    /** Returns the data stored in this graph object.
     * @param v The object whose information is requested.
     * @return The data stored in the given object.
     */    
    public Object inf(Node v){return v.data;}
    /** Returns the data stored in this graph object.
     * @param e The object whose information is requested.
     * @return The data stored in the given object.
     */    
    public Object inf(Edge e){return e.data;}
    /** Returns the data stored in this graph object.
     * @param f The object whose information is requested.
     * @return The data stored in the given object.
     */    
    public Object inf(Face f){return f.data;}
    
    /** Splits edge e into edges e1 and e2.
     * @param e Edge to be split.
     * @param node_inf Node data for target node.
     * @param e1 First edge si is split into.
     * @param e2 Second edge e is split into.
     * @return The new target node.
     */    
    protected Node split_edge(Edge e, Object node_inf, Edge e1, Edge e2){
        // splits e into e1 and e2 by putting new node v on e
        // WARNING: changes e1, e2.
        //node v = source(e);
        Node w = e.target();
        Node u = add_node(node_inf);
        e1 = e;
        e2 = add_edge(u,w,e.data);
        //waiting on copy_edge_entry		copy_edge_entry(e2.data);
        if (undirected){
            u.append_adj_edge(e2,0,0);
            w.insert_adj_edge(e2,e,0,1,0);
            w.del_adj_edge(e,0,1);
            e.term[1] = u;
            u.append_adj_edge(e,0,1);
        }
        else{
            u.append_adj_edge(e2,0,0);
            w.insert_adj_edge(e2,e,1,1,0);
            w.del_adj_edge(e,1,1);
            e.term[1] = u;
            u.append_adj_edge(e,1,1);
        }
        return u;
    }
    
    /** Assigns the given data to the graph object.
     * @param v The node to store the data.
     * @param x The data stored.
     */    
    protected void assign(Node v,Object x){v.data = x;}
    /** Assigns the given data to the graph object.
     * @param e The edge to store the data.
     * @param x The data stored.
     */    
    protected void assign(Edge e,Object x){e.data = x;}
    /** Assigns the given data to the graph object.
     * @param f The face to store the data.
     * @param x The data stored.
     */    
    protected void assign(Face f,Object x){f.data = x;}
    
    /** Returns the face containing e.
     * @param e Edge for which face is requested.
     * @return The face holding e.
     */    
    protected Face access_face(Edge e){return (Face)FaceOf.map_access(e); }
    
    /** Merges the given nodes.
     * @param v1 First node merged.
     * @param v2 Second node merged.
     * @return The merged node.
     */    
    public Node merge_nodes(Node v1,Node v2){
        if (undirected)
            System.err.println("merge_nodes not implemented for undirected graphs.");	//error_handler 1
        for(int i=0; i<2; i++){
            if (v1.last_adj_edge[i] != null)
                v1.last_adj_edge[i].succ_adj_edge[i] = v2.first_adj_edge[i];
            else
                v1.first_adj_edge[i] = v2.first_adj_edge[i];
            if (v2.first_adj_edge[i] != null){
                v2.first_adj_edge[i].pred_adj_edge[i] = v1.last_adj_edge[i];
                v1.last_adj_edge[i] = v2.last_adj_edge[i];
            }
            v1.adj_length[i] += v2.adj_length[i];
            v2.adj_length[i] = 0;
            v2.first_adj_edge[i] = null;
            v2.last_adj_edge[i] = null;
        }
        //waiting for del_node		del_node(v2);
        return v1;
    }
    
    /** Splits edge e into e1 and e2.
     * @param e Edge to be split.
     * @param e1 First edge split from e.
     * @param e2 Second edge split from e.
     * @return The target node of the split edge.
     */    
    public Node split_edge(Edge e,Edge e1,Edge e2){
        //Warning: changes e1 and e2
        Object x = null;
        //waiting for init_node_entry		init_node_entry(x);
        return split_edge(e,x,e1,e2);
    }
    
    /** Makes the given edge hidden.
     * @param e Edge to hide.
     */    
    public void hide_edge(Edge e){
        if (is_hidden(e))
            System.err.println("graph::hide_edge: edge is already hidden.");	//error_handler 1
        pre_hide_edge_handler(e);
        Node v = e.source();