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)

Base.isequal(bg1::BipartiteGraph{T}, bg2::BipartiteGraph{T}) where {T<:Integer} 

Test whether two BipartiteGraphs are equal.

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

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

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)

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)

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)

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

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