# Synopse

The iacc_and() function makes the labeling of a graph connected components.

• g = iacc_and(A)
• Output
• g: ndarray, 1D, integer, size=graph_order. Array where each position corresponds to a graph node. Each value point out the connected component to which the associated node belongs.
• Input
• A: ndarray, 2D, square. Adjacency matrix with 1/True where there is an edge/arc, and 0/False where there is not.

# Description

The iacc_and() function makes the labeling of a graph connected components by trying to build a spanning tree. The algorithm stops when the spanning tree is reached or if all edges/arcs are tested. It is based on a union-find procedure.

# Function Code

``` 1 def iacc_and(A):
2     from numpy import hstack, vstack, triu, tril, arange
3
4     m,n = A.shape
5     if not m==n:
6         return None
7
8     # get the list of edges
9     edges = vstack(triu(A).nonzero())
10
11     # initial node labels
12     labels = arange(n)
13     n -= 1
14     c = 0
15     for i in arange(edges.shape[1]):
16         u,v = (edges[0,i],edges[1,i])
17
18         # test if the edge {u,v} is not in the same connected component
19         if not labels[u]==labels[v]:
20             c += 1
21
22             # change label of node v
23             labels[labels==labels[v]] = labels[u]
24
25             # stop if reach one spanning tree
26             if c==n:
27                 break
28
29     return labels
```

# Examples

In a small graph with two connected components.

```1 A = array( [[0,1,1,0,0,0,0,0,0],
2             [1,0,0,0,0,0,0,1,0],
3             [1,0,0,1,0,0,0,1,0],
4             [0,0,1,0,0,0,0,1,0],
5             [0,0,0,0,0,1,1,0,0],
6             [0,0,0,0,1,0,1,0,1],
7             [0,0,0,0,1,1,0,0,1],
8             [0,1,1,1,0,0,0,0,0],
9             [0,0,0,0,0,1,1,0,0]], dtype=byte)
```
```1 from iacc_and import iacc_and
2
3 t = time.time()
4 l = iacc_and(A)
5 print 'Labels: ', l
6 print 'Number of components: ', len(set(l))
7 print 'Computational time: ', time.time() - t
```
```Labels:  [0 0 0 0 4 4 4 0 4]
Number of components:  2
Computational time:  0.00071907043457
```

In a random graph with order=2000 and avgDegree=2.

```1 G = randomGraph(2000,avgDegree=2)
2 t = time.time()
3 l = iacc_and(G)
4 print 'Number of components: ', len(set(l))
5 print 'Computational time: ', time.time() - t
```
```Number of components:  340
Computational time:  0.202105045319
```

In a random graph with order=2000 and avgDegree=200.

```1 G = randomGraph(2000,avgDegree=200)
2 t = time.time()
3 l = iacc_and(G)
4 print 'Number of components: ', len(set(l))
5 print 'Computational time: ', time.time() - t
```
```Number of components:  1
Computational time:  0.244961977005
```

# Performance Tests

Function is tested by running the tests defined at the page Connected Components Performance Test.

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

Autor Funcao Two components   500 phi=4/500   500 phi=0   500 phi=1
Andre iacc_and 0.23 ms 2 15.809 ms 6 7.5 ms 500 15.778 ms 1

# Contributions

• André Costa, 1o semestre de 2012.