I am finding this hard to reason about.
One issue is the sheer arbitrariness of the result. It's "a maximal
clique". It's not "all maximal cliques". It's not a maximal clique
which is in some way notable except that it's a particular maximal
clique which just happens to be convenient to express using a
particular notation.
So I'm having a hard time reasoning about what makes this particular
maximal clique notable, and why I should expect it to be convenient to
express using different notation.
For reference, though, here's another explicit verb which I believe
finds a different maximal clique:
g=: 3 :0
*/>({ <: ])&.>/(]&.>@i.@#,<) y
)
The ({ <: ]) part corresponds to the inside of the loop.
If you wanted a tacit verb, use 13 :0 instead of 3 :0 in the definition of g.
I do not know if this helps.
--
Raul
On Fri, May 3, 2013 at 3:22 PM, Christopher Rosin <[email protected]> wrote:
> Hi all. Reading this list has been very useful as I've been learning J.
>
> I'd like to ask for help in finding a simple tacit way to express f below,
> or at least an appropriate commonly-used tacit J idiom.
>
> Say s is a symmetric boolean matrix with 1's on the diagonal, and define:
> f =: 3 : 0
> for_k. i.#y do. y =. (<:~ k&{) y end.
> */ y
> )
>
> e.g.
> ] s =: ((= |:) (?. 10 10 $ 2))
> 1 0 0 0 1 1 0 1 0 0
> 0 1 0 0 0 1 1 1 1 1
> 0 0 1 0 1 1 0 0 0 0
> 0 0 0 1 1 1 1 1 1 0
> 1 0 1 1 1 0 0 1 1 1
> 1 1 1 1 0 1 1 0 1 0
> 0 1 0 1 0 1 1 0 1 0
> 1 1 0 1 1 0 0 1 0 1
> 0 1 0 1 1 1 1 0 1 1
> 0 1 0 0 1 0 0 1 1 1
> f s
> 1 0 0 0 1 0 0 1 0 0
>
> One way to describe f is: given undirected graph s it finds a maximal
> clique:
> http://mathworld.wolfram.com/MaximalClique.html
> (maximal clique, not maximum clique... which would be NP-hard)
> The 1's in (f s) mark a clique of nodes linked by edges (marked by 1's in s)
> and this clique is maximal in that nothing can be added to it.
>
> One tacit approach is to translate the for loop using a boxed list of
> indices:
> g =: [: */@>@((]<:~{)&.>/) <"0@|.@i.@# , <
> g s
> 1 0 0 0 1 0 0 1 0 0
>
> Another is to rotate repeatedly so the head is always next to be processed:
> h =: */@(([:(1 1)&|.]<:~{.)^:#)
> h s
> 1 0 0 0 1 0 0 1 0 0
>
> But these seem somewhat awkward to me.
> The explicit function f has just two verbs inside the body of the for loop,
> so I was hoping to find a tacit solution that also needed at most two verbs
> inside the / or ^: or whatever else is used to replace the loop.
>
> Any ideas?
> Or maybe there is an entirely different approach, more suited to tacit J?
>
> Thanks.
> -Chris
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
