Tie a transition matrix to a BoxSet?

[gaioguy]

As it stands, a BoxSet is unordered, so by assigning an ordering, we introduce additional structure. We do not necessarily need this when constructing a graph (i.e. for computing strongly connected components), but we do need it when computing a transition (probability) matrix. The problem is - and this has been a problem since the early days - that the information that one typically computes from a transition matrix (e.g. eigenvectors) is later linked back to the BoxSet (by, e.g., assiging a color to each Boxaccording to the corresponding entry in the eigenvector), so one must not change the BoxSet in the meantime or otherwise the information from the transition matrix is no longer valid for the BoxSet. So the question is whether we should somehow 'tie' a transition matrix to a BoxSet, i.e. whether we should define something like BoxTransitionMatrix which, e.g., takes a BoxSet and a BoxMap for construction.

Originally posted by @gaioguy in https://github.com/gaioguy/GAIO.jl/pull/1#issuecomment-654901328

[cafaxo]

I have to following two ideas to deal with this:

1. We delay putting an order onto a BoxSet as long as possible. Once the user requests a transition matrix, we additionally return an ordered boxset. This is the currently implemented approach in #20. There, the ordered boxset is a function that takes a set of integers and returns the corresponding boxset.

2. We give the user an explicit way to order a boxset:

   boxlist = order(boxset) # put an arbitrary order on the elements in the boxset; boxlist is immutable.
   G = transition_graph(g, boxlist)
   mat = matrix(G)
   # mat[1,1] corresponds to the weight of the edge boxlist[1] -> boxlist[1]
   # boxlist[[3,45,7]] returns a boxset

   What do you think?

A downside of the second idea is of course the thing that @gaioguy already mentioned: We do not need an order for some other things that take a BoxGraph. (e.g. strongly connected components). To deal with that, we could simply have transition_graph(g, boxset) that orders the boxset anyways. This order would then be hidden from the user.

[MaHermann]

Personally, I find 2. to be more intuitive. As you said, having an additional interface along the lines of

function transition_graph(g::BoxMap,boxset::BoxSet)
    return transition_graph(g,order(boxset))
end

(or maybe a little bit more sophisticated/optimized) would solve the issue, right?

By the way, I'm not yet super sure about this, but I think I'd prefer that boxlist[[3,45,7]] returns a boxlist again, and have boxlist really act like a list of boxes. Maybe we can have an additional constructor BoxSet(boxlist) or something like that to convert a boxlist or a sublist of it back to a boxset?

[cafaxo]

Good point. As discussed, I will work on a PR for the second approach.