Le blog de Jean David TECHER, un Réunionnais à Saint-Priest/Lyon

Aller au contenu | Aller au menu | Aller à la recherche


< 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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 >

jeudi 26 avril 2007

Livre "PostgreSQL, Second Edition" - URL pour les exemples du livres

Pour ceux qui comme moi auraient le bouquin suivant


. PostgreSQL, Second Edition.

Je tiens à signaler que les exemples sont disponibles à l'adresse http://www.conjectrix.com/pgbook/index.html. Plus sobrement, on peut aussi télécharger les exemples compressés en faisant

wget http://www.conjectrix.com/pgbook/source2/bookdata.tar.gz

Il y a aussi ce lien qui est intéressant http://book.itzero.com/read/others/0508/Sams.PostgreSQL.2nd.Edition.Jul.2005_html/

J'avoue que

  • c'est un gros pavé de plus de 1000 pages ;
  • qu'il est écrit en anglais ;
  • qu'il est basé sur la 8.0 de PostgreSQL qui date un peu
  • ....

Mais pour un quelqu'un qui veut voir l'utilisation de la programmation, je trouve qu'il est bien fait: PHP, Python, C, C++, Java, connexion ODBC, Visual C++, Perl etc...Comme on dit généralement en été, il y a la mode pour certains bouquins - romans policiers, magazines spécialisés etc... -.

Eh bien pour les programmeurs et administrateurs

  • ce serait un bon bouquin pour l'été à lire sur la plage en sirotant un bon sirop;
  • Un bon pavé de + de 1000 pages très intéressant;
  • Un autre plus est dans le chapitre 25, un petit tour d'horizon bien fait XML et sur sur tsearch (même si celà n'est pas adapté à la 8.1 ou la 8.2);
  • des exemples bien faits, des chapitres sur libpgeasy, libpq++ notamment;
  • plutôt pour un public averti déjà familier avec PostgreSQL, n'ayant pas peur de l'anglais (ça fait des révisions).

Chez la librairie Sauramps (à Montpellier), je l'ai payé 44.95€ mais je ne regrette pas mon investissement. Il y a certains outils dont j'ai eu du mal à trouver une meilleur documentation en fonction du peu d'exemples trouvés ça et là sur internet.

Libpgeasy - une C-API pour PostgreSQL bien sympathique -, un exemple d'utilisation en langage C pour la fonctionnalité TSP de PgRouting.

Libpgeasy est une C-API pour PostgreSQL bien sympathique. Je vais l'utiliser ici dans le cadre de mon précédent billet. En fait pour tout dire, ce billet vient donc à la suite du précédent. Ce sera pour moi aussi le moment de faire quelques révisions en C. Mon code fourni ici est pas nécessairement optimisé! Alors reprenons le fil de nos investigations.

N.B: coder la dernière partie de mon précédent billet en PHP est facilement réalisable. C'est ici pour moi l'occasion surtout d'utiliser une C-API de PostgreSQL assez basique pour mon apprentissage personnel.

Nous avons pour le moment la requête suivante

routing=# SELECT  * from tsp('select  distinct source as source_id, x1::double precision as x, y1::double precision as y from 
troncon_route_edges where source in (43,30,18,41,1,13)','43,30,18,41,1,13',41);
 vertex_id |  edge_id  |         cost
-----------+-----------+-----------------------
        41 | 138321080 |                     0
        30 |         0 | 2.12199579047121e-314
         1 |         8 | 6.84394238386657e-316
        18 |        16 | 2.12199611507234e-314
        13 | 138523056 | 6.79720117142741e-313
        43 |       406 | 1.23516411460312e-322
(6 lignes)
Mon but ici est de récupérer les couples (41,30), (30,1),(1,18) que j'aimerais appliquer à la suite à la fonctionnalité shortest_path_astar() de pgrouting. Autrement dit si j'ai au préalable une table aller
CREATE TABLE aller(gid int4) WITH oids;

SELECT AddGeometryColumn( 'aller', 'the_geom', -1, 'MULTILINESTRING', 2 );
dans laquelle je souhaiterais stocker les diverses portions de chemins renvoyés par les couples (source,target) - (41,30),(30,1) - pour shortest_path_astar() en faisant
INSERT INTO aller(the_geom) 
  (
   SELECT the_geom FROM troncon_route_edges  WHERE edge_id IN
     (SELECT edge_id FROM shortest_path_astar('SELECT  id,source,target,cost,
      reverse_cost, x1,y1,x2,y2 FROM troncon_route_edges',????,???,false,true)
     )
  );
où "????,???" vaudra "41,30" puis "30,1" etc...
Installation de libpgeasy
Rien de compliqué pour l'installation. Chez moi, PostgreSQL est installé à /opt/pgsql et c'est la version 8.2.3 que j'utilise. Conformément à la documentation, on fera tout simplement
wget ftp://gborg.postgresql.org/pub/pgeasy/stable/libpgeasy-3.0.4.tar.gz
tar xvzf libpgeasy-3.0.4.tar.gz
cd libpgeasy-3.0.4
export PATH=/opt/pgsql/bin:$PATH
export CPPFLAGS=-I$(pg_config --includedir)
export LDFLAGS=-L$(pg_config --libdir)
./configure --prefix=/opt/pgsql
make
make install
ldconfig
Le programme calcul_trajet.c
Mon code est le suivant
/* calcul_trajet.c */
#include <stdlib.h>
#include <stdio.h>
#include <libpq-fe.h>
#include <libpgeasy.h>

int main(int argc, char * argv[])
{
   char vertex_id[2];
   int VertexIndice=0; int Nb_vertex=0,i;
   char vertex[53][2];
   for(i=0;i<=2;i++)
{   for(VertexIndice=0;VertexIndice<=53;VertexIndice++)
   {
       vertex[VertexIndice][i]=' ';//printf("%d\n",vertex[VertexIndice]);
   }
}
   char query[600]="SELECT  vertex_id::int from tsp('select  distinct source as source_id\
, x1::double precision as x, y1::double precision as y from \
troncon_route_edges where source in (";
 char	query2[800]="INSERT INTO aller(the_geom) SELECT the_geom FROM troncon_route_edges\
  WHERE edge_id IN (SELECT edge_id FROM shortest_path_astar('SELECT  id,source,target,cost,reverse_cost,\
 x1,y1,x2,y2 FROM troncon_route_edges',";
   PGconn * connexion;		
   if (argc != 4)
		halt("Usage:  %s \"dbname=XXX user=XXX host=XXX\" \"liste de points\" startpoint\n\
  Exemple %s \"dbname=routing user=postgres\" \"43,30,18,41,1\" 30\n", argv[0],argv[0]);
   connexion = connectdb( argv[1] ? argv[1]:"");
   on_error_stop();
   strcat(query,argv[2]);
   strcat(query,")','");
   strcat(query,argv[2]);
   strcat(query,"',");
   strcat(query,argv[3]);
   strcat(query,")");
   doquery(query);
   printf("-- REQUETE %s",query);VertexIndice=0;
   while( fetch(vertex_id)!=END_OF_TUPLES)
   {
     printf("-- noeud = %c%c%c\n",vertex_id[0],vertex_id[1],vertex_id[2]);
     vertex[VertexIndice][0]=vertex_id[0];
     vertex[VertexIndice][1]=vertex_id[1];
     vertex[VertexIndice][2]=vertex_id[2];
     VertexIndice++;Nb_vertex++;
   }
 for(VertexIndice=1;VertexIndice<Nb_vertex;VertexIndice++)
   { 
;    char a[2]={vertex[VertexIndice][0],vertex[VertexIndice][1]};
     char b[2]={vertex[VertexIndice-1][0],vertex[VertexIndice-1][1]};
     char c[10]={'0','1','2','3','4','5','6','7','8','9'};
     int test_a=0,test_b=0;

     for(i=0;i<10;i++)
     {if (c[i]==a[1]) test_a=1;if (c[i]==b[1]) test_b=1;}
      if ((test_a==1)&&(test_b==1))
       printf("%s %c%c,%c%c,false,true));\n",query2,b[0],b[1],a[0],a[1]);
      if ((test_a==0)&&(test_b==0))
       printf("%s %c,%c,false,true));\n",query2,b[0],a[0]);
      if ((test_a==1)&&(test_b==0))
       printf("%s %c,%c%c,false,true));\n",query2,b[0],a[0],a[1]);
      if ((test_a==0)&&(test_b==1))
       printf("%s %c%c,%c,false,true));\n",query2,b[0],b[1],a[0]);

   }
 disconnectdb();
 return 0;

}
Un petit Makefile pour la route
On pourra par exemple utiliser le Makefile suivant
POSTGRES_HOME=/opt/pgsql

CFLAGS= -O
TARGET = calcul_trajet

all : $(TARGET)

%: %.c
	gcc $(CFLAGS) -I$(POSTGRES_HOME)/include -o $@ $@.c -L$(POSTGRES_HOME)/lib -lpgeasy

clean:
	rm -f $(TARGET)
Pour compiler le programme, on fera tout simplement
make
Utilisation
Un simple ./calcul_trajet me donne un descriptif succinct de son utilisation
root@bremko:/mnt/sources/tmp# ./calcul_trajet
Usage:  ./calcul_trajet "dbname=XXX user=XXX host=XXX" "liste de points" startpoint
  Exemple ./calcul_trajet "dbname=routing user=postgres" "43,30,18,41,1" 30
Je n'aurais donc qu'à faire pour peupler ma table aller
./calcul_trajet "dbname=routing user=postgres host=localhost" "43,30,18,41,1,13" 41 | psql -U postgres -d routing
Si on enlève la commande " | psql -U postgres -d routing", on a alors la sortie suivante dans le terminal
./calcul_trajet "dbname=routing user=postgres host=localhost" "43,30,18,41,1,13" 41
-- REQUETE SELECT  vertex_id::int from tsp('select  distinct source as source_id,
 x1::double precision as x, y1::double precision as y from troncon_route_edges 
where source in (43,30,18,41,1,13)','43,30,18,41,1,13',41)
-- noeud = 41
-- noeud = 30
-- noeud = 1
-- noeud = 18
-- noeud = 13
-- noeud = 43
INSERT INTO aller(the_geom) SELECT the_geom FROM troncon_route_edges  WHERE edge_id 
IN (SELECT edge_id FROM shortest_path_astar('SELECT  id,source,target,cost,reverse_cost, 
x1,y1,x2,y2 FROM troncon_route_edges', 41,30,false,true));
INSERT INTO aller(the_geom) SELECT the_geom FROM troncon_route_edges  WHERE edge_id 
IN (SELECT edge_id FROM shortest_path_astar('SELECT  id,source,target,cost,reverse_cost, 
x1,y1,x2,y2 FROM troncon_route_edges', 30,1,false,true));
INSERT INTO aller(the_geom) SELECT the_geom FROM troncon_route_edges  WHERE edge_id 
IN (SELECT edge_id FROM shortest_path_astar('SELECT  id,source,target,cost,reverse_cost, 
x1,y1,x2,y2 FROM troncon_route_edges', 1,18,false,true));
INSERT INTO aller(the_geom) SELECT the_geom FROM troncon_route_edges  WHERE edge_id 
IN (SELECT edge_id FROM shortest_path_astar('SELECT  id,source,target,cost,reverse_cost, 
x1,y1,x2,y2 FROM troncon_route_edges', 18,13,false,true));
INSERT INTO aller(the_geom) SELECT the_geom FROM troncon_route_edges  WHERE edge_id
 IN (SELECT edge_id FROM shortest_path_astar('SELECT  id,source,target,cost,reverse_cost,
 x1,y1,x2,y2 FROM troncon_route_edges', 13,43,false,true));
Ce qui se traduira donc - comme déjà attendu dans le bille précédent - par le schéma suivant pour la table aller

Parcours à effectuer dans l'ordre 41,30,1,18,13,43 en partant du noeud 41.

mercredi 25 avril 2007

PgRouting: Nouvelle version 1.0.0.a et utilisation de la fonctionnalité TSP

Nouvelle version 1.0.0a

Anton A. Patrushev annonçait aujourd'hui que la version 1.0.0a de PgRouting était disponible sur le site http://www.postlbs.org/. Je l'ai compilé aujourd'hui, pas de problème particulier sous Ubuntu Dapper.

fonction TSP

Dans ma doc pour le moment, je m'étais arrêté à l'utilisation de la fonctionnalité shortest_path_astar() - qui utilise l'algorythme A* -. Ce soir, j'ai essayé la fonctionnalité tsp(). TSP signifie Traveling Salesman Problem, désignant ainsi le problème du voyageur du commerce. Pour une définition plus profane, il s'agit du problème du père Noël, ou de l'agent commercial qui doit visiter des clients dans un trajet professionnel en essayant d'optimiser son parcours - un peu de théorie des graphes, celà ne fait pas de mal que les puristes de la discipline m'excusent -.

Exemple
Pour rappel dans ma doc, j'ai le graphe avec les noeuds

Fig 1. Noeuds de mon graphe.
Supposons que je veuille trouver le chemin de longueur totale minimale passant par les noeuds 43,30,18,41,1,13. Mon point de départ sera le noeud 41.

Fig 2. Noeuds par lesquels je souhaite passer en commençant par le noeud 41.
La requête sera tout simplement
routing=# SELECT  * from tsp('select  distinct source as source_id, x1::double precision as x, y1::double precision as y from 
troncon_route_edges where source in (43,30,18,41,1,13)','43,30,18,41,1,13',41);
 vertex_id |  edge_id  |         cost
-----------+-----------+-----------------------
        41 | 138321080 |                     0
        30 |         0 | 2.12199579047121e-314
         1 |         8 | 6.84394238386657e-316
        18 |        16 | 2.12199611507234e-314
        13 | 138523056 | 6.79720117142741e-313
        43 |       406 | 1.23516411460312e-322
(6 lignes)
Les colonnes edge_id et cost n'ont pas d'importance. Seul compte la colonne vertex_id. Selon l'ordre énuméré des valeurs des lignes de la colonne de vertex_id, il me faudra donc pour optimiser mon parcours aller de 41 à 30, puis de 30 à 1, puis de 1 à 18, de 18 à 13 et de 13 à 43. Pour la suite, pour trouver le parcours finale, il suffira par exemple d'appliquer de proche en proche la fonction shortest_path_astar() sur les couples (source,target) avec dans l'ordre d'énumération (41,30), puis (30,1), puis (1,18) etc...

Et on obtiendra par exemple le parcours suivant


Fig 3. Parcours à effectuer dans l'ordre 41,30,1,18,13,43 en partant du noeud 41.
Je m'excuse si l'exemple n'est pas des + convaincants mais c'est juste pour le fun .

TODO: A ajouter dans la doc

mardi 24 avril 2007

Journées du Libre à Montpellier - ALL - 14 au 16 juin 2007

La news n'est pas nouvelle mais je me permets quand même de la faire apparaître sur mon blog. Comme chaque année ALL - Association pour le Logiciel Libre - organise la 6ème édition des Journées du Logiciel Libre à Montpellier. Répartie sur 3 journées, elle se décline sur 3 journées dédiée chacune à un public et un thème différent:

  1. Jeudi 14 : journée collectivités - le poste de travail libre;
  2. Vendredi 15 : journée entreprises - enjeux, migration et sécurité;
  3. Samedi 16 : journée grand public - citoyenneté, éducation et jeux.

Je me souviens quand 2005, j'avais tenu un stand avec Gérald. On a reçu des contacts très intéressants cette année-là. Un des liens possibles à consulter est http://www.all.asso.fr/Realisations/2007/jlm07/