Function iadijkstra_tia

Synopse

Input:
  • M Array: Adj. matrix
  • seedIndex Array: Seed node
Output:
  • costs Array: with the costs considering the seed

Description

Dijkstra algorithm considering the max function as cost.

Algorithm

Algoritmo 1:

Function Code

 1 from numpy import *
 2 from courseIA368Q1S2012.tia_libGraph import *
 3 
 4 def iadijkstra_tia(M,seedIndex):
 5 
 6     #Tratando matrizes com Inf
 7     matrixCopy = triu(copy(M))
 8     matrixCopy[matrixCopy==Inf]=0
 9     matrixCopy = nan_to_num(matrixCopy)
10 
11     currentNode = seedIndex
12 
13     numElements = shape(matrixCopy)[0]
14 
15     #Matrix de custo dos nos
16     costs = zeros(numElements)-1
17 
18     #Nós visitados
19     #visitedNodes = [False for i in range(numElements)]
20     visitedNodes = zeros(numElements)
21 
22     #Condicoes iniciais
23     costs[currentNode] = 0
24 
25     while(True):
26         #Visitando o nó
27         visitedNodes[currentNode] = True
28 
29         #Condição de parada Visitou todos os nós
30         if(sum(visitedNodes)==numElements):
31             break
32 
33         neighbours = checkNeighbours(matrixCopy,currentNode,isDigraph=False)
34 
35         for neighbour in neighbours:
36 
37             if(visitedNodes[neighbour]==1):
38                 continue
39 
40             #Condicao da matriz triangular superior
41             nodeA = min(currentNode,neighbour)
42             nodeB = max(currentNode,neighbour)
43 
44             #Soma
45             #possibleNewCost = costs[currentNode] + matrixCopy[nodeA][nodeB]
46 
47             #Usando fmax
48             possibleNewCost = max(costs[currentNode],matrixCopy[nodeA][nodeB])
49 
50             if((costs[neighbour]==-1)or(costs[neighbour]>=possibleNewCost)):
51                costs[neighbour] = possibleNewCost
52 
53         #Definindo o menor custo para o próximo passo que é o mínimo dos custos que NÃO foram visitados
54         nonVisited = where(visitedNodes==0)[0]
55         nonVisitedMajor0 = nonVisited[where(costs[nonVisited]>0)[0]]
56 
57         #Condição de parada. Grafo não conectado
58         if(len(nonVisitedMajor0)==0):
59             costs[0] = Inf
60             break
61 
62         currentNode = nonVisitedMajor0[argmin(costs[nonVisitedMajor0])]
63 
64 
65     return costs
/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

This function is tested by running the tests defined at the page Optimum Path Test.

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

Autor Funcao Simple Test Graph   Complete(v =50)   Complete(v =100)   3 connected components  
Tiago iadijkstra_tia 0.885 ms 41.0 12.892 ms 476.028758628 46.007 ms 394.654708216 0.731 ms inf
Autor:tiagofrepereira
Data:04/07/2012