Function iamstk_fer

Synopse

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

  • A = iamstk_fer(M)

    • Output
      • A: Array. Weighted Adjacency matrix of the MST
    • Input
      • M: Array. Weighted Adjacency matrix of a graph.

Description

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

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

If the adjacency matrix doesn't represents a weighted graph, the parameter w should be False. Also, this matrix should have a M[i][j] equals to 0, if there is no edge between i and j and 1, otherwise.

Function Code

 1 from courseIA368Q1S2012.fer_lib import Matrix2ListWithWeight
 2 from numpy import *
 3 from scipy.sparse import *
 4 import iaOPF
 5 
 6 def iamstk_fer(M):
 7     n = M.shape[1]
 8     R = range(0,n)
 9 
10     #seleciona matriz diagonal inferior para criar vetor de arestas
11     X = M.copy()
12     for i in range(M.shape[0]):
13         M[i][range(i)] = Inf
14 
15     A = Matrix2ListWithWeight(X)  # lista de arestas da matriz triangular superior do grafo M
16 
17     T = ones((n,n))*Inf
18 
19     V = [R[i:i+1] for i in range(0,n)] # vetor de componentes conexos
20 
21     # ordena lista de arestas quanto ao peso
22     A = sorted(A, key=lambda A:A[2])
23 
24     k=0
25     while(k<(n-1)):
26         a = A.pop(0)  # aresta minima
27 
28         # identifica os componentes conexos aos quais pertencem cada um dos vértices da aresta escolhida
29         for l in range(0,len(V)):
30             if(a[0] in V[l]):
31                 i1 = l
32             if(a[1] in V[l]):
33                 i2 = l
34 
35         # se vertice inicial e final pertencem a componentes conexos diferentes
36         if(i1!=i2):
37             T[a[0],a[1]] = a[2]    # marca aresta no grafo MST final
38             T[a[1],a[0]] = a[2]
39 
40             # transforma os 2 componentes conexos em um unico componente
41             V[i1].extend(V[i2])
42             V.pop(i2)
43 
44             k+=1
45 
46     return T

Examples

Example 1

Grafo com 5 vértices ponderado
Grafo= [[ Inf   2.   3.   1.  Inf]
 [  2.  Inf   2.   5.   3.]
 [  3.   2.  Inf  Inf   2.]
 [  1.   5.  Inf  Inf   1.]
 [ Inf   3.   2.   1.  Inf]]

Kruskal= [[ Inf   2.  Inf   1.  Inf]
 [  2.  Inf   2.  Inf  Inf]
 [ Inf   2.  Inf  Inf  Inf]
 [  1.  Inf  Inf  Inf   1.]
 [ Inf  Inf  Inf   1.  Inf]]
Custo do MST pelo Kruskal: 6.0
/media/_xsb/iaOPF/iamstk_fer/GRVIZ83523_001.png

Grafo 1

/media/_xsb/iaOPF/iamstk_fer/GRVIZ83523_002.png

Kruskal 1

Example 2:

Grafo com 7 vértices ponderado
Grafo= [[ Inf   7.  Inf   5.  Inf  Inf  Inf]
 [  7.  Inf   8.   9.   7.  Inf  Inf]
 [ Inf   8.  Inf  Inf   5.  Inf  Inf]
 [  5.   9.  Inf  Inf  15.   6.  Inf]
 [ Inf   7.   5.  15.  Inf   8.   9.]
 [ Inf  Inf  Inf   6.   8.  Inf  11.]
 [ Inf  Inf  Inf  Inf   9.  11.  Inf]]

Kruskal= [[ Inf   7.  Inf   5.  Inf  Inf  Inf]
 [  7.  Inf  Inf  Inf   7.  Inf  Inf]
 [ Inf  Inf  Inf  Inf   5.  Inf  Inf]
 [  5.  Inf  Inf  Inf  Inf   6.  Inf]
 [ Inf   7.   5.  Inf  Inf  Inf   9.]
 [ Inf  Inf  Inf   6.  Inf  Inf  Inf]
 [ Inf  Inf  Inf  Inf   9.  Inf  Inf]]
Custo do MST pelo Kruskal: 39.0
/media/_xsb/iaOPF/iamstk_fer/GRVIZ83523_003.png

Grafo 2

/media/_xsb/iaOPF/iamstk_fer/GRVIZ83523_004.png

Kruskal 2

Algorithm

Algoritmo 1:

Performance Tests

Function is tested by running the tests defined at the page Connected Components Performance Test. The following code represent the steps to run these tests and show the results. Additionally, these information will also be summarized at the above page.

1. The module where the tests were subscribed must be imported. It's very important to run the SETUP(xsPackage, xsModule) function before executing the tests, as shown below:

Note: here you must choose between import BINARY or INFINITY WEIGHTED test module, according to the expected input of your function.

 1 from iamcc_test import objTestes_inf
 2 from iamstk_fer import iamstk_fer
 3 
 4 
 5 objTestes_inf.setup(xsPackage, xsModule)
 6 
 7 listF = []
 8 
 9 listPP = []
10 posproc_1 = lambda x,y: y[y!=Inf].sum()/2
11 listPP.append(posproc_1)
12 
13 fnc_1 = ['Fernanda', 'iamstk_fer', lambda x:iamstk_fer(x), listPP]
14 listF.append(fnc_1)
/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__)
<type 'numpy.float64'>

3. To finalize, run the tests using the imported test module object. Note: do not forget to configure the option output_format: rest, otherwise you will not visualize the results table.

1 objTestes_inf.runTests(listF)

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

Autor Funcao A simple   A: rand(6,6)   100 nodes, complete   100 nodes, 0.5   Grafo MST  
Fernanda iamstk_fer 1.561 ms 9.0 2.288 ms 21.0 126.642 ms 318.055294457 77.431 ms 624.679654926 0.543 ms 139.0

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

  • Rodrigo Dias, 1o semestre de 2012.