IOzSeF

Guido Tack

An Integrated Oz Search Factory

IOzSef is a search factory for Mozart. It is a toolbox that can be used to build custom search engines for solving constraint problems. It features both a graphical interface very similar to that of the Oz Explorer, and a search engine library that may serve as a replacement for the Search module.

Information about the design behind IOzSeF can be found in the paper Compositional Abstractions for Search Factories by Guido Tack and Didier LeBotlan, which was presented at the 2004 International Mozart/Oz Conference.

Installation

You can obtain IOzSeF from the Mogul. It requires the TkTreeWidget to be installed. Both packages can be downloaded and installed using ozmake:

ozmake --install --package=mogul:/tack/TkTreeWidget
ozmake --install --package=mogul:/tack/iozsef

Example

The interactive interface can be used as a replacement for the Oz Explorer. The following example shows how to solve the n-Queens puzzle using IOzSeF:

declare
[IOZSEF] = {Module.link ['x-ozlib://tack/iozsef/iozsef.ozf']}

fun {Queens N}
   proc{$ Row}
      L1N  = {MakeTuple c N}
      LM1N = {MakeTuple c N}
   in
      {FD.tuple queens N 1#N Row}
      {For 1 N 1 proc{$ I}
                     L1N.I=I LM1N.I=~I
                 end}
      {FD.distinct Row}
      {FD.distinctOffset Row LM1N}
      {FD.distinctOffset Row L1N}
      {FD.distribute generic(value:min) Row}
   end
end

{IOZSEF.exploreAll {Queens 8}}

Working with the interactive IOzSeF

The tree view

The main part of the IOzSeF window is used by the tree view that displays the current search tree. The tree consists of six different node types:

• Blue circles are choice nodes.
• Red squares are nodes representing a failure.
• Green diamonds are nodes representing solutions.
• Gray triangles are nodes representing yet unexplored parts of the search tree.
• Big red triangles represent hidden subtrees.
• Orange stars represent nodes that have a suspended computation.

You can select nodes by clicking on them. Double-clicking invokes the currently selected inspection action, which defaults to displaying the root variable of the current node in the Oz Inspector.

You can also navigate through the tree using the arrow keys. The down-arrow moves to the leftmost child of a node. The up-arrow moves to the parent node. The left- and right-arrows move to the left and right sibling.

The IOzSeF menu

In this menu, you find the operations Halt, Reset, and Quit, which should be self-explaining.

The Node menu

This menu lets you hide or unhide the selected node, unhide all nodes in the current subtree, or unhide failed subtrees below the current subtree.

The Search menu

Using the items in this menu, you can search for the next n solutions, for the next solution, or for all remaining solutions. Search always starts at the currently selected node and only affects the subtree below that node.

Clicking the menu item One step performs a single search step. You can use this to manually explore the search tree.

The item Next phase is only active for search engines based on phases, like iterative deepening.

The Options menu

Using the items in this menu, you can control how IOzSeF searches for solutions, how they can be displayed, and how the memory of the search tree is managed.

• The Search engine submenu lets you choose the exploration strategy, for instance dfs (depth first search) or id (iterative deepening).
• The Information action submenu presents you the available information actions. For hints on programming your own actions, see the section below.
• The PopUp action submenu presents you the available pop-up actions.
• The Recomputation... dialog lets you choose the parameters for recomputation.
• The Drawing... dialog lets you choose whether failed subtrees should be hidden during exploration, after how many solutions the tree should be redrawn, and after how many solutions the exploration should stop.

The status line

The status line provides information about the search tree. It presents the number of nodes of each type, and the time needed for the last search.

Interface

The IOzSeF module

Actions

Actions can be used to visualize information about a node in the search tree. The default inspection action just opens the Oz Inspector and displays the root variable of the node.

Information Actions

Information actions are invoked when the user double-clicks a node in the search tree. Information is not available for failed nodes.

An information action can either get the space of the clicked node or its root variable, depending on the Type parameter given on registration. If the type space is used, you must note that that is the actual space of the node, not a copy, for efficiency reasons. This means that you must not merge it or post constraints on it, as that may make subsequent exploration from that space impossible.

Pop-up Actions

Pop-up actions are invoked when the user "hoovers" over a node in the search tree, that is, when the mouse stays over the same place for more than a second.

A pop-up action must return a string that is then displayed in the pop-up window above the note. It can, just as for information actions, operate on a space or a root variable, and the same restrictions for spaces apply.

Using actions to compare two nodes

The Oz Explorer provides comparison actions that can be used to compare different nodes in the search tree. We can partly emulate this behavior using a combination of information and pop-up actions.

The main idea is to select the first node using an information action, and then use a pop-up action to compare it to a second node. Let us assume that we have a procedure CmpSpacesToString/3 that returns a string, given two root variables. Then we can implement comparison as follows:

declare
local
   S = {NewCell unit}
in
   proc {InfoAction NewS}
      S := NewS
   end
   fun {PopupAction R}
      {CmpSpacesToString @S R}
   end
   {IOZSEF.addInformationAction compare root InfoAction}
   {IOZSEF.addPopUpAction compare root PopupAction}
end

Options