======================= Exchangeable components ======================= * :ref:`dev_guide_input` * :ref:`dev_guide_qa` * :ref:`dev_guide_estimation` * **Search component** * :ref:`dev_guide_output` .. image:: ../images/components/component_overview_search.png :alt: Search component overview .. _dev_guide_search: Search component ================ The *Search* component controls how the search space (modeled as a tree-like graph structure) is traversed, i.e., which nodes to approximate and validate next and when to terminate the approximation process. This also means that the *Search* component must manage already visited nodes, soon to be visited nodes, and "anomalies" in the search space, such as recurring circuit configurations, on its own. Structure of the search space ----------------------------- .. image:: ../images/term_definition.pdf :width: 80% :alt: Term definitions To talk about the concepts of the search space more efficiently, we first define some terms and explain their meaning. The figure above visualizes the terms. :*Candidate*: A *candidate* is a part of the input circuit which can be approximated independently and then inserted back into the input circuit to replace its own original variant, thereby creating an approximated version of the whole input circuit. The *set of candidates* of the input circuit is generated during the *Input* stage before the approximation process begins. For each candidate there must be at least one *approximation method* and at least one *error metric* with an upper bound specified. :*Variant*: We denote an approximated version of a candidate as *variant*. Each variant has a unique candidate, but candidates generally have multiple variants. The original, non-approximated version of a candidate is called *original variant*. Variants are uniquely identified by the ID of their candidate in conjunction with an error bound for each error metric and exactly one approximation method. :*Circuit configuration*: Assume the input circuit has the candidates :math:`(C_1,C_2,\ldots,C_n)` and each candidate :math:`C_j` can be represented by one of its variants :math:`\{V_{1}^{(j)},V_{2}^{(j)},\ldots,V_{m}^{(j)}\}`. We call the tuple of variants :math:`\left(V_{x}^{(1)},V_{y}^{(2)},\ldots,V_{z}^{(n)}\right)` the *configuration* of the circuit in which each candidate :math:`C_j` is replaced by one of its variants :math:`V_{i}^{(j)}`. A circuit configuration is unique. :*Node*: A *node* in the search space represents a single circuit configuration :math:`\left(V_{x}^{(1)},V_{y}^{(2)},\ldots,V_{z}^{(n)}\right)` and is treated as a node (or vertex) in a graph. It is connected to its *parent node* and to its *child nodes* (or *children*) once they are created. The children of a node represent circuit configurations which differ from the node (their *parent node*) in exactly one variant, i.e., one variant :math:`V_{i}^{(j)}` is replaced by another variant of that candidate :math:`C_j` and all other variants remain the same. The new variant of that candidate is not arbitrary, but must have either a different approximation method or a single error bound increased by one step. Note that nodes representing the same configuration can be created by different parent nodes, so that some nodes in the search space may have multiple parent nodes (this is the reason why the search space is not really a tree). The node representing the circuit configuration with only original variants is called the *root node*. It does not have a parent node. Nodes are represented by ``Node`` instances which contain all necessary information about the circuit configuration represented by the graph node. A ``Node`` instance can generate its children with the ``generateChildren`` method. These nodes are freshly generated each time the method is called and neither do they have any file representations nor are they stored in any data structure, i.e., at first, they are temporary objects iwth the minimal required information. The search can then decide whether these nodes are generated by the approximation stage or simply discarded. Functions ========= .. .. todo:: Add links to function documentations ``setup(gen_info: GeneralInformation, root_node: Node): None`` -------------------------------------------------------------- The ``setup`` method can be used to initialize the component by storing the ``GeneralInformation`` instance and the search space's root node. The default implementation does exactly these two things. This is where you should initialize data structures and variables based on the ``CandidateSet`` instance in ``GeneralInformation``, which is complete at this point and defines all possible circuit configurations that can occur in the search space. ``hasTerminated(): Boolean`` ---------------------------- This is a simple query issued at the start of every iteration. It should return ``True`` if and only if the search has finished and there is nothing left for the component to do. When this happens, the approximation process stops and the output is generated. .. note:: Note that by implementing this method incorrectly you can run into an infinite loop, so make sure to double check your termination conditions! ``popNextNode(): Node`` ----------------------- The ``popNextNode`` method is called once at the start of every iteration and it will return one ``Node`` instance. The returned instance is validated by the *QualityAssurance* component. Only if it is validated successfully, the other methods of the *Search* component are called in that iteration. With this in mind, you should implement your *Search* component in a way that supports multiple consecutive calls of this function. In the context of the search space graph, the returned ``Node`` marks the current position in the search space. Note that, if it is validated successfully, you can use this fact to generate new nodes from this position to explore the search space step by step. ``expandSearchSpace(): List`` ----------------------------------- The ``expandSearchSpace`` method is the first method which is called if a node was successfully validated. It returns a list of newly generated ``Node`` instances which will then be approximated and analyzed, i.e., they will receive files for their variants and circuits and their ``stats`` dictionaries will be filled with values for the metrics supported by the *Estimation* component. To create a better intuition for the purpose of this method, imagine a search space tree with only the current node in it. The ``expandSearchSpace`` method returns a list of all hidden nodes which are possible candidates for exploration in the next iterations and marks them for the other components so they can discover them and fill them with information. In many cases, it makes sense to simply return the children of the current node. ``evaluateNodes(): None`` ------------------------- The ``evaluateNodes`` method is called at the end of each iteration if the current node was validated successfully. It gives you the chance to process the results of the *Approximation* and *Estimation* stage before ``popNextNode`` is called again. The ``Node``\ s that were returned by ``expandSearchSpace`` have now been approximated and filled with statistics to evaluate. As a rule of thumb, in this method you should create a sorted list of all ``Node``\ s you want to validate, using the statistics generated by the *Estimation* component. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :ref:`Back to the Developer Guide `