[T.....y]

Jaka jest najlepsza implementacja grafu, jeżeli mam zamiar w nim zarówno dodawać jak i usuwać wierzchołki oraz krawędzie? Nie chcę również, żeby to były stałe tablice i wolałbym uniknąć tablicy sąsiedztwa na rzecz listy sąsiedztwa, bo grafy będą duże. #grafy #programowanie #algorytmy

[tell_me_more]

@TenAnonToKlopoty:

std::map< std::pair, bool > edges;

Dodawanie, usuwanie krawędzi O(1), dodawanie wierzchołków O(1), jedynie usuwanie wierzchołków O(liczba wierzchołków). Można przyśpieszyć dodając listę sąsiedztwa:

std::map< int, std::set > neighbors;

[T.....y]

@tell_me_more: a jak z usuwaniem wierzchołka? pewnie pętlą po kluczach?

[tell_me_more]

@TenAnonToKlopoty: nom, ewentualnie można dodać listę sąsiedztwa, żeby usuwanie było O(liczba sąsiadów), ale kosztem wolniejszego (ale wciąż O(1) dodawania/usuwania krawędzi i dodawania wierzchołków).

Tyko w sumie niepotrzebnie neighobors to jest mapa, może byćstd::vector< std::set >

[T.....y]

@tell_me_more: a teraz w sumie pomyślałem sobie, że jak będę mieć liste sąsiedztwa to nawet pętli nie potrzebuję
w takim razie dzięki i kodzę, jak coś nie wyjdzie to dopytam ciebie lub kogokolwiek :)

[T.....y]

@tell_me_more: napisaliśmy niemal w tym samym czasie, ale nie zrozumiałem ostatniego zdania, ten vector z setami to mają być sąsiedztwa?

[tell_me_more]

@TenAnonToKlopoty: po głębszym zastanowieniu można dać:

std::set< std::pair > edges; // albo jest krawędź od x do y, albo nie ma
std::vector< std::set > neighbors; // lista zbiorów, każdy zbiór to nr wierzchołków sąsiednie z wierzchołkiem z danego indeksu listy

Mapa to był trochę overkill, skoro tylko potrzebna jest informacja true/false w pierwszym przypadku. A w drugim mapa z int na coś, kiedy wiadomo, że wszystkie nr będą - można zastąpić

[T.....y]

@tell_me_more: czy compare tej pary w sumie ma tu jakieś znaczenie? i jeżeli chciałbym dodać, że wierzchołkami grafów są jakieś obiekty(struktury) to wystarczy, że dodam vector vertices i będę posługiwał się wszędzie indeksami?

[T.....y]

@tell_me_more: a nie, to musiałbym mieć tu chyba map vertices

[tell_me_more]

@TenAnonToKlopoty: masz unordered_set, i wtedy compare niepotrzebne, ale potrzebny hash, albo normalny set, i wtedy compare potrzebne (ale nie ma O(1), tylko O(log n), choć to w praktyce niewielka różnica). Normalny set pozwala przeglądać po kolei, ale Tobie to chyba niepotrzebne.

możesz trzymać obiekty oddzielnie od indeksów. map vertices to w sumie równie dobrze vector, o ile wszystkie indeksy będą. Kwestia, jak obsługujesz usuwanie wierzchołków (bo przesuwanie obiektów za usuwanym wierzchołkiem

[T.....y]

@tell_me_more: no właśnie do tego problemu co chwilę dochodzę, że vectorem łatwo nie usunę, a w liście nie mam łatwego dostępu do obiektu, dlatego pomyślałem o tym map

jeżeli usuwam wierzchołek to trochę słabo trzymać po nim jego truchło w postaci struktury, która na pewno mi się nigdy nie przyda, ale równie dobrze będę chciał się często odnosić do obiektu pod konkretnym indeksem (tj. gdzieś funkcja zwróci mi indeks i chciałbym

[tell_me_more]

@TenAnonToKlopoty: no to próbuj z map

Swoją drogą mapy też są 2 - zwykła (wymaga komparatora), i unordered. Działają analogicznie jak zbiory.

[T.....y]

@tell_me_more: tak myślałem, zapomniałem po prostu, że są te unordered ogólnie :)
dzięki za pomoc jeszcze raz, w sumie pierwsza myśl była podobna, ale zamiast setów dałem tam list i trochę to toporne było

[T.....y]

@tell_me_more: niby wszystko zakodzone powinno działać a wyskakuje przy kompilacji:
Error C2280 'std::hash<Kty>::hash(const std::hash<Kty> &)': attempting to reference a deleted function
i odniesienie do biblioteki unordered_set, więc nawet nie mogę sprawdzić w którym miejscu mojego kodu coś się psuje (╯︵╰,)

[T.....y]

@tell_me_more: dobra, po krótkiej walce z tymi hashami pair znalazlem ze boost biblioteki #!$%@? to dosc dobrze (na tyle, ze mam nadzieje ze nic mi sie nie popsuje)
wszystko dziala dobrze poza tym, moge robic juz co chce z tym grafem :)

zeby nie byc taki tajemniczy z tym to robie taka dosc prosta appke gdzie mozna graficznie(SDL+OpenGL) rysowac grafy i sprawdzac w czasie rzeczywistym jego wlasciwosci, od prostych jak najwiekszy

[tell_me_more]

Gratulacje. Na przyszłość

attempting to reference a deleted function

@TenAnonToKlopoty: to znaczy, że klasa nie ma jakiejś funkcji, a ty ją próbujuesz (niekoniecznie bezpośrednio) wywołać. W tym wypadku chodzi o copy constructor

std::hash(const std::hash& h)

Czyli to, co pozwala ci np. przekazywać wartości tego typu przez wartość do funkcji. Więc skoro nie ma tego konstruktora, to takie coś:

bool funkcja(std::hash h) {
//...
}

Nie zadziała. Natomiast takie:

bool funkcja(std::hash& h)

[T.....y]

@tell_me_more: po prostu ponoc matematycznie jest niemozliwe zahashowanie par liczb calkowitych tak zeby kazda para byla oryginalna

[tell_me_more]

@TenAnonToKlopoty: matematycznie jest możliwe :) Patrz dowód na równoliczność zbiorów liczb całkowitych i wymiernych :) https://pl.wikipedia.org/wiki/Zbi%C3%B3r_przeliczalny

Natomiast to nei działa, jak liczb jest skończona ilość.

Tak, czy inaczej - nie ądzę, żeby to miało coś wspólnego. Hasze zawsze mogą mieć kolizję, map to obsługuje.

[T.....y]

@tell_me_more: Chodzilo mi dla tego przypadku, wiem ktore zbiory sa przeliczalne :D

Z drugiej strony nie wiem jak dzialaja te hashe. Co robi mapa lub set jak dojdzie do kolizji?

[tell_me_more]

@TenAnonToKlopoty: z grubsza są 2 opcje - trzyma po kilka wartości i kluczy w liście dla jednego hasha, albo jak jest kolizja to liczy nowego hasha wg jakiegoś algorytmu (np. dodając do starego hasha klucz, który mu zajął miejsce pod starym hashem, albo używając innego algorytmu haszującego po prostu) - po iluś próbach (zwykle po jednej, o ile mapa nie jest prawie cała pełna) trafi na puste miejsce i tam zapisze.

[T.....y]

@tell_me_more: dobrze wiedziec, dzieki