#227 Bug in algorithm for overdetermined detection

closed
nobody
5
2014-07-09
2012-07-30
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); ...

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

Discussion

• Chris Myers - 2012-08-01

I am accepting this issue as valid.

• 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 - 2014-04-04
• labels: Level 2 Version 4 --> Level 2 Version 4, Level 3 Version 1 Core

• Lucian Smith - 2014-04-04

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

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

• 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 - 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 - 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).

• Dagmar Waltemath - 2014-07-09

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

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

• Lucian Smith - 2014-07-09

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