Jak dopasować niestandardowy wykres do szablonu biblioteki wykresów boost?

Question

Jestem zardzewiały na szablonach C++ i używam biblioteki wykresu doładowania (śmiertelna kombinacja). Przeszukałem sieć i nie mogę znaleźć żadnych bezpośrednich instrukcji, jak zaimplementować niestandardową strukturę wykresu i dopasować ją do BGL (biblioteka wykresów doładowania), którą mogę wykorzystać do zwiększenia algorytmów przeszukiwania wykresów. Czy ktoś dobrze zna bibliotekę, żeby mi pomóc?

EDYCJA: Głównym problemem, jaki miałem, było znalezienie źródła, w którym łączne wymagania do odwzorowania dowolnego wykresu na wykres BGL. Jestem naprawdę nowy w szablonach, więc trudno mi przeczytać specyfikację/przykłady BGL. Może powinienem szukać ogólnego źródła na szablonach?

Answer 1

Podejście, jak rozumiem, polega na specjalizacji struktury boost::graph_traits dla danego typu wykresu. To konfiguruje BGL z różnymi ważnymi właściwościami, które musi znać o twoim wykresie. Następnie wyspecjalizujesz globalne funkcje szablonów dla swojego specjalistycznego typu wykresu: graph_traits, aby wdrożyć dowolne interfejsy wykresów przyspieszenia, które mogą mieć zastosowanie do określonego rodzaju wykresu.

Przykładem jest tam w dokumentacji BGL:

http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/leda_conversion.html

Są linki do kilku różnych interfejsów tam, które wskazują, który globalne funkcje szablonów trzeba specjalizować na wykresie, jeżeli chcesz obsługiwać ten interfejs. Pełną listę interfejsów jest tutaj:

http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/graph_concepts.html

Answer 2

Moja sugestia byłoby porzucić stosowanie BGL całkowicie chyba masz już znaczną ilość kodu napisanego na wierzchu. Ostatnio testowałem to do przyszłego wykorzystania w projekcie analizy dużych wykresów i okazało się, że jest prawie bezużyteczne z powodu zbyt skomplikowanego i źle zaprojektowanego interfejsu API.

Nie ma prostych zadań w BGL, tylko skomplikowane, i ciągle walczyłem z kompilatorem z powodu zbyt skomplikowanej hierarchii szablonów, jaką ma BGL. Nie ma żadnej przydatnej dokumentacji (przynajmniej tam, gdzie jest to naprawdę potrzebne), a niewystarczająca liczba przykładów tylko pogłębia sprawy. Nie da się napisać kodu.

Zalecam przejście na LEMON. Jest stabilny, napisany w języku C++, łatwy do zrozumienia i kodowania, oferuje kilka wyspecjalizowanych formularzy wykresów, które obsługują różne potrzeby związane z użytkowaniem, a także obsługuje funkcje wyszukiwania/odwiedzania systemu plików BFS i DFS. Ma również własny odpowiednik map właściwości dla węzłów/krawędzi, więc powinieneś być w stanie dopasować do niego swoją własną strukturę wykresu i inne dane.

Wypróbuj LEMON; smakuje o wiele lepiej i spowoduje mniej wrzodów. ;-)