org.graffiti.graph
Class FastGraph

java.lang.Object
  extended by org.graffiti.attributes.AbstractAttributable
      extended by org.graffiti.graph.AbstractGraph
          extended by org.graffiti.graph.FastGraph
All Implemented Interfaces:
Attributable, DeepCopy, Graph

public class FastGraph
extends AbstractGraph

An adjacency list implementation of the Graph interface tuned for speed (not for size!). AbstractGraph.addNode(), AbstractGraph.addEdge(Node, Node, boolean), and AbstractGraph.deleteEdge(Edge) run in constant time. AbstractGraph.deleteNode(Node) needs linear time in the node degree. Any iteration step in any of the supported iterations has constant complexity.

Version:
$Revision: 5767 $ $Date: 2006-01-26 10:09:40 +0100 (Do, 26 Jan 2006) $
Author:
forster
See Also:
FastNode, FastEdge

Field Summary
(package private)  int numberOfDirectedEdges
          The number of directed edges contained in the graph.
 
Fields inherited from class org.graffiti.graph.AbstractGraph
attTypesManager, defaultDirectedEdgeAttribute, defaultGraphAttribute, defaultNodeAttribute, defaultUndirectedEdgeAttribute, listenerManager
 
Fields inherited from class org.graffiti.attributes.AbstractAttributable
attributes
 
Constructor Summary
FastGraph()
          Creates a new graph.
FastGraph(CollectionAttribute attributes)
          Creates a new graph with a given set of attributes.
 
Method Summary
 Object copy()
          Returns a deep copy of this object.
 Edge createEdge(Node source, Node target, boolean directed, CollectionAttribute attribute)
          Creates a new Edge without actually adding it to the Graph.
(package private)  Node createNode()
          Creates a new Node.
 Node createNode(CollectionAttribute attribute)
          Creates a new Node that is initialize with the given CollectionAttribute.
protected  Edge doAddEdge(Node source, Node target, boolean directed, CollectionAttribute col)
          Adds a new edge to the current graph.
protected  void doAddNode(Node node)
          Adds the node to the graph.
protected  void doClear()
          Deletes the current graph by resetting all its attributes.
protected  void doDeleteEdge(Edge e)
          Deletes the given edge from the current graph.
protected  void doDeleteNode(Node n)
          Deletes the given node.
 Collection<Edge> getEdges()
          Returns all edges of the graph.
 List<Node> getNodes()
          Returns a list containing a copy of the node list of the graph.
 Iterator<Node> getNodesIterator()
          Returns an iterator over the nodes of the graph.
 int getNumberOfDirectedEdges()
          Returns the number of directed edges of the graph.
 boolean isModified()
          Indicates whether the Graph has been modified.
 void setModified(boolean modified)
          Should be set to False after saving changes and to True after making changes to the Graph.
 
Methods inherited from class org.graffiti.graph.AbstractGraph
addAttributeConsumer, addEdge, addEdge, addEdgeCopy, addGraph, addNode, addNode, addNodeCopy, areConnected, clear, containsEdge, containsNode, deleteEdge, deleteNode, doAddEdge, getAttTypesManager, getEdges, getEdgesIterator, getGraphElements, getListenerManager, getNumberOfEdges, getNumberOfNodes, getNumberOfUndirectedEdges, isDirected, isEmpty, isUndirected, removeAttributeConsumer, setDirected, setDirected
 
Methods inherited from class org.graffiti.attributes.AbstractAttributable
addAttribute, addBoolean, addByte, addDouble, addFloat, addInteger, addLong, addShort, addString, changeBoolean, changeByte, changeDouble, changeFloat, changeInteger, changeLong, changeShort, changeString, containsAttribute, getAttribute, getAttributes, getBoolean, getByte, getDouble, getFloat, getInteger, getLong, getShort, getString, removeAttribute, setBoolean, setByte, setDouble, setFloat, setInteger, setLong, setShort, setString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface org.graffiti.attributes.Attributable
addAttribute, addBoolean, addByte, addDouble, addFloat, addInteger, addLong, addShort, addString, changeBoolean, changeByte, changeDouble, changeFloat, changeInteger, changeLong, changeShort, changeString, containsAttribute, getAttribute, getAttributes, getBoolean, getByte, getDouble, getFloat, getInteger, getLong, getShort, getString, removeAttribute, setBoolean, setByte, setDouble, setFloat, setInteger, setLong, setShort, setString
 

Field Detail

numberOfDirectedEdges

int numberOfDirectedEdges
The number of directed edges contained in the graph.

Constructor Detail

FastGraph

public FastGraph()
Creates a new graph.


FastGraph

public FastGraph(CollectionAttribute attributes)
Creates a new graph with a given set of attributes.

Parameters:
attributes - The initial attributes of the graph
Method Detail

copy

public Object copy()
Description copied from interface: DeepCopy
Returns a deep copy of this object.

Returns:
A deep copy of this object.

createEdge

public Edge createEdge(Node source,
                       Node target,
                       boolean directed,
                       CollectionAttribute attribute)
Description copied from interface: Graph
Creates a new Edge without actually adding it to the Graph.

Parameters:
source - source-node
target - target-node
directed - shall the new edge be directed?
attribute - attributes for the new edge
Returns:
the newly created edge

createNode

Node createNode()
Description copied from class: AbstractGraph
Creates a new Node.

Specified by:
createNode in class AbstractGraph
Returns:
the newly created node.

createNode

public Node createNode(CollectionAttribute attribute)
Description copied from class: AbstractGraph
Creates a new Node that is initialize with the given CollectionAttribute.

Specified by:
createNode in interface Graph
Specified by:
createNode in class AbstractGraph
Parameters:
attribute - attributes for the new node
Returns:
the newly created node.

doAddEdge

protected Edge doAddEdge(Node source,
                         Node target,
                         boolean directed,
                         CollectionAttribute col)
                  throws GraphElementNotFoundException
Description copied from class: AbstractGraph
Adds a new edge to the current graph. Informs the ListenerManager about the new node.

Specified by:
doAddEdge in class AbstractGraph
Parameters:
source - the source of the edge to add.
target - the target of the edge to add.
directed - true if the edge shall be directed, false otherwise.
col - the CollectionAttribute with which the edge is initialized.
Returns:
the new edge.
Throws:
GraphElementNotFoundException - if any of the nodes cannot be found in the graph.

doAddNode

protected void doAddNode(Node node)
Description copied from class: AbstractGraph
Adds the node to the graph.

Specified by:
doAddNode in class AbstractGraph
Parameters:
node - the node to add

doClear

protected void doClear()
Description copied from class: AbstractGraph
Deletes the current graph by resetting all its attributes. The graph is then equal to a new generated graph i.e. the list of nodes and edges will be empty.

Specified by:
doClear in class AbstractGraph

doDeleteEdge

protected void doDeleteEdge(Edge e)
                     throws GraphElementNotFoundException
Description copied from class: AbstractGraph
Deletes the given edge from the current graph.

Specified by:
doDeleteEdge in class AbstractGraph
Parameters:
e - the edge to delete.
Throws:
GraphElementNotFoundException - if the edge to delete cannot be found in the graph.

doDeleteNode

protected void doDeleteNode(Node n)
                     throws GraphElementNotFoundException
Description copied from class: AbstractGraph
Deletes the given node. First all in- and out-going edges will be deleted using deleteEdge() and thereby informs the ListenerManager implicitly.

Specified by:
doDeleteNode in class AbstractGraph
Parameters:
n - the node to delete.
Throws:
GraphElementNotFoundException - if the node to delete cannot be found in the graph.

getEdges

public Collection<Edge> getEdges()
Description copied from interface: Graph
Returns all edges of the graph. The returned collection may be unmodifiable and is only valid as long as the graph is not modified.

Specified by:
getEdges in interface Graph
Overrides:
getEdges in class AbstractGraph
Returns:
a list of all edges of the graph.

getNodes

public List<Node> getNodes()
Description copied from class: AbstractGraph
Returns a list containing a copy of the node list of the graph. Removing elements from this collection will have no effect on the graph whereas nodes can be modified.

Specified by:
getNodes in interface Graph
Overrides:
getNodes in class AbstractGraph
Returns:
a new java.util.List containing all the nodes of the graph.

getNodesIterator

public Iterator<Node> getNodesIterator()
Description copied from interface: Graph
Returns an iterator over the nodes of the graph. If the graph is empty an empty iterator will be returned. Note that the iterator is not guaranteed to support the Iterator.remove() operation.

Returns:
an iterator containing the nodes of the graph.

getNumberOfDirectedEdges

public int getNumberOfDirectedEdges()
Description copied from class: AbstractGraph
Returns the number of directed edges of the graph.

Specified by:
getNumberOfDirectedEdges in interface Graph
Overrides:
getNumberOfDirectedEdges in class AbstractGraph
Returns:
the number of directed edges of the graph.

isModified

public boolean isModified()
Description copied from interface: Graph
Indicates whether the Graph has been modified. A call to setModified can change this property to false e.g. after the graph has been saved to disc. Changes to attributes and delete/add commands of nodes and edges should change this property to true.

Returns:
True, if the graph has been modifed, False if not.

setModified

public void setModified(boolean modified)
Description copied from interface: Graph
Should be set to False after saving changes and to True after making changes to the Graph. The add/delete nodes and edges commands as well as the property change methods should set this value to True.

Parameters:
modified - Indicates the new status of this field.


Generated at 2012-05-30 11:00:36 PM CEST