Function iacc_fer

Synopse

iacc_fer - Count the number of connected components using breadth first search.

  • n = iacc_fer(M)

    • Output
      • n: Number. Number of connected components of a graph
    • Input
      • M: Array. Weighted Adjacency matrix of a graph. 'Inf' indicates no edge.

Description

Function that counts the number of connected components of a graph.

If the adjacency matrix represents a weighted graph, this matrix should have a M[i][j] equals to Inf, if there is no edge between i and j

Function Code

 1 from numpy import *
 2 
 3 def iacc_fer(M):
 4     n = 0
 5 
 6     V = range(0,M.shape[1])   # lista de vértices do grafo ainda nao visitados
 7     L = []                    # lista de vértices a serem visitados, pois são adjacentes a algum vértice ja visitado
 8 
 9     while (V):
10         L.append(V[0])
11 
12         while(L):
13             i = L.pop(0)
14             V.remove(i)
15             aux = getNeighbors(M,i)
16             L.extend(list((set(aux) - set(L)) & set(V)))     # adiciona vértices vizinhos, que ainda não foram acrescentados , nem visitados
17         n+=1
18 
19     return n
20 
21 # funçao que verifica quais os vizinhos do vertice v a partir de uma matriz de adjacência M
22 def getNeighbors(M,v):
23     r,c = where(M!=Inf)    # retorna indices que tenham o valor na matriz diferente de Inf
24     d = c[where(r==v)]  # determina quais valores de i satisfazem a condicao M[v,i]=1
25     e = r[where(c==v)]  # determina quais valores de i satisfazem a condicao M[i,v]=1
26     e = concatenate((d,e), axis=1)   # concatena os dois resultados: d, e
27     e = e.tolist()
28 
29     return list(set(e)) #retorna lista sem elementos duplicados

Examples

Example 1

Digrafo com 5 vértices ponderado
[[ Inf   2.   3.  Inf  Inf]
 [  1.  Inf   0.  Inf   1.]
 [ Inf   2.  Inf  Inf   2.]
 [ Inf  Inf  Inf  Inf  Inf]
 [ Inf   3.  Inf   1.  Inf]]
Numero de componentes do digrafo 1
1
/media/_xsb/iaOPF/iacc_fer/GRVIZ34806_001.png

digrafo 1

Example 2:

Digrafo com 5 vértices ponderado
[[ Inf   2.   3.  Inf  Inf]
 [  1.  Inf   0.  Inf  Inf]
 [ Inf   2.  Inf  Inf  Inf]
 [ Inf  Inf  Inf  Inf  Inf]
 [ Inf  Inf  Inf   1.  Inf]]
Numero de componentes do digrafo 2
2
/media/_xsb/iaOPF/iacc_fer/GRVIZ34806_002.png

digrafo 2

Example 3:

Digrafo com 5 vértices ponderado
[[ Inf   2.   3.  Inf  Inf]
 [  1.  Inf   0.  Inf  Inf]
 [ Inf   2.  Inf  Inf  Inf]
 [ Inf  Inf  Inf  Inf  Inf]
 [ Inf  Inf  Inf   1.  Inf]]
Numero de componentes do digrafo 3
2
/media/_xsb/iaOPF/iacc_fer/GRVIZ34806_003.png

digrafo 2

Algorithm

Algoritmo 1:

Performance Tests

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

Autor Funcao Two components   500 phi=4/500   500 phi=0   500 phi=1  
Fernanda iacc_fer 0.395 ms 2 2751.604 ms 6 2712.881 ms 500 7402.395 ms 1

References

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

See also

Contributions

  • Fernanda Brandao Silva, 1o semestre de 2012.