Discussion :

[deuzef68]

Bonjour

pour un projet perso de recherche sur un graphe, qui fait d'ailleurs l'objet d'une autre discussion,
je me demande si on ne pourrait pas utiliser les expressions régulières pour générer...tout d'abord
mais surtout valider qu'un chemin fait une boucle.

Je m'explique
voila j'ai un graphe représenté par le schéma ci-dessous


ce graphe représente toutes les possibilités réelles d'avoir un boucle dans mon graphe

je m'explique : si on prend comme départ D1 (ça pourrait être D2 ou un autre état)...
et que l'on parcourt le graphe...
on est certain d'avoir une boucle en ressortant en D1,
j'ajoute comme condition qu'il faut aussi avoir parcouru chaque état au moins une fois

ainsi le chemin, par exemple, D1-D2-D3-D4-D5-D6-D1 est une boucle...
D1-D2-D1-D2-D3-D4-D3-D4-D5-D6-D1 est aussi une boucle

mais D1-D2-D1-D2-D3-D4-D3-D2-D1 n'est pas une boucle

Ne pourrait-on pas "exprimer" ce graphe sous la forme d'une expression régulière...
ou plusieurs expression régulière si on prend chaque état comme une entrée alors
peut être 6 expressions régulières...
dans laquelle on passerai le chemin à vérifier...et au final cela dirait oui ou non

un truc dans le genre "D1(D2D1)*D2(D3D2)*D3(D4D3)*D4(D5D4)*D5(D6D5)*D6(D1D6)*D1"
et les 5 autres correspondants...
ici je n'ai pas mis les tirets "-" pour simplifier l'écriture

Qu'en pensez-vous

[Flodelarab]

Bonjour

Il semble que tu considères une boucle quand la voie par laquelle tu rentres n'est pas la même que celle par laquelle tu es sorti.
Ainsi, il suffit de regarder si le successeur du premier est le même que le prédécesseur du dernier.
Le chemin n'a aucune importance.

NB: en plus ton raisonnement est faux car tu ne considères que les hésitations de longueur 2 (et multiples).

[deuzef68]

Bonjour

Il semble que tu considères une boucle quand la voie par laquelle tu rentres n'est pas la même que celle par laquelle tu es sorti.

Bonjour

il ne me semble pas... je me cite "si on prend comme départ D1... une boucle en ressortant en D1"
donc je ressors au même endroit que je suis entré

de plus j'ai cité aussi 2 boucles:
"D1-D2-D3-D4-D5-D6-D1" D1 est au début et à la fin
"D1-D2-D1-D2-D3-D4-D3-D4-D5-D6-D1" D1 est au début et à la fin

Ainsi, il suffit de regarder si le successeur du premier est le même que le prédécesseur du dernier.
Le chemin n'a aucune importance.

oulàlà... je ne vois pas comment dans la boucle D1-D2-D3-D4-D5-D1
le successeur du premier est le même que le prédécesseur du dernier... là faut m'expliquer je ne pige pas

NB: en plus ton raisonnement est faux car tu ne considères que les hésitations de longueur 2 (et multiples).

là c'est toi qui te trompe...le caractère "*" dans une expression régulière je cite (http://www.expreg.com/symbole.php)
Indique 0, 1 ou plusieurs occurrences du caractère ou de la classe précédente

donc dans le bout de l'expression "D1(D2D1)*D2" (je n'ai pas pris tout pour ne pas surcharger)
normalement on peux en "sortir"
si "*" vaut 0 -> D1D2 (le couple D1D2 apparait 1 fois)
si "*" vaut 1 -> D1D2D1D2 (le couple D1D2 apparait 2 fois)
si "*" vaut 2 -> D1D2D1D2D1D2 (le couple D1D2 apparait 3 fois)
si "*" vaut 3 -> D1D2D1D2D1D2D1D2 (le couple D1D2 apparait 4 fois
si "*" vaut n -> D1D2....D1D2 (le couple D1D2 apparait n+1 fois)

est-ce que je me trompe ?

[Flodelarab]

je ressors au même endroit que je suis entré

Je ne te parle pas du point d'entrée/sortie qui est forcément le même mais de la voie pour y accéder.

Ma suggestion est totalement en phase avec la question:
D1-D2-D3-D4-D5-D6-D1 : boucle. D2 différent de D6
D1-D2-D1-D2-D3-D4-D3-D4-D5-D6-D1 : boucle. D2 différent de D6

mais D1-D2-D1-D2-D3-D4-D3-D2-D1 : pas boucle. D2 égale D2

oulàlà... je ne vois pas comment dans la boucle D1-D2-D3-D4-D5-D1 le successeur du premier est le même que le prédécesseur du dernier

D1-D2-D3-D4-D5-D1
Et oui. Justement, il ne l'est pas. C'est donc bien une boucle.

si "*" vaut 0 -> D1D2 (le couple D1D2 apparait 1 fois)
si "*" vaut 1 -> D1D2D1D2 (le couple D1D2 apparait 2 fois)
si "*" vaut 2 -> D1D2D1D2D1D2 (le couple D1D2 apparait 3 fois)
si "*" vaut 3 -> D1D2D1D2D1D2D1D2 (le couple D1D2 apparait 4 fois
si "*" vaut n -> D1D2....D1D2 (le couple D1D2 apparait n+1 fois)

est-ce que je me trompe ?

Ben oui. Encore.
Les hésitations sont de longueurs 0,2,4,6,8 et 2n+2.
Donc c'est bien ce que j'écris. Tu as 2 et ses multiples. Mais pas 3, 5, 7, 11, 13 et leurs multiples.

De toute façon, on s'en moque. Puisque le message principal était de dire que seules la première marche et la dernière sont à observer. Les hésitations paires, impaires, circulaires ou non n'ont aucune importance.

[deuzef68]

Je ne te parle pas du point d'entrée/sortie qui est forcément le même mais de la voie pour y accéder.

Ma suggestion est totalement en phase avec la question:
D1-D2-D3-D4-D5-D6-D1 : boucle. D2 différent de D6
D1-D2-D1-D2-D3-D4-D3-D4-D5-D6-D1 : boucle. D2 différent de D6

mais D1-D2-D1-D2-D3-D4-D3-D2-D1 : pas boucle. D2 égale D2


D1-D2-D3-D4-D5-D1
Et oui. Justement, il ne l'est pas. C'est donc bien une boucle.

bon je comprends mieux ce que tu voulais dire... ce n'était pas clair pour moi

mais c'est toi qui fait une erreur ! je te le prouve par un contre exemple
si tu prends le chemin D1-D2-D1-D6-D5-D4-D3-D2-D1

D2 les 2 fois...mais pourtant c'est bien une boucle !

Ben oui. Encore.
Les hésitations sont de longueurs 0,2,4,6,8 et 2n+2.
Donc c'est bien ce que j'écris. Tu as 2 et ses multiples. Mais pas 3, 5, 7, 11, 13 et leurs multiples.

encore faux... le chemin que je viens de donner
enfin tout dépend ce que tu comptes comme longueur... le nombre de lien entre chaque état ou le nombre d'état
D1-D2-D1-D6-D5-D4-D3-D2-D1
pour moi ça fait 9... pour toi cela fait peut être 8 si tu comptes les liens

[stendhal666]

mais c'est toi qui fait une erreur ! je te le prouve par un contre exemple
si tu prends le chemin D1-D2-D1-D6-D5-D4-D3-D2-D1

D2 les 2 fois...mais pourtant c'est bien une boucle !

Je pense que tu te trompes: le chemin en question contient une boucle mais n'est pas une boucle lui-même: si tu en donnes une représentation graphique:

  |
 / \
 \_/

(dsl pour la qualité) on voit bien que le symbole | n'appartient pas à la boucle.

En revanche sur le rapport entre graphe et expression régulière, il y a du vrai. Les expressions régulières peuvent être implémentées comme des automates qui sont, dans leur nature profonde, des graphes.

[dourouc05]

En revanche sur le rapport entre graphe et expression régulière, il y a du vrai. Les expressions régulières peuvent être implémentées comme des automates qui sont, dans leur nature profonde, des graphes.

Pour être plus précis : des automates finis (et pas à pile ou une machine de Turing — bon, pour être rigoureux, ce sont des généralisations des automates finis). Ce qui implique que tu cherches à reconnaître un langage régulier (https://fr.wikipedia.org/wiki/Langage_rationnel). Bon, par le lemme d'itération (https://fr.wikipedia.org/wiki/Lemme_de_l'%C3%A9toile), ça ne semble pas impossible qu'il le soit (en prenant un chemin, on peut répéter autant de fois une boucle que l'on veut tout en gardant un mot du langage).

Pour atteindre le pragmatisme, je verrais bien un automate (non déterministe) qui lit autant de fois n'importe quel symbole, puis une arête spécifique, n'importe quel symbole un nombre indéfini de fois : s'il relit la même arête, ça fait un cycle. (Pensée DFA, qui peut être transformée en expression régulière après déterminisation.) Il me semble bien que travailler en arêtes est plus bénéfique qu'avec des nœuds directement (inspiré de https://en.wikipedia.org/wiki/Cycle_...ycle_detection).