silico.biotoul.fr
 

M1 BBS Graphes TP Librairie - Parcours de graphes

From silico.biotoul.fr

(Difference between revisions)
Jump to: navigation, search
m (TP1 - 2h)
m (Structures de données et représentation d'un graphe)
Line 95: Line 95:
def TP1():
def TP1():
-
#~ from Graph import createGraph
+
#~ import Graph as gr
pprint('#### createGraph ####')
pprint('#### createGraph ####')
G = createGraph()
G = createGraph()
Line 124: Line 124:
if attributes is None: # create empty attributes if not provided
if attributes is None: # create empty attributes if not provided
attributes = {}
attributes = {}
-
g['nodes'][n] = attributes # init attributes
+
g['nodes'][n] = attributes
-
g['edges'][n] = {} # init edges
+
g['edges'][n] = {} # init outgoing edges
-
return n
+
g['nb_nodes'] += 1
 +
return g['nodes'][n] # return node attributes
</source>
</source>
Line 140: Line 141:
if n1 not in g['nodes']: addNode(g, n1) # ensure n1 exists
if n1 not in g['nodes']: addNode(g, n1) # ensure n1 exists
if n2 not in g['nodes']: addNode(g, n2) # ensure n2 exists
if n2 not in g['nodes']: addNode(g, n2) # ensure n2 exists
-
# add edges ONLY if they do not exist
+
# add edge(s) only if they do not exist
if n2 not in g['edges'][n1]:
if n2 not in g['edges'][n1]:
-
if attributes is None: # create empy attributes if not provided
+
if attributes is None:
attributes = {}
attributes = {}
-
g['edges'][n1][n2] = attributes # set attributes
+
g['edges'][n1][n2] = attributes
-
if not g['directed']: # add reverse edge if undirected graph
+
if not g['directed']:
-
g['edges'][n2][n1] = g['edges'][n1][n2]
+
g['edges'][n2][n1] = g['edges'][n1][n2] # share the same attributes as n1->n2
g['nb_edges'] += 1
g['nb_edges'] += 1
-
return g['edges'][n1][n2]
+
return g['edges'][n1][n2] # return edge atributes
</source>
</source>
Line 158: Line 159:
def loadSIF(filename, directed=True): # TP1
def loadSIF(filename, directed=True): # TP1
# line syntax: nodeD <relationship type> nodeE nodeF nodeB
# line syntax: nodeD <relationship type> nodeE nodeF nodeB
-
g = createGraph(directed)
+
g = createGraph(directed) # new empty graph
with open(filename) as f: # OPEN FILE
with open(filename) as f: # OPEN FILE
-
# PROCESS ALL LINES
+
# PROCESS THE REMAINING LINES
-
row = f.readline().rstrip()
+
row = f.readline().rstrip() # read next line and remove ending whitespaces
while row:
while row:
-
vals = row.split('\t')
+
vals = row.split('\t') # split line on tab
for i in range(2, len(vals)):
for i in range(2, len(vals)):
att = { 'type': vals[1] } # set edge type
att = { 'type': vals[1] } # set edge type
addEdge(g, vals[0], vals[i], att)
addEdge(g, vals[0], vals[i], att)
-
row = f.readline().rstrip()
+
row = f.readline().rstrip() # read next line
-
return g
+
return g # return graph
</source>
</source>

Revision as of 10:51, 30 November 2016

Contents

Librairie python pour le traitement de graphes

Vous allez réaliser une pseudo-bibliothèque pour les graphes (orientés ou non) que vous allez construire au fur et à mesure de ce TP, du suivant, et du projet pour cette UE.

Cette librairie va permettre :

  • le chargement d'un graphe sous différents formats (SIF et TAB vus précédemment, OBO pour la Gene Ontology et produits de gènes pour les annotations des gènes en GOTerm),
  • le parcours en profondeur (DFS),
  • la détection de cycle/circuit,
  • le tri topologique,
  • le parcours en largeur (BFS),
  • l'identification des plus courts chemin à partir d'un sommet (Bellman-Ford), ou entre toutes les paires de sommets (Floyd-Warshall),
  • ...

TP1 - 2h

Structures de données et représentation d'un graphe

Pour commencer, il vous faut définir les structures de données que vous allez utiliser pour représenter et traiter des graphes. Un graphe

  • peut avoir différents attributs (nom, ordre, diamètre, ...),
  • peut être orienté ou non,
  • peut être pondéré ou non,
  • possède un ensemble de sommets,
  • possède un ensemble d'arcs ou d'arêtes.

De plus, un sommet peut avoir différentes étiquettes ou attributs : identifiant, nom, index, date de passage, couleur, coordonnées (x,y), etc.. De même, un arc ou une arête peut avoir différents attributs : poids, longueur, couleur, type, etc..

Un des choix cruciaux va être de choisir le stockage pour les arcs ou arêtes (notés arcs par la suite) : il est possible, par exemple, d'opter pour une matrice d'adjacence ou des listes d'adjacence. Si l'on manipule des graphes peu denses, la représentation par listes d'adjacence est préférable.

Toutes ces informations peuvent être stockées dans un dictionnaire à l'allure suivante (avec la syntaxe python) :

graph = {
     'directed':    True/False,
     'weighted':    True/False,
     'attributes':  {},
     'nodes':       {},
     'edges':       {}
}

Les clés attributes, nodes et edges pointent elles-mêmes vers des dictionnaires imbriqués.

Considérons le graphe G très simple suivant constitué de 2 sommets et d'un arc (A,B) ayant un poids de 5 :

     5
A ------> B

Le plus compliqué est le stockage des arcs qui peuvent avoir différents attributs. Le choix proposé est d'utiliser un dictionnaire de dictionnaires de dictionnaires de dictionnaires ... : pour l'arc de A à B de poids 5 :

graph['edges']['A']['B']['weight'] = 5

En d'autres termes :

  • graph['edges'] est un dictionnaire dont les clés sont les sommets source des arcs et dont les valeurs sont des dictionnaires,
  • graph['edges']['A'] est un dictionnaire pour les arcs dont l'extrémité initiale est le sommet A. Ce sommet peut avoir un degré sortant supérieur à 1, donc il faut stocker les extrémités terminales sous forme de dictionnaire. Les clés de ce dictionnaire seront donc les sommets correspondants aux extrémités terminales des sommets dont l'extrémité initiale est A,
  • graph['edges']['A']['B'] est un dictionnaire permettant de stocker les attributs de l'arc (A,B),
  • graph['edges']['A']['B']['weight'] est ainsi le poids de l'arc A --> B.

Ainsi, si un graphe pondéré est chargé, on pourra choisir de stocker le poids des arcs dans les attributs des arcs (accessibles à partir de la clé edges) avec la clé weight. Pour G, le dictionnaire pour son stockage aura l'allure suivante :

 G = {
   'directed': True,
   'weighted': True,
   'attributes':  { 
       'weight_attribute': 'weight'   
       },
   'nodes': {
      'A': { },
      'B': { }
      },
   'edges': {
      'A': { 
        'B': {
           'weight': 5
           }
        }
   }
}

Pour créer un graphe, la librairie python que vous allez développer devrait donc commencer par le code python suivant :

#!/usr/bin/python3
# -*- coding: utf-8 -*-
 
from pprint import pprint
import numpy as np # for Floyd-Warshall matrices
 
# TP1 functions
###############
 
 
def createGraph(directed = True, weighted = False): # TP1
	g = { 'directed': directed, 'weighted': weighted, 'nb_nodes': 0, 'nb_edges': 0, 'weight_attribute': None , 'nodes': {}, 'edges': {}  }
	return g
 
 
#############
# TP1 Tests
 
def TP1():
	#~ import Graph as gr
	pprint('#### createGraph ####')
	G = createGraph()
	pprint(G)
 
#############
# TP2 Tests
def TP2():
	return
 
#############
 
# Perform tests if not imported by another script
if __name__ == "__main__":
	TP1()
	TP2()

Créez le fichier correspondant à votre librairie (par exemple Graph.py) et testez-le.

Il s'agit maintenant de pouvoir ajouter des sommets et des arcs.

Avant d'ajouter un sommet, il faut s'assurer qu'il n'existe pas déjà :

def addNode(g, n, attributes = None): # TP1
	if n not in g['nodes']: # ensure node does not already exist
		if attributes is None: # create empty attributes if not provided
			attributes = {}
		g['nodes'][n] = attributes
		g['edges'][n] = {} # init outgoing edges
		g['nb_nodes'] += 1
	return g['nodes'][n] # return node attributes

De même, pour ajouter un arc, il faut

  • s'assurer que l'extrémité initiale existe
  • s'assurer que l'extrémité terminale existe
  • s'assurer que l'arc n'existe pas
  • si le graphe n'est PAS orienté, il faut ajouter A --> B et B --> A
def addEdge(g, n1, n2, attributes = None): # TP1
	# create nodes if they do not exist
	if n1 not in g['nodes']: addNode(g, n1) # ensure n1 exists
	if n2 not in g['nodes']: addNode(g, n2) # ensure n2 exists
	# add edge(s) only if they do not exist
	if n2 not in g['edges'][n1]:
		if attributes is None:
			attributes = {}
		g['edges'][n1][n2] = attributes
		if not g['directed']:
			g['edges'][n2][n1] = g['edges'][n1][n2] # share the same attributes as n1->n2
		g['nb_edges'] += 1
	return g['edges'][n1][n2] # return edge atributes

Chargement d'un fichier au format SIF : il s'agit de

  • créer un graphe (orienté ou non, mais pas pondéré)
  • lire le fichier ligne par ligne, et pour chacune ligne : ajout des sommets et des arcs
def loadSIF(filename, directed=True): # TP1
	# line syntax: nodeD <relationship type> nodeE nodeF nodeB
	g = createGraph(directed) # new empty graph
	with open(filename) as f: # OPEN FILE
		# PROCESS THE REMAINING LINES
		row = f.readline().rstrip() # read next line and remove ending whitespaces
		while row:
			vals = row.split('\t') # split line on tab
			for i in range(2, len(vals)):
				att = { 'type': vals[1] } # set edge type
				addEdge(g, vals[0], vals[i], att)
			row = f.readline().rstrip() # read next line
	return g # return graph

Vous pourrez tester ces fonction sue le fichier File:M1BBS Graphe dressing.sif avec la fonction TP1() suivante :

def TP1():
	print('#### createGraph ####')
	G = createGraph()
	pprint(G)
 
	print('## Adding node A')
	addNode(G,'A')
	pprint(G)
 
	print('## Adding edge A -> B')
	addEdge(G, 'A', 'B')
	pprint(G)
 
	print('## #Loading SIF file dressing.sif')
	G = loadSIF('dressing.sif')
	pprint(G)

Parcours en profondeur et applications

Implémentez et testez ensuite le parcours en profondeur dont on vous rappelle l'algorithme :

 DFS(G)
   for each vertex u \in V(G)
     do color[u] \leftarrow WHITE
        pred[u]  \leftarrow NIL
   time \leftarrow 0
   for each vertex u \in V(G)
     do if color[u] = WHITE
       then DFS-VISIT(u)
 DFS-VISIT(u)
   color[u] \leftarrow GRAY
   time \leftarrow time + 1
   d[u] \leftarrow time
   for each vertex v \in Adj[u]
     do if color[v] = WHITE
       then pred[v] \leftarrow u
            DFS-VISIT(v)
            class[ (u,v) ] \leftarrow TREE EDGE
       else if color[v] = GRAY
            then class[ (u,v) ] \leftarrow BACK EDGE
            else if d[u] > d[v]
                 then class[ (u,v) ] \leftarrow CROSS EDGE
                 else class[ (u,v) ] \leftarrow FORWARD EDGE
   color[u] \leftarrow BLACK
   time \leftarrow time + 1
   f[u] \leftarrow time


Implémentez et testez la méthode isAcyclic() qui renvoie vrai ou faux selon que le graphe est sans circuit ou non.

Implémentez et testez la méthode topologicalSort() qui renvoie les sommets du graphes en ayant effectué un tri topologique.

Quels sont les sommets que l'on peut atteindre à partir de WBBJ sur EcolA_String_coexpression.sif (en vous servant de DFS) ?

Autres fichiers :

TP2 - 4h

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 utilisé précédemment (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 Media:M1BBS 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 fonction adjacency_matrix qui renvoie le graphe source forme de matrice d'adjacence.

Aide : Création d'une matrice de 10 lignes et 20 colonnes initialisées avec des valeurs infinies avec numpy

import numpy as np
 
matrix = np.full( (10, 20), np.inf )

Testez ces méthodes sur le graphe Media:M1BBS 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.