graph.java

java数据挖掘算法

        Node w = e.target();
        del_adj_edge(e,v,w);
        e_list.remove(e);
        h_list.addLast(e);
        e.id |= 0x80000000;
        post_hide_edge_handler(e);
    }
    
    /** Returns true if the given edge is hidden, false otherwise.
     * @param e The edge to be checked.
     * @return True if the given edge is hidden, false otherwise.
     */    
    public boolean is_hidden(Edge e){return (e.id & 0x80000000) != 0;}
    
    /** Restores edge from being hidden.
     * @param e Edge to be restored.
     */    
    public void restore_edge(Edge e){
        if (!is_hidden(e))
            System.err.println("graph::restore_edge: edge is not hidden.");	//error_handler 1
        pre_restore_edge_handler(e);
        Node v = e.source();
        Node w = e.target();
        h_list.remove(e);
        e_list.addLast(e);
        if (undirected){
            v.append_adj_edge(e,0,0);
            w.append_adj_edge(e,0,1);
        }
        else{
            v.append_adj_edge(e,0,0);
            w.append_adj_edge(e,1,1);
        }
        //		e.id = indexof(e);	//edge id needs to be updated to point to the right location :JL
        e.id = e.index();
        post_restore_edge_handler(e);
    }
    
    /** Restore all edges.
     */    
    public void restore_all_edges(){
        Edge e;
        while (h_list.size() > 0){
            e =(Edge)h_list.getFirst();
            restore_edge(e);
        }
        //obs		Edge e = (Edge)h_list.head();
        //obs		while (e){
        //obs			edge succ = (edge)h_list.succ(e);
        //obs			restore_edge(e);
        //obs			e = succ;
        //obs		}
    }
    
    /** Delete the given node.
     * @param v The node to be deleted.
     */    
    public void del_node(Node v){
        if (v.owner != this)
            System.err.println("del_node(v): v is not in G");	//error_handler 4
        // delete adjacent edges
        Edge  e;
        //waiting for del_edge		while ((e=v.first_adj_edge[0]) != null) del_edge(e);
        if (!undirected)
            //waiting for del_edge		while ((e=v.first_adj_edge[1]) != null) del_edge(e);
            pre_del_node_handler(v);
        //waiting for clear_node_entry		if (parent == null) clear_node_entry(v.data);
        v_list.remove(v);
        v_free.addLast(v);
        //obs		v_free.append(v);
        //waiting for GraphMap() in GraphMap		GraphMap m;
        //waiting for GraphMap() in GraphMap		for(int j = 0;j < 3; j++){
        //waiting for GraphMap() in GraphMap			int i = m.g_index;
        //waiting for clear_entry in GraphMap			if (i > 0) m.clear_entry(v.data);
        //waiting for GraphMap() in GraphMap		}
        //obs		forall(m,map_list[0]){
        //obs			int i = m.g_index;
        //obs			if (i > 0) m.clear_entry(v.data);
        //obs		}
        //waiting for post_del_node_handler in GraphMap		post_del_node_handler();
    }
    
    private void del_face(Face f){
        f_list.remove(f);
        f_free.addLast(f);
        //obs		f_free.append(f);
        GraphMap m;
        for(ListIterator maps = map_list[2].listIterator(); maps.hasNext(); ){
            m = (GraphMap)maps.next();
            //obs		forall(m,map_list[2]){
            int i = m.g_index;
            //waiting for clear_entry in GraphMap			if (i > 0) m.clear_entry(f.data);
            //obs			if (i > 0) m.clear_entry(f.data[i]);
        }
    }
    
    /** Edge to be deleted.
     * @param e Edge to be deleted.
     */    
    public void del_edge(Edge e){
        Node v = e.source();
        Node w = e.target();
        if (v.owner != this) System.err.println("del_edge(e): e is not in G");	//error_handler 10
        pre_del_edge_handler(e);
        if (is_hidden(e)) restore_edge(e);
        if (e.rev != null) e.rev.rev = null;
        del_adj_edge(e,v,w);
        //waiting for clear_edge_entry		if (parent == null) clear_edge_entry(e.data);
        e_list.remove(e);
        e_free.addLast(e);
        //obs		e_free.append(e);
        GraphMap m;
        int i;
        for(int j = 0; j < map_list[1].size(); j++){
            m = (GraphMap)map_list[1].get(j);
            i = m.g_index;
            //waiting for clear_entry			if (i > 0) m.clear_entry(e.data);
        }
        //obs		forall(m,map_list[1]){
        //obs			int i = m->g_index;
        //obs			if (i > 0) m->clear_entry(e->data[i]);
        //obs		}
        post_del_edge_handler(v,w);
    }
    
    /** Deletes the nodes in the given list.
     * @param L List of nodes to be deleted.
     */    
    public void del_nodes(LinkedList L){
        for(int i = 0; i < L.size(); i++) del_node((Node)L.get(i));
        //obs		Node v;
        //obs		forall(v,L) del_node(v);
    }
    
    /** Deletes the edges in the given list.
     * @param L List of edges to be deleted.
     */    
    public void del_edges(LinkedList L){
        for(int i = 0; i < L.size(); i++) del_edge((Edge)L.get(i));
        //obs		edge e;
        //obs		forall(e,L) del_edge(e);
    }
    
    /** Deletes all nodes in graph.
     */    
    public void del_all_nodes() { clear(); }
    
    /** Deletes all edges in graph.
     */    
    public void del_all_edges(){
        Edge e;
        //obs		e = (Edge)e_list.getFirst();
        //obs		while (e)
        //obs			{ edge next = (edge)e_list.succ(e);
        //obs			dealloc_edge(e);
        //obs			e = next;
        //obs		}
        //obs		e = (edge)h_list.head();
        //obs		while (e)
        //obs			{ edge next = (edge)h_list.succ(e);
        //obs			dealloc_edge(e);
        //obs			e = next;
        //obs		}
        //obs		e = (edge)e_free.head();
        //obs		while (e)
        //obs			{ edge next = (edge)e_free.succ(e);
        //obs			dealloc_edge(e);
        //obs			e = next;
        //obs		}
        e_list.clear();
        h_list.clear();
        e_free.clear();
        max_edge_index = -1;
        Node v;
        for(int n = 0; n < v_list.size(); n++){
            v =(Node)v_list.get(n);
            for(int i = 0; i<2; i++){
                v.first_adj_edge[i] = null;
                v.last_adj_edge[i] = null;
                v.adj_length[i] = 0;
            }
        }
        //obs		forall_nodes(v,*this)
        //obs		for(int i=0; i<2; i++)
        //obs			{ v->first_adj_edge[i] = nil;
        //obs			v->last_adj_edge[i] = nil;
        //obs			v->adj_length[i] = 0;
        //obs		}
    }
    
    /** Deletes all faces of graph.
     */    
    public void del_all_faces(){
        f_free.clear();
        f_list.clear();
        FaceOf = null;
        max_face_index = -1;
    }
    
    /** Moves edge e.
     * @param e Edge to be moved.
     * @param e1 Edge connected to the source node.
     * @param e2 Edge connected to the target node.
     * @param d1 Method of connecting to e1. The new edge is connected after(if d1=0)/before(if d1=1) e1.
     * @param d2 Method of connecting to e2. The new edge is connected after(if d2=0)/before(if d2=1) e2.
     */    
    public void move_edge(Edge e,Edge e1,Edge e2,int d1,int d2){
        if (is_hidden(e))
            System.err.println("graph::move_edge:  cannot move hidden edge.");	//error_handler 1
        Node v0 = e.source();
        Node w0 = e.target();
        Node v = e1.source();
        Node w = e1.target();
        pre_move_edge_handler(e,v,w);
        del_adj_edge(e,e.source(),e.target());
        e.term[0] = v;
        e.term[1] = w;
        ins_adj_edge(e,v,e1,w,e2,d1,d2);
        post_move_edge_handler(e,v0,w0);
    }
    
    /** Moves edge e.
     * @param e Edge to be moved.
     * @param e1 Edge connected to the source node.
     * @param w New target node.
     * @param dir Method of connecting to e1. The new edge is connected after(if dir=0)/before(if dir=1) e1.
     */    
    public void move_edge(Edge e,Edge e1,Node w,int dir){
        if (is_hidden(e))
            System.err.println("graph::move_edge:  cannot move hidden edge.");	//error_handler 1
        Node v0 = e.source();
        Node w0 = e.target();
        Node v = e1.source();
        pre_move_edge_handler(e,v,w);
        del_adj_edge(e,e.source(),e.target());
        e.term[0] = v;
        e.term[1] = w;
        ins_adj_edge(e,e1.source(),e1,w,null,dir,0);
        post_move_edge_handler(e,v0,w0);
    }
    
    /** Moves edge e.
     * @param e Edge to be moved.
     * @param v New source node.
     * @param w New target node.
     */    
    public void move_edge(Edge e, Node v, Node w){
        if (is_hidden(e))
            System.err.println("graph::move_edge:  cannot move hidden edge.");	//error_handler 1
        Node v0 = e.source();
        Node w0 = e.target();
        pre_move_edge_handler(e,v,w);
        del_adj_edge(e,e.source(),e.target());
        e.term[0] = v;
        e.term[1] = w;
        ins_adj_edge(e,v,null,w,null,0,0);
        post_move_edge_handler(e,v0,w0);
    }
    
    /** Reverses the direction of the given edge.
     * @param e The edge whose direction is reversed.
     * @return The reversed edge.
     */    
    public Edge rev_edge(Edge e){
        if (is_hidden(e))
            System.err.println("graph::move_edge:  cannot move hidden edge.");	//error_handler	1
        Node v = e.source();
        Node w = e.target();
        pre_move_edge_handler(e,w,v);
        if (is_hidden(e)){ // e hidden
            e.term[0] = w;
            e.term[1] = v;
            return e;
        }
        if (undirected){
            Edge s = e.succ_adj_edge[0];
            Edge p = e.pred_adj_edge[0];
            e.succ_adj_edge[0] = e.succ_adj_edge[1];
            e.pred_adj_edge[0] = e.pred_adj_edge[1];
            e.succ_adj_edge[1] = s;
            e.pred_adj_edge[1] = p;
            e.term[0] = w;
            e.term[1] = v;
        }
        else{
            del_adj_edge(e,v,w);
            e.term[0] = w;
            e.term[1] = v;
            ins_adj_edge(e,w,null,v,null,0,0);
        }
        post_move_edge_handler(e,v,w);
        return e;
    }
    
    /** Reverses the direction on all edges.
     */    
    public void rev_all_edges(){
        if (!undirected){
            LinkedList L = all_edges();
            for(ListIterator LI = L.listIterator();
            LI.hasNext();
            rev_edge((Edge)LI.next()));
            //obs    edge e;
            //obs    forall(e,L) rev_edge(e);
        }
    }
    
    /** Reverses all edges.
     * @return Graph of reversed edges.
     */    
    public Graph rev(){rev_all_edges(); return this;}
    
    /** Creates a list of reversed edges.
     * @return List of reversed edges.
     */    
    public LinkedList insert_reverse_edges(){
        
        LinkedList L = new LinkedList();
        Edge e = first_edge();
        if (e != null){
            L.addLast(new_edge(e.target(),e.source(),e.data));
            //waiting for copy_edge_entry			copy_edge_entry(e.data);
            e = succ_edge(e);
        }
        Edge stop = last_edge();
        while (e != stop){
            L.addLast(new_edge(e.target(),e.source(),e.data));
            //waiting for copy_edge_entry			copy_edge_entry(e.data);
            e = succ_edge(e);
        }
        return L;
    }
    
    /** Converts this graph