Module de.learnlib.filter.reuse
Package de.learnlib.filter.reuse.tree

Class ReuseTree<S,​I,​O>

  • Type Parameters:
    S - system state type
    I - input symbol type
    O - output symbol type
    All Implemented Interfaces:
    Iterable<ReuseNode<S,​I,​O>>, net.automatalib.automaton.concept.FiniteRepresentation, net.automatalib.graph.Graph<ReuseNode<S,​I,​O>,​ReuseEdge<S,​I,​O>>, net.automatalib.graph.IndefiniteGraph<ReuseNode<S,​I,​O>,​ReuseEdge<S,​I,​O>>, net.automatalib.graph.IndefiniteSimpleGraph<ReuseNode<S,​I,​O>>, net.automatalib.graph.SimpleGraph<ReuseNode<S,​I,​O>>
    public final class ReuseTree<S,​I,​O>
extends Object
implements net.automatalib.graph.Graph<ReuseNode<S,​I,​O>,​ReuseEdge<S,​I,​O>>
    The ReuseTree is a tree like structure consisting of nodes (see ReuseNode) and edges (see ReuseEdge) that is used by the ReuseOracle:
    • Nodes may contain a system state (see ReuseNode.fetchSystemState(boolean)) that could be used for executing suffixes of membership queries. Each node consists of a (possible empty) set of outgoing edges.
    • Edges consists beside source and target node of input and output behavior.
    The ReuseTree is the central data structure that maintains observed behavior from the SUL and maintains also available system states. The ReuseTree is only 'tree like' since it may contain reflexive edges at nodes (only possible if ReuseTreeBuilder.withFailureOutputs(Set) or ReuseTreeBuilder.withInvariantInputs(Set) is set).

    • Method Detail

      • getOutput

        public @Nullable net.automatalib.word.Word<O> getOutput​(net.automatalib.word.Word<I> query)
        Returns the known output for the given query or null if not known.
        Parameters:
        query - the query
        Returns:
        The output for query if already known from the ReuseTree or null if unknown.

      • getPartialOutput

        public net.automatalib.word.Word<@Nullable O> getPartialOutput​(net.automatalib.word.Word<I> query)
        Returns the known output for "reflexive" edges in the tree for the given query. All other symbols are set to null.
        Parameters:
        query - the query
        Returns:
        The partial output for query from the ReuseTree with outputs for "reflexive" edges filled with null for "non-reflexive" and not-known parts of the input word.

      • disposeSystemStates

        public void disposeSystemStates()
        This method removes all system states from the tree. The tree structure remains, but there will be nothing for reuse.

        The SystemStateHandler will be informed about all disposals.

      • clearTree

        public void clearTree()
        Clears the whole tree which means the root will be reinitialized by a new ReuseNode and all existing system states will be disposed. All invariant input symbols as well as all failure output symbols will remain.

        The SystemStateHandler will not be informed about any disposings.

      • fetchSystemState

        public @Nullable ReuseNode.NodeResult<S,​I,​O> fetchSystemState​(net.automatalib.word.Word<I> query)
        Returns a reusable ReuseNode.NodeResult with system state accessed by the given access sequence. or null if none such exists.
        Parameters:
        query - the access sequence to the node
        Returns:
        the node accessed by the given query, null if no such node exists

      • insert

        public void insert​(net.automatalib.word.Word<I> query,
                   ReuseCapableOracle.QueryResult<S,​O> queryResult)
        Inserts the given Word with ReuseCapableOracle.QueryResult into the tree starting from the root node of the tree. For the longest known prefix of the given Word there will be no new nodes or edges created.

        Will be called from the ReuseOracle if no system state was available for reuse for the query (otherwise insert(Word, ReuseNode, ReuseCapableOracle.QueryResult) would be called). The last node reached by the last symbol of the query will hold the system state from the given ReuseCapableOracle.QueryResult.

        This method should only be invoked internally from the ReuseOracle unless you know exactly what you are doing (you may want to create a predefined reuse tree before start learning).

        Parameters:
        query - the query determining a path in the tree
        queryResult - the output that should be associated with the given path
        Throws:
        ReuseException - if non-deterministic behavior is detected

      • insert

        public void insert​(net.automatalib.word.Word<I> query,
                   ReuseNode<S,​I,​O> sink,
                   ReuseCapableOracle.QueryResult<S,​O> queryResult)
        Inserts the given Word (suffix of a membership query) with ReuseCapableOracle.QueryResult (suffix output) into the tree starting from the ReuseNode (contains prefix with prefix output) in the tree. For the longest known prefix of the suffix from the given Word there will be no new nodes or edges created.

        Will be called from the ReuseOracle if an available system state was reused for the query (otherwise insert(Word, ReuseCapableOracle.QueryResult) would be called). The old system state was already removed from the ReuseNode (through fetchSystemState(Word)) if the ''invalidateSystemstates'' flag in the ReuseOracle was set to true.

        This method should only be invoked internally from the ReuseOracle unless you know exactly what you are doing (you may want to create a predefined reuse tree before start learning).

        Parameters:
        query - the query determining a path in the tree
        sink - the starting node of the path
        queryResult - the output that should be associated with the given path
        Throws:
        ReuseException - if non-deterministic behavior is detected

      • getNodes

        public Collection<ReuseNode<S,​I,​O>> getNodes()
        Specified by:
        getNodes in interface net.automatalib.graph.SimpleGraph<S>

      • getOutgoingEdges

        public Collection<ReuseEdge<S,​I,​O>> getOutgoingEdges​(ReuseNode<S,​I,​O> node)
        Specified by:
        getOutgoingEdges in interface net.automatalib.graph.Graph<S,​I>

      • getTarget

        public ReuseNode<S,​I,​O> getTarget​(ReuseEdge<S,​I,​O> edge)
        Specified by:
        getTarget in interface net.automatalib.graph.IndefiniteGraph<S,​I>

      • getVisualizationHelper

        public net.automatalib.visualization.VisualizationHelper<ReuseNode<S,​I,​O>,​ReuseEdge<S,​I,​O>> getVisualizationHelper()
        Specified by:
        getVisualizationHelper in interface net.automatalib.graph.Graph<S,​I>
        Specified by:
        getVisualizationHelper in interface net.automatalib.graph.SimpleGraph<S>