silico.biotoul.fr
 

M1 MABS Graphes TP Parcours en largeur - Plus court chemin

From silico.biotoul.fr

(Difference between revisions)
Jump to: navigation, search
m (→Parcours en largeur)
m (→Plus courts chemins - Floyd-Warshall)
 
(11 intermediate revisions not shown)
Line 2: Line 2:
Algorithme :
Algorithme :
  BFS(G, s)
  BFS(G, s)
-
   for each vertex u in V(G)
+
   '''for each''' vertex u <math>\in</math> V(G)
-
     do color[u] <- white
+
     '''do''' color[u] <math>\leftarrow</math> WHITE
-
         d[u] <- inf
+
         d[u] <math>\leftarrow</math> <math>\infty</math>
-
         pred[u] <- NIL
+
         <math>\pi</math>[u] <math>\leftarrow</math> NIL
-
   color[s] <- gray
+
   color[s] <math>\leftarrow</math> GRAY
-
   d[s] <- 0
+
   d[s] <math>\leftarrow</math> 0
-
   Q <- <math>\empty</math>
+
   Q <math>\leftarrow</math> <math>\empty</math>
   enqueue(Q, s)
   enqueue(Q, s)
-
   while Q <math>\ne</math> <math>\empty</math>
+
   '''while''' Q <math>\ne</math> <math>\empty</math>
-
     do u <- dequeue(Q)
+
     '''do''' u <math>\leftarrow</math> dequeue(Q)
-
       for each v in Adj[u]
+
       '''for each''' vertex v <math>\in</math> Adj[u]
-
         do if color[v] = white
+
         '''do if''' color[v] = WHITE
-
           then color[v] <- gray
+
           '''then''' color[v] <math>\leftarrow</math> GRAY
-
                 d[v] <- d[u] + 1
+
                 d[v] <math>\leftarrow</math> d[u] + 1
-
                 pred[v] <- u
+
                 <math>\pi</math>[v] <math>\leftarrow</math> u
                 enqueue(Q, v)
                 enqueue(Q, v)
-
       color[u] <- black
+
       color[u] <math>\leftarrow</math> BLACK
-
Charger le graphe de la séance précédente ([[File:M1MABS Graphe dressing.sif]]), et faire un parcours en largeur depuis sous-vetements.
+
'''Charger''' le graphe de la séance précédente ([[File:M1MABS Graphe dressing.sif]]), et effectuer un parcours en largeur depuis sous-vetements.
 +
= Plus court chemin - Bellman-Ford =
 +
Rappel de l'algorithme:
 +
  INITIALIZE-SINGLE-SOURCE(G, s)
 +
    '''for each''' vertex v <math>\in</math> V(G)
 +
      '''do''' d[v] <math>\leftarrow</math> <math>\infty</math>
 +
        <math>\pi</math>[v] <math>\leftarrow</math> NIL
 +
    d[s] <math>\leftarrow</math> 0
 +
  RELAX(u, v, w)
 +
    '''if''' d[v] > d[u] + w(u, v)
 +
      '''then''' d[v] = d[u] + w(u,v)
 +
          <math>\pi</math>[v] <math>\leftarrow</math> u
 +
  BELLMAN-FORD(G, s, w)
 +
    INITIALIZE-SINGLE-SOURCE(G, s)
 +
    '''for''' i <math>\leftarrow</math> 1 '''to''' |V(G)| - 1
 +
      '''do for each''' edge (u,v) <math>\in</math> E(G)
 +
        '''do''' RELAX(u, v, w)
 +
 +
'''Ajoutez''' la méthode à votre librairie et testez la sur le graphe [[File:M1MABS Graphe Bellman-Ford.tab]] à partir du sommet A.
 +
 +
Afin de gagner du temps, la méthode <tt>loadTAB</tt> vous est fournie :
 +
<source lang='python'>
 +
def loadTAB(self, filename):
 +
"""
 +
Loads a graph in Cytoscape tab format
 +
Assumed input:
 +
  id1 id2 weight color ...
 +
  A B 6 blue ...
 +
"""
 +
with open(filename) as f:
 +
# GET COLUMNS NAMES
 +
tmp = f.readline().rstrip()
 +
attNames= tmp.split('\t')
 +
# REMOVES FIRST TWO COLUMNS WHICH CORRESPONDS TO THE LABELS OF THE CONNECTED VERTICES
 +
attNames.pop(0)
 +
attNames.pop(0)
 +
# PROCESS THE REMAINING LINES
 +
row = f.readline().rstrip()
 +
while row:
 +
vals = row.split('\t')
 +
v1 = vals.pop(0)
 +
v2 = vals.pop(0)
 +
att = {}
 +
for i in xrange(len(attNames)):
 +
att[ attNames[i] ] = vals[i]
 +
self.addEdge(v1, v2, att)
 +
row = f.readline().rstrip() # NEXT LINE
 +
</source>
 +
 +
<!--
= Plus court chemin - Dijkstra =
= Plus court chemin - Dijkstra =
Pour l'algorithme suivant,  
Pour l'algorithme suivant,  
Line 57: Line 106:
     'RFBD': 'RFBC',  
     'RFBD': 'RFBC',  
     'WBBK': 'WBBJ'}}
     'WBBK': 'WBBJ'}}
 +
-->
= Plus courts chemins - Floyd-Warshall =
= Plus courts chemins - Floyd-Warshall =
Line 65: Line 115:
Algorithme :
Algorithme :
-
  initialiser D = W, et N
+
  initialiser D = W, et N à partir des arcs/arêtes du graphe
  pour k de 1 à n
  pour k de 1 à n
     pour i de 1 à n
     pour i de 1 à n
Line 71: Line 121:
           si D[i,k] + D[k,j] < D[i,j] alors
           si D[i,k] + D[k,j] < D[i,j] alors
             D[i,j] = D[i,k] + D[k,j]
             D[i,j] = D[i,k] + D[k,j]
-
             N[i,j] = k
+
             N[i,j] = N[i,k]
Récupération du plus court chemin à partir de la matrice N :
Récupération du plus court chemin à partir de la matrice N :
Line 84: Line 134:
     ajouter(chemin, j)
     ajouter(chemin, j)
-
Implémenter les algorithmes ci-dessus en R et les tester sur la matrice suivante :
+
'''Implémentez''' les méthodes FloydWarshall(W) et FloydWarshallPath(source, destination) dans votre librairie. Pour cela, vous êtes forcement incité(e) à ajouter une méthode ''adjacencyMatrix'' qui renvoie le graphe source forme de matrice d'adjacence.
 +
 
 +
 
 +
'''Testez''' ces méthodes sur le graphe [[File:M1MABS Graphe Floyd-Warshall.tab]] et '''affichez''' les plus courts chemins de A à C et de A à B (avec leur longueur).
 +
 
 +
Quel est le diamètre du graphe ? '''Affichez''' le chemin correspondant.
 +
 
 +
 
 +
<!--
<source lang='rsplus'>
<source lang='rsplus'>
# adjacency matrix
# adjacency matrix
Line 122: Line 180:
* [[Media:String_EcolA_selection.tab|String_EcolA_selection.tab]]
* [[Media:String_EcolA_selection.tab|String_EcolA_selection.tab]]
* [[Media:WBBJ_EcolA_String_subgraph.tab|WBBJ_EcolA_String_subgraph.tab]]
* [[Media:WBBJ_EcolA_String_subgraph.tab|WBBJ_EcolA_String_subgraph.tab]]
 +
-->

Current revision as of 15:22, 20 February 2015

Parcours en largeur

Algorithme : 

BFS(G, s)
  for each vertex u \in V(G)
    do color[u] \leftarrow WHITE
       d[u] \leftarrow \infty
       π[u] \leftarrow NIL
  color[s] \leftarrow GRAY
  d[s] \leftarrow 0
  Q \leftarrow \empty
  enqueue(Q, s)
  while Q \ne \empty
    do u \leftarrow dequeue(Q)
      for each vertex v \in Adj[u]
        do if color[v] = WHITE
          then color[v] \leftarrow GRAY
               d[v] \leftarrow d[u] + 1
               π[v] \leftarrow u
               enqueue(Q, v)
      color[u] \leftarrow BLACK

Charger le graphe de la séance précédente (File:M1MABS Graphe dressing.sif), et effectuer un parcours en largeur depuis sous-vetements.

Plus court chemin - Bellman-Ford

Rappel de l'algorithme: 

 INITIALIZE-SINGLE-SOURCE(G, s)
   for each vertex v \in V(G)
     do d[v] \leftarrow \infty
        π[v] \leftarrow NIL
   d[s] \leftarrow 0
 RELAX(u, v, w)
   if d[v] > d[u] + w(u, v)
     then d[v] = d[u] + w(u,v)
          π[v] \leftarrow u
 BELLMAN-FORD(G, s, w)
   INITIALIZE-SINGLE-SOURCE(G, s)
   for i \leftarrow 1 to |V(G)| - 1
     do for each edge (u,v) \in E(G)
       do RELAX(u, v, w)

Ajoutez la méthode à votre librairie et testez la sur le graphe File:M1MABS Graphe Bellman-Ford.tab à partir du sommet A.

Afin de gagner du temps, la méthode loadTAB vous est fournie : 

	def loadTAB(self, filename):
		"""
		Loads a graph in Cytoscape tab format
		Assumed input:
		   id1	id2	weight	color	...
		   A	B	6	blue	...
		"""
		with open(filename) as f: 
			# GET COLUMNS NAMES
			tmp = f.readline().rstrip()
			attNames= tmp.split('\t')
			# REMOVES FIRST TWO COLUMNS WHICH CORRESPONDS TO THE LABELS OF THE CONNECTED VERTICES
			attNames.pop(0)
			attNames.pop(0)
			# PROCESS THE REMAINING LINES
			row = f.readline().rstrip()
			while row:
				vals = row.split('\t')
				v1 = vals.pop(0)
				v2 = vals.pop(0)
				att = {}
				for i in xrange(len(attNames)):
					att[ attNames[i] ] = vals[i]
				self.addEdge(v1, v2, att)
				row = f.readline().rstrip() # NEXT LINE


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 à partir des arcs/arêtes du graphe
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] = N[i,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émentez les méthodes FloydWarshall(W) et FloydWarshallPath(source, destination) dans votre librairie. Pour cela, vous êtes forcement incité(e) à ajouter une méthode adjacencyMatrix qui renvoie le graphe source forme de matrice d'adjacence.


Testez ces méthodes sur le graphe File:M1MABS Graphe Floyd-Warshall.tab et affichez les plus courts chemins de A à C et de A à B (avec leur longueur).

Quel est le diamètre du graphe ? Affichez le chemin correspondant.


Retrieved from "http://silico.biotoul.fr/p/M1_MABS_Graphes_TP_Parcours_en_largeur_-_Plus_court_chemin"