Correspondance d'indices matrice-string

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:

---

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.

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

Code:

---

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++; }

---

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:

---

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++; } }

---

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

1. Définitions
   On se place dans le cas d'une matrice d'adjacence de taille https://chart.googleapis.com/chart?cht=tx&chl=T. On cherche à établir la bijection entre l'indice de ta chaine binaire (noté : https://chart.googleapis.com/chart?cht=tx&chl=i) et le couple composé des numéros de nœuds source et destination ( noté : https://chart.googleapis.com/chart?c...chl=(n_s, n_d)).
   
   
2. Le décalage
   https://chart.googleapis.com/chart?c...)\(n_s%2B1\)}2
   
   
3. Du couple à l'indice
   https://chart.googleapis.com/chart?c...elta%2Bn_d-n_s
   
   
4. De l'indice au couple
   https://chart.googleapis.com/chart?c...chl=n_s=s(i,T) avec
   
   http://www.futura-sciences.com/cgi-b...{array}\right.
   https://chart.googleapis.com/chart?c...i%2Bn_s-\Delta

En espérant que ça aidera ;)

Citation:

---

Envoyé par Franck Dernoncourt

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

Code:

---

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:

---

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).

Citation:

---

Envoyé par Acrim

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

---

Ah oui bien vu, j'avais zappé de repartir depuis la diagonale ;)
Enfin bon le but était que dvp_zero voit l'idée. Merci pour la correction !

Merci à tous pour votre aide!:ccool: