Function iacc_fra

Francisco Leite | Página Inicial

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
      • A: Array. Adjacency matrix.

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
13         adj=ianeighvert(G,v)
14         if (len(adj)==0):
15           lbl[v] = id
16           return id
17         for a in adj:
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 *
 2 from courseIA368Q1S2012.wen_lib import adj2Graph
 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
18 graph=adj2Graph(d)
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]
/media/_xsb/iaOPF/iacc_fra/GRVIZ54084_001.png

Graph with 5 vertex

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')
 2 graph1=adj2Graph(graph)
 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]
/media/_xsb/iaOPF/iacc_fra/GRVIZ54084_002.png

Random Graph

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

Algorithm

Algoritmo 1:

See also

A list of other related functions can be found on link below: