Morse Graphs

Mathematical Background

A pivotal result in dynamical systems theory due to Conley states (in essence) that a dynamical system can be deconstructed into "recurrent" and "gradient-like" parts. The recurrent dynamics are captured within the chain recurrent sets, and are often analyzed using the Conley Index.

Much the same way that morse theory can describe a smooth closed manifold by means of a gradient field, Conley-Morse theory proves the existence of a gradient field which captures the dynamics of the nonrecurrent components of a dynamical system (this is referred to as Conley's decomposition theorem [16], or occasionally the fundamental theorem of dynamical systems).

For practical purposes, this means a dynamical system can be described as an acyclic directed graph where the nodes are the recurrent components, and edges are drawn if there exists an orbit between recurrent components.

morse_graph(F::BoxMap, B::BoxSet) -> MetaGraph
morse_graph(F♯::TransferOperator) -> MetaGraph

Example

julia> using GAIO, MetaGraphsNext
julia> const θ₁, θ₂ = 20., 20.(20.0, 20.0)
julia> f((x, y)) = ( (θ₁*x + θ₂*y) * exp(-0.1*(x + y)), 0.7*x )f (generic function with 1 method)
julia> center, radius = (38, 26), (38, 26)((38, 26), (38, 26))
julia> Q = Box(center, radius)Box{2, Float64}:
   center: [38.0, 26.0]
   radius: [38.0, 26.0]
julia> P = BoxPartition(Q, (256,256))256 x 256 - element BoxPartition
julia> S = cover(P, :)65536 - element BoxSet in 256 x 256 - element BoxPartition
julia> F = BoxMap(:interval, f, Q)IntervalBoxMap with (4, 4) subintervals
julia> F♯ = TransferOperator(F, S, S)65536 x 65536 TransferOperator over 256 x 256 - element BoxPartition with 280828 stored entries:

⎡⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎤
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎥
⎣⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⎦
julia> G = morse_graph(F♯)Meta graph based on a SimpleDiGraph{Int64} with vertex labels of type Int64, vertex metadata of type BoxSet{Box{2, Float64}, BoxPartition{2, Float64, Int64}, Set{Tuple{Int64, Int64}}}, edge metadata of type Nothing, graph metadata given by 256 x 256 - element BoxPartition, and default weight 1.0
julia> labels(G)Base.Generator{Base.OneTo{Int64}, MetaGraphsNext.var"#20#21"{MetaGraph{Int64, SimpleDiGraph{Int64}, Int64, BoxSet{Box{2, Float64}, BoxPartition{2, Float64, Int64}, Set{Tuple{Int64, Int64}}}, Nothing, BoxPartition{2, Float64, Int64}, MetaGraphsNext.var"#15#17", Float64}}}(MetaGraphsNext.var"#20#21"{MetaGraph{Int64, SimpleDiGraph{Int64}, Int64, BoxSet{Box{2, Float64}, BoxPartition{2, Float64, Int64}, Set{Tuple{Int64, Int64}}}, Nothing, BoxPartition{2, Float64, Int64}, MetaGraphsNext.var"#15#17", Float64}}(Meta graph based on a SimpleDiGraph{Int64} with vertex labels of type Int64, vertex metadata of type BoxSet{Box{2, Float64}, BoxPartition{2, Float64, Int64}, Set{Tuple{Int64, Int64}}}, edge metadata of type Nothing, graph metadata given by 256 x 256 - element BoxPartition, and default weight 1.0), Base.OneTo(4))
julia> tiles = [G[label] for label in labels(G)]4-element Vector{BoxSet{Box{2, Float64}, BoxPartition{2, Float64, Int64}, Set{Tuple{Int64, Int64}}}}:
 1 - element BoxSet in 256 x 256 - element BoxPartition
 117 - element BoxSet in 256 x 256 - element BoxPartition
 8662 - element BoxSet in 256 x 256 - element BoxPartition
 314 - element BoxSet in 256 x 256 - element BoxPartition
julia> using GraphsWARNING: using Graphs.radius in module Main conflicts with an existing identifier.
WARNING: using Graphs.center in module Main conflicts with an existing identifier.
julia> n = nv(G) # number of vertices4

Plotting Morse Graphs with Plots.jl or Makie.jl

To plot a graph using Plots.jl, there is the package GraphRecipes.jl:

using Plots
using GraphRecipes

colors = cgrad(palette(:auto, n), categorical=true)

p1 = graphplot(
    G.graph,
    names=1:n,
    markercolor=collect(colors),
    markersize=0.2
)

p2 = plot(BoxMeasure(G), colormap=colors, colorbar=false)

p = plot(p1, p2)

WARNING: using Plots.center in module Main conflicts with an existing identifier.

The same result can be created using Makie.jl and GraphMakie.jl:

using GLMakie
using GraphMakie

colors = Makie.wong_colors()    # default colors
colors = colors[ [1:n;] .% length(colors) .+ 1 ]

fig, ax, ms = graphplot(
    G.graph,
    ilabels=1:n,
    node_color=colors
)
    
ax = Axis(fig[1,2])
for (i, label) in enumerate(labels(G))
    morse_set = G[label]
    plot!(ax, morse_set, color=colors[i])
end