diva.pod.lwgraph
Class LightweightGraph

java.lang.Object
  extended by diva.pod.lwgraph.LightweightGraph
Direct Known Subclasses:
LightweightNetwork

public class LightweightGraph
extends Object

A light-weight graph data structure. This class requires only that clients implement two very simple interfaces, LWNode and LWEdge (or use the basic implementations provided in this package). Clients add nodes to the graph, and connect them. Clients that want to connect to "ports" on components should use the LightweightNetwork class instead. Clients that want a very fast and compact graph representation should use the low-level classes Topology and Traversal.

Light-weight graphs are hierarchical, in a very simple (and light-weight!) way. Every node can have a "parent" node set for it. Some methods are provided for iterating through the "children" of a given node. Clients that want more complicated or rigid notions of containment can implement it over the top of this API.

Version:
$Revision: 1.10 $
Author:
John Reekie

Nested Class Summary
 class LightweightGraph.TraversalIterator
          The iterator class that is used to iterate over integer arrays of things and map them into objects.
 
Constructor Summary
LightweightGraph()
          Create a new, empty, light-weight graph
 
Method Summary
 void addEdge(LWEdge edge)
          Add an edge object to the graph.
 void addNode(LWNode node)
          Add a node object to the graph
 void cacheTraversal()
          Reconstruct the cache of the topology (this is contained in a pair of Traversal objects).
 void connect(LWEdge edge, LWNode tail, LWNode head)
          Connect the given tail and head nodes using the given edge.
 Iterator edges()
          Return an iterator over the edges of the graph.
 LWEdge getEdge(int edgeid)
          Get the edge with the given id, or null if the edge does not exist.
 int getEdgeCount()
          Get the number of edges in this graph
 LWNode getHeadNode(LWEdge edge)
          Get the head node of the given edge
 LWNode getNode(int nodeid)
          Get the node with the given id, or null if the edge does not exist.
 int getNodeCount()
          Get the number of nodes in this graph
 LWNode getParent(LWNode node)
          Get the parent node of the given node, or null if the node has no parent (ie is at the root level of the graph).
 LWNode getTailNode(LWEdge edge)
          Get the tail node of the given edge
 Topology getTopology()
          Get the topology used by this graph.
 Iterator inEdges(LWNode node)
          Return an iterator over the edges into the given node.
 void invalidateCache()
          Invalidate the cache of the topology.
 Iterator nodes()
          Return an iterator over the nodes of the graph.
 Iterator nodes(LWNode parent)
          Return an iterator over the nodes that are children of the given node.
 Iterator outEdges(LWNode node)
          Return an iterator over the edges out of the given node.
 Iterator predecessors(LWNode node)
          Return an iterator over the predecessors of the given node.
 void removeEdge(LWEdge edge)
          Remove the given edge.
 void removeNode(LWNode node)
          Remove the given node.
 Iterator roots()
          Return an iterator over the root nodes of the graph.
 void setHeadNode(LWEdge edge, LWNode head)
          Set the head node of the given edge.
 void setParent(LWNode node, LWNode parent)
          Set the parent node of the given node.
 void setTailNode(LWEdge edge, LWNode tail)
          Set the tail node of the given edge.
 Iterator successors(LWNode node)
          Return an iterator over the successors of the given node.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

LightweightGraph

public LightweightGraph()
Create a new, empty, light-weight graph

Method Detail

addEdge

public void addEdge(LWEdge edge)
Add an edge object to the graph.


addNode

public void addNode(LWNode node)
Add a node object to the graph


cacheTraversal

public void cacheTraversal()
Reconstruct the cache of the topology (this is contained in a pair of Traversal objects). This method is automatically called by methods of this class when necessary, so it should not be necessary for the client to call it.


connect

public void connect(LWEdge edge,
                    LWNode tail,
                    LWNode head)
Connect the given tail and head nodes using the given edge. The nodes must have been added to this graph previously with the addNode() method. The edge must have previously been added to the graph with the addEdge() method. The same two nodes can be connected by more than one edge. The head and tail nodes cannot be null; if you wish to connect just one end of the edge, use the setHead() or setTail() method


edges

public Iterator edges()
Return an iterator over the edges of the graph. The remove() method is supported, and is equivalent to calling removeEdge() on the current edge. Removing edges by any other means while in an iterator is a very bad idea.


getEdge

public LWEdge getEdge(int edgeid)
Get the edge with the given id, or null if the edge does not exist.


getEdgeCount

public int getEdgeCount()
Get the number of edges in this graph


getHeadNode

public LWNode getHeadNode(LWEdge edge)
Get the head node of the given edge


getTopology

public Topology getTopology()
Get the topology used by this graph.


getNode

public LWNode getNode(int nodeid)
Get the node with the given id, or null if the edge does not exist.


getNodeCount

public int getNodeCount()
Get the number of nodes in this graph


getParent

public LWNode getParent(LWNode node)
Get the parent node of the given node, or null if the node has no parent (ie is at the root level of the graph).


getTailNode

public LWNode getTailNode(LWEdge edge)
Get the tail node of the given edge


inEdges

public Iterator inEdges(LWNode node)
Return an iterator over the edges into the given node.


invalidateCache

public void invalidateCache()
Invalidate the cache of the topology. This method is automatically called by methods of this class when necessary, so it should not be necessary for the client to call it.


nodes

public Iterator nodes()
Return an iterator over the nodes of the graph. The remove() method is supported, and is equivalent to calling removeNode() on the most recently returned node. Removing nodes by any other means while in an iterator is not a good idea.


nodes

public Iterator nodes(LWNode parent)
Return an iterator over the nodes that are children of the given node. The remove() method is supported, and is equivalent to calling setParent(null) on the most recently returned node. NOTE: it does not remove the node from the graph!


outEdges

public Iterator outEdges(LWNode node)
Return an iterator over the edges out of the given node.


predecessors

public Iterator predecessors(LWNode node)
Return an iterator over the predecessors of the given node.


removeEdge

public void removeEdge(LWEdge edge)
Remove the given edge. Will throw an exception of the edge is not in this graph. The edge will of course be disconnected as well as being removed from the graph.


removeNode

public void removeNode(LWNode node)
Remove the given node. Connected edges will not be affected, it is the client's responsibility to disconnect edges before calling this method. Will throw an exception of the node is not in this graph.


roots

public Iterator roots()
Return an iterator over the root nodes of the graph. (Where a root is a node that has no predecessor.)


setHeadNode

public void setHeadNode(LWEdge edge,
                        LWNode head)
Set the head node of the given edge. If the edge is unknown to this graph, it will be added to it. To disconnect the edge from the node, set the node to null.


setParent

public void setParent(LWNode node,
                      LWNode parent)
Set the parent node of the given node. Both nodes must have previously been added to the graph.


setTailNode

public void setTailNode(LWEdge edge,
                        LWNode tail)
Set the tail node of the given edge. If the edge is unknown to this graph, it will be added to it. To disconnect the edge from the node, set the node to null.


successors

public Iterator successors(LWNode node)
Return an iterator over the successors of the given node.



Copyright © 2015 Central Laboratory of the Research Councils. All Rights Reserved.