Discussion :

[ludovic.fernandez]

Salut a Tous,

Petite question toute bete:

Je cherche a construire un arbre a partir d'une table de relations xRy non ordonnees et possedant certaines cyclicites de type xRy et yRx que je peux simplifier en :

- Si xRy et yRx alors xRy.

Ce qui implique aussi dans mon cas :

- Si xRy et yRz et zRx alors xRy et yRz.

(EDIT) Le probleme vient aussi du fait que le chemin le plus long l'emporte; par exemple:

- Si xRy et xRz et yRz alors xRy et yRz

Comment batir cet arbre de facon optimisee ?
Le contexte pour les curieux est l'affichage relationnel de certains contrats bancaires.

Merci par avance,
Ludovic

[FrancisSourd]

- Si xRy et yRx alors xRy.

Je ne comprends pas bien. D'un poin de vue mathématique, c'est une tautologie.

Est-ce une règle de simplification du graphe qui voudrait dire que tu enlèves l'arc yRx? Et donc que dans ton graphe, tu casses chaque cycle rencontré jusqu'à obtenir un arbre. Dans un tel cas, ne suffit-il pas de parcourir ton graphe en appliquant la règle "Si tu rencontres un arc retour (qui ferme un cycle), tu le supprimes."

[Pragmateek]

- Si xRy et yRx alors xRy.

N'est-ce pas plutôt:
-Si xRy et yRx alors x=y.
?
Ce qui définie une relation antisymétrique.

[ludovic.fernandez]

Je ne comprends pas bien. D'un poin de vue mathématique, c'est une tautologie.

Est-ce une règle de simplification du graphe qui voudrait dire que tu enlèves l'arc yRx? Et donc que dans ton graphe, tu casses chaque cycle rencontré jusqu'à obtenir un arbre. Dans un tel cas, ne suffit-il pas de parcourir ton graphe en appliquant la règle "Si tu rencontres un arc retour (qui ferme un cycle), tu le supprimes."

Les maths sont un peu loin pour moi mais en effet ce sont plusieurs regles qui cassent chaque cycle recontre. Comment les exprimeriez-vous? Pour rappel, qu'est-ce qu'une tautologie va poser comme probleme ; c'est toujours vrai c'est tout ?

Bref, pour l'algo, si je suis tes suggestions, je compare chaque nouvelle entree avec l'arbre en cours de construction ~ complexite en o(n!) ? ou suis-je completement a l'ouest?

Ludo

[FrancisSourd]

Les maths sont un peu loin pour moi mais en effet ce sont plusieurs regles qui cassent chaque cycle recontre. Comment les exprimeriez-vous? Pour rappel, qu'est-ce qu'une tautologie va poser comme probleme ; c'est toujours vrai c'est tout ?

Une tautologie, c'est effectivement quelque chose qui est toujours vrai et qui, en qq sorte, n'apporte rien, comme dire "Si X est Grand et beau alors X est grand".

Bref, pour l'algo, si je suis tes suggestions, je compare chaque nouvelle entree avec l'arbre en cours de construction ~ complexite en o(n!) ? ou suis-je completement a l'ouest?
Ludo

En fait, je n'ai toujours pas bien identifié le problème de graphe sous-jacent. C'est lié aux fermetures transitives et aux composantes fortement connexes. Mais j'ai un peu peur que ton problème ne soit pas assez formalisé pour avoir une réponse unique.

Que veux tu obtenir si tu as:
aRb
bRc
aRe
dRe
dRc

[ludovic.fernandez]

Oui, tu as tout a fait raison : le probleme vient du fait que j'ai tente de modeliser l'experience sans approche organisee.

Par consequent, on pourrait poser la question ainsi : en cas de cyclicite dans un graphe et afin de batir un arbre, existe t-il des approches connues ou encore, suffit-il de recourir a l'emploi de tautologies pour supprimer ces dernieres (ou supprimer l'arc retour selon certaines priorites etablies par avance)?

Ludovic

[FrancisSourd]

Il faut avant tout savoir si tu veux modéliser ton problème comme avec des arcs orientés (x->y) ou non orientés (x--y)

D'après ce que j'ai compris, l'orientation compte. Je me place donc dans ce cas.

• Je construirerai le graphe où les arcs x->y correspondent aux xRy.
• Je chercherai les composantes fortements connexes de ce graphe. Cela me donne un graphe réduit.
• Ensuite, je prends une arborescence couvrante de ce graphe réduit que j'obtiens par un parcours.

J'ai mis volontairement des mots-clés assez traditionnels de la théorie des graphes. En recherchant ces termes dans un bouquin de graphe ou sur internet, cela devrait te donner des idées et te permettre de voir si cela suffit pour representer tes relations.

Le tout est bien sûr de condenser la représentation de l'information... sans en perdre (trop?) Pour analyser ton problème, il faudrait définir quelles sont les relations qui peuvent être omises sans dégrader la connaissance du système global de relations.

[ludovic.fernandez]

Merci pour ces informations/rappels que je vais pouvoir mettre a profit immediatement. Au sujet de la perte d'informations, il existe des
"mock-ups" a ce sujet; donc pas de soucis.

Le travail m'attend.

Ludo