Package nl.tue.astar

Interface AStarThread<H extends Head,​T extends Tail>

  • Type Parameters:
    H -
    T -
    All Known Subinterfaces:
    ObservableAStarThread<H,​T>
    All Known Implementing Classes:
    AbstractAStarThread, AStarThread.CPUEfficient, AStarThread.MemoryEfficient
    public interface AStarThread<H extends Head,​T extends Tail>
    Interface for computing one (or more) alignments between a trace and a model. After instantiation, the sorting and priority queue ordering should be set before any call to getOptimalRecord. On the first call to getOptimalRecord, the AStar algorithm is used to compute an optimal alignment between a model and a trace. The possible moves in every state are computed using the delegate. When finished, a record is always returned. If wasReliable() returns true, then the record is indeed an optimal one, otherwise it is a best-guess. As long as wasReliable() returns true, more alignments can be computed by repeated calls to getOptimalRecord(C, i), where i is the cost of the previous optimal record. This way, the algorithm quarantees that all states which are on a shortest path from the source to the target node will be visisted (note that this does not imply that all paths will be found).
    Author:
    bfvdonge

    • Method Detail

      • getTrace

        Trace getTrace()
        Returns the trace for which this AStarThread was instantiated.
        Returns:

      • getDelegate

        Delegate<H,​T> getDelegate()
        returns the delegate used for determining the possible moves during replay.
        Returns:

      • getOptimalRecord

        Record getOptimalRecord​(AStarThread.Canceller c)
                 throws AStarException
        Returns a Record for an optimal alignment. If no optimal alignment exists, or if none is found in time, a "best guess" is returned. To check whether the returned alignment is optimal, the method isReliable() can be used. To make sure you investigated the entire graph from which the (a) final node is reachable, keep calling the method getOptimalRecord(c, stopAt) with the stopAt cost equal to the total cost of the first record. When doing so until the first unreliable result, the entire search space is covered.
        Parameters:
        c -
        Returns:
        Throws:
        java.lang.Exception
        AStarException

      • getOptimalRecord

        Record getOptimalRecord​(AStarThread.Canceller c,
                        int stopAt)
                 throws AStarException
        Returns a Record for an optimal alignment. If no optimal alignment exists, if none is found in time or if the cost of an optimal alignment is higher than stopAt a "best guess" is returned. To check whether the returned alignment is optimal, the method isReliable() can be used. To make sure you investigated the entire graph from which the (a) final node is reachable, keep calling the method getOptimalRecord(c, stopAt) with the stopAt cost equal to the total cost of the first record. When doing so until the first unreliable result, the entire search space is covered.
        Parameters:
        c -
        Returns:
        Throws:
        java.lang.Exception
        AStarException

      • getQueuedStateCount

        int getQueuedStateCount()
        Returns the number of nodes queueud. This is at least the number of nodes visisted, but can be higher due to updates.
        Returns:

      • getTraversedArcCount

        int getTraversedArcCount()
        Returns the number of arcs that were traversed in the statespace.
        Returns:

      • getVisitedStateCount

        int getVisitedStateCount()
        Returns the number of visited states.
        Returns:

      • setPreferBreadth

        void setPreferBreadth​(boolean preferBreadth)
        By default, depth is preferred. With a call to preferBreadth, this can be changed. The internal priority queue is changed, such that if depth is preferred, then records with the same total costs are sorted according to their cost so far, with the highest cost first. If breadth is preferred, then records with the same total costs are sorted with lowest cost so far first. This call should be placed before any call to any of the run methods.
        Parameters:
        preferBreath -

      • getPreferBreadth

        boolean getPreferBreadth()

      • setASynchronousMoveSorting

        void setASynchronousMoveSorting​(AStarThread.ASynchronousMoveSorting sorting)
        When aligning a trace with a model, any moves between two synchronous moves can be sorted. When sorting is set to LOGMOVEFIRST, then no logMove can ever follow a modelMove. If sorting is set to ModelMoveFirst, then no modelMove can ever follow a logMove. The default is LOGMOVEFIRST;
        Parameters:
        sorting -

      • wasReliable

        boolean wasReliable()
        After a call to run(), this method returns true if the returned Record yields the optimal result. If this method returns false, then the returned Record was subOptimal, for example because the maximum state count was reached, of because no solution was found. The Record returned by the previous call to run should be considered as a best guess.
        Returns:

      • setType

        void setType​(AStarThread.Type type)
        Sets the type of the AStar algorithm. Can be changed during execution, however if type is set to any weighted variant, the epsilon and expected length should be set.
        Parameters:
        type -

      • setEpsilon

        void setEpsilon​(double epsilon)
        Set epsilon for the weighted variants of A Star
        Parameters:
        epsilon -

      • setExpectedLength

        void setExpectedLength​(int length)
        Set expected length for the dynamic weighted variant of A Star
        Parameters:
        length -