#227 Bug in algorithm for overdetermined detection

closed
nobody
5
2014-07-09
2012-07-30
Michael Hucka
No

This was spotted by Andreas Draeger:

From: Andreas Dr?ger andreas.draeger@uni-tuebingen.de To: Sven Sahle sven.sahle@bioquant.uni-heidelberg.de CC: sbml-editors@caltech.edu, a.doerr@student.uni-tuebingen.de Subject: Re: [sbml-editors] Algorithm to check whether a model is overdetermined and solving algebraic rules version-4-rel-1.pdf Date: Thu, 10 Jun 2010 10:45:30 +0200

Dear all,

We now have checked the matching algorithm to determine which algebraic rules determine the value of which species/compartmens/parameters.

It seems that the description of the algorithm as given in the specification of "Level 3 Version 1 Core Release Candidate 1" is correct and works fine for the models in the SBML test suite.

The main difference between the description of the algorithm in "Level 2 Version 2" and the one of Level 3 is that no edges are to be created between assignment rules and its elements anymore besides the variable field. This significantly reduces the number of edges in the bipartite matching. Furthermore, the edges between assignment rules and elements other than the variable field are not needed at all because only the value of the variable is to be determined by an assignment rule.

The paper of Hopcroft and Karp that is cited by the specification is hard to understand due to several technical mistakes in the publication. Implementing the algorithm exactly as described in the paper leads to incorrect solutions. As an example, we can mention the most crucial issue here: the so-called Hopcroft-Karp algorithm is explained at page 5, but the algorithm to obtain the maximum matching is actually on page 3 of the paper, where the Hopcroft-Karp algorithm is invoked first to obtain an arbitrary matching as a starting point. This matching is then to be extended in a step-wise procedure. The mistake is that after calling Hopcroft-Karp, the set M is re-initialized as an empty set instead of using the matching just computed by the Hopcroft-Karp algorithm. After this change, the algorithm works well. This means, the paper should look like this:

M - HopcroftKarp(G); ...

instead of

HopcroftKarp(G); M - emptySet(); ...

Discussion

  • Chris Myers
    Chris Myers
    2012-08-01

    I am accepting this issue as valid.

     
  • Sarah Keating
    Sarah Keating
    2012-08-05

    They are quite right that we simplified the algorithm between l2v4 and L3v1 to reduce the number of matchings you begin with. This is not actually an error though - it merely makes the initial matchings fewer and the elimination of matchings faster. It improves the algorithm as applied to sbml; rather than corrects it.

    And yes I agree the Hopcroft and Karp paper is not the easiset thing in the world to understand and I do not really explain the actual algorithm or how to implement it; but is that the job of the SBML spec. I know googling bipartite matching and Hopcroft and Karp does produce examples of code that other people have written; which helps to figure it out.

     
  • Lucian Smith
    Lucian Smith
    2014-04-04

    • labels: Level 2 Version 4 --> Level 2 Version 4, Level 3 Version 1 Core
     
  • Lucian Smith
    Lucian Smith
    2014-04-04

    Whoops, misread: not actually a l3v1 issue. Can we close this issue for l2v4 as well?

     
  • Lucian Smith
    Lucian Smith
    2014-04-04

    • labels: Level 2 Version 4, Level 3 Version 1 Core --> Level 2 Version 4
     
  • Michael Hucka
    Michael Hucka
    2014-06-04

    This is not an issue for L3.

    We can't close the issue for L2 because the problem still exists. This is thus an issue for L2v5.

    I propose we make the L2v5 algorithm match the L3 one.

     
  • Frank Bergmann
    Frank Bergmann
    2014-06-28

    Mike's proposal of making the L2v5 algorithm match L3 core works for me.

     
  • I am fine with L2V5 matching L3 core

     
  • Lucian Smith
    Lucian Smith
    2014-07-08

    This is now fixed in SVN and added to the errata page, but we do still need one more vote from Brett, Dagmar, or Sven to make it official (or for them to vote en masse against it to make it unofficial).

     
  • I accept the issue as valid.
    I agree to making the L2v5 algorithm match the L3 one.

     
  • Lucian Smith
    Lucian Smith
    2014-07-09

    • status: open --> closed
    • Group: Reported-Proposed --> Accept-no-conformance-implications
     
  • Lucian Smith
    Lucian Smith
    2014-07-09

    Great! This issue is now officially accepted, incorporated into SVN, and will be part of the forthcoming L2v5 specification.