Comment transformer un graphe très cyclique non orienté en un graphe acyclique orienté?

Je travaille sur un algorithme TopSort modifié et je n'arrive pas à trouver/créer de grands graphes acycliques dirigés (plus de 1000 nœuds) à utiliser pour les tests. J'ai un graphe d'échantillon non orienté provenant d'un autre projet qui est de bonne taille, mais qui comporte plusieurs cycles. Y at-il un algorithme que je pourrais utiliser pour diriger les bords afin qu'il n'y ait plus de cycles?Comment transformer un graphe très cyclique non orienté en un graphe acyclique orienté?

Source

2010-12-15 Frank D.

-1

Vous cherchez à convertir le graphique en une forêt d'arbres enracinés. faire une traversée de premier plan ou de première en profondeur de chaque composant du graphe. Pendant la traversée, créez un bord dirigé entre les sommets parent-enfant.

voir http://en.wikipedia.org/wiki/Graph_traversal

Source

2010-12-15 02:26:11 gdj

errm .. il n'essaie pas de faire des arbres. il veut diriger chaque bord de sorte que le graphique résultant soit acyclique. et la méthode proposée supprimera certaines arêtes (créant ainsi un arbre). – lijie

this fournit un moyen d'obtenir des graphiques acyclique. Fondamentalement, une traversée de graphe produit un arbre, qui définit un ordre partiel sur les noeuds d'origine. Ensuite, il suffit de diriger toutes les arêtes afin qu'elles pointent dans une direction cohérente selon l'ordre partiel, ou qu'elles soient entre 2 éléments qui ne sont pas ordonnés (ils peuvent pointer dans n'importe quelle direction).

Source

2010-12-28 16:05:01 lijie

Je n'ai pas tout lu, mais à ma connaissance: la section 2.1 de cet article décrit un moyen de convertir un graphe orienté en DAG (c'est-à-dire des cycles de rupture). Et vous proposez d'ajouter une étape précédente pour convertir le graphique non orienté en graphique orienté en utilisant (tout) la traversée du graphique. –

Pour garantir que le nouveau graphe orienté est connecté, j'utiliserais la recherche par le biais de la méthode Beadth-First comme suit.

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

ce graphique doit contenir tous les bords du graphe original mais doit être orientée qu'il n'y aura pas de cercles.

Source

2013-01-18 16:36:42

Comment transformer un graphe très cyclique non orienté en un graphe acyclique orienté?

Répondre

Questions connexes