Witam,
Czy znacie jakąś strukturę, która szybko może usuną krawędź ? Tzn przechodzimy graf DFS-em i powiedzmy, że idziemy krawędzią nieskierowaną z a do b, to wówczas usuwamy "informację", że z a jest ścieżka do b oraz, że z b jest ścieżka do a. Co więcej oczekuję, że będzie można wybrać szybko dowolną krawędź z (powiedzmy) wierzchołka a - tzn idź byle gdzie.
Zdaję sobie sprawę, że można to wykonać za pomocą set'a z STL'a. Jednak czy znacie coś szybszego ?
Owszem, dodaj do rekordu krawędzi wartość logiczną.
Nie rozumiem pytania. W każdej z 3 głównych reprezentacji grafu - macierz VxV, macierz ExV i lista sąsiedztwa V->{E} można takie coś wykonywać w czasie stałym.
Fajnie, że przyszliście do wątku.
@Shalom. Owszem, w macierzy sąsiedztwa można w czasie stałym, ale nas nie stać na taką macierz, bo mamy do stu tysięcy wierzchołków i do miliona krawędzi.
A co do listy sąsiedztwa to się nie zgadzam, że wykonamy to w czasie stałym, bo jak ?
@_13th_Dragon nie bardzo rozumiem jak miałoby to wyglądać. Może trochę bardziej "pseudokodowo" ?
if(!Krawedz.Usunenta)
{
...
Krawedz.Usunenta=true;
}
_13th_Dragon napisał(a):
if(!Krawedz.Usunenta)
{
...
Krawedz.Usunenta=true;
}
Poproszę jednak o "głębsze przemyślenia". Nie wydaje mi się, że może w ten sposób się to udac. Powiedzmy, że wybieramy krawędź a---b.
Wówczas łatwo faktcznie "zablokować" przejście od a do b (w czasie stałym). Jak jednak w czasie stałym zablokujesz przejście z b do a ?
Do struktury/obiektu reprezentującej krawędź dodajesz zmienną logiczną i używasz ją w algorytmach.
Głębsze przemyślenia będą dopiero po podaniu przez ciebie twojej reprezentacji grafu.
Ja reprezentuję graf jako listę sąsiedztwa, ale zamiast listy mam set.
Możesz więc pokazać, jak Ty realizujesz takie usuwanie krawędzi w czasie stalym
Jak masz tego set'a zadeklarowanego?
set <int> G[N];
Więc teraz będzie:
set<pair<bool,int> > G[N];
lub:
map<int,bool> G[N];
I czy dostajesz czas stały ? Nadal masz narzut set'a - logarytmiczny.
Ale ja nie rozumiem za bardzo problemu. Przecież usuwanie z unordered_set działa w czasie stałym. Pobieranie elementu też. Skoro znasz indeksy wierzchołków dla krawędzi którą chcesz usuwać to robisz sobie
G[x].erase(y);
G[y].erase(x);
I voila, mamy usunięcie krawędzi średnio w O(1).
Dla jasności C++11 wprowadziło unordered_set i unordered_map ( http://www.cplusplus.com/reference/unordered_set/unordered_set/ ) które są implementowane na tablicy hashujacej i mają czasy O(1).
Tak, ale co w przypadku gdy nie możemy zastosować C++ 11 ?
To cudów nie zdziałasz. Czas O(1) mozesz mieć realnie tylko podczas używania tablicy. Skoro wymagania pamięciowe są zbyt duże żeby zrobic normalną macierz (i do tego byłaby to macierz rzadka więc opłacalność słaba) to musisz użyć implementacji macierzy rzadkich. I znów wielkiego wyboru nie ma -> albo drzewa albo hashtable. Skoro nie ma C++11 to zawsze możesz napisać własny hashtable, ale z jakością może być różnie.
xawery napisał(a):
I czy dostajesz czas stały ? Nadal masz narzut set'a - logarytmiczny.
Przecież nie usuwasz fizycznie tej krawędzi tylko zaznaczasz jako usuniętą.
Ok, powiem dokładnie o co chodzi.
To jest DFS, ale trochę zmodyfikowany. Odpalam DFS'a i idę ZAWSZE dowolną krawędzią. ZAWSZE idę, byle iść. O to gdzie dojdę to się nie martwcie, ja już wiem co robić. Czyli nie mam żadnej pętli po wierzchołkach sąsiadujących, tylko zawsze idę do "*begin()". Dosłownie tak, idę do begin, następnie go usuwam. (z a do b oraz z b do a). I teraz powiedz mi jak to zastąpić, a raczej czy w ogóle się da?
Tak na prawdę to potrzebuję operacji:
Daj mi dowolną krawędź, którą mogę iść (która nie została zużyta).
A realizuje to tak jak opisałem za pomocą seta.
Jak ktoś ma inny pomysł (może inny zupełnie) to chętnie posłucham.
Zrób listę krawędzi która będzie miała w sobie dwa inty określające v1 i v2? Wyciągaj z tej listy krawędzie do przetworzenia i tyle...
Pamięciowo będziesz miał połowę z tego co teraz O(E) zamiast 2*O(E)
Czy przypadkiem nie próbujesz zrobić w ten sposób:
@Shalom, jak mogę dać radę to wykonać w ten sposób ? Przecież jak wybiorę pierwszą krawędź to dalej muszę zacząć iść po grafie przecież.
@Dragon
Tak, muszę w celu późniejszego przetwarzania rozłożyć na cykle (rozłączne krawędziowo).
I właśnie tym zmodyfikowanym DFS'em dokonje tego rozkładu, następnie dalej przetwarzam ten rozkład.
Koniec końców nie uda nam się znaleźć lepszego rozwiązania.
Nie bądź niedowiarkiem :P Jeden sposób na lepsze rozwiazanie już ci podałem -> hash_set zamiast tree_seta. Sposób dragona też jest w twoim przypadku dobry.
Ale ja bym zrobił w takim razie tablicę referencji/wskaźników do obiektów <int, int, bool> i wkładał krawędzie na zasadzie:
edge* e = new edge(v1, v2, false);
G[v1].add(e);
G[v2].add(e);
I teraz oznaczenie takiej krawędzi jako już przebytą wymaga jedynie zrobienia edge->traversed=true bo mamy tylko jedną krawędź i z obu stron zrobi się niedostępna.
W takim razie porzuć ten pomysł.
@Dragon Mógłbyś uzasadnić dlaczego otrzymasz cykle rozłączne krawędziowo, bo nie widzę tego.
@Shalom, wiem że podałeś lepszy sposób, ale czy dobrze myślę że ten sposób nie może być zrealziowany w standardowej bibliotece C++'a (bez 11) ?
@xawery ty tak poważnie? ;] Wyobraź sobie że ten hashset w C++11 też jakoś ktoś zaimplementował, nie wykorzystano do tego magii. Zaręczam ci że da się tą sztukę potwórzyć! W skrócie: możesz sobie taki hashset po prostu napisać samemu. Jakas prosta implementacja to jest zadanie na godzinę dla studenta 1 roku ;]
Poza tym mamy rok 2014, niedługo będzie 2015. A ta 11 w C+11 nie wzięła sie z przypadku... ;)
No tak, spodziewałem się tego. Ciągniemy wątek przez trzy strony i jedyny wniosek, to jest taki że należy zmienić strukturę danych. Wystarczyłby jeden post, a wszyscy mi chcą tutaj pokazywać rożne różne pomysły, które ostatecznie biorą w łeb :)
Nie otrzymam cykle rozłączne krawędziowo. Tylko że znacznie szybciej tym algorytmem otrzymasz wszystkie cykle podstawowe i z nich wybierzesz rozłączne krawędziowo niż będziesz je szukać przejściem DFS
Jak to ? Z duzego zbiorów cykli uzyskasz mniejsze zbiory cykli. Doszliśmy do tego sameo. Teraz mam kilka mniejszych cykli.
Uzyskam tyle samo ale w krótszym czasie.
Potrzebujemy rozebrać graf na cykle rozłączne krawędziowo Ty tego nie uzyskasz w ten sposób. Uzyskasz rozkład na cykle, ale nierozłączne krawędziowo. Czyli kręcisz się w kółko.
Załóż my że masz taki graf:
┌─┬─┐
├─┼─┤
└─┴─┘
Algorytmem co podałem znajdziesz 4 cykle w czasie O(n) z których wybierzesz 2 również w czasie O(n).
Tym co próbujesz zrobić możliwe że znajdziesz tylko jeden, również może że dwa (zależy jak wypadnie), ale sprawdzać możesz nawet 14 sztuk (wzrost wykładniczy)