mumuse avec dijkstra - Page 1

huhu je viens de coder dijkstra sur le réseau de la RATP que nous connaissons et ça me sort des trucs amusants :

avec: http://www.unsads.com/~squalyl/pics/dijkstra/metro.png

[squalyl@dedibox dijkstra]$ ./dijkstra graphe.txt 42 80
total: 86 stations
total: 269 links
Start : #42 (Montparnasse Bienvenue)
End   : #80 (Olympiades)
Station: 0      (42) Montparnasse Bienvenue
Station: 4      (46) Odeon
Station: 7      (54) Chatelet-Les Halles
Station: 8      (81) Gare de Lyon
Station: 9      (78) Bercy
Station: 11     (79) Bibliotheque Francois Mitterand
Station: 12     (80) Olympiades
[squalyl@dedibox dijkstra]$

va falloir prendre en compte les temps... En nb de stations il a raison (on en gagne 2) mais c'est pas vachement pratique quand même...

(quoi... sisi j'ai codé la ligne 6 )

tu pourrais aussi prendre en compte les correspondances (i.e. ne pas avoir 1 station = un seul noeud dans le graphe, mais avoir un noeud pour chacune des lignes qui ont une correspondance à cette station ^^)

c'est prévu pour la version 3 et ça évitera de passer par châtelet à chaque fois à cause de la ligne 14

là j'ajoute TOUTES les stations () j'en ai pour la nuit!

tu sais que le site de la ratp propose la même chose ?

ouais, et c'est compatible pour n'importe quelle ville en changeant de fichier XML?

(et puis d'abord je programme ce que je veux )
(et puis à la base c'était juste pour tester mon algo, mais je trouve marrant alors je pousse un peu )

Hum ça serait marrant de tester dijkstra sur Toulouse

Bin le format est simple

Si tu veux tester (les correspondances ça suffit)

1 ligne avec le num de station

N lignes avec numéro TAB nom

Puis autant de lignes que tu veux avec debut TAB fin TAB poids

(poids: nb de stations entre les correspondances, distance a vol d'oiseau, ce que tu veux...)

https://anon:anon@svn.unsads.com/squalyl/dijkstra/algotest/https://anon:anon@svn.unsads.com/squalyl/dijkstra/algotest/
https://anon:anon@svn.unsads.com/squalyl/dijkstra/algotest/graphe.txthttps://anon:anon@svn.unsads.com/squalyl/dijkstra/algotest/graphe.txt

Tiens squalyl si ce genre de truc t'amuse tu peux regarder les divers graphes qui sont là-dedans : http://recherche.ign.fr/labos/cogit/pdf/THESES/GLEYZE/These_Gleyze_2002.zip

Si tu veux plus de donnees, un prof a fait ca:
http://www.di.ens.fr/~granboul/enseignement/mmfai/algo2002-2003/tp7/

Neuroo > C'est exactement ce que j'ai fait

Là j'ai fini de saisir les stations et de les numéroter (1-299 ), j'ai plus qu'à saisir les segments de ligne et les coordonnées des stations sur mon plan

J'envisage d'en faire un outil pratique, avec des fonctions qui seront plutot cools

un jour, je me promènerai dans toutes les lignes pour mesurer les temps de trajet

Sally> 122 Mo ton truc j'espère que c'est intéressant

tu sais que sur le lien de neuroo il y a déjà une version avec les coordonnées de toutes les stations et tout ? (enfin pas tout à fait, y a pas Olympiades évidemment )

squalyl > ah j'ai pas regardé la taille, je sais pas comment il a fait pour que ce soit aussi énorme
en fait le ppt de sa soutenance suffirait pour avoir la plupart des jolis diagrammes a priori, mais je sais pas où le trouver

./6: Avec ou sans les bus ? #ange#

Hmm intéressante cette thèse y'a plein de résultats d'algos intéressants, sur Delaunay, les PCC dans un diagramme de Delaunay, des calculs sur les polygones... je garde, ça peut servir

Pollux > Oui... Mais je vais passer plus de temps à transformer son format perso en XML alors que là, je le fais direct, et sur un plan de 3000x3000, et à y être j'y mets les tram et les RER

PpHd > sans bus à toulouse (ou grenoble) ça sert pas à grand chose

squalyl (./14) :
Pollux > Oui... Mais je vais passer plus de temps à transformer son format perso en XML

tu dois taper sacrément vite pour taper 300 stations avec leurs coordonnées plus vite que tu n'écrirais un script perl de 2-3 lignes

ne m'embête pas en me prouvant que je perds du temps.

D'une part je ne maitrise pas le perl, et n'ai pas envie de m'y plonger

D'autre part je suis en stage et je fais des compilations de plusieurs dizaines de minutes, donc j'ai du temps.

Et en plus j'utilise ma propre version de plan qui n'est pas forcément celle de l'auteur. Une dilatation des coordonnées données n'apporte rien à la précision de la chose.

Accepte la situation telle qu'elle est, ne perds pas de temps, je ne changerai pas pour te faire plaisir.

Passons à d'autres discussions, ce sera plus intéressant.

ouh là, du calme

tu fais ce que tu veux, je m'en fous, je répondais juste à ton affirmation que ça aurait pris plus de temps à convertir qu'à retaper ^^

pour moi, oui, vu que je sais pas comment faire vite ^^

bref

bah même en C ça devrait pas prendre plus de dix minutes à coder de toute façon ^^

mais comme tu dis, bref

quand mon fichier XML sera terminé, tu me diras comment j'aurais pu l'obtenir à partir du truc donné

squalyl (./10) :
un jour, je me promènerai dans toutes les lignes pour mesurer les temps de trajet

Dans la même journée, c'est possible : Le Défi Métro !
(encore un type de l'ENS ; c'est fou ce qu'ils sont populaires)

Sinon, personnellement, pour ta conversion, je ferais un script sed
(petit outil assez rapide à apprendre et à maîtriser).

bon vous commencez à me les casser avec vos conversions.

https://anon:anon@svn.unsads.com/squalyl/dijkstra/withxml/paris.xml

faites moi ça en sed avec les coordonnées basées sur:

https://anon:anon@svn.unsads.com/squalyl/dijkstra/withxml/plan.png

les deux liens sont dead

mon

fais un s/anon:anon@// et utilise la boite d'auth

le certoche est signé par moi.

squalyl (./22) :
bon vous commencez à me les casser avec vos conversions.

Ce ne sont que des suggestions ; tu fais comme tu veux, hein...

faites moi ça en sed avec les coordonnées

Un bouzin de ce genre pourrait marcher (à partir de 'metro+.plan') :
s/\([^:]*\):[^:]*:\([^:]*\):\([0-9]*\):\([0-9]*\):[*0-9.]*:[0-9.]*/<station ligne="\1" x="\3" y="\4">\2<\/station>/
Bon, évidemment, ça n'ajoute pas automagiquement les « numéros de station ».

> Bon, évidemment, ça n'ajoute pas automagiquement les « numéros de station ».
Quitte à rajouter une chaîne de caractères pour pouvoir déclencher une règle de match, je pense que c'est faisable avec un script awk qui passe après le script sed (clause begin + ajout de print du numéro courant dans la règle de match), ou en awk pur (?).

Et Perl est, sauf exception - features assez obscures de awk, par exemple - un sur-ensemble de bash, awk et sed.

mais c'est PAS LES MEMES COORDONNEES!

Lionel Debroux (./26) :
Et Perl est, sauf exception - features assez obscures de awk, par exemple - un sur-ensemble de bash, awk et sed.

Oui, bien sûr. De toute façon, sed est déjà Turing-complet...
L'important, c'est de voir avec quel outil tu sera le plus productif - en ce qui me concerne, j'ai abandonné Perl il y a quelques années.

squalyl (./27) :
mais c'est PAS LES MEMES COORDONNEES!

Ah, d'accord. Pour régler ça, il ne suffit pas de redimensionner l'image ?