y.base
Class Graph

java.lang.Object
  |
  +--y.base.Graph

All Implemented Interfaces:

GraphInterface

Direct Known Subclasses:

LayoutGraph

public class Graph

extends Object

implements GraphInterface

This class implements a directed graph structure. Basically a directed graph consists of a set of objects called nodes (represented by instances of class Node) and a set of node pairs which are called edges (represented by instances of class Edge).

This class fires notification events that signal structural changes of the graph. Classes that implement the GraphListener interface can be added to this class in order to receive such events.

Field Summary

static int	AFTER Object insertion specifier.
static int	BEFORE Object insertion specifier.
protected Vector	listeners A vector of graph listeners. listeners references null iff no listeners are registered.

Constructor Summary

Graph()
Instantiates an empty Graph.

Graph(Graph argGraph)
Instantiates a new Graph object as a copy of argGraph.

Graph(Graph graph, YCursor subNodes)
Instantiates a new Graph object as a partial copy of the argument graph.

Method Summary

void	addDataProvider(Object providerKey, DataProvider data) Registers the given data provider under the given lookup key.
void	addGraphListener(GraphListener listener) Adds the given graph listener to this graph.
void	changeEdge(Edge e, Edge e1, Edge e2, int d1, int d2) This method redefines the endpoints of e.
void	changeEdge(Edge e, Node newSource, Edge sourceReference, int sourceD, Node newTarget, Edge targetReference, int targetD) This method redefines the endpoints of e.
void	changeEdge(Edge e, Node newSource, Node newTarget) This method redefines the endpoints of e.
void	clear() Removes all nodes and edges from this graph.
boolean	contains(Edge e) Whether or not this graph contains the given edge.
boolean	contains(Node v) Whether or not this graph contains the given node.
boolean	containsEdge(Node source, Node target) Returns whether or not this grpah contains an edge from node source to node target.
Graph	createCopy() Creates a copy of this graph.
Edge	createEdge(Node v, Edge e1, Node w, Edge e2, int d1, int d2) Creates a new edge in this graph The new edge e has source node v and target node w.
Edge	createEdge(Node v, Node w) Creates a new edge in this graph.
EdgeMap	createEdgeMap() Returns a newly created edge map that is valid for the edges in this graph.
Graph	createGraph() Creates an empty.base object of the same type as this graph.
Node	createNode() Creates a new node in this graph.
NodeMap	createNodeMap() Returns a newly created node map that is valid for the nodes in this graph.
void	disposeEdgeMap(EdgeMap map) Informs the graph that the given edge map is not needed any longer.
void	disposeNodeMap(NodeMap map) Informs the graph that the given node map is not needed any longer.
int	E() Same as Graph.edgeCount()
int	edgeCount() Returns the number of edges in this graph.
Iterator	edgeObjects() Returns an iterator that provides access to all edges residing in this graph.
EdgeCursor	edges() Provides access to the edges of the graph.
protected void	fireGraphEvent(GraphEvent e) Propagates the given graph event to all registered graph listeners.
void	firePostEvent() Propagates a post event to all registered graph listeners.
void	firePostEvent(Object id) Like Graph.firePostEvent().
void	firePreEvent() Propagates a pre event to all registered graph listeners.
void	firePreEvent(Object id) Like Graph.firePreEvent().
Edge	firstEdge() Returns the first edge in this graph.
Node	firstNode() Returns the first node in this graph.
protected static Edge	firstOutEdge(Node v) Low level iteration support for adj edges.
DataProvider	getDataProvider(Object providerKey) Returns a data provider that is registered with the graph under the given key.
Object[]	getDataProviderKeys() Returns an array of all data provider keys that are registered with this graph.
Edge[]	getEdgeArray() Returns an array containing all edges of this graph.
Iterator	getGraphListeners() Returns an iterator that grants access to all registered GraphListeners.
Node[]	getNodeArray() Returns an array containing all nodes of this graph.
EdgeMap[]	getRegisteredEdgeMaps() Returns all undisposed edge maps that have been created by this graph.
NodeMap[]	getRegisteredNodeMaps() Returns all undisposed node maps that have been created by this graph.
Object	getSource(Object edge) Returns the source node associated with the given edge.
Object	getTarget(Object edge) Returns the target node associated with the given edge.
void	hide(Edge e) Hides the given edge from this graph.
void	hide(Node v) Hides the given node from this graph.
boolean	isEmpty() Returns true if this graph contains no nodes.
Edge	lastEdge() Returns the first edge in this graph.
Node	lastNode() Returns the last node in this graph.
EdgeList	moveSubGraph(NodeList subNodes, Graph targetGraph) Moves the subgraph induced by subNodes to target.
void	moveToFirst(Edge e) Moves the given edge to the first position within the sequence of edges in this graph.
void	moveToFirst(Node v) Moves the given node to the first position within the sequence of nodes in this graph.
void	moveToLast(Edge e) Moves the given edge to the last position within the sequence of edges in this graph.
void	moveToLast(Node v) Moves the given node to the last position within the sequence of nodes in this graph.
int	N() Same as Graph.nodeCount().
int	nodeCount() Returns the number of nodes in this graph.
Iterator	nodeObjects() Returns an iterator that provides access to all nodes residing in this graph.
NodeCursor	nodes() Provides access to the nodes of the graph.
void	printNodeSlotSize() For internal debugging purposes only.
void	reInsertEdge(Edge e) Reinsert an Edge in this graph that was formerly removed.
void	reInsertNode(Node v) Reinsert a Node in this graph that was formerly removed.
void	removeDataProvider(Object providerKey) Removes a data provider that is registered under the given key.
void	removeEdge(Edge e) Remove Edge e in this graph.
void	removeGraphListener(GraphListener listener) Removes the given graph listener from this graph.
void	removeNode(Node v) Remove Node v in this graph.
void	reverseEdge(Edge e) Reverses the given Edge.
void	sortEdges(Comparator inComp, Comparator outComp) Sorts the out- and ingoing edges at each node of the graph.
String	toString() Returns a string representation of this graph.
void	unhide(Edge e) Unhides the given edge in this graph.
void	unhide(Node v) Unhides the given node in this graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

listeners

protected Vector listeners

A vector of graph listeners. listeners references null iff no listeners are registered.

BEFORE

public static final int BEFORE

Object insertion specifier. An object gets inserted before another one.

See Also:

Constant Field Values

AFTER

public static final int AFTER

Object insertion specifier. An object gets inserted after another one.

See Also:

Constant Field Values

Constructor Detail

Graph

public Graph()

Instantiates an empty Graph.

Graph

public Graph(Graph argGraph)

Instantiates a new Graph object as a copy of argGraph. Values bound to the argument graph via node and edge keys are available in the new graph instance with the keys registered with argGraph. Only references to these values are copied.

Parameters:

argGraph - Graph to be copied

Graph

public Graph(Graph graph,
             YCursor subNodes)

Instantiates a new Graph object as a partial copy of the argument graph. Only the subgraph induced by nodeList will be copied to the new graph instance.

Method Detail

createCopy

public Graph createCopy()

Creates a copy of this graph.

createNode

public Node createNode()

Creates a new node in this graph.

Returns:

newly created Node object

createEdge

public Edge createEdge(Node v,
                       Node w)

Creates a new edge in this graph. The new edge has source node v and target node w. No EdgeRealizer will be bound to the created edge.

Parameters:

v - the source node of the edge

w - the target node of the edge

Returns:

newly created Edge object

createEdge

public Edge createEdge(Node v,
                       Edge e1,
                       Node w,
                       Edge e2,
                       int d1,
                       int d2)

Creates a new edge in this graph The new edge e has source node v and target node w. Edge e is inserted in such a way that an iteration over the edges at node v returns e after (before) e1 if d1 == AFTER (d1 == BEFORE) and an iteration over the edges at w return e after (before) e2 if d2 == AFTER (d2 == BEFORE).

Precondition: Edge e1 must have source node v and edge e2 must have target node w

Parameters:

v - the source node of the edge

e1 - an edge with source node v

w - the target node of the edge

e2 - an edge with target node w

d1 - one of the object insertion specifiers BEFORE or AFTER

d2 - one of the object insertion specifiers BEFORE or AFTER

removeNode

public void removeNode(Node v)

Remove Node v in this graph. All edges connected to v are removed as well. The node will be deselected before it gets removed.

Parameters:

v - node to be removed in this graph

removeEdge

public void removeEdge(Edge e)

Remove Edge e in this graph. The edge will be deselected before it gets removed.

Parameters:

e - edge to be removed

reInsertNode

public void reInsertNode(Node v)

Reinsert a Node in this graph that was formerly removed.

Parameters:

v - a node to be reinserted

reInsertEdge

public void reInsertEdge(Edge e)

Reinsert an Edge in this graph that was formerly removed.

Parameters:

e - an edge to be reinserted

changeEdge

public void changeEdge(Edge e,
                       Edge e1,
                       Edge e2,
                       int d1,
                       int d2)

This method redefines the endpoints of e. Edge ev := e1.source() and target node w := e2.target(). Edge e is inserted in such a way that an iteration over the edges at v returns e after (before) e1 if d1 == AFTER (d1 == BEFORE) and an iteration over the edges at w return e after (before) e2 if d2 == AFTER (d2 == BEFORE).

Precondition: Edges e, e1, e2 must be contained in this graph.

Parameters:

e - the edge to be changed

e1 - reference edge for insertion at a new source node

e2 - reference edge for insertion at a new target node

d1 - one of the object insertion specifiers BEFORE or AFTER

d2 - one of the object insertion specifiers BEFORE or AFTER

changeEdge

public void changeEdge(Edge e,
                       Node newSource,
                       Edge sourceReference,
                       int sourceD,
                       Node newTarget,
                       Edge targetReference,
                       int targetD)

This method redefines the endpoints of e. Edge ev := sourceReference.source() or v := newSource if sourceReference == null and target node w := targetReference.target(). or w := newTarget if targetReference == null Edge e is inserted in such a way that an iteration over the edges at v returns e after (before) sourceReference if sourceD == AFTER (sourceD == BEFORE) and an iteration over the edges at w return e after (before) targetReference if targetD == AFTER (targetD == BEFORE).

Precondition: Edges e must be contained in this graph and either sourceReference or newSource must be non-null and contained in the graph as well as targetReference or newTarget.

Parameters:

e - the edge to be changed

newSource - the new source

sourceReference - reference edge for insertion at the new source node

sourceD - one of the object insertion specifiers BEFORE or AFTER

newTarget - the new target

targetReference - reference edge for insertion at the new target node

targetD - one of the object insertion specifiers BEFORE or AFTER

changeEdge

public void changeEdge(Edge e,
                       Node newSource,
                       Node newTarget)

This method redefines the endpoints of e.

Precondition: newSource, newTarget must be contained in this graph.

Parameters:

e - the edge to be changed

newSource - the new source node of the given edge

newTarget - the new target node of the given edge

reverseEdge

public void reverseEdge(Edge e)

Reverses the given Edge. This operation exchanges source and target node of the edge.

hide

public void hide(Edge e)

Hides the given edge from this graph. To hide an edge means to (temporarily) remove the edge from the graph.

The difference to a proper object removal as performed by Graph.removeEdge(Edge) or Graph.removeNode(Node) is that no GraphEvents will be emitted that signal object removal.

Hiding should be used in the sense of temporarily removing an object that will be reinserted shortly after. To reinsert a hidden object again use unhide(edge) or unhide(Node).

unhide

public void unhide(Edge e)

Unhides the given edge in this graph. To unhide an edge means to reinsert an edge that was formerly hidden from this graph by a call to Graph.hide(Edge).

The difference to a proper object reinsertion as performed by Graph.reInsertEdge(Edge) or Graph.reInsertNode(Node) is that no GraphEvents will be emitted that signal object reinsertion.

To reinsert a hidden object again use unhide(edge) or unhide(Node).

hide

public void hide(Node v)

Hides the given node from this graph. To hide a node means to (temporarily) remove the nodee from the graph.

The difference to a proper object removal as performed by Graph.removeEdge(Edge) or Graph.removeNode(Node) is that no GraphEvents will be emitted that signal object removal.

Hiding should be used in the sense of temporarily removing an object that will be reinserted shortly after. To reinsert a hidden object again use unhide(edge) or unhide(Node).

unhide

public void unhide(Node v)

Unhides the given node in this graph. To unhide a node means to reinsert a node that was formerly hidden from this graph by a call to Graph.hide(Node).

The difference to a proper object reinsertion as performed by Graph.reInsertEdge(Edge) or Graph.reInsertNode(Node) is that no GraphEvents will be emitted that signal object reinsertion.

To reinsert a hidden object again use unhide(edge) or unhide(Node).

moveToLast

public void moveToLast(Node v)

Moves the given node to the last position within the sequence of nodes in this graph.

moveToFirst

public void moveToFirst(Node v)

Moves the given node to the first position within the sequence of nodes in this graph.

moveToLast

public void moveToLast(Edge e)

Moves the given edge to the last position within the sequence of edges in this graph.

moveToFirst

public void moveToFirst(Edge e)

Moves the given edge to the first position within the sequence of edges in this graph.

N

public int N()

Same as Graph.nodeCount().

Returns:

number of nodes in this graph

nodeCount

public int nodeCount()

Returns the number of nodes in this graph.

Returns:

number of nodes in this graph

E

public int E()

Same as Graph.edgeCount()

Returns:

number of edges in this graph

edgeCount

public int edgeCount()

Returns the number of edges in this graph.

Returns:

number of edges in this graph

isEmpty

public boolean isEmpty()

Returns true if this graph contains no nodes.

Returns:

true if graph contains no nodes, otherwise false

clear

public void clear()

Removes all nodes and edges from this graph.

contains

public boolean contains(Node v)

Whether or not this graph contains the given node.

contains

public boolean contains(Edge e)

Whether or not this graph contains the given edge.

containsEdge

public boolean containsEdge(Node source,
                            Node target)

Returns whether or not this grpah contains an edge from node source to node target.

See Also:

Node.getEdgeTo(Node), Node.getEdgeFrom(Node), Node.getEdge(Node)

firstNode

public Node firstNode()

Returns the first node in this graph.

Precondition: !isEmpty()

firstEdge

public Edge firstEdge()

Returns the first edge in this graph.

Precondition: edgeCount() > 0

lastNode

public Node lastNode()

Returns the last node in this graph.

Precondition: !isEmpty()

lastEdge

public Edge lastEdge()

Returns the first edge in this graph.

Precondition: edgeCount() > 0

getNodeArray

public Node[] getNodeArray()

Returns an array containing all nodes of this graph.

getEdgeArray

public Edge[] getEdgeArray()

Returns an array containing all edges of this graph.

nodes

public NodeCursor nodes()

Provides access to the nodes of the graph.

Returns:

A NodeCursor over the nodes in the graph

edges

public EdgeCursor edges()

Provides access to the edges of the graph.

Returns:

A EdgeCursor over the edges in the graph

moveSubGraph

public EdgeList moveSubGraph(NodeList subNodes,
                             Graph targetGraph)

Moves the subgraph induced by subNodes to target. Returns a list of removed edges that connected the induced subgraph with the rest of the graph.
Preconditions: subNodes must iterate over nodes contained in this graph.

createGraph

public Graph createGraph()

Creates an empty.base object of the same type as this graph. Subclasses should overwrite this method.

sortEdges

public void sortEdges(Comparator inComp,
                      Comparator outComp)

Sorts the out- and ingoing edges at each node of the graph. If a given comparator is null then outedges, inedges resp., will not be sorted.

Parameters:

inComp - the edge comparator used for the ingoing edges at a node.

outComp - the edge comparator used for the outgoing edges at a node.

addGraphListener

public void addGraphListener(GraphListener listener)

Adds the given graph listener to this graph. The listener will receive graph events that indicate structural changes occuring within this graph.

removeGraphListener

public void removeGraphListener(GraphListener listener)

Removes the given graph listener from this graph.

getGraphListeners

public Iterator getGraphListeners()

Returns an iterator that grants access to all registered GraphListeners.

firePreEvent

public void firePreEvent()

Propagates a pre event to all registered graph listeners. This method should only be used if a corresponding call of firePostEvent follows.

firePreEvent

public void firePreEvent(Object id)

Like Graph.firePreEvent(). Additionally an event id may be specified.

firePostEvent

public void firePostEvent()

Propagates a post event to all registered graph listeners. This method should only be used if a corresponding call of firePreEvent was made.

firePostEvent

public void firePostEvent(Object id)

Like Graph.firePostEvent(). Additionally an event id may be specified.

fireGraphEvent

protected void fireGraphEvent(GraphEvent e)

Propagates the given graph event to all registered graph listeners.

createNodeMap

public NodeMap createNodeMap()

Returns a newly created node map that is valid for the nodes in this graph. The implementation returned by this method can be used for any node, that is part of this graph instance at any point of time, i.e. it is safe to modify the graph structure (add and remove nodes and edges) freely. The implementation returned uses O(n) memory at all times and provides true O(1) read and write access for each node. In order to release the resources held by this map, Graph.disposeNodeMap(NodeMap) has to be called.

createEdgeMap

public EdgeMap createEdgeMap()

Returns a newly created edge map that is valid for the edges in this graph. The implementation returned by this method can be used for any edge, that is part of this graph instance at any point of time, i.e. it is safe to modify the graph structure (add and remove nodes and edges) freely. The implementation returned uses O(m) memory at all times and provides true O(1) read and write access for each node. In order to release the resources held by this map, Graph.disposeEdgeMap(EdgeMap) has to be called.

disposeNodeMap

public void disposeNodeMap(NodeMap map)

Informs the graph that the given node map is not needed any longer. This method is used for NodeMap implementations that have been obtained using the Graph.createNodeMap() factory method. Calling this method will destroy the node map and associated resources can be freed. It is strongly suggested to dispose all node maps that are not needed anymore using this method.

disposeEdgeMap

public void disposeEdgeMap(EdgeMap map)

Informs the graph that the given edge map is not needed any longer. This method is used for EdgeMap implementations that have been obtained using the Graph.createEdgeMap() factory method. Calling this method will destroy the edge map and associated resources can be freed. It is strongly suggested to dispose all edge maps that are not needed anymore using this method.

getRegisteredNodeMaps

public NodeMap[] getRegisteredNodeMaps()

Returns all undisposed node maps that have been created by this graph.

See Also:

Graph.createNodeMap(), Graph.disposeNodeMap(NodeMap)

getRegisteredEdgeMaps

public EdgeMap[] getRegisteredEdgeMaps()

Returns all undisposed edge maps that have been created by this graph.

See Also:

Graph.createEdgeMap(), Graph.disposeEdgeMap(EdgeMap)

getSource

public Object getSource(Object edge)

Returns the source node associated with the given edge.

Specified by:

getSource in interface GraphInterface

getTarget

public Object getTarget(Object edge)

Returns the target node associated with the given edge.

Specified by:

getTarget in interface GraphInterface

nodeObjects

public Iterator nodeObjects()

Returns an iterator that provides access to all nodes residing in this graph.

Specified by:

nodeObjects in interface GraphInterface

edgeObjects

public Iterator edgeObjects()

Returns an iterator that provides access to all edges residing in this graph.

Specified by:

edgeObjects in interface GraphInterface

getDataProvider

public DataProvider getDataProvider(Object providerKey)

Returns a data provider that is registered with the graph under the given key. The lookup domain of a data provider returned will normally consist of either the nodes of the graph or its edges or both.

Specified by:

getDataProvider in interface GraphInterface

addDataProvider

public void addDataProvider(Object providerKey,
                            DataProvider data)

Registers the given data provider under the given lookup key. If there is already a data provider registered under that key then that provider will be overwritten with the new one.

removeDataProvider

public void removeDataProvider(Object providerKey)

Removes a data provider that is registered under the given key.

getDataProviderKeys

public Object[] getDataProviderKeys()

Returns an array of all data provider keys that are registered with this graph.

Specified by:

getDataProviderKeys in interface GraphInterface

firstOutEdge

protected static final Edge firstOutEdge(Node v)

Low level iteration support for adj edges.

printNodeSlotSize

public void printNodeSlotSize()

For internal debugging purposes only.

toString

public String toString()

Returns a string representation of this graph. The string contains all string representation of the nodes and all string representation of the edges.

Overrides:

toString in class Object