Discussion :

[zeinab ali]

bonjour
j'ai implémenté un algorithme de génération de réseau maillé lorsque le nombre de noeuds est petit par exemple n=10
le graphe apparait normal mais lorsque j'augmente le nombre de noeuds n=25 ou n=100 le graphe sera déformé les noeuds se placent en dessus des eux
s'il vous plait comment je peux modifier mon code pour que j'obtiens un résultat acceptable.
voici le 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
import re, random, os, sys, math
import networkx as nx
import pylab as P
import matplotlib.pyplot as plt
 
RADIUS = 15
 
TOPOBORDER = 60
 
class Topology:
 
	def __init__(self, inputTopo, outputTopo):
		self.inputTopo = inputTopo
		self.outputTopo = outputTopo
		return
 
 
	def getGraph(self):	
		return self.G.copy()
 
 
	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))
 
 
	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 = math.sqrt (float((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):
		nx.draw(self.G)
    		plt.savefig("path.png")
 
	def getParents(self, nodeid):
		neighbors= set()		
		for n in sorted([int(x) for x in self.G.nodes()]):
			if int(nodeid) != n:
				if nx.shortest_path_length(self.G, nodeid, int(n)) == 1:
					if nx.shortest_path_length(self.G, int(n)) < nx.shortest_path_length(self.G, int(nodeid)):
						neighbors.add(n)
		return neighbors
 
 
	def getChildren(self, nodeid):
		neighbors= set()		
		for n in sorted([int(x) for x in self.G.nodes()]):
			if int(nodeid) != n:
				if nx.shortest_path_length(self.G, nodeid, int(n)) == 1:
					if nx.shortest_path_length(self.G, int(n)) > nx.shortest_path_length(self.G, int(nodeid)):
						neighbors.add(n)
		return neighbors	
 
	def getNodes(self):
		return sorted([int(x) for x in self.G.nodes()])
 
 
	def getBrothers(self, nodeid):
		neighbors= set()		
		for n in sorted([int(x) for x in self.G.nodes()]):
			if int(nodeid) != n:
				if nx.shortest_path_length(self.G, int(nodeid), int(n)) == 1:
					if nx.shortest_path_length(self.G, int(n)) == nx.shortest_path_length(self.G, int(nodeid)):
						neighbors.add(int(n))
		return neighbors
 
	def getNeighbors(self, nodeid):
		neighbors= set()		
		for n in sorted([int(x) for x in self.G.nodes()]):
			if int(nodeid) != n:
				if nx.shortest_path_length(self.G, int(nodeid), int(n)) == 1:
							neighbors.add(int(n))
		return neighbors
 
 
	def get_parent_child(self, node1, node2):
	   		if nx.shortest_path_length(self.G, int(node1)) < nx.shortest_path_length(self.G, int(node2)):	
				return -1
	   		if nx.shortest_path_length(self.G, int(node1)) > nx.shortest_path_length(self.G, int(node2)):	
				return 1
			return 0
 
 
	def getNodes(self):	
		return self.G.nodes()

lorsque j'augmente le nombre des noeuds j'obtiens cette image à n=100
Merci d'avance