FAQ
Hello Gophers,

I'm happy to announce the release of a small package providing an
implementation of the Hungarian Assignment algorithm (a.k.a.
Kuhn-Munkres a.k.a. Munkres). The code is available here:
   https://github.com/clyphub/munkres
See the repo for README and license information.

I developed this code for my employer, clypd, after encountering an
issue with the existing implementation available in go-gt. I
previously sent an email to this list (copied below) but didn't hear
any responses so decided to roll my own.

As I'm relatively new to Go I'd appreciate any feedback on this code.
And, since this is Open Source, patches or pull requests are welcome!

brian

On Wed, Feb 19, 2014 at 1:44 PM, Brian Fallik wrote:
Hi,

Wondering if any Gophers out there have experience using the go-gt
package [1], specifically its Hungarian() [2] method.

I'm exploring solutions to an assignment problem but the go-gt
implementation panics with "Index out of range" for certain input.
I've logged the bug [3] but haven't seen any response so I wonder if
the library is actively maintained. I suspect the bug is in go-gt
since (AFAIK) the Hungarian algorithm itself safely handles any square
matrix.

Is anyone out there using this code successfully? Am I just missing
something obvious?

Alternatively is there another recommended graph library I should be
using? I found go-gt on the go-wiki [4].

Thanks,
brian


1 - https://code.google.com/p/go-gt/
2 - https://code.google.com/p/go-gt/source/browse/gt/hungarian.go
3 - https://code.google.com/p/go-gt/issues/detail?id=2
4 - https://code.google.com/p/go-wiki/wiki/Projects#Mathematics
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

  • Damian Gryski at Mar 18, 2014 at 10:18 am

    On Monday, March 17, 2014 3:31:46 PM UTC+1, Brian Fallik wrote:
    I developed this code for my employer, clypd, after encountering an
    issue with the existing implementation available in go-gt. I
    previously sent an email to this list (copied below) but didn't hear
    any responses so decided to roll my own.
        I added clypd to the GoUsers wiki page
    (https://code.google.com/p/go-wiki/wiki/GoUsers) using the "Going to Go"
    blog post as a reference.

        Damian

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Brian Fallik at Mar 18, 2014 at 12:49 pm
    Excellent, Thanks!

    brian

    On Tue, Mar 18, 2014 at 6:18 AM, Damian Gryski wrote:

    On Monday, March 17, 2014 3:31:46 PM UTC+1, Brian Fallik wrote:

    I developed this code for my employer, clypd, after encountering an
    issue with the existing implementation available in go-gt. I
    previously sent an email to this list (copied below) but didn't hear
    any responses so decided to roll my own.

    I added clypd to the GoUsers wiki page
    (https://code.google.com/p/go-wiki/wiki/GoUsers) using the "Going to Go"
    blog post as a reference.

    Damian

    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Egon at Mar 18, 2014 at 5:28 pm

    On Monday, March 17, 2014 4:31:46 PM UTC+2, Brian Fallik wrote:
    Hello Gophers,

    I'm happy to announce the release of a small package providing an
    implementation of the Hungarian Assignment algorithm (a.k.a.
    Kuhn-Munkres a.k.a. Munkres). The code is available here:
    https://github.com/clyphub/munkres
    See the repo for README and license information.

    I developed this code for my employer, clypd, after encountering an
    issue with the existing implementation available in go-gt. I
    previously sent an email to this list (copied below) but didn't hear
    any responses so decided to roll my own.

    As I'm relatively new to Go I'd appreciate any feedback on this code.
    One thing I noticed that you can replace your Step interface with this:

    type Step func(ctx *Context) (Step, bool)

    That way you don't need those "type Step1 struct{}" stubs. e.g.

    func step1(ctx *Context) (Step, bool) { return step2, true }

    The step1, step2... and most of the code is non-descriptive... From just
    reading the code it's hard to understand what it does. It might make sense
    so that the code uses words like "worker" "job" as array indexes, or
    something like that... but I'm not able to give very good advice without
    thoroughly going through the algorithm myself.

    It might make sense to avoid the whole "step" ... thing and try to write
    something like:

    // step 0
    m := createMatrix(jobs, workers)
    assignCosts(m, ...)
    // step 1
    for _, row := range rows(m.A) {
       v := min(row...)
       subtract(work, v)
    }
    // step 2
    Z, row, col := findZero(m)
    if ctx.hasStarIn(row, col) (
       ctx.markStarred(Z)
    }
    ... etc...

    (WARNING, no clue about the actual algorithm, just trying to write the
    6-step algorithm into code)

    But then again, since the original paper contained the "step0", "step1"...
    approach, it's probably safer that way... it's easier to verify whether
    it's correct, although the readability/understandability of the code won't
    be great. Also my suggestion is worse from observability standpoint... so
    nevermind :)

    You should probably get rid of the "i*n" multiplications in the loops
    (unnecessary calculations), e.g.

    func erasePrimes(ctx *Context) {
       n := ctx.m.n
       n2 := n*n
       for i := 0; i < n2; i += n {
          for j := 0; j < n; j++ {
            if ctx.marked[i+j] == Primed {
    ...

    func findPrimeInRow(ctx *Context, row int) int {
       n := ctx.m.n
       rowstart := row*n
       for j := 0; j < n; j++ {
         if ctx.marked[rowstart + j] == Primed {

    + egon

    And, since this is Open Source, patches or pull requests are welcome!
    brian

    On Wed, Feb 19, 2014 at 1:44 PM, Brian Fallik wrote:
    Hi,

    Wondering if any Gophers out there have experience using the go-gt
    package [1], specifically its Hungarian() [2] method.

    I'm exploring solutions to an assignment problem but the go-gt
    implementation panics with "Index out of range" for certain input.
    I've logged the bug [3] but haven't seen any response so I wonder if
    the library is actively maintained. I suspect the bug is in go-gt
    since (AFAIK) the Hungarian algorithm itself safely handles any square
    matrix.

    Is anyone out there using this code successfully? Am I just missing
    something obvious?

    Alternatively is there another recommended graph library I should be
    using? I found go-gt on the go-wiki [4].

    Thanks,
    brian


    1 - https://code.google.com/p/go-gt/
    2 - https://code.google.com/p/go-gt/source/browse/gt/hungarian.go
    3 - https://code.google.com/p/go-gt/issues/detail?id=2
    4 - https://code.google.com/p/go-wiki/wiki/Projects#Mathematics
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Brian Fallik at Mar 18, 2014 at 11:25 pm
    Hi,
    On Tue, Mar 18, 2014 at 1:28 PM, egon wrote:
    On Monday, March 17, 2014 4:31:46 PM UTC+2, Brian Fallik wrote:

    Hello Gophers,

    I'm happy to announce the release of a small package providing an
    implementation of the Hungarian Assignment algorithm (a.k.a.
    Kuhn-Munkres a.k.a. Munkres). The code is available here:
    https://github.com/clyphub/munkres
    See the repo for README and license information.

    I developed this code for my employer, clypd, after encountering an
    issue with the existing implementation available in go-gt. I
    previously sent an email to this list (copied below) but didn't hear
    any responses so decided to roll my own.

    As I'm relatively new to Go I'd appreciate any feedback on this code.

    One thing I noticed that you can replace your Step interface with this:

    type Step func(ctx *Context) (Step, bool)

    That way you don't need those "type Step1 struct{}" stubs. e.g.

    func step1(ctx *Context) (Step, bool) { return step2, true }
    That makes sense - the Interface may be overkill when all I'm doing is
    declaring it to contain a single function. I wondered about that but
    ultimately opted for the Interface approach. I'll take a look at
    switching it.
    The step1, step2... and most of the code is non-descriptive... From just
    reading the code it's hard to understand what it does. It might make sense
    so that the code uses words like "worker" "job" as array indexes, or
    something like that... but I'm not able to give very good advice without
    thoroughly going through the algorithm myself.

    It might make sense to avoid the whole "step" ... thing and try to write
    something like:

    // step 0
    m := createMatrix(jobs, workers)
    assignCosts(m, ...)
    // step 1
    for _, row := range rows(m.A) {
    v := min(row...)
    subtract(work, v)
    }
    // step 2
    Z, row, col := findZero(m)
    if ctx.hasStarIn(row, col) (
    ctx.markStarred(Z)
    }
    ... etc...

    (WARNING, no clue about the actual algorithm, just trying to write the
    6-step algorithm into code)

    But then again, since the original paper contained the "step0", "step1"...
    approach, it's probably safer that way... it's easier to verify whether it's
    correct, although the readability/understandability of the code won't be
    great. Also my suggestion is worse from observability standpoint... so
    nevermind :)
    Yeah, at this point I'd rather match the paper. As non-descriptive as
    the named steps are, at least they're consistent with the upstream
    documentation. Perhaps the code should provide a few more breadcrumb
    links to better document the source material.
    You should probably get rid of the "i*n" multiplications in the loops
    (unnecessary calculations), e.g.
    Sure, can do.
    func erasePrimes(ctx *Context) {
    n := ctx.m.n
    n2 := n*n
    for i := 0; i < n2; i += n {
    for j := 0; j < n; j++ {
    if ctx.marked[i+j] == Primed {
    ...

    func findPrimeInRow(ctx *Context, row int) int {
    n := ctx.m.n
    rowstart := row*n
    for j := 0; j < n; j++ {
    if ctx.marked[rowstart + j] == Primed {

    + egon
    Thanks for taking a look.

    brian
    And, since this is Open Source, patches or pull requests are welcome!

    brian

    On Wed, Feb 19, 2014 at 1:44 PM, Brian Fallik wrote:
    Hi,

    Wondering if any Gophers out there have experience using the go-gt
    package [1], specifically its Hungarian() [2] method.

    I'm exploring solutions to an assignment problem but the go-gt
    implementation panics with "Index out of range" for certain input.
    I've logged the bug [3] but haven't seen any response so I wonder if
    the library is actively maintained. I suspect the bug is in go-gt
    since (AFAIK) the Hungarian algorithm itself safely handles any square
    matrix.

    Is anyone out there using this code successfully? Am I just missing
    something obvious?

    Alternatively is there another recommended graph library I should be
    using? I found go-gt on the go-wiki [4].

    Thanks,
    brian


    1 - https://code.google.com/p/go-gt/
    2 - https://code.google.com/p/go-gt/source/browse/gt/hungarian.go
    3 - https://code.google.com/p/go-gt/issues/detail?id=2
    4 - https://code.google.com/p/go-wiki/wiki/Projects#Mathematics
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Brian Fallik at Mar 19, 2014 at 3:31 am
    Hi,
    On Tue, Mar 18, 2014 at 7:25 PM, Brian Fallik wrote:
    Hi,
    On Tue, Mar 18, 2014 at 1:28 PM, egon wrote:
    On Monday, March 17, 2014 4:31:46 PM UTC+2, Brian Fallik wrote:

    Hello Gophers,

    I'm happy to announce the release of a small package providing an
    implementation of the Hungarian Assignment algorithm (a.k.a.
    Kuhn-Munkres a.k.a. Munkres). The code is available here:
    https://github.com/clyphub/munkres
    See the repo for README and license information.

    I developed this code for my employer, clypd, after encountering an
    issue with the existing implementation available in go-gt. I
    previously sent an email to this list (copied below) but didn't hear
    any responses so decided to roll my own.

    As I'm relatively new to Go I'd appreciate any feedback on this code.

    One thing I noticed that you can replace your Step interface with this:

    type Step func(ctx *Context) (Step, bool)

    That way you don't need those "type Step1 struct{}" stubs. e.g.

    func step1(ctx *Context) (Step, bool) { return step2, true }
    That makes sense - the Interface may be overkill when all I'm doing is
    declaring it to contain a single function. I wondered about that but
    ultimately opted for the Interface approach. I'll take a look at
    switching it.
    After attempting to remove the interface I ran into the problem I
    remember encountering during development which prompted me to move to
    the interface in the first place. Perhaps someone can enlighten me on
    a better approach.

    The tests try to ensure that, after each stage of the algorithm (a
    "Mark" in the test code), the current step returns the correct next
    step. The line of test code looks similar to:
       assert.IsType(t, Step2{}, result)
    Without the interface I I'm not sure how to compare the returned
    function type without using reflection or runtime, both of which seem
    like a step in the wrong direction.

    I can't directly compare function types in Go for equality.
    Theoretically I could declare local variables pointing to each step
    function and then compare the addresses of those, but since the step
    functions have a cyclical nature (Step4 -> Step6 -> Step4), Go
    complains about an "initialization loop".

    While the empty structs are a bit of a wart in the source code it
    seems worth it for the benefit of interface equality comparisons. Or
    am I missing something obvious?

    brian

    The step1, step2... and most of the code is non-descriptive... From just
    reading the code it's hard to understand what it does. It might make sense
    so that the code uses words like "worker" "job" as array indexes, or
    something like that... but I'm not able to give very good advice without
    thoroughly going through the algorithm myself.

    It might make sense to avoid the whole "step" ... thing and try to write
    something like:

    // step 0
    m := createMatrix(jobs, workers)
    assignCosts(m, ...)
    // step 1
    for _, row := range rows(m.A) {
    v := min(row...)
    subtract(work, v)
    }
    // step 2
    Z, row, col := findZero(m)
    if ctx.hasStarIn(row, col) (
    ctx.markStarred(Z)
    }
    ... etc...

    (WARNING, no clue about the actual algorithm, just trying to write the
    6-step algorithm into code)

    But then again, since the original paper contained the "step0", "step1"...
    approach, it's probably safer that way... it's easier to verify whether it's
    correct, although the readability/understandability of the code won't be
    great. Also my suggestion is worse from observability standpoint... so
    nevermind :)
    Yeah, at this point I'd rather match the paper. As non-descriptive as
    the named steps are, at least they're consistent with the upstream
    documentation. Perhaps the code should provide a few more breadcrumb
    links to better document the source material.
    You should probably get rid of the "i*n" multiplications in the loops
    (unnecessary calculations), e.g.
    Sure, can do.
    func erasePrimes(ctx *Context) {
    n := ctx.m.n
    n2 := n*n
    for i := 0; i < n2; i += n {
    for j := 0; j < n; j++ {
    if ctx.marked[i+j] == Primed {
    ...

    func findPrimeInRow(ctx *Context, row int) int {
    n := ctx.m.n
    rowstart := row*n
    for j := 0; j < n; j++ {
    if ctx.marked[rowstart + j] == Primed {

    + egon
    Thanks for taking a look.

    brian
    And, since this is Open Source, patches or pull requests are welcome!

    brian

    On Wed, Feb 19, 2014 at 1:44 PM, Brian Fallik wrote:
    Hi,

    Wondering if any Gophers out there have experience using the go-gt
    package [1], specifically its Hungarian() [2] method.

    I'm exploring solutions to an assignment problem but the go-gt
    implementation panics with "Index out of range" for certain input.
    I've logged the bug [3] but haven't seen any response so I wonder if
    the library is actively maintained. I suspect the bug is in go-gt
    since (AFAIK) the Hungarian algorithm itself safely handles any square
    matrix.

    Is anyone out there using this code successfully? Am I just missing
    something obvious?

    Alternatively is there another recommended graph library I should be
    using? I found go-gt on the go-wiki [4].

    Thanks,
    brian


    1 - https://code.google.com/p/go-gt/
    2 - https://code.google.com/p/go-gt/source/browse/gt/hungarian.go
    3 - https://code.google.com/p/go-gt/issues/detail?id=2
    4 - https://code.google.com/p/go-wiki/wiki/Projects#Mathematics
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Kyle Lemons at Mar 19, 2014 at 7:31 pm

    On Tue, Mar 18, 2014 at 8:31 PM, Brian Fallik wrote:

    Hi,
    On Tue, Mar 18, 2014 at 7:25 PM, Brian Fallik wrote:
    Hi,
    On Tue, Mar 18, 2014 at 1:28 PM, egon wrote:
    On Monday, March 17, 2014 4:31:46 PM UTC+2, Brian Fallik wrote:

    Hello Gophers,

    I'm happy to announce the release of a small package providing an
    implementation of the Hungarian Assignment algorithm (a.k.a.
    Kuhn-Munkres a.k.a. Munkres). The code is available here:
    https://github.com/clyphub/munkres
    See the repo for README and license information.

    I developed this code for my employer, clypd, after encountering an
    issue with the existing implementation available in go-gt. I
    previously sent an email to this list (copied below) but didn't hear
    any responses so decided to roll my own.

    As I'm relatively new to Go I'd appreciate any feedback on this code.

    One thing I noticed that you can replace your Step interface with this:

    type Step func(ctx *Context) (Step, bool)

    That way you don't need those "type Step1 struct{}" stubs. e.g.

    func step1(ctx *Context) (Step, bool) { return step2, true }
    That makes sense - the Interface may be overkill when all I'm doing is
    declaring it to contain a single function. I wondered about that but
    ultimately opted for the Interface approach. I'll take a look at
    switching it.
    After attempting to remove the interface I ran into the problem I
    remember encountering during development which prompted me to move to
    the interface in the first place. Perhaps someone can enlighten me on
    a better approach.

    The tests try to ensure that, after each stage of the algorithm (a
    "Mark" in the test code), the current step returns the correct next
    step. The line of test code looks similar to:
    assert.IsType(t, Step2{}, result)
    Without the interface I I'm not sure how to compare the returned
    function type without using reflection or runtime, both of which seem
    like a step in the wrong direction.

    I can't directly compare function types in Go for equality.
    Theoretically I could declare local variables pointing to each step
    function and then compare the addresses of those, but since the step
    functions have a cyclical nature (Step4 -> Step6 -> Step4), Go
    complains about an "initialization loop".

    While the empty structs are a bit of a wart in the source code it
    seems worth it for the benefit of interface equality comparisons. Or
    am I missing something obvious?

    You're not missing anything obvious, function equality is not defined. You
    may want to take a step back though and try to test only client-visible
    state in your tests, instead of testing implementation details like
    precisely which step is returned. Among other things, this will allow you
    to make changes to the implementation without having to spuriously modify a
    test; it also often makes for more coherent and readable test cases (e.g.
    for a state-based lexer, seeing a string like "0x12x4" in a table driven
    test is often more evocative than tracing through a sequence of state
    checks and transitions in if statements).

    brian

    The step1, step2... and most of the code is non-descriptive... From just
    reading the code it's hard to understand what it does. It might make
    sense
    so that the code uses words like "worker" "job" as array indexes, or
    something like that... but I'm not able to give very good advice without
    thoroughly going through the algorithm myself.

    It might make sense to avoid the whole "step" ... thing and try to write
    something like:

    // step 0
    m := createMatrix(jobs, workers)
    assignCosts(m, ...)
    // step 1
    for _, row := range rows(m.A) {
    v := min(row...)
    subtract(work, v)
    }
    // step 2
    Z, row, col := findZero(m)
    if ctx.hasStarIn(row, col) (
    ctx.markStarred(Z)
    }
    ... etc...

    (WARNING, no clue about the actual algorithm, just trying to write the
    6-step algorithm into code)

    But then again, since the original paper contained the "step0",
    "step1"...
    approach, it's probably safer that way... it's easier to verify whether
    it's
    correct, although the readability/understandability of the code won't be
    great. Also my suggestion is worse from observability standpoint... so
    nevermind :)
    Yeah, at this point I'd rather match the paper. As non-descriptive as
    the named steps are, at least they're consistent with the upstream
    documentation. Perhaps the code should provide a few more breadcrumb
    links to better document the source material.
    You should probably get rid of the "i*n" multiplications in the loops
    (unnecessary calculations), e.g.
    Sure, can do.
    func erasePrimes(ctx *Context) {
    n := ctx.m.n
    n2 := n*n
    for i := 0; i < n2; i += n {
    for j := 0; j < n; j++ {
    if ctx.marked[i+j] == Primed {
    ...

    func findPrimeInRow(ctx *Context, row int) int {
    n := ctx.m.n
    rowstart := row*n
    for j := 0; j < n; j++ {
    if ctx.marked[rowstart + j] == Primed {

    + egon
    Thanks for taking a look.

    brian
    And, since this is Open Source, patches or pull requests are welcome!

    brian

    On Wed, Feb 19, 2014 at 1:44 PM, Brian Fallik wrote:
    Hi,

    Wondering if any Gophers out there have experience using the go-gt
    package [1], specifically its Hungarian() [2] method.

    I'm exploring solutions to an assignment problem but the go-gt
    implementation panics with "Index out of range" for certain input.
    I've logged the bug [3] but haven't seen any response so I wonder if
    the library is actively maintained. I suspect the bug is in go-gt
    since (AFAIK) the Hungarian algorithm itself safely handles any
    square
    matrix.

    Is anyone out there using this code successfully? Am I just missing
    something obvious?

    Alternatively is there another recommended graph library I should be
    using? I found go-gt on the go-wiki [4].

    Thanks,
    brian


    1 - https://code.google.com/p/go-gt/
    2 - https://code.google.com/p/go-gt/source/browse/gt/hungarian.go
    3 - https://code.google.com/p/go-gt/issues/detail?id=2
    4 - https://code.google.com/p/go-wiki/wiki/Projects#Mathematics
    --
    You received this message because you are subscribed to the Google
    Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send
    an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Egon at Mar 20, 2014 at 7:35 am

    On Wednesday, March 19, 2014 5:31:15 AM UTC+2, Brian Fallik wrote:
    Hi,
    On Tue, Mar 18, 2014 at 7:25 PM, Brian Fallik wrote:
    Hi,

    On Tue, Mar 18, 2014 at 1:28 PM, egon <egon...@gmail.com <javascript:>>
    wrote:
    On Monday, March 17, 2014 4:31:46 PM UTC+2, Brian Fallik wrote:

    Hello Gophers,

    I'm happy to announce the release of a small package providing an
    implementation of the Hungarian Assignment algorithm (a.k.a.
    Kuhn-Munkres a.k.a. Munkres). The code is available here:
    https://github.com/clyphub/munkres
    See the repo for README and license information.

    I developed this code for my employer, clypd, after encountering an
    issue with the existing implementation available in go-gt. I
    previously sent an email to this list (copied below) but didn't hear
    any responses so decided to roll my own.

    As I'm relatively new to Go I'd appreciate any feedback on this code.

    One thing I noticed that you can replace your Step interface with this:

    type Step func(ctx *Context) (Step, bool)

    That way you don't need those "type Step1 struct{}" stubs. e.g.

    func step1(ctx *Context) (Step, bool) { return step2, true }
    That makes sense - the Interface may be overkill when all I'm doing is
    declaring it to contain a single function. I wondered about that but
    ultimately opted for the Interface approach. I'll take a look at
    switching it.
    After attempting to remove the interface I ran into the problem I
    remember encountering during development which prompted me to move to
    the interface in the first place. Perhaps someone can enlighten me on
    a better approach.

    The tests try to ensure that, after each stage of the algorithm (a
    "Mark" in the test code), the current step returns the correct next
    step. The line of test code looks similar to:
    assert.IsType(t, Step2{}, result)
    Without the interface I I'm not sure how to compare the returned
    function type without using reflection or runtime, both of which seem
    like a step in the wrong direction.

    I can't directly compare function types in Go for equality.
    Theoretically I could declare local variables pointing to each step
    function and then compare the addresses of those, but since the step
    functions have a cyclical nature (Step4 -> Step6 -> Step4), Go
    complains about an "initialization loop".

    While the empty structs are a bit of a wart in the source code it
    seems worth it for the benefit of interface equality comparisons. Or
    am I missing something obvious?
    I would simply test whether each step got me the correct matrix. As for the
    flow I would run a few full cases checking each matrix at each step. And
    obviously test for the visible interface. You probably don't need to
    explicitly check the returned next step... when it's wrong then the next
    step matrix check will probably fail.

    As for Kyle-s suggestion only testing the "visible interface", I would
    generally agree with this, but at the moment, it's quite a complex process,
    and when you do some speed improvements, then tracking down the "bug" will
    be much easier with fine-grained tests... obviously they are based on just
    checking a matrix, which means you won't have too much trouble with writing
    those or getting rid of them. tl;dr; Yes, when you modify the algorithm
    then the tests change, but the cost of changing them is (probably) small.

    + egon

    brian

    The step1, step2... and most of the code is non-descriptive... From
    just
    reading the code it's hard to understand what it does. It might make
    sense
    so that the code uses words like "worker" "job" as array indexes, or
    something like that... but I'm not able to give very good advice
    without
    thoroughly going through the algorithm myself.

    It might make sense to avoid the whole "step" ... thing and try to
    write
    something like:

    // step 0
    m := createMatrix(jobs, workers)
    assignCosts(m, ...)
    // step 1
    for _, row := range rows(m.A) {
    v := min(row...)
    subtract(work, v)
    }
    // step 2
    Z, row, col := findZero(m)
    if ctx.hasStarIn(row, col) (
    ctx.markStarred(Z)
    }
    ... etc...

    (WARNING, no clue about the actual algorithm, just trying to write the
    6-step algorithm into code)

    But then again, since the original paper contained the "step0",
    "step1"...
    approach, it's probably safer that way... it's easier to verify whether
    it's
    correct, although the readability/understandability of the code won't
    be
    great. Also my suggestion is worse from observability standpoint... so
    nevermind :)
    Yeah, at this point I'd rather match the paper. As non-descriptive as
    the named steps are, at least they're consistent with the upstream
    documentation. Perhaps the code should provide a few more breadcrumb
    links to better document the source material.
    You should probably get rid of the "i*n" multiplications in the loops
    (unnecessary calculations), e.g.
    Sure, can do.
    func erasePrimes(ctx *Context) {
    n := ctx.m.n
    n2 := n*n
    for i := 0; i < n2; i += n {
    for j := 0; j < n; j++ {
    if ctx.marked[i+j] == Primed {
    ...

    func findPrimeInRow(ctx *Context, row int) int {
    n := ctx.m.n
    rowstart := row*n
    for j := 0; j < n; j++ {
    if ctx.marked[rowstart + j] == Primed {

    + egon
    Thanks for taking a look.

    brian
    And, since this is Open Source, patches or pull requests are welcome!

    brian

    On Wed, Feb 19, 2014 at 1:44 PM, Brian Fallik wrote:
    Hi,

    Wondering if any Gophers out there have experience using the go-gt
    package [1], specifically its Hungarian() [2] method.

    I'm exploring solutions to an assignment problem but the go-gt
    implementation panics with "Index out of range" for certain input.
    I've logged the bug [3] but haven't seen any response so I wonder if
    the library is actively maintained. I suspect the bug is in go-gt
    since (AFAIK) the Hungarian algorithm itself safely handles any
    square
    matrix.

    Is anyone out there using this code successfully? Am I just missing
    something obvious?

    Alternatively is there another recommended graph library I should be
    using? I found go-gt on the go-wiki [4].

    Thanks,
    brian


    1 - https://code.google.com/p/go-gt/
    2 - https://code.google.com/p/go-gt/source/browse/gt/hungarian.go
    3 - https://code.google.com/p/go-gt/issues/detail?id=2
    4 - https://code.google.com/p/go-wiki/wiki/Projects#Mathematics
    --
    You received this message because you are subscribed to the Google
    Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send
    an
    email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Brian Fallik at Mar 21, 2014 at 2:10 pm

    On Thu, Mar 20, 2014 at 3:34 AM, egon wrote:
    On Wednesday, March 19, 2014 5:31:15 AM UTC+2, Brian Fallik wrote:

    Hi,
    On Tue, Mar 18, 2014 at 7:25 PM, Brian Fallik wrote:
    Hi,
    On Tue, Mar 18, 2014 at 1:28 PM, egon wrote:
    On Monday, March 17, 2014 4:31:46 PM UTC+2, Brian Fallik wrote:

    Hello Gophers,

    I'm happy to announce the release of a small package providing an
    implementation of the Hungarian Assignment algorithm (a.k.a.
    Kuhn-Munkres a.k.a. Munkres). The code is available here:
    https://github.com/clyphub/munkres
    See the repo for README and license information.

    I developed this code for my employer, clypd, after encountering an
    issue with the existing implementation available in go-gt. I
    previously sent an email to this list (copied below) but didn't hear
    any responses so decided to roll my own.

    As I'm relatively new to Go I'd appreciate any feedback on this code.

    One thing I noticed that you can replace your Step interface with this:

    type Step func(ctx *Context) (Step, bool)

    That way you don't need those "type Step1 struct{}" stubs. e.g.

    func step1(ctx *Context) (Step, bool) { return step2, true }
    That makes sense - the Interface may be overkill when all I'm doing is
    declaring it to contain a single function. I wondered about that but
    ultimately opted for the Interface approach. I'll take a look at
    switching it.
    After attempting to remove the interface I ran into the problem I
    remember encountering during development which prompted me to move to
    the interface in the first place. Perhaps someone can enlighten me on
    a better approach.

    The tests try to ensure that, after each stage of the algorithm (a
    "Mark" in the test code), the current step returns the correct next
    step. The line of test code looks similar to:
    assert.IsType(t, Step2{}, result)
    Without the interface I I'm not sure how to compare the returned
    function type without using reflection or runtime, both of which seem
    like a step in the wrong direction.

    I can't directly compare function types in Go for equality.
    Theoretically I could declare local variables pointing to each step
    function and then compare the addresses of those, but since the step
    functions have a cyclical nature (Step4 -> Step6 -> Step4), Go
    complains about an "initialization loop".

    While the empty structs are a bit of a wart in the source code it
    seems worth it for the benefit of interface equality comparisons. Or
    am I missing something obvious?

    I would simply test whether each step got me the correct matrix. As for the
    flow I would run a few full cases checking each matrix at each step. And
    obviously test for the visible interface. You probably don't need to
    explicitly check the returned next step... when it's wrong then the next
    step matrix check will probably fail.

    As for Kyle-s suggestion only testing the "visible interface", I would
    generally agree with this, but at the moment, it's quite a complex process,
    and when you do some speed improvements, then tracking down the "bug" will
    be much easier with fine-grained tests... obviously they are based on just
    checking a matrix, which means you won't have too much trouble with writing
    those or getting rid of them. tl;dr; Yes, when you modify the algorithm then
    the tests change, but the cost of changing them is (probably) small.
    Kyle and Egon,

    Thanks so much for the input. I hear what you both are saying
    regarding testing the visible interfaces but I'm having a little
    trouble understanding the benefit in this specific case. I don't think
    I understand the drawback(s) of the interface+struct{} approach
    besides the few extra lines of declarations.

    My experience from other languages is that testing in the small - by
    unit testing isolated functions individually - is more expressive and
    flexible than trying to test larger assemblies. Both are valuable, but
    I often test smaller pieces to ensure I can hit corner cases. Larger
    black box testing is valuable for an end-to-end view but usually fails
    to provide the same level of control since setting up the testing
    context typically involves more effort. Given that the testing package
    has internal access to non-exported package elements its design seems
    to promote finer-grained testing.

    Of course this may just be a question of degrees, but I am interested
    in trying to understand this feedback a bit more.

    brian

    + egon
    brian

    The step1, step2... and most of the code is non-descriptive... From
    just
    reading the code it's hard to understand what it does. It might make
    sense
    so that the code uses words like "worker" "job" as array indexes, or
    something like that... but I'm not able to give very good advice
    without
    thoroughly going through the algorithm myself.

    It might make sense to avoid the whole "step" ... thing and try to
    write
    something like:

    // step 0
    m := createMatrix(jobs, workers)
    assignCosts(m, ...)
    // step 1
    for _, row := range rows(m.A) {
    v := min(row...)
    subtract(work, v)
    }
    // step 2
    Z, row, col := findZero(m)
    if ctx.hasStarIn(row, col) (
    ctx.markStarred(Z)
    }
    ... etc...

    (WARNING, no clue about the actual algorithm, just trying to write the
    6-step algorithm into code)

    But then again, since the original paper contained the "step0",
    "step1"...
    approach, it's probably safer that way... it's easier to verify whether
    it's
    correct, although the readability/understandability of the code won't
    be
    great. Also my suggestion is worse from observability standpoint... so
    nevermind :)
    Yeah, at this point I'd rather match the paper. As non-descriptive as
    the named steps are, at least they're consistent with the upstream
    documentation. Perhaps the code should provide a few more breadcrumb
    links to better document the source material.
    You should probably get rid of the "i*n" multiplications in the loops
    (unnecessary calculations), e.g.
    Sure, can do.
    func erasePrimes(ctx *Context) {
    n := ctx.m.n
    n2 := n*n
    for i := 0; i < n2; i += n {
    for j := 0; j < n; j++ {
    if ctx.marked[i+j] == Primed {
    ...

    func findPrimeInRow(ctx *Context, row int) int {
    n := ctx.m.n
    rowstart := row*n
    for j := 0; j < n; j++ {
    if ctx.marked[rowstart + j] == Primed {

    + egon
    Thanks for taking a look.

    brian
    And, since this is Open Source, patches or pull requests are welcome!

    brian


    On Wed, Feb 19, 2014 at 1:44 PM, Brian Fallik <bfa...@gmail.com>
    wrote:
    Hi,

    Wondering if any Gophers out there have experience using the go-gt
    package [1], specifically its Hungarian() [2] method.

    I'm exploring solutions to an assignment problem but the go-gt
    implementation panics with "Index out of range" for certain input.
    I've logged the bug [3] but haven't seen any response so I wonder if
    the library is actively maintained. I suspect the bug is in go-gt
    since (AFAIK) the Hungarian algorithm itself safely handles any
    square
    matrix.

    Is anyone out there using this code successfully? Am I just missing
    something obvious?

    Alternatively is there another recommended graph library I should be
    using? I found go-gt on the go-wiki [4].

    Thanks,
    brian


    1 - https://code.google.com/p/go-gt/
    2 - https://code.google.com/p/go-gt/source/browse/gt/hungarian.go
    3 - https://code.google.com/p/go-gt/issues/detail?id=2
    4 - https://code.google.com/p/go-wiki/wiki/Projects#Mathematics
    --
    You received this message because you are subscribed to the Google
    Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send
    an
    email to golang-nuts...@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Egon at Mar 21, 2014 at 2:48 pm

    On Friday, March 21, 2014 4:09:57 PM UTC+2, Brian Fallik wrote:
    On Thu, Mar 20, 2014 at 3:34 AM, egon <egon...@gmail.com <javascript:>>
    wrote:
    On Wednesday, March 19, 2014 5:31:15 AM UTC+2, Brian Fallik wrote:

    Hi,
    On Tue, Mar 18, 2014 at 7:25 PM, Brian Fallik wrote:
    Hi,
    On Tue, Mar 18, 2014 at 1:28 PM, egon wrote:
    On Monday, March 17, 2014 4:31:46 PM UTC+2, Brian Fallik wrote:

    Hello Gophers,

    I'm happy to announce the release of a small package providing an
    implementation of the Hungarian Assignment algorithm (a.k.a.
    Kuhn-Munkres a.k.a. Munkres). The code is available here:
    https://github.com/clyphub/munkres
    See the repo for README and license information.

    I developed this code for my employer, clypd, after encountering an
    issue with the existing implementation available in go-gt. I
    previously sent an email to this list (copied below) but didn't
    hear
    any responses so decided to roll my own.

    As I'm relatively new to Go I'd appreciate any feedback on this
    code.

    One thing I noticed that you can replace your Step interface with
    this:
    type Step func(ctx *Context) (Step, bool)

    That way you don't need those "type Step1 struct{}" stubs. e.g.

    func step1(ctx *Context) (Step, bool) { return step2, true }
    That makes sense - the Interface may be overkill when all I'm doing
    is
    declaring it to contain a single function. I wondered about that but
    ultimately opted for the Interface approach. I'll take a look at
    switching it.
    After attempting to remove the interface I ran into the problem I
    remember encountering during development which prompted me to move to
    the interface in the first place. Perhaps someone can enlighten me on
    a better approach.

    The tests try to ensure that, after each stage of the algorithm (a
    "Mark" in the test code), the current step returns the correct next
    step. The line of test code looks similar to:
    assert.IsType(t, Step2{}, result)
    Without the interface I I'm not sure how to compare the returned
    function type without using reflection or runtime, both of which seem
    like a step in the wrong direction.

    I can't directly compare function types in Go for equality.
    Theoretically I could declare local variables pointing to each step
    function and then compare the addresses of those, but since the step
    functions have a cyclical nature (Step4 -> Step6 -> Step4), Go
    complains about an "initialization loop".

    While the empty structs are a bit of a wart in the source code it
    seems worth it for the benefit of interface equality comparisons. Or
    am I missing something obvious?

    I would simply test whether each step got me the correct matrix. As for the
    flow I would run a few full cases checking each matrix at each step. And
    obviously test for the visible interface. You probably don't need to
    explicitly check the returned next step... when it's wrong then the next
    step matrix check will probably fail.

    As for Kyle-s suggestion only testing the "visible interface", I would
    generally agree with this, but at the moment, it's quite a complex process,
    and when you do some speed improvements, then tracking down the "bug" will
    be much easier with fine-grained tests... obviously they are based on just
    checking a matrix, which means you won't have too much trouble with writing
    those or getting rid of them. tl;dr; Yes, when you modify the algorithm then
    the tests change, but the cost of changing them is (probably) small.
    Kyle and Egon,

    Thanks so much for the input. I hear what you both are saying
    regarding testing the visible interfaces but I'm having a little
    trouble understanding the benefit in this specific case. I don't think
    I understand the drawback(s) of the interface+struct{} approach
    besides the few extra lines of declarations.
    In this case the differences are probably small so doing either won't
    matter that much. But, what we practice is what we'll do in the future.

    Firstly, I definitely do not agree with making something "more testable" at
    the cost of more difficult implementation. If the only reason to make a
    change to the design is to "make it testable", then I believe it worsens
    the code quality rather than benefits it. If you can find a better design,
    because it's not testable, then there's a benefit.

    The benefit from testing the "next step" isn't very big, because other
    tests will probably catch it anyway... so making a decision to add the
    "struct" is a net-loss... i.e. you added a test that didn't do anything
    useful and you made your design worse. (Of course it's only marginally
    worse...)

    The problem with fine-grained tests is that they split the functionality to
    smaller and smaller pieces until there's nothing left of the original
    implementation and you'll have a pile of quarter-ideas that do something
    together; which means the code is hard to read.

    Fine-grained tests can often just duplicate the logic of the code... if the
    code isn't clear what it does and it needs tests to make sure it works,
    then the initial code should improved.

    Randomized tests will probably work better for finding the problematic
    cases. If you use deterministic tests you can only think of the
    border-cases which have been taken into account when implementing. Those
    border-cases that you weren't able to think about are more likely to fail.
    It's more beneficial to write a randomized test for the visible parts than
    multiple fine-grained tests for the internals.

    Tests are not free, they take resource to maintain, fix and change. So if
    you decide to improve your code by changing few of the steps then you would
    need to fix the tests as well... of course if you only test the visible
    parts, then there's no need for fixing the tests.

    + egon

    My experience from other languages is that testing in the small - by
    unit testing isolated functions individually - is more expressive and
    flexible than trying to test larger assemblies. Both are valuable, but
    I often test smaller pieces to ensure I can hit corner cases. Larger
    black box testing is valuable for an end-to-end view but usually fails
    to provide the same level of control since setting up the testing
    context typically involves more effort. Given that the testing package
    has internal access to non-exported package elements its design seems
    to promote finer-grained testing.

    Of course this may just be a question of degrees, but I am interested
    in trying to understand this feedback a bit more.

    brian

    + egon
    brian

    The step1, step2... and most of the code is non-descriptive... From
    just
    reading the code it's hard to understand what it does. It might make
    sense
    so that the code uses words like "worker" "job" as array indexes, or
    something like that... but I'm not able to give very good advice
    without
    thoroughly going through the algorithm myself.

    It might make sense to avoid the whole "step" ... thing and try to
    write
    something like:

    // step 0
    m := createMatrix(jobs, workers)
    assignCosts(m, ...)
    // step 1
    for _, row := range rows(m.A) {
    v := min(row...)
    subtract(work, v)
    }
    // step 2
    Z, row, col := findZero(m)
    if ctx.hasStarIn(row, col) (
    ctx.markStarred(Z)
    }
    ... etc...

    (WARNING, no clue about the actual algorithm, just trying to write
    the
    6-step algorithm into code)

    But then again, since the original paper contained the "step0",
    "step1"...
    approach, it's probably safer that way... it's easier to verify
    whether
    it's
    correct, although the readability/understandability of the code
    won't
    be
    great. Also my suggestion is worse from observability standpoint...
    so
    nevermind :)
    Yeah, at this point I'd rather match the paper. As non-descriptive as
    the named steps are, at least they're consistent with the upstream
    documentation. Perhaps the code should provide a few more breadcrumb
    links to better document the source material.
    You should probably get rid of the "i*n" multiplications in the
    loops
    (unnecessary calculations), e.g.
    Sure, can do.
    func erasePrimes(ctx *Context) {
    n := ctx.m.n
    n2 := n*n
    for i := 0; i < n2; i += n {
    for j := 0; j < n; j++ {
    if ctx.marked[i+j] == Primed {
    ...

    func findPrimeInRow(ctx *Context, row int) int {
    n := ctx.m.n
    rowstart := row*n
    for j := 0; j < n; j++ {
    if ctx.marked[rowstart + j] == Primed {

    + egon
    Thanks for taking a look.

    brian
    And, since this is Open Source, patches or pull requests are
    welcome!
    brian


    On Wed, Feb 19, 2014 at 1:44 PM, Brian Fallik <bfa...@gmail.com>
    wrote:
    Hi,

    Wondering if any Gophers out there have experience using the
    go-gt
    package [1], specifically its Hungarian() [2] method.

    I'm exploring solutions to an assignment problem but the go-gt
    implementation panics with "Index out of range" for certain
    input.
    I've logged the bug [3] but haven't seen any response so I wonder
    if
    the library is actively maintained. I suspect the bug is in go-gt
    since (AFAIK) the Hungarian algorithm itself safely handles any
    square
    matrix.

    Is anyone out there using this code successfully? Am I just
    missing
    something obvious?

    Alternatively is there another recommended graph library I should
    be
    --
    You received this message because you are subscribed to the Google
    Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it,
    send
    an
    email to golang-nuts...@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Brian Fallik at Mar 21, 2014 at 3:20 pm
    Hi,
    On Fri, Mar 21, 2014 at 10:48 AM, egon wrote:

    On Friday, March 21, 2014 4:09:57 PM UTC+2, Brian Fallik wrote:
    On Thu, Mar 20, 2014 at 3:34 AM, egon wrote:

    On Wednesday, March 19, 2014 5:31:15 AM UTC+2, Brian Fallik wrote:

    Hi,
    On Tue, Mar 18, 2014 at 7:25 PM, Brian Fallik wrote:
    Hi,
    On Tue, Mar 18, 2014 at 1:28 PM, egon wrote:
    On Monday, March 17, 2014 4:31:46 PM UTC+2, Brian Fallik wrote:

    Hello Gophers,

    I'm happy to announce the release of a small package providing an
    implementation of the Hungarian Assignment algorithm (a.k.a.
    Kuhn-Munkres a.k.a. Munkres). The code is available here:
    https://github.com/clyphub/munkres
    See the repo for README and license information.

    I developed this code for my employer, clypd, after encountering an
    issue with the existing implementation available in go-gt. I
    previously sent an email to this list (copied below) but didn't
    hear
    any responses so decided to roll my own.

    As I'm relatively new to Go I'd appreciate any feedback on this
    code.

    One thing I noticed that you can replace your Step interface with
    this:

    type Step func(ctx *Context) (Step, bool)

    That way you don't need those "type Step1 struct{}" stubs. e.g.

    func step1(ctx *Context) (Step, bool) { return step2, true }
    That makes sense - the Interface may be overkill when all I'm doing
    is
    declaring it to contain a single function. I wondered about that but
    ultimately opted for the Interface approach. I'll take a look at
    switching it.
    After attempting to remove the interface I ran into the problem I
    remember encountering during development which prompted me to move to
    the interface in the first place. Perhaps someone can enlighten me on
    a better approach.

    The tests try to ensure that, after each stage of the algorithm (a
    "Mark" in the test code), the current step returns the correct next
    step. The line of test code looks similar to:
    assert.IsType(t, Step2{}, result)
    Without the interface I I'm not sure how to compare the returned
    function type without using reflection or runtime, both of which seem
    like a step in the wrong direction.

    I can't directly compare function types in Go for equality.
    Theoretically I could declare local variables pointing to each step
    function and then compare the addresses of those, but since the step
    functions have a cyclical nature (Step4 -> Step6 -> Step4), Go
    complains about an "initialization loop".

    While the empty structs are a bit of a wart in the source code it
    seems worth it for the benefit of interface equality comparisons. Or
    am I missing something obvious?

    I would simply test whether each step got me the correct matrix. As for
    the
    flow I would run a few full cases checking each matrix at each step. And
    obviously test for the visible interface. You probably don't need to
    explicitly check the returned next step... when it's wrong then the next
    step matrix check will probably fail.

    As for Kyle-s suggestion only testing the "visible interface", I would
    generally agree with this, but at the moment, it's quite a complex
    process,
    and when you do some speed improvements, then tracking down the "bug"
    will
    be much easier with fine-grained tests... obviously they are based on
    just
    checking a matrix, which means you won't have too much trouble with
    writing
    those or getting rid of them. tl;dr; Yes, when you modify the algorithm
    then
    the tests change, but the cost of changing them is (probably) small.
    Kyle and Egon,

    Thanks so much for the input. I hear what you both are saying
    regarding testing the visible interfaces but I'm having a little
    trouble understanding the benefit in this specific case. I don't think
    I understand the drawback(s) of the interface+struct{} approach
    besides the few extra lines of declarations.

    In this case the differences are probably small so doing either won't matter
    that much. But, what we practice is what we'll do in the future.
    Right, just trying to learn more from this example.
    Firstly, I definitely do not agree with making something "more testable" at
    the cost of more difficult implementation. If the only reason to make a
    change to the design is to "make it testable", then I believe it worsens the
    code quality rather than benefits it. If you can find a better design,
    because it's not testable, then there's a benefit.

    The benefit from testing the "next step" isn't very big, because other tests
    will probably catch it anyway... so making a decision to add the "struct" is
    a net-loss... i.e. you added a test that didn't do anything useful and you
    made your design worse. (Of course it's only marginally worse...)
    I think I understand a bit better. Taken to it's conclusion, in this
    case the test code should simply pass in the input matrix and verify
    the output assignments without taking into consideration the stepwise
    results.There's less test code to maintain. The drawback is less
    testing precision, which in this case is marginal anyway since each
    test mark simply passes through the context from the previous mark.
    The problem with fine-grained tests is that they split the functionality to
    smaller and smaller pieces until there's nothing left of the original
    implementation and you'll have a pile of quarter-ideas that do something
    together; which means the code is hard to read.

    Fine-grained tests can often just duplicate the logic of the code... if the
    code isn't clear what it does and it needs tests to make sure it works, then
    the initial code should improved.

    Randomized tests will probably work better for finding the problematic
    cases. If you use deterministic tests you can only think of the border-cases
    which have been taken into account when implementing. Those border-cases
    that you weren't able to think about are more likely to fail. It's more
    beneficial to write a randomized test for the visible parts than multiple
    fine-grained tests for the internals.

    Tests are not free, they take resource to maintain, fix and change. So if
    you decide to improve your code by changing few of the steps then you would
    need to fix the tests as well... of course if you only test the visible
    parts, then there's no need for fixing the tests.
    Right, I don't disagree there.

    Thanks for the explanation,
    brian
    + egon
    My experience from other languages is that testing in the small - by
    unit testing isolated functions individually - is more expressive and
    flexible than trying to test larger assemblies. Both are valuable, but
    I often test smaller pieces to ensure I can hit corner cases. Larger
    black box testing is valuable for an end-to-end view but usually fails
    to provide the same level of control since setting up the testing
    context typically involves more effort. Given that the testing package
    has internal access to non-exported package elements its design seems
    to promote finer-grained testing.

    Of course this may just be a question of degrees, but I am interested
    in trying to understand this feedback a bit more.

    brian

    + egon
    brian

    The step1, step2... and most of the code is non-descriptive... From
    just
    reading the code it's hard to understand what it does. It might make
    sense
    so that the code uses words like "worker" "job" as array indexes, or
    something like that... but I'm not able to give very good advice
    without
    thoroughly going through the algorithm myself.

    It might make sense to avoid the whole "step" ... thing and try to
    write
    something like:

    // step 0
    m := createMatrix(jobs, workers)
    assignCosts(m, ...)
    // step 1
    for _, row := range rows(m.A) {
    v := min(row...)
    subtract(work, v)
    }
    // step 2
    Z, row, col := findZero(m)
    if ctx.hasStarIn(row, col) (
    ctx.markStarred(Z)
    }
    ... etc...

    (WARNING, no clue about the actual algorithm, just trying to write
    the
    6-step algorithm into code)

    But then again, since the original paper contained the "step0",
    "step1"...
    approach, it's probably safer that way... it's easier to verify
    whether
    it's
    correct, although the readability/understandability of the code
    won't
    be
    great. Also my suggestion is worse from observability standpoint...
    so
    nevermind :)
    Yeah, at this point I'd rather match the paper. As non-descriptive as
    the named steps are, at least they're consistent with the upstream
    documentation. Perhaps the code should provide a few more breadcrumb
    links to better document the source material.
    You should probably get rid of the "i*n" multiplications in the
    loops
    (unnecessary calculations), e.g.
    Sure, can do.
    func erasePrimes(ctx *Context) {
    n := ctx.m.n
    n2 := n*n
    for i := 0; i < n2; i += n {
    for j := 0; j < n; j++ {
    if ctx.marked[i+j] == Primed {
    ...

    func findPrimeInRow(ctx *Context, row int) int {
    n := ctx.m.n
    rowstart := row*n
    for j := 0; j < n; j++ {
    if ctx.marked[rowstart + j] == Primed {

    + egon
    Thanks for taking a look.

    brian
    And, since this is Open Source, patches or pull requests are
    welcome!

    brian


    On Wed, Feb 19, 2014 at 1:44 PM, Brian Fallik <bfa...@gmail.com>
    wrote:
    Hi,

    Wondering if any Gophers out there have experience using the
    go-gt
    package [1], specifically its Hungarian() [2] method.

    I'm exploring solutions to an assignment problem but the go-gt
    implementation panics with "Index out of range" for certain
    input.
    I've logged the bug [3] but haven't seen any response so I wonder
    if
    the library is actively maintained. I suspect the bug is in go-gt
    since (AFAIK) the Hungarian algorithm itself safely handles any
    square
    matrix.

    Is anyone out there using this code successfully? Am I just
    missing
    something obvious?

    Alternatively is there another recommended graph library I should
    be
    using? I found go-gt on the go-wiki [4].

    Thanks,
    brian


    1 - https://code.google.com/p/go-gt/
    2 - https://code.google.com/p/go-gt/source/browse/gt/hungarian.go
    3 - https://code.google.com/p/go-gt/issues/detail?id=2
    4 - https://code.google.com/p/go-wiki/wiki/Projects#Mathematics
    --
    You received this message because you are subscribed to the Google
    Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it,
    send
    an
    email to golang-nuts...@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google
    Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send
    an
    email to golang-nuts...@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedMar 17, '14 at 2:32p
activeMar 21, '14 at 3:20p
posts11
users4
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase