7.2.10 Climbing principle

• identifier: principle.climbing
• dimension variables: D1, D2
• argument variables:
  Subgraphs: bool
MotherCards: bool
• default values:
  Subgraphs: true
MotherCards: true
• model record: empty
• constraints: Climbing (priority 110)
• edge constraints: none

This principle assumes that the Graph principle (Graph) is used on dimensions D1 and D2.

The climbing principle stipulates that D1 is a flatter graph than D2. Intuitively, that means that nodes on D2 dimension can “climb up” and end up higher up on D1.

The argument variable Subgraphs specifies whether each node is required to take its entire subgraph along when migrating upwards (true), or not (false). Its default value is true.

The argument variable MotherCards specifies whether the for each node, the cardinalities of the sets of mothers on D1 and D2 must be equal (true), or not (false). This is an optimization for the case that both D1 and D2 are trees. If any of the two is not a tree, MotherCards should be set to false. The default value of MotherCards is true.

Climbing can be restricted by the Barriers principle (Barriers).

Here is the definition of the Climbing constraint functor:

%% Copyright 2001-2008
%% by Ralph Debusmann <rade@ps.uni-sb.de> (Saarland University) and
%%    Denys Duchier <duchier@ps.uni-sb.de> (LIFO, Orleans) and
%%    Jorge Marques Pelizzoni <jpeliz@icmc.usp.br> (ICMC, Sao Paulo) and
%%    Jochen Setz <info@jochensetz.de> (Saarland University)
%%
functor
import
   Helpers(checkModel) at 'Helpers.ozf'
export
   Constraint
define
   proc {Constraint Nodes G Principle FD FS Select}
      DVA2DIDA = Principle.dVA2DIDA
      ArgRecProc = Principle.argRecProc
      %%
      D1DIDA = {DVA2DIDA 'D1'}
      D2DIDA = {DVA2DIDA 'D2'}
   in
      %% check features
      if {Helpers.checkModel 'Climbing.oz' Nodes
	  [D1DIDA#equp
	   D1DIDA#mothers
	   D2DIDA#equp
	   D1DIDA#up
	   D2DIDA#mothers]} then
	 SubgraphsB = {ArgRecProc 'Subgraphs' o}==2
	 MotherCardsB = {ArgRecProc 'MotherCards' o}==2
	 %%
	 D1EqupMs = {Map Nodes
		     fun {$ Node} Node.D1DIDA.model.equp end}
      in
	 for Node in Nodes do
	    %% climbing
	    %% mothers_D1(v) subseteq equp_D2(v)
	    {FS.subset Node.D1DIDA.model.mothers Node.D2DIDA.model.equp}
	    
	    if SubgraphsB then
	       %% equp_D1_mothers_D2(v) =
	       %%   union { equp_D1(v') | v' in mothers_D2(v) }
	       D1EqupD2MothersM =
	       {Select.union D1EqupMs Node.D2DIDA.model.mothers}
	    in
	       %% up_D1(v) subseteq equp_D1_mothers_D2(v)
	       {FS.subset Node.D1DIDA.model.up D1EqupD2MothersM}
	    end
	    
	    if MotherCardsB then
	       %% |mothers_D1(v)| = |mothers_D2(v)|
	       {FD.equal
		{FS.card Node.D1DIDA.model.mothers}
		{FS.card Node.D2DIDA.model.mothers}}
	    end
	 end
      end
   end
end