Function iacc_thi

Synopse

iacc_thi - Using breadth first search, return the number of connected components and a list of nodes of each connected component splitted by lists.

  • n,cc = iacc_thi(M)

    • Output
      • n: Number. Number of connected components of a graph
      • cc: List. List with lists. Each list has the nodes from a connected component.
    • Input
      • M: Array. Weighted Adjacency matrix of a graph. 'Inf' indicates no edge.

Description

Using breadth first search, It finds the number of connected components and create a list that has as many lists as there are connected component. Each one has all nodes from the related to the latter.

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 import collections as col
 2 import numpy as np
 3 
 4 def iacc_thi(M):
 5 
 6     nV = M.shape[0]
 7     V = set(range(nV))
 8     L = col.deque()
 9     ccList = []
10     ccCount=0
11     label = [-1]*nV
12 
13     while V:
14         ccCount+=1
15         ccList.append([])
16         L.appendleft(V.pop())
17 
18         while L:
19             ccList[-1].append(L.pop())
20             neighV = np.where(M[ccList[-1][-1]] != np.inf)[0]
21             for i in neighV:
22                 if label[i] == -1:
23                     L.appendleft(i)
24                     label[i] = ccCount
25 
26             V = V.difference(neighV)
27 
28     return (ccCount,ccList)

Examples

Example 1

[[ Inf  Inf  10.  Inf  Inf]
 [ Inf  Inf  Inf  Inf  Inf]
 [ 10.  Inf  Inf   8.  Inf]
 [ Inf  Inf   8.  Inf  Inf]
 [ Inf  Inf  Inf  Inf  Inf]]
Numero de componentes do grafo1:  3
Vértices de cada componente separados por listas:  [[0, 2, 0, 3], [1], [4]]
/media/_xsb/iaOPF/iacc_thi/GRVIZ39203_001.png

Grafo1

Performance Tests

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

Autor Funcao Two components   500 phi=4/500   500 phi=0   500 phi=1  
Thiago iacc_thi 0.244 ms 2 14.63 ms 6 13.16 ms 500 96.397 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