Boost logo

Boost Users :

Subject: Re: [Boost-users] time out for r_c_shortest_paths
From: Brammert Ottens (Brammert.Ottens_at_[hidden])
Date: 2013-02-25 09:05:27


> Hi,
>
> I want to be able to put a time out on the r_c_shortest_paths, and still
> be able to get the optimal paths that have been found so far. Currently,
> I changed the REF such that it always returns false as soon as the time
> out has reach, in effect emptying the unprocessed_labels queue. The
> problem with this is that the algorithm still needs quite some time to
> actually empty the queue.
>
> I tried to have the on_label_popped(cur_label) throw an exception when
> the timeout has been reached. The timeout itself works like a charm, but
> because the pareto_optimal_solutions container is only filled after the
> while loop I can't access the already found optimal solutions.

You might want to have on_label_popped(l, g) take l by reference and set
l.b_is_dominated to true. You'll still need to empty the queue, but (if
that approach works) it should be faster that way.

-- Jeremiah Willcock

Hi Jeremiah,

Thanks for your suggestion, but if I understand correctly it would mean a change to the code. I do not want to change the code, because if ever there is an update to boost I just want to be able to replace the old libraries with the new ones. If I would change the code, I would keep the exception and put a try/catch statement around the while-loop. Then you go around the problem of having to empty the queue.

Is there any change to get something like a graceful timeout supported in the boost graph algorithms?

Brammert Ottens

Hi,

I've had a closer look and I was too quick in dismissing your solution. however, the on_label_popped(cur_label) gets a const reference to the label. I've used a const_cast to remove the const (see code below), but now the code crashes when cleaning up the labels using deallocate. Any ideas on what could be wrong?

template<class Label, class Graph>
void QRCSPPVisitor::on_label_popped( const Label& label, const Graph& graph )
{
  RCSPPVisitorData().IncrementLabelsPopped();

  if ( TimedOut() || GetMillis(StartTime()) > MaxMillis() )
  {
    this->SetTimedOut();
    const_cast<Label&>(label).b_is_dominated = true;
  }
}

regards,

Brammert Ottens


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net