Module xl.impl
Package de.grogra.xl.impl.base

Class Graph

java.lang.Object
de.grogra.xl.impl.base.Graph
All Implemented Interfaces:
Graph, Cloneable
Direct Known Subclasses:
GraphImpl, RGGGraph
public abstract class Graph extends Object implements Graph, Cloneable
This class is an abstract base class for implementations of XL's runtime model for graph-like structures. Graph represents a single graph on which XL's query statements may operate.

The package documentation contains more information about the structure of the graph that is implied by this base class.

The current derivation mode for rule applications acting on this graph is set by setDerivationMode(int) and may be truly parallel (PARALLEL_MODE), parallel and non-deterministic (PARALLEL_NON_DETERMINISTIC_MODE, one application is chosen out of several applications which delete the same node), sequential (SEQUENTIAL_MODE, only the first rule application per derivation step is used), or sequential and non-deterministic (SEQUENTIAL_NON_DETERMINISTIC_MODE, only one rule application per derivation step is used).

Author:
Ole Kniemeyer

  • Field Details

    • PARALLEL_MODE

      public static final int PARALLEL_MODE
      Bit mask for getDerivationMode() indicating a true parallel derivation mode. All rules are applied via every possible match in parallel. A single node may be deleted by several rule applications.
      See Also:

    • PARALLEL_NON_DETERMINISTIC_MODE

      public static final int PARALLEL_NON_DETERMINISTIC_MODE
      Bit mask for getDerivationMode() indicating a parallel non-deterministic derivation mode. It is ensured that a single node is deleted by at most one actual rule application. If several potential rule applications delete the same node, one actual application is chosen pseudo-randomly.
      See Also:

    • SEQUENTIAL_MODE

      public static final int SEQUENTIAL_MODE
      Bit mask for getDerivationMode() indicating a sequential derivation mode. Only one rule application is performed in a single step (as marked by derive()). If several applications are possible, only the first one is chosen.
      See Also:

    • SEQUENTIAL_NON_DETERMINISTIC_MODE

      public static final int SEQUENTIAL_NON_DETERMINISTIC_MODE
      Bit mask for getDerivationMode() indicating a sequential derivation mode. Only one rule application is performed in a single step (as marked by derive()). If several applications are possible, one is chosen pseudo-randomly.
      See Also:

    • MODE_MASK

      public static final int MODE_MASK
      Mask for getDerivationMode() to obtain the mode part (one of PARALLEL_MODE, PARALLEL_NON_DETERMINISTIC_MODE, SEQUENTIAL_MODE, SEQUENTIAL_NON_DETERMINISTIC_MODE).
      See Also:

    • INTERPRETIVE_FLAG

      public static final int INTERPRETIVE_FLAG
      Bit mask for getDerivationMode() which indicates that rules have to be applied as interpretive rules.
      See Also:

    • EXCLUDE_DELETED_FLAG

      public static final int EXCLUDE_DELETED_FLAG
      Bit mask for getDerivationMode() which indicates that nodes which were already deleted by previous rule applications of the current derivation step shall be excluded from further matches of the same step.
      See Also:

  • Constructor Details

  • Method Details

    • getThreadData

      protected Graph.ThreadData getThreadData()

    • createThreadData

      protected Graph.ThreadData createThreadData()

    • getModel

      public RuntimeModel getModel()
      Description copied from interface: Graph
      Returns this graph's run-time model.
      Specified by:
      getModel in interface Graph
      Returns:
      the run-time model

    • createQueue

      protected abstract GraphQueue createQueue(QueueCollection qc, QueueDescriptor descr)

    • createQueryState

      public Graph.QState createQueryState()
      Description copied from interface: Graph
      Creates a query state to be used for queries which use this graph. The returned query state has to be an instance of the type defined by CompiletimeModel.getQueryStateType() of the corresponding compile-time model.
      Specified by:
      createQueryState in interface Graph
      Returns:
      a new query state

    • allowNoninjectiveMatchesByDefault

      public void allowNoninjectiveMatchesByDefault(boolean value)

    • allowNoninjectiveMatchesForNextQuery

      @Deprecated public void allowNoninjectiveMatchesForNextQuery(boolean value)
      Deprecated.

    • getDerivationMode

      public int getDerivationMode()
      Returns the current derivation mode. This is a combination of one of the bit masks PARALLEL_MODE, PARALLEL_NON_DETERMINISTIC_MODE, SEQUENTIAL_MODE, SEQUENTIAL_NON_DETERMINISTIC_MODE with the flags INTERPRETIVE_FLAG and EXCLUDE_DELETED_FLAG.
      Returns:
      current derivation mode
      See Also:

    • setDerivationMode

      public void setDerivationMode(int mode)
      Sets the current derivation mode. mode is a combination of the bit masks PARALLEL_MODE, PARALLEL_NON_DETERMINISTIC_MODE, SEQUENTIAL_MODE, SEQUENTIAL_NON_DETERMINISTIC_MODE with the flags INTERPRETIVE_FLAG and EXCLUDE_DELETED_FLAG.
      Parameters:
      mode - desired derivation mode
      See Also:

    • derive

      public long derive()

    • beginModifications

      protected abstract void beginModifications()

    • commitModifications

      protected abstract void commitModifications()

    • getQueues

      public QueueCollection getQueues()

    • canEnumerateNodes

      public boolean canEnumerateNodes(Type type)
      Description copied from interface: Graph
      Can nodes of the specified type be enumerated? This method returns true iff this graph can enumerate nodes of the given type using the method Graph.enumerateNodes(de.grogra.reflect.Type, de.grogra.xl.query.QueryState, int, de.grogra.xl.query.MatchConsumer, int).
      Specified by:
      canEnumerateNodes in interface Graph
      Parameters:
      type - the type of nodes
      Returns:
      true iff nodes of type can be enumerated

    • enumerateEdges

      public void enumerateEdges(Object node, EdgeDirection dir, Type edgeType, QueryState qs, int toIndex, int patternIndex, Serializable pattern, int matchIndex, MatchConsumer consumer, int arg)
      Specified by:
      enumerateEdges in interface Graph

    • getPredecessor

      protected Object getPredecessor(Object node)

    • createMatcher

      public Pattern.Matcher createMatcher(Pattern pred, XBitSet providedConstants, IntList neededConstantsOut)
      Specified by:
      createMatcher in interface Graph

    • enumerateSpaces

      public void enumerateSpaces(Object node, EdgeDirection dir, Type edgeType, QueryState qs, int toIndex, int patternIndex, Serializable pattern, int matchIndex, MatchConsumer consumer, int arg)
      Searches the graph (with reference to the type graph) for matching multiscale patterns
      Specified by:
      enumerateSpaces in interface Graph
      Parameters:
      node - node already bound before this spacing
      dir - edge direction
      edgeType - class type of edge, normally int
      qs - QueryState instance
      toIndex -
      patternIndex -
      pattern - edge pattern, i.e. successor, branching, refinement, etc.
      matchIndex -
      consumer - CompoundPattern instance for continuing match logic
      arg -

    • isInTypeGraph

      public boolean isInTypeGraph(Object node)
      Check if a node is in the type graph
      Parameters:
      node -
      Returns:
      true if input node is part of the type graph, false otherwise

    • sortedTypeGraph

      public HashMap<Object,Integer> sortedTypeGraph()
      Description copied from interface: Graph
      Returns the ordered scale values of the nodes in the type graph
      Specified by:
      sortedTypeGraph in interface Graph
      Returns:
      HashMap instance containing mappings from the type graph nodes to scale values

    • getScaleValue

      public int getScaleValue(HashMap<Object,Integer> sortedTypeGraph, Object node)

    • getTypeNode

      public Object getTypeNode(Type t)

    • getTypeNode

      public Object getTypeNode(Object node)
      Get node in type graph representing the type of the input node
      Parameters:
      node -
      Returns:
      node from type graph representing type of input node

    • areComparableScales

      public boolean areComparableScales(Object nodeA, Object nodeB)

    • isSameScale

      public boolean isSameScale(Object nodeA, Object nodeB)
      Checks if 2 nodes are in the same scale in the type graph.
      Parameters:
      nodeA -
      nodeB -
      Returns:

    • getMinimumEncoarseDepthDiff

      public int getMinimumEncoarseDepthDiff(Object coarseNode, Object fineNode)
      Returns the length of the shortest encoarsement path from fineNode to coarseNode
      Parameters:
      coarseNode -
      fineNode -
      Returns:
      length of path, 0 if coarseNode is not encoarsement of fineNode, -1 if error