Correspondance d'indices matrice-string

**dvp_zero** · 07/04/2011, 11h36

Bonjour à tous,

je possède une matrice d'adjacence représentant un graphe :

0 1 1 0 1
1 0 1 0 0
1 1 0 0 1
0 0 0 0 1
1 0 1 1 0

Afin de ne pas devoir stocker cette matrice diagonale dans son entièreté, j'utilise la représentation suivante :

1 1 0 1 1 0 0 0 1 1

c'est à dire que je met à la suite les lignes du triangle supérieur.

Cependant, je n'arrive pas à faire la correspondance avec les indices de la représentation de ma chaîne de bits et les noeuds concernés dans le graphe.

J'aimerai pouvoir associer le bit en position 1 dans ma chaine au lien (1,2).

Dans mon cas, on aurait la correspondance suivante :

position 1 = 1 = lien (1,2) existe
position 2 = 1 = lien (1,3) existe
position 3 = 0 = lien (1,4) n'existe pas
position 4 = 1 = lien (1,5) existe
position 5 = 1 = lien (2,3) existe
position 6 = 0 = lien (2,4) n'existe pas

etc...

Pour le code, j'ai débuté comme ceci :

Code :

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

1
2
3
4
5
6
7
8
9
 
for(i=0; i<NBITS; i++)
  {
  	if(chaine[i] == 1)
    		{
                     Noeud source = ???
                     Noeud dest = ???
                }
}

J'ai essayé de jouer avec les modulos (sur le nombre de noeuds du graphe) mais je n'y arrive pas.

Merci d'avance.

**Franck Dernoncourt** · 07/04/2011, 13h04

Une piste écrite rapidement, donc je te laisse corriger les fautes s'il y en a :

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
col = 0
line = 0
for(i=0; i<NBITS; i++)
  {
	if (line == matrix_height) break
  	if(chaine[i] == 1)
    		{
                     Noeud source = line
                     Noeud dest = col
                }
	if (col == matrix_width - 1) {
		line++;
		col = line+1;
	}
	else col++;
}

**dvp_zero** · 07/04/2011, 16h29

Merci pour ton aide.
Je n'ai pas encore testé ton code mais je comprends ton principe.

Entre temps j'avais réfléchi de mon côté et j'ai pris le problème dans l'autre sens en partant des noeuds et non plus de la chaine.

Comme je connais le nombre de noeuds, j'effectue une double boucle en mettant un compteur à jour :

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
 
int position_bit = 0;
 
for(i=0; i< NNODE-1; i++)
  {
  	for(j=i+1; j<NNODE; j++)
  	{
  		if(chaine[position_bit] == 1)
    		{
    			 Noeud source = i;
                         Noeud dest = j;
    		}
    		position_bit++;		
  	}  
  }

**prgasp77** · 07/04/2011, 16h31

Salut,
loin de toute implémentation, je propose les relations suivantes.

Définitions
On se place dans le cas d'une matrice d'adjacence de taille $T$ . On cherche à établir la bijection entre l'indice de ta chaine binaire (noté : $i$ ) et le couple composé des numéros de nœuds source et destination ( noté : $(n_s, n_d)$ ).
Le décalage
$\Delta=\sum_{k=T-1-n_s}^{T-1} k\,\,=\,\,\frac{$2T-2-n_s$$n_s+1$}2$
Du couple à l'indice
$i\,=\,\Delta+n_d-n_s$
De l'indice au couple
$n_s=s(i,T)$ avec

$s(i_c, t_c)\,=\,\left\{\begin{array}{lr}T-t_c &\mbox{si}\,i<t_c-1 \\ s(i-t_c+1,t_c-1) &\mbox{sinon}\end{array}\right.$
$n_d\,=\,i+n_s-\Delta$

En espérant que ça aidera

**Acrim** · 07/04/2011, 17h05

Envoyé par Franck Dernoncourt

Une piste écrite rapidement, donc je te laisse corriger les fautes s'il y en a :

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
col = 0
line = 0
for(i=0; i<NBITS; i++)
  {
	if (line == matrix_height) break
  	if(chaine[i] == 1)
    		{
                     Noeud source = line
                     Noeud dest = col
                }
	if (col == matrix_width - 1) {
		col = 0;
		line++;
	}
	else col++;
}

Je crois qu'il y a une erreur au niveau des lignes 11-13:

Code :

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

1
2
3
4
	if (col == matrix_width - 1) {
		line++;
		col = line+1;
	}

Si tu souhaites trouver le 'bit' correspondant à l'arc (c,l), tu devrais pouvoir utiliser une "formule" de la forme (c-1) + matrix_width*l - l*(l+1)/2 (somme des l premiers entiers).