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
