Overview | Package | Class | Tree | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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)

Overview | Package | Class | Tree | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD