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 <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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
