Function iacc_rob

Synopse

This function counts the number of connected components of a graph.

  • counter = iacc_rob(A)

    • Output

      • counter: The number of connected components. 'Inf' value means unconnected vertices.
    • Input

      • A: Adjacency matrix of a graph. 'Inf' value means unconnected vertices.

Description

This function counts the number of connected components of a graph using the Depth-First-Search (DFS) algorithm. The pseudo-code is shown below.

Algoritmo 1:

Function Code

 1 from  numpy import*
 2 
 3 global visited
 4 global graph
 5 
 6 # Function that counts the number of connected components
 7 def iacc_rob(A):
 8 
 9    global visited
10    global graph
11 
12    graph = A
13    visited= zeros(len(graph[0]))
14 
15    counter = 0
16    label = 0
17 
18    for i in range(len(graph[0])):
19       if (visited[i] == 0):
20          counter += 1
21          label += 1
22          iadfs_rob(i,label)
23 
24    return counter
25 
26 # Depth First Search Algorithm
27 ##########################################################################################
28 
29 def iadfs_rob(i,label):
30    global visited
31    global graph
32    visited[i] = label
33    neighbors = iafindConnectedVertices(i)
34 
35    for i in neighbors:
36       if (visited[i] == 0):
37          iadfs_rob(i,label)
38    return
39 
40 # Function that finds the vertices that are connected to a vertex i
41 ##########################################################################################
42 
43 def iafindConnectedVertices(i):
44    global graph
45    connected_vertices = where(graph[i,:]!=float('inf'))
46    return connected_vertices[0]

Examples

This example generates a random graph and counts its connected components

Example 1:

1 from courseIA368Q1S2012.rob_iarandgraph import iarandGraph
2 from courseIA368Q1S2012.wen_lib import adj2Graph
3 from iacc_rob import*
4 
5 
6 graph1 = iarandGraph(5,0.2)
7 mmgraphviz(adj2Graph(graph1), 'Rando graph with 5 vertices')
8 print('The number of connected components is %s' %iacc_rob(graph1))
The number of connected components is 2
/media/_xsb/iaOPF/iacc_rob/GRVIZ57551_001.png

Rando graph with 5 vertices

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_rob/testperf.pkl

Autor Funcao Two components   500 phi=4/500   500 phi=0   500 phi=1  
Roberto iacc_rob 0.263 ms 2 16.81 ms 6 11.443 ms 500 391.823 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

  • Roberto Souza, 1o semestre de 2012.