Function iacc_rod

Synopse

iacc_rod - Connected Components using breadth first search.

  • a = iasym(A)

    • a: Boolean. TRUE if matrix A is symmetric or FALSE otherwise.

    • A: Numpy array. Matrix that will be checked. Valor 'Inf'

      indica .

Description

Function finds the connected components of the adjacency matrix and return a labeled adjacency matrix.

Function Code

 1 from numpy import *
 2 
 3 def iacc_rod(MA):
 4     #Pega o numero de vertices
 5     n_vert = MA.shape[0]
 6     #Cria uma fila
 7     Q = []
 8     #Cria vetor de rotulos
 9     rotulos = zeros(n_vert, dtype='uint')
10     #Enquanto houverem vertices nao rotulados, marca um componente conexo
11     n_cconexo = 0
12     while len(where(rotulos == 0)[0]) > 0:
13         #Incrementa o contador de componentes conexos
14         n_cconexo += 1
15 
16         #Pega o primeiro vertice ainda nao rotulado
17         naoRotulados = where(rotulos == 0)
18         #Adiciona na fila e rotula-o
19         Q.append( naoRotulados[0][0] )
20         rotulos[ naoRotulados[0][0] ] = n_cconexo
21 
22         #Varre um componente conexo
23         while (len(Q) > 0):
24             #Pega o primeiro vertice da fila
25             v = Q.pop(0)
26             #Pega os vertices adjacentes
27             adj = nonzero(MA[:,v])
28             #verifica os adjacentes e marca os que nao estiverem rotulados
29             for w in adj[0]:
30                 if rotulos[w] == 0:
31                     Q.append(w)
32                     rotulos[w] = n_cconexo
33 
34 
35     return rotulos

Examples

1 from iacc_rod import iacc_rod

Equation

Performance Tests

Function is tested by running the tests defined at the page Connected Components Performance Test. The following code represent the steps to run these tests and show the results. Additionally, these information will also be summarized at the above page.

1. The module where the tests were subscribed must be imported. It's very important to run the SETUP(xsPackage, xsModule) function before executing the tests, as shown below:

Note: here you must choose between import BINARY or INFINITY WEIGHTED test module, according to the expected input of your function.

1 from iacc_test import objTestes_bin
2 #from iacc_test import objTestes_inf
3 
4 objTestes_bin.setup(xsPackage, xsModule)
5 #objTestes_inf.setup(xsPackage, xsModule)
  1. Then you subscribe your function and the post-processing methods (same way as previous versions of the PerfTest module):
1 listF = []
2 
3 listPP = []
4 posproc_1 = lambda x,y: y.max()
5 listPP.append(posproc_1)
6 
7 fnc_1 = ['Rodrigo', 'iacc_rod', lambda x:iacc_rod(x), listPP]
8 listF.append(fnc_1)

3. To finalize, run the tests using the imported test module object. Note: do not forget to configure the option output_format: rest, otherwise you will not visualize the results table.

1 objTestes_bin.runTests(listF)

gravando arquivo: /home/rubens/www/media/Attachments/iaOPF/iacc_rod/testperf.pkl

Autor Funcao Two components   500 phi=4/500   500 phi=0   500 phi=1  
Rodrigo iacc_rod 0.47 ms 2 28.264 ms 6 24.601 ms 500 1720.879 ms 1

References

[Feof2009]Paulo Feofiloff. Algoritmos para Grafos em C via Sedgewick. IME-USP. http://www.ime.usp.br/~pf/algoritmos_para_grafos

See also

Contributions

  • Rodrigo Dias, 1o semestre de 2012.