Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## sim.field.network
Class NetworkField

    java.lang.Object
      sim.field.network.NetworkField

All Implemented Interfaces:
  java.io.Serializable

public class NetworkField
extends java.lang.Object
implements java.io.Serializable

The NetworkField is a field which stores binary graph structures of all kinds, using hash tables to allow reasonably rapid dynamic modification.

The nodes of a NetworkField'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.

Edge objects also contain pointers to the Nodes that they are to and from (plus some auxillary index information for speed).

Nodes and Edges are stored in the NetworkField 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).

To add a node to the NetworkField, simply use addNode(node). To remove a node, use removeNode(node). To add an edge to the NetworkField, 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.

Traversing a NetworkField is easy. To get a Bag of all the incoming (or outgoing) Edges to a node, use getEdgesIn(node) or getEdgesOut(node). Do not 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.

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 NetworkField which doesn't change the topology at all but traverses it a lot and changes just the contents of the edge info objects and the node object contents, you might consider first getting an adjacency list for the NetworkField with getAdjacencyList(...). This gives you a fast double array of edges that you can use to do rapid traversal algorithms. 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.

Computational Complexity. 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.

Warning About Hashing. 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 change 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 immutable -- 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 and hashed by value.

This affects you in only one way in a NewtworkField: edges are hashed by nodes. The NetworkField 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 NetworkField.

Undirected Graphs. NetworkField is directed. If you need undirected graphs, you have two choices. Either you can store TWO edges between your nodes (one from->to, the other to->from). We don't suggest this approach. Or you just designate an arbitrary ordering between the edges. In this case, to get all the edges attached to a node, remember to check BOTH its incoming edges AND its outgoing edges.

Multigraphs. NetworkField is binary. In the future we may provide a Multigraph 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:

1. Make a special foo object.
2. field.addEdge(foo,node1,new Double(0));
3. field.addEdge(foo,node2,new Double(1));
4. field.addEdge(foo,node3,new Double(2));

See Also:
  Serialized Form

Nested Class Summary
`static class` | `NetworkField.IndexOutIn` The structure stored in the indexOutInHash hash table.

Field Summary
`Bag` | `allNodes` All the objects in the sparse field.
`java.util.HashMap` | `indexOutInHash` Hashes NetworkField.IndexInOut structures by Node.

Constructor Summary
`NetworkField()`

Method Summary
`void` | `addEdge(Edge edge)` Add an edge.
`void` | `addEdge(java.lang.Object from, java.lang.Object to, java.lang.Object info)` Add an edge, storing info as the edge's associated information object.
`void` | `addNode(java.lang.Object node)` Add a node
`Bag` | `clear()` Removes all nodes, deleting all edges from the Field as well.
`Edge[][]` | `getAdjacencyList(boolean outEdges)` Creates and returns an adjacency list.
`Bag` | `getAllNodes()` Returns all the objects in the Sparse Field.
`Bag` | `getEdgesIn(java.lang.Object node)` Get all edges that enter a node.
`Bag` | `getEdgesOut(java.lang.Object node)` Get all edges that leave a node.
`java.util.Iterator` | `iterator()` Iterates over all objects.
`Bag` | `removeAllNodes()` Synonym for clear(), here only for backward-compatibility.
`Edge` | `removeEdge(Edge edge)` Removes an edge and returns it.
`java.lang.Object` | `removeNode(java.lang.Object node)` Removes a node, deleting all incoming and outgoing edges from the Field as well.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### indexOutInHash

    public java.util.HashMap indexOutInHash

  Hashes NetworkField.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.

### allNodes

    public Bag allNodes

  All the objects in the sparse field. For fast scans. Do not rely on this bag always being the same object.

Constructor Detail

### NetworkField

    public NetworkField()

Method Detail

### getAdjacencyList

    public Edge[][] getAdjacencyList(boolean outEdges)

  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.

  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.

  As soon as you modify any part of the NetworkField'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.

  You can modify these edge arrays any way you like -- they're not used internally..

### getEdgesOut

    public Bag getEdgesOut(java.lang.Object node)

  Get all edges that leave a node. Returns null if there is no such node in the field. Do not modify this Bag -- it is used internally.

### getEdgesIn

    public Bag getEdgesIn(java.lang.Object node)

  Get all edges that enter a node. Returns null if there is no such node in the field. Do not modify this Bag -- it is used internally.

### addNode

    public void addNode(java.lang.Object node)

  Add a node

### addEdge

    public void addEdge(java.lang.Object from,
                        java.lang.Object to,
                        java.lang.Object info)

  Add an edge, storing info as the edge's associated information object. If you add an edge, and its nodes have not been added yet, they will automatically be added as well.

### addEdge

    public void addEdge(Edge edge)

  Add an edge. If you add an edge, and its nodes have not been added yet, they will automatically be added as well. Throws an exception if the edge is null or if it's already added to a Field (including this one).

### removeEdge

    public Edge removeEdge(Edge edge)

  Removes an edge and returns it. The edge will still retain its info, to, and from fields, so you can add it again with addEdge. Returns null if the edge is null or if there is no such edge added to the field.

### removeNode

    public java.lang.Object removeNode(java.lang.Object node)

  Removes a node, deleting all incoming and outgoing edges from the Field as well. Returns the node, or null if there is no such node in the field.

### clear

    public Bag clear()

  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 NetworkField.

### removeAllNodes

    public Bag removeAllNodes()

  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 NetworkField.

### getAllNodes

    public Bag getAllNodes()

  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 new Bag(foo.getallNodes()).

### iterator

    public java.util.Iterator iterator()

  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:

  `for(int x=0;x`

  ... but do NOT modify the allNodes.objs array.

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD