4 # Un graphe c'est un hachage nodes et un hachage edges avec trucs dedans
5 # nodes{nom}{type}, nodes{nom}{X}, nodes{nom}{Y}, nodes{nom}{in}, nodes{nom}{out} par exemple
6 # edges{nom}{src}, edges{nom}{dst}, edges{nom}{type}, edges{nom}{delay}, edges{nom}{bw}
10 my(%nodes,%edges); # a new graph...
11 return(\%nodes,\%edges);
15 my($nodes,$edges,$name) = @_;
16 $$nodes{$name}{name}=$name;
17 $$nodes{$name}{type}=2;
21 my($nodes,$edges,$src,$dst) = @_;
22 my($edge_count)=scalar(keys(%{$edges}));
23 $$edges{$edge_count}{src}=$src;
24 $$edges{$edge_count}{dst}=$dst;
25 # $$edges{$edge_count}{delay} = $delay;
26 # $$edges{$edge_count}{bw} = $bw;
27 # $$edges{$edge_count}{type} = $type;
28 # $$edges{$edge_count}{using_path} = [];
29 $$nodes{$src}{out}{$dst} = $edge_count;
30 $$nodes{$dst}{in}{$src} = $edge_count;
31 $$nodes{$dst}{out}{$src} = $edge_count;
32 $$nodes{$src}{in}{$dst} = $edge_count;
37 my($nodes,$edges,$src,$dst) = @_;
38 my($edge_count)=scalar(keys(%{$edges}));
39 $$edges{$edge_count}{src}=$src;
40 $$edges{$edge_count}{dst}=$dst;
41 # $$edges{$edge_count}{delay} = $delay;
42 # $$edges{$edge_count}{bw} = $bw;
43 # $$edges{$edge_count}{type} = $type;
44 # $$edges{$edge_count}{using_path} = [];
45 $$nodes{$src}{out}{$dst} = $edge_count;
46 $$nodes{$dst}{in}{$src} = $edge_count;
50 sub G_simgrid_export {
51 my($nodes,$edges,$filename) = @_;
55 open MSG_OUTPUT, "> $filename";
57 print MSG_OUTPUT "HOSTS\n";
58 foreach $u (keys %{$nodes}) {
59 if (!((defined($$nodes{$u}{host}))&&($$nodes{$u}{host}==1))) { next; }
60 if (!((defined($$nodes{$u}{Mflops}))&&($$nodes{$u}{host}==1))) {
61 die "Lacking Mflops for $u\n";
63 print MSG_OUTPUT "$u $$nodes{$u}{Mflops}\n";
66 print MSG_OUTPUT "LINKS\n";
67 foreach $e (keys %{$edges}) {
68 (defined($$edges{$e}{bw})) or die "Lacking bw for $u\n";
69 (defined($$edges{$e}{delay})) or die "Lacking bw for $u\n";
70 print MSG_OUTPUT "$e $$edges{$e}{bw} $$edges{$e}{delay}\n";
72 print MSG_OUTPUT "ROUTES\n";
73 foreach $u (@host_list){
74 foreach $v (@host_list){
79 my($next) = $$nodes{$w}{shortest_route}{$v};
80 $e = $$nodes{$w}{out}{$next};
84 print MSG_OUTPUT "$u $v (@path)\n";
91 sub G_surfxml_export {
92 my($nodes,$edges,$filename) = @_;
96 open MSG_OUTPUT, "> $filename";
98 print MSG_OUTPUT "<?xml version='1.0'?>\n";
99 print MSG_OUTPUT "<!DOCTYPE platform_description SYSTEM \"surfxml.dtd\">\n";
100 print MSG_OUTPUT "<platform_description>\n";
102 foreach $u (keys %{$nodes}) {
103 if (!((defined($$nodes{$u}{host}))&&($$nodes{$u}{host}==1))) { next; }
104 if (!((defined($$nodes{$u}{Mflops}))&&($$nodes{$u}{host}==1))) {
105 die "Lacking Mflops for $u\n";
107 print MSG_OUTPUT " <cpu name=\"$$nodes{$u}{name}\" power=\"$$nodes{$u}{Mflops}\"/>\n";
110 foreach $e (keys %{$edges}) {
111 (defined($$edges{$e}{bw})) or die "Lacking bw for $u\n";
112 (defined($$edges{$e}{delay})) or die "Lacking bw for $u\n";
114 $lat = $$edges{$e}{delay} / 1000;
115 print MSG_OUTPUT " <network_link name=\"$e\" bandwidth=\"$$edges{$e}{bw}\" latency=\"$lat\"/>\n";
117 foreach $u (@host_list){
118 foreach $v (@host_list){
123 my($next) = $$nodes{$w}{shortest_route}{$v};
124 $e = $$nodes{$w}{out}{$next};
128 print MSG_OUTPUT " <route src=\"$$nodes{$u}{name}\" dst=\"$$nodes{$v}{name}\">";
130 print MSG_OUTPUT "<route_element name=\"$w\"/>";
132 print MSG_OUTPUT " </route>\n";
136 print MSG_OUTPUT "</platform_description>\n";
140 ##############################
141 ### GRAPH ALGORITHMS ###
142 ##############################
145 my($nodes,$edges) = @_;
151 my(@node_list) = sort (keys %$nodes);
152 my($n) = scalar(@node_list);
154 my($u,$v,$w,$step,$e);
156 foreach $u (@node_list){
157 foreach $v (@node_list){
158 $connexion{$u}{$v} = 0;
159 $distance{$u}{$v} = 0;
160 $shortest{$u}{$v} = -1;
164 foreach $e (sort (keys %$edges)){
165 my($x1)=$$edges{$e}{src};
166 my($x2)=$$edges{$e}{dst};
167 $connexion{$x1}{$x2} = $connexion{$x2}{$x1} = 1;
168 $distance{$x1}{$x2} = $distance{$x2}{$x1} = 1;
169 $shortest{$x1}{$x2} = $x2;
170 $shortest{$x2}{$x1} = $x1;
173 # print_matrix(\%connexion);
174 # matrix2viz(\%connexion);
176 foreach $step (0..$n-1){
178 foreach $u (@node_list){
179 foreach $v (@node_list){
180 foreach $w (@node_list){
181 if(($connexion{$u}{$w} != 0)
182 && ($distance{$w}{$v}!=0)
183 && (($distance{$u}{$v} >
184 $distance{$u}{$w} + $distance{$w}{$v}) || ($distance{$u}{$v}==0))
187 $distance{$u}{$w} + $distance{$w}{$v};
188 $shortest{$u}{$v} = $w;
194 if($modif == 0) {last;}
197 foreach $u (@node_list){
198 foreach $v (@node_list){
200 $$nodes{$u}{shortest_route}{$v} = $u;
201 $$nodes{$u}{number_hops}{$v} = 0;
203 $$nodes{$u}{shortest_route}{$v} = $shortest{$u}{$v};
204 $$nodes{$u}{number_hops}{$v} = $distance{$u}{$v};
210 sub build_interferences{
211 my($nodes,$edges,$host_list) = @_;
216 foreach $u (@$host_list){
217 foreach $v (@$host_list){
220 push(@{ $$nodes{$u}{using_path}},[$u,$v]);
222 my($next) = $$nodes{$w}{shortest_route}{$v};
223 $e = $$nodes{$w}{out}{$next};
224 push(@{ $$edges{$e}{using_path}},[$u,$v]);
225 push(@{ $$nodes{$next}{using_path}},[$u,$v]);
231 # foreach $e (keys %$edges){
233 # foreach $e1 (@{$$edges{$e}{using_path}}) {
234 # my($p1,$q1) = @$e1;
235 # foreach $e2 (@{$$edges{$e}{using_path}}) {
236 # my($p2,$q2) = @$e2;
237 # $interference{$p1}{$p2}{$q1}{$q2} = 1;
243 foreach $p1 (@$host_list) {
244 foreach $p2 (@$host_list) {
245 foreach $q1 (@$host_list) {
246 foreach $q2 (@$host_list) {
247 $interference{$p1}{$p2}{$q1}{$q2}=0;
253 foreach $e (keys %$nodes){
255 foreach $e1 (@{$$nodes{$e}{using_path}}) {
257 foreach $e2 (@{$$nodes{$e}{using_path}}) {
259 $interference{$p1}{$p2}{$q1}{$q2} = 1;
264 foreach $e (keys %$nodes){
265 undef(@{$$nodes{$e}{using_path}});
268 foreach $e (keys %$edges){
269 undef(@{$$edges{$e}{using_path}});
272 # foreach $u (@host_list){
273 # foreach $v (@host_list){
274 # if((defined($interference[$u]))&&(defined($interference[$u][$v]))) {
275 # print_matrix($interference[$u][$v]);
279 return(\%interference);
283 my($nodes,$edges,$u,$time,$direction,$stamp) = @_;
285 $$nodes{$u}{"Couleur_$stamp"}=1;
287 $$nodes{$u}{"Debut_$stamp"}=$$time;
288 foreach $v (keys (%{$$nodes{$u}{$direction}})) {
289 if ($$nodes{$v}{"Couleur_$stamp"} == 0) {
290 $$nodes{$v}{"PI_$stamp"} = $u;
291 __visit_pp($nodes,$edges,$v,$time,$direction,$stamp);
294 $$nodes{$u}{"Couleur_$stamp"}=2;
296 $$nodes{$u}{"Fin_$stamp"}=$$time;
300 my($nodes,$edges,$direction,$stamp,$stampSorter) = @_;
302 my(@node_list) = (keys %$nodes);
303 if(defined($stampSorter)) {
305 $$nodes{$b}{$stampSorter}
307 $$nodes{$a}{$stampSorter}
313 foreach $u (@node_list) {
314 $$nodes{$u}{"Couleur_$stamp"} = 0;
317 foreach $u (@node_list) {
318 if($$nodes{$u}{"Couleur_$stamp"} == 0) {
319 __visit_pp($nodes,$edges,$u,\$time,$direction,$stamp);
326 sub GO_SCC_Topological_Sort{
327 my($nodes,$edges) = @_;
329 my(@node_list) = (keys %$nodes);
331 ### Strongly Connected Components building
332 __PP($nodes,$edges,"out","1");
333 __PP($nodes,$edges,"in","2","Fin_1");
337 if ($$nodes{$a}{"Fin_2"}<$$nodes{$b}{"Debut_2"}) {
339 } elsif ($$nodes{$a}{"Debut_2"}<$$nodes{$b}{"Debut_2"}) {
347 my($scc)=$node_list[0];
349 foreach $u (@node_list) {
350 if($$nodes{$u}{Fin_2} > $$nodes{$scc}{Fin_2}) {
353 push @{$SCC{$scc}},$u;
354 $$nodes{$u}{SCC_leader}=$scc;
358 my($n_SCC,$e_SCC)=G_new_graph();
359 foreach $scc (keys %SCC) {
360 G_new_node($n_SCC,$e_SCC,$$nodes{$scc}{SCC_leader});
361 foreach $u (@{$SCC{$scc}}) {
362 foreach $v (keys (%{$$nodes{$u}{out}})) {
363 if(!defined($$n_SCC{$$nodes{$u}{SCC_leader}}{out}{$$nodes{$v}{SCC_leader}})) {
364 GO_connect($n_SCC,$e_SCC,$$nodes{$u}{SCC_leader},$$nodes{$v}{SCC_leader});
370 __PP($n_SCC,$e_SCC,"out","TS");
371 my(@SCC_list) = keys %SCC;
372 @SCC_list = sort {$$n_SCC{$b}{Fin_TS} <=> $$n_SCC{$a}{Fin_TS}} @SCC_list;
374 foreach $scc (@SCC_list) {
375 push @ordering, $SCC{$scc};