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
|
# -*-coding:Latin-1 -*
import networkx as nx
import random
import fonction_base as fb
import time
from threading import Thread
import time
temps1 = time.clock()
g=nx.readwrite.read_gpickle("testPartiel.graph")
cg = fb.comp_connexe(g)
#cg = nx.connected_component_subgraphs(g)[0] # /!\ on ne prend que la premiere composante connexe
product=list()
customers=list()
print "création des listes de neouds"
for n in cg.nodes():
if type(n) == int:
product.append(n)
else:
customers.append(n)
print "nombre de produits", len(product)
print "nombre de customers", len(customers)
product_graph=nx.Graph(name="product")
product_graph.add_nodes_from(product)
customers_graph=nx.Graph(name="customers")
customers_graph.add_nodes_from(customers)
print "construction des dicos"
# build a neighbors (products) dictionnary
prod_neighbors={}
for a in product:
prod_neighbors[a]=cg.neighbors(a)
# build a neighbors (customers) dictionnary
cust_neighbors={}
for c in customers:
cust_neighbors[c]=cg.neighbors(c)
#product_indice=0
nbprod = len(product)
def diviseIntervalle(longueur, nbinter):
intervalles = [] #liste de bornes
pas = longueur/nbinter #l=21, nb=4, pas=5
intervalles.append([0,pas])#[0,5]
for i in range(1,(longueur/pas)-1): #i=1 a 4
intervalles.append([i*(pas)+1,(i+1)*(pas)]) #[6,10] [11,15] [16,20]
intervalles.append([((longueur/pas)-1)*(pas)+1,longueur-1])
#intervalles.append([(longueur/pas)*pas+1,longueur-1])
return intervalles
intervalles = diviseIntervalle(nbprod,5)
print "nombre d'intervalles", len(intervalles)
dictthreads = {}
def forthread(nb1,nb2,numthread):
global product
global prod_neighbors
global cust_neighbors
global product_graph
global dictthreads
listearretes = []
for i in range(nb1,nb2):
print numthread
x=product[i]
for y in prod_neighbors[x]:
for z in cust_neighbors[y]:
nbCommuns = len(set(prod_neighbors[x]) & set(prod_neighbors[z]));
if nbCommuns > 0:
listearretes.append([(x,z,nbCommuns)])
#product_graph.add_weighted_edges_from([(x,z,nbCommuns)]) #tenter de liste les edges pour chaqe thread et de construire le graphe ensuite
dictthreads[numthread] = listearretes
print "lancement des threads"
listethreads = {}
for i in range(0,len(intervalles)):
listethreads[i] = Thread(None, forthread, None, (intervalles[i][0],intervalles[i][1],i), {})
listethreads[i].start()
print "fin du lancement des threads, au nombre de ", len(listethreads.keys())
for i in range(0,len(intervalles)):
listethreads[i].join()
#listethreads[i]._Thread__stop()
print "ajout d'un lot d'arretes numéro ", i+1, "en contenant ", len(dictthreads[i])
for j in range(0,len(dictthreads[i])):
product_graph.add_weighted_edges_from(dictthreads[i][j])
print "fin de l'ajout d'arrêtes"
#print "construction cust"
#for x in customers:
#print "plop ",product_indice
#product_indice=product_indice+1
#if len(prod_neighbors[x]) > 1:
# add_clique(customers_graph,prod_neighbors[x])
#for y in cust_neighbors[x]:
#for z in prod_neighbors[y]:
#nbCommuns = len(set(cust_neighbors[x]) & set(cust_neighbors[z]));
#if nbCommuns > 0:
#customers_graph.add_weighted_edges_from([(x,y,nbCommuns)])
#rq: construire custumer prend 5 fois plus de temps à nb_prod= 5k
#complexité supposée : n^3
#Pour 1K : 2s
#pour 2.5k : 5s
#pour 5k : 20s
#pour 10k : 64s
subgraphprod = fb.comp_connexe(product_graph)
nx.readwrite.write_gpickle(subgraphprod,"productPartiel.graph")
nx.readwrite.write_gpickle(customers_graph,"customers.graph")
print "Le nombre de liens est de ",len(subgraphprod.edges()) ## liens
print "Le nombre de noeuds est de ",len(subgraphprod.nodes()) ## noeuds
print "La densité est de ", nx.density(subgraphprod) #densite
#print "Le diamètre est de ", nx.diameter(subgraph) #diametre
#print product_graph.nodes()
#print product_graph.edges(data=True)
duree = time.clock() - temps1
print "Durée : ", duree |
