<!--
  - Authors:
  -   Christian Schulte <schulte@ps.uni-sb.de>
  -
  - Copyright:
  -   Christian Schulte, 1998
  -
  - Last change:
  -   $Date$ by $Author$
  -   $Revision$
  -
  - This file is part of Mozart, an implementation
  - of Oz 3
  -    http://www.mozart-oz.org
  -
  - See the file "LICENSE" or
  -    http://www.mozart-oz.org/LICENSE.html
  - for information on usage and redistribution
  - of this file, and for a DISCLAIMER OF ALL
  - WARRANTIES.
  -
  -->

<chapter id="chapter.tree">
  <Title/The Search Tree/

  <P>
    <Figure id="figure.nodes">
      <Caption/Nodes in the search tree./
      <Table id="figure.nodes.table">
        <Tr>
          <Th>Node</Th>
          <Th>Kind</Th>
          <Th Colspan=2>Color</Th>
          <Th Colspan=2>BW</Th>
        </Tr>
        <Tr>
          <Td>choice</Td>
          <Td>open</Td>
          <Td><Picture.Extern id="pic.c-open"
			      inline to="pictures/c-open.ps.gz" type=ps info="-width 40"></Td>
          <Td>light blue</Td>
          <Td><Picture.Extern id="pic.b-open"
			      inline to="pictures/b-open.ps.gz" type=ps info="-width 40"></Td>
          <Td>thin border</Td>
        </Tr>
        <Tr>
          <Td>choice</Td>
          <Td>closed</Td>
          <Td><Picture.Extern id="pic.c-closed"
			      inline to="pictures/c-closed.ps.gz" type=ps info="-width 40"></Td>
          <Td>blue</Td>
          <Td><Picture.Extern id="pic.b-closed"
			      inline to="pictures/b-closed.ps.gz" type=ps info="-width 40"></Td>
          <Td>thick border</Td>
        </Tr>
        <Tr>
          <Td>solved</Td>
          <Td>suspended</Td>
          <Td><Picture.Extern id="pic.c-suspended"
			      inline to="pictures/c-suspended.ps.gz" type=ps info="-width 40"></Td>
          <Td>light green</Td>
          <Td><Picture.Extern id="pic.b-suspended"
			      inline to="pictures/b-suspended.ps.gz" type=ps info="-width 40"></Td>
          <Td>thin border</Td>
        </Tr>
        <Tr>
          <Td>solved</Td>
          <Td>entailed</Td>
          <Td><Picture.Extern id="pic.c-entailed"
			      inline to="pictures/c-entailed.ps.gz" type=ps info="-width 40"></Td>
          <Td>green</Td>
          <Td><Picture.Extern id="pic.b-entailed"
			      inline to="pictures/b-entailed.ps.gz" type=ps info="-width 40"></Td>
          <Td>thick border</Td>
        </Tr>
        <Tr>
          <Td>failed</Td><td><p.silent>&nbsp;</td>
          <Td><Picture.Extern id="pic.c-failed"
			      inline to="pictures/c-failed.ps.gz" type=ps info="-width 40"></Td>
          <Td>red</Td>
          <Td><Picture.Extern id="pic.b-failed"
			      inline to="pictures/b-failed.ps.gz" type=ps info="-width 40"></Td>
          <Td>thin border</Td>
        </Tr>
        <Tr>
          <Td>suspended</Td><td><p.silent>&nbsp;</td>
          <Td><Picture.Extern id="pic.c-blocked"
			      inline to="pictures/c-blocked.ps.gz" type=ps info="-width 40"></Td>
          <Td>orange</Td>
          <Td><Picture.Extern id="pic.b-blocked"
			      inline to="pictures/b-blocked.ps.gz" type=ps info="-width 40"></Td>
          <Td>thin border</Td>
        </Tr>
      </Table>
    </Figure>
  </P>

  <P>
    <Ptr to="figure.nodes"> sketches how the different nodes
    are drawn by the Explorer.
  </P>

  <Para Class=Apropos><Title/Choice nodes/
    Choice nodes are drawn as circles.  A choice node is <Em/closed/,
    if all of its direct descendants are explored, otherwise it is
    <Em/open/.
  </Para>

  <Para Class=Apropos><Title/Solved nodes/
    Solved nodes are drawn as diamonds. The Explorer distinguishes
    between nodes corresponding to <Em/entailed/ (i.e., spaces where
    no actors and propagators are left) or <Em/suspended/ (i.e.,
    spaces where actors or propagators are left) computation spaces.
  </Para>

  <Para Class=Apropos><Title/Failed nodes/
    Failed nodes are drawn as rectangular boxes.
  </Para>

  <Para Class=Apropos><Title/Suspended nodes/
    Suspended nodes are drawn as stars. If the search tree contains a
    suspended node, it cannot be further explored. If the corresponding
    computation space becomes stable, the node will change to a node
    corresponding to the now stable space.
  </Para>

  <P>
  <Figure id="figure.trees">
    <Caption/Hidden subtrees in the search tree./
      <Table id="figure.trees.table">
        <Tr>
          <Th>Explored</Th>

          <Th>Solutions</Th>
          <Th Colspan=2>Color</Th>
        </Tr>
        <Tr>
          <Td>partially</Td>
          <Td>yes</Td>
          <Td><Picture.Extern id="pic.c-h-part-solved"
			      inline to="pictures/c-h-part-solved.ps.gz" type=ps info="-width 40"></Td>
          <Td>light green</Td>
        </Tr>
        <Tr>
          <Td>partially</Td>
          <Td>no</Td>
          <Td><Picture.Extern id="pic.c-h-part-failed"
			      inline to="pictures/c-h-part-failed.ps.gz" type=ps info="-width 40"></Td>
          <Td>purple</Td>
        </Tr>
        <Tr>
          <Td>fully</Td>
          <Td>yes</Td>
          <Td><Picture.Extern id="pic.c-h-solved"
			      inline to="pictures/c-h-solved.ps.gz" type=ps info="-width 40"></Td>
          <Td>green</Td>
        </Tr>
        <Tr>
          <Td>fully</Td>
          <Td>no</Td>
          <Td><Picture.Extern id="pic.c-h-failed"
			      inline to="pictures/c-h-failed.ps.gz" type=ps info="-width 40"></Td>
          <Td>red</Td>
        </Tr>
      </Table>
  </Figure>
  </P>

  <Para Class=Apropos><Title/Hidden subtrees/
    Besides of nodes, the search tree may also contain hidden
    subtrees. Hidden subtrees are drawn as triangles, see <Ptr
    to="figure.trees">. More on hiding subtrees can be 
    found in <Ptr to="section.menu.hide">.
  </Para>

  <P>
    <Note.gui icon="note-gui-l1.gif" info="Left mouse click"/Selecting nodes/
    Choice nodes, solved nodes, and hidden subtrees can be selected by
    clicking on them with the left mouse button. The selected node is
    drawn shadowed (See also <Ptr to="chapter.interface">).
  </P>

  <Para Class=Apropos><Title/Numbered nodes/
    Invoking an action on a node marks the node
    with a number. For invoking actions see 
	<Ptr to="section.menu.nodes">.
  </Para>

</chapter>





