Exercicio 8

Incluir os pseudo-códigos nos algoritmos que já foram implementados

Função que monta os clusters a partir da MST

Na função abaixo, usa-se o critério de distância.

Por esse critério, um cluster pode ter arestas com peso menor ou igual a distância maxima

 1 import fer_lib as lib
 2 
 3 def findClustersByDist(MST, maxDist):
 4     n = MST.shape[0]
 5 
 6     V = array((range(0,n)))
 7 
 8     arestas = lib.Matrix2ListWithWeight(MST)
 9     while(len(arestas)>0):
10         a = arestas.pop()
11 
12         if((a[2]<=maxDist) and (V[a[0]]!=V[a[1]])):
13             aux = V[a[0]]
14             V[V==aux] = V[a[1]]
15             n-=1;
16 
17     return [V,n]

Na função abaixo, usa-se o critério de número de classes

Por esse critério, para se separar um cluster em 2, o cirtério é a aresta de maior peso do cluster

 1 import fer_lib as lib
 2 
 3 def findClustersByClass(MST, numero):
 4     n = MST.shape[0]
 5 
 6     V = array(range(0,n))
 7 
 8     arestas = lib.Matrix2ListWithWeight(MST)
 9     arestas = sorted(arestas, key=lambda arestas:arestas[2])
10 
11     while(n>numero):
12         a = arestas.pop(0)
13         aux = V[a[1]]
14         if(V[a[0]] != V[a[1]]):
15             V[V==aux] = V[a[0]]
16             n-=1
17 
18     return V

A função abaixo, desenha um grafo colorindo os vértices de acordo com os clusters a que eles pertencem Cada cluster é associado a uma cor. Sendo assim, vértices pertencentes a um mesmo cluster, tem a mesma cor

 1 from numpy import *
 2 import gvgen
 3 
 4 def drawCluster(M, V):
 5     colors = ["blue", "red", "yellow", "black", "pink", "green", "orange","purple"]
 6 
 7     graph = gvgen.GvGen(options="compound=false;")
 8 
 9     r = M.shape[0]      # calcula o numero de nos do (di)grafo
10     T = {}
11 
12     # cria nos do grafo
13     for i in range(r):
14         T[i] = graph.newItem("n"+str(i))
15         graph.propertyAppend(T[i], "color", colors[V[i]%len(colors)])
16 
17     r,c = where(M!=Inf)  # identifica arestas
18     a={}
19 
20     #cria arcos/arestas do (di)grafo
21     for i in range(r.shape[0]):
22         # essa condiçao impede a criaçao de 2 arestas entre 2 vértices para um grafo, p.e. a-b e b-a
23         if(r[i]>=c[i]):
24             a[i] = graph.newLink(T[r[i]],T[c[i]])
25             graph.propertyAppend(a[i], "label",str( M[r[i],c[i]]))
26 
27     import StringIO
28     fd = StringIO.StringIO()
29     graph.dot(fd)
30     dottext = fd.getvalue()
31 
32     # caso em que M é um grafo, transforma de digrafo em grafo
33     dottext = dottext.replace('digraph', 'graph')
34     dottext = dottext.replace('->', '--')
35 
36     return dottext

Exemplos

Clusters definidos por distância maxima

Clusters com maxDist=9:  [0 0 0 0 0 0 0]
Numero de clusters:  1
Clusters com maxDist=7:  [0 0 0 0 0 0 6]
Numero de clusters:  2

Clusters com maxDist=6:  [0 1 2 0 2 0 6]
Numero de clusters:  4

Clusters com maxDist=5:  [0 1 2 0 2 5 6]
Numero de clusters:  5


Clusters definidos por numero de classes

Clusters com numero de classes = 1 :  [0 0 0 0 0 0 0]
Clusters com numero de classes = 2 :  [0 0 0 0 0 0 6]

Clusters com numero de classes = 3 :  [0 0 2 0 2 0 6]

Clusters com numero de classes = 4 :  [0 1 2 0 2 0 6]

Clusters com numero de classes = 5 :  [0 1 2 0 2 5 6]
/media/_xsb/courseIA368Q1S2012/fer_8/GRVIZ82055_001.png

MST com maxDist=9

/media/_xsb/courseIA368Q1S2012/fer_8/GRVIZ82055_002.png

MST com maxDist=7

/media/_xsb/courseIA368Q1S2012/fer_8/GRVIZ82055_003.png

MST com maxDist=6

/media/_xsb/courseIA368Q1S2012/fer_8/GRVIZ82055_004.png

MST com maxDist=5

/media/_xsb/courseIA368Q1S2012/fer_8/GRVIZ82055_005.png

MST com numero de classes = 1

/media/_xsb/courseIA368Q1S2012/fer_8/GRVIZ82055_006.png

MST com numero de classes = 2

/media/_xsb/courseIA368Q1S2012/fer_8/GRVIZ82055_007.png

MST com numero de classes = 3

/media/_xsb/courseIA368Q1S2012/fer_8/GRVIZ82055_008.png

MST com numero de classes = 4

/media/_xsb/courseIA368Q1S2012/fer_8/GRVIZ82055_009.png

MST com numero de classes = 5