graph.java

java数据挖掘算法

        }
        //obs		forall_nodes(v,G) N[index(v)] = 0;
        parent = G;
        for(ListIterator edges = el.listIterator(); edges.hasNext();){
            e =(Edge)edges.next();
            //obs		forall(e,el)
            v = e.source();
            w = e.target();
            if (N[v.index()] == null) N[v.index()] = new_node((Object)v);
            if (N[w.index()] == null) N[w.index()] = new_node((Object)w);
            if ( e.graph_of() != parent )
                System.err.println("graph: illegal edge in subgraph constructor");	//error_handler 1
            new_edge(N[v.index()],N[w.index()],(Object)e);
        }
        undirected = G.undirected;
        N = null;
        //obs		delete[] N;
    }
    
    /** Returns a listiterator of the list of nodes in this graph.
     * @return The list iterator of nodes.
     */    
    public ListIterator nodeIterator(){return v_list.listIterator();}

    /** Returns a listiterator of edges in this graph.
     * @return The list iterator of edges in this graph.
     */    
    public ListIterator edgeIterator(){return e_list.listIterator();}
    
    
    
    
    /** Creates a new edge to the given nodes. Can be used with undirected graphs.
     * @param v The source node.
     * @param e1 Edge connecting to the source node.
     * @param w The target node.
     * @param e2 Edge connecting to the target node.
     * @param i The data to be stored in the edge.
     * @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.
     * @return The new edge. */    
    public Edge new_edge(Node v, Edge e1, Node w, Edge e2, Object i,int d1,int d2){
        if (undirected)
        { if (v == w)
              System.err.println("new_edge(v,e1,w,e2): selfloop in undirected graph.");
          if (e1 != null && v != e1.source() && v != e1.target())
              System.err.println("new_edge(v,e1,w,e2): v is not adjacent to e1.");
          if (e2 != null && w != e2.source() && w != e2.target())
              System.err.println("new_edge(v,e1,w,e2): w is not adjacent to e2.");
        }
        else
        { if (e1 != null && v != e1.source())
              System.err.println("new_edge(v,e1,w,e2): v is not source of e1.");
          if (e2 != null && w != e2.source() && w != e2.target())
              System.err.println("new_edge(v,e1,w,e2): w is not target of e2.");
        }
        
        pre_new_edge_handler(v,w);
        Edge e = add_edge(v,w,i);
        ins_adj_edge(e,v,e1,w,e2,d1,d2);
        post_new_edge_handler(e);
        return e ;
    }
    
    /** Creates a new edge between the given nodes and containing the given information.
     * @param v The source node for the new edge.
     * @param w The target node for the new edge.
     * @param i The data to be stored in the edge.
     * @return The new edge. */    
    public Edge new_edge(Node v, Node w, Object i){
        // append (v,w) it to adj_list of v and to in_list (adj_list) of w
        return new_edge(v,null,w,null,i,0,0);}
    
    /** Creates a new edge between the source of the given edge and the given target node.
     * @param e The edge connected to the source node.
     * @param w The target node.
     * @param i The data stored in the new edge.
     * @param dir Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
     * @return The new edge. */    
    public Edge new_edge(Edge e, Node w, Object i, int dir){
        // add edge (e.source(),w) after/before e1 to adj_list of e.source()
        // append it to in_list (adj_list) of w
        return new_edge(e.source(),e,w,null,i,dir,0);
    }
    
    /** Creates a new edge between the target of the given edge and the given source node.
     * @param v The source node.
     * @param e The edge connected to the target node.
     * @param i The data stored in the new edge.
     * @param dir Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
     * @return The new edge. */    
    public Edge new_edge(Node v, Edge e, Object i, int dir){
        // append edge(v,e.target())  to adj_list of v
        // insert it after/before e to in_list (adj_list) of e.target()
        return new_edge(v,null,e.target(),e,i,0,dir);
    }
    
    /** Creates a new edge 
     * @param e1 Edge connecting to source node.
     * @param e2 Edge connecting to target node.
     * @param i The data stored in the new edge.
     * @param dir1 Method of connecting to e1. The new edge is connected after(if dir1=0)/before(if dir1=1) e1.
     * @param dir2 Method of connecting to e2. The new edge is connected after(if dir2=0)/before(if dir2=1) e2.
     * @return The new edge. */    
    public Edge new_edge(Edge e1, Edge e2, Object i, int dir1, int dir2){
        //add edge (e1.source(),e2.target())
        //after(dir=0)/before(dir=1) e1 to adj_list of e1.source()
        //after(dir=1)/before(dir=1) e2 to in_list (adj_list) of e2.target()
        return new_edge(e1.source(),e1,e2.target(),e2,i,dir1,dir2);
    }
    
    /** Creates a new edge between the given nodes.
     * @param v The source node.
     * @param e Edge connected to the source node.
     * @param w The target node.
     * @param i The data stored in the new edge.
     * @param dir Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
     * @return The new edge. */    
    public Edge new_edge(Node v, Edge e, Node w, Object i, int dir){
        // add edge (v,w) after/before e to adj_list of v
        // append it to in_list (adj_list) of w
        return new_edge(v,e,w,null,i,dir,0);
    }
    
    /** Creates a new edge between the given nodes.
     * @param v The source node.
     * @param w The target node.
     * @param e Edge connected to the target node.
     * @param i The data stored in the new edge.
     * @param dir Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
     * @return The new edge. */    
    public Edge new_edge(Node v, Node w, Edge e, Object i, int dir){
        // append edge (v,w) to adj_list of v
        // insert it after/before e to in_list (adj_list) of w
        return new_edge(v,null,w,e,i,dir,0);
    }
    
    /** Creates a new edge between the given nodes.
     * @param v The source node.
     * @param w The target node.
     * @return The new edge. */    
    public Edge new_edge(Node v,Node w){
        Object x= null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(v,w,x);
    }
    
    /** Creates a new edge between the source of the given edge and the given target node.
     * @param e Edge connected to the source node.
     * @param w The target node.
     * @return The new edge. */    
    public Edge new_edge(Edge e,Node w){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(e,w,x,after);
    }
    
    /** Creates a new edge between the source of the given edge and the given target node.
     * @param e Edge connected to the source node.
     * @param w The target node.
     * @param dir Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
     * @return The new edge. */    
    public Edge new_edge(Edge e,Node w,int dir){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(e,w,x,dir);
    }
    
    /** Creates a new edge between the given source node and the target of the given edge.
     * @param v The source node.
     * @param e Edge connected to the target node.
     * @return The new edge. */    
    public Edge new_edge(Node v, Edge e){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(v,e,x,after);
    }
    
    /** Creates a new edge between the given source node and the target of the given edge.
     * @param v The source node.
     * @param e Edge connected to the target node.
     * @param dir Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
     * @return The new edge. */    
    public Edge new_edge(Node v, Edge e, int dir){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(v,e,x,dir);
    }
    
    /** Creates a new edge between the source and target nodes of the given edges.
     * @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.
     * @return The new edge. */    
    public Edge new_edge(Edge e1, Edge e2, int d1, int d2){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(e1,e2,x,d1,d2);
    }
    
    /** Creates a new edge between the source and target nodes of the given edges. The new edge is added after e2.
     * @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.
     * @return The new edge. */    
    public Edge new_edge(Edge e1, Edge e2, int d1){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(e1,e2,x,d1,after);
    }
    
    /** Creates a new edge between the source and target nodes of the given edges. The new edge is added after both edges.
     * @param e1 Edge connected to the source node.
     * @param e2 Edge connected to the target node.
     * @return The new edge. */    
    public Edge new_edge(Edge e1, Edge e2){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(e1,e2,x,after,after);
    }
    
    /** Creates a new edge between the given nodes.
     * @param v The source node.
     * @param e1 Edge connected to the source node.
     * @param w The target 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.
     * @return The new edge. */    
    public Edge new_edge(Node v, Edge e1, Node w, Edge e2, int d1, int d2){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(v,e1,w,e2,x,d1,d2);
    }
    
    /** Creates a new edge between the given nodes. The new edge is added after e2.
     * @param v The source node.
     * @param e1 Edge connected to the source node.
     * @param w The target 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.
     * @return The new edge.
     */    
    public Edge new_edge(Node v, Edge e1, Node w, Edge e2, int d1){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(v,e1,w,e2,x,d1,after);
    }
    
    /** Creates a new edge between the given nodes. The new edge is added after both edges.
     * @param v The source node.
     * @param e1 Edge connected to the source node.
     * @param w The target node.
     * @param e2 Edge connected to the target node.
     * @return The new edge. */    
    public Edge new_edge(Node v, Edge e1, Node w, Edge e2){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(v,e1,w,e2,x,after,after);
    }
    
    /** Creates a new edge between the given nodes.
     * @param v The source node.
     * @param e Edge connected to the source node.
     * @param w The target node.
     * @param d Method of connecting to e. The new edge is connected after(if d=0)/before(if d=1) e.
     * @return The new edge. */    
    public Edge new_edge(Node v, Edge e, Node w,int d){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(v,e,w,x,d);
    }
    
    /** Creates a new edge between the given nodes. the new edge is added after e.
     * @param v The source node.
     * @param e Edge connected to the source node.
     * @param w The target node.
     * @return The new edge. */    
    public Edge new_edge(Node v, Edge e, Node w){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(v,e,w,x,after);
    }
    
    /** Creates a new edge between the given nodes.
     * @param v The source node.
     * @param w The target node.
     * @param e Edge connected to the target node.
     * @param d Method of connecting to e. The new edge is connected after(if d=0)/before(if d=1) e.
     * @return The new edge. */    
    public Edge new_edge(Node v, Node w, Edge e, int d){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(v,e,w,x,d);
    }
    
    /** Creates a new edge between the given nodes.
     * @param v The source node.
     * @param w The target node.
     * @param e Edge connected to the target node.
     * @return The new edge. */    
    public Edge new_edge(Node v, Node w, Edge e){
        Object x = null;
        //waiting for init_edge_entry		init_edge_entry(x);
        return new_edge(v,e,w,x,after);
    }
    
    private Node add_node(Object info){
        Node v;
        if (v_free.size() == 0){
            //obs			v = (node)std_memory.allocate_bytes(node_bytes());
            //obs			new (v) node_struct(info);
            v = new Node(info);
            v.owner = this;
            v.id = ++max_node_index;
            //don't know what succ_link is			v.succ_link = null;
        }
        else{
            v = (Node)v_free.removeFirst();
            v.data = info;
        }
        v_list.addLast(v);
        GraphMap m;
        //obs		forall(m,map_list[0]) m->re_init_entry(v);
        for(ListIterator maps = map_list[0].listIterator();
        maps.hasNext();
        m = (GraphMap)maps.next(), m.re_init_entry(v));
        return v;
    }
    
    private Edge add_edge(Node v,Node w,Object info){
        Edge e;
        if (v.owner != this)
            System.err.println("new_edge(v,w): v not in graph");
        if (w.owner != this)