Function iacc_and

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.