augment = function(x) fx[x] = true for y in [0:n]: if not fy[y] t = lx[x] + ly[y] - a[x][y] if t == 0 fy[y] = true if mate[y] == nil or fself(mate[y]) mate[y] = x return true end end end return false end
for x in [0:n] loop fx = [].comp(a, {=> false}) fy = [].comp(a, {=> false}) delta = nil if augment(x): break for xx in [0:n]: if fx[xx] for yy in [0:n]: if not fy[yy] t = lx[xx] + ly[yy] - a[xx][yy] if delta == nil or t < delta: delta, optx, opty = t, xx, yy end end
for i in [0:n] if fx[i]: lx[i] -= delta if fy[i]: ly[i] += delta end > fx.describe(), fy.describe() input() end end
sum = {s => reduce({a,b => a+b}, s)} return sum(lx) + sum(ly) end
> augment = function(x) > fx[x] = true > for y in [0:n]: if not fy[y] > t = lx[x] + ly[y] - a[x][y] > if t == 0 > fy[y] = true > if mate[y] == nil or fself(mate[y]) > mate[y] = x > return true > end > end > end > return false > end
> for x in [0:n] > loop > fx = [].comp(a, {=> false}) > fy = [].comp(a, {=> false}) > delta = nil > if augment(x): break > for xx in [0:n]: if fx[xx] > for yy in [0:n]: if not fy[yy] > t = lx[xx] + ly[yy] - a[xx][yy] > if delta == nil or t < delta: delta, optx, opty = t, xx, yy > end > end
> for i in [0:n] > if fx[i]: lx[i] -= delta > if fy[i]: ly[i] += delta > end > > fx.describe(), fy.describe() > input() > end > end
> sum = {s => reduce({a,b => a+b}, s)} > return sum(lx) + sum(ly) > end
> a = .[ .[1 2 3] > .[5 0 2] > .[3 2 1] ]
> > KuhnMunkres(a)
> Thanks in advance for any suggestions.
I didn't run it, but isn't ...
function ...
fx = nil fy = nil
n = a.len()
function ... fx[ ... ]
closing a nil in fx? -- if so, fx[...] will always be invalid, as the value it had when closed was a nil (invalid operands can refer to a nil[x] accessor).
On Wed, Apr 18, 2012 at 03:01:45PM +0200, Giancarlo Niccolai wrote: > On 18/04/2012 03:47, Ray Song wrote: > > Hi all, I'm working on an implementation of Kuhn-Munkres algorithm when come cross this issue.
> > falcon: FATAL - Program terminated with error. > > TypeError MD0017 at a._lambda#_id_5:11: Invalid operands given opcode > > Traceback: > > a._lambda#_id_5:11(PC:0) > > "/home/ray/a.fal" a._lambda#_id_5:16(PC:232) > > "/home/ray/a.fal" a.KuhnMunkres:30(PC:440) > > "/home/ray/a.fal" a.__main__:55(PC:168)
> > augment = function(x) > > fx[x] = true > > for y in [0:n]: if not fy[y] > > t = lx[x] + ly[y] - a[x][y] > > if t == 0 > > fy[y] = true > > if mate[y] == nil or fself(mate[y]) > > mate[y] = x > > return true > > end > > end > > end > > return false > > end
> > for x in [0:n] > > loop > > fx = [].comp(a, {=> false}) > > fy = [].comp(a, {=> false}) > > delta = nil > > if augment(x): break > > for xx in [0:n]: if fx[xx] > > for yy in [0:n]: if not fy[yy] > > t = lx[xx] + ly[yy] - a[xx][yy] > > if delta == nil or t < delta: delta, optx, opty = t, xx, yy > > end > > end
> > for i in [0:n] > > if fx[i]: lx[i] -= delta > > if fy[i]: ly[i] += delta > > end > > > fx.describe(), fy.describe() > > input() > > end > > end
> > sum = {s => reduce({a,b => a+b}, s)} > > return sum(lx) + sum(ly) > > end
> > a = .[ .[1 2 3] > > .[5 0 2] > > .[3 2 1] ]
> > > KuhnMunkres(a)
> > Thanks in advance for any suggestions.
> I didn't run it, but isn't ...
> function ...
> fx = nil > fy = nil
> n = a.len()
> function ... > fx[ ... ]
> closing a nil in fx? -- if so, fx[...] will always be invalid, as the value it had when closed was a nil (invalid operands can refer to a nil[x] accessor).
This issue is triggered when the function `augment' is called by `fself(mate[y])' . The most reliable guess I come up with is that a nested called inner function does not have access to variables in the outer function, which a directly called inner function has.
Is there any other approach to circumvent this issue?
> > > augment = function(x) > > > fx[x] = true > > > for y in [0:n]: if not fy[y] > > > t = lx[x] + ly[y] - a[x][y] > > > if t == 0 > > > fy[y] = true > > > if mate[y] == nil or fself(mate[y]) > > > mate[y] = x > > > return true > > > end > > > end > > > end > > > return false > > > end
> > > for x in [0:n] > > > loop > > > fx = [].comp(a, {=> false}) > > > fy = [].comp(a, {=> false}) > > > delta = nil > > > if augment(x): break > > > for xx in [0:n]: if fx[xx] > > > for yy in [0:n]: if not fy[yy] > > > t = lx[xx] + ly[yy] - a[xx][yy] > > > if delta == nil or t < delta: delta, optx, opty = t, xx, yy > > > end > > > end
> > > for i in [0:n] > > > if fx[i]: lx[i] -= delta > > > if fy[i]: ly[i] += delta > > > end > > > > fx.describe(), fy.describe() > > > input() > > > end > > > end
> On 18/04/2012 15:13, Ray Song wrote: >> function KuhnMunkres(a) >>>> lx = [].comp(a, {s => reduce({a,b => max(a, b)}, s)}) >>>> ly = [].comp(a, {=> 0}) >>>> mate = [].comp(a, {=> nil}) >>>> fx = nil >>>> fy = nil
>>>> n = a.len()
>>>> augment = function(x) >>>> fx[x] = true >>>> for y in [0:n]: if not fy[y] >>>> t = lx[x] + ly[y] - a[x][y] >>>> if t == 0 >>>> fy[y] = true >>>> if mate[y] == nil or fself(mate[y]) >>>> mate[y] = x >>>> return true >>>> end >>>> end >>>> end >>>> return false >>>> end
>>>> for x in [0:n] >>>> loop >>>> fx = [].comp(a, {=> false}) >>>> fy = [].comp(a, {=> false}) >>>> delta = nil >>>> if augment(x): break >>>> for xx in [0:n]: if fx[xx] >>>> for yy in [0:n]: if not fy[yy] >>>> t = lx[xx] + ly[yy] - a[xx][yy] >>>> if delta == nil or t < delta: delta, optx, opty = t, xx, yy >>>> end >>>> end
>>>> for i in [0:n] >>>> if fx[i]: lx[i] -= delta >>>> if fy[i]: ly[i] += delta >>>> end >>>> > fx.describe(), fy.describe() >>>> input() >>>> end >>>> end
>>>> sum = {s => reduce({a,b => a+b}, s)} >>>> return sum(lx) + sum(ly) >>>> end
>>>> > KuhnMunkres(a) > Uhm, tested the program; it seems there's something wrong with fself: > it calls the function, but not the closure. A working workaround is:
> augment = function(x, func) > ... > if mate[y] == nil or func(mate[y],func) > ....
> if augment(x, augment): break
> Gian.
Just committed a patch on the main git branch where fself points to the actual closure. This requries a bit of extra time at call frame, but since we're nearing an alpha release in the new engine (which deals with performance of call frames), the performance issue is not very relevant.
