Directed Grid Graphs; All Possible Paths Through Nodes

Question

I have a problem in which I am interested in taking a matrix of positive integer weights, including zero, where the matrix has dimensions nrow x ncol and the columns always sum to the same arbitrary number. I want to search for a list of paths (sets of edges essentially) that traverse through the grid space of the same dimension & create the paths such that the # of edges in a path going through a node is equal to the nodes weight (from the matrix). Ie: if a particular index in my matrix was "3", there would be 3 edges that would run into (and out of) this node.

Some important restrictions. Firstly, The only direction the edges can move is rightward (so vertical edges are disallowed) but only one column distance at a time. I do allow for the edges to go from any row_j (in column_i) to any other possible row_j in column_i+1, so diagonal edges (either upwards or downwards are allowed). Here's an example of such a solution (it is non singular which is why Im interested in ALL possible paths)

Most importantly, I am interested in two things. First I want all possible paths from this process, and even more critically, I want to minimise the number of possible diagonal edges that my resulting paths will contain.

Any sort of algorithm here to solve this would be hugely helpful.

I have managed to solve the case when I don't care about the number of diagonal edges, and just want a set of paths that match with the weights. To do that, I used the weights at adjacent columns to generate a Markov transition process. This gave me a series of transition matrices (of length ncol-1) which from there I was able to construct probabilistically what my paths through my weights were.

Let me know if anyone needs any more details/explanations here.

Update & Further Questions

I've looked into the mincost flow algo's & although they are definitely in the right wheelhouse for this problem here, they aren't 100% exactly what I need for a few reasons. First one important thing to note is that in my real world scenario, these weights are actually more of a probability mass, so they can take any value (0,1) non inclusive. But for a toy example, the integer weights work ok to derive a framework.

I think the way I had solved the problem (prior to posting this question) essentially was in a network flow like manner already without realizing it, ie: looking at fluxes coming in & out of the various nodes across my lattice. However, the main problem with this manner of solving the problem is how this solution affects my inference of downstream results. Essentially behind this 'weight' matrix (in the example, it is a 3x3 grid) is a grid that encodes with a binary alphabet {0,1} a letter for each weight. Ie one possible reference grid (as I call it) could be

1 0 0
0 1 1
0 0 0

By using this reference grid & weighted panel together, we end up with a series of weighted references which has two important properties we can calculate (given some weights & some ref panel): the column means from this weighted reference panel, and the expected covariance (how often do 1's stay 1's essentially) of the weighted reference encodings.

Ie. in the example outlined above, we have on column A a weight of (4 * 1 + 0 * 1 +0 * 1)/(4+1+1) = 0.67.

The covariance terms are slightly more difficult to derive but essentially we look at what proportion of the total flow (that we have already derived) comes from elements encoded '1' in column i and stays encoded '1' column in i+1. Here that contribution would only come from {row_1,column_1}->{row_2,column_2}.

To get the longer distance covariance what I do is perform matrix multiplication on the flow matrices. You can think of the flow matrices as a series (of length ncol--1) of matrices (each with dimensions nrow x nrow) which look from each successive column (i->i+1), how much % flow is going from one row to itself, or to other rows.

When I perform this inference, I am able to properly calculate the correct expected value for the covariance based on the flow given an underlying reference matrix & weight matrix. However, I don't really want the expected value, but actually an expected value conditional on us having not used as high a proportion of diagonal edges as we would have in the naive case. The reason for this is when we perform this operation on larger matrices, the covariance terms (the proportion of times 1's flow to other 1's along the columns) is weakened over long distances (this is because this is a memoryless markov process if that helps) since with this diagonal flow we don't get the same set of encodings as the reference panel. (eg: in our example we would looking at the reference have only ({1,0,0},{0,1,1},{0,0,0}) as the possible paths, but with diagonal flow we could have some element such as {0,1,0}.

So in essence I guess what I'm wondering is if there is some sort of expected covariance I can derive, based on the graph traversal (or the framework I have developed here) that would allow me to get the expected covariance based on different # of diagonal switches possible, or more broadly to look at ways how to minimise this long-distance loss phenomena I am facing here.

One idea I had was to sort my reference panel based on the positional burrow wheels transform (http://alimanfoo.github.io/2016/06/21/understanding-pbwt.html) which would allow me to look at series of blocks in my reference panel that were more similar to one another. Unsure exactly how I would use that however?

Answer 1

It seems to me that what you need is an integer mincost flow algorithm. Each matrix entry gets a vertex in the network, with each vertex having arcs to all of the vertices in the next column. The solution flow values indicate how many edges to place between each pair of entries. The flow constraint enforces equal numbers of edges in and out of each entry. You would set capacity constraints on the vertices to enforce the limit on how many edges enter and exit each entry.[*] You would assign zero cost for horizontal edges and nonzero cost to diagonal edges (either a fixed cost for all diagonal edges or a cost based on the diagonal length, depending on what you are optimizing for).

Off-the-shelf open source solvers and libraries for mincost flow are widely available, so you can just construct the flow network and then hand it off to a solver to get a solution. If you want to get entire left-to-right paths out of this, you would have to construct them from the flow solution. But that is easy enough by graph search.

[*] Mincost flow is usually presented with capacity constraints on the arcs rather than on the vertices. This is easily worked around by splitting each vertex in two, with a capacity-limited arc in-between. That is, if a vertex $v$ has a capcity limit $c$, replace $v$ with two vertices $v_1$ and $v_2$ such that all the arcs that entered $v$ instead enter $v_1$, all the arcs that left $v$ instead leave $v_2$, and there is an arc with capacity limit $c$ from $v_1$ to $v_2$.