m-gist.tex.in

% -*- mode: LaTeX; -*- 
\chapter{Gist}
\label{chap:m:gist}

The Graphical Interactive Search Tool, Gist, provides
user-controlled search, search tree visualization, and inspection
of arbitrary nodes in the search tree. Gist can be helpful when
experimenting with different branching strategies, with different
models for the same problem (for instance adding redundant
constraints), or with propagation strength (for instance bounds
versus domain propagation). It gives you direct feedback how the
search tree looks like, if your branching heuristic works, or
where propagation is weaker than you expected.

\paragraph{Overview.}

How the search tree of a problem is used as the central metaphor
in Gist is sketched in \autoref{sec:m:gist:tree}.
\autoref{sec:m:gist:invoke} explains how to invoke Gist, whereas
\autoref{sec:m:gist:use} explains how to use Gist.

\begin{important}
Do not forget to add
\begin{code}
#include <gecode/gist.hh>
\end{code}
to your program when you want to use Gist.
\end{important}

\section{The search tree}
\label{sec:m:gist:tree}

\begin{figure}
  {\parindent 0em\mbox{}\hfill
  \includegraphics[scale=.7]{images/gist_smm_full_tree_clean}\hfill
  \mbox{}}
  \caption{A search tree}
  \label{fig:m:gist:smm_full_tree_clean}
\end{figure}

The central metaphor in Gist is the \emph{search tree}. Each node
in the tree represents a fixpoint of propagation (that is, an
invocation of \?status()?, see \autoref{tip:m:started:status}).
Inner nodes stand for \emph{choices} (fixpoints with a subsequent
brancher), while leaf nodes correspond to \emph{failure} (dead
ends in the search) or \emph{solutions} of the problem.
\autoref{fig:m:gist:smm_full_tree_clean} shows a search tree as
drawn by Gist. The inner nodes (blue circles) are choices, the
red square leaf nodes are failures, and the green diamond leaf
node is a solution.

Conceptually, every node in the tree contains a corresponding space, which the user can access in order to inspect the node. Internally, Gist does not store all these spaces, but recomputes them on demand. That way, Gist can handle very large search trees (with millions of nodes) efficiently.

\section{Invoking Gist}
\label{sec:m:gist:invoke}

Gist is implemented using the \AURL{http://www.qtsoftware.com/}{Qt} application framework. It can be invoked either as a standalone component, or as part of a bigger Qt-based application.

The screenshots in this chapter show Gist running on Mac~OS~X, but the functionality, the menus and the keyboard shortcuts are the same on all platforms (with small exceptions that will be mentioned later).

\subsection{Standalone use}

\begin{figure}

  {\parindent 0em\mbox{}\hfill
  \includegraphics[width=0.45\textwidth]{images/gist_smm_init}\hfill
  \includegraphics[width=0.45\textwidth]{images/gist_smm_full_tree}\hfill
  \mbox{}}
  \caption{Gist, solving the Send More Money problem}
  \label{fig:m:gist:gist_smm}
\end{figure}

When used as a standalone component, invoking Gist merely amounts to calling
\begin{code}
  Gist::dfs(m);
\end{code}
where \?m? is a pointer to the space that contains the model to be solved. This call opens a new instance of Gist, with the root node initialized with \?m?. \autoref{fig:m:gist:gist_smm} (left) shows Gist initialized with the Send More Money puzzle from \autoref{chap:m:started}.

If you want to solve an optimization problem using branch-and-bound search, you can invoke Gist with optimization turned on:
\begin{code}
  Gist::bab(m);
\end{code}

\subsection{Use as a Qt widget}

If you are developing an application with a graphical user interface using the Qt toolkit, you can embed Gist as a widget. Either use \gecoderef[class]{Gist::GistMainWindow}, which gives you an independent widget that inherits from \?QMainWindow?, or directly embed the \gecoderef[class]{Gist::Gist} widget into your own widgets. You have to include the files \CppInline{\litstr{gecode/gist/mainwindow.hh}} for the independent widget, or \CppInline{\litstr{gecode/gist/qtgist.hh}} for the widget you can embed.

Apart from the integration into your own application, the advantage over the standalone approach is that you get access to Gist's \emph{signals} and \emph{slots}. For example, you can use more than one inspector, or you can control the search programatically instead of by user input. The details of this are beyond the scope of this document, please refer to the reference documentation of the corresponding classes for more information, and have a look at the directory \texttt{gecode/gist/standalone-example} in the Gecode source distribution.

\section{Using Gist}
\label{sec:m:gist:use}

This section gives an overview of the functionality available in Gist. Most of Gist is intuitive to use, and the easiest way of learning how to use it is to start one of the examples that come with Gecode using the \?-mode gist? commandline option, and then play around.

\subsection{Automatic search}

When you invoke Gist, it initializes the root node of the search tree, as seen in \autoref{fig:m:gist:gist_smm}. Any node that has not yet been explored by the search is drawn as a white circle, indicating that it is not yet known whether this node is in fact a choice, failure, or solution. White nodes are called \emph{open}.

Obviously, the first thing a user will then want to do is to search for a solution of the given problem. Gist provides an automatic first-solution and all-solution depth-first search engine. It can be activated from the \emph{Search} menu:

  {\parindent 0em\mbox{}\hfill
  \includegraphics[scale=.5]{images/gist_menu_search}\hfill
  \mbox{}}

If you click \emph{All solutions} (or alternatively press the \emph{A} key), Gist will explore the entire tree. The result appears in \autoref{fig:m:gist:gist_smm} (right). Depending on the preferences, Gist may collapse subtrees that contain only failed nodes (such as the rightmost subtree in the figure) into big red triangles.

The search engines always only explore the subtree under the \emph{currently selected node}, which is marked by a shadow. For example, the root node is selected after initialization, and the rightmost choice node is selected in \autoref{fig:m:gist:gist_smm} (right). A single click selects a node, and there is always exactly one selected node.

\paragraph{Stopping search after exhausting a branching.}
If you want to learn more about how your branchings affect the shape of the search tree, you can add \emph{stop branchings} to your problem using the \?Gist::stopBranch()? function. This will install a brancher that does not modify the search tree (in fact, it simply inserts a single unary choice), but Gist will recognize the brancher and halt exploration. A special node (shaped like a stop-sign) marks the position in the tree where the stop brancher was active. You can toggle whether Gist continues exploration beyond the brancher using the options in the \emph{Node} menu. Obviously, this is most useful if the call to \?stopBranch? is placed \emph{between} calls to other branchings.

\subsection{Interactive search}

As an alternative to automatic search, you can also explore the search tree interactively. Just select an arbitrary open (white) node and choose \emph{Inspect} from the \emph{Node-Inspect} menu (or press the \emph{Return} key).

You can navigate in the tree using the arrow keys (or the corresponding options from the \emph{Node} menu). Automatic and interactive search can be freely mixed. In order to focus on interesting parts of the search tree, you can hide subtrees using the \emph{Hide/unhide} option, or hide all subtrees below the selected node that are completely failed. The option \emph{Unhide all} expands all hidden subtrees below the current node again. The red triangle in \autoref{fig:m:gist:hidden} is a hidden subtree.

If you want to start over, the \emph{Search} menu provides an option to reset Gist.

\begin{figure}
  {\parindent 0em\mbox{}\hfill
  \includegraphics[width=.45\textwidth]{images/gist_hidden}\hfill
  \mbox{}}
  
  \caption{A hidden subtree in Gist}
  \label{fig:m:gist:hidden}
\end{figure}

\paragraph{Bookmarks.}

The \emph{Node} menu has a submenu \emph{Bookmarks}, where you can collect nodes for quick access. You can set a bookmark for the currently selected node by chosing \emph{Add/remove bookmark} from the submenue, or by pressing \emph{Shift+B}. You can then enter a name for the bookmark (or leave it empty, then the bookmark will get a number). Chosing \emph{Add/remove bookmark} for an already bookmarked node removes the bookmark. Bookmarked nodes are drawn with a small black circle. Selecting a bookmark moves you directly to the corresponding node.

\subsection{Branch-and-bound search}

If Gist has been invoked in branch-and-bound mode, it prunes the search tree with each new solution that is found. Branch-and-bound works with any order of exploration, so you can for instance explore interactively, or start automatic search for just a subtree.

The last solution that was found, which in branch-and-bound is always the best solution known so far, is displayed in orange instead of green.

\subsection{Inspecting and comparing nodes}
\label{sec:m:gist:inspecting_nodes}
\label{sec:m:gist:print}

\begin{figure}
  {\parindent 0em\mbox{}\hfill
  \includegraphics[scale=.5]{images/gist_menu_node}\hfill
  \mbox{}}
  
  \caption{The \emph{Node} menu}
  \label{fig:m:gist:node_menu}
\end{figure}

Of course just looking at the shape of the tree is most of the time not very enlightening by itself. We want to see the content of the nodes. For this, you can display information about the \emph{alternatives} in the tree (provided by print functions, see~\autoref{sec:m:branch:print}), and add \emph{inspectors} and \emph{comparators} to Gist. Inspectors and comparators can be called on solution, choice, or failure nodes (but obviously not on open nodes).

\paragraph{Displaying branching information.}

The \emph{Node} menu (\autoref{fig:m:gist:node_menu}) has two
options for displaying information about branches in the tree.
Choosing \emph{Label/clear branches} will add information on all
branches in the subtree below the currently selected node (or
clear that information if it is already present).
\emph{Label/clear path} adds that information on the path from
the current node to the root. \autoref{fig:m:gist:branches} shows
branching information for the Send More Money problem.

\begin{figure}
  {\parindent 0em\mbox{}\hfill
  \includegraphics[scale=.5]{images/gist_smm_branches}\hfill
  \mbox{}}
  
  \caption{Branch information in Gist}
  \label{fig:m:gist:branches}
\end{figure}

Gist uses print functions provided by the branchers of a
space. For variable-value branchers as described in
\autoref{chap:m:branch}, the information displayed for the
branches can be supplied by the user, see
\autoref{sec:m:branch:print} for details. Also other branchers
can define which information is printed for a branch, see
\autoref{par:b:started:print}. 

\paragraph{Invoking inspectors and comparators.}

The \emph{Node} menu (\autoref{fig:m:gist:node_menu}) provides
several options for inspecting and comparing nodes. If you choose
\emph{Inspect} from the \emph{Inspect} submenu (or simply press
\emph{Return}), all double-click inspectors that are active in
the \emph{Tools} menu (see below) will be invoked for the
currently selected node. You can also invoke a particular
inspector by choosing it from th \emph{Inspect} menu or typing
its shortcut (the first nine inspectors get the shortcuts 0--9).

If you choose an inspector from the \emph{Inspect before fixpoint} menu instead, the state of the node after branching but before fixpoint propagation is shown.

When choosing the \emph{Compare} option, the mouse cursor turns into a crosshair, and clicking on another node will invoke the comparators that have been activated in the \emph{Tools} menu. Again, \emph{Compare before fixpoint} considers the state of the second node after branching but before fixpoint propagation. This is especially useful to find out what the branching does at a particular node: Select a node, choose \emph{Compare before fixpoint}, and click on the child node you are interested in. The comparison will show you exactly how the branching has changed the variable domains.

\paragraph{Choosing the active inspectors and comparators.}

Gist distinguishes between three groups of inspectors, and the group of comparators, which can be chosen from the \emph{Tools} menu (\autoref{fig:m:gist:tools_menu}):
\begin{itemize}
  \item \emph{Move inspectors} are called whenever the user moves to a different node.
  \item \emph{Solution inspectors} are called for each new solution that is found.
  \item \emph{Double-click inspectors} are called when the user explicitly inspects a node, for instance by choosing \emph{Inspect} from the \emph{Node} menu or by double-clicking.
  \item \emph{Comparators} are called when the user chooses \emph{Compare} or \emph{Compare before fixpoint}, and then clicks on another node to compare the currently selected one to. 
\end{itemize}

\begin{figure}
  {\parindent 0em\mbox{}\hfill
  \includegraphics[scale=.5]{images/gist_menu_tools}\hfill
  \mbox{}}
  \caption{The \emph{Tools} menu}
  \label{fig:m:gist:tools_menu}
\end{figure}

\paragraph{The printing inspector.}

\begin{figure}
  {\parindent 0em\mbox{}\hfill
  \includegraphics[width=.8\textwidth]{images/gist_smm_solution}\hfill
  \mbox{}}
  
  \caption{Inspecting a solution in Gist}
  \label{fig:m:gist:inspect}
\end{figure}

The simplest way to add an inspector to your model is to use the
\gecoderef[class]{Gist::Print} inspector, as demonstrated in
\autoref{sec:m:started:gist}. \autoref{fig:m:gist:inspect} shows
the \gecoderef[class]{Gist::Print} inspector after
double-clicking the solution of the Send More Money problem.

\paragraph{Implementing inspectors.}

An inspector is an object that inherits from the abstract base
class \gecoderef[class]{Gist::Inspector}. The abstract base class declares a
virtual member function, \?inspect(const Space& s)?, which is
called when one of the events described above happens. The space
that is passed as an argument corresponds to the inspected node
in the tree. The inspector is free to perform any \?const?
operation on the space.

\paragraph{The variable comparator.}

Similar to the printing inspector, there is a predefined
comparator \gecoderef[class]{Gist::VarComparator} that can be
easily added to scripts. It requires the script to implement a
member function \?compare()? in which it outputs the result of
comparing itself to another space.
\autoref{fig:m:gist:gist-compare} shows how to add comparison to
the example from \autoref{sec:m:started:gist}. It uses a
convenience member function from the class
\gecoderef[class]{Gist::Comparator} that produces a string
representation of the differences between two variable arrays.

\begin{figure}
\insertlitcode{send more money with gist comparison}
\caption{Using Gist for Send More Money with node comparison}
\label{fig:m:gist:gist-compare}
\end{figure}


\paragraph{Implementing comparators.}

A comparator inherits from \gecoderef[class]{Gist::Comparator} and implements at least its
\?compare(const Space& s0, const Space& s1)? member function.
This function is called when the currently selected node with
space \?s0? is compared to the node with space \?s1?. As for
inspectors, a comparator can perform any \?const? operation on
these two spaces.

\paragraph{Subtree statistics.}

The \emph{Node} menu provides an option \emph{Node statistics}, which when clicked opens a small window that displays statistics of the subtree rooted at the currently selected node, as shown in \autoref{fig:m:gist:subtreestats}. The statistics include the depth of the current node (the upper right number in \autoref{fig:m:gist:subtreestats}), the maximum depth of the subtree (the lower right number), and how many of the different node types the subtree contains (the numbers at the small nodes). The information is automatically updated when you select a different node.

\begin{figure}
  {\parindent 0em\mbox{}\hfill
  \includegraphics[width=.8\textwidth]{images/gist_node_stats}\hfill
  \mbox{}}
  
  \caption{Node statistics}
  \label{fig:m:gist:subtreestats}
\end{figure}

\subsection{Zooming, centering, exporting, printing}

Here is some functionality you may have already found during your experiments with Gist.

\paragraph{Mouse wheel zoom.}
You probably noticed that the slider right of the search tree lets you zoom in and out. Another way of zooming is to hold \emph{Shift} while using the mouse wheel. It will zoom in and out keeping the area under the mouse cursor visible.

\paragraph{Zoom and center.}
In addition to manual zooming, Gist provides automatic options. The button with the magnifying glass icon above the zoom slider toggles the auto-zoom feature, which always zooms the tree such that as much of it as possible is visible in the window. During auto-zoom, the manual zoom is disabled. Instead of auto-zoom, you can also select \emph{Zoom to fit} from the \emph{Node} menu (or press \emph{Z}) in order to adjust the zoom so that the current tree fits. When working with large trees, it is sometimes useful to scroll back to the currently selected node by choosing \emph{Center current node} from the \emph{Node} menu or pressing \emph{C}.

\paragraph{Exporting and printing.}
The \emph{File} menu provides options for exporting the current search tree as a PDF file or printing it. If you want to export a single subtree, select \emph{Export subtree PDF} from the \emph{Node} menu. The tree is exported or printed as seen, including hidden nodes.

\subsection{Options and preferences}
\label{sec:m:gist:preferences}

When invoking Gist, you can pass it an optional argument of type
\gecoderef[class]{Gist::Options}. This options class inherits
from the standard search options discussed in
\autoref{sec:m:search:options}, but adds a \?class? with two
member functions, \?inspect.click()? and \?inspect.solution()?,
that you can use to pass inspectors to Gist.

The two options for recomputation, \?c_d? and \?a_d?, as well as
the \?clone? option of \gecoderef[class]{Search::Options} are
honored by Gist; the remaining options are ignored.

During execution, Gist can be configured using the \emph{Preferences} dialog, available from the program menu on Mac OS or the \emph{File} menu on Windows and Linux.

\begin{figure}
  {\parindent 0em\mbox{}\hfill
  \includegraphics[width=0.45\textwidth]{images/gist_preferences_drawing}\hfill
  \includegraphics[width=0.45\textwidth]{images/gist_preferences_search}\hfill
  \mbox{}}
  
  \caption{Gist preferences}
  \label{fig:m:gist:preferences}
\end{figure}


The drawing preferences (\autoref{fig:m:gist:preferences}, left) let you
specify whether failed subtrees are hidden automatically during search, and
whether the auto-zoom and smooth scrolling features are enabled at start-up.
Furthermore, you can set the refresh interval -- this is the number of nodes
that are explored before the tree is redrawn. If you set this to a large
number, search will be faster, but you get less visual feedback. You can
enable slow search, which will explore only around three nodes per second,
useful for demonstrating how search proceeds. Finally, enabling the ``Move
cursor during search'' option means that the move inspectors will be called
for every single node during search. Again, this is great for demonstration
and debugging purposes, but it slows down the search considerably. Drawing
preferences (except for the slow-down and cursor moving options) are
remembered between sessions and across different invocations of Gist.

The search preferences are exactly the parameters you can pass using the \gecoderef[class]{Gist::Options} class. In addition, you can switch on the display of where Gist actually stores spaces in the tree, as shown in \autoref{fig:m:gist:copies}. A small red circle indicates a clone used for recomputation, while a small yellow circle shows that the node has an active space used for exploration (a so-called \emph{working clone}).

The recomputation parameters are not remembered between sessions.

\begin{figure}
  {\parindent 0em\mbox{}\hfill
  \includegraphics[width=.45\textwidth]{images/gist_show_copies}\hfill
  \mbox{}}
  
  \caption{Displaying where Gist stores spaces in the tree}
  \label{fig:m:gist:copies}
\end{figure}

\begin{litcode}{send more money with gist comparison}{schulte,tack}
#include <gecode/int.hh>
#include <gecode/gist.hh>
\begin{litblock}{anonymous}

using namespace Gecode;

\end{litblock}
class SendMoreMoney : public Space {
  \begin{litblock}{anonymous}
protected:
  IntVarArray l;
public:
  SendMoreMoney(void) : l(*this, 8, 0, 9) {
    IntVar s(l[0]), e(l[1]), n(l[2]), d(l[3]),
           m(l[4]), o(l[5]), r(l[6]), y(l[7]);
    rel(*this, s, IRT_NQ, 0);
    rel(*this, m, IRT_NQ, 0);
    distinct(*this, l);
    IntArgs c(4+4+5); IntVarArgs x(4+4+5);
    c[0]=1000; c[1]=100; c[2]=10; c[3]=1;
    x[0]=s;    x[1]=e;   x[2]=n;  x[3]=d;
    c[4]=1000; c[5]=100; c[6]=10; c[7]=1;
    x[4]=m;    x[5]=o;   x[6]=r;  x[7]=e;
    c[8]=-10000; c[9]=-1000; c[10]=-100; c[11]=-10; c[12]=-1;
    x[8]=m;      x[9]=o;     x[10]=n;    x[11]=e;   x[12]=y;
    linear(*this, c, x, IRT_EQ, 0);
    branch(*this, l, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
  }
  SendMoreMoney(bool SendMoreMoney& s) : Space(s) {
    l.update(*this, s.l);
  }
  virtual Space* copy(void) {
    return new SendMoreMoney(*this);
  }
  void print(std::ostream& os) const {
    os << l << std::endl;
  }
  \end{litblock}
  void compare(const Space& s, std::ostream& os) const {
    os << Gist::Comparator::compare<IntVar>("l",l,
      static_cast<const SendMoreMoney&>(s).l);
  }

};

int main(int argc, char* argv[]) {
  SendMoreMoney* m = new SendMoreMoney;
  Gist::Print<SendMoreMoney> p("Print solution");
  Gist::VarComparator<SendMoreMoney> c("Compare nodes");
  Gist::Options o;
  o.inspect.click(&p);
  o.inspect.compare(&c);
  Gist::dfs(m,o);
  delete m;
  return 0;
}
\end{litcode}