[Lemon-user] adding new arcs to a graph

[Leandro Callegari Coelho]

Hello list,

Suppose I have an initial graph, which I can compute whatever I want, e.g.,
min cost flow using the network simplex algorithm:


         NetworkSimplex<ListDigraph, int, int> graph(g);
       int status = graph
      .lowerMap(lowerMap)
      .upperMap(upperMap)
      .costMap(costMap)
      .supplyMap(supplyMap)
      .run();

Then suppose that after creating the basic structures I want to add a
couple of arcs to this graph. I don't know them beforehand, and then I want
to reoptimize it. Currently I do:

  //add more arcs here
  //define the lowerMap, upperMap, costMap for the new arcs here
  graph.reset();

   and then again


       int status = graph
      .lowerMap(lowerMap)
      .upperMap(upperMap)
      .costMap(costMap)
      .supplyMap(supplyMap)
      .run();

I tend to believe this is rather slow, because apparently I am redefining
the whole structure again. However, I know that only a few arcs (whose
labels I know) have been added. Is there a more efficient way of
reoptimizing it?

Thanks in advance
Leandro


-- 

LCC

"Absence of evidence is not evidence of absence"
Carl Sagan (1934 - 96)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20121016/acece24b/attachment.html>