Discussion :

[PaulNero]

Bonjour,
je travail sur un reseau de noeud de poteau electrique depuis hier.
Un réseau est constitué d'un poste,qui possède des départ (souvent de 1 à 9) chaque depart contient des supports.Un support qui est l'origine de deux ou plus de supports suivant est un noeud.
Mon but est de parcourir ces noeuds et de créer des segments de ligne(noeud-fin de branche ou bien départ-noeud ou encore noeud-noeud).

J'ai ainsi créer ma requête qui me recupère tous les élément du reseau(départ,et support)

voici ce que fait présentement mon code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
ROCEDURE SEGMENT_LIGNE_PRINCIPALE(SAI_numposte)
HLitRecherche(Elément,Elément.Codif_Poste_Support,SAI_numposte)
SI HTrouve(Elément) ALORS
	//on va chercher tous les départs éventuels qui commencent par 1,2,3,4,5,6,7,8,9 et qui n'ont pas de dérivation
	HExécuteRequête(REQ_UnionCodif,hRequêteDéfaut,SAI_numposte,SAI_numposte)
	POUR TOUT REQ_UnionCodif 
		//on part du départ
		SI Gauche(NumériqueVersChaîne(REQ_UnionCodif.EL_codif),1)="1"  ALORS
			SI REQ_UnionCodif.EL_noeud=1 ALORS
				c'est ici que ça bloque!!!
			FIN
		FIN

Le code n'est pas fini, il doit faire les testes pour tous les départs de 1 à 9.
Ma préocupation dans la partie en rouge est que , je voudrai.Une fois un noeud lu,je passe au noeud nuivant,ainsi de suite sans chevauchement.

Cela ressemble à un parcours d'arbre binaire, mais là je sèche un peu.Si quelqu'un a une ideé je suis preneur.

[Nicolas_Jeanneau]

Bonjour,

il va falloir expliquer comment sont articulées tes donnnées : tables, liaisons etc ... car sans ces infos nous aurons du mal à comprendre comment tu as stocké tes lignes.

De plus, pourquoi distingués les supports ayant 1 ou plusieurs supports suivants car ça t'oblige à ajouter un champ pour cela. Si tu as des enfants reporte l'id du parent dans la table des enfants et tu filtres sur cet id.

à bientôt,

Nicolas

[DelphiManiac]

Globalement pour parcourir un arbre, le plus simple reste un appel récursif, du style.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
parcours(racine)
 
function parcours(noeud):
  si noeud.estFinal alors
    retour
  sinon
    parcours(noeud)
  fin

A toi de voir si cette piste te convient et nous dire ce qui ne vas pas, au cas où !

[lazariel]

Le problème c'est qu'un réseau n'est pas un arbre et le parcours récursif ne sera pas alors aussi simple.

Pour parcourir un réseau, voir le parcours en profondeur et le parcours en largeur (dépendant de ce que tu recherches exactement).

Mais effectivement, comment sont articulées tes données ?

[DelphiManiac]

Il ne me semble pas qu'au niveau parcours, le réseau soit plus problématique que l'arbre. Il suffit de marquer les éléments déjà parcouru et dans le cas ou on tombe sur un élément déjà traités on sort (comme dans le cas d'une feuille).

[PaulNero]

Bonjour,
Merci de votre participation à ce poste.
En effet,je vais dans un premier temps essayer de développer l'algorithme et ensuite si ça bloque je vous expliquerais comment mes données sont agencés.Mais je vous le dit d'avance c'est une usine à GAZ.

[lazariel]

Il ne me semble pas qu'au niveau parcours, le réseau soit plus problématique que l'arbre. Il suffit de marquer les éléments déjà parcouru et dans le cas ou on tombe sur un élément déjà traités on sort (comme dans le cas d'une feuille).

En effet, mais vous ne l'avez pas signalé dans le premier post.

Le problème que PaulNero cherche à résoudre est donc la recherche d'un arbre recouvrant (sans poids?) si j'ai bien compris. Vous cherchez bien des segments partant d'un poteau de départ ?

Il existe des algorithmes déjà faits :

Kruskal : http://fr.wikipedia.org/wiki/Algorithme_de_Kruskal
Prim : http://fr.wikipedia.org/wiki/Algorithme_de_Prim (mais là, il faut que le graphe soit connexe ^^)

[Hibernatus34]

(hum... heureusement qu'il faut un graphe connexe, parce que j'imagine mal un algo qui inventerait lui-même des connexions)

PaulNero, si vous savez déjà que c'est une usine à gaz, alors c'est le moment de tout remettre à plat et de simplifier.

Souhaitez-vous lister les tous les chemins possibles allant d'une terminaison à une autre ? L'ACM ne donne pas le chemin optimal pour chaque paire de noeuds, mais un graphe optimal les reliant tous, ce n'est pas du tout pareil.

D'après la question d'origine, que je ne comprends pas très bien (j'ai pas lu le code), j'ai l'impression que vous souhaitez seulement lister des connexions qui sont dans une base de données en éliminant des doublons. Alors il faut vraiment nous dire comment elles sont stockées...

[Nicolas_Jeanneau]

Reste donc à savoir si les lignes sont toutes issues d'un point de départ et bien d'un seul (1 seul père pour le support et 0 ou plusieurs supports fils) ou si elles se recoupent et que 2 lignes peuvent aboutir au même support (1 ou plusieurs pères et 0 ou plusieurs fils). Dans la 2e hypothèse, ça risque en effet d'être plus coton si la base est construite ... comme la tuyauterie d'une usine à Gaz

[PaulNero]

Bonjour,
voici le détail du problème en pièce jointe:
Ceux qui n'ont pas office 2007 pourraient me le faire savoir pour que je transforme en 2003.

voici le début du code que j'ai fait:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
ROCEDURE SEGMENT_LIGNE_PRINCIPALE(SAI_numposte)
montableau est un tableau de chaînes
HLitRecherche(Elément,Elément.Codif_Poste_Support,SAI_numposte) // on cherche si le poste a des supports sur le réseau
SI HTrouve(Elément) ALORS
	//on va chercher tous les départs éventuels qui commencent par 1,2,3,4,5,6,7,8,9 et qui n'ont pas de dérivation
	HExécuteRequête(REQ_UnionCodif,hRequêteDéfaut,SAI_numposte,SAI_numposte)
	POUR TOUT REQ_UnionCodif 
		//on part du départ
		SI Gauche(NumériqueVersChaîne(REQ_UnionCodif.EL_codif),1)="1"  ALORS
			SI REQ_UnionCodif.EL_noeud=1  ALORS
				//on est sur les noeuds de la ligne principale (pas de lettre de dérivation)
				SI Asc(REQ_UnionCodif.EL_codif[[4]])<65 ET Asc(REQ_UnionCodif.EL_codif[[4]])>90 ALORS
					Ajoute(montableau,REQ_UnionCodif)
					Trie(montableau,ttCroissant)
				FIN
				POUR TOUT j DE montableau
					SI Asc(REQ_UnionCodif.EL_codif[[4]])=65 OU Asc(REQ_UnionCodif.EL_codif[[4]])=78
					    SI Gauche(montableau[j],3)=Gauche(REQ_UnionCodif.EL_codif,3) ALORS
					    	//on teste ici si le premier élément de la dérivation est noeud
					    	SI REQ_UnionCodif.EL_codif=1 ALORS
					    		nomfichier_segment_Ligne.élémentDébut=montableau[j]
					    		nomfichier_segment_Ligne.élémentFin=REQ_UnionCodif.EL_codif
					    		HAjoute(nomfichier_segment_Ligne)
					    	//c'est ici que je bloque ..................
					    	FIN
					    FIN
					    	
					    FIN
					 FIN
				FIN
			FIN
				
			
		FIN

Je rappelle juste qu'il n'y apas de notion de direction dans l'arbre.Une fois on est d'un côté, si on dérive, on est toujours de ce côté (voir graphe)

[Nicolas_Jeanneau]

Bonjour,

à la lecture de tes documents, je dirais qu'il n'y a pas de cohérence dans la structure des noms de supports car si on voulait être logique, un support devrait avoir un nom d'autant plus long qu'il est loin en dérivation sur la ligne. Hors ici, on a bien une distinction qui se fait mais seulement sur 2 niveaux !

Je ne vois pas comment tu peux savoir si un support est au niveau 2, 3 ou plus, puisque la lettre n'est pas significative et les numéros non plus .....

Si le support 100Q00 s'appelait N00100, on pourrait retracer le chemin mais là on pourrait considérer que le suppot est directement lié au 100000 et pas au 100N00.

à bientôt,

Nicolas

[PaulNero]

Bonjour Nicolas,
La notion de direction n'a pas de priorité ici.En effet, si tu dérives c'est par rapport uniquement à la ligne principale.
Et il n'est pas possible d'avoir des éléments avec la même codification sur une même branche.
par exemple.100N01, 100N02 et 100N03 indiquent qu'ils sont sur une même branche de ligne et que l'élément 100N00 existe.Cela veut dire aussi que ils ont tous comme "père" l'élement noeud 100000 de la ligne principale.
Si on prend encore 100N01 ,100P01 et 100Q01 montre bien que 100P01 et 100Q01 ont comme père 100N01.Car P et Q suivent N dans l'alphabet.

J'espère t'avoir un peu édifier.

[Hibernatus34]

Bonjour,

J'ai survolé, très rapidement, votre doc et comme Nicolas, ça me perturbe un peu, car d'une part ça semble être un arbre plutôt qu'un graphe, et d'autre part je vois 102A00 qui est "père" de 102B00, 102A01 et 102C00, pas très logique.

Ce qu'il faut nous donner, plutôt qu'un algo qu'on ne lira pas et une doc verbeuse mais incomplète, c'est :
- la structure du fichier ELEMENT
- une explication claire et concise de la notion de "noeud"
- la différence (s'il y en a une) entre la connexion 102A00-102A01 et 102A00-102B00
- si ces identifiants sont suffisants pour connaître leur branche complète (visiblement non, comme le dit Nicolas)
- et surtout un exemple clair et complet : graphe en entrée, résultat complet de la fonction

[Nicolas_Jeanneau]

Bonjour Nicolas,
La notion de direction n'a pas de priorité ici.En effet, si tu dérives c'est par rapport uniquement à la ligne principale.
Et il n'est pas possible d'avoir des éléments avec la même codification sur une même branche.
par exemple.100N01, 100N02 et 100N03 indiquent qu'ils sont sur une même branche de ligne et que l'élément 100N00 existe.Cela veut dire aussi que ils ont tous comme "père" l'élement noeud 100000 de la ligne principale.
Si on prend encore 100N01 ,100P01 et 100Q01 montre bien que 100P01 et 100Q01 ont comme père 100N01.Car P et Q suivent N dans l'alphabet.

J'espère t'avoir un peu édifier.

Je suis à peu près d'accord pour le premier niveau mais comment savoir si on ne se trouve pas déjà au 2e niveau, 3e niveau etc... ?
Prends par exemple ton noeud 102D00 sur ton schéma Noeud réseaux.docx : qu'est ce qui te permet de savoir si ce noeud est rattaché au 102C00 plutôt qu'au 102A00 ?

[PaulNero]

Bonjour,

J'ai survolé, très rapidement, votre doc et comme Nicolas, ça me perturbe un peu, car d'une part ça semble être un arbre plutôt qu'un graphe, et d'autre part je vois 102A00 qui est "père" de 102B00, 102A01 et 102C00, pas très logique.

Ce qu'il faut nous donner, plutôt qu'un algo qu'on ne lira pas et une doc verbeuse mais incomplète, c'est :
- la structure du fichier ELEMENT
- une explication claire et concise de la notion de "noeud"
- la différence (s'il y en a une) entre la connexion 102A00-102A01 et 102A00-102B00
- si ces identifiants sont suffisants pour connaître leur branche complète (visiblement non, comme le dit Nicolas)
- et surtout un exemple clair et complet : graphe en entrée, résultat complet de la fonction

La structure du fichier élément va encore compliqué beaucoup l'équation.J'ai reussi a trié tous les éléments et à bien notifier la situation de chaque élément dans la requête (noeud ou pas noeud).La requête existe elle est là dans le début du code que j'ai posté.

un noeud est définit comme ceci: quand un support a au moins deux fils.
connexion 102A00-102A01 et 102A00-102B00
102A00-102A01 veut dire que ces deux éléments sont sur un même segment
102A00-102B00 veut dire que 102B00 est un fils de 102A00

L'exemple que j'ai posté (graph) est pour moi le plus clair que je puisse vous donner.En effet, si vous constatez, dans mon code j'ai pris comme "racine" chaque noeud de la ligne principale.J'ai fait abstraction du début du départ pour éviter les lourdeurs.
Ainsi, j'ai dévéloppé une autre procédure qui me recupère bien les élément de la ligne principale avec lesquels je crée mes segments sur cette ligne.

J'espère t'avoir édifié.
Je continue mon implémentation dès que j'aurais quelque chose je posterai.

[PaulNero]

Je suis à peu près d'accord pour le premier niveau mais comment savoir si on ne se trouve pas déjà au 2e niveau, 3e niveau etc... ?
Prends par exemple ton noeud 102D00 sur ton schéma Noeud réseaux.docx : qu'est ce qui te permet de savoir si ce noeud est rattaché au 102C00 plutôt qu'au 102A00 ?

102D00 n'est pas un noeud car il n'a pas au moins deux fils.Si tu as 102A00 et 102C00 il est clair que 102B00 existe et donc que 102C00 et 102B00 sont des fils de 102A00 car les deux derniers caractères 00 sont identiques.

Jette aussi un coup d'oeil sur la réponse que j'ai envoyé à d'hibernatus34

[Hibernatus34]

La structure du fichier élément va encore compliqué beaucoup l'équation.

C'est la donnée d'entrée (si j'ai bien compris), on ne peut donc pas s'en passer et elle ne compliquera rien, elle permettra juste de commencer à réfléchir sérieusement.

un noeud est définit comme ceci: quand un support a au moins deux fils.

Donc si un noeud n'a qu'un fils, ce n'est plus appelé un fils, mais un segment qui part de ce noeud et on ne change plus de lettre. C'est ça ?

connexion 102A00-102A01 et 102A00-102B00
102A00-102A01 veut dire que ces deux éléments sont sur un même segment
102A00-102B00 veut dire que 102B00 est un fils de 102A00

OK, et donc 100P00-100P02 est un segment, mais pas 100N00-100P01 ? (ça aurait été bien de mettre 100P02 dans l'exemple)

L'exemple que j'ai posté (graph) est pour moi le plus clair que je puisse vous donner.En effet, si vous constatez, dans mon code j'ai...

Je ne lis pas le code, je veux savoir quelles données sont en entrée quelles données on veut en sortie, c'est tout. Si le code peut servir de référence alors vous n'avez plus besoin d'aide.
L'exemple liste des segments dont on ne peut déduire aucune règle logique, notamment parce que c'est incomplet. Un exemple plus simple et complet serait plus clair. Mais à priori on dirait une liste des couples noeud-feuille et noeud-noeud. ("noeud" dans le sens que vous donnez)

[PaulNero]

C'est la donnée d'entrée (si j'ai bien compris), on ne peut donc pas s'en passer et elle ne compliquera rien, elle permettra juste de commencer à réfléchir sérieusement.?

Ok, on va refléchir très sérieusement:
le fichier est de la forme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
num_enr      élément    élément_prec  situation    poste
1            100E02      100E01             0      3100004
2            100000      100N01             1      3100004

La situation c'est par à l'élément.
Dans ma requete j'ai selectionné les élements avec leur situation avec la condition du poste.

Donc si un noeud n'a qu'un fils, ce n'est plus appelé un fils, mais un segment qui part de ce noeud et on ne change plus de lettre. C'est ça ?

oui bien compris!!

OK, et donc 100P00-100P02 est un segment, mais pas 100N00-100P01 ? (ça aurait été bien de mettre 100P02 dans l'exemple)

malheureusement,100N00-100P01 est aussi un segment car visiblement 100P01 est en fin de ligne.

Mais à priori on dirait une liste des couples noeud-feuille et noeud-noeud. ("noeud" dans le sens que vous donnez)

En effet, bien vu!!

[Hibernatus34]

On continuera demain parce que moi je termine à 17h
Mais j'ai encore une question : "situation" c'est le fameux flag "noeud" ou bien c'est votre requête qui le crée ? Sinon c'est quoi la situation ?

Ca paraît très simple, chaque noeud est défini par son identifiant et celui de son père. C'est un arbre tout bête.

Hmm, dernière question : veut-on un ensemble de segments minimal sans aucun recouvrement ?
Si j'ai 100000-102000 et 10200-10400, est-ce que je vais quand même lister 100000-104000 ?
Et donc le critère de découpe, c'est quand je rencontre un noeud (2+ fils) ou une feuille je m'arrête.

A demain.

[PaulNero]

Mais j'ai encore une question : "situation" c'est le fameux flag "noeud" ou bien c'est votre requête qui le crée ? Sinon c'est quoi la situation ?

oui en effet,c'est le fameux flag noeud (=0 si élément pas noeud,=1 si noeud)

Ca paraît très simple, chaque noeud est défini par son identifiant et celui de son père. C'est un arbre tout bête.

Oui moi aussi j'ai vu comme cela,mais quand je suis resté bloqué,je m'en suis ressaisi pour solliciter de l'aide.

Hmm, dernière question : veut-on un ensemble de segments minimal sans aucun recouvrement ?

Je pense qu'on veut un ensemble de segment existant possible.Je rappelle qu'un segment a un élément de début et un élément de fin dans le fichier segment de ligne qu'on va populler.

Si j'ai 100000-102000 et 10200-10400, est-ce que je vais quand même lister 100000-104000 ?

Cette question démontre bien que vous avez saisie le problème!!En effet ils doivent aussi être listé.

Et donc le critère de découpe, c'est quand je rencontre un noeud (2+ fils) ou une feuille je m'arrête.

En effet,mais regarde bien le schéma,dès qu'il y a dérivation, c'est que sur la ligne (segment de ligne en fait) où il y a le noeud, il y a forcément un ou plusieurs autre éléments.

Je joins le document un peu modifié selon certaines informations eues hier soir.
La modification est que: quand on part du noeud 100000 à 100N00 ,il fallait plutot écrire 100N01 (pas bien grave pour la compréhension).Et 102000-102A00 est plutot 102000-102A01

d'où le nouveau graphe.