network.java

MASON代表多主体邻里或网络仿真(Multi-Agent Simulator of Neighborhoods or Networks)。它是乔治梅森大学用Java开发的离散事件多主体仿真核心库

    
    /** Synonym for clear(), here only for backward-compatibility.
        Removes all nodes, deleting all edges from the Field as well.  Returns the nodes as a Bag, which you
        are free to modify as it's no longer used internally by the Network. */
    public Bag removeAllNodes()
        {
        return clear();
        }

    /** Returns all the objects in the Sparse Field.  Do NOT modify the bag that you receive out this method -- it
        is used internally.  If you wish in modify the Bag you receive, make a copy of the Bag first, 
        using something like <b>new Bag(<i>foo</i>.getallNodes())</b>. */
    public Bag getAllNodes()
        {
        return allNodes;
        }
    
    /** Iterates over all objects.  
        NOT fail-fast, and remove() not supported.  Use this method only if you're
        woozy about accessing allObject.numObjs and allObject.objs directly. 
        
        For the fastest scan, you can do:
        <p><tt>
        
        for(int x=0;x&lt;field.allNodes.numObjs;x++) ... field.allNodes.objs[x] ... </tt>
        
        <p>... but do NOT modify the allNodes.objs array.
    */
    public Iterator iterator() { return allNodes.iterator(); }

    /** The structure stored in the indexOutInHash hash table.  Holds the index of
        a node in the allNodes bag, a Bag containing the node's outgoing edges,
        and a Bag containing the node's incoming edges.  */
    public static class IndexOutIn implements java.io.Serializable
        {
        /** Index of the node in the allNodes bag */
        public int index;
        /** Bag containing outgoing edges of (leaving) the node */
        public Bag out;
        /** Bag containing incoming edges of (entering) the node */
        public Bag in;
               
        public IndexOutIn(final int index, final Bag out, final Bag in)
            {
            this.index = index;
            this.out = out;
            this.in = in;
            }
        // static inner classes don't need serialVersionUIDs
        }

    /*
      Returns the index of a node.
    */
    public int getNodeIndex( final Object node )
        {
        IndexOutIn ioi = (IndexOutIn)(indexOutInHash.get(node));
        if( ioi == null )
            throw new RuntimeException( "Object parameter is not a node in the network." );
        return ioi.index;
        }



    /**
     * This reverse the direction of all edges in the graph.
     * It is more expensive to clone the graph than to reverse the edges in place.
     * It is more than twice as fast to reverse the edges than to 
     * create the dual graph. As a matter of fact getDualNetwork() took 240 time units
     * while  two reverseAllEdges() calls took only 40 time units on a directed
     * graph (1time unit = 1 millisecond / 10000 calls).
     * 
     * In that case it is more advantageous to reverse the edges, 
     * compute whatever stats on the dual and revert it than to allocate memory.
     * 
     */
    public void reverseAllEdges()
        {
        if(!directed) return;//that was quick
        int n = allNodes.numObjs;
        Iterator i = indexOutInHash.values().iterator();
        for(int k=0;k<n;k++)
            {
            IndexOutIn ioi= (IndexOutIn)i.next();
            Bag tmpB = ioi.out;   ioi.out = ioi.in;   ioi.in = tmpB;
            if(ioi.in!=null)
                for(int j=0;j<ioi.in.numObjs;j++)
                    {
                    Edge e = (Edge)ioi.in.objs[j];
                    //reverse e
                    Object tmpO = e.from;      e.from = e.to;                e.to= tmpO;
                    int tmpI = e.indexFrom;    e.indexFrom = e.indexTo;      e.indexTo = tmpI;
                    }
            }
        }
    
    
    /**
     * An advantage over calling addNode and addEdge n and m times, 
     * is to allocate the Bags the right size the first time.
     * @return a clone of this graph
     * 
     * I cannot use clone() cause it's too shallow.
     * I don't need the deep clone cause I want to reuse the nodes 
     * I need a special custom clone
     */
    public Network cloneGraph()
        {
        Network clone = new Network(directed);
        clone.allNodes.addAll(allNodes);
        int n = allNodes.numObjs;
        Iterator ioiIterator = indexOutInHash.values().iterator();
        Network.IndexOutIn[] ioiArray = new                Network.IndexOutIn[n];

        for(int k=0;k<n;k++)
            {
            IndexOutIn oldIOI = (IndexOutIn)ioiIterator.next();
            int index = oldIOI.index;
            Bag copyOutBag = oldIOI.out==null?new Bag():new Bag(oldIOI.out.numObjs);
            Bag copyInBag = directed? (oldIOI.in==null?new Bag():new Bag(oldIOI.in.numObjs)):copyOutBag;
            IndexOutIn clonedIOI = new IndexOutIn( oldIOI.index, copyOutBag, copyInBag);
            clone.indexOutInHash.put( allNodes.objs[index], clonedIOI);
            ioiArray[k]=oldIOI;
            }
        //so far I avoided any resizing.
        //TODO now I could work around addEdge, too.
        //for instance I already now "IndexOutIn oldIOI", no need to hash-table look-up it. 
        for(int k=0;k<n;k++)
            {
            IndexOutIn oldIOI = ioiArray[k];
            Object node_k = allNodes.objs[oldIOI.index];
            if(oldIOI.out!=null)
                for(int i=0;i<oldIOI.out.numObjs;i++)
                    {
                    Edge e = (Edge) oldIOI.out.objs[i];
                    if(directed || e.from==node_k)
                        clone.addEdge(new Edge(e.from, e.to, e.info));
                    }           
            }
        return clone;
        }
//    /**
//     * Probably slightly faster than clone().reverseAllEdges()
//     */
//      public static Network getDualNetwork(final Network network)
//      {
//              if(!network.directed) return network.cloneGraph();
//              Network dual = new Network(true);
//              int n = network.allNodes.numObjs;
//              for(int k=0;k<n;k++)
//                      dual.addNode(network.allNodes.objs[k]);
//              Iterator i = network.indexOutInHash.values().iterator();
//              for(int k=0;k<n;k++)
//              {
//                      Network.IndexOutIn ioi= (Network.IndexOutIn)i.next();
//                      Bag out =ioi.out;
//                      if(out==null) 
//                              continue;
//                      for(int j=0;j<out.numObjs;j++)
//                      {
//                              Edge e = (Edge)out.objs[j];
//                              dual.addEdge(new Edge(e.to, e.from, e.info));
//                      }
//              }
//              return dual;
//      }
//      public static void compareDual(final Network net)
//      {
//              int iterations = 500000;
//              long t0 = System.currentTimeMillis();
//              for(int i=0;i<iterations;i++)
//                      getDualNetwork(net);
//              System.out.println("getDualNetwork = "+(System.currentTimeMillis() -t0));
//      
//              t0 = System.currentTimeMillis();
//              for(int i=0;i<iterations;i++)
//              {
//                      net.reverseAllEdges();
//                      
//                      net.reverseAllEdges();
//              }               
//              System.out.println("reverseAllEdges x2 =  "+(System.currentTimeMillis() -t0));
//      
//              t0 = System.currentTimeMillis();
//              for(int i=0;i<iterations;i++)
//              {
//                      net.cloneGraph().reverseAllEdges();
//              }               
//              System.out.println("clone + reverseAllEdges =  "+(System.currentTimeMillis() -t0));
//      }

    /**
     * Complements the graph: same nodes, no edges were they were, edges where they were not.
     * 
     * An advantage over calling addNode and addEdge n and m times, 
     * is to allocate the Bags the right size the first time.
     */
    public Network getGraphComplement(boolean allowSelfLoops)
        {
        Network complement = new Network(directed);
        complement.allNodes.addAll(allNodes);
        int n = allNodes.numObjs;

        Iterator ioiIterator = indexOutInHash.values().iterator();
        Network.IndexOutIn[] ioiArray = new Network.IndexOutIn[n];
        int maxDegree = n-1+(allowSelfLoops?1:0);
        
        for(int k=0;k<n;k++)
            {
            Network.IndexOutIn oldIOI = (Network.IndexOutIn)ioiIterator.next();
            int index = oldIOI.index;
            //TODO if i am multigraph, oldIOI.out.numObjs might be bigger than n, 
            //so that's how you get it to bomb on your hands.
            Bag newOutBag = oldIOI.out==null?
                new Bag(maxDegree):
                new Bag(maxDegree-oldIOI.out.numObjs);
            Bag newInBag = (!directed)? 
                newOutBag:
            (oldIOI.in==null?
             new Bag(maxDegree):
             new Bag(maxDegree-oldIOI.in.numObjs));
            Network.IndexOutIn clonedIOI = new Network.IndexOutIn( oldIOI.index, newOutBag, newInBag);
            complement.indexOutInHash.put( allNodes.objs[index], clonedIOI);
            //so far I avoided any resizing.
            ioiArray[k]=oldIOI;
            }
        //TODO now I could work around addEdge, too.
        //for instance I already now "IndexOutIn oldIOI", no need to hash-table look-up it. 
        boolean[] edgeArray = new boolean[n];
        for(int k=0;k<n;k++)
            {
            Network.IndexOutIn oldIOI = ioiArray[k];
            int nodeIndex = oldIOI.index;
            Object nodeObj = allNodes.objs[nodeIndex];
            for(int i=0;i<n;i++) edgeArray[i]=true;
            if(!allowSelfLoops) edgeArray[nodeIndex]= false;
                
            if(oldIOI.out!=null)
                for(int i=0;i<oldIOI.out.numObjs;i++)
                    {
                    Edge e = (Edge) oldIOI.out.objs[i];
                    Object otherNode = e.getOtherNode(nodeObj);
                    int otherIndex = getNodeIndex(otherNode);
                    edgeArray[otherIndex]=false;
                    }
                
            for(int i=0;i<n;i++) 
                if(edgeArray[i] && (directed || nodeIndex<=i))
                    complement.addEdge(nodeObj,allNodes.objs[i], null);
            }
        return complement;
        }       

    }