Cytoscape 2.8.0 API

cytoscape.graph.dynamic.util
Class DynamicGraphFactory

java.lang.Object
  extended by cytoscape.graph.dynamic.util.DynamicGraphFactory

public final class DynamicGraphFactory
extends Object

A factory for getting cytoscape.graph.dynamic.DynamicGraph instances. This DynamicGraph implementation requires a bare minimum of roughly 64 megabytes for a graph with one million edges and one hundred thousand nodes. That is, the memory requirements are roughly 64 bytes per node and edge.

Nodes and edges created by the returned DynamicGraph are strictly less than Integer.MAX_VALUE. This implementation of DynamicGraph has been coded to assume that graphs containing Integer.MAX_VALUE number of nodes and Integer.MAX_VALUE number of edges will be created; however, due to lack of sufficient memory in available hardware, such large graphs have not [yet] been tested using this implementation.

This implementation of DynamicGraph creates nodes and edges with small integer values. This implementation re-uses node and edge values as nodes and edges are removed and added. Thus, nodes and edges will not take ever-increasing values if they are continually being removed and added.

The returned DynamicGraph does not free up memory. That is, if a DynamicGraph contains one million edges and one hundred thousand nodes, it consumes roughly 64 megabytes. If all nodes and edges are then removed from the DynamicGraph, it will still consume roughly 64 megabytes of memory. If one hundred thousand nodes and one million edges are then created, the DynamicGraph will still consume roughly 64 megabytes of memory. If all nodes and edges are removed and then re-created, repeatedly over an infinite number of iterations, the overall memory consumption required by this DynamicGraph will remain constant.

The DynamicGraph instances generated by this factory implement the java.io.Serializable interface. However, do not use the serialization facility to store graphs in a persistent manner because the serialization in this graph implementation does not handle versioning; if the class structure of the graph implementation changes (due to bug fixes or performance optimizations, for example), graphs serialized and saved from the old class definition will fail to be loaded by the new class definition.

Below are time complexities of DynamicGraph methods:

DynamicGraph methodtime complexity
nodes() An IntEnumerator is returned in constant time. The enumerator returns each successive element in constant time. The enumerator reports the number of elements remaining in constant time.
edges() An IntEnumerator is returned in constant time. The enumerator returns each successive element in constant time. The enumerator reports the number of elements remaining in constant time.
nodeCreate() A node is created in amortized constant time. Amortized because doubling the size of an underlying array will be necessary as the DynamicGraph increases in its total node count.
nodeRemove(int) A node is removed in O(E) time, where E is the number of edges touching the node being removed.
edgeCreate(int, int, boolean) An edge is created in amortized constant time. Amortized because doubling the size of an underlying array will be necessary as the DynamicGraph increases in its total edge count.
edgeRemove(int) An edge is removed in constant time.
nodeExists(int) The existence of a node is determined in constant time.
edgeType(int) The existence/type of an edge is determined in constant time.
edgeSource(int) The source node of an edge is determined in constant time.
edgeTarget(int) The target node of an edge is determined in constant time.
edgesAdjacent(int, boolean, boolean, boolean) An IntEnumerator is returned in constant time. The enumerator always reports the number of elements remaining in constant time. The enumeration can be completely traversed in O(E) time, where E is the number of edges touching the node in question. Each individual successive element is returned by the enumeration in average O(E/F) time, where F is the total number of elements in this enumeration.
edgesConnecting(int, int, boolean, boolean, boolean) An IntIterator is returned in constant time. The iteration can be completely traversed in O(min(E, F)) time, where E is the total number of edges touching one node and F is the total number of edges touching the other node.


Method Summary
static DynamicGraph instantiateDynamicGraph()
          Returns a new instance of DynamicGraph with every invocation.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

instantiateDynamicGraph

public static DynamicGraph instantiateDynamicGraph()
Returns a new instance of DynamicGraph with every invocation.


Cytoscape 2.8.0 API

Copyright 2010 Cytoscape Consortium. All rights reserved.