Discussion :

[zeinab ali]

Bonsoir
je veux obtenir la matrice de coût d'un graphe de réseau maillé sachant que le coût est le nombre des sauts entre deux noeuds.
je veux que le coût entre deux nœuds soit minimal.Donc svp je veux vous interroger est ce que j'utilise cette fonction single_source_dijkstra_path ou bien la fonction nx.shortest_path_length(G, xi, xj)
Merci d'avance
cordialement

[dividee]

A priori, la fonction que tu veux... mais certaines seront plus efficaces que d'autres.

Tu sembles utiliser la libraire networkx, tu as pas mal de choix possibles.

Il y a des variantes pour calculer les plus courts chemins:

• depuis un sommet donné vers un autre sommet donné
• depuis un sommet donné vers tous les autres
• entre toutes les paires de sommets

Tu as aussi des variantes plus efficaces si le graphe est dense (càd si la plupart des paires de sommets sont connectés par un arête).

En fonction de ce que tu as besoin, à toi de voir quelle variante te convient le mieux.

[zeinab ali]

A priori, la fonction que tu veux... mais certaines seront plus efficaces que d'autres.

Tu sembles utiliser la libraire networkx, tu as pas mal de choix possibles.

Il y a des variantes pour calculer les plus courts chemins:

• depuis un sommet donné vers un autre sommet donné
• depuis un sommet donné vers tous les autres
• entre toutes les paires de sommets

Tu as aussi des variantes plus efficaces si le graphe est dense (càd si la plupart des paires de sommets sont connectés par un arête).

En fonction de ce que tu as besoin, à toi de voir quelle variante te convient le mieux.

merci bien pour la réponse
j'utilise la troisiéme variante(entre toutes les paires des sommets)
voici mon code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
def get_matrix(self):
                path_length=nx.all_pairs_shortest_path_length(self.G)
                n = len(self.G.nodes())
                distances=np.zeros((n,n))
                for u,p in path_length.iteritems():
                        for v,d in p.iteritems():
                                distances[int(u)-1][int(v)-1] = d
                return distances

mais j'ai obtenu une matrice d'adjacence qui ne corresponde pas au graphe
Merci d'avance
cordialement

[dividee]

Le résultat du calcul ne te donne pas une matrice d'adjacence, mais une matrice de coût (comme tu l'as d'ailleurs appelé dans ton post initial). Si tu l’interprètes comme la matrice d'adjacence d'un graphe, cela te donnera un graphe complet si ton graphe d'origine est connexe.

Le bout de code que tu as posté me semble correct, si ta matrice de coût n'est pas celle que tu attendais vérifie que le graphe en entrée est bien celui que tu crois.

[zeinab ali]

Le résultat du calcul ne te donne pas une matrice d'adjacence, mais une matrice de coût (comme tu l'as d'ailleurs appelé dans ton post initial). Si tu l’interprètes comme la matrice d'adjacence d'un graphe, cela te donnera un graphe complet si ton graphe d'origine est connexe.

Le bout de code que tu as posté me semble correct, si ta matrice de coût n'est pas celle que tu attendais vérifie que le graphe en entrée est bien celui que tu crois.

je vous remercie infiniment pour vos réponses.
en fait,moi je créer un graphe de réseau maillé aléatoire s'il vous plait merci de vérifier avec moi cet code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
import re, random, os, sys, math
import networkx as nx
import pylab as P
import matplotlib.pyplot as plt
import numpy as np
 
RADIUS = 60
TOPOBORDER = 15
 
class Topology:
 
	def __init__(self, inputTopo, outputTopo, sink):
		self.inputTopo = inputTopo
		self.outputTopo = outputTopo
		self.sink=sink
		return
 
 
	def getGraph(self):	
		return self.G.copy()
 
 
	def generateAvroraTopoFromTossimTop(self, inputTopo, outputTopo):
		self.Positions = {}
		self.G = nx.Graph()
		f = open(inputTopo, "r")
		for l in [x.strip() for x in f.readlines()]:
			if len(l)>0:
                                parts = l.split('	')
				print parts[1], parts[2]
				self.G.add_edge(int(parts[1]),int(parts[2]))
 				self.G.add_edge(int(parts[2]),int(parts[1])) 		 	
 		for node in self.G.nodes():
			if node not in self.Positions.keys():
				while True:
					random.seed()
					x0 = random.randint(0,TOPOBORDER)
					y0 = random.randint(0,TOPOBORDER)
					if self.validatePosition(node, x0, y0) == True:
						self.Positions[node] = (x0,y0)
						print self.Positions
						break	
			else:
				print self.Positions
 		print self.Positions		
		return
 
 
	def generateAvrorTopo(self):
		print "Avrora Topo"
		if len(self.outputTopo) != 0:		
			f = open(self.outputTopo+".avr", "w")
			for node in self.Positions.keys():
				(x,y) = self.Positions[node]
				f.write("node%d  %d  %d  0\n"%(node, x, y)) 				
			f.close()
 
 
 
	def generateTossimTopo(self):
		if len(self.outputTopo) != 0:
			f = open(self.outputTopo+".tos", "w")
			for node in self.G.nodes():
				for neighbor in self.getNeighbors(node):
					f.write("gain	%d	%d	0\n"%(node, neighbor)) 
				f.write("\n")
				f.write("\n")  
			f.close()
 
 
	def generateTopNodeDegree(self, numNodes, degree):
		if len(self.inputTopo) == 0:
			self.numNodes = numNodes
			if (degree != None):
			    self.randomByDegree(degree)
		else:
			print "I am here"
			f = open(self.inputTopo+".avr", "r")
			self.Positions = {}
			for l in [x.strip() for x in f.readlines()]:
				if (l.rfind('node')!=-1):
					s = l.split("  ")
					node = int(s[0].split("node")[1])
					self.Positions[node] = (int(s[1]), int(s[2]))
 
					#self.G.add_edge(int(s[0]), int(s[1]),{'color':'blue'})
 
   		        self.G = nx.Graph()
			for n0 in self.Positions.keys():
				(x0,y0) = self.Positions[n0]
				self.G.add_node(n0)
				for n1 in self.Positions.keys():
				    (x1,y1) = self.Positions[n1]
				    if n1==n0:
					continue
				    d = (x1-x0)**2+(y1-y0)**2
				    if (d<=RADIUS**2):
					self.G.add_edge(max(n0, n1),min(n0,n1))
 
		self.generateAvrorTopo()
		#self.generateTossimTopo()
 
	def random(self,X,Y):		
                while (True):		    
                        print 'Generating %dx%d random topology...'%(X,Y)
                        random.seed()
                        self.G = nx.Graph()
                        self.Positions = {}
                        for i in range(int(self.numNodes)):
				ix = random.randint(0,X)
				iy = random.randint(0,Y)
				self.Positions[i] = (ix,iy)
 
                        degMean = 0
                        for n0 in self.Positions.keys():
                                (x0,y0) = self.Positions[n0]
                                self.G.add_node(n0)
                                for n1 in self.Positions.keys():
                                        (x1,y1) = self.Positions[n1]
 
                                        if n1==n0:
                                                continue
                                        d = (x1-x0)**2+(y1-y0)**2
                                        if (d<=RADIUS**2):
                                                self.G.add_edge(max(n0, n1),min(n0,n1), style='dashed')
                                degMean += self.G.degree(n0)
 
                        components = [comp for comp in nx.connected_components(self.G)]
                        component_size = [len(comp) for comp in components]
                        print component_size
 
                        if (len(component_size)==1):
                                break
 
                        print "Graph is not connected"
 
                print "Effective density=%.2f"%(float(degMean)/len(self.Positions.keys()))
                #if (self.includeIntruder == 1):
                print 'Topology generated !'
 
 
	def randomByDegree(self,degree):
		x = int(math.sqrt(self.numNodes*math.pi*(RADIUS-1.5)**2/(degree)))
		y = x
		self.random(x,y)
 
	def draw(self):
                pos=nx.spring_layout(self.G)   
		nx.draw(self.G,pos,with_labels=True)
    		plt.savefig("path_topo.png")
 
 
	def getEdges(self):
                print self.G.edges()
        def get_nb_nodes(self):
                print self.G.number_of_nodes()
        def get_nb_edges(self):
                print self.G.number_of_edges()
        def get_matrix(self):
                path_length=nx.all_pairs_shortest_path_length(self.G)
                n = len(self.G.nodes())
                distances=np.zeros((n,n))
                for u,p in path_length.iteritems():
                        for v,d in p.iteritems():
                                distances[int(u)-1][int(v)-1] = d
                return distances

et par la suite je veux calculer la matrice de coût .s'il vous plait pouvez voire mes résultats la matrice de coût obtenu ne correspond pas au graphe.

[dividee]

OK, c'est le "- 1" qui est de trop, vu que tes nœuds sont numérotés à partir de 0:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
...
for u,p in path_length.iteritems():
    for v,d in p.iteritems():
        distances[int(u)][int(v)] = d

[zeinab ali]

OK, c'est le "- 1" qui est de trop, vu que tes nœuds sont numérotés à partir de 0:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
...
for u,p in path_length.iteritems():
    for v,d in p.iteritems():
        distances[int(u)][int(v)] = d

merci beaucoup ca marche correctement