Function iadijkstra_rod

Synopse

iadijkstra_rod - Optimum Path with Dijkstra algoritm.

  • a = iadijkstra_rod(A)

    • a: Boolean. TRUE if matrix A is symmetric or FALSE otherwise.

    • A: Numpy array. Matrix that will be checked. Valor 'Inf'

      indica .

Description

Function finds the connected components of the adjacency matrix and return a labeled adjacency matrix.

Function Code

 1 from numpy import *
 2 
 3 def iadijkstra_rod(W, root = 0):
 4     #Numero de vertices do grafo
 5     n_vert = W.shape[0]
 6 
 7     #Array com custos mínimos até cada vértice. Inicializa em infinito
 8     v_min = ones(n_vert)*inf
 9 
10     #Lista de vértices ainda não visitados (pendentes). Inicializa com todos
11     v_pend = range(n_vert)
12 
13     #Inicializa zerando a distância a semente (que será zero)
14     v_min[root] = 0
15 
16     #Enquanto houverem vértices ainda não visitados
17     while len(v_pend) > 0:
18         #Retorna o índice (relativo a lista de vértices não-visitados) de menor custo
19         indice_menor = argmin(v_min[ v_pend ])
20 
21         #Remove da lista retornando qual o vértice
22         vertice = v_pend.pop(indice_menor)
23 
24         #Pega o custo até o vértice atual
25         custo_v = v_min[vertice]
26 
27         #Pega a lista das distâncias do vértice a todos os outros.
28         w_viz = W[:,vertice]
29 
30         #Calcula novo custo para todos os vizinho, a partir do vertice atual
31         custo_viz = maximum(custo_v, w_viz)
32 
33         #Atualiza o vetor de custos mínimos (melhores caminhos)
34         v_min = minimum(v_min, custo_viz)
35 
36     return v_min

Examples

 1 from iadijkstra_rod import iadijkstra_rod
 2 
 3 #Monta matriz de Pesos
 4 W=array([[0.0,1,0,2,0,0,0,0,0],
 5    [1,0,7,0,9,0,0,0,0],
 6    [0,7,0,0,0,8,0,0,0],
 7    [2,0,0,0,6,0,10,0,0],
 8    [0,9,0,6,0,12,0,11,0],
 9    [0,0,8,0,12,0,0,0,5],
10    [0,0,0,10,0,0,0,4,0],
11    [0,0,0,0,11,0,4,0,3],
12    [0,0,0,0,0,5,0,3,0]])
13 W[ W==0 ] = inf
14 print W
15 
16 D = iadijkstra_rod(W, 0)
17 print D
18 
19 graph01 = array([[inf,3,inf,7,inf,inf,inf,inf,inf],[3,inf,2,inf,1,inf,inf,inf,inf],
20 [inf,2,inf,inf,inf,11,inf,inf,inf],[7,inf,inf,inf,9,inf,5,inf,inf],
21 [inf,1,inf,9,inf,4,inf,12,inf],[inf,inf,11,inf,4,inf,inf,inf,10],
22 [inf,inf,inf,5,inf,inf,inf,2,inf],[inf,inf,inf,inf,12,inf,2,inf,6],[inf,inf,inf,inf,inf,10,inf,6,inf]])
23 
24 print graph01
25 
26 D2 = iadijkstra_rod(graph01, 0)
27 print sum(D2)
[[ Inf   1.  Inf   2.  Inf  Inf  Inf  Inf  Inf]
 [  1.  Inf   7.  Inf   9.  Inf  Inf  Inf  Inf]
 [ Inf   7.  Inf  Inf  Inf   8.  Inf  Inf  Inf]
 [  2.  Inf  Inf  Inf   6.  Inf  10.  Inf  Inf]
 [ Inf   9.  Inf   6.  Inf  12.  Inf  11.  Inf]
 [ Inf  Inf   8.  Inf  12.  Inf  Inf  Inf   5.]
 [ Inf  Inf  Inf  10.  Inf  Inf  Inf   4.  Inf]
 [ Inf  Inf  Inf  Inf  11.  Inf   4.  Inf   3.]
 [ Inf  Inf  Inf  Inf  Inf   5.  Inf   3.  Inf]]
[ 0.  1.  7.  2.  6.  8.  8.  8.  8.]
[[ Inf   3.  Inf   7.  Inf  Inf  Inf  Inf  Inf]
 [  3.  Inf   2.  Inf   1.  Inf  Inf  Inf  Inf]
 [ Inf   2.  Inf  Inf  Inf  11.  Inf  Inf  Inf]
 [  7.  Inf  Inf  Inf   9.  Inf   5.  Inf  Inf]
 [ Inf   1.  Inf   9.  Inf   4.  Inf  12.  Inf]
 [ Inf  Inf  11.  Inf   4.  Inf  Inf  Inf  10.]
 [ Inf  Inf  Inf   5.  Inf  Inf  Inf   2.  Inf]
 [ Inf  Inf  Inf  Inf  12.  Inf   2.  Inf   6.]
 [ Inf  Inf  Inf  Inf  Inf  10.  Inf   6.  Inf]]
41.0

Equation

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 iaoptpath_test import objTestes
2 
3 objTestes.setup(xsPackage, xsModule)
/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__)
  1. Then you subscribe your function and the post-processing methods (same way as previous versions of the PerfTest module):
1 listF = []
2 listPP = []
3 
4 pp_soma = lambda x,y: sum(y)
5 listPP.append(pp_soma)
6 
7 fnc_1 = ['Rodrigo', 'iadijkstra_rod', lambda x:iadijkstra_rod(x,0), listPP]
8 listF.append(fnc_1)

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.runTests(listF)

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

Autor Funcao Simple Test Graph   Complete(v =50)   Complete(v =100)   3 connected components  
Rodrigo iadijkstra_rod 0.415 ms 41.0 1.787 ms 488.129970057 3.381 ms 417.759426795 0.335 ms inf

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.