This was spotted by Andreas Draeger:
From: Andreas Dr?ger email@example.com To: Sven Sahle firstname.lastname@example.org CC: email@example.com, firstname.lastname@example.org 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
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(); ...