Ujemne sprawdzanie masy krawędzi w dijkstra_shortest_paths boostu

Używam biblioteki wykresów doładowania, aby wykonać połączenie z dijkstra_shortest_paths. Mam jednak coś specjalnego w tym, że weight_map jest w rzeczywistości funktorem. Dlatego za każdym razem, gdy biblioteka doładowań wymaga wagi krawędzi, mój funktor jest nazywany, wykonuje skomplikowane obliczenia i dostarcza wynik do zwiększenia.Ujemne sprawdzanie masy krawędzi w dijkstra_shortest_paths boostu

Niestety w dijkstra_shortest_paths.hpp metoda struct dijkstra_bfs_visitor „s examine_edge ma get wezwanie do weightmap, tylko w celu sprawdzenia, czy zwrócona wartość jest ujemna. Jestem w pełni świadomy, że nie mogę użyć algorytmu Dijkstry z wartościami ujemnymi i jestem pewien, że mój funktor zwraca tylko wartości dodatnie. Jednak to sprawdzenie powoduje, że mój funktor jest wywoływany dwa razy dla każdej krawędzi. Ponieważ wykonuje skomplikowane obliczenia, chciałbym uniknąć wykonywania go dwa razy (wyniki nie zmieniają się między połączeniami. Każda krawędź dostaje takie samo oczekiwanie podczas uruchomienia dijkstra_shortest_paths).

Do tej pory ręcznie sprawdzam krawędź przekazywaną funktorowi, a w przypadku duplikatu zwracam poprzedni zapamiętany wynik. To oczywiście jest bardziej rozwiązaniem niż rozwiązaniem.

Próbowałem przekazać mojego gościa, który nadpisał examine_edge, jednak nadal stosowana jest oryginalna metoda zdefiniowana przez kryterium doładowania dijkstra_bfs_visitor.

Czy ktoś wie, czy jest lepszy sposób radzenia sobie z tą sytuacją i jakoś uniknąć kontroli wagi krawędzi ujemnej?

Źródło

2011-07-15 Frank

Jeśli jest to kosztowne, buforowanie tego obliczania wagi krawędzi wydaje się dobrym pomysłem. poza tym ... może możesz dostarczyć funktora kombajnu, który zawsze zwraca wartość false? – fearlesstost

Oczywiście już to zrobiłem. Po prostu nie podoba mi się, że funktor jest wywoływany dwa razy bez powodu. Funktor kombajnu powinien zwrócić wartość odległości, więc co masz na myśli mówiąc o zwracaniu fałszu? – Frank

Czy możesz wywodzić się z 'struct DijkstraVisitorConcept' i przeciążać własną funkcję' void constraints() ', w której możesz całkowicie usunąć sprawdzanie' examine_edge() '. –

Masz rację, nawet dostarczając ci gościa, przeprowadzony zostanie test negatywności.

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

Ale w każdym razie weight_map ma być nazywane wielokrotność czasu (patrz impuls doc):

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

Wystarczy zadzwonić djikstra z precomputed wagi mapie, każda waga krawędź będą musiały być obliczane tak.

Źródło

2011-08-02 12:42:13 log0

Niestety, nie jest to prawdą w moim przypadku. Po pierwsze: dokument nie mówi, że dwa razy wywołuje w (u, v). To tylko pseudo-kod, a boost może również ponownie wykorzystać wynik. Po drugie, nie mogę wykonać wstępnej kalkulacji, ponieważ mój użytkownik rzuca wyjątek na osiągnięcie wierzchołka docelowego, więc nie wiedziałbym, co do wstępnego obliczenia (i oczywiście, nie chcę tego obliczyć). – Frank

Sposób, w jaki jest to udokumentowane, sugeruje, że nie powinieneś polegać na tym, że jest on wywoływany tylko raz. Wtedy możliwe jest dokonanie memoizacji. Lub dziedzicz po 'DijkstraVisitorConcept' zgodnie z sugestią Aditya Kumar. – log0

Proponuję użyć leniwego obliczenia, aby zapewnić, że każde kosztowne obliczenie zostanie wykonane co najwyżej raz. Najprostszym sposobem na wdrożenie tego byłoby uzyskanie leniwego gettera z klasy Edge, nie jestem zaznajomiony z biblioteką, z której korzystasz, więc nie jestem pewien, jak ją zintegrować z funktorem.

Źródło

2011-08-10 06:15:02

Ujemne sprawdzanie masy krawędzi w dijkstra_shortest_paths boostu

Odpowiedz

Powiązane problemy