[ moki21 @ 10.05.2007. 10:27 ] @
Pozdrav svima!

Dobio sam zadatak da napisem strukturu Graph koja omogucava pohranjivanje i obradu usmjerenih grafova. Treba napisati neke metode tipa dodavanja cvora, grane, brisanja cvora, grane...
Cvor (node) je neka struktura koja vraca jedinstven ID i ima metodu za to...
Problem je u tome jer se grafu prilikom stvaranja mora moci odrediti koje ce se strukture koristiti za spremanje liste cvorova i pohranu liste susjeda za svaki cvor...
Napravio sam verziju koja sprema cvorove u <vector> i listu susjeda u <list> iz STL-a, ali to prof. nije dovoljno...
Zato bih molio nekoga za pomoc ako ima ideju kako to izvesti.

Hvala


[ rumpl @ 12.05.2007. 13:07 ] @
Citat:

Problem je u tome jer se grafu prilikom stvaranja mora moci odrediti koje ce se strukture koristiti za spremanje liste cvorova i pohranu liste susjeda za svaki cvor...


A koje strukture hoce da koristis?
[ K-up @ 14.05.2007. 11:09 ] @
Ocigledno zeli da omogucis da cvorovi budu ili u listi ili u vektoru, a da u svakom cvoru susedi budu ili u listi ili u vektoru. Prakticno, da napravis razlicite implementacije grafa i cvora... Ne znam da li sve moras da zamotas u nekakve templejte ili ne, pitaj coveka.

Ovo je sasvim validan, stavise interesantan zahtev. Imao sam prilike da pisem nekakve dekodere koji rade sa grafovima pomocu STL kontejnera, i zaista je vrlo znacajno kakva ce biti implementacija grafa. Obrada grafa je gomila stalnih prolaza kroz listu cvorova, pa u svakom cvoru kroz njegovu listu grana. U nekim primenama, cvorovi se stalno brisu; u nekim drugim se grane stalno raskidaju (odn. cvorovi brisu iz liste suseda); ali cesto je i zahtev da nekoj grani pristupis indeksiranjem, pa performanse jako zavise od implementacije.

Vredi procitati nesto i o boost::graph klasi iz biblioteke Boost, mozda. Ne znam kako su oni pisali...
[ K-up @ 15.05.2007. 09:28 ] @
Evo ga -- sigurno ti je previse, al mozda ti da neku ideju o tome sta graph klasa treba da ima: http://www.boost.org/libs/graph/doc/table_of_contents.html