Module graph
Package de.grogra.graph

Interface Graph

All Superinterfaces:
Lockable
All Known Implementing Classes:
AttributeOverwritingFilter, GraphBase, GraphFilter, GraphManager, HighlightFilter, TopologyGraph
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:

  • Field Details

  • Method Details

    • 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:

    • 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

    • getRootKeys

      String[] getRootKeys()
      Returns the root keys for the graph.
      Returns:
      an array of root keys
      See Also:

    • getRoot

      Object getRoot(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:

    • getFirstEdge

      Object getFirstEdge(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:

    • getNextEdge

      Object getNextEdge(Object edge, 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:

    • getSourceNode

      Object getSourceNode(Object edge)
      Returns the source node of edge.
      Parameters:
      edge - an edge
      Returns:
      the source node
      See Also:

    • getTargetNode

      Object getTargetNode(Object edge)
      Returns the target node of edge.
      Parameters:
      edge - an edge
      Returns:
      the target node
      See Also:

    • getLifeCycleState

      int getLifeCycleState(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

    • getId

      long getId(Object node)
      Returns a unique identifier for the given node.
      Parameters:
      node - a node
      Returns:
      the node's unique identifier
      See Also:

    • getNodeForId

      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:

    • getName

      String getName(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

      Object getObjectForName(boolean node, 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:

    • getEdgeBits

      int getEdgeBits(Object edge)
      Returns the edge bits of an edge.
      Parameters:
      edge - the edge
      Returns:
      the edge's edge bits
      See Also:

    • getAttributes

      Attribute[] getAttributes(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

    • getDependent

      Attribute[] getDependent(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

    • getAccessor

      AttributeAccessor getAccessor(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

    • getInstantiator

      Instantiator getInstantiator(Object node)

    • accept

      void accept(Object startNode, Visitor visitor, ArrayPath placeInPath)

    • getStateMap

      Map getStateMap()

    • createBooleanMap

      BooleanMap createBooleanMap()

    • createObjectMap

      <V> ObjectMap<V> createObjectMap()

    • getParentAttribute

      ObjectAttribute getParentAttribute()
      Defines the derived attribute which has as value the parent object.
      Returns:
      the parent attribute
      See Also:

    • getTreePattern

      EdgePattern getTreePattern()
      Defines the pattern used for the construction of this graph's tree.
      Returns:
      an edge pattern
      See Also:

    • getSpecialEdgeDescriptors

      SpecialEdgeDescriptor[] getSpecialEdgeDescriptors(Object node, boolean asSource)

    • getDescription

      Object getDescription(Object object, boolean asNode, 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

    • getSymbol

      int getSymbol(Object object, boolean asNode)

    • getColor

      int getColor(Object object, boolean asNode)

    • addChangeBoundaryListener

      void addChangeBoundaryListener(ChangeBoundaryListener l)

    • removeChangeBoundaryListener

      void removeChangeBoundaryListener(ChangeBoundaryListener l)

    • addAttributeChangeListener

      void addAttributeChangeListener(AttributeChangeListener l)

    • removeAttributeChangeListener

      void removeAttributeChangeListener(AttributeChangeListener l)

    • addEdgeChangeListener

      void addEdgeChangeListener(EdgeChangeListener l)

    • removeEdgeChangeListener

      void removeEdgeChangeListener(EdgeChangeListener l)

    • addAttributeChangeListener

      void addAttributeChangeListener(Object object, boolean asNode, AttributeChangeListener l)

    • removeAttributeChangeListener

      void removeAttributeChangeListener(Object object, boolean asNode, AttributeChangeListener l)

    • addEdgeChangeListener

      void addEdgeChangeListener(Object object, boolean asNode, EdgeChangeListener l)

    • removeEdgeChangeListener

      void removeEdgeChangeListener(Object object, boolean asNode, EdgeChangeListener l)