From silico.biotoul.fr

Revision as of 11:40, 20 February 2013

Parcours en profondeur

Algorithme :

BFS(graphe g, sommet s)
   f = créerFile
   marquer(s)
   enfiler(f,s)
   tant que f n'est pas vide
      x = défiler(f)
      afficher(x)
      pour chaque successeur de x faire
         si successeur n'est pas marqué alors
            marquer(successeur)
            enfiler(f, successeur)

Charger le graphe de la séance précédente, et faire un parcours en largeur depuis WBBJ.

Résultat attendu :

DFS
['WBBJ', 'RFBX', 'RFBC', 'RFBD', 'WBBH', 'WBBK', 'WBBI']
BFS
['WBBJ', 'RFBX', 'WBBH', 'WBBK', 'WBBI', 'RFBC', 'RFBD']

Plus court chemin - Dijkstra

Pour l'algorithme suivant,

• D[x] donne la plus courte distance entre s et x. Au départ, D[s]=0 et D[x]=infini pour tout x différent s.
• P[x] est le prédécesseur de x dans le chemin de plus courte distance allant de s à x. Au départ, P[x]=rien pour tout x.
• C est l'ensemble de sommets qu'il reste à parcourir. Au départ, C=V (V étant l'ensemble des sommets du graphe).
• W[x,y] est la valuation de l'arc (x,y)

Algorithme :

Dijkstra(graphe g, sommet s)
   initialiser D, P et C
   tant que C n'est pas vide faire
      x = extraire le sommet le plus proche de C
      pour chaque successeur de x faire
         si D[x] + W[x,successeur] < D[successeur] alors 
            D[successeur] = D[x] + D[successeur]
            P[successeur] = x

Extraire la composante connexe contenant WBBJ, puis faire tourner l'algorithme ci-dessus à partir de WBBJ. Pour la valuation des arêtes, on prendra 1000-combined.

Résultat attendu :

{'distances': 
  {'WBBI': 29, 
   'WBBH': 34, 
   'RFBX': 71, 
   'WBBJ': 0, 
   'RFBC': 103, 
   'RFBD': 104, 
   'WBBK': 6}, 
 'predecessors': {
    'WBBI': 'WBBK', 
    'WBBH': 'WBBK', 
    'RFBX': 'WBBJ', 
    'RFBC': 'RFBX', 
    'RFBD': 'RFBC', 
    'WBBK': 'WBBJ'}}

Plus courts chemins - Floyd-Warshall

Pour l'agorithme suivant,

• D[x,y] est la distance du plus court chemin entre les sommets x et y
• N[x,y] est le successeur de x dans le plus court chemin allant de x à y
• W[x,y] est la valuation de l'arc (x,y)

Algorithme :

initialiser D = W, et N
pour k de 1 à n
   pour i de 1 à n
      pour j de 1 à n
         si D[i,k] + D[k,j] < D[i,j] alors
            D[i,j] = D[i,k] + D[k,j]
            N[i,j] = k

Récupération du plus court chemin à partir de la matrice N :

plusCourtChemin(D,N, i,j)
   si D[i,j] est infinie alors
      il n'y a pas de chemin entre i et j
   chemin = initialiserChemin(i)
   k = N[i,j]
   tant que k est défini faire
      ajouter(chemin, k)
      k = N[k,j]
   ajouter(chemin, j)

Implémenter les algorithmes ci-dessus en R et les tester sur la matrice suivante :

# adjacency matrix
M=matrix( c(0,1,0,0,1,0,0,1,0,0,1,1,0,0,0,0), ncol=4, byrow=T)
M
#     [,1] [,2] [,3] [,4]
#[1,]    0    1    0    0
#[2,]    1    0    0    1
#[3,]    0    0    1    1
#[4,]    0    0    0    0
 
# test
fw=FloydWarshall(M)
fw
#$distances
#     [,1] [,2] [,3] [,4]
#[1,]    2    1  Inf    2
#[2,]    1    2  Inf    1
#[3,]  Inf  Inf    1    1
#[4,]  Inf  Inf  Inf  Inf
#
#$chemins
#     [,1] [,2] [,3] [,4]
#[1,]    2   NA  Inf    2
#[2,]   NA    1  Inf   NA
#[3,]  Inf  Inf   NA   NA
#[4,]  Inf  Inf  Inf  Inf
 
FloydWarshallPath(fw, 1,4)
#[1] 1 2 4

Extraire la grosse composante connexe de String au format sif puis transformer le fichier en matrice d'adjacence. Ensuite, sous R, charger la matrice et calculer le diamètre du graphe.