The adjacency matrix A is important because it tells us which constraint to
look up in C. This also explains why the lower diagonal is doubled.
For example, take the less than constraint:
c =: |: (i.n) </ (i.n)
2 2 $ '' ; 'Dx' ; 'Dy' ; c
+--+-------+
| |Dx |
+--+-------+
|Dy|0 0 0 0|
| |1 0 0 0|
| |1 1 0 0|
| |1 1 1 0|
+--+-------+
This constraint is useful for filtering Dx given Dy. Let's look at how
revDom works (revDom is the heart of the algorithm). Let's generate a
domain for x and y.
Dx=: 1 1 1 1 NB. {0,1,2,3}
Dy=: 1 1 1 0 NB. {0,1,2}
To visualize, stick Dy on the left, and Dx on top:
2 2 $ '' ; Dx ; (|:,:Dy) ; c
+-+-------+
| |1 1 1 1|
+-+-------+
|1|0 0 0 0|
|1|1 0 0 0|
|1|1 1 0 0|
|0|1 1 1 0|
+-+-------+
Now we use Dy to select the relevant rows of c (each row represents the set
of values compatible with that value of Dy).
Dy # c
0 0 0 0
1 0 0 0
1 1 0 0
Take the logical-or of these rows to compute the set of values of Dx that
have some compatible value in Dy.
+./ Dy # c
1 1 0 0
Finally, take the logical-and with Dx so we don't add values that weren't
there in the first place.
Dx *. +./ Dy # c
1 1 0 0
Now, with all this done, what if we want to filter Dy on Dx? We need to
take the transpose of c. To prevent constant transposing, A and C store
these for us.
Mike
On Sun, Nov 4, 2012 at 9:53 AM, Mike Day <mike_liz....@tiscali.co.uk> wrote:
> As far as I can understand the "revise" verb, you don't need the
> adjacency matrix a, although it does help to have a 2-column matrix of
> index pairs.
>
> I think Raul has overlooked your use of the right argument ys within that
> verb, though he's right about selecting with it. Here's a derivation of
> arcs without explicit recourse to the adjacency matrix (I've just noticed
> that Raul presents a similar idiom):
>
> arcs=. ys (]#~ (e.~ {."1)) ($#: I.@,) *|:A
>
> I. returns a vector of indices to the ravelled boolean; $ #: turns them
> into a matrix of pairs of indices to an array of the shape of |:A.
>
> (]#~ (e.~ {."1)) selects those arcs with an element of ys as the from-node
> (or perhaps they're the to-nodes?)
>
> This form renders the arcs array already sorted, but note that if you do
> need to sort the elements of an array, it's sufficient to use the idiom
> /: ~ (rather than ({~ /:) . Presumably sorting "arcs" is merely a
> matter of taste.
>
> It's quite nice to be able to input several components of an argument by
> (local) name with
> 'A a C'=.x
> 'ys D'=. y
> rather than
> A=. > 0{x
> a=. > 1{x
> ys=. > 0{y
> D=. > 1{y
>
> As A is invariant in "ac", you could of course preset the array of
> indices for all arcs in A, aix =: ($#: I.@,) *|:A and use aix as an
> input to "revise" instead of a .
>
> I used *|:A or (0<|:A) here and wonder why you need to double its lower
> diagonal elements.
>
> I also wonder whether your example will still work if there are binary
> constraints involving variables (say z and t) indexed with 2 or 3. And
> what happens if there are more than one binary constraints on a pair of
> variables? eg, X+Y=4 AND X>Y ?
>
> I'd have been very pleased with myself if I'd come up with code as good as
> this when I started J - would be pretty pleased if I managed it now!
>
> Mike
>
>
>
> On 04/11/2012 2:40 PM, Raul Miller wrote:
>
>> In
>> A=. 0= ? (2$n)$2 NB. generate random matrix of [0,1]
>>
>> The 0= is unnecessary, and probably reflects a habit based on the
>> false idea that boolean algebra is does not have an integer domain.
>> Boolean rings have (subset of) integer domains, and [even after
>> redefinition] boolean algebra is a boolean ring.
>>
>> If you ever want to treat Heyting Algebras or Bayesian Probability you
>> might also want to consider what happens when you replace the $2 with
>> $0.
>>
>> I think I would also be more comfortable with
>> 2 2 $ ''; 'y'; 'x'; A
>> for the displayed table, but that's a minor quibble.
>>
>> An alternative definition for adj might be
>> adj=: <@I.@:*
>>
>> But somewhere around here, I get lost. Your use pattern for arcsX is:
>>
>> (i.n) arcsX A
>>
>> where A has the shape n,n
>>
>> What is the domain of the left argument of arcsX? I am guessing that
>> it's either i.n or a single element choosen from i.n but if that is
>> the case, I think I'd define arcsX to only work for the i.n case --
>> the name says "arcs" after all. Also, if I wanted to extract the
>> values from the result of arcsX which correspond to a single value
>> from i. n, that's simple enough -- I can select on the first column of
>> the result.
>>
>> In other words, perhaps something like this:
>>
>> arcs=: $ #: I.@,
>> arcs *A
>>
>> Also, I have not taken the time yet, to read "revise", so I will stop
>> here.
>>
>>
> ------------------------------**------------------------------**----------
> For information about J forums see
> http://www.jsoftware.com/**forums.htm<http://www.jsoftware.com/forums.htm>
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
