Tuesday, October 31, 2006

Halloween 2006



Maya ma grande princesse
Anael mon grand fils
Nyssia ma petite princess
Il commence à faire froid en Vendée, mais tout le monde est heureux ;-)

Friday, April 14, 2006

Ecran Urbain Multimedia

Depuis debut 2005:
issus du concept "Citizencom", développé par la société Dauphin – Adshel (Clear Channel) pour répondre aux besoins de communications spécifiques des grandes villes, les mobiliers sont opérationnels depuis ce premier semestre 2005.

http://www.nantes.fr/mairie/art_255.asp

Friday, March 31, 2006

Open Gateway for Geospatial Data

Basic C implementation of DSATUR (Brelaz, 1979)

/*
Parcours en profondeur
Colororation
Philippe Rolland Balzon
prolland at free dot fr
01/2006
*/

//////////////////////////////////////
// INCLUDE & DEFINE
//////////////////////////////////////
#include
#include
#define ORDER_MAX 30


//////////////////////////////////////
// STRUCTURE
//////////////////////////////////////
typedef struct t_graphe Type_G;
struct t_graphe {
int order;
int matrice[ORDER_MAX][ORDER_MAX];
};

int dsat[ORDER_MAX];
int degre[ORDER_MAX];
int coloration_issu_de_dsat[ORDER_MAX];

//////////////////////////////////////
// INIT
//////////////////////////////////////

Type_G init(Type_G g){
int i,j;
for(i=1;i<= g.order;i++){
for(j=1;j<= g.order;j++){
g.matrice[i][j]=0;
}
}
return (g);
}

Type_G init_rand(Type_G g){
//matrice symétrique
int i,j;
for(i=1;i<= g.order;i++){
for(j=1;j<=(i-1);j++){
if(rand()%2==0){
g.matrice[i][j]=0;
g.matrice[j][i]=0;
}
else {
g.matrice[i][j]=1;
g.matrice[j][i]=1;
}
}
}
return (g);
}

void init_dsat(Type_G g){
int i,j;
for(i=1;i<=g.order;i++){
dsat[i]=0;
coloration_issu_de_dsat[i]=0;
for(j=1;j<=g.order;j++){
if(g.matrice[i][j]==1) dsat[i]++;
}//for j
degre[i]=dsat[i];
}//for i
}

//////////////////////////////////////
// walking Graph Function
//////////////////////////////////////
void parcours_profondeur(Type_G g, unsigned int som_depart)
{
int *marque,i;
marque=malloc(sizeof(int)*(g.order));
for(i=1;i<=g.order;i++)
marque[i]=0;

printf("\n\nParcours en profondeur à partir du sommet=%d\n",som_depart);
printf("\n\n\tRencontre prefixe de %d\n",som_depart);
parcours_profondeur_rec(g,som_depart,marque);
printf("\tRencontre suffixe de %d\n",som_depart);
free(marque);
printf("\n");
}


void parcours_profondeur_rec(Type_G g, unsigned int s, int *marque)
{
unsigned int i;
marque[s]=1;
for (i=1;i<=g.order;i++)
{
if (g.matrice[s][i]!=0) // si i est un voisin de s
if(!marque[i]) // si i n'est pas encore visite
{
printf("\tRencontre prefixe de %d\n",i);
parcours_profondeur_rec(g,i,marque);
printf("\tRencontre suffixe de %d\n",i);
}
}
}


void parcours_largeur(Type_G g, unsigned int s){
// la pile fifo
int * list;
//le juda pour memoriser les sommets par ou on est deja passé
int *marque;
int i,deb,fin;
int sommet_a_parcourir;

list =(int *)malloc(sizeof(int)*(g.order+2));
marque=(int *)malloc(sizeof(int)*(g.order+2));
//init du marque
for(i=1;i<=g.order;i++)
marque[i]=0;
//on enfile le sommet de depart
deb=1;
fin=2;
list[deb]=s;
marque[s]=1;// on le marque deja passe
while(deb<=g.order){
//depiler
sommet_a_parcourir=list[deb];
deb++;
printf("\n sommet %d) ",sommet_a_parcourir);
//enfiler les voisins de sommet_a_parcourir
for(i=1;i<=g.order;i++){
//si voisin et non marque
if((g.matrice[sommet_a_parcourir][i]!=0)&&(marque[i]==0)){
list[fin]=i;
marque[i]=1;
fin++;
}
}
}

}

int * copyYdansZ(int * destination, int *origine, Type_G g){
int i;
for(i=1;i<=g.order;i++)
destination[i]=origine[i];
return(destination);
}

int premier_sommet_de_Z (int * vecteur, Type_G g){
int i;
for(i=1;i<=g.order;i++)
if (vecteur[i]==0)
return(i);
return(-1);
}

int * retirer_s_et_ces_voisins (int s, int * vecteur, Type_G g){
int i;
vecteur[s]=1;
vecteur[g.order+1]++;
for(i=1;i<=g.order;i++)
if((g.matrice[s][i]>0)&&(vecteur[i]==0)){
vecteur[g.order+1]++;
vecteur[i]=1;
}
return(vecteur);
}

//////////////////////////////////////
// Glouton Graph algorithm
//////////////////////////////////////
int * glouton(Type_G g){
int i,s;
int * Y;
int * Z;
int cardY=0;
int cardZ=0;
int color=0;

Y=(int *)malloc(sizeof(int)*(g.order+2));
Z=(int *)malloc(sizeof(int)*(g.order+2));
Z[g.order+1]=0;//contient cardZ
//init
for(i=1;i<=g.order;i++){
Y[i]=0;
Z[i]=0;
}
while (cardY Z=copyYdansZ(Z,Y,g);
Z[g.order+1]=cardY;
color++;
printf("\n\tChangement de couleur à %d",color);
while(Z[g.order+1] s=premier_sommet_de_Z(Z,g);
printf("\ncoloration de y=%d avec color=%d",s,color);
Y[s]=color;cardY++;
Z=retirer_s_et_ces_voisins(s,Z,g);
}
}
return (Y);
}

//////////////////////////////////////
// DSAT graph algorithm
//////////////////////////////////////

int sommet_non_colorie_de_dsat_max(Type_G g){
//coloration_issu_de_dsat
int v,i,dsat_max_local=0;
for(i=1;i<= g.order;i++){
if (coloration_issu_de_dsat[i]==0){
if (dsat[i]>dsat_max_local){
v=i;
dsat_max_local=dsat[i];
}
}//if
}//for i
return(v);
}//end fct

int coloration_avec_couleur_mininum(int t, Type_G g){
int i;
int color_used[ORDER_MAX];

//init
for(i=1;i<= g.order;i++)color_used[i]=0;

for(i=1;i<= g.order;i++){
if((g.matrice[t][i]==1)&&(coloration_issu_de_dsat[i]>0)){
color_used[coloration_issu_de_dsat[i]]=1;
}//if
}//for

// on colorie t par la plus petite couleur non utilise
// dans son premier voisinage
for(i=1;i<= g.order;i++){
if (color_used[i]==0){
return (i);
}
}//for
}

int nb_de_couleur_differente_autour_de (int t, Type_G g){
int i, nb_de_couleur_utilisee_autour_de_t;
int color_used[ORDER_MAX];

//init
for(i=1;i<= g.order;i++)color_used[i]=0;

for(i=1;i<= g.order;i++){
if((g.matrice[t][i]==1)&&(coloration_issu_de_dsat[i]>0)){
color_used[coloration_issu_de_dsat[i]]=1;
}//if
}//for

nb_de_couleur_utilisee_autour_de_t=0;
for(i=1;i<= g.order;i++)
if (color_used[i]==1) nb_de_couleur_utilisee_autour_de_t++;
return (nb_de_couleur_utilisee_autour_de_t);
}

void maj_du_vecteur_dsat (int t, Type_G g){
int i;

// synthèse pour que le sommet actuellement colorié
// soit rapidement ecarté pour les autres choix
dsat[t]=-1;
for(i=1;i<= g.order;i++){
if((g.matrice[t][i]==1)&&(coloration_issu_de_dsat[i]==0)){
dsat[i]= nb_de_couleur_differente_autour_de (i,g);
}//if
}//for
}

void color_by_dsatur(Type_G g){
int i,j,s;

init_dsat(g);
for(i=1;i<= g.order;i++){
s=sommet_non_colorie_de_dsat_max(g);
coloration_issu_de_dsat[s]=coloration_avec_couleur_mininum(s,g);
printf("\n s=%d colorié par %d",s,coloration_issu_de_dsat[s]);
maj_du_vecteur_dsat(s,g);
}
}

//////////////////////////////////////
// DISPLAY
//////////////////////////////////////
void display_graph(Type_G g){
int i,j;
printf("\n\nDISPLAY graph:\n");
for(i=1;i<= g.order;i++){
printf("\n");
for(j=1;j<=(i-1);j++){
printf(" (%d,%d)=%d ",i,j,g.matrice[i][j]);
}
}
}

void display_vecteur(int *vecteur, Type_G g){
int i;
printf("\n\nDISPLAY vecteur (i,value):\n");
for(i=1;i<= g.order;i++){
printf(" (%d,%d) ",i,vecteur[i]);
}
}

//////////////////////////////////////
// MAIN
//////////////////////////////////////

int main (int argc, const char * argv[]) {
// insert code here...
int i;
Type_G g;
int * coloration;



g.order=10;
g=init_rand(g);
display_graph(g);
//parcours_profondeur(g,1);
//parcours_largeur(g,1);


//coloration=glouton(g);
//display_vecteur(coloration,g);

color_by_dsatur(g);

printf("\nFin.\n");
return 0;
}

Monday, February 27, 2006

Largest & Depth First Algorithm

In the same file, implementation example of these walking, written in C (02/2006), here http://prolland.free.fr/Cours/Cycle2/Maitrise/GraphsTheory/TP/parcours.c
and some details here http://prolland.free.fr/Cours/Cycle2/Maitrise/GraphsTheory/

prolland

Graph Colouring: Glouton

Algorithm written in C (02/2006)

Free download here:

http://prolland.free.fr/Cours/Cycle2/Maitrise/GraphsTheory/TP/glouton.c

prolland

movie & anim vecto

Movies en format flv (sous debian apt-get install flvtool, un pipe avec ffmepg)

ex: ffmpeg -i movie.mpg -f flv I flvtool -U stdin converted_movie.flv

sinon en w32: total video converter ou riva flv encoder

Ensuite demo lecteur flv sur flashkod




prolland

Wednesday, August 03, 2005

tournage de "A peu de chose près"

Short movie can be seen in QT H.264 file format (MPEG4 Part 10) in the following URL:
http://www.eticproduction.com/extrait2.html

Here some pictures about it.

For french people...

Mardi 2 Aout 2005 fin du tournage de "Jean".
Un court métrage de 20mn commencé le 02/2005 produit par ETIC Production.
Image glanée sur le tournage:


Jean & marcel