Bounty Ended with 50 reputation awarded by Karolis
    Post Undeleted by lalmei
2 fixed bugs and added explanation that this may not be a findminimumcost in the end.
source | link

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"];

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

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

This should work on Mathematica 9Another way would be to just match two frames at a time. At moment doesnt work if In simple tracking codes you can keep the there are disjoint graphs as partasigment to two frames at a time. You can keep track of the edge list, but it should be easily generalized. I developed a similar mtt tracker in Mathematica last yearvelocity (or diffusion) of the particle, but never completely finishedand set the cost based on the distance and velocity of currently matched particles. So let me know how it goesThis however is going to miss blinking, or if you need some onecan then do secondary passes to double check anything. The assigment part had a simplified Hungarian Algorithm assigment, but this function should be much faster, which wasn't available in Mathematica 8find any missing links due to blinking.  

The idea is to just to find one path at a time and remove those vertices from the graph and find the next one.

  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};

  g = Graph[edges, EdgeCost -> costs, VertexLabels -> "Name"];

  paths = Last@Reap[While[Length[edges] > 0,
          d = FindMinimumCostFlow[g, 0, 4, 1, "EdgeList"];
          removeverterz = 
          VertexList[Graph[Cases[d, x_ -> y_ /; x != 0 && y != 4]]];
          g = VertexDelete[g, removevertez];
          Sow[d];
          edges = EdgeList[g];
   ]]

This should work on Mathematica 9. At moment doesnt work if the there are disjoint graphs as part of the edge list, but it should be easily generalized. I developed a similar mtt tracker in Mathematica last year, but never completely finished. So let me know how it goes, or if you need some one to double check anything. The assigment part had a simplified Hungarian Algorithm assigment, but this function should be much faster, which wasn't available in Mathematica 8.  

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.

    Post Deleted by lalmei
1
source | link

The idea is to just to find one path at a time and remove those vertices from the graph and find the next one.

  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};

  g = Graph[edges, EdgeCost -> costs, VertexLabels -> "Name"];

  paths = Last@Reap[While[Length[edges] > 0,
          d = FindMinimumCostFlow[g, 0, 4, 1, "EdgeList"];
          removeverterz = 
          VertexList[Graph[Cases[d, x_ -> y_ /; x != 0 && y != 4]]];
          g = VertexDelete[g, removevertez];
          Sow[d];
          edges = EdgeList[g];
   ]]

This should work on Mathematica 9. At moment doesnt work if the there are disjoint graphs as part of the edge list, but it should be easily generalized. I developed a similar mtt tracker in Mathematica last year, but never completely finished. So let me know how it goes, or if you need some one to double check anything. The assigment part had a simplified Hungarian Algorithm assigment, but this function should be much faster, which wasn't available in Mathematica 8.