iadijkstra_fra

Francisco Leite | Página Inicial

Synopse

Brief function synopse: This function returns the least cost path between two vertices t e s, using Dijkstra algorithm with a modified connectivity function.

Input:
  • G - Adjacency matrix
  • t - target vertex
  • s - root vertex
Output:
  • Cost - cost between t and s
  • Path - pathcost between t and s
  • Vertex - vertex offering the best cost

Description

Given an adjacency matrix A and a connectivity function assigning a value from root vertex s to target vertex t. The function returns the cost from vertex t to s performing a maximization between vertex cost and path cost.

The functions accepts multiple seeds, in which case, t shall receive the list of multiple seeds and s the target vertex.

Function Code

 1 from numpy import *
 2 from iacc_fra import ianeighvert
 3 
 4 
 5 def iadijkstra_fra(G, t, s):
 6     sizeG=G.shape[0]
 7     d = {}
 8     previous = {}
 9     for v in arange(sizeG):
10         d[v] = float('inf') # infinity
11         previous[v] = None
12     del v
13     d[s] = 0
14     S = []
15 
16     Q = list(arange(sizeG))
17 
18     def ExtractCheapest(Q):
19         m = None
20         md = None
21         for u in Q:
22             if m is None:
23                 m = u
24                 md = d[u]
25             else:
26                 if d[u] < md:
27                      md = d[u]
28                      m = u
29         Q.remove(m)
30         return m
31 
32     while Q:
33         u = ExtractCheapest(Q)
34 
35         S.append(u)
36         ngb=ianeighvert(G,u)
37 
38         for v in ngb:
39             mxd=max(d[u],G[u,v])
40 
41             if mxd < d[v]:
42                 d[v] = mxd
43                 previous[v] = u
44 
45     C=[]
46     S=[]
47     CC=[]
48 
49     for i in range(len(t)):
50         Sc = []
51         u = t[i]
52         while previous[u] is not None:
53             Sc.insert(0, u)
54             u = previous[u]
55         C.append(d[t[i]])
56         CC.append(len(Sc))
57         S.append(t[i])
58     soma=0.0
59     for j in arange(sizeG):
60         soma=soma+d[j]
61 
62     return C,CC,S,soma

Example

Example 1

Simple graph o illustrate function usage

 1 from iadijkstra_fra import *
 2 from courseIA368Q1S2012.wen_lib import adj2Graph
 3 
 4 graph01 = array([[inf,3,inf,7,inf,inf,inf,inf,inf],[3,inf,2,inf,1,inf,inf,inf,inf],
 5 [inf,2,inf,inf,inf,11,inf,inf,inf],[7,inf,inf,inf,9,inf,5,inf,inf],
 6 [inf,1,inf,9,inf,4,inf,12,inf],[inf,inf,11,inf,4,inf,inf,inf,10],
 7 [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]])
 8 
 9 graph=adj2Graph(graph01)
10 mmgraphviz(graph, 'Graph with 8 nodes used in classroom')
11 r1=iadijkstra_fra(graph01,[8],0)
12 print ("One seed")
13 print ("Sum:")
14 print (r1[3])
15 r1=iadijkstra_fra(graph01,[0,3],8)
16 print ("Two seeds")
17 print ("Sum:")
18 print (r1[3])
19 print ("Cost per path to reach target node 8")
20 print (r1[0])
21 print ("Number of nodes in path")
22 print (r1[1])
23 print ("ID o each node in above lists")
24 print (r1[2])
One seed
Sum:
41.0
Two seeds
Sum:
53.0
Cost per path to reach target node 8
[7.0, 6.0]
Number of nodes in path
[4, 3]
ID o each node in above lists
[0, 3]
/media/_xsb/iaOPF/iadijkstra_fra/GRVIZ55731_001.png

Graph with 8 nodes used in classroom

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

Autor Funcao Simple Test Graph   Complete(v =50)   Complete(v =100)   3 connected components  
Francisco iadijkstra_fra 0.355 ms 41.0 5.968 ms 488.129970057 21.272 ms 417.759426795 0.372 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

A list of other related functions can be found on link below: