7.2.64 Subgraphs principle

• identifier: principle.subgraphs
• dimension variables: D1, D2, D3
• argument variables:
  Start: vec(label(D1) set(label(D2)))
• default values:
  Start: ^.D3.entry.start
• model record: empty
• constraints: Subgraphs (priority 110)
• edge constraints: none

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

The principle creates two sets S1 and S2 for each node v, and each edge label l on D1: S1 is the set of nodes (i.e. the subgraph) below an edge labeled l emanating from v on D1. S2 is the set of nodes below all edges labeled by a label in Start(l) emanating from v on D2.

The principle then stipulates for each node v, and each edge label l on D1:

• if Start(l) is not empty, then S1 must be a subset of S2

Here is the definition of the Subgraphs 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
%   System(show)

   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'}
      DIDA2LabelLat = G.dIDA2LabelLat
      D1LabelLat = {DIDA2LabelLat D1DIDA}
      D1LAs = D1LabelLat.constants
      D2LabelLat = {DIDA2LabelLat D2DIDA}
      D2LAs = D2LabelLat.constants
   in
      %% check features
      if {Helpers.checkModel 'Subgraphs.oz' Nodes
	  [D1DIDA#downL
	   D2DIDA#downL]} then
	 %% Linking Subgraphs
	 %%
	 %% forall v in V: forall l in L_1:
	 %%   Start(v)(l) neq emptyset => 
	 %%     v -l->1+ D1 and v -(Start(v)(l))->2+ D2 and
	 %%       D1 subseteq D2
	 for Node in Nodes do
	    StartLALMRec =
	    {ArgRecProc 'Start' o('^': Node)}
	    %%
	    D2DownLMs = {Map D2LAs
			 fun {$ LA} Node.D2DIDA.model.downL.LA end}
	 in
	    for D1LA in D1LAs do
	       StartLM = StartLALMRec.D1LA
	       %%
	       D1M = Node.D1DIDA.model.downL.D1LA
	       D2M = {Select.union D2DownLMs StartLM}
	    in
	       {FD.impl
		{FD.nega {FS.reified.equal StartLM FS.value.empty}}
		{FS.reified.subset D1M D2M} 1}
	    end
	 end
      end
   end
end