Limit FindMinimumCostFlow function to one vertex per path

Question

I want find a set of paths through a graph that maximise flow and minimise cost set on each Edge. However, I have an additional constraint where each Vertex can only be visited once.

Mathematica has the function FindMinimumCostFlow for finding this, but I cannot figure out how to limit the solution to unique vertices only. Please help.

Example code:

costs = Range[24];
g = Graph[
   {0 -> 11, 0 -> 12, 0 -> 13,
    11 -> 21, 11 -> 22, 11 -> 23, 12 -> 21, 12 -> 22, 12 -> 23, 
    13 -> 21, 13 -> 22, 13 -> 23, 21 -> 31, 21 -> 32, 21 -> 33, 
    22 -> 31, 22 -> 32, 22 -> 33, 23 -> 31, 23 -> 32, 23 -> 33,
    31 -> 4, 32 -> 4, 33 -> 4}, EdgeCost -> costs, VertexLabels -> "Name"];
FindMinimumCostFlow[g, 0, 4, "EdgeList"];
HighlightGraph[g, Graph[%], GraphHighlightStyle -> "Thick"]

but ideally i would like to get

Motivation: This is for reconstructing particle trajectories from video data. Each Vertex corresponds to a particle detection at a given frame and position.

Answer 1

The idea is to just to find one path at a time and remove those vertices from the graph and find the next one, by restring the flow. Not sure if this is still a minimum cost flow in the end.

Also using source and targets for assignment, usually you need to set the cost of from the sources and targets to 0. It seems the FindMiniumCost only solves the assigment problem for two layers graphs (plus source and target).I will play more with it today.

  costs = Range[24];
  edges = {0 -> 11, 0 -> 12, 0 -> 13, 11 -> 21, 11 -> 22, 11 -> 23, 
       12 -> 21, 12 -> 22, 12 -> 23, 13 -> 21, 13 -> 22, 13 -> 23, 
       21 -> 31, 21 -> 32, 21 -> 33, 22 -> 31, 22 -> 32, 22 -> 33, 
       23 -> 31, 23 -> 32, 23 -> 33, 31 -> 4, 32 -> 4, 33 -> 4};



      paths = Last@Reap[While[Length[edges] > 0,
          g = Graph[edges, EdgeCost -> costs, VertexLabels -> "Name"];
          d = FindMinimumCostFlow[g, 0, 4, 1, "EdgeList"];
          Sow[d];
          removeverterz = VertexList[
              Graph[Cases[d, x_ \[DirectedEdge] y_ /; (x != 0 && y != 4)]]];
          edgecosts = DeleteCases[Thread[{edges, costs}], {x_ -> y_, c_} /;       
                     (MemberQ[removeverterz, x] || MemberQ[removeverterz, y])];

          {edges, costs} = If[edgecosts == {}, {{}, {}},
           Thread[edgecosts]];
        ]];

Another way would be to just match two frames at a time. In simple tracking codes you can keep the asigment to two frames at a time. You can keep track of the velocity (or diffusion) of the particle, and set the cost based on the distance and velocity of currently matched particles. This however is going to miss blinking, you can then do secondary passes to find any missing links due to blinking.

Answer 2

Is it acceptable for your problem to change the costs associated to traversing the edges?

If it is, then you can set the costs to:

costs = {
  1, 1, 1,
  1, 10, 10,
  10, 1, 10,
  10, 10, 1,
  1, 10, 10,
  10, 1, 10,
  10, 10, 1,
  1, 1, 1
};

(* The following is your original code: *)
g = Graph[{0 -> 11, 0 -> 12, 0 -> 13, 11 -> 21, 11 -> 22, 11 -> 23, 
    12 -> 21, 12 -> 22, 12 -> 23, 13 -> 21, 13 -> 22, 13 -> 23, 
    21 -> 31, 21 -> 32, 21 -> 33, 22 -> 31, 22 -> 32, 22 -> 33, 
    23 -> 31, 23 -> 32, 23 -> 33, 31 -> 4, 32 -> 4, 33 -> 4}, 
   EdgeCost -> costs, VertexLabels -> "Name"];

FindMinimumCostFlow[g, 0, 4, "EdgeList"];
HighlightGraph[g, Graph[%], GraphHighlightStyle -> "Thick"]

This seems to reproduce your desired flow:

Note: for some reason my MMA defaults to really tiny arrow heads to indicate the directed graph edges. The non-highlighted arrows are there if you look reeeeally closely...