Проверка веса отрицательного края в dijkstra_shortest_paths boost

Я использую библиотеку графов повышения, чтобы позвонить dijkstra_shortest_paths. Однако у меня есть кое-что особенное в том, что weight_map на самом деле является функтором. Следовательно, каждый раз, когда библиотеке boost требуется вес ребра, вызывается мой функтор, он выполняет сложное вычисление и отправляет результат обратно в boost.

К сожалению, в dijkstra_shortest_paths.hpp метод examine_edge структуры dijkstra_bfs_visitor имеет get вызов карты весов только для проверки, является ли возвращаемое значение отрицательным. Я полностью осознаю, что не могу использовать алгоритм Дейкстры с отрицательными значениями, и я уверен, что мой функтор возвращает только положительные значения. Однако эта проверка приводит к тому, что мой функтор вызывается дважды для каждого ребра. Поскольку он выполняет сложные вычисления, я бы хотел избежать его повторного выполнения (результаты не меняются между вызовами... каждое ребро получает одно и то же ожидание во время dijkstra_shortest_paths запуска).

Пока что я вручную проверяю ребро, переданное функтору, и в случае повторного вызова возвращаю предыдущий запомненный результат. Это явно скорее обходной путь, чем решение.

Я попытался передать свой собственный посетитель, который перезаписывает examine_edge, однако исходный метод, определенный dijkstra_bfs_visitor повышения, все еще применяется.

Кто-нибудь знает, есть ли лучший способ справиться с этой ситуацией и как-то избежать проверки веса отрицательного края?


c++ boost dijkstra
person Frank    schedule 15.07.2011    source источник
comment
если это дорого, кэширование этого расчета веса ребра в любом случае кажется хорошей идеей. кроме этого ... может быть, вы можете предоставить комбинированный функтор, который всегда возвращает false?   -  person fearlesstost    schedule 15.07.2011
comment
Я его уже кеширую, конечно. Мне просто не нравится, когда функтор вызывается дважды без всякой причины. Комбинированный функтор должен возвращать значение расстояния, так что вы имеете в виду, возвращая false?   -  person Frank    schedule 18.07.2011
comment
Можете ли вы извлечь из struct DijkstraVisitorConcept и перегрузить свою собственную функцию void constraints(), где вы можете вообще удалить проверку examine_edge().   -  person A. K.    schedule 21.07.2011
comment
@Aditya Kumar: Звучит как ответ для меня - вы должны опубликовать это в разделе ответов   -  person Soren    schedule 22.07.2011

Ответы (2)


arrow_upward
0
arrow_downward

Вы правы, даже предложив своему посетителю тест на негатив будет проведен.

  void examine_edge(Edge e, Graph& g) {
    if (m_compare(get(m_weight, e), m_zero))
        boost::throw_exception(negative_edge());
    m_vis.examine_edge(e, g);
  }

Но в любом случае, weight_map предполагается вызывать несколько раз (см. boost документ):

 for each vertex v in Adj[u]
  if (w(u,v) + d[u] < d[v])
    d[v] := w(u,v) + d[u]

Просто вызовите djikstra с предварительно вычисленной картой весов, все равно придется вычислять вес каждого ребра.

person log0    schedule 02.08.2011
comment
К сожалению, в моем случае это не так. Во-первых: документ не говорит, что он вызывает w(u,v) дважды. Это всего лишь псевдокод, и boost также может повторно использовать результат. Во-вторых, я не могу предварительно вычислить, потому что мой посетитель выдает исключение при достижении целевой вершины, поэтому я не знаю, что нужно предварительно вычислить (и, очевидно, не хочу вычислять все сразу). - person Frank; 02.08.2011
comment
Ну, то, как это задокументировано, предполагает, что вы не должны полагаться на тот факт, что он вызывается только один раз. Тогда мемоизация является возможным выбором. Или наследуйте от DijkstraVisitorConcept, как предлагает Адитья Кумар. - person log0; 02.08.2011

arrow_upward
0
arrow_downward

Я предлагаю вам использовать ленивые вычисления, чтобы гарантировать, что каждое дорогостоящее вычисление выполняется не более одного раза. Самый простой способ реализовать это - дать вашему Edge классу getWeight() ленивый геттер, я не знаком с библиотекой, которую вы используете, поэтому я не уверен, как вы интегрируете ее с функтором.

person Rasmus Storjohann    schedule 10.08.2011