de.grogra.graph
Interface Graph

All Superinterfaces:

Lockable

All Known Implementing Classes:

AttributeOverwritingFilter, GraphBase, GraphFilter, GraphManager

public interface Graph
extends Lockable

A Graph represents a graph-like structure. It consists of nodes, connected by directed edges. Both nodes and edges are objects, their classes are not restricted by this interface.

Topological Structure

The nodes and edges of a graph are obtained in the following way:

• The method getRootKeys() returns an array of strings, the root keys. These are used as arguments to getRoot(String). The returned value is a node, namely the root of the subgraph identified by the root key. The root key MAIN_GRAPH is a predefined root key, it identifies the root of the main graph which should always be present. Further root keys may be defined, depending on the Graph.
• For every node n, there is a linked list of edges with unspecified order. The first edge of this linked list is obtained by getFirstEdge(Object) with n passed as argument, the next edges are obtained by getNextEdge(Object, Object) with the previous edge as first argument and n as second. Thus, a loop over all edges of n in a graph g can be implemented as follows:

   for (Object e = g.getFirstEdge(n); e != null; e = g.getNextEdge(e, n))
   {
       // do something with the current edge e
   }
   

• Given an edge e, its source and target nodes are obtained by the method getSourceNode(Object) and getTargetNode(Object).

Attributes

Besides topological information, a Graph provides attribute-like information for nodes and edges:

• Every node has a unique id which is obtained by getId(Object). The inverse method getNodeForId(long) returns the node identified by the given id.
• Every node and every edge has a name which is obtained by getName(Object, boolean). The name is not necessarily unique, the inverse method getObjectForName(boolean, String) returns one of the nodes or edges with the given name.
• Every edge has a set of edge bits (getEdgeBits(Object)). These are stored in a single int-value which is interpreted as a set of sub-edges in the following way:
  • The bits 0 to 7 (masked by SPECIAL_EDGE_MASK) represent the edge's special sub-edge. If these bits, interpreted as a byte, have the value 0, no special sub-edge is present. Otherwise, the special sub-edge identified by this byte is present in this edge. The value 255 (all bits set) is reserved for special purposes. Note that at most one special edge may exist at a time between an ordered tuple of nodes.
  • The other 24 bits (bits 8 to 31) represent 24 possible sub-edges, each indicated by the presence of its specific bit in the int-value. It is up to the concrete graph to specify the meaning of the sub-edges. The Graph interface provides three standard meanings: SUCCESSOR_EDGE, BRANCH_EDGE, and CONTAINMENT_EDGE.
• Every node and every edge has a set of attributes which is returned by getAttributes(Object, boolean). Each attribute is represented by an instance of Attribute, attribute values are read and written on nodes and edges within the context of a GraphState.

Threading Issues

In order to ensure a stable and predictable behaviour in the context of multiple threads, the following rules have to be followed:

1. Modifications to a graph may only be performed within the context of the main graph state (see getMainState()), and only when a write lock has been obtained by (see Lockable which is extended by this interface).
2. In principle, reading of structure and attributes can be done without any special arrangement. However, it is safer to do this when a read lock has been obtained (again see Lockable). because then it is guaranteed that no other thread may modify the graph during the invocation (if the other threads conform to these rules).
3. The methods for adding and removing of event listeners in this interface have to be implemented thread-safe.
4. The implementation of this interface has to ensure that its event listeners are notified about modifications only within the context of the main graph state.

The Tree of a Graph

A graph defines a tree pattern (see getTreePattern()). Starting at the root of the main graph (getRoot(String), MAIN_GRAPH), this pattern is used as a filter to construct a subgraph out of the whole graph. The subgraph has to be a tree, but it is not necessarily a spanning tree for the whole graph. The parent attribute (see getParentAttribute()) of the graph has to be a derived attribute which has as value for every node of the tree its parent edge and for every edge of the tree its parent node. For objects which are not part of the tree the value is null.

Author:

Ole Kniemeyer

See Also:

GraphState, Attribute

Nested Class Summary

Nested classes/interfaces inherited from interface de.grogra.util.Lockable

Lockable.DeadLockException

Field Summary

static int	BRANCH_EDGE The bit mask indicating the presence of a branch edge in edge bits.
static int	CONTAINMENT_EDGE The bit mask indicating the presence of a containment edge in edge bits.
static int	CONTAINMENT_END_EDGE The bit mask indicating the presence in edge bits of an edge signalling "end of containment".
static int	EDGENODE_IN_EDGE
static int	EDGENODE_OUT_EDGE
static int	ELLIPSE_SYMBOL
static java.lang.String	MAIN_GRAPH The predefined root key which identifies the main graph.
static int	MARK_EDGE The bit mask indicating the presence of a mark edge in edge bits.
static int	MIN_NORMAL_BIT_INDEX
static int	MIN_UNUSED_EDGE
static int	MIN_UNUSED_EDGE_BIT
static int	NOTIFIES_EDGE
static int	PERSISTENT Return value for getLifeCycleState(java.lang.Object, boolean) indicating that the object is persistent, i.e., it belongs the graph.
static int	PERSISTENT_DELETED Return value for getLifeCycleState(java.lang.Object, boolean) indicating that the object has been persistent and is currently being deleted from the graph.
static int	RECTANGLE_SYMBOL
static int	REFINEMENT_EDGE
static int	RHOMBUS_SYMBOL
static int	ROUND_RECTANGLE_SYMBOL
static int	SPECIAL_EDGE_MASK The bit mask for the special edge in edge bits.
static int	SPECIAL_EDGE_OF_SOURCE_BIT
static int	STD_EDGE_5
static int	STD_EDGE_6
static int	SUCCESSOR_EDGE The bit mask indicating the presence of a successor edge in edge bits.
static int	TRANSIENT Return value for getLifeCycleState(java.lang.Object, boolean) indicating that the object is transient, i.e., it does not belong to the graph.

Method Summary

void	accept(java.lang.Object startNode, Visitor visitor, ArrayPath placeInPath)
void	addAttributeChangeListener(AttributeChangeListener l)
void	addAttributeChangeListener(java.lang.Object object, boolean asNode, AttributeChangeListener l)
void	addChangeBoundaryListener(ChangeBoundaryListener l)
void	addEdgeChangeListener(EdgeChangeListener l)
void	addEdgeChangeListener(java.lang.Object object, boolean asNode, EdgeChangeListener l)
BooleanMap	createBooleanMap()
<V> ObjectMap<V>	createObjectMap()
AttributeAccessor	getAccessor(java.lang.Object object, boolean asNode, Attribute attribute) Returns an attribute accessor for the given attribute on the given object.
Attribute[]	getAttributes(java.lang.Object object, boolean asNode) Returns the set of attributes which are available for the given object.
int	getColor(java.lang.Object object, boolean asNode)
Attribute[]	getDependent(java.lang.Object object, boolean asNode, Attribute a) Returns the set of attributes whose values depend on the given attribute a for the given object.
java.lang.Object	getDescription(java.lang.Object object, boolean asNode, java.lang.String type) Returns a description for the given object.
int	getEdgeBits(java.lang.Object edge) Returns the edge bits of an edge.
java.lang.Object	getFirstEdge(java.lang.Object node) Returns the first edge of the linked list of edges of node.
long	getId(java.lang.Object node) Returns a unique identifier for the given node.
Instantiator	getInstantiator(java.lang.Object node)
int	getLifeCycleState(java.lang.Object object, boolean asNode) Returns the life cycle state of the given object as part of this graph.
GraphState	getMainState() Returns the main graph state.
java.lang.String	getName(java.lang.Object object, boolean asNode) Returns a name for the given object.
java.lang.Object	getNextEdge(java.lang.Object edge, java.lang.Object node) Returns the edge after edge in the linked list of edges of node.
java.lang.Object	getNodeForId(long id) Returns the node identified by id.
java.lang.Object	getObjectForName(boolean node, java.lang.String name) Returns the object with the given name.
ObjectAttribute	getParentAttribute() Defines the derived attribute which has as value the parent object.
java.lang.Object	getRoot(java.lang.String key) Returns the root node for the given root key.
java.lang.String[]	getRootKeys() Returns the root keys for the graph.
java.lang.Object	getSourceNode(java.lang.Object edge) Returns the source node of edge.
SpecialEdgeDescriptor[]	getSpecialEdgeDescriptors(java.lang.Object node, boolean asSource)
int	getStamp() Returns a modification stamp for the whole graph.
java.util.Map	getStateMap()
int	getSymbol(java.lang.Object object, boolean asNode)
java.lang.Object	getTargetNode(java.lang.Object edge) Returns the target node of edge.
EdgePattern	getTreePattern() Defines the pattern used for the construction of this graph's tree.
void	removeAttributeChangeListener(AttributeChangeListener l)
void	removeAttributeChangeListener(java.lang.Object object, boolean asNode, AttributeChangeListener l)
void	removeChangeBoundaryListener(ChangeBoundaryListener l)
void	removeEdgeChangeListener(EdgeChangeListener l)
void	removeEdgeChangeListener(java.lang.Object object, boolean asNode, EdgeChangeListener l)

Methods inherited from interface de.grogra.util.Lockable

execute, execute, executeForcedly, executeForcedly, getMaxWaitingTime, getQueueLength, isLocked

Field Detail

BRANCH_EDGE

static final int BRANCH_EDGE

The bit mask indicating the presence of a branch edge in edge bits. This means that the target node of the edge is the first node of a branch (in some graph-dependent sense) originating at the source node of the edge.

See Also:

Graph, getEdgeBits(Object), Constant Field Values

CONTAINMENT_EDGE

static final int CONTAINMENT_EDGE

The bit mask indicating the presence of a containment edge in edge bits. This means that the target node of the edge is contained (in some graph-dependent sense) in the source node of the edge.

See Also:

Graph, getEdgeBits(Object), Constant Field Values

CONTAINMENT_END_EDGE

static final int CONTAINMENT_END_EDGE

The bit mask indicating the presence in edge bits of an edge signalling "end of containment".

See Also:

Graph, getEdgeBits(Object), Constant Field Values

EDGENODE_IN_EDGE

static final int EDGENODE_IN_EDGE

See Also:

Constant Field Values

EDGENODE_OUT_EDGE

static final int EDGENODE_OUT_EDGE

See Also:

Constant Field Values

ELLIPSE_SYMBOL

static final int ELLIPSE_SYMBOL

See Also:

Constant Field Values

MAIN_GRAPH

static final java.lang.String MAIN_GRAPH

The predefined root key which identifies the main graph.

See Also:

Graph, Constant Field Values

MARK_EDGE

static final int MARK_EDGE

The bit mask indicating the presence of a mark edge in edge bits. The precise meaning of a mark edge is not specified by this interface, it may be used for multiple purposes.

See Also:

Graph, getEdgeBits(Object), Constant Field Values

MIN_NORMAL_BIT_INDEX

static final int MIN_NORMAL_BIT_INDEX

See Also:

Constant Field Values

MIN_UNUSED_EDGE

static final int MIN_UNUSED_EDGE

See Also:

Constant Field Values

MIN_UNUSED_EDGE_BIT

static final int MIN_UNUSED_EDGE_BIT

See Also:

Constant Field Values

NOTIFIES_EDGE

static final int NOTIFIES_EDGE

See Also:

Constant Field Values

PERSISTENT

static final int PERSISTENT

Return value for getLifeCycleState(java.lang.Object, boolean) indicating that the object is persistent, i.e., it belongs the graph.

See Also:

Constant Field Values

PERSISTENT_DELETED

static final int PERSISTENT_DELETED

Return value for getLifeCycleState(java.lang.Object, boolean) indicating that the object has been persistent and is currently being deleted from the graph.

See Also:

Constant Field Values

RECTANGLE_SYMBOL

static final int RECTANGLE_SYMBOL

See Also:

Constant Field Values

REFINEMENT_EDGE

static final int REFINEMENT_EDGE

See Also:

Constant Field Values

RHOMBUS_SYMBOL

static final int RHOMBUS_SYMBOL

See Also:

Constant Field Values

ROUND_RECTANGLE_SYMBOL

static final int ROUND_RECTANGLE_SYMBOL

See Also:

Constant Field Values

SPECIAL_EDGE_MASK

static final int SPECIAL_EDGE_MASK

The bit mask for the special edge in edge bits.

See Also:

Graph, getEdgeBits(Object), Constant Field Values

SPECIAL_EDGE_OF_SOURCE_BIT

static final int SPECIAL_EDGE_OF_SOURCE_BIT

See Also:

Constant Field Values

STD_EDGE_5

static final int STD_EDGE_5

See Also:

Constant Field Values

STD_EDGE_6

static final int STD_EDGE_6

See Also:

Constant Field Values

SUCCESSOR_EDGE

static final int SUCCESSOR_EDGE

The bit mask indicating the presence of a successor edge in edge bits. This means that the target node of the edge is the successor (in some graph-dependent sense) of the source node of the edge.

See Also:

Graph, getEdgeBits(Object), Constant Field Values

TRANSIENT

static final int TRANSIENT

Return value for getLifeCycleState(java.lang.Object, boolean) indicating that the object is transient, i.e., it does not belong to the graph.

See Also:

Constant Field Values

Method Detail

accept

void accept(java.lang.Object startNode,
            Visitor visitor,
            ArrayPath placeInPath)

addAttributeChangeListener

void addAttributeChangeListener(AttributeChangeListener l)

addAttributeChangeListener

void addAttributeChangeListener(java.lang.Object object,
                                boolean asNode,
                                AttributeChangeListener l)

addChangeBoundaryListener

void addChangeBoundaryListener(ChangeBoundaryListener l)

addEdgeChangeListener

void addEdgeChangeListener(EdgeChangeListener l)

addEdgeChangeListener

void addEdgeChangeListener(java.lang.Object object,
                           boolean asNode,
                           EdgeChangeListener l)

createBooleanMap

BooleanMap createBooleanMap()

createObjectMap

<V> ObjectMap<V> createObjectMap()

getAccessor

AttributeAccessor getAccessor(java.lang.Object object,
                              boolean asNode,
                              Attribute attribute)

Returns an attribute accessor for the given attribute on the given object.

Parameters:

object - the object

asNode - true if object is a node, false if object is an edge

attribute - the attribute

Returns:

an accessor for the object's attribute value

getAttributes

Attribute[] getAttributes(java.lang.Object object,
                          boolean asNode)

Returns the set of attributes which are available for the given object.

Parameters:

object - the object

asNode - true if object is a node, false if object is an edge

Returns:

the object's attributes

getColor

int getColor(java.lang.Object object,
             boolean asNode)

getDependent

Attribute[] getDependent(java.lang.Object object,
                         boolean asNode,
                         Attribute a)

Returns the set of attributes whose values depend on the given attribute a for the given object.

Parameters:

object - the object

asNode - true if object is a node, false if object is an edge

a - the attribute

Returns:

the set of dependent attributes

getDescription

java.lang.Object getDescription(java.lang.Object object,
                                boolean asNode,
                                java.lang.String type)

Returns a description for the given object. The type of the desired description (e.g., text, icon) is specified in the argument type; it is interpreted as in Described.getDescription(String).

Parameters:

object - the object

asNode - true if object is a node, false if object is an edge

type - the type of description

Returns:

a description of the given type, or null

getEdgeBits

int getEdgeBits(java.lang.Object edge)

Returns the edge bits of an edge.

Parameters:

edge - the edge

Returns:

the edge's edge bits

See Also:

Graph

getFirstEdge

java.lang.Object getFirstEdge(java.lang.Object node)

Returns the first edge of the linked list of edges of node.

Parameters:

node - the common node of the edges of the linked list

Returns:

the first edge of the linked list

See Also:

Graph, getNextEdge(Object, Object)

getId

long getId(java.lang.Object node)

Returns a unique identifier for the given node.

Parameters:

node - a node

Returns:

the node's unique identifier

See Also:

getNodeForId(long)

getInstantiator

Instantiator getInstantiator(java.lang.Object node)

getLifeCycleState

int getLifeCycleState(java.lang.Object object,
                      boolean asNode)

Returns the life cycle state of the given object as part of this graph.

Parameters:

object - the object to test

asNode - true if object is a node, false if object is an edge

Returns:

life cycle state, one of PERSISTENT, PERSISTENT_DELETED, TRANSIENT

getMainState

GraphState getMainState()

Returns the main graph state. The main graph state is the only graph state within which modifications to the graph may be done. The notification of event listeners is done in the context of this state, too.

Returns:

this graph's main graph state

See Also:

Graph

getName

java.lang.String getName(java.lang.Object object,
                         boolean asNode)

Returns a name for the given object. Names are not necessarily unique.

Parameters:

object - the object

asNode - true if object is a node, false if object is an edge

Returns:

a name

See Also:

getObjectForName(boolean, String)

getNextEdge

java.lang.Object getNextEdge(java.lang.Object edge,
                             java.lang.Object node)

Returns the edge after edge in the linked list of edges of node.

Parameters:

edge - the previous edge in the linked list

node - the common node of the edges of the linked list

Returns:

the next edge of the linked list

See Also:

Graph, getFirstEdge(Object)

getNodeForId

java.lang.Object getNodeForId(long id)

Returns the node identified by id.

Parameters:

id - an identifier

Returns:

the corresponding node, or null if id identifies no node

See Also:

getId(Object)

getObjectForName

java.lang.Object getObjectForName(boolean node,
                                  java.lang.String name)

Returns the object with the given name. If several such objects exist, one of them is chosen in an unspecified manner. If no such object exists, null is returned.

Parameters:

node - true if a node of the given name is to be found, false if an edge is to be found

name - the name of the object

Returns:

an object of the given kind (node or edge) with the given name, or null if no such object exists

See Also:

getName(Object, boolean)

getParentAttribute

ObjectAttribute getParentAttribute()

Defines the derived attribute which has as value the parent object.

Returns:

the parent attribute

See Also:

Graph, getTreePattern()

getRoot

java.lang.Object getRoot(java.lang.String key)

Returns the root node for the given root key.

Parameters:

key - a root key, one of getRootKeys()

Returns:

the root node of the graph identified by key, or null if no such root node exists

See Also:

Graph

getRootKeys

java.lang.String[] getRootKeys()

Returns the root keys for the graph.

Returns:

an array of root keys

See Also:

Graph, getRoot(String)

getSourceNode

java.lang.Object getSourceNode(java.lang.Object edge)

Returns the source node of edge.

Parameters:

edge - an edge

Returns:

the source node

See Also:

Graph

getSpecialEdgeDescriptors

SpecialEdgeDescriptor[] getSpecialEdgeDescriptors(java.lang.Object node,
                                                  boolean asSource)

getStamp

int getStamp()

Returns a modification stamp for the whole graph. Each modification increments the value, so that the test whether some modification occured can be simply performed on values of the stamp.

Returns:

a stamp for the whole graph

getStateMap

java.util.Map getStateMap()

getSymbol

int getSymbol(java.lang.Object object,
              boolean asNode)

getTargetNode

java.lang.Object getTargetNode(java.lang.Object edge)

Returns the target node of edge.

Parameters:

edge - an edge

Returns:

the target node

See Also:

Graph

getTreePattern

EdgePattern getTreePattern()

Defines the pattern used for the construction of this graph's tree.

Returns:

an edge pattern

See Also:

Graph, getParentAttribute()

removeAttributeChangeListener

void removeAttributeChangeListener(AttributeChangeListener l)

removeAttributeChangeListener

void removeAttributeChangeListener(java.lang.Object object,
                                   boolean asNode,
                                   AttributeChangeListener l)

removeChangeBoundaryListener

void removeChangeBoundaryListener(ChangeBoundaryListener l)

removeEdgeChangeListener

void removeEdgeChangeListener(EdgeChangeListener l)

removeEdgeChangeListener

void removeEdgeChangeListener(java.lang.Object object,
                              boolean asNode,
                              EdgeChangeListener l)