Function iacc_wes()

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.

Pseudocode

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 
18 #busca em profundidade
19 def BuscaProfundidade(A):
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):
35   L = BuscaProfundidade(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.