Function iacc_tia

Synopse

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

  • ccCounter = iacc_tia(M)

    • Input
      • M: Array Weighted Adjacency matrix of a graph.
    • Output
      • ccCounter: Number. Number of connected components of a graph

Description

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

Function Code

 1 from numpy import *
 2 from courseIA368Q1S2012.tia_libGraph import *
 3 
 4 
 5 '''
 6 ' Conta o numero de componentes conexos de um GRAFO
 7 '@param matrix Matriz de adjacência
 8 '@return Número de componentes conectados
 9 '''
10 def iacc_tia(M):
11     matrixCopy = triu(M.copy())
12     matrixCopy[matrixCopy==Inf]=0
13     matrixCopy = nan_to_num(matrixCopy)
14     nNodes = size(matrixCopy,0) #Numero de nós no grafo
15 
16     ccCounter = 0
17 
18     #Varre todos os nós do grafo procurando por nós não visitados
19     for i in range(nNodes):
20         neighbours = checkNeighbours(matrixCopy,i,False)
21         numberCC = deepNavigation(matrixCopy,i,neighbours)
22         if(numberCC > 0):
23             ccCounter = ccCounter + 1
24 
25     return ccCounter
/usr/local/lib/python2.6/dist-packages/scikits/__init__.py:1: UserWarning: Module dateutil was already imported from /usr/local/lib/python2.6/dist-packages/matplotlib-1.1.0-py2.6-linux-x86_64.egg/dateutil/__init__.pyc, but /usr/lib/pymodules/python2.6 is being added to sys.path
  __import__('pkg_resources').declare_namespace(__name__)

Performance Tests

('index must be either an int or a sequence',)

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

Autor Funcao Two components   500 phi=4/500   500 phi=0   500 phi=1
Tiago iacc_tia 0.805 ms 2 115.016 ms 6 46.539 ms 500 IndexError
Autor:tiagofrepereira
Data:05/07/2012