# Synopse

iacc_wes()

• cc = iacc_wes(A)

• cc: Numpy List. It's a list where:

[0] - list with levels of vertices [1] - number of connected components

• A: Numpy array. Matrix of adjacency that will be checked.

• Call of the function: iacc_wes(A)

## Description

iacc_wes: Connected Components in a Graph (adjacency matrix) using recursive depth first search.

Algoritmo 1:

## Function Code

``` 1 from numpy import *
2
3 #apresentando os vizinhos de cada vértice
4 def GrafoNeighborVertex(A,v):
5     indice=where(A[:,v]!=float('inf'))
6     return indice[0]
7
8 #função recursiva para a busca em profundidade
9 def dfsR(A,v,conta,lbl):
10   lbl[v]=conta
11   conta=conta+1
12   z = GrafoNeighborVertex(A,v)
13   for ve in z:
14     if lbl[ve]==-1:
15       dfsR(A,ve,conta,lbl)
16   return
17
20   V = range(A.shape[0])
21   lbl=[]
22   conta = 0
23   codgrafo = -1
24
25   for x in V:
26      lbl.append(-1);
27   for x in V:
28      if lbl[x]==-1:
29         dfsR(A,x,conta,lbl)
30         conta=0
31   return lbl
32
33
34 def iacc_wes(G):
36   return L, L.count(0)
```

## Example 1

``` 1 from iacc_wes import iacc_wes
2
3
4 A = array([[ Inf,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf],
5            [  5.,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf],
6            [  2.,   5.,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf],
7            [  3.,   2.,   5.,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf],
8            [  4.,  Inf,   2.,   5.,  Inf,  Inf,  Inf,  Inf,  Inf],
9            [  5.,   4.,  Inf,   2.,   5.,  Inf,  Inf,  Inf,  Inf],
10            [ Inf,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf,  Inf],
11            [ Inf,  Inf,  Inf,  Inf,  Inf,  Inf,   1.,  Inf,  Inf],
12            [ Inf,  Inf,  Inf,  Inf,  Inf,  Inf,   2.,   3.,  Inf]])
13
14 CC = iacc_wes(A)
15 print "Level of depth in each vertex = " +  str(CC[0])
16 print "Number of connected components = " + str(CC[1])
```
```Level of depth in each vertex = [0, 1, 2, 3, 4, 5, 0, 1, 2]
Number of connected components = 2
```

# Example 2:

Example using four different graphs. The results and the processing time are diplayed in a Table.

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

Autor Funcao Two components   500 phi=4/500   500 phi=0   500 phi=1
Wesley iacc_wes 0.2 ms 2 15.216 ms 6 11.214 ms 500 65.549 ms 1

## References

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

## Contributions

• Wesley Angelino de Souza, 1o semestre de 2012.