
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.base.Graph
public class Graph
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
).
The directed stems from the fact that all edges in the graph have direction,
i.e., they have a distinct source node and a distinct target node.
Using the aforementioned pair notation, an edge would be written as
(<source node>, <target node>).
Class Graph presents a proper data type that provides support for all essential
operations like element creation, removal, access, and iteration.
Important:
Class Graph is the single authority for any structural changes to the graph data
type.
Specifically, this means that there is no way to create or delete a node or an
edge without using an actual Graph instance.
Furthermore, this class is also responsible for providing access to its elements.
This is done by means of bidirectional cursors that present a readonly view
on the node set (interface NodeCursor
) and edge set (interface
EdgeCursor
).
Class Graph fires notification events that signal structural changes, like, e.g.,
creation, removal, reinsertion, or modification of graph elements.
Classes that implement the GraphListener
interface can be registered
with this class using the addGraphListener
method in order to receive such events.
This class provides direct support for the notion of data accessors.
It allows to register socalled data providers (implementations of interface
DataProvider
) that hold arbitrary data which is associated to its nodes
and/or edges.
Also, it serves as a factory to create socalled maps (NodeMap
,
EdgeMap
) that can be utilized to bind arbitrary data to nodes and edges.
Field Summary  

static int 
AFTER
Object insertion specifier. 
static int 
BEFORE
Object insertion specifier. 
Constructor Summary  

Graph()
Instantiates an empty Graph object. 

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

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

void 
addDataProvider(java.lang.Object providerKey,
DataProvider data)
Registers the given data provider using the given lookup key. 
void 
addGraphListener(GraphListener listener)
Registers the given graph listener with this graph. 
void 
changeEdge(Edge e,
Edge e1,
Edge e2,
int d1,
int d2)
Redefines an edge's end points and fires corresponding notification events to inform registered listeners. 
void 
changeEdge(Edge e,
Node newSource,
Edge sourceReference,
int sourceD,
Node newTarget,
Edge targetReference,
int targetD)
Redefines an edge's end points and fires corresponding notification events to inform registered listeners. 
void 
changeEdge(Edge e,
Node newSource,
Node newTarget)
Redefines an edge's end points and fires corresponding notification events to inform registered listeners. 
void 
clear()
Removes all nodes and edges from this graph and fires corresponding notification events to inform registered listeners. 
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 graph contains an edge that connects the given nodes. 
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 to be ordered before or after a given edge and fires a corresponding notification event to inform registered listeners. 
Edge 
createEdge(Node v,
Node w)
Creates a new edge in this graph and fires a corresponding notification event to inform registered listeners. 
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. 
protected GraphCopier.CopyFactory 
createGraphCopyFactory()
Factory method that is called by getGraphCopyFactory()
to create a (possibly shared) instance. 
Node 
createNode()
Creates a new node in this graph and fires a corresponding notification event to inform registered listeners. 
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 no longer needed. 
void 
disposeNodeMap(NodeMap map)
Informs the graph that the given node map is no longer needed. 
int 
E()
Returns the number of edges in this graph. 
int 
edgeCount()
Returns the number of edges in this graph. 
java.util.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 socalled POST event to all registered graph listeners. 
void 
firePostEvent(java.lang.Object id)
Like firePostEvent() . 
void 
firePreEvent()
Propagates a socalled PRE event to all registered graph listeners. 
void 
firePreEvent(java.lang.Object id)
Like 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)
Lowlevel iteration support for adjacent edges. 
DataProvider 
getDataProvider(java.lang.Object providerKey)
Returns the data provider that is registered with the graph using the given lookup key. 
java.lang.Object[] 
getDataProviderKeys()
Returns an array of all data provider lookup keys that are registered with this graph. 
Edge[] 
getEdgeArray()
Returns an array containing all edges of this graph. 
GraphCopier.CopyFactory 
getGraphCopyFactory()
Returns the copy factory that is associated with this instance. 
java.util.Iterator 
getGraphListeners()
Returns an iterator that grants access to all registered graph listeners. 
Node[] 
getNodeArray()
Returns an array containing all nodes of this graph. 
EdgeMap[] 
getRegisteredEdgeMaps()
Returns all edge maps that have been created by this graph but have not yet been disposed. 
NodeMap[] 
getRegisteredNodeMaps()
Returns all node maps that have been created by this graph but have not yet been disposed. 
java.lang.Object 
getSource(java.lang.Object edge)
Returns the source node associated with the given edge. 
java.lang.Object 
getTarget(java.lang.Object edge)
Returns the target node associated with the given edge. 
protected boolean 
hasListeners()
Determines whether there are listeners registered with this instance. 
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 last edge in this graph. 
Node 
lastNode()
Returns the last node in this graph. 
EdgeList 
moveSubGraph(NodeList subNodes,
Graph targetGraph)
Moves an induced subgraph to another graph. 
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()
Returns the number of nodes in this graph. 
int 
nodeCount()
Returns the number of nodes in this graph. 
java.util.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)
Reinserts a formerly removed edge into this graph and fires a corresponding notification event to inform registered listeners. 
void 
reInsertNode(Node v)
Reinserts a formerly removed node into this graph and fires a corresponding notification event to inform registered listeners. 
void 
removeDataProvider(java.lang.Object providerKey)
Removes the data provider that is registered using the given lookup key. 
void 
removeEdge(Edge e)
Removes the given edge from this graph and fires a corresponding notification event to inform registered listeners. 
void 
removeGraphListener(GraphListener listener)
Removes the given graph listener from this graph. 
void 
removeNode(Node v)
Removes the given node from this graph. 
void 
reverseEdge(Edge e)
Reverses the given edge and fires corresponding notification events to inform registered listeners. 
void 
setGraphCopyFactory(GraphCopier.CopyFactory copyFactory)
Sets the copy factory that is associated with this instance. 
void 
sortEdges(java.util.Comparator comp)
Sorts the internally held list of edges. 
void 
sortEdges(java.util.Comparator inComp,
java.util.Comparator outComp)
Sorts incoming and outgoing edges at each node of the graph. 
void 
sortNodes(java.util.Comparator comp)
Sorts the internally held list of nodes. 
java.lang.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 

public static final int BEFORE
public static final int AFTER
Constructor Detail 

public Graph()
Graph
object.
public Graph(Graph argGraph)
Graph
object as a copy of the given graph.
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.
The new Graph
instance also inherits all graph listeners registered with the
given graph.
This constructor does not use a GraphCopier
.
argGraph
 The graph to be copied.public Graph(Graph graph, YCursor subNodes)
Graph
object as a partial copy of the given graph.
Only the subgraph induced by the given cursor will be copied to the new Graph
instance.
Values bound to the argument graph via node and edge keys are available in
the new Graph
instance with the keys registered with graph
.
Only references to these values are copied.
The new Graph
instance also inherits all graph listeners registered with the
given graph.
This constructor does not use a GraphCopier
.
graph
 The graph to be (partially) copied.subNodes
 A cursor to iterate over the nodes that actually induce the subgraph to be
copied.Method Detail 

public GraphCopier.CopyFactory getGraphCopyFactory()
createGraphCopyFactory()
(if no
instance has been specified before).
createGraphCopyFactory()
,
setGraphCopyFactory(y.util.GraphCopier.CopyFactory)
protected GraphCopier.CopyFactory createGraphCopyFactory()
getGraphCopyFactory()
to create a (possibly shared) instance.
public void setGraphCopyFactory(GraphCopier.CopyFactory copyFactory)
createGraphCopyFactory()
(if no
instance has been specified before).
copyFactory
 the new factory to use.createGraphCopyFactory()
,
setGraphCopyFactory(y.util.GraphCopier.CopyFactory)
protected final boolean hasListeners()
public Graph createCopy()
Graph(Graph)
.
public Node createNode()
public Edge createEdge(Node v, Node w)
v
and target node w
,
i.e., would be written as edge e = (v, w)
.
The edge is appended to the lists of incoming and outgoing edges at the source node and target node, respectively.
v
 The source node of the edge.w
 The target node of the edge.
public Edge createEdge(Node v, Edge e1, Node w, Edge e2, int d1, int d2)
e
has source node v
and target node
w
, i.e., would be written as edge e = (v, w)
.
e
is inserted in such a way that an iteration over the edges
at node v
returns e
e1
, if d1 == AFTER
e1
, if d1 == BEFORE
,
w
returns e
e2
, if d2 == AFTER
e2
, if d2 == BEFORE
.
e1
must have source node v
and
edge e2
must have target node w
.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
.
public void removeNode(Node v)
The node will be deselected before it gets removed.
v
 The node to be removed from this graph.public void removeEdge(Edge e)
The edge will be deselected before it gets removed.
e
 The edge to be removed.public void reInsertNode(Node v)
The reinserted node is appended to the sequence of nodes in this graph, i.e., normally, its new position does not match the position before its removal.
v
 The node to be reinserted.removeNode(Node)
public void reInsertEdge(Edge e)
The reinserted edge is appended to the sequence of edges in this graph, i.e., normally, its new position does not match the position before its removal. The same holds for the edge's positions in the list of incoming and outgoing edges at its source node and target node, respectively.
Note that reinserting an edge whose source/target is not in the graph (e.g., because it's currently hidden/removed) causes an exception. Hence, in such cases, you first have to unhide/reinsert the corresponding endpoints.
e
 The edge to be reinserted.removeEdge(Edge)
public void changeEdge(Edge e, Edge e1, Edge e2, int d1, int d2)
e
has
source node v := e1.source()
and
target node w := e2.target()
.
e
is inserted in such a way that an iteration over the edges
at v
returns e
e1
, if d1 == AFTER
e1
, if d1 == BEFORE
,
w
returns e
e2
, if d2 == AFTER
e2
, if d2 == BEFORE
.
e
, e1
, and e2
must belong to this
graph.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
.public void changeEdge(Edge e, Node newSource, Edge sourceReference, int sourceD, Node newTarget, Edge targetReference, int targetD)
e
has
source node v := sourceReference.source()
or v := newSource
,
if sourceReference == null
and
target node w := targetReference.target()
or w := newTarget
,
if targetReference == null
.
e
is inserted in such a way that an iteration over the edges
at v
returns e
sourceReference
, if sourceD == AFTER
sourceReference
, if sourceD == BEFORE
,
w
returns e
targetReference
, if targetD == AFTER
targetReference
, if targetD == BEFORE
.
e
must belong to this graph.
Also, either sourceReference
or newSource
must be
nonnull and belong to this graph, and either targetReference
or newTarget
must be nonnull and belong to this graph.e
 The edge to be changed.newSource
 The new source node.sourceReference
 Reference edge for insertion at the new source node.sourceD
 One of the object insertion specifiers BEFORE
or AFTER
.newTarget
 The new target node.targetReference
 Reference edge for insertion at the new target node.targetD
 One of the object insertion specifiers BEFORE
or AFTER
.public void changeEdge(Edge e, Node newSource, Node newTarget)
The edge is appended to the lists of incoming and outgoing edges at the given source node and target node, respectively.
newSource
and newTarget
must belong to this graph.e
 The edge to be changed.newSource
 The new source node of the given edge.newTarget
 The new target node of the given edge.public void reverseEdge(Edge e)
public void hide(Edge e)
The only difference to a proper edge removal as performed by removeEdge(Edge)
is that no GraphEvent
will be emitted that signals the structural change
(i.e. the edge's removal).
Generally, hiding should only be used in the sense of temporarily removing an object that will be reinserted shortly after.
To reinsert a hidden edge use unhide(Edge)
.
hide(Node)
,
unhide(Node)
public void unhide(Edge e)
hide(Edge)
.
The only difference to a proper edge reinsertion as performed by reInsertEdge(Edge)
is that no GraphEvent
will be emitted that signals the structural change
(i.e. the edge's reinsertion).
Note that unhiding an edge whose source/target is not in the graph (e.g., because it's currently hidden/removed) causes an exception. Hence, in such cases, you first have to unhide/reinsert the corresponding endpoints.
hide(Node)
,
unhide(Node)
public void hide(Node v)
The only difference to a proper node removal as performed by removeNode(Node)
is that no GraphEvent
will be emitted that signals the structural change
(i.e. the node's removal).
Generally, hiding should only be used in the sense of temporarily removing an object that will be reinserted shortly after.
To reinsert a hidden node use unhide(Node)
.
hide(Edge)
,
unhide(Edge)
public void unhide(Node v)
hide(Node)
.
The only difference to a proper node reinsertion as performed by reInsertNode(Node)
is that no GraphEvent
will be emitted that signals the structural change
(i.e. the node's reinsertion).
public void moveToLast(Node v)
public void moveToFirst(Node v)
public void moveToLast(Edge e)
public void moveToFirst(Edge e)
public int N()
nodeCount()
.
public int nodeCount()
public int E()
edgeCount()
.
public int edgeCount()
public boolean isEmpty()
true
if this graph contains no nodes.
true
if this graph contains no nodes, otherwise false
.public void clear()
public boolean contains(Node v)
public boolean contains(Edge e)
public boolean containsEdge(Node source, Node target)
source
 The source node.target
 The target node.Node.getEdgeTo(Node)
,
Node.getEdgeFrom(Node)
,
Node.getEdge(Node)
public Node firstNode()
!isEmpty()
public Edge firstEdge()
edgeCount() > 0
public Node lastNode()
!isEmpty()
public Edge lastEdge()
edgeCount() > 0
public Node[] getNodeArray()
public Edge[] getEdgeArray()
public NodeCursor nodes()
public EdgeCursor edges()
public EdgeList moveSubGraph(NodeList subNodes, Graph targetGraph)
subNodes
must belong to this
graph.subNodes
 A list of nodes that induce the subgraph to be moved.targetGraph
 The graph where the subgraph is moved to.
public Graph createGraph()
Subclasses should override this method.
public void sortEdges(java.util.Comparator comp)
null
, then the edges will not be sorted.
This list determines the order of the edges as returned by edges()
.
comp
 The comparator used for the edges.public void sortNodes(java.util.Comparator comp)
null
, then the nodes will not be sorted.
This list determines the order of the nodes as returned by nodes()
.
comp
 The comparator used for the nodes.public void sortEdges(java.util.Comparator inComp, java.util.Comparator outComp)
null
, then the corresponding edges (i.e.,
incoming/outgoing) will not be sorted.
This sorts the order of the edges as returned by Node.outEdges()
and Node.inEdges()
respectively.
inComp
 The comparator used for the incoming edges at each node.outComp
 The comparator used for the outgoing edges at each node.public void addGraphListener(GraphListener listener)
GraphEvent
public void removeGraphListener(GraphListener listener)
public java.util.Iterator getGraphListeners()
public void firePreEvent()
firePostEvent()
follows.
Generally, PRE and POST events serve as a means to bracket a sequence of graph events.
GraphListener
public void firePreEvent(java.lang.Object id)
firePreEvent()
.
Additionally, an event ID may be specified.
id
 An identifying tag for the event.GraphListener
public void firePostEvent()
firePreEvent()
was made.
Generally, PRE and POST events serve as a means to bracket a sequence of graph events.
GraphListener
public void firePostEvent(java.lang.Object id)
firePostEvent()
.
Additionally, an event ID may be specified.
id
 An identifying tag for the event.GraphListener
protected void fireGraphEvent(GraphEvent e)
public NodeMap createNodeMap()
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, disposeNodeMap(NodeMap)
has to be called.
public EdgeMap createEdgeMap()
The implementation returned uses O(m)
memory at all times and
provides true O(1)
read and write access for each edge.
In order to release the resources held by this map, disposeEdgeMap(EdgeMap)
has to be called.
public void disposeNodeMap(NodeMap map)
createNodeMap()
factory method.
Calling this method will destroy the node map and associated resources can be freed. It is strongly recommended to dispose of all node maps that are not needed anymore using this method.
public void disposeEdgeMap(EdgeMap map)
createEdgeMap()
factory method.
Calling this method will destroy the edge map and associated resources can be freed. It is strongly recommended to dispose of all edge maps that are not needed anymore using this method.
public NodeMap[] getRegisteredNodeMaps()
createNodeMap()
,
disposeNodeMap(NodeMap)
public EdgeMap[] getRegisteredEdgeMaps()
createEdgeMap()
,
disposeEdgeMap(EdgeMap)
public java.lang.Object getSource(java.lang.Object edge)
getSource
in interface GraphInterface
public java.lang.Object getTarget(java.lang.Object edge)
getTarget
in interface GraphInterface
public java.util.Iterator nodeObjects()
nodeObjects
in interface GraphInterface
public java.util.Iterator edgeObjects()
edgeObjects
in interface GraphInterface
public DataProvider getDataProvider(java.lang.Object providerKey)
getDataProvider
in interface GraphInterface
public void addDataProvider(java.lang.Object providerKey, DataProvider data)
public void removeDataProvider(java.lang.Object providerKey)
public java.lang.Object[] getDataProviderKeys()
getDataProviderKeys
in interface GraphInterface
protected static final Edge firstOutEdge(Node v)
public void printNodeSlotSize()
public java.lang.String toString()
toString
in class java.lang.Object

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 