4
$\begingroup$

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

enter image description here

but ideally i would like to get

enter image description here

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

$\endgroup$
2
+50
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Good idea, but it reminds me of greedy search, which does not find the optimum solution. I have to think about an example that could demonstrate this. $\endgroup$ – Karolis May 9 '15 at 20:56
  • $\begingroup$ I awarded the bounty for this answer, because your solution is closest to the desired solution. Thank you! $\endgroup$ – Karolis May 14 '15 at 10:17
2
$\begingroup$

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:

Graph with thick arrows

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...

$\endgroup$
  • 1
    $\begingroup$ The costs are externally supplied by the problem. In my case it is the squared distance between particles, thus rewarding particles that are closer together. $\endgroup$ – Karolis May 9 '15 at 20:59
  • $\begingroup$ @Karolis I see. I have to rethink my approach then. Thank you for the clarification. $\endgroup$ – MarcoB May 11 '15 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.