Jak przekształcić niekierowany, bardzo cykliczny wykres w skierowany wykres acykliczny?

Question

Pracuję nad zmodyfikowanym algorytmem TopSort i mam problem ze znalezieniem/tworzeniem dużych (ponad 1000 węzłów) skierowanych acyklicznych wykresów do wykorzystania do testowania. Mam nieukierunkowany przykładowy wykres z innego projektu, który ma dobry rozmiar, ale ma wiele cykli. Czy istnieje algorytm, którego można użyć do kierowania krawędziami, aby nie było już cykli?

Answer 1

Szukasz sposobu przekształcenia wykresu w las zrootowanych drzew. wykonać pierwszy lub pierwszy odgłos wykresu każdego komponentu wykresu. Podczas przemierzania ustaw krawędź pośrednią między wierzchołkami nadrzędnymi i podrzędnymi.

zobaczyć http://en.wikipedia.org/wiki/Graph_traversal

Answer 2

this zapewnia sposób, aby uzyskać acykliczne wykresy. Zasadniczo, przejście przez wykres tworzy drzewo, które definiuje częściową kolejność na pierwotnych węzłach. Następnie po prostu kieruj wszystkie krawędzie tak, aby albo były skierowane w spójnym kierunku, zgodnie z kolejnością częściową, albo pomiędzy 2 elementami, które nie są uporządkowane (mogą one wskazywać w dowolnym kierunku).

Answer 3

Aby zapewnić, że nowy kierowany wykres jest podłączony, użyłbym pierwszego wyszukiwania w następujący sposób.

old_undirected graph G 
new_directed graph D 
dequeue Q 
v is any node in G 
add v to D 
Q.push_back(v) 
while(Q is not empty): 
    v = Q.pop_front() 
    for all neighbors u to v: 
     if u in D 
       add edge u->v to D 
     else 
       add u to D and add edge v->u to D 
       Q.push_back(u) 

return D 

ten wykres powinien zawierać wszystkie krawędzie oryginalnego wykresu, ale powinien być tak skierowany, aby nie było żadnych okręgów.