# Synopse

Brief function synopse: This function returns the number of connected components of Graph together with the labels of each component

• array= iacc_fra(A)
• Output
• Array: List. Number of connected components and array of labels of each component whose size equals number of nodes in A.
• Input

# Description

Given an adjacency matrix A, the function returns the number of connected components and a an array of labels of each component, each element of this array is a node of A. The search for graph component is performed using recursive depth search algorithm.

# Function Code

``` 1 from numpy import *
2 from numpy.random import rand
3 from courseIA368Q1S2012.rob_iarandgraph import iarandGraph
4 from courseIA368Q1S2012.fra_t1 import ianeighvert
5
6
7 # calcula componente conexa a partir da matriz adjacencia
8
9 def iacc_fra (G):
10
11     def depths(G, lbl, v, id):
12         lbl[v] = id
15           lbl[v] = id
16           return id
18           if (lbl[a] == -1):
19             depths(G, lbl,a, id)
20         return id
21
22     #vetor de indices
23     ind=arange(G.shape[0])
24     label=[]
25     id = 0
26     for v in ind:
27         label.append(ind[v]);
28         label[v] = -1;
29     for r in ind:
30         if (label[r] == -1):
31           id=id+1
32           idx=depths(G, label,r, id);
33     t=id,label
34     return t;
```

# Examples

## Example 1: educative example

This example shows a simple matrix where Vertex 0 to 2 ara connected and vertex 3 to 5 are separetely connected.

``` 1 from iacc_fra import *
3
4 d=ones((6,6),int)
5 d=d*float("inf")
6 d[0,1]=1
7 d[0,2]=1
8 d[1,0]=1
9 d[1,2]=1
10 d[2,0]=1
11 d[2,1]=1
12 d[3,4]=1
13 d[3,5]=1
14 d[4,3]=1
15 d[4,5]=1
16 d[5,3]=1
17 d[5,4]=1
19 mmgraphviz(graph, 'Graph with 5 vertex')
20 print("")
21 print("")
22 print("Connected components")
23 cx=iacc_fra(d)
24 print(cx[0])
25 print("")
26 print("Component labels:")
27 print(cx[1])
```
```Connected components
2

Component labels:
[1, 1, 1, 2, 2, 2]
```

## Example 2- Complex Graph

This example shows a a very sparse adjacency matrix filled with only 5% of elements.

``` 1 graph = iarandGraph(20, 0.05,'yes')
3 mmgraphviz(graph1, 'Random Graph' )
4 print('\n')
5 print("Connected components")
6 cx=iacc_fra(graph)
7 print(cx[0])
8 print("")
9 print("Component labels:")
10 print(cx[1])
```
```Connected components
10

Component labels:
[1, 2, 3, 3, 4, 5, 2, 2, 6, 7, 3, 3, 8, 9, 3, 3, 10, 9, 2, 2]
```

## Test:

Test using four different graphs. The results and the processing time are diplayed in a Table. See also Performance test comparisson

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

Autor Funcao Two components   500 phi=4/500   500 phi=0   500 phi=1
Francisco iacc_fra 0.208 ms 2 12.522 ms 6 10.193 ms 500 68.514 ms 1

# References

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

Algoritmo 1: