network.java

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

package sim.field.network;
import sim.util.*;
import java.util.*;

/** The Network is a field which stores binary graph and multigraph structures of all kinds, using hash tables to allow
    reasonably rapid dynamic modification.
    
    <p>The nodes of a Network's graph can be any arbitrary, properly hashable object.  The edges of the
    graph are members of the Edge class.  This class is little more than a wrapper around arbitrary object as well (the Edge's 'info'
    object).  Thus your graph's nodes and edges can essentially be objects entirely of your choosing.
    
    <p>Edge objects also contain pointers to the Nodes that they are to and from (plus some auxillary index information
    for speed).
    
    <p>Nodes and Edges are stored in the Network using two data structures: a Bag containing all the nodes in the Field;
    and a HashMap which maps each Node to a container holding the Node's index in the Bag, plus a Bag of the Node's outgoing
    Edges and a Bag of the Node's incoming Edges.  Ordinarily you won't fool with these structures other than to scan through
    them (in particular, to scan rapidly through the allNodes bag rather than use an iterator).
    
    <p>To add a node to the Network, simply use addNode(node).  To remove a node, use removeNode(node).
    To add an edge to the Network, use addEdge(fromNode,toNode,edgeInfoObject), where edgeInfoObject is your
    arbitrary edge object. Alternatively, you can make an Edge object from scratch and add it with addEdge(new Edge(fromNode, toNode, edgeInfoObject)).
    You remove edges with removeEdge(edge).  If you add an edge, and its nodes have not been added yet, they will
    automatically be added as well.
    
    <p>Traversing a Network is easy.  
    To get a Bag of all the incoming (or outgoing) Edges to a node, use getEdgesIn(node) or getEdgesOut(node).
    Do <b>not</b> add or remove Edges from this Bag -- it's used internally and we trust you here.  Also don't expect the
    Bag to not change its values mysteriously later on.  Make a copy of the Bag if you want to keep it and/or modify it.
    Once you have an Edge, you can call its to() method and from() methods to get the nodes it's from and to, and you can
    at any time get and modify its info object.  The to() and from() are fast and inlined.
    
    <p>However, the getEdgesIn(node) and getEdgesOut(node) methods are not super fast: they require a hash lookup.  If you
    are planning on applying an algorithm on the Network which doesn't change the topology at all but traverses it a lot
    and changes just the <b>contents</b> of the edge info objects and the node object contents, you might consider first 
    getting an adjacency list for the Network with getAdjacencyList(...), or an adjacency matrix with getAdjacencyMatrix(...)
    or getMultigraphAdjacencyMatrix(...).  But remember that as soon as the topology changes (adding/deleting a node or edge),
    the adjacency list is invalid, and you need to request another one.
    
    <p><b>Computational Complexity.</b>  Adding a node or an edge is O(1).  Removing an edge is O(1).  Removing a node is O(m), where
    m is the total number of edges in and out of the node.  Removing all nodes is O(1) and fast.  Getting the in-edges or out-edges for a node
    is O(1).  Getting the to or from node for an edge is O(1) and fast.
    
    <p><b>Warning About Hashing.</b>  Java's hashing method is broken in an important way.  One can override the hashCode() and equals()
    methods of an object so that they hash by the value of an object rather than just the pointer to it.  But if this is done, then if
    you use this object as a key in a hash table, then <i>change</i> those values in the object, it will break the hash table -- the key
    and the object hashed by it will both be lost in the hashtable, unable to be accessed or removed from it.  The moral of the story is:
    do not override hashCode() and equals() to hash by value unless your object is <i>immutable</i> -- its values cannot be changed.  This
    is the case, for example, with Strings, which hash by value but cannot be modified.  It's also the case with Int2D, Int3D, Double2D,
    and Double3D, as well as Double, Integer, etc.  Some of Sun's own objects are broken in this respect: Point, Point2D, etc. are both
    mutable <i>and</i> hashed by value.
    
    <p>This affects you in only one way in a Network: edges are hashed by nodes.  The Network permits you to use any object
    as a node -- but you have been suitably warned: if you use a mutable but hashed-by-value node object, do NOT modify its values while
    it's being used as a key in the Network.
    
    <p><b>Directed vs. Undirected Graphs.</b>  Networks are constructed to be either directed or undirected, and they cannot be changed
    afterwards.  If the network is directed, then an Edge's to() and from() nodes have explicit meaning: the Edge goes from() one node to()
    another.  If the network is undirected, then to() and from() are simply the two nodes at each end of the Edge with no special meaning,
    though they're always consistent.  The convenience method <i>edge</i>.getOtherNode(<i>node</i>) will provide "other" node (if node is to(),
    then from() is returned, and vice versa).  This is particularly useful in undirected graphs where you could be entering an edge as to()
    or as from() and you just want to know what the node on the other end of the edge is.
        
    <p>There are three methods for getting all the edges attached to a node: getEdgesIn(), getEdgesOut(), and the less efficient getEdges().  These methods
    work differently depending on whether or not the network is directed:
        
    <p><table width="100%" border=0>
    <tr><td><td><b>Directed</b><td><b>Undirected</b>
    <tr><td><b>getEdgesIn()</b><td>Bag&nbsp;of&nbsp;incoming&nbsp;edges<td>Bag&nbsp;of&nbsp;all&nbsp;edges
    <tr><td><b>getEdgesOut()</b><td>Bag&nbsp;of&nbsp;outgoing&nbsp;edges<td>Bag&nbsp;of&nbsp;all&nbsp;edges
    <tr><td><b>getEdges()</b><td><i>Modifiable</i>&nbsp;Bag&nbsp;of&nbsp;all&nbsp;edges<td><i>Modifiable</i>&nbsp;Bag&nbsp;of&nbsp;all&nbsp;edges
    </table>
        
    <p><b>Hypergraphs.</b> Network is binary.  In the future we may provide a Hypergraph facility if it's needed, but for now you'll
    need to make "multi-edge nodes" and store them in the field, then hook them to your nodes via Edges.  For example, to store the
    relationship foo(node1, node2, node3), here's one way to do it:
    <ol>
    <li>Make a special foo object.
    <li>field.addEdge(foo,node1,new Double(0));
    <li>field.addEdge(foo,node2,new Double(1));
    <li>field.addEdge(foo,node3,new Double(2));
    </ol>
*/

public class Network implements java.io.Serializable
    {
    final public boolean directed;
    
    /** Constructs a directed or undirected graph. */
    public Network(boolean directed){this.directed = directed;  }

    /** Constructs a directed graph */
    public Network(){this(true); }
    
        
    /** Hashes Network.IndexInOut structures by Node.  These structures
        contain the incoming edges of the Node, its outgoing edges, and the index of
        the Node in the allNodes bag. */
    public HashMap indexOutInHash = new HashMap();

    // perhaps rather than using a bag we should use an edge array... it'd be faster...
    /** All the objects in the sparse field.  For fast scans.  Do not rely on this bag always being the same object. */
    public Bag allNodes = new Bag();
        
    // returned instead of null for those methods which require a guarantee that the returned Bag should never be touched.
    final Bag emptyBag = new Bag();

    /** Creates and returns an adjacency list.  If you're doing lots of operations (especially network traversals)
        which won't effect the topology of the network, an adjacency list structure might be more efficient for you to access rather than lots of
        calls to getEdgesIn() and getEdgesOut() etc.  Building the list is an O(#edges) operation.
        
        <p>The adjacency list is an array of Edge arrays.  Each edge array holds all outgoing edges from a node
        (if outEdges is true -- otherwise it's the incoming edges to the node).  The edge arrays are ordered in
        their parent array in the same order that the corresponding nodes are ordered in the allNodes bag.
           
        <p>As soon as you modify any part of the Network's topology (through addEdge(), addNode(), removeEdge(),
        removeNode(), removeAllNodes(), etc.), the adjacency list data is invalid and should not be used.  Instead, request
        a new adjacency list. 
        
        <p>You can modify these edge arrays any way you like, though the Edge objects are the actual Edges.
    */
    public Edge[][] getAdjacencyList(boolean outEdges)
        {
        final Edge[][] list = new Edge[allNodes.numObjs][];
        for(int x=0;x<allNodes.numObjs;x++)
            {
            // load each list slot with an array consisting of all in or out edges for the node
            final Bag edges = 
                (outEdges ? getEdgesOut(allNodes.objs[x]) : getEdgesIn(allNodes.objs[x]));
            list[x] = new Edge[edges.numObjs];
            final Edge[] l = list[x];  // a little faster, one less level of indirection
            final int n = edges.numObjs;  // likewiswe
            final Object[] objs = edges.objs; // likewise
            System.arraycopy(objs,0,l,0,n); // I don't know if this is faster or not, given the type mismatch -- Sean
            /*            for(int y=0;y<n;y++)
                          l[y] = (Edge)(objs[y]);  // hmmm, can we do an array copy across array types?
            */
            }
        return list;
        }
        
    /** Creates and returns a simple adjacency matrix, where only one edge between any two nodes is considered -- if you're
        using a multigraph, use getMultigraphAdjacencyMatrix() instead.  If you're doing lots of operations (especially network traversals)
        which won't effect the topology of the network, an adjacency matrix structure might be more efficient for you to access rather than lots of
        calls to getEdgesIn() and getEdgesOut() etc.  Building the matrix is an O(#edges + #nodes^2) operation.
        
        <p>The adjacency matrix is a two-dimensional array of Edges, each dimension as long as the number of nodes in the graph.
        Each entry in the array is either an Edge FROM a node TO another, or it is null (if there is no such edge).  If there are multiple
        edges between any two nodes, an arbitrary one is chosen.  The Edge array returned is organized as Edge[FROM][TO].
        The indices are ordered in the same order that the corresponding nodes are ordered in the allNodes bag.
           
        <p>As soon as you modify any part of the Network's topology (through addEdge(), addNode(), removeEdge(),
        removeNode(), removeAllNodes(), etc.), the adjacency matrix data is invalid and should not be used.  Instead, request
        a new adjacency matrix. 
        
        <p>You can modify the array returned any way you like, though the Edge objects are the actual Edges.
    */
    public Edge[][] getAdjacencyMatrix()
        {
        final int n = allNodes.numObjs;
        final Edge[][] matrix = new Edge[n][n];   // I assume it filled with nulls?

        Iterator nodeIO = indexOutInHash.values().iterator();
        while(nodeIO.hasNext()) // this replaces n hash lookups with n class casts
            {
            IndexOutIn ioi = (IndexOutIn)nodeIO.next();
            if(ioi.out==null) continue;
            int outDegree = ioi.out.numObjs;
            Edge[] outEdges = matrix[ioi.index];
            Object sourceNode =  allNodes.objs[ioi.index];
                        
            for(int i=0;i<outDegree;i++)
                {
                Edge e = (Edge)ioi.out.objs[i];
                // this is getNodeIndex without the function call
                outEdges[((IndexOutIn)indexOutInHash.get(e.getOtherNode(sourceNode))).index] = e;
                }
            }
        return matrix;
        }
        
    /** Creates and returns a multigraph adjacency matrix, which includes all edges from a given node to another -- if you know for sure
        that you have a simple graph (no multiple edges between two nodes), use getAdjacencyMatrix instead.  
        If you're doing lots of operations (especially network traversals) which won't effect the topology of the network, an 
        adjacency matrix structure might be more efficient for you to access rather than lots of calls to getEdgesIn() and 
        getEdgesOut() etc.  Building the matrix is expensive: it's an O(#edges + #nodes^2) operation.
        
        <p>The adjacency matrix is a two-dimensional array of Edge arrays, both of the dimensions as long as the number of nodes in the graph.
        Each entry in this two-dimensional array is an <b>array</b> of all edges FROM a node TO another.  Thus the
        returned array structure is organized as Edge[FROM][TO][EDGES].
        The FROM and TO indices are ordered in the same order that the corresponding nodes are ordered in the allNodes bag.
    
        <p>Important note: if there are <i>no</i> edges FROM a given node TO another, an empty array is placed in that entry.
        For efficiency's sake, the <i>same</i> empty array is used.  Thus you should not assume that you can compare edge arrays
        for equality (an unlikely event anyway). 
                                         
        <p>As soon as you modify any part of the Network's topology (through addEdge(), addNode(), removeEdge(),
        removeNode(), removeAllNodes(), etc.), the adjacency matrix data is invalid and should not be used.  Instead, request
        a new adjacency matrix. 
        
        <p>You can modify the array returned any way you like, though the Edge objects are the actual Edges.
    */
    public Edge[][][] getMultigraphAdjacencyMatrix()
        {
        final int n = allNodes.numObjs;
        final Edge[][][] matrix = new Edge[n][n][]; //I assume it filled with nulls?

        Iterator nodeIO = indexOutInHash.values().iterator();
        Bag[] tmp  = new Bag[n];
        for(int i=0; i<n;i++)
            tmp[i]=new Bag(n);
                        
        while(nodeIO.hasNext()) // this replaces n hash lookups with n class casts
            {
            IndexOutIn ioi = (IndexOutIn)nodeIO.next();
            if(ioi.out==null) continue;
            int outDegree = ioi.out.numObjs;
            Object sourceNode =  allNodes.objs[ioi.index];

            for(int i=0;i<outDegree;i++)
                {
                Edge e = (Edge)ioi.out.objs[i];
                //this is getNodeIndex without the function call
                int j = ((IndexOutIn)indexOutInHash.get(e.getOtherNode(sourceNode))).index;
                tmp[j].add(e);
                }       
                        
            Edge[][] outEdges = matrix[ioi.index];
            for(int i=0;i<n;i++)
                {
                Bag b = tmp[i];
                int ne = b.numObjs;
                outEdges[i]=new Edge[ne];
                if(ne>0)
                    {
                    System.arraycopy(b.objs,0,outEdges[i], 0, ne );
                    b.clear();
                    }
                }       
            }
        //now the nodes with 0 out-degree have a row full of nulls in the matrix
        for(int i=0;i<n;i++)
            {
            Edge[][] e2 = matrix[i];
            if(e2[0]==null)
                for(int j=0;j<n;j++)
                    e2[j]=emptyEdgeArray;
            }
                 
        return matrix;
        }
        
    static Edge[] emptyEdgeArray = new Edge[0];

//TODO do I want to use this? (ask liviu too)