org.sbml.jsbml.validator

Class OverdeterminationValidator

java.lang.Object

org.sbml.jsbml.validator.OverdeterminationValidator

public class OverdeterminationValidator
extends java.lang.Object

This class creates a bipartite graph and a matching for the given model using the algorithm by Hopcroft and Karp (1973).

Since:

0.8

Author:

Alexander Dörr

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private class	OverdeterminationValidator.InnerNode<T extends SBase> This class represents an inner node in the bipartite graph, e.g., a varibale or an reaction
private static interface	OverdeterminationValidator.Node<S> This Interface represents a node in the bipartite graph
private class	OverdeterminationValidator.StartNode<T extends SBase> This class represents the start node in the bipartite graph
private class	OverdeterminationValidator.TerminalNode<T extends SBase> This class represents the end node in the bipartite graph

Field Summary

Fields

Modifier and Type	Field and Description
private OverdeterminationValidator.StartNode<SBase>	bipartiteGraph The source node of the bipartite graph, respectively the bipartite graph
private java.util.HashMap<SBase,OverdeterminationValidator.Node<SBase>>	equationHash HashMap with id -> node for equations
private java.util.List<OverdeterminationValidator.Node<SBase>>	equations List with nodes representing an equation in the model
private java.util.Map<SBase,SBase>	matching HashMap representing the current matching with value of the left node -> value of the right node
private Model	model The given SBML model
private java.util.List<java.util.List<OverdeterminationValidator.Node<SBase>>>	paths A list of all paths of a certain length in the graph
private java.util.Set<java.lang.String>	reactants A set with the ids of all reactants in the model
private java.util.List<SBase>	svariables A list where the ids of all global species in an MathML expression are saved temporarily
private java.util.HashMap<SBase,OverdeterminationValidator.Node<SBase>>	variableHash HashMap with id -> node for variables
private java.util.List<OverdeterminationValidator.Node<SBase>>	variables List with nodes representing an variable in the model

Constructor Summary

Constructors

Constructor and Description
OverdeterminationValidator(Model model) Creates a new OverdeterminationValidator for the given model

Method Summary

Modifier and Type	Method and Description
private void	augmentMatching() Improves the matching as far as possible with augmenting paths
private void	augmentPath(int length) Tries augment every path found in the graph to a new path of the given length + 2 (a new node at the beginning and the end of the path)
private void	buildGraph() Build the bipartite graph by reference to SBML specification level 3 version 1 Core
private void	buildMatching() Build the maximum matching with the greedy algorithm from the Hopcroft and Karp paper.
private void	findShortestPath(int i, OverdeterminationValidator.Node<SBase> node, java.util.List<OverdeterminationValidator.Node<SBase>> path) Finds all paths of the length i whose nodes are part of the matching.
java.util.Map<SBase,SBase>	getMatching() Returns the determined matching
private void	getVariables(ListOf<LocalParameter> param, ASTNode node, java.util.List<SBase> variables, int level) Returns the variables in a MathML object without local parameter
private void	init() Initializes the Converter
boolean	isOverdetermined() Returns a boolean that indicates whether the given model is over determined or not.
private void	updateMatching(java.util.List<OverdeterminationValidator.Node<SBase>> path) Updates the matching of the model on the basis of the found augmented path.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

equations

private java.util.List<OverdeterminationValidator.Node<SBase>> equations

List with nodes representing an equation in the model

variables

private java.util.List<OverdeterminationValidator.Node<SBase>> variables

List with nodes representing an variable in the model

variableHash

private java.util.HashMap<SBase,OverdeterminationValidator.Node<SBase>> variableHash

HashMap with id -> node for variables

equationHash

private java.util.HashMap<SBase,OverdeterminationValidator.Node<SBase>> equationHash

HashMap with id -> node for equations

matching

private java.util.Map<SBase,SBase> matching

HashMap representing the current matching with value of the left node -> value of the right node

bipartiteGraph

private OverdeterminationValidator.StartNode<SBase> bipartiteGraph

The source node of the bipartite graph, respectively the bipartite graph

svariables

private java.util.List<SBase> svariables

A list where the ids of all global species in an MathML expression are saved temporarily

paths

private java.util.List<java.util.List<OverdeterminationValidator.Node<SBase>>> paths

A list of all paths of a certain length in the graph

reactants

private java.util.Set<java.lang.String> reactants

A set with the ids of all reactants in the model

model

private Model model

The given SBML model

Constructor Detail

OverdeterminationValidator

public OverdeterminationValidator(Model model)

Creates a new OverdeterminationValidator for the given model

Parameters:

model -

Method Detail

augmentMatching

private void augmentMatching()

Improves the matching as far as possible with augmenting paths

augmentPath

private void augmentPath(int length)

Tries augment every path found in the graph to a new path of the given length + 2 (a new node at the beginning and the end of the path)

Parameters:

length -

buildGraph

private void buildGraph()

Build the bipartite graph by reference to SBML specification level 3 version 1 Core

buildMatching

private void buildMatching()

Build the maximum matching with the greedy algorithm from the Hopcroft and Karp paper. Matching is not necessarily maximal.

findShortestPath

private void findShortestPath(int i,
                              OverdeterminationValidator.Node<SBase> node,
                              java.util.List<OverdeterminationValidator.Node<SBase>> path)

Finds all paths of the length i whose nodes are part of the matching.

Parameters:

i - length

node - next node

path - nodes already visited in the path

getMatching

public java.util.Map<SBase,SBase> getMatching()

Returns the determined matching

Returns:

getVariables

private void getVariables(ListOf<LocalParameter> param,
                          ASTNode node,
                          java.util.List<SBase> variables,
                          int level)

Returns the variables in a MathML object without local parameter

Parameters:

param -

node -

variables -

level -

init

private void init()

Initializes the Converter

isOverdetermined

public boolean isOverdetermined()

Returns a boolean that indicates whether the given model is over determined or not.

Returns:

updateMatching

private void updateMatching(java.util.List<OverdeterminationValidator.Node<SBase>> path)

Updates the matching of the model on the basis of the found augmented path. Please note that because of starting the search for a path through the graph at an equation, the first node in the augmented path is always a variable and the last one an equation.

Parameters:

path -