16.3.10 Complete Solver

Test the dominance constraint solver:

declare  
  [DC]={Link ['x-ozlib://oz-kurs/DC.ozf']}
  local  
     proc {DomCon [N1 N2 N3 N4 N5]}
        {DC.daughters N1 [N2]}
        {DC.dominates N2 N5}
        {DC.daughters N3 [N4]}
        {DC.dominates N4 N5}
        {ForAll [N1#N2 N1#N3 N1#N4 N1#N5  
                 N2#N3 N2#N4 N2#N5  
                 N3#N4 N3#N5
                 N4#N5]
         proc{$ N#M}
            {DC.notEqual N M}
         end}
     end 
  in  
     DomConExample = 'unit'(domCon:DomCon
                            vars:5)
  end 
in  
  {Explorer.all {DC.makePredicate DomConExample}}

The code of the dominance constraint solver:

functor 
import 
   FS FD Space
export 
   MakePredicate
   Daughters
   Dominates
   NotEqual
define 
   proc {Daughters N L}
      N.daughters = L
      {FS.partition {Map L fun {$ D} D.eqdown end} N.down}
      for D in L do D.up=N.equp end 
   end 
   proc {Dominates N1 N2}
      {FS.subset N2.eqdown N1.eqdown}
      {FS.subset N1.equp   N2.equp  }
      {FS.subset N1.side   N2.side  }
   end 
   proc {NotEqual N1 N2}
      {FS.disjoint N1.eq N2.eq}
   end 
   local 
      proc {Equal N1 N2} N1=N2 end 
      proc {StrictlyDominates N1 N2}
         {Dominates N1 N2}
         {NotEqual  N1 N2}
      end 
      proc {Side N1 N2}
         {FS.subset N1.eqdown N2.side}
         {FS.subset N2.eqdown N1.side}
      end 
      fun {MakeNode I VDom}
         Eq     = {FS.var.upperBound VDom}
         Down   = {FS.var.upperBound VDom}
         Up     = {FS.var.upperBound VDom}
         Side   = {FS.var.upperBound VDom}
         EqDown = {FS.union Eq Down}
         EqUp   = {FS.union Eq Up}
      in 
         {FS.partition [Eq Down Up Side] {FS.value.make VDom}}
         {FS.include I Eq}
         node(
            eq        : Eq
            down      : Down
            up        : Up
            side      : Side
            eqdown    : EqDown
            equp      : EqUp
            daughters : _)
      end 
   in 
      fun {MakePredicate 'unit'(domCon:DomCon vars:N)}  
         proc {$ Nodes}  
           VDom = [1#N]
           {List.make N Nodes}   % constrains Nodes to a list
                                 % [_ ... _] of length N
           for Node in Nodes I in 1..do {MakeNode I VDom Node} end  
           {DomCon Nodes}
           % waits for stability
           {Space.waitStable}  
           ChoiceVariables =
           {List.foldRTail Nodes
            fun {$ Ni|Ns Cs}
               {List.foldR Ns
                fun {$ Nj Cs}  
                   C in C::1#4
                   thread  
                      or C = 1 {Equal Ni Nj}
                      [] C = 2 {StrictlyDominates Ni Nj}
                      [] C = 3 {StrictlyDominates Nj Ni}
                      [] C = 4 {Side Nj Ni}
                      end 
                   end 
                   C|Cs
                end Cs}
            end nil}  
         in 
           {FD.distribute ff ChoiceVariables}
         end  
      end   
   end 
end

Draw the example graph:

%% this file contains an example for the Oz-DaVinci-Interface
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% the following constants have to be adapted.
%%
 
declare 
%% The value of   DaVinciPath   has to be adapted to be  
%% the path where to find the executable DaVinci-binaries
 
DaVinciPath= "/export/global/ps/soft/daVinci_V2.1/linux-i486/daVinci" 
%% The value of Version determines the pickle version
%% required by your Oz System. Mozart 1.0.1 requires
%% version 1.5 and Mozart 1.1.0 needs version 2.0.
 
Version = 'Version.3.2' 
 
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%% the following constants remain unchanged.
 
URL = 'http://www.ps.uni-sb.de/~niehren/DaVinci' 
GraphOzf = '/'#Version#'/graph.ozf' 
PipeOzf  = '/'#Version#'/pipe.ozf' 
     
[Mod1 Mod2] = {Module.link [URL#GraphOzf URL#PipeOzf]}
 
MakeDaVinciGraph = {Mod1.daVinciGraph LayoutParameter}
MakeDaVinciEdges = {Mod1.daVinciEdges LayoutParameter}
NewDaVinci = {Mod2.makeNewDaVinci DaVinciPath}
 
LayoutParameter =
unit(edge:unit(default:edge(to:default
                            'EDGECOLOR':black
                            'EDGEPATTERN':solid
                            '_DIR':none
                            'HEAD':arrow)
               dom:edge('EDGECOLOR':blue
                        'EDGEPATTERN':dotted)
               void:edge('EDGEPATTERN':none)
              )
     label: unit(default:label('COLOR':white
                               '_GO':text
                               'OBJECT':default)
                )
    )
Graph = [node(id:1
              edges:[edge(to:2)]
              label:label('OBJECT':'X1:'#forall#' '#men))
         node(id:2
              edges:[edge(kind:dom to:5)]
              label:label('OBJECT':'X2'))
         node(id:3
              edges:[edge(to:4)]
              label:label('OBJECT':'X3:'#exists#' '#woman))
         node(id:4
              edges:[edge(kind:dom to:5)]
              label:label('OBJECT':'X4'))
         node(id:5
              edges:nil
              label:label('OBJECT':'X5:'#loves))
        ]
 
DVG = {MakeDaVinciGraph Graph} {Browse DVG}
DaVinci = {NewDaVinci}  
{DaVinci.graph DVG}


Denys Duchier, Claire Gardent and Joachim Niehren
Version 1.3.99 (20050412)