Mike, I changed f as you suggest.
n=: 5
A=:?(2#n)$2 NB. generate random matrix of [0,1]
A=:A*(i.n)</i.n NB. make it upper diagonal, zeros on diagonal
]A=:A+|:2*A
0 0 1 0 0
0 0 0 0 0
2 0 0 1 1
0 0 2 0 1
0 0 2 2 0
adj=:((<@#)&(i.n))@(0&<)
adj
<@#&0 1 2 3 4@(0&<)
adj Al
--TT-----T---T---┐
│2││0 3 4│2 4│2 3│
L-++-----+---+----
f=: 13 :'(0<y)<@#i.#y'
f
(0 < ]) <@# [: i. #
f A
--TT-----T---T---┐
│2││0 3 4│2 4│2 3│
L-++-----+---+----
I'm still hoping to remove @ and I guess it will be useful to deal with
rank as Henry suggests. I think I'll take a second look at A. Thanks for
all your help.
Linda
-----Original Message-----
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Mike Day
Sent: Sunday, November 11, 2012 7:15 AM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J
I don't think you can remove the @, although you may use the cap, [: ,
instead, but then you need to force the rank:
([:<(#&0 1 2 3@(0&<)))"1 A
+-++---+-+
|2||0 3|2|
+-++---+-+
I don't like using 0 1 2 3 explicitly since it presumes you know the
dimension of A, so I prefer either
adja =: * <@# i.@# NB. or use caps if @ is too horrible
adja A
+-++---+-+
|2||0 3|2|
+-++---+-+
or
adjI =: <@I.@:*
adjI A
+-++---+-+
|2||0 3|2|
+-++---+-+
I. is so useful that I've defined an I "dfn" in my Dyalog APL too!
As for Raul's point about D, I understood it to represent the domains of
the variables: if there are m variables and the domain of all their
possible values is i.n, then 1 = D{~<i,j means that variable number i may
have value j . m and n are likely to be different. So i<D is a boolean
representing the a priori values that variable i might have.
The consistency algorithm apparently examines which of these a priori values
are consistent with the domains of the other variables given certain unary
and binary constraints which are also inputs to the problem.
Michal's example had m=n which tends to mislead the casual reader!
I believe The m*m A array points to which constraints apply, so 0<l=A{<i,k
means that binary constraint number l applies between variables i and k.
This is why A isn't just a boolean adjacency matrix nor do the entries
signify distances as they would in a weighted graph.
I'm puzzled that the algorithm requires each binary relation to be presented
in both direct and transposed form (this explains Michal's need to patch in
a new index (to a transposed C) in the lower triangle of A for each index to
a direct C in the upper triangle). Perhaps the later algorithms (arc-4...
?) deal with this difficulty.
It strikes me that for a real problem, concise relations such as x <:
y, or 2x+3y>5 can become pretty large and unwieldy C-tables, but perhaps
that's unavoidable when working in the integers.
(The other) Mike
On 11/11/2012 10:16 AM, Linda Alvord wrote:
Mike, I think this will work as an alternative to adj
A
0 0 1 0
0 0 0 0
2 0 0 1
0 0 2 0
adj
<@#&0 1 2 3@(0&<)
adj A
--TT---T-┐
│2││0 3│2│
L-++---+--
h
0 1 2 3 <@#~ 0 < ]
h A
--TT---T-┐
│2││0 3│2│
L-++---+--
Can anyone remove the final @ from h ?
Linda
-----Original Message-----
From:programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Raul Miller
Sent: Saturday, November 10, 2012 12:44 PM To:programm...@jsoftware.com
Subject: Re: [Jprogramming] Arc consistency in J
On Sat, Nov 10, 2012 at 12:16 PM, Michal D.<michal.dobrog...@gmail.com>
wrote:
> Here X is telling us to use the constraint c1 (presumably b/c C is not
> shown) between the variables 1 and 3 (0 based). Likewise, use the
> transpose going the other direction (3,1).
Ouch, you are correct, I did not specify C. On retesting, though, it looks
like my results stay the same when I use:
arccon=:3 :0
'D c1 X'=: y
'n d'=: $D
adj =: ((<@#)&(i.n)) @ (0&<)
A =: adj X
C=: a: , c1 ; (|:c1)
ac =: > @ (1&{) @ (revise^:_) @ ((i.n)&;)
ac D
)
For longer scripts like this, I really need to get into the habit of
restarting J for every test. So that probably means I should be using jhs.
> Given the structure of X, only variables 1 and 3 can possibly change.
> So if they are all changing something is definitely wrong.
This line of thinking does not make sense to me. I thought that the
requirement was that a 1 in D exists only when there is a valid relationship
along a relevant arc. If a 1 in D can also exist in the absence of any
relevant arc, I am back to needing a description of the algorithm.
> Unfortunately I've run out of time to read the rest of your response
> but hopefully I can get through it soon. I've also wanted to write a
> simpler version of the algorithm where the right argument of ac is
> only D and it runs through all the arcs in the problem instead of
> trying to be smart about which ones could have changed.
Yes... I am currently suspicious of the "AC-3 algorithm".
In the case of symmetric consistency, I think that it's unnecessary
complexity, because the system converges on the initial iteration.
In the case of asymmetric consistency, I think that the work involved in
maintaining the data structures needed for correctness will almost always
exceed the work saved.
But I could be wrong. I am not sure yet if I understand the underlying
algorithm!
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
