Generowanie losowego DAG'u

Witam!

Mam za zadanie napisać program do pomiaru czasu działania algorytmu sortowania topologicznego, na podstawie losowego DAG'u o nasyceniu krawędziami 60%. Generowanie grafu o nasyceniu 60% udało mi się zrobić, problem tylko w tym, że do sortowania topologicznego graf nie może zawierać cykli i niestety z tym mam problem :( Szukałem u wujka Google, ale niestety zbyt wielu przydatnych informacji nie znalazłem, jedynie tytuł książki "Algorytmy C++, Grafy", gdzie widnieje w spisie treści pozycja "Generowanie grafów", niestety nie posiadam tej książki. Wskazówki mile widziane :)

Pozdrawiam!

Wskazówka: kupić tą książkę ;P

Wszystko byłoby ok, gdybym miał kiedy i gdzie ją zakupić... Poza tym to jest jedyne zadanie, w którym muszę wygenerować graf nie zawierający cykli, więc jaki jest sens wydawać 60zł na książkę, która w przyszłości mi się nie przyda.

Graf bez cykli to drzewo. Musisz wygenerować drzewo. Możesz losować każdemu kolejnemu wierzchołkowi ile ma mieć potomków, albo losować każdemu wierzchołkowi rodzica wśród wierzchołków już po losowaniu.
Gorzej tylko z tym 60% nasyceniem. W grafie o 100% nasyceniu mamy n*(n-1)/2 krawędzi (przy n wierzchołkach). W drzewie każdy wierzchołek (oprócz korzenia) ma jednego rodzica - jedną krawędź, która należy tylko do niego, więc wszystkich jest n-1. Łatwo policzyć, że nasycenie krawędzi w drzewie będzie wynosić zawsze (2/n)*100%

adf88 napisał(a)

Graf bez cykli to drzewo. Musisz wygenerować drzewo. Możesz losować każdemu kolejnemu wierzchołkowi ile ma mieć potomków, albo losować każdemu wierzchołkowi rodzica wśród wierzchołków już po losowaniu.
Gorzej tylko z tym 60% nasyceniem. W grafie o 100% nasyceniu mamy n*(n-1)/2 krawędzi (przy n wierzchołkach). W drzewie każdy wierzchołek (oprócz korzenia) ma jednego rodzica - jedną krawędź, która należy tylko do niego, więc wszystkich jest n-1. Łatwo policzyć, że nasycenie krawędzi w drzewie będzie wynosić zawsze (2/n)*100%

Błąd, to jest graf skierowany, więc niekoniecznie jest drzewem, gdy nie ma cykli.

Może zastosuj algorytm jakby odwrotny do sortowania topologicznego? Wierzchołki masz ponumerowane od 1..n, dla każdego wierzchołka i, począwszy od 1 losujesz liczbę krawędzi wychodzących z niego (najlepiej od razu tak, żeby statystycznie nasycenie wyszło te 60%) i losujesz do których wierzchołków one prowadzą (z liczb i..n). Teraz, żeby był sens sortowania topologicznego, przemieszaj tą tablicę. :P