graph.java

java数据挖掘算法

            System.err.println("new_edge(v,w): w not in graph");
        if ( e_free.size() == 0){
            //obs			e = (edge)std_memory.allocate_bytes(edge_bytes());
            //obs			new (e) edge_struct(v,w,inf);
            e = new Edge(v,w,info);
            e.id = ++max_edge_index;
        }
        else{
            e = (Edge)e_free.removeFirst();
            e.data = info;
            e.term[0] = v;
            e.term[1] = w;
            e.rev = null;
            e.succ_adj_edge[0] = null;
            e.succ_adj_edge[1] = null;
            e.pred_adj_edge[0] = null;
            e.pred_adj_edge[1] = null;
        }
        e_list.addLast(e);
        GraphMap m;
        //obs		forall(m,map_list[1]) m->re_init_entry(e);
        for(ListIterator maps = map_list[1].listIterator();
        maps.hasNext();
        m = (GraphMap)maps.next(), m.re_init_entry(e));
        return e;
    }
    
    
    private Face add_face(Object info){
        Face f;
        if (f_free.size() == 0){
            //obs			f = (face)std_memory.allocate_bytes(face_bytes());
            //obs			new (f) face_struct(inf);
            f = new Face(info);
            f.owner = this;
            f.id = ++max_face_index;
        }
        else{
            f = (Face)f_free.removeFirst();
            f.data = info;
        }
        f_list.addLast(f);
        GraphMap m;
        //obs		forall(m,map_list[2]) m->re_init_entry(f);
        for(ListIterator maps = map_list[2].listIterator();
        maps.hasNext();
        m = (GraphMap)maps.next(), m.re_init_entry(f));
        return f;
    }
    
    
    /** Adds edge e between the given nodes.
     * @param e Edge to be added.
     * @param v Source node for the edge.
     * @param e1 Edge connected to the source node.
     * @param w Target node for the edge.
     * @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 ins_adj_edge(Edge e, Node v, Edge e1, Node w, Edge e2,int d1,int d2){
        // insert edge e
        // after(if d1=0)/before(if d1=1) e1 to adj_list of v
        // after(if d2=0)/before(if d2=1) e2 to in_list (adj_list) of w
        // (most general form of new_edge)
        
        if ( undirected )
        { if (v == w)
              System.err.print("new_edge(v,e1,w,e2): selfloop in undirected graph.");
          if (e1 != null && v != e1.source() && v != e1.target())
              System.err.print("new_edge(v,e1,w,e2): v is not adjacent to e1.");
          if (e2 != null && w != e2.source() && w != e2.target())
              System.err.print("new_edge(v,e1,w,e2): w is not adjacent to e2.");
          
          v.insert_adj_edge(e,e1,0,0,d1);
          w.insert_adj_edge(e,e2,0,1,d2);
        }
        else
        { if (e1 != null && v != e1.source())
              System.err.print("new_edge(v,e1,w,e2): v is not source of e1.");
          if (e2 != null && w != e2.source() && w != e2.target())
              System.err.print("new_edge(v,e1,w,e2): w is not target of e2.");
          
          v.insert_adj_edge(e,e1,0,0,d1);
          w.insert_adj_edge(e,e2,1,1,d2);
        }
    }
    
    /** Deletes the given edge between the given nodes.
     * @param e The edge to be deleted.
     * @param v The source node for the edge.
     * @param w The target node for the edge. */    
    public void del_adj_edge(Edge e, Node v, Node w)
    { if (undirected){
          v.del_adj_edge(e,0,0);
          w.del_adj_edge(e,0,1);
      }
      else{
          v.del_adj_edge(e,0,0);
          w.del_adj_edge(e,1,1);
      }
    }
    
    /** Registers the given GraphMap.
     * @param M Graphmap to be registered.
     * @return -1 if there is not enough free_data space, 0 otherwise. */    
    public int register_map(GraphMap M){
        int k = M.kind;
        map_list[k].addLast(M);				//appends the map onto the end of map_list
        //		M.g_loc = map_list[k].size() - 1;		//M.g_loc gets the index number of GraphMap M in map_list
        
        //waiting on LEDA_GRAPH_DATA		if (LEDA_GRAPH_DATA)		//may be added to Globals class
        //		if (free_data[k].size() <= 0)
        //		System.err.println("graph::register_map: all data " + data_sz[k] + " slots used");	//error_handler 1
        return (free_data[k].size() <= 0) ? -1 : 0; //free_data[k].removeFirst();
        
    }
    
    /** Unregisters the given GraphMap.
     * @param M Graphmap to be unregistered. */    
    public void unregister_map(GraphMap M){
        int k = M.kind;
        map_list[k].remove(M.g_loc);
        if (M.g_index > 0) free_data[k].addFirst(new Integer(M.g_index));
    }
    
    /** Returns the first node in the graph's node list.
     * @return The first node.
     */    
    public Node first_node(){return (Node) v_list.getFirst();}

    /** Returns the last node in the graph's node list.
     * @return The last node.
     */    
    public Node last_node(){return (Node) v_list.getLast();}

    /** Returns the next node in the node list.
     * @param v The node whose successor is requested.
     * @return The next node. */    
    public Node succ_node(Node v){
        if (v != null && v.id < v_list.size() && v.id > 0)
        {return (Node)v_list.get(v.id + 1);}
        else {return null;}
    }
    
    /** Returns the previous node in the node list.
     * @param v The node whose predecessor is requested.
     * @return The previous node. */    
    public Node pred_node(Node v){
        if (v != null && v.id <= v_list.size() && v.id >= 0)
        {return (Node)v_list.get(v.id - 1);}
        else {return null;}
    }
    
    /** Returns the first edge in the edge list.
     * @return The first edge. */    
    public Edge first_edge(){return (Edge) e_list.getFirst();}

    /** Returns the last edge in the edge list.
     * @return The last edge. */    
    public Edge last_edge(){return (Edge) e_list.getLast();}

    /** Returns the next edge in the edge list.
     * @param e The edge whose successor is requested.
     * @return The next edge.
     */    
    public Edge succ_edge(Edge e){
        if (e != null && e.id < e_list.size() && e.id >= 0)
        {return (Edge)e_list.get(e.id + 1);}
        else {return null;}
    }

    /** Returns the previous edge in the edge list.
     * @param e The edge whose predecessor is requested.
     * @return The previous edge. */    
    public Edge pred_edge(Edge e){
        if (e != null && e.id <= e_list.size() && e.id > 0)
        {return (Edge)e_list.get(e.id - 1);}
        else {return null;}
    }
    
    /** Copy constructor.
     * @param a Graph to be copied.
     */    
    public Graph(Graph a){
        undirected = a.undirected;
        copy_graph(a);
        node_data_map = new GraphMap(this,0);
        edge_data_map = new GraphMap(this,1);
        adj_iterator = new GraphMap(this,0,0);
        a.copy_all_entries();
    }
    
    /** Copies all entries; does nothing.
     */    
    protected void copy_all_entries(){
        //obs		Node v;
        
        //waiting for copy_node_entry		for(ListIterator nodes = v_list.listIterator();
        //waiting for copy_node_entry		    nodes.hasNext();
        //waiting for copy_node_entry		    copy_node_entry(((Node)nodes.next()).data));
        
        //obs		forall_nodes(v,this) copy_node_entry(v.data[0]);
        //obs		for(Node LOOP_VAR = G.first_node(); LOOP_VAR != null; LOOP_VAR = G.succ_node(LOOP_VAR);)
        //obs			copy_node_entry(LOOP_VAR.data);
        //obs		Edge e;
        //obs		forall_edges(e,this) copy_edge_entry(e.data[0]);
        
        //waiting for copy_edge_entry		for(ListIterator edges = e_list.listIterator();
        //waiting for copy_edge_entry		    edges.hasNext();
        //waiting for copy_edge_entry		    copy_edge_entry(((Edge)edges.next()).data));
        // hidden edges
        //waiting for copy_edge_entry		for(ListIterator h_edges = h_list.listIterator();
        //waiting for copy_edge_entry		    h_edges.hasNext();
        //waiting for copy_edge_entry		    copy_edge_entry(((Edge)h_edges.next()).data));
        
        //obs		for(e = (Edge)h_list.getFirst(); e != null; e = (Edge)h_list.succ(e))
        //obs			copy_edge_entry(e.data);
    }
    
    /** Clears all entries, does nothing.
     */    
    protected void clear_all_entries(){
        //waiting for clear_node_entry		for(ListIterator nodes = v_list.listIterator();
        //waiting for clear_node_entry		    nodes.hasNext();
        //waiting for clear_node_entry		    clear_node_entry(((Node)nodes.next()).data));
        //obs		node v;
        //obs		forall_nodes(v,*this) clear_node_entry(v->data[0]);
        //waiting for clear_edge_entry		for(ListIterator edges = e_list.listIterator();
        //waiting for clear_edge_entry		    edges.hasNext();
        //waiting for clear_edge_entry		    clear_edge_entry(((Edge)edges.next()).data));
        //obs		edge e;
        //obs		forall_edges(e,*this) clear_edge_entry(e->data[0]);
        // hidden edges
        //waiting for clear_edge_entry		for(ListIterator h_edges = h_list.listIterator();
        //waiting for clear_edge_entry		    h_edges.hasNext();
        //waiting for clear_edge_entry		    clear_edge_entry(((Edge)h_edges.next()).data));
        //obs		for(e = (edge)h_list.head(); e; e = (edge)h_list.succ(e))
        //obs		clear_edge_entry(e->data[0]);
    }
    
    /** Returns "void".
     * @return "void" */    
    public String node_type(){ return "void"; }

    /** Returns "void".
     * @return "void" */    
    public String edge_type(){ return "void"; }

    /** Returns "void".
     * @return "void" */    
    public String face_type(){ return "void"; }
    
    /** Copies the given graph.
     * @param G The graph to be copied. */    
    public void copy_graph(Graph G){
        
        int n = G.number_of_nodes();
        
        for(int k = 0; k < 3; k++){
            data_sz[k] = G.data_sz[k];
            //free_data isn't a list of integers			for(int i=0; i < data_sz[k]; i++) free_data[k].addLast(i);
        }
       
        max_node_index = -1;
        max_edge_index = -1;
        max_face_index = -1;
        e_list.clear();
        FaceOf = null;
        parent = null;
        
        if (n == 0) return;	//If there are no nodes in Graph G there is no need to copy them
        
        Node[] node_vec = new Node[G.max_node_index+1];			//allocate additional vectors
        Edge[] edge_vec = new Edge[G.max_edge_index+1];
        
        if (node_vec == null || edge_vec == null)				//checks to see if vectors were allocated
            System.err.println(" copy_graph: out of memory");	//error_handler 1
        
        // allocate a single block of memory for all nodes
        //no memory allocation in java		// memory_allocate_block(sizeof(node_struct),n);
        
        Node v;
        for(ListIterator nodes = G.v_list.listIterator();
        nodes.hasNext();
        v = (Node)nodes.next(),
        new_node(v.data));
        
        
        // allocate a single block of memory for all edges
        // memory_allocate_block(sizeof(edge_struct),m);
        
        boolean loops_deleted = false;
        
        // copy faces (if existing)
        Face f;
        Face f1;
        for(ListIterator faces = G.f_list.listIterator();
        faces.hasNext();
        f = (Face)faces.next());
        node_vec = null;
        edge_vec = null;
        if ( loops_deleted )
            System.err.println("selfloops deleted in ugraph copy constructor");
    }
    
    /** Creates a new node.
     * @return A new node. */    
    public Object new_node(){
        Object x = null;
        pre_new_node_handler();
        Node v = add_node(x);
        v.setIndexNumber(v_list.indexOf(v));//used to provide reference numbers for Inducer.display_struct
        post_new_node_handler(v);
        return v;
    }
    
    /** Creates a new node.
     * @param i Data to be stored in this node.
     * @return A new node. */    
    protected Node new_node(Object i){
        pre_new_node_handler();
        Node v = add_node(i);
        v.setIndexNumber(v_list.indexOf(v)); //used to provide reference numbers for Inducer.display_struct
        post_new_node_handler(v);
        return v;
    }
    
    private Face new_face(Object i){
        return add_face(i);
    }
    
    private Face new_face(){
        Object i = null;
        return add_face(i);
    }