Trouver tous les cycles dans le graphe, redux

Je sais qu'il y a assez peu de réponses existantes sur cette question. Cependant, je l'ai trouvé aucun d'entre eux vraiment mettre au point.
Certains prétendent qu'un cycle est (presque) la même chose qu'un fortement les composants raccordés (s). Trouver tous les cycles dans un graphe orienté) , donc on peut utiliser des algorithmes conçus pour cet objectif.
Certains font valoir que la conclusion de un cycle peut être fait par DFS et de contrôle pour le dos-bords (s). boost graph de la documentation sur les dépendances des fichiers).

Maintenant, je voudrais avoir quelques suggestions que tous cycles dans un graphe peuvent être détectés par DFS et de contrôle pour le dos-bords?
http://www.me.utexas.edu/~bard/IP/Documents/cycles.pdf (trouvé ici sur S. O.) - une autre methode basée sur le cycle de bases. Moi, personnellement, je ne trouve pas ça très intuitif donc je suis à la recherche d'une solution différente.

EDIT: Mon avis initial a été apparemment mal. S. ensuite répondre par "Idiot".

Initiale avis:
Mon avis est qu'il pouvait, en fait, travailler de cette façon que DFS-VISITE. pseudo-code de DFS) fraîchement entre chaque nœud qui n'a pas encore visité. En ce sens, chaque sommet présente un potentiel de début de cycle. En outre, comme DFS visites chaque bord une fois, chaque bord vers le point de départ d'un cycle est également couvert. Ainsi, à l'aide de DFS et le dos-bord de la vérification, il devrait en effet être possible de détecter tous cycles dans un graphe. Notez que, si les cycles avec différents nombres de participant nœuds existent (par exemple des triangles, des rectangles, etc.), le travail supplémentaire doit être fait pour discriminer les acutal "forme" de chaque cycle.

OriginalL'auteur Shadow | 2010-05-15

6

J'ai déjà répondu à cette profondeur, afin de vérifier ceci:

Une source à l'enlèvement de la sorte toujours de retour maximale du cycle?

La partie pertinente de la réponse:

Effectuer une Profondeur d'Abord de Recherche sur votre
le graphique.

Vous êtes intéressé dans la reconnaissance de retour
bords, c'est à dire, dans la traversée, un bord
qui renvoie à un ancêtre (en
l'arborescence DFS, qui est induite par
les bords de la visite de nœuds pour la première
de temps) du nœud visité. Pour
exemple, si le DFS pile a des noeuds
[A->B->C->D] et tandis que vous explorez D
vous trouverez un bord D->B, c'est un retour
bord. Chaque bord arrière définit un cycle.

Plus important encore, les cycles induits
en arrière-bords sont un ensemble de base de
les cycles du graphe. "Un ensemble de base de
les cycles": vous pouvez construire tous les cycles
le graphique juste en Fusion et en
XORing cycles du jeu de base. Pour
exemple, considérons les cycles
[A1->A2->A3->A1] et
[A2->B1->B2->B3->A2]. Vous pouvez l'union
pour le cycle:
[A1->A2->B1->B2->B3->A2->A3->A1].

OriginalL'auteur Dimitris Andreou

Peut-être cela peut vous aider en quelque sorte, j'ai trouvé cette site où une couleur de dfs pour un graphe orienté est décrite. Ainsi, vous pouvez envisager de corriger le dfs traduction en php que je présente ici.

Ce que j'ai ajoutée est une pièce pour créer une forêt et une autre partie pour trouver tous les cycles. Veuillez donc considérer qu'il n'est pas sûr de prendre ces deux parties de mon code correct pour vous.

Un avec des connaissances sur la théorie des graphes peut être en mesure de tester pour vous. Il n'y a pas de commentaires dans le dfs partie parce qu'il est déjà décrit dans le site de référence. Je vous suggère de prendre un exemple avec plus d'un arbre et de dessiner la forêt (besoin de 4 couleurs) dans un article pour mieux comprendre.

C'est le code:

 <?php 

    //define the graph
    $g = Array(
    1 => Array(1,2,3,4,5),
    2 => Array(1,2,3,4,5),
    3 => Array(1,2,3,4,5),
    4 => Array(1,2,3,4,5),
    5 => Array(1,2,3,4,5)
    );

    //add needed attributes on the graph
    $G = Array();
    foreach($g as $name => $children)
    {
        $child = Array();
        foreach($children as $child_name)//attaching a v letter is not needed, just a preference
            $child['v'.$child_name] = null;

        $G['v'.$name] = 
        Array('child'=>$child, 
            'color'=>'WHITE',//is used in dfs to make visit
            'discover_time'=>null,//is used in dfs to classify edges
            'finish_time'=>null,//is used in dfs to classify edges                  
            'father'=>null,//is used to walk backward to the start of a cycle
            'back_edge'=>null//can be omited, this information can be found with in_array(info, child_array)
        );
    }   


new test($G);
class test
{
    private $G = Array();//graph
    private $C = Array();//cycles
    private $F = Array();//forest
    private $L = Array();//loops
    private $time_counter = 0;

    public function __construct($G)
    {
        $this->G = $G;

        foreach($this->G as $node_name => $foo)
        {
            if($this->G[$node_name]['color'] === 'WHITE')
                $this->DFS_Visit($node_name);
        }

        $tree =array();
        foreach($this->G as $node_name => $data)
        {
            if($data['father'] === null)//new tree found
            {
                $this->F[] = $tree;//at first an empty array is inserted
                $tree = Array();
                $tree[$node_name] = $data; 
            }
            else
                $tree[$node_name] = $data;
        }
        array_shift($this->F);//remove the empty array
        $this->F[] = $tree;//add the last tree

        $this->find_all_elementary_cycles();

        file_put_contents('dump.log', count($this->L)." Loops found: \n", FILE_APPEND);
        file_put_contents('dump.log', print_r($this->L,true)."\n", FILE_APPEND);

        file_put_contents('dump.log', count($this->C)." Cycles found: \n", FILE_APPEND);
        file_put_contents('dump.log', print_r($this->C,true)."\n", FILE_APPEND);

        file_put_contents('dump.log', count($this->F)." trees found in the Forest: \n", FILE_APPEND);
        file_put_contents('dump.log', print_r($this->F,true)."\n", FILE_APPEND);
    }

    public function find_all_elementary_cycles()
    {
        /*** For each tree of the forest ***/
        foreach($this->F as $tree)
        {
            /*** Foreach node in the tree ***/
            foreach($tree as $node_name => $node)
            {
                /*** If this tree node connects to some child with backedge 
                (we hope to avoid some loops with this if) ***/
                if ( $node['back_edge'] === true )
                    /*** Then for every child ***/
                    foreach ( $node['child'] as $child_name => $edge_classification)
                        if($edge_classification === 'BACK_EDGE')
                            $this->back_edge_exploit($node_name, $child_name, $tree);               
            }
        }
    }

    private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree)
    {
        /*** The input of this function is a back edge, a back edge is defined as follows
        -a sender node: which stands lower in the tree and a reciever node which of course stands higher
        ***/

        /*** We want to get rid of loops, so check for a loop ***/
        if($back_edge_sender == $back_edge_receiver)
            return $this->L[] = $back_edge_sender;//we need to return cause no there is no cycle in a loop

        /*** For this backedge sender node the backedge reciever might send a direct edge to the sender ***/
        if( isset($this->G[$back_edge_receiver]['child'][$back_edge_sender]) > 0 )
            /*** This edge that the reciever sends could be a tree edge, this will happen 
            -in the case that: the backedge reciever is a father, but it can be a forward edge
            -in this case: for the forward edge to exist the backedge reciever does not have to be 
            -a father onlly: it can also be an ancestore. Whatever of both cases, we have a cycle
            ***/
            if( $this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'TREE_EDGE' or 
                $this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'FORWARD_EDGE')
                    $this->C[md5(serialize(Array($back_edge_receiver,$back_edge_sender)))]
                    = Array($back_edge_receiver,$back_edge_sender);


        /*** Until now we have covered, loops, cycles of the kind father->child which occur from one tree edge 
        - and one: back edge combination, and also we have covered cycles of the kind ancestore->descendant 
        -which: occur from the combination of one forward edge and one backedge (of course might happen that 
        -a father: can send to the child both forward and tree edge, all these are covered already).
        -what are left: are the cycles of the combination of more than one tree edges and one backedge ***/
        $cycle = Array();
        attach_node://loops must be handled before this, otherwise goto will loop continously
        $cycle[] =  $back_edge_sender; //enter the backedge sender
        $back_edge_sender = $tree[$back_edge_sender]['father']; //backedge sender becomes his father
        if($back_edge_sender !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet
            goto attach_node;//the loop again

        $cycle[] = $back_edge_receiver;
        $cycle = array_reverse($cycle);
        $this->C[md5(serialize($cycle))] = $cycle;
    }


    private function DFS_Visit($node_name)
    { 
        $this->G[$node_name]['color'] = 'GRAY';
        $this->G[$node_name]['discover_time'] = $this->time_counter++;

        foreach($this->G[$node_name]['child'] as $child_name => $foo)
        {               
                if($this->G[$child_name]['color'] === 'BLACK') {#child black 

                    if( $this->G[$node_name]['discover_time'] < 
                    $this->G[$child_name]['discover_time'] ){#time of father smaller
                        $this->G[$node_name]['child'][$child_name] = 'FORWARD_EDGE';
                    }
                    else{#time of child smaller
                        $this->G[$node_name]['child'][$child_name] = 'CROSS_EDGE';
                    }
                }
                elseif($this->G[$child_name]['color'] === 'WHITE'){#child white
                    $this->G[$node_name]['child'][$child_name] = 'TREE_EDGE';
                    $this->G[$child_name]['father'] = $node_name;#father in the tree
                    $this->DFS_Visit($child_name);
                }#child discovered but not explored (and father discovered)
                elseif($this->G[$child_name]['color'] === 'GRAY'){#child gray
                    $this->G[$node_name]['child'][$child_name] = 'BACK_EDGE';
                    $this->G[$node_name]['back_edge'] = true;
                }
        }//for  
        $this->G[$node_name]['color'] = 'BLACK';//fully explored
        $this->G[$node_name]['finish_time'] = $this->time_counter++;
    }

}

?>

Et c'est la sortie:

EDIT 1 :
Le back_edge_exploit méthode pourrait être erplaced par cette version:

![private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree)
{
    /*** The input of this function is a back edge, a back edge is defined as follows
    -a sender node: which stands lower in the tree and a reciever node which of course stands higher
    ***/

    /*** We want to get rid of loops, so check for a loop ***/
    if($back_edge_sender == $back_edge_receiver)
        return $this->L\[\] = $back_edge_sender;//we need to return cause no there is no cycle in a loop

    $cycle = Array();//There is always a cycle which is a combination of tree edges and on backedge 
    $edges_count = 0; //If the cycle has more than 2 nodes we need to check for forward edge
    $backward_runner = $back_edge_sender;//this walks backward up to the start of cycle

    attach_node://loops must be handled before this, otherwise goto will loop continously
    $edges_count++;
    $cycle\[\] =    $backward_runner; //enter the backedge sender
    $backward_runner = $tree\[$backward_runner\]\['father'\]; //backedge sender becomes his father
    if($backward_runner !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet
        goto attach_node;//the loop again
    else
        $cycle\[\] = $backward_runner;

    if($edges_count>1 and $this->G\[$back_edge_receiver\]\['child'\]\[$back_edge_sender\] === 'FORWARD_EDGE' )
        $this->C\[\] = Array($back_edge_receiver,$back_edge_sender);

    $this->C\[\] = array_reverse($cycle); //store the tree edge->back_edge cycle 
}][2]

EDIT 2:
Je dois dire que j'ai trouvé que back_edge_exploit est insuffisante, elle ne pourra trouver cycles qui sont faits avec des arbres des bords et un bord arrière.

**** Edit 3: ****
Bien que ces solutions est incomplète, il dispose de quelques informations utiles, même l'insuffisance de soi est un élément d'information, donc je pense qu'il pourrait être utile de le garder. Mais la principale raison pour laquelle j'ai édité ma réponse est que j'ai trouvé une autre solution que je vais vous présenter ci-dessous.

Mais avant cela, un autre avis peut être faite à propos de la dfs approche, il y a des cycles qui pourrait se produire par la marche n'importe quelle combinaison valide toutes les croix de l'avant,arbre,bord arrière. Afin de trouver le réel cycles en s'appuyant sur les informations de dfs n'est pas trivial (nécessite un code supplémentaire), pensez à
cet exemple:

Trouver tous les cycles dans le graphe, redux

Aussi longtemps que la nouvelle solution est concernée, elle est décrite dans un vieux livre de 1970, par James C. Tiernan (Suivez ce lien) comme un algorithme efficace pour la recherche de tous les cycles élémentaires dans un graphe orienté. Il y a aussi un moderne mise en œuvre du présent sans goto Voir ici

Mon de la mise en œuvre du Cycle Élémentaire de l'Algorithme (c'est le nom) est en php et est aussi proche que possible de l'original . J'ai déjà vérifié et il fonctionne. C'est sur les graphes orientés, si vous déclarez graphique de sorte qu'il est dirigé cycle v1->v2->v3 et v2->v3->v1 puis les deux cycles seront trouvés ce qui est logique puisqu'il fonctionne sur les graphes orientés.

Comme pour les graphes non dirigés, l'auteur propose d'autres algorithmes qui font une meilleure solution que de modifier les algorithmes, mais il peut être fait en modifiant le graphe de définition et par l'ajout d'une vérification supplémentaire pour les cycles de longueur 2 qui sont considérés comme non-orienté bords. En particulier, un non-orienté cycle de trois noeuds seraient définies deux fois, dans la définition, à la fois par l'orientation, comme ceci: v1->v2->v3 et v3->v2->v1. Ensuite, l'algorithme va trouver deux fois, une fois par orientation, alors une modification d'une seule ligne sur EC3_Circuit_Confirmation pouvez couper le plus.

Les nœuds sont définis de manière séquentielle, on peut changer la constante first et la liste d'adjacence de faire le premier nœud de compter à partir de zéro ou un.

C'est le code php pour la CE, l'Algorithme de Tiernan :

<?php 

    define(first,1);    //Define how to start counting, from 0 or 1 
    //nodes are considered to be sequential 
    $G[first] = Array(2); $G[] = Array(1,3); $G[] = Array(4); $G[] = Array(1); 


    $N=key(array_slice($G, -1, 1, TRUE));//last key of g
    $H=Array(Array());
    $P = Array();
    $P[first] = first;
    $k = first;
    $C = Array();//cycles
    $L = Array();//loops

########################## ALGORITHM START #############################

    #[Path Extension]
    EC2_Path_Extension:  
    //scan adjacency list
        foreach($G[$P[$k]] as $j => $adj_node)
            //if there is an adjacent node bigger than P[1] and this nodes does not belong in P
            if( ($adj_node > $P[first]) and (in_array($adj_node, $P))===false and 
            (count($H[$P[$k]])>0 and in_array($adj_node, $H[$P[$k]]))===false)
            {
                $k++;
                $P[$k] = $G[$P[$k-1]][$j];  
                goto EC2_Path_Extension;    
            }

    #[EC3 Circuit Confirmation]  
    EC3_Circuit_Confirmation: 
    if(!in_array($P[first], $G[$P[$k]]))
        goto EC4_Vertex_Closure;
    //otherwise
    if (count($P)===1)
        $L[] = current($P);
    else
        $C[] = implode($P);


    #[EC4 Vertex Closure]
    EC4_Vertex_Closure:
    if($k===first)
        goto EC5_Advance_Initial_Vertex;

    $H[$P[$k]] = Array(); 
    $H[$P[$k-1]][] = $P[$k];
    unset($P[$k]);
    $k--;
    goto EC2_Path_Extension;


    #[EC5 Advance Initial Vertex]
    EC5_Advance_Initial_Vertex:
    if($P[first] === $N)
        goto EC6_Terminate;

    $P[first]++; 
    $k=first;
    //Reset H 
    $H=Array(Array()); 
    goto EC2_Path_Extension;

    EC6_Terminate:
########################### ALGORITHM END ##################################

    echo "\n\n".count($L)."$count loops found: ".implode(", ",$L)."\n\n";
    echo count($C)." cycles found!\n".implode("\n",$C)."\n";

    /*** Original graph found in the paper ***/
    //$G[first] = Array(2); $G[] = Array(2,3,4);
    //$G[] = Array(5); $G[] = Array(3); $G[] = Array(1);


    ?>

OriginalL'auteur Melsi

1

Ma suggestion est d'utiliser l'algorithme de Tarjan pour trouver ensemble des composantes fortement connexes, et Hierholzer de l'algorithme pour trouver tous les cycles dans la composante fortement connexe.

Voici le lien pour l'implémentation de Java avec un cas de test:
http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html

OriginalL'auteur stones333
0

Si une traversée de l'algorithme de visites chaque bord qu'une seule fois, alors il ne peut pas trouver tous les cycles. Un tronçon peut faire partie de plusieurs cycles.

btw, ce qui est un arrière-edge?

Aussi, peut-être vous devriez reformuler/format de votre question. Il est très difficile à lire.

Un dos-bord est un avantage qui va d'un nœud à l'un de ses ancêtres dans un arbre de recherche. E. g. les arêtes (A,B), (B,C) et (C,A) un graphe non-dirigé, alors soit (A,B) ou (C,A) sera un dos-bord (si racine = Un). Ce n'est pas un arbre de pointe de l'arbre de recherche, et il est créé lorsque, au cours de DFS-VISITE, un bord conduit à partir d'un nouveau nœud à un déjà visité (gris), mais pas encore fini, nœud.<br> Pour votre première réponse: Si une arête est partie de plusieurs cycles, chaque cycle sera traversé la fois => tous les bords seront détectés => tous les cycles doivent être détectées autant que je sache.<br> s'il vous Plaît corrigez-moi si je me trompe!
Désolé, je dois corriger moi-même et d'accord avec vous "Débile". J'ai limité mon "cycles" de triangles lors de l'exploration d'exemples et de se concentrer fortement sur la détection de ces triangles. Cela signifie que l ' "algorithme" toujours suivi les bords qui mènent directement à triangles, bien que ce ne doit pas être le cas. E. g. Les 2 triangles, le partage d'un bord (plus grand cycle = rectangle), le rectangle peut être découvert d'abord comme un cycle, et les 2 triangles peut-être manqué. Et vice-versa.

OriginalL'auteur

Vous devez vous connecter pour publier un commentaire.