Haha, hello Mike D!
I figured you were talking about "a". I think I followed the 2-column
matrix of node-pairs conversation for the most part, except for RE Boss's
contribution which I didn't appreciate until just now. The -: initially
threw me off so I thought the whole expression was replaced and not just
the generate node-pairs part. It's quite clever but also very specialized
to J, it would be nice to use more primitive operations. Why the dislike
for "a"? I'm guessing it's a stab at removing some of the code?
Yes, the idea is that 0{C is the empty box corresponding to the 0 indices
in A. Also "(<: #C) = (>./ ,A)" - that is the number of entries in C
minus 1 corresponds to the maximum index in A. So you could imagine A with
3s, 4s, etc.
Cheers,
Mike
On Sun, Nov 4, 2012 at 4:21 PM, Mike Day <[email protected]> wrote:
> Hello, Michal D - Mike Day here!
>
> Sorry, I meant your lower case "a", the boxed array of to-nodes, derived
> from upper case "A" which IS the adjacency matrix, which is of course
> essential. "revise" need not be provided with a as well as A, and can
> make do with the 2-column matrix of node-pairs instead. RE Boss
> demonstrates a nice side-effect of sparse arrays "(4 $. $.)" .
>
> OK - I'd never used {:: so didn't appreciate the subtlety of the ones and
> twos in A! So would you need 3s & 4s etc in A to cater for constraints on
> pairs of variables other than the first two?
>
> the other Mike D
>
>
>
> On 04/11/2012 8:54 PM, Michal D. wrote:
>
>> 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 <[email protected]>
>> 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><http://www.**
>>> jsoftware.com/forums.htm <http://www.jsoftware.com/forums.htm>>
>>>
>>> ------------------------------**------------------------------**
>> ----------
>> 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<http://www.jsoftware.com/forums.htm>
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
