Function iadijkstra_rob

Synopse

This function implements Max-Dijkstra algorithm.

  • dist = iadijkstra_rob(graph,seed)

    • Output

      • dist: Distance vector containing the distances of each node with respect to the seed.
    • Input

      • graph: Weighted Adjacency matrix of the graph. 'Inf' value means unconnected vertices.
      • seed: Seed node that will be used as reference to calculate the distances from the other nodes in the graph.

Description

This function implements the single-source Max-Dijkstra algorithm.

Function Code

 1 from numpy import*
 2 
 3 
 4 def iadijkstra_rob(graph,seeds):
 5 
 6    dist = ones((2,len(graph[0])))*float('inf') #seta todas as distâncias igual a 'inf'
 7    dist[0,seeds] = seeds
 8    dist[1,seeds] = 0
 9 
10    Q = range(len(graph[0])) #vetor dos vértices do grafo
11 
12    while(Q):
13 
14       x = (dist[1,Q]).argmin()
15       u = Q[x] # seleciona o vértice com menor distância na fila Q
16 
17       if dist[1,u] == float('inf'):
18          break
19 
20       Q.remove(u) #Retira p índice da fila
21 
22       u_neighbors = findNeighbors(graph,u)
23 
24       for k in u_neighbors:
25          if k in Q:
26 
27             alt = maximum(dist[1,u], graph[u,k])
28 
29             if alt < dist[1,k]:
30                dist[1,k] = alt
31                dist[0,k] = dist[0,u]
32 
33 
34    return dist
35 
36 def findNeighbors(graph,i):
37    connected_vertices = where(graph[i,:]!=float('inf'))
38    return connected_vertices[0]

Examples

These examples apply Max-Dijkstra algorithm for a simple graph and also compares its processing time for graphs with different numbers of edges.

Example 1:

 1 from courseIA368Q1S2012.wen_lib import adj2Graph
 2 from iadijkstra_rob import*
 3 
 4 
 5 graph01 = array([[inf,3,inf,7,inf,inf,inf,inf,inf],[3,inf,2,inf,1,inf,inf,inf,inf],
 6 [inf,2,inf,inf,inf,11,inf,inf,inf],[7,inf,inf,inf,9,inf,5,inf,inf],
 7 [inf,1,inf,9,inf,4,inf,12,inf],[inf,inf,11,inf,4,inf,inf,inf,10],
 8 [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]])
 9 
10 
11 
12 dist = iadijkstra_rob(graph01, 0)
13 print 'Distances with respect to node 0: \n', dist
14 
15 mmgraphviz(adj2Graph(graph01), 'Simple Test Graph')
/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__)
Distances with respect to node 0: 
[[ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  3.  3.  7.  3.  4.  7.  7.  7.]]
/media/_xsb/iaOPF/iadijkstra_rob/GRVIZ17722_001.png

Simple Test Graph

Performance Test

These tests are imported from Optimum Path Test Page. Example using four different graphs. The results and the processing time are diplayed in a Table.

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

Autor Funcao Simple Test Graph   Complete(v =50)   Complete(v =100)   3 connected components  
Roberto iadijkstra_rob 0.81 ms 41.0 42.233 ms 476.028758628 277.023 ms 394.654708216 0.567 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

  • iaprim - Prim's algorithm implementatoion for finding MSTs

Contributions

  • Roberto Souza, 1o semestre de 2012.