tania reprezentacja grafu C++

Witam,
Możecie zaproponować mi jakąś tanią (w sensie pamięciożerności) reprezentację grafu ?
Graf może mieć pętle, krawędzie wielokrotne. Jest skierowany.
Zwykłe vector <int> G[N] odpada - za ciężkie jak na warunki zadania.

Według mnie najlepiej na liście sąsiedztwa

A jak coś takiego napisać efektywnie i elegancko ?

Jeżeli ilość krawędzi jest mała w stosunku do możliwej ilości krawędzi to lista sąsiedztwa:

struct Edge { size_t from,to; double weight; };
list<Edge> LS;

Jeżeli duża to macierz sąsiedztwa:

vector<vector<list<double> > > MS(NodeCount,vector<list<double> >(NodeCount));

Witam.
Możesz też zaglądnąć do źródeł otwartych bibliotek grafowych. W którejś widziałem chyba takie rozwiązanie:

• liczba wierzchołków
• tablica o długości równej liczbie wierzchołków, przechowująca indeks ostatniej krawędzi wychodzącej z wierzchołka
• tablica o długości równej liczbie krawędzi, przechowująca indeks wierzchołka do którego prowadzi krawędź
  Można sporo zaoszczędzić, zwłaszcza jeśli indeksy wierzchołków i/lub krawędzi mogą być mniejsze od wskaźnika. Graf nie jest też rozsiany po pamięci. Problemem jest jednak wydajne modyfikowanie takiego grafu, chyba że chodzi o stworzenie poprzez dodawanie kolejnych wierzchołków (których ilość też dobrze aby byłą znana z góry), wraz z wychodzącymi z nich krawędziami. Napisz jakie operacje chcesz wykonywać na tym grafie, to może uda się jakoś lepiej pomóc.

Chciałbym móc budować dynamiczne ten graf. Tzn wiem ile będzie maxymalnie krawędzi i werzchołków(wierzchołków milion, tyle samo krawędzi)
Graf skierowany - wszystkie krawędzie dozwolone. Dynamicznie, czyli dodając po krawędzi (losowa kolejność).
Ile by mniej więcej ważył Twój graf?
Chciałbym też ten graf przechodzić DFSem i BFSem.

maturzysta2013 napisał(a):

Chciałbym móc budować dynamiczne ten graf. Tzn wiem ile będzie maksymalnie krawędzi i werzchołków(wierzchołków milion, tyle samo krawędzi)
Graf skierowany - wszystkie krawędzie dozwolone. Dynamicznie, czyli dodając po krawędzi (losowa kolejność).

Nie znam wydajnego sposobu budowania tej struktury jeśli krawędzie nie są posortowane po wierzchołku źródłowym. Jeśli jesteś zainteresowany mogę spróbować poszukać biblioteki, które jej używała, może tam znalazło by się jakieś rozwiązanie.

Ile by mniej więcej ważył Twój graf?

(liczba_wierzchołków + 1) * rozmiar_indeksu_dla_wierzchołka + liczba_krawędzi * rozmiar_indeksu_dla krawędzi
Skoro milion, można użyć indeksów 4 bajtowych, więc około 8MB.
Można też kosztem wydajności i skomplikowania upychać liczby na 20 bitach co dało by około 5MB.

Chciałbym też ten graf przechodzić DFSem i BFSem.

Do tego nadaje się dobrze, ale musisz doliczyć jeszcze miejsce na atrybuty, można je trzymać w kolejnych tablicach, lub jeśli nie upychał być wszystkiego na 20 bitach upchnąć na niewykorzystanych bitach wierzchołków i krawędzi.

Skoro miejsce na poprzedników jest potrzebne po wczytaniu grafu, to można na początku wczytywać do niej wierzchołki źródłowe, a później posortować tą tablice, przemieszczając jednocześnie dane w tablicy wierzchołków docelowych, następnie na jej podstawie zbudować tablicę z liczbą krawędzi wychodzących z danego wierzchołka i problem wydajnego wczytywania rozwiązany.
Równa ilość wierzchołków i krawędzi może sugerować, że autorzy zadania chcieli ułatwić implementacje czegoś takiego:)

A jak można to upychać na 20 bitach ?

Wykorzystujesz pola bitowe: http://4programmers.net/C/Pola_bitowe

A to będzie trudne takie korzystanie z tych pól bitowych ?

No ok.
Ale czemu sizeof zwraca ten sam rozmiar dla:
struct T{
int T;
int Q;
}
T[10^6]
struct O{
int T:20;
int W:20;
}
O [10^6]

Jaka jest przyczyna, że sizeof(T) = sizeof(O) ?

Pakowanie pól bitowych w pamięci jest zależne od kompilatora (niestety). Jeśli chcesz mieć maksymalną możliwą oszczędność to musisz ręcznie wyciągać z pamięci co Cię interesuje.

W takim razie można coś zdziałać tymi polami bitowymi czy nie ?

Ja kiedyś przepchałem jedno zadanie dzięki użyciu pól bitowych, a kompilator na sprawdzarce to był g++, a taki jest w sumie na każdym automatycznym serwisie sprawdzającym, więc można - próbuj.

Rozmiar pojedynczego elementu tablicy (struktura) bedzie wyrownany do wielokrotnosci inta niezaleznie od struktury pol bitowych. Absolutne minimum to wyrownanie do bajtow, chyba nie wyobrazacie sobie umieszczenia obiektu pod adresem XYZ i 5/8?

maturzysta2013 napisał(a):

A jak można to upychać na 20 bitach ?

Operować nie na tablicy liczb, tylko na tablicy bajtów, używać przesunięć bitowych tam gdzie bajty nie są równe, tak aby rozłożyć je w pamięci co 20 bitów, czyli 2,5 bajta. Łatwiej będzie jeśli można na każdy indeks poświęcić całe 3 bajty, ewentualnie rozbijając na dwie tablice (16+8). Można opakować sobie w klasę z przeciążonym operatorem[] , to nawet by się wygodnie tym operowało.

W ile pamięci musisz się zmieścić? Czy limit przekracza już sama struktura, czy razem z innymi danymi (atrybuty, itp.)? Może lepiej poszukać pamięci gdzie indziej? Takie upakowanie danych może bardzo negatywnie wpłynąć na wydajność.

W takim razie zrobię to wszystko inaczej, skoro tak nie idzie.

Rozmiar każdej struktury jest dobijany do pewnego ustalonego rozmiaru najczęściej to rozmiar int'a (jest nieco bardziej skomplikowane, poczytaj o data allignment).
Czyli struct BF { int A:16; int B:16; }; już będzie miała mniejszy rozmiar.
Dynamicznie dobrze zadziała pierwsza struktura którą podałem.

Struktura przechowująca indeksy wierzchołków źródłowych i docelowych będzie zajmowała tyle samo pamięci w przypadku gdy liczba wierzchołków jest równa liczbie krawędzi, jeśli przechowywane będą w tablicy, a nie liście. Problemem będzie jednak wydajne pobranie listy sąsiadów celem przeszukania grafu.

witold napisał(a):

Struktura przechowująca indeksy wierzchołków źródłowych i docelowych będzie zajmowała tyle samo pamięci w przypadku gdy liczba wierzchołków jest równa liczbie krawędzi, jeśli przechowywane będą w tablicy, a nie liście.
Chrzani waść.
Załóżmy że mamy 3 wierzchołki oraz 3 krawędzi. W macierze mamy 33sizeof(Value) w liście mamy 3*(2sizeof(Index)+sizeof(Value))
Dla index'u 32 bitowego zaś Value typu double mamy:
Macierz: 338=72
Lista: 3(2*4+8)=48
Przy większych ilościach wierzchołków różnica będzie jeszcze większa.

witold napisał(a):

Problemem będzie jednak wydajne pobranie listy sąsiadów celem przeszukania grafu.
Nigdy nie było to problemem, chyba że beznadziejnie zorganizowany graf, np wybrano macierz sąsiedztwa.

_13th_Dragon napisał(a):

Załóżmy że mamy 3 wierzchołki oraz 3 krawędzi. W macierze mamy 33sizeof(Value)

Nie pisałem nic o macierzy sąsiedztwa.

_13th_Dragon napisał(a):

w liście mamy 3*(2*sizeof(Index)+sizeof(Value))

Tyle mamy w tablicy, w liście mamy jeszcze wskaźniki na poprzednie i następne elementy. O tej różnicy właśnie pisałem.

witold napisał(a):

Problemem będzie jednak wydajne pobranie listy sąsiadów celem przeszukania grafu.
Nigdy nie było to problemem, chyba że beznadziejnie zorganizowany graf, np wybrano macierz sąsiedztwa.</quote>
W strukturze którą podałeś, dostęp do listy sąsiadów danego wierzchołka wymaga wyszukania ich na podstawie wartości pola source, co jest niepotrzebnym narzutem którego można by uniknąć wybierając strukturę lepiej dostosowaną do takiej operacji.
W takim razie zostaje mi założyć, że nie jest problemem zaimplementowanie BFS i DFS bez iterowania po sąsiadach danego wierzchołka. Czy mógłbyś podzielić się rozwiązaniem?