Dependency Graphs

Types

ModelingToolkit.BipartiteGraphType
mutable struct BipartiteGraph{T<:Integer}

A bipartite graph representation between two, possibly distinct, sets of vertices (source and dependencies). Maps source vertices, labelled 1:N₁, to vertices on which they depend (labelled 1:N₂).

Fields

  • ne

    Number of edges from source vertices to vertices they depend on.

  • fadjlist

    Forward adjacency list mapping index of source vertices to the vertices they depend on.

  • badjlist

    Backward adjacency list mapping index of vertices that are dependencies to the source vertices that depend on them.

Example

using ModelingToolkit

ne = 4
srcverts = 1:4
depverts = 1:2

# six source vertices
fadjlist = [[1],[1],[2],[2],[1],[1,2]]

# two vertices they depend on 
badjlist = [[1,2,5,6],[3,4,6]]

bg = BipartiteGraph(7, fadjlist, badjlist)
source

Utility functions for BiPartiteGraphs

Functions for calculating dependency graphs

ModelingToolkit.equation_dependenciesFunction
equation_dependencies(sys::AbstractSystem; variables=states(sys))

Given an AbstractSystem calculate for each equation the variables it depends on.

Notes:

  • Variables that are not in variables are filtered out.
  • get_variables! is used to determine the variables within a given equation.
  • returns a Vector{Vector{Variable}}() mapping the index of an equation to the variables it depends on.

Example:

using ModelingToolkit
@parameters β γ κ η t
@variables S(t) I(t) R(t)

# use a reaction system to easily generate ODE and jump systems
rxs = [Reaction(β, [S,I], [I], [1,1], [2]),
       Reaction(γ, [I], [R]),
       Reaction(κ+η, [R], [S])]
rs = ReactionSystem(rxs, t, [S,I,R], [β,γ,κ,η])

# ODEs:
odesys = convert(ODESystem, rs)

# dependency of each ODE on state variables
equation_dependencies(odesys)    

# dependency of each ODE on parameters
equation_dependencies(odesys, variables=parameters(odesys))

# Jumps
jumpsys = convert(JumpSystem, rs)

# dependency of each jump rate function on state variables
equation_dependencies(jumpsys)    

# dependency of each jump rate function on parameters
equation_dependencies(jumpsys, variables=parameters(jumpsys))    
source
ModelingToolkit.asgraphFunction
asgraph(eqdeps, vtois)    

Convert a collection of equation dependencies, for example as returned by equation_dependencies, to a BipartiteGraph.

Notes:

  • vtois should provide a Dict like mapping from each Variable dependency in eqdeps to the integer idx of the variable to use in the graph.

Example: Continuing the example started in equation_dependencies

digr = asgraph(equation_dependencies(odesys), Dict(s => i for (i,s) in enumerate(states(odesys))))
source
asgraph(sys::AbstractSystem; variables=states(sys), 
                                      variablestoids=Dict(convert(Variable, v) => i for (i,v) in enumerate(variables)))

Convert an AbstractSystem to a BipartiteGraph mapping the index of equations to the indices of variables they depend on.

Notes:

  • Defaults for kwargs creating a mapping from equations(sys) to states(sys) they depend on.
  • variables should provide the list of variables to use for generating the dependency graph.
  • variablestoids should provide Dict like mapping from a Variable to its Int index within variables.

Example: Continuing the example started in equation_dependencies

digr = asgraph(odesys)
source
ModelingToolkit.variable_dependenciesFunction
variable_dependencies(sys::AbstractSystem; variables=states(sys), variablestoids=nothing)

For each variable determine the equations that modify it and return as a BipartiteGraph.

Notes:

  • Dependencies are returned as a BipartiteGraph mapping variable indices to the indices of equations that modify them.
  • variables denotes the list of variables to determine dependencies for.
  • variablestoids denotes a Dict mapping Variables to their Int index in variables.

Example: Continuing the example of equation_dependencies

variable_dependencies(odesys)
source
ModelingToolkit.asdigraphFunction
asdigraph(g::BipartiteGraph, sys::AbstractSystem; variables = states(sys), equationsfirst = true)

Convert a BipartiteGraph to a LightGraph.SimpleDiGraph.

Notes:

  • The resulting SimpleDiGraph unifies the two sets of vertices (equations and then states in the case it comes from asgraph), producing one ordered set of integer vertices (SimpleDiGraph does not support two distinct collections of vertices so they must be merged).
  • variables gives the variables that g is associated with (usually the states of a system).
  • equationsfirst (default is true) gives whether the BipartiteGraph gives a mapping from equations to variables they depend on (true), as calculated by asgraph, or whether it gives a mapping from variables to the equations that modify them, as calculated by variable_dependencies.

Example: Continuing the example in asgraph

dg = asdigraph(digr)
source
ModelingToolkit.eqeq_dependenciesFunction
eqeq_dependencies(eqdeps::BipartiteGraph{T}, vardeps::BipartiteGraph{T}) where {T <: Integer}

Calculate a LightGraph.SimpleDiGraph that maps each equation to equations they depend on.

Notes:

  • The fadjlist of the SimpleDiGraph maps from an equation to the equations that modify variables it depends on.
  • The badjlist of the SimpleDiGraph maps from an equation to equations that depend on variables it modifies.

Example: Continuing the example of equation_dependencies

eqeqdep = eqeq_dependencies(asgraph(odesys), variable_dependencies(odesys))
source
ModelingToolkit.varvar_dependenciesFunction
varvar_dependencies(eqdeps::BipartiteGraph{T}, vardeps::BipartiteGraph{T}) where {T <: Integer} = eqeq_dependencies(vardeps, eqdeps)

Calculate a LightGraph.SimpleDiGraph that maps each variable to variables they depend on.

Notes:

  • The fadjlist of the SimpleDiGraph maps from a variable to the variables that depend on it.
  • The badjlist of the SimpleDiGraph maps from a variable to variables on which it depends.

Example: Continuing the example of equation_dependencies

varvardep = varvar_dependencies(asgraph(odesys), variable_dependencies(odesys))
source