--- /dev/null
+#
+# Parameters for Network Model ModelId: 856566616
+# ============================
+#
+# Value Parameter
+# ----- ---------
+#
+# 1 NW: number of WANs
+# 5 NM: number of MANs per WAN
+# 5 NL: number of LANs per MAN
+# 10 SW: number of nodes per WAN
+# 10 SM: number of nodes per MAN
+# 5 SL: number of nodes per LAN
+# 2 RW: intranetwork redundancy for WAN
+# 1 RM: intranetwork redundancy for MANs
+# 1 RL: intranetwork redundancy for LANs
+# 2 RMW: internetwork redundancy for MAN to WAN
+# 1 RLM: internetwork redundancy for LAN to MAN
+#
+# 100 Grid size (square)
+# 40 Grid unit for WAN
+# 8 Grid unit for MAN
+# 2 Grid unit for LAN
+#
+# 0 Proximity test for WAN (0 is inactive)
+# 0 Proximity test for MAN (0 is inactive)
+# 0 Proximity test for LAN (0 is inactive)
+#
+# 0 Edge list is directed (0) or undirected (1)
+# Total Number of Nodes (derived) : 185
+#
+# Edge Metrics
+# ------------
+#
+# From To Band- Fixed Delay/Unit
+# Type Type width Delay Distance
+# ------------------------------------------
+# 0 0 10 5 1
+# 0 1 10 50 1
+# 0 2 0 0 1
+# 1 0 10 50 1
+# 1 1 100 100 10
+# 1 2 100 1000 1
+# 2 0 0 0 1
+# 2 1 100 1000 1
+# 2 2 1000 150 100
+#
+# NODES
+# =====
+#
+# Node X Y Type (0 = WAN, 1 = MAN, 2 = LAN)
+# ------------------------------------
+0 800 2160 0
+1 520 3400 0
+2 2280 2720 0
+3 2120 3120 0
+4 2960 2680 0
+5 600 1280 0
+6 1400 2720 0
+7 2480 2480 0
+8 1400 3080 0
+9 3760 920 0
+10 3360 2784 1
+11 3680 2984 1
+12 3680 2968 1
+13 3448 3376 1
+14 3312 3048 1
+15 3120 3328 1
+16 3192 2904 1
+17 3080 2840 1
+18 3128 2928 1
+19 3728 3040 1
+20 2168 3168 1
+21 2600 3304 1
+22 2792 3944 1
+23 2240 3808 1
+24 2160 3688 1
+25 2568 3408 1
+26 2288 3648 1
+27 2672 3704 1
+28 2792 3280 1
+29 2160 3928 1
+30 992 2328 1
+31 1272 2264 1
+32 1016 2328 1
+33 792 2688 1
+34 1024 2368 1
+35 928 2336 1
+36 1056 2408 1
+37 1000 2760 1
+38 1136 2608 1
+39 1072 2488 1
+40 792 1792 1
+41 1032 1464 1
+42 728 2024 1
+43 1080 1256 1
+44 720 1432 1
+45 808 1984 1
+46 1152 2008 1
+47 1320 1992 1
+48 1136 1448 1
+49 1256 1608 1
+50 3112 2800 1
+51 3264 2888 1
+52 3008 2776 1
+53 2880 2808 1
+54 3056 3240 1
+55 2792 3168 1
+56 2696 3152 1
+57 2656 2856 1
+58 2688 2544 1
+59 2704 2872 1
+60 3383 3233 2
+61 3485 3161 2
+62 3503 3171 2
+63 3417 3109 2
+64 3419 3229 2
+65 3303 3025 2
+66 3231 3111 2
+67 3191 2937 2
+68 3293 3069 2
+69 3139 2995 2
+70 3251 3001 2
+71 3309 3015 2
+72 3141 3119 2
+73 3187 2967 2
+74 3295 2967 2
+75 3319 3083 2
+76 3325 2993 2
+77 3313 3003 2
+78 3223 2951 2
+79 3373 3067 2
+80 3119 2941 2
+81 3245 2909 2
+82 3133 2889 2
+83 3111 2931 2
+84 3229 2939 2
+85 2665 3409 2
+86 2747 3399 2
+87 2701 3305 2
+88 2699 3469 2
+89 2705 3349 2
+90 2323 3797 2
+91 2205 3749 2
+92 2233 3743 2
+93 2267 3829 2
+94 2323 3743 2
+95 2601 3445 2
+96 2709 3315 2
+97 2785 3481 2
+98 2771 3393 2
+99 2621 3487 2
+100 2173 3277 2
+101 2231 3343 2
+102 2365 3355 2
+103 2325 3169 2
+104 2263 3189 2
+105 2967 4037 2
+106 2799 3981 2
+107 2989 4047 2
+108 2953 4021 2
+109 2891 4111 2
+110 1185 2687 2
+111 1245 2665 2
+112 1147 2663 2
+113 1119 2579 2
+114 1247 2509 2
+115 1139 2641 2
+116 1171 2603 2
+117 1221 2665 2
+118 1111 2607 2
+119 1107 2529 2
+120 1161 2551 2
+121 1043 2447 2
+122 1029 2421 2
+123 1145 2511 2
+124 1163 2411 2
+125 1077 2551 2
+126 1151 2453 2
+127 1245 2545 2
+128 1143 2523 2
+129 1135 2493 2
+130 1431 2437 2
+131 1293 2311 2
+132 1359 2269 2
+133 1403 2309 2
+134 1449 2417 2
+135 1347 2071 2
+136 1213 2039 2
+137 1163 2045 2
+138 1239 2015 2
+139 1251 2155 2
+140 829 1901 2
+141 975 1915 2
+142 811 1977 2
+143 861 1951 2
+144 989 1947 2
+145 913 2041 2
+146 867 2181 2
+147 807 2159 2
+148 839 2089 2
+149 783 2073 2
+150 1341 2127 2
+151 1505 2125 2
+152 1519 2031 2
+153 1405 2011 2
+154 1397 2165 2
+155 775 1507 2
+156 837 1573 2
+157 919 1625 2
+158 833 1485 2
+159 789 1461 2
+160 2881 2611 2
+161 2711 2555 2
+162 2807 2739 2
+163 2727 2561 2
+164 2853 2709 2
+165 2715 2731 2
+166 2751 2713 2
+167 2691 2571 2
+168 2727 2677 2
+169 2703 2549 2
+170 3015 2897 2
+171 3041 2925 2
+172 3167 2927 2
+173 3161 2941 2
+174 3079 2865 2
+175 2721 2901 2
+176 2743 3041 2
+177 2801 2887 2
+178 2867 2985 2
+179 2851 2873 2
+180 3067 2853 2
+181 2999 2957 2
+182 2941 2875 2
+183 2933 2959 2
+184 2895 2981 2
+#
+# EDGES
+# =====
+#
+# From To Delay Band- From To State (1:active, 2:redundant
+# Node Node width Type Type 3:internetwork, 4:red.inter.)
+# ---------------------------------------------------
+#
+# WAN 0
+#
+0 6 805 10 0 0 1
+0 5 885 10 0 0 1
+0 32 51 10 0 1 3
+0 42 51 10 0 1 4
+1 8 925 10 0 0 1
+1 6 1085 10 0 0 2
+2 3 405 10 0 0 1
+2 7 285 10 0 0 1
+2 27 51 10 0 1 4
+2 51 51 10 0 1 4
+3 8 725 10 0 0 1
+3 2 405 10 0 0 1
+3 23 51 10 0 1 3
+4 7 525 10 0 0 1
+4 9 1925 10 0 0 1
+4 15 51 10 0 1 3
+5 0 885 10 0 0 1
+5 47 51 10 0 1 3
+6 8 365 10 0 0 1
+6 0 805 10 0 0 1
+6 1 1085 10 0 0 2
+6 32 51 10 0 1 4
+7 2 285 10 0 0 1
+7 4 525 10 0 0 1
+7 9 2005 10 0 0 2
+7 15 51 10 0 1 4
+7 51 51 10 0 1 3
+8 1 925 10 0 0 1
+8 6 365 10 0 0 1
+8 3 725 10 0 0 1
+9 4 1925 10 0 0 1
+9 7 2005 10 0 0 2
+#
+# MAN 0
+#
+10 16 2100 100 1 1 1
+11 19 820 100 1 1 1
+11 12 260 100 1 1 1
+11 14 3780 100 1 1 1
+12 11 260 100 1 1 1
+13 15 3380 100 1 1 1
+13 14 3620 100 1 1 2
+14 11 3780 100 1 1 1
+14 16 1940 100 1 1 1
+14 15 3460 100 1 1 1
+14 13 3620 100 1 1 2
+14 60 1001 100 1 2 3
+15 14 3460 100 1 1 1
+15 13 3380 100 1 1 1
+15 4 51 10 1 0 3
+15 7 51 10 1 0 4
+16 14 1940 100 1 1 1
+16 18 740 100 1 1 1
+16 10 2100 100 1 1 1
+16 75 1001 100 1 2 3
+17 18 1060 100 1 1 1
+17 80 1001 100 1 2 3
+18 16 740 100 1 1 1
+18 17 1060 100 1 1 1
+18 65 1001 100 1 2 3
+18 70 1001 100 1 2 3
+19 11 820 100 1 1 1
+#
+# MAN 1
+#
+20 21 4580 100 1 1 1
+20 100 1001 100 1 2 3
+21 25 1140 100 1 1 1
+21 28 2020 100 1 1 1
+21 20 4580 100 1 1 1
+21 85 1001 100 1 2 3
+21 95 1001 100 1 2 3
+22 27 2740 100 1 1 1
+22 105 1001 100 1 2 3
+23 24 1540 100 1 1 1
+23 29 1540 100 1 1 1
+23 3 51 10 1 0 3
+24 26 1380 100 1 1 1
+24 23 1540 100 1 1 1
+24 90 1001 100 1 2 3
+25 21 1140 100 1 1 1
+25 27 3220 100 1 1 1
+25 26 3780 100 1 1 1
+26 25 3780 100 1 1 1
+26 24 1380 100 1 1 1
+27 25 3220 100 1 1 1
+27 22 2740 100 1 1 1
+27 2 51 10 1 0 4
+28 21 2020 100 1 1 1
+29 23 1540 100 1 1 1
+#
+# MAN 2
+#
+30 32 340 100 1 1 1
+30 35 740 100 1 1 1
+31 32 2660 100 1 1 1
+31 130 1001 100 1 2 3
+32 34 500 100 1 1 1
+32 30 340 100 1 1 1
+32 31 2660 100 1 1 1
+32 0 51 10 1 0 3
+32 6 51 10 1 0 4
+33 37 2260 100 1 1 1
+34 36 580 100 1 1 1
+34 32 500 100 1 1 1
+34 120 1001 100 1 2 3
+35 30 740 100 1 1 1
+36 39 900 100 1 1 1
+36 34 580 100 1 1 1
+36 125 1001 100 1 2 3
+37 38 2100 100 1 1 1
+37 33 2260 100 1 1 1
+38 39 1460 100 1 1 1
+38 37 2100 100 1 1 1
+39 38 1460 100 1 1 1
+39 36 900 100 1 1 1
+39 110 1001 100 1 2 3
+39 115 1001 100 1 2 3
+#
+# MAN 3
+#
+40 45 2020 100 1 1 1
+40 44 3700 100 1 1 1
+40 140 1001 100 1 2 3
+41 44 3220 100 1 1 1
+41 48 1140 100 1 1 1
+42 45 980 100 1 1 1
+42 0 51 10 1 0 4
+42 145 1001 100 1 2 3
+43 48 2100 100 1 1 1
+44 40 3700 100 1 1 1
+44 41 3220 100 1 1 1
+44 155 1001 100 1 2 3
+45 42 980 100 1 1 1
+45 40 2020 100 1 1 1
+45 46 3540 100 1 1 1
+46 45 3540 100 1 1 1
+46 47 1780 100 1 1 1
+46 135 1001 100 1 2 3
+47 46 1780 100 1 1 1
+47 5 51 10 1 0 3
+47 150 1001 100 1 2 3
+48 41 1140 100 1 1 1
+48 43 2100 100 1 1 1
+48 49 2100 100 1 1 1
+49 48 2100 100 1 1 1
+#
+# MAN 4
+#
+50 52 1140 100 1 1 1
+50 51 1780 100 1 1 1
+51 50 1780 100 1 1 1
+51 7 51 10 1 0 3
+51 2 51 10 1 0 4
+52 50 1140 100 1 1 1
+52 53 1380 100 1 1 1
+52 170 1001 100 1 2 3
+53 52 1380 100 1 1 1
+53 59 1940 100 1 1 1
+53 180 1001 100 1 2 3
+54 55 2820 100 1 1 1
+55 56 1060 100 1 1 1
+55 54 2820 100 1 1 1
+56 59 2900 100 1 1 1
+56 55 1060 100 1 1 1
+57 59 580 100 1 1 1
+57 58 3220 100 1 1 1
+58 57 3220 100 1 1 1
+58 160 1001 100 1 2 3
+58 165 1001 100 1 2 3
+59 53 1940 100 1 1 1
+59 57 580 100 1 1 1
+59 56 2900 100 1 1 1
+59 175 1001 100 1 2 3
+#
+# LAN 0
+#
+60 61 12550 1000 2 2 1
+61 60 12550 1000 2 2 1
+60 62 13550 1000 2 2 1
+62 60 13550 1000 2 2 1
+60 63 12950 1000 2 2 1
+63 60 12950 1000 2 2 1
+60 64 3750 1000 2 2 1
+64 60 3750 1000 2 2 1
+60 14 1001 100 2 1 3
+14 60 1001 100 1 2 3
+#
+# LAN 1
+#
+65 66 11350 1000 2 2 1
+66 65 11350 1000 2 2 1
+65 67 14350 1000 2 2 1
+67 65 14350 1000 2 2 1
+65 68 4550 1000 2 2 1
+68 65 4550 1000 2 2 1
+65 69 16750 1000 2 2 1
+69 65 16750 1000 2 2 1
+65 18 1001 100 2 1 3
+18 65 1001 100 1 2 3
+#
+# LAN 2
+#
+70 71 5950 1000 2 2 1
+71 70 5950 1000 2 2 1
+70 72 16150 1000 2 2 1
+72 70 16150 1000 2 2 1
+70 73 7350 1000 2 2 1
+73 70 7350 1000 2 2 1
+70 74 5550 1000 2 2 1
+74 70 5550 1000 2 2 1
+70 18 1001 100 2 1 3
+18 70 1001 100 1 2 3
+#
+# LAN 3
+#
+75 76 9150 1000 2 2 1
+76 75 9150 1000 2 2 1
+75 77 8150 1000 2 2 1
+77 75 8150 1000 2 2 1
+75 78 16350 1000 2 2 1
+78 75 16350 1000 2 2 1
+75 79 5750 1000 2 2 1
+79 75 5750 1000 2 2 1
+75 16 1001 100 2 1 3
+16 75 1001 100 1 2 3
+#
+# LAN 4
+#
+80 81 13150 1000 2 2 1
+81 80 13150 1000 2 2 1
+80 82 5350 1000 2 2 1
+82 80 5350 1000 2 2 1
+80 83 1350 1000 2 2 1
+83 80 1350 1000 2 2 1
+80 84 11150 1000 2 2 1
+84 80 11150 1000 2 2 1
+80 17 1001 100 2 1 3
+17 80 1001 100 1 2 3
+#
+# LAN 5
+#
+85 86 8350 1000 2 2 1
+86 85 8350 1000 2 2 1
+85 87 11150 1000 2 2 1
+87 85 11150 1000 2 2 1
+85 88 6950 1000 2 2 1
+88 85 6950 1000 2 2 1
+85 89 7350 1000 2 2 1
+89 85 7350 1000 2 2 1
+85 21 1001 100 2 1 3
+21 85 1001 100 1 2 3
+#
+# LAN 6
+#
+90 91 12750 1000 2 2 1
+91 90 12750 1000 2 2 1
+90 92 10550 1000 2 2 1
+92 90 10550 1000 2 2 1
+90 93 6550 1000 2 2 1
+93 90 6550 1000 2 2 1
+90 94 5550 1000 2 2 1
+94 90 5550 1000 2 2 1
+90 24 1001 100 2 1 3
+24 90 1001 100 1 2 3
+#
+# LAN 7
+#
+95 96 16950 1000 2 2 1
+96 95 16950 1000 2 2 1
+95 97 18750 1000 2 2 1
+97 95 18750 1000 2 2 1
+95 98 17750 1000 2 2 1
+98 95 17750 1000 2 2 1
+95 99 4750 1000 2 2 1
+99 95 4750 1000 2 2 1
+95 21 1001 100 2 1 3
+21 95 1001 100 1 2 3
+#
+# LAN 8
+#
+100 101 8750 1000 2 2 1
+101 100 8750 1000 2 2 1
+100 102 20750 1000 2 2 1
+102 100 20750 1000 2 2 1
+100 103 18750 1000 2 2 1
+103 100 18750 1000 2 2 1
+100 104 12550 1000 2 2 1
+104 100 12550 1000 2 2 1
+100 20 1001 100 2 1 3
+20 100 1001 100 1 2 3
+#
+# LAN 9
+#
+105 106 17750 1000 2 2 1
+106 105 17750 1000 2 2 1
+105 107 2550 1000 2 2 1
+107 105 2550 1000 2 2 1
+105 108 2150 1000 2 2 1
+108 105 2150 1000 2 2 1
+105 109 10750 1000 2 2 1
+109 105 10750 1000 2 2 1
+105 22 1001 100 2 1 3
+22 105 1001 100 1 2 3
+#
+# LAN 10
+#
+110 111 6350 1000 2 2 1
+111 110 6350 1000 2 2 1
+110 112 4550 1000 2 2 1
+112 110 4550 1000 2 2 1
+110 113 12750 1000 2 2 1
+113 110 12750 1000 2 2 1
+110 114 18950 1000 2 2 1
+114 110 18950 1000 2 2 1
+110 39 1001 100 2 1 3
+39 110 1001 100 1 2 3
+#
+# LAN 11
+#
+115 116 4950 1000 2 2 1
+116 115 4950 1000 2 2 1
+115 117 8550 1000 2 2 1
+117 115 8550 1000 2 2 1
+115 118 4550 1000 2 2 1
+118 115 4550 1000 2 2 1
+115 119 11750 1000 2 2 1
+119 115 11750 1000 2 2 1
+115 39 1001 100 2 1 3
+39 115 1001 100 1 2 3
+#
+# LAN 12
+#
+120 121 15750 1000 2 2 1
+121 120 15750 1000 2 2 1
+120 122 18550 1000 2 2 1
+122 120 18550 1000 2 2 1
+120 123 4350 1000 2 2 1
+123 120 4350 1000 2 2 1
+120 124 14150 1000 2 2 1
+124 120 14150 1000 2 2 1
+120 34 1001 100 2 1 3
+34 120 1001 100 1 2 3
+#
+# LAN 13
+#
+125 126 12350 1000 2 2 1
+126 125 12350 1000 2 2 1
+125 127 16950 1000 2 2 1
+127 125 16950 1000 2 2 1
+125 128 7150 1000 2 2 1
+128 125 7150 1000 2 2 1
+125 129 8350 1000 2 2 1
+129 125 8350 1000 2 2 1
+125 36 1001 100 2 1 3
+36 125 1001 100 1 2 3
+#
+# LAN 14
+#
+130 131 18750 1000 2 2 1
+131 130 18750 1000 2 2 1
+130 132 18350 1000 2 2 1
+132 130 18350 1000 2 2 1
+130 133 13150 1000 2 2 1
+133 130 13150 1000 2 2 1
+130 134 2750 1000 2 2 1
+134 130 2750 1000 2 2 1
+130 31 1001 100 2 1 3
+31 130 1001 100 1 2 3
+#
+# LAN 15
+#
+135 136 13750 1000 2 2 1
+136 135 13750 1000 2 2 1
+135 137 18550 1000 2 2 1
+137 135 18550 1000 2 2 1
+135 138 12150 1000 2 2 1
+138 135 12150 1000 2 2 1
+135 139 12750 1000 2 2 1
+139 135 12750 1000 2 2 1
+135 46 1001 100 2 1 3
+46 135 1001 100 1 2 3
+#
+# LAN 16
+#
+140 141 14750 1000 2 2 1
+141 140 14750 1000 2 2 1
+140 142 7950 1000 2 2 1
+142 140 7950 1000 2 2 1
+140 143 5950 1000 2 2 1
+143 140 5950 1000 2 2 1
+140 144 16750 1000 2 2 1
+144 140 16750 1000 2 2 1
+140 40 1001 100 2 1 3
+40 140 1001 100 1 2 3
+#
+# LAN 17
+#
+145 146 14750 1000 2 2 1
+146 145 14750 1000 2 2 1
+145 147 15950 1000 2 2 1
+147 145 15950 1000 2 2 1
+145 148 8950 1000 2 2 1
+148 145 8950 1000 2 2 1
+145 149 13350 1000 2 2 1
+149 145 13350 1000 2 2 1
+145 42 1001 100 2 1 3
+42 145 1001 100 1 2 3
+#
+# LAN 18
+#
+150 151 16550 1000 2 2 1
+151 150 16550 1000 2 2 1
+150 152 20350 1000 2 2 1
+152 150 20350 1000 2 2 1
+150 153 13350 1000 2 2 1
+153 150 13350 1000 2 2 1
+150 154 6750 1000 2 2 1
+154 150 6750 1000 2 2 1
+150 47 1001 100 2 1 3
+47 150 1001 100 1 2 3
+#
+# LAN 19
+#
+155 156 9150 1000 2 2 1
+156 155 9150 1000 2 2 1
+155 157 18750 1000 2 2 1
+157 155 18750 1000 2 2 1
+155 158 6350 1000 2 2 1
+158 155 6350 1000 2 2 1
+155 159 4950 1000 2 2 1
+159 155 4950 1000 2 2 1
+155 44 1001 100 2 1 3
+44 155 1001 100 1 2 3
+#
+# LAN 20
+#
+160 161 17950 1000 2 2 1
+161 160 17950 1000 2 2 1
+160 162 14750 1000 2 2 1
+162 160 14750 1000 2 2 1
+160 163 16150 1000 2 2 1
+163 160 16150 1000 2 2 1
+160 164 10150 1000 2 2 1
+164 160 10150 1000 2 2 1
+160 58 1001 100 2 1 3
+58 160 1001 100 1 2 3
+#
+# LAN 21
+#
+165 166 4150 1000 2 2 1
+166 165 4150 1000 2 2 1
+165 167 16150 1000 2 2 1
+167 165 16150 1000 2 2 1
+165 168 5550 1000 2 2 1
+168 165 5550 1000 2 2 1
+165 169 18350 1000 2 2 1
+169 165 18350 1000 2 2 1
+165 58 1001 100 2 1 3
+58 165 1001 100 1 2 3
+#
+# LAN 22
+#
+170 171 3950 1000 2 2 1
+171 170 3950 1000 2 2 1
+170 172 15550 1000 2 2 1
+172 170 15550 1000 2 2 1
+170 173 15350 1000 2 2 1
+173 170 15350 1000 2 2 1
+170 174 7150 1000 2 2 1
+174 170 7150 1000 2 2 1
+170 52 1001 100 2 1 3
+52 170 1001 100 1 2 3
+#
+# LAN 23
+#
+175 176 14150 1000 2 2 1
+176 175 14150 1000 2 2 1
+175 177 8150 1000 2 2 1
+177 175 8150 1000 2 2 1
+175 178 16950 1000 2 2 1
+178 175 16950 1000 2 2 1
+175 179 13350 1000 2 2 1
+179 175 13350 1000 2 2 1
+175 59 1001 100 2 1 3
+59 175 1001 100 1 2 3
+#
+# LAN 24
+#
+180 181 12550 1000 2 2 1
+181 180 12550 1000 2 2 1
+180 182 12750 1000 2 2 1
+182 180 12750 1000 2 2 1
+180 183 17150 1000 2 2 1
+183 180 17150 1000 2 2 1
+180 184 21550 1000 2 2 1
+184 180 21550 1000 2 2 1
+180 53 1001 100 2 1 3
+53 180 1001 100 1 2 3
+# End of Model
--- /dev/null
+#!/usr/bin/perl -w
+use strict;
+
+# Un graphe c'est un hachage nodes et un hachage edges avec trucs dedans
+# nodes{nom}{type}, nodes{nom}{X}, nodes{nom}{Y}, nodes{nom}{in}, nodes{nom}{out} par exemple
+# edges{nom}{src}, edges{nom}{dst}, edges{nom}{type}, edges{nom}{delay}, edges{nom}{bw}
+
+
+sub G_new_graph {
+ my(%nodes,%edges); # a new graph...
+ return(\%nodes,\%edges);
+}
+
+sub G_new_node {
+ my($nodes,$edges,$name) = @_;
+ $$nodes{$name}{name}=$name;
+ $$nodes{$name}{type}=2;
+}
+
+sub G_connect {
+ my($nodes,$edges,$src,$dst) = @_;
+ my($edge_count)=scalar(keys(%{$edges}));
+ $$edges{$edge_count}{src}=$src;
+ $$edges{$edge_count}{dst}=$dst;
+# $$edges{$edge_count}{delay} = $delay;
+# $$edges{$edge_count}{bw} = $bw;
+# $$edges{$edge_count}{type} = $type;
+# $$edges{$edge_count}{using_path} = [];
+ $$nodes{$src}{out}{$dst} = $edge_count;
+ $$nodes{$dst}{in}{$src} = $edge_count;
+ $$nodes{$dst}{out}{$src} = $edge_count;
+ $$nodes{$src}{in}{$dst} = $edge_count;
+ return($edge_count);
+}
+
+sub GO_connect {
+ my($nodes,$edges,$src,$dst) = @_;
+ my($edge_count)=scalar(keys(%{$edges}));
+ $$edges{$edge_count}{src}=$src;
+ $$edges{$edge_count}{dst}=$dst;
+# $$edges{$edge_count}{delay} = $delay;
+# $$edges{$edge_count}{bw} = $bw;
+# $$edges{$edge_count}{type} = $type;
+# $$edges{$edge_count}{using_path} = [];
+ $$nodes{$src}{out}{$dst} = $edge_count;
+ $$nodes{$dst}{in}{$src} = $edge_count;
+ return($edge_count);
+}
+
+sub G_simgrid_export {
+ my($nodes,$edges,$filename) = @_;
+ my($u,$v,$w,$e);
+ my(@host_list)=();
+
+ open MSG_OUTPUT, "> $filename";
+
+ print MSG_OUTPUT "HOSTS\n";
+ foreach $u (keys %{$nodes}) {
+ if (!((defined($$nodes{$u}{host}))&&($$nodes{$u}{host}==1))) { next; }
+ if (!((defined($$nodes{$u}{Mflops}))&&($$nodes{$u}{host}==1))) {
+ die "Lacking Mflops for $u\n";
+ }
+ print MSG_OUTPUT "$u $$nodes{$u}{Mflops}\n";
+ push @host_list,$u;
+ }
+ print MSG_OUTPUT "LINKS\n";
+ foreach $e (keys %{$edges}) {
+ (defined($$edges{$e}{bw})) or die "Lacking bw for $u\n";
+ (defined($$edges{$e}{delay})) or die "Lacking bw for $u\n";
+ print MSG_OUTPUT "$e $$edges{$e}{bw} $$edges{$e}{delay}\n";
+ }
+ print MSG_OUTPUT "ROUTES\n";
+ foreach $u (@host_list){
+ foreach $v (@host_list){
+ if($u ne $v) {
+ my(@path)=();
+ $w = $u;
+ while ($w ne $v) {
+ my($next) = $$nodes{$w}{shortest_route}{$v};
+ $e = $$nodes{$w}{out}{$next};
+ push(@path,$e);
+ $w = $next;
+ }
+ print MSG_OUTPUT "$u $v (@path)\n";
+ }
+ }
+ }
+ close(MSG_OUTPUT);
+}
+
+sub G_surfxml_export {
+ my($nodes,$edges,$filename) = @_;
+ my($u,$v,$w,$e);
+ my(@host_list)=();
+
+ open MSG_OUTPUT, "> $filename";
+
+ print MSG_OUTPUT "<?xml version='1.0'?>\n";
+ print MSG_OUTPUT "<!DOCTYPE platform_description SYSTEM \"surfxml.dtd\">\n";
+ print MSG_OUTPUT "<platform_description>\n";
+
+ foreach $u (keys %{$nodes}) {
+ if (!((defined($$nodes{$u}{host}))&&($$nodes{$u}{host}==1))) { next; }
+ if (!((defined($$nodes{$u}{Mflops}))&&($$nodes{$u}{host}==1))) {
+ die "Lacking Mflops for $u\n";
+ }
+ print MSG_OUTPUT " <cpu name=\"$$nodes{$u}{name}\" power=\"$$nodes{$u}{Mflops}\"/>\n";
+ push @host_list,$u;
+ }
+ foreach $e (keys %{$edges}) {
+ (defined($$edges{$e}{bw})) or die "Lacking bw for $u\n";
+ (defined($$edges{$e}{delay})) or die "Lacking bw for $u\n";
+ my($lat);
+ $lat = $$edges{$e}{delay} / 1000;
+ print MSG_OUTPUT " <network_link name=\"$e\" bandwidth=\"$$edges{$e}{bw}\" latency=\"$lat\"/>\n";
+ }
+ foreach $u (@host_list){
+ foreach $v (@host_list){
+ if($u ne $v) {
+ my(@path)=();
+ $w = $u;
+ while ($w ne $v) {
+ my($next) = $$nodes{$w}{shortest_route}{$v};
+ $e = $$nodes{$w}{out}{$next};
+ push(@path,$e);
+ $w = $next;
+ }
+ print MSG_OUTPUT " <route src=\"$$nodes{$u}{name}\" dst=\"$$nodes{$v}{name}\">";
+ foreach $w (@path) {
+ print MSG_OUTPUT "<route_element name=\"$w\"/>";
+ }
+ print MSG_OUTPUT " </route>\n";
+ }
+ }
+ }
+ print MSG_OUTPUT "</platform_description>\n";
+ close(MSG_OUTPUT);
+}
+
+##############################
+### GRAPH ALGORITHMS ###
+##############################
+
+sub shortest_paths{
+ my($nodes,$edges) = @_;
+
+ my(%connexion);
+ my(%distance);
+ my(%shortest);
+
+ my(@node_list) = sort (keys %$nodes);
+ my($n) = scalar(@node_list);
+
+ my($u,$v,$w,$step,$e);
+
+ foreach $u (@node_list){
+ foreach $v (@node_list){
+ $connexion{$u}{$v} = 0;
+ $distance{$u}{$v} = 0;
+ $shortest{$u}{$v} = -1;
+ }
+ }
+
+ foreach $e (sort (keys %$edges)){
+ my($x1)=$$edges{$e}{src};
+ my($x2)=$$edges{$e}{dst};
+ $connexion{$x1}{$x2} = $connexion{$x2}{$x1} = 1;
+ $distance{$x1}{$x2} = $distance{$x2}{$x1} = 1;
+ $shortest{$x1}{$x2} = $x2;
+ $shortest{$x2}{$x1} = $x1;
+ }
+
+# print_matrix(\%connexion);
+# matrix2viz(\%connexion);
+
+ foreach $step (0..$n-1){
+ my($modif) = 0;
+ foreach $u (@node_list){
+ foreach $v (@node_list){
+ foreach $w (@node_list){
+ if(($connexion{$u}{$w} != 0)
+ && ($distance{$w}{$v}!=0)
+ && (($distance{$u}{$v} >
+ $distance{$u}{$w} + $distance{$w}{$v}) || ($distance{$u}{$v}==0))
+ ){
+ $distance{$u}{$v} =
+ $distance{$u}{$w} + $distance{$w}{$v};
+ $shortest{$u}{$v} = $w;
+ $modif = 1;
+ }
+ }
+ }
+ }
+ if($modif == 0) {last;}
+ }
+
+ foreach $u (@node_list){
+ foreach $v (@node_list){
+ if($u eq $v) {
+ $$nodes{$u}{shortest_route}{$v} = $u;
+ $$nodes{$u}{number_hops}{$v} = 0;
+ } else {
+ $$nodes{$u}{shortest_route}{$v} = $shortest{$u}{$v};
+ $$nodes{$u}{number_hops}{$v} = $distance{$u}{$v};
+ }
+ }
+ }
+}
+
+sub build_interferences{
+ my($nodes,$edges,$host_list) = @_;
+
+ my($u,$v,$w,$e);
+ my(%interference);
+
+ foreach $u (@$host_list){
+ foreach $v (@$host_list){
+ if($u ne $v) {
+ $w = $u;
+ push(@{ $$nodes{$u}{using_path}},[$u,$v]);
+ while ($w ne $v) {
+ my($next) = $$nodes{$w}{shortest_route}{$v};
+ $e = $$nodes{$w}{out}{$next};
+ push(@{ $$edges{$e}{using_path}},[$u,$v]);
+ push(@{ $$nodes{$next}{using_path}},[$u,$v]);
+ $w = $next;
+ }
+ }
+ }
+ }
+# foreach $e (keys %$edges){
+# my($e1,$e2);
+# foreach $e1 (@{$$edges{$e}{using_path}}) {
+# my($p1,$q1) = @$e1;
+# foreach $e2 (@{$$edges{$e}{using_path}}) {
+# my($p2,$q2) = @$e2;
+# $interference{$p1}{$p2}{$q1}{$q2} = 1;
+# }
+# }
+# }
+ my($p1,$p2,$q1,$q2);
+
+ foreach $p1 (@$host_list) {
+ foreach $p2 (@$host_list) {
+ foreach $q1 (@$host_list) {
+ foreach $q2 (@$host_list) {
+ $interference{$p1}{$p2}{$q1}{$q2}=0;
+ }
+ }
+ }
+ }
+
+ foreach $e (keys %$nodes){
+ my($e1,$e2);
+ foreach $e1 (@{$$nodes{$e}{using_path}}) {
+ my($p1,$q1) = @$e1;
+ foreach $e2 (@{$$nodes{$e}{using_path}}) {
+ my($p2,$q2) = @$e2;
+ $interference{$p1}{$p2}{$q1}{$q2} = 1;
+ }
+ }
+ }
+
+ foreach $e (keys %$nodes){
+ undef(@{$$nodes{$e}{using_path}});
+ }
+
+ foreach $e (keys %$edges){
+ undef(@{$$edges{$e}{using_path}});
+ }
+
+# foreach $u (@host_list){
+# foreach $v (@host_list){
+# if((defined($interference[$u]))&&(defined($interference[$u][$v]))) {
+# print_matrix($interference[$u][$v]);
+# }
+# }
+# }
+ return(\%interference);
+}
+
+sub __visit_pp {
+ my($nodes,$edges,$u,$time,$direction,$stamp) = @_;
+ my($v);
+ $$nodes{$u}{"Couleur_$stamp"}=1;
+ $$time++;
+ $$nodes{$u}{"Debut_$stamp"}=$$time;
+ foreach $v (keys (%{$$nodes{$u}{$direction}})) {
+ if ($$nodes{$v}{"Couleur_$stamp"} == 0) {
+ $$nodes{$v}{"PI_$stamp"} = $u;
+ __visit_pp($nodes,$edges,$v,$time,$direction,$stamp);
+ }
+ }
+ $$nodes{$u}{"Couleur_$stamp"}=2;
+ $$time++;
+ $$nodes{$u}{"Fin_$stamp"}=$$time;
+}
+
+sub __PP {
+ my($nodes,$edges,$direction,$stamp,$stampSorter) = @_;
+
+ my(@node_list) = (keys %$nodes);
+ if(defined($stampSorter)) {
+ @node_list = sort {
+ $$nodes{$b}{$stampSorter}
+ <=>
+ $$nodes{$a}{$stampSorter}
+ } @node_list;
+ }
+
+ my($u,$time);
+
+ foreach $u (@node_list) {
+ $$nodes{$u}{"Couleur_$stamp"} = 0;
+ }
+ $time = 0;
+ foreach $u (@node_list) {
+ if($$nodes{$u}{"Couleur_$stamp"} == 0) {
+ __visit_pp($nodes,$edges,$u,\$time,$direction,$stamp);
+ }
+ }
+ return $time;
+}
+
+
+sub GO_SCC_Topological_Sort{
+ my($nodes,$edges) = @_;
+
+ my(@node_list) = (keys %$nodes);
+
+ ### Strongly Connected Components building
+ __PP($nodes,$edges,"out","1");
+ __PP($nodes,$edges,"in","2","Fin_1");
+
+ @node_list = sort
+ {
+ if ($$nodes{$a}{"Fin_2"}<$$nodes{$b}{"Debut_2"}) {
+ return -1;
+ } elsif ($$nodes{$a}{"Debut_2"}<$$nodes{$b}{"Debut_2"}) {
+ return -1;
+ }
+ return 1;
+ }
+ @node_list;
+
+ my($u,$v);
+ my($scc)=$node_list[0];
+ my(%SCC);
+ foreach $u (@node_list) {
+ if($$nodes{$u}{Fin_2} > $$nodes{$scc}{Fin_2}) {
+ $scc = $u;
+ }
+ push @{$SCC{$scc}},$u;
+ $$nodes{$u}{SCC_leader}=$scc;
+ }
+
+ ### Topological Sort
+ my($n_SCC,$e_SCC)=G_new_graph();
+ foreach $scc (keys %SCC) {
+ G_new_node($n_SCC,$e_SCC,$$nodes{$scc}{SCC_leader});
+ foreach $u (@{$SCC{$scc}}) {
+ foreach $v (keys (%{$$nodes{$u}{out}})) {
+ if(!defined($$n_SCC{$$nodes{$u}{SCC_leader}}{out}{$$nodes{$v}{SCC_leader}})) {
+ GO_connect($n_SCC,$e_SCC,$$nodes{$u}{SCC_leader},$$nodes{$v}{SCC_leader});
+ }
+ }
+ }
+ }
+
+ __PP($n_SCC,$e_SCC,"out","TS");
+ my(@SCC_list) = keys %SCC;
+ @SCC_list = sort {$$n_SCC{$b}{Fin_TS} <=> $$n_SCC{$a}{Fin_TS}} @SCC_list;
+ my(@ordering)=();
+ foreach $scc (@SCC_list) {
+ push @ordering, $SCC{$scc};
+ }
+
+ return \@ordering;
+}
+
+
+1;
--- /dev/null
+#!/usr/bin/perl -w
+use strict;
+
+#################################
+### GRAPH VISUALISATION ###
+#################################
+
+sub graph2viz{
+ my($nodes,$edges,$filename) = @_;
+
+ open VIZ, "> $filename.dot";
+ print VIZ "graph essai { \n";
+ print VIZ " graph [overlap=scale]\n";
+ #print VIZ " graph [overlap=false spline=true]\n";
+ print VIZ " node [shape=box, style=filled]\n";
+ print VIZ " node [width=.3, height=.3, style=filled, color=skyblue]\n";
+
+ my($u,$e);
+ foreach $u (sort (keys %$nodes)){
+ print VIZ " \"$u\" [label=\"$u\"";
+# if((defined($$nodes{$u}{max_interf}))&&($$nodes{$u}{max_interf}==1)) {print VIZ ",color=green";}
+ if(defined($$nodes{$u}{host}) && ($$nodes{$u}{host}==1)) {print VIZ ",color=red";}
+ print VIZ "];\n";
+ }
+
+ foreach $e (sort (keys %$edges)){
+ my($src)=$$edges{$e}{src};
+ my($dst)=$$edges{$e}{dst};
+# my($len)=log(10000/$$edges{$e}{bw});
+ print VIZ " \"$src\" -- \"$dst\" [";
+# print VIZ "len=$len";
+# print VIZ "label=$e";
+ if($#{$$edges{$e}{using_path}}>=0) {
+ print VIZ "color=red";
+ } else {
+ print VIZ "color=gray";
+ }
+ print VIZ "];\n";
+ }
+
+ print VIZ "}\n";
+ close VIZ;
+
+ system("neato -Tps $filename.dot > $filename.ps");
+# system("gv $filename.ps");
+ system("pstoedit -f fig $filename.ps $filename.fig 2>/dev/null");
+# system("xfig -startg 0 $filename.fig ");
+}
+
+sub digraph2viz{
+ my($nodes,$edges,$filename) = @_;
+
+ open VIZ, "> $filename.dot";
+ print VIZ "digraph essai { \n";
+ print VIZ " graph [overlap=scale]\n";
+ #print VIZ " graph [overlap=false spline=true]\n";
+ print VIZ " node [shape=box, style=filled]\n";
+ print VIZ " node [width=.3, height=.3, style=filled, color=skyblue]\n";
+
+ my($u,$e);
+ foreach $u (sort (keys %$nodes)){
+ print VIZ " $u [label=$u";
+ if((defined($$nodes{$u}{host}))&&($$nodes{$u}{host}==1)) {print VIZ ",color=red";}
+ print VIZ "];\n";
+ }
+
+ foreach $e (sort (keys %$edges)){
+ my($src)=$$edges{$e}{src};
+ my($dst)=$$edges{$e}{dst};
+# my($len)=log(10000/$$edges{$e}{bw});
+ print VIZ " $src -> $dst\n";
+# print VIZ "len=$len";
+# print VIZ "label=$e";
+ }
+
+ print VIZ "}\n";
+ close VIZ;
+
+ system("dot -Tps $filename.dot > $filename.ps");
+# system("gv $filename.ps");
+ system("pstoedit -f fig $filename.ps $filename.fig 2>/dev/null");
+ system("xfig -startg 0 $filename.fig ");
+}
+
+sub graph2fig_basic{
+ my($nodes,$edges,$filename) = @_;
+
+ open VIZ, "> $filename.fig";
+
+ print VIZ "#FIG 3.2\n";
+ print VIZ "Landscape\n";
+ print VIZ "Center\n";
+ print VIZ "Metric\n";
+ print VIZ "A4\n";
+ print VIZ "100.00\n";
+ print VIZ "Single\n";
+ print VIZ "-2\n";
+ print VIZ "1200 2\n";
+
+ my($scale)=5;
+
+ my($u,$e);
+ foreach $u (sort (keys %$nodes)){
+ my($x) = $scale * $$nodes{$u}{X};
+ my($y) = $scale * $$nodes{$u}{Y};
+ print VIZ "4 1 0 50 -1 0 12 0.0000 0 135 270 $x $y $u\\001\n";
+ }
+
+ foreach $e (sort (keys %$edges)){
+ my($src)=$$edges{$e}{src};
+ my($dst)=$$edges{$e}{dst};
+ my($x1) = $scale * $$nodes{$src}{X};
+ my($y1) = $scale * $$nodes{$src}{Y};
+ my($x2) = $scale * $$nodes{$dst}{X};
+ my($y2) = $scale * $$nodes{$dst}{Y};
+ print VIZ "2 1 0 1 4 7 50 -1 -1 0.000 0 0 -1 0 0 2\n";
+ print VIZ "\t $x1 $y1 $x2 $y2\n";
+ }
+ close VIZ;
+
+ system("xfig -startg 0 $filename.fig ");
+}
+
+sub interfgraph2viz{
+ my($nodes,$edges,$count_interferences,$value_interferences,$figbase,$filename) = @_;
+
+ system("cp $figbase.fig $filename.fig");
+ open FIG, ">> $filename.fig";
+ my($e);
+ foreach $e (@{$$count_interferences{$value_interferences}}){
+ my($src)=$$e[0];
+ my($dst)=$$e[1];
+ my(@tab);
+ print STDERR "($src - $dst)\n";
+ $src = `grep ' $src\\\\001' $filename.fig`;
+ $dst = `grep ' $dst\\\\001' $filename.fig`;
+ @tab = split(/\s+/,$src);
+ my($x1) = $tab[11];
+ my($y1) = $tab[12];
+ @tab = split(/\s+/,$dst);
+ my($x2) = $tab[11];
+ my($y2) = $tab[12];
+ print FIG "2 1 0 3 14 7 999 -1 -1 0.000 0 0 -1 0 0 2\n";
+ print FIG "\t $x1 $y1 $x2 $y2\n";
+# print VIZ " $src -- $dst [color=green];\n";
+ }
+ close(FIG);
+# system("xfig -startg 0 $filename.fig ");
+ system("fig2dev -L png $filename.fig $filename.png");
+ unlink("$filename.fig");
+}
+
+
+sub graph_get_layout{
+ my($nodes,$edges,$filename) = @_;
+
+ graph2viz($nodes,$edges,$filename);
+
+ my($u);
+ foreach $u (sort (keys %$nodes)){
+ my($val_u) = `grep ' $u\\\\001' $filename.fig`;
+ my(@tab) = split(/\s+/,$val_u);
+ my($x1) = $tab[11];
+ my($y1) = $tab[12];
+ $$nodes{$u}{X}=$x1;
+ $$nodes{$u}{Y}=$y1;
+ }
+}
+
+sub graph2viz_withlayout{
+ my($nodes,$edges,$filename) = @_;
+
+ open FIG, ">> $filename.fig";
+ my($e,$u);
+ foreach $u (sort (keys %$nodes)){
+ my($x1) = int ($$nodes{$u}{X});
+ my($y1) = int ($$nodes{$u}{Y});
+ print FIG "1 3 0 1 0 31 50 -1 20 0.000 1 0.0000 $x1 $y1 75 75 $x1 $y1 ".($x1+75)." $y1\n";
+ }
+ foreach $e (sort (keys %$edges)){
+ my($src)=$$edges{$e}{src};
+ my($dst)=$$edges{$e}{dst};
+ my($x1) = int ($$nodes{$src}{X});
+ my($y1) = int ($$nodes{$src}{Y});
+ my($x2) = int ($$nodes{$dst}{X});
+ my($y2) = int ($$nodes{$dst}{Y});
+ print FIG "2 1 0 3 14 7 60 -1 -1 0.000 0 0 -1 0 0 2\n";
+ print FIG "\t $x1 $y1 $x2 $y2\n";
+ }
+ close(FIG);
+# system("xfig -startg 0 $filename.fig ");
+# system("fig2dev -L png $filename.fig $filename.png");
+}
+
+sub print_matrix{
+ my($M) = shift;
+
+ if(!defined($M)) {return;}
+ my($u,$v);
+
+ my(@node_list) = sort (keys %$M);
+ my($n) = scalar(@node_list);
+
+ foreach $u (0..$n-1){
+ print "==";
+ }
+ print "\n";
+
+ foreach $u (@node_list){
+ if(defined($$M{$u})) {
+ foreach $v (@node_list){
+ if(defined($$M{$u}{$v})){
+ print "$$M{$u}{$v} ";
+ } else {
+ print " ";
+ }
+ }
+ }
+ print "\n";
+ }
+ foreach $u (0..$n-1){
+ print "==";
+ }
+ print "\n\n";
+}
+
+sub matrix2viz{
+ my($M) = shift;
+ my($filename) = "foo";
+ open VIZ, "> $filename.dot";
+
+ print VIZ "# Brite topology translated by Alvin\n";
+ print VIZ "graph essai { \n";
+ print VIZ " graph [overlap=scale]\n";
+
+ #print VIZ " graph [overlap=false spline=true]\n";
+ print VIZ " node [shape=box, style=filled]\n";
+ print VIZ " node [width=.3, height=.3, style=filled, color=skyblue]\n";
+ my(@node_list) = sort (keys %$M);
+ my($n) = scalar(@node_list);
+
+ my($u,$v);
+ foreach $u (@node_list){
+ print VIZ " $u [label=$u, color = red];\n";
+ }
+
+ foreach $u (@node_list){
+ foreach $v (@node_list){
+ if($$M{$u}{$v}!=0){
+ print VIZ " $u -- $v ;\n";
+ }
+ }
+ }
+ print VIZ "}\n";
+ close VIZ;
+
+ system("neato -Tps $filename.dot > $filename.ps");
+ system("gv $filename.ps");
+}
+
+
+sub print_object {
+ my($M) = @_;
+ my($key);
+ if(!defined($M)) {
+ } elsif (!ref($M)) {
+ print "\"$M\"";
+ return;
+ } elsif (ref($M) eq "SCALAR") {
+ print "\"$$M\"";
+ return;
+ } elsif (ref($M) eq "HASH") {
+ print "{";
+ foreach $key (sort (keys %{$M})) {
+ if($key eq "number_hops") {next;}
+ if($key eq "shortest_route") {next;}
+ if($key eq "using_path") {next;}
+ print "\"$key\" => ";
+ print_object($$M{$key});
+ print ","
+ }
+ print "}";
+ } elsif (ref($M) eq "ARRAY") {
+ print "[";
+ foreach $key (0..$#$M) {
+ print_object($$M[$key]);
+ print ","
+ }
+ print "]";
+ } else {
+ }
+}
+
+# sub print_object{
+# my($indent,$M) = @_;
+# my($key);
+# if (!ref($M)) {
+# print "$M";
+# return;
+# } elsif (ref($M) eq "SCALAR") {
+# print "$$M";
+# return;
+# } elsif (ref($M) eq "HASH") {
+# print "\n";
+# foreach $key (sort (keys %{$M})) {
+# print "$indent $key => { ";
+# print_object($indent." ", $$M{$key});
+# print "$indent }\n"
+# }
+# } elsif (ref($M) eq "ARRAY") {
+# print "\n";
+# foreach $key (0..$#$M) {
+# print "$indent $key : [";
+# print_object($indent." ", $$M[$key]);
+# print "$indent ]\n"
+# }
+# } else {
+# }
+# }
+
+1;
--- /dev/null
+#!/usr/bin/perl -w
+use strict;
+
+use graph_viz;
+use graph_tbx;
+
+
+##############################
+### GRAPH GENERATION ###
+##############################
+
+sub parse_tiers_file {
+ my($filename);
+ my($nodes,$edges)=G_new_graph(); # a new graph...
+ $filename=shift or die "Need a tiers file!";
+
+ open INPUT, $filename;
+
+ my($state) = 0;
+ my($line);
+
+ while(defined($line=<INPUT>)){
+ if($line =~ /^\# NODES/) {$state=1; next;}
+ if($line =~ /^\# EDGES/) {$state=2; next;}
+ if(($line=~/^\s*$/) || ($line=~/^\#/)) {next;}
+ if ($state==1){ # Getting the nodes
+ # Node X Y Type (0 = WAN, 1 = MAN, 2 = LAN)
+ my($name,$X,$Y,$type) = split(/\s+/,$line);
+ G_new_node($nodes,$edges,$name);
+ $$nodes{$name}{X} = $X;
+ $$nodes{$name}{Y} = $Y;
+ $$nodes{$name}{type} = $type;
+ $$nodes{$name}{using_path} = [];
+ print STDERR "$name [$X $Y $type]\n";
+ next;
+ }
+ if ($state==2){ # Getting the edges
+ # From To Delay Band- From To State (1:active, 2:redundant
+ # Node Node width Type Type 3:internetwork, 4:red.inter.)
+ my($src,$dst,$delay,$bw,$srct,$dstt,$type) = split(/\s+/,$line);
+ if(!defined($$nodes{$src}{out}{$dst})) {
+ # links are symetric and simple
+ my($edge_count)=G_connect($nodes,$edges,$src,$dst);
+ $$edges{$edge_count}{delay} = $delay;
+ $$edges{$edge_count}{bw} = $bw;
+ $$edges{$edge_count}{type} = $type;
+ $$edges{$edge_count}{using_path} = [];
+ print STDERR "($dst,$src) [$delay $bw $type]\n";
+ }
+ next;
+ }
+ }
+ close(INPUT);
+ return($nodes,$edges);
+}
+
+sub generate_host_list{
+ my($nodes,$edges,$proba) = @_;
+ my($u);
+ my(@host_list)=();
+ foreach $u (sort (keys %$nodes)){ # type 0 = WAN, 1 = MAN, 2 = LAN
+ if(($$nodes{$u}{type}==2) && (rand() < $proba)) {
+ $$nodes{$u}{host}=1;
+ push @host_list, $u;
+ } else {
+ $$nodes{$u}{host}=0;
+ }
+ }
+ @host_list = sort {$a <=> $b} @host_list;
+ return(\@host_list);
+}
+
+1;
--- /dev/null
+#!/usr/bin/perl -w
+use strict;
+
+use AlvinMisc;
+use graph_viz;
+use graph_tbx;
+use tiers;
+
+my (%machine);
+$machine{"canaria.ens-lyon.fr"}{"CPU_clock"} = "347.669";
+$machine{"canaria.ens-lyon.fr"}{"CPU_Mflops"} = "34.333";
+$machine{"canaria.ens-lyon.fr"}{"CPU_model"} = "Pentium II (Deschutes)";
+$machine{"canaria.ens-lyon.fr"}{"CPU_num"} = "2";
+$machine{"canaria.ens-lyon.fr"}{"Machine_type"} = "i686";
+$machine{"canaria.ens-lyon.fr"}{"OS_version"} = "Linux 2.2.19pre17";
+
+$machine{"moby.ens-lyon.fr"}{"CPU_clock"} = "996.698";
+$machine{"moby.ens-lyon.fr"}{"CPU_Mflops"} = "114.444";
+$machine{"moby.ens-lyon.fr"}{"CPU_model"} = "Intel(R) Pentium(R) III Mobile CPU 1000MHz";
+$machine{"moby.ens-lyon.fr"}{"CPU_num"} = "1";
+$machine{"moby.ens-lyon.fr"}{"Machine_type"} = "i686";
+$machine{"moby.ens-lyon.fr"}{"OS_version"} = "Linux 2.4.18-accelerated";
+
+$machine{"popc0.ens-lyon.fr"}{"CPU_clock"} = "199.095";
+$machine{"popc0.ens-lyon.fr"}{"CPU_Mflops"} = "22.151";
+$machine{"popc0.ens-lyon.fr"}{"CPU_model"} = "Pentium Pro";
+$machine{"popc0.ens-lyon.fr"}{"CPU_num"} = "1";
+$machine{"popc0.ens-lyon.fr"}{"Machine_type"} = "i686";
+$machine{"popc0.ens-lyon.fr"}{"OS_version"} = "Linux 2.2.19";
+
+$machine{"sci0.ens-lyon.fr"}{"CPU_clock"} = "451.032446";
+$machine{"sci0.ens-lyon.fr"}{"CPU_Mflops"} = "48.492";
+$machine{"sci0.ens-lyon.fr"}{"CPU_model"} = "Pentium II (Deschutes)";
+$machine{"sci0.ens-lyon.fr"}{"CPU_num"} = "2";
+$machine{"sci0.ens-lyon.fr"}{"Machine_type"} = "i686";
+$machine{"sci0.ens-lyon.fr"}{"OS_version"} = "Linux 2.2.13";
+
+$machine{"lancelot.u-strasbg.fr"}{"OS_version"} = "Linux 2.2.17-21mdk";
+$machine{"lancelot.u-strasbg.fr"}{"CPU_clock"} = "400.916";
+$machine{"lancelot.u-strasbg.fr"}{"CPU_model"} = "Celeron (Mendocino)";
+$machine{"lancelot.u-strasbg.fr"}{"CPU_Mflops"} = "42.917000000000002";
+$machine{"lancelot.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"lancelot.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"caseb.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.8-26mdk";
+$machine{"caseb.u-strasbg.fr"}{"CPU_clock"} = "1399.763";
+$machine{"caseb.u-strasbg.fr"}{"CPU_model"} = "AMD Athlon(tm) 4 Processor";
+$machine{"caseb.u-strasbg.fr"}{"CPU_Mflops"} = "137.333";
+$machine{"caseb.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"caseb.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"pellinore.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.18-6mdksmp";
+$machine{"pellinore.u-strasbg.fr"}{"CPU_clock"} = "802.922";
+$machine{"pellinore.u-strasbg.fr"}{"CPU_model"} = "Pentium III (Coppermine)";
+$machine{"pellinore.u-strasbg.fr"}{"CPU_Mflops"} = "68.667000000000002";
+$machine{"pellinore.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"pellinore.u-strasbg.fr"}{"CPU_num"} = "2";
+
+$machine{"dinadan.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.19-686";
+$machine{"dinadan.u-strasbg.fr"}{"CPU_clock"} = "933.375";
+$machine{"dinadan.u-strasbg.fr"}{"CPU_model"} = "Pentium III (Coppermine)";
+$machine{"dinadan.u-strasbg.fr"}{"CPU_Mflops"} = "85.832999999999998";
+$machine{"dinadan.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"dinadan.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"darjeeling.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.18-5";
+$machine{"darjeeling.u-strasbg.fr"}{"CPU_clock"} = "1793.371";
+$machine{"darjeeling.u-strasbg.fr"}{"CPU_model"} = "Intel(R) Pentium(R) 4 CPU 1.80GHz";
+$machine{"darjeeling.u-strasbg.fr"}{"CPU_Mflops"} = "98.094999999999999";
+$machine{"darjeeling.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"darjeeling.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"gauvain.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.17";
+$machine{"gauvain.u-strasbg.fr"}{"CPU_clock"} = "1050.034";
+$machine{"gauvain.u-strasbg.fr"}{"CPU_model"} = "AMD Athlon(tm) Processor";
+$machine{"gauvain.u-strasbg.fr"}{"CPU_Mflops"} = "114.444";
+$machine{"gauvain.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"gauvain.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"sekhmet.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.18-k7";
+$machine{"sekhmet.u-strasbg.fr"}{"CPU_clock"} = "1399.803";
+$machine{"sekhmet.u-strasbg.fr"}{"CPU_model"} = "AMD Athlon(tm) 4 Processor";
+$machine{"sekhmet.u-strasbg.fr"}{"CPU_Mflops"} = "171.667";
+$machine{"sekhmet.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"sekhmet.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"shaitan.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.18-6mdk";
+$machine{"shaitan.u-strasbg.fr"}{"CPU_clock"} = "800.030";
+$machine{"shaitan.u-strasbg.fr"}{"CPU_model"} = "Pentium III (Coppermine)";
+$machine{"shaitan.u-strasbg.fr"}{"CPU_Mflops"} = "76.296000000000006";
+$machine{"shaitan.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"shaitan.u-strasbg.fr"}{"CPU_num"} = "1";
+
+my (%network);
+#0.587500,0.655,0.681
+
+$network{"bw"}{10} = [ [274285,0.514433], [330233,0.059904],
+ [949460,0.136931], [1063823,0.131098],
+ [2041829,7.413073] ];
+
+$network{"bw"}{100} = [ [64121,35.076518], [65264,0.270544],
+ [67418,0.156056], [80797,0.479780], [82517,6.932556],
+ [92951,0.189980], [94763,0.370788],
+ [123015,35.083019], [171318,295.890617],
+ [223570,0.278066], [274285,0.514433],
+ [330233,0.059904] ];
+
+$network{"bw"}{1000} = [ [937,53.930106], [2013,4.455826],
+ [2022,5.704550], [2025,5.652577], [2073,4.460898],
+ [2179,5.922616], [2195,4.669142], [2321,4.522355],
+ [2327,4.477270], [2427,4.062241], [2539,4.583831],
+ [3777,5.161451], [4448,3.101854], [4629,5.473705],
+ [4840,87.981858], [5773,0.006406], [6150,8.762440],
+ [7413,0.601375], [7837,0.424305], [7867,2.885584],
+ [7924,1.742977], [8394,9.647856], [9015,0.287840],
+ [9612,0.468130], [9842,1.502106], [10069,1.340162],
+ [10255,6.104672], [10609,1.402769], [11014,0.449267],
+ [11724,0.863872], [11741,0.869727], [11753,1.114548],
+ [12100,1.200141], [12122,0.844683], [12513,0.788956],
+ [13022,0.278175], [14341,7.877863], [14864,0.820952],
+ [15084,0.950938], [15111,1.081287], [15141,0.162735],
+ [15449,0.951830], [15797,0.380044], [15868,0.848211],
+ [17433,0.320114], [17819,0.907120], [17906,1.043314],
+ [18382,1.087968], [18788,0.259761], [18944,9.547561],
+ [20667,0.410463], [20864,0.637001], [22546,0.247605],
+ [24227,0.677908], [24547,0.040300], [25404,0.472524],
+ [26205,0.658142], [26382,0.595883], [26970,0.666676],
+ [27441,0.536941], [28416,3.870785], [29714,3.866813],
+ [31020,0.863123], [31452,1.913591], [31964,0.678645],
+ [33067,9.693542], [33378,0.728103], [34162,0.672289],
+ [34363,0.539000], [35178,0.677601], [35333,0.019773],
+ [35689,0.106949], [35881,0.126045], [37202,0.705967],
+ [37438,0.848712], [38536,0.117352], [38723,0.751810],
+ [39826,7.164412], [41518,0.630529], [41827,0.039417],
+ [42392,0.520693], [43729,0.272268], [44597,0.227430],
+ [45776,0.789218], [46068,4.760145], [46531,0.164758],
+ [52408,0.522878], [54216,0.533340], [57678,1.461517],
+ [60272,0.125428] ];
+
+sub assign_host_speed{
+ my($nodes,$edges) = @_;
+
+ my($u);
+
+ my(@label_list) = keys %machine;
+ foreach $u (keys %$nodes) {
+ my($mach_type_nb) = scalar(@label_list);
+ my($mach_type) = int rand($mach_type_nb);
+ $$nodes{$u}{Mflops} = $machine{$label_list[$mach_type]}{CPU_Mflops};
+ }
+}
+
+sub assign_host_names{
+ my($nodes,$edges) = @_;
+
+ my(@name_list) = qw(Abbott Adoncourt Aikin Alain Alfred Amadeus
+ Angie Anjou Anne_Marie Apple April Archibald
+ Aubertin Auclair Audy AutoCAD Barry BASIC
+ Beaudoin Beaulac Bellemarre Bellevue
+ Bell_Northern Benoit Bentz Bernard Bescherelle
+ Blais Boily Boivin Borduas Boston Boucherville
+ Bourassa Bousquet Boyer Brian Brosseau Brown
+ Browne Cadieux Cambridge Canada Carole
+ Casavant Chambly Charles Charron Christian
+ Claude Cloutier Colin Comeau Corp Coulombe
+ Cousineau Croteau Daniel Decelles Denis Denise
+ Desjardins Dick Dionne Disney Dodge Domey
+ Dominique Doris Dorval Doyon Drouin Dumoulin
+ EDF Emacs Ethernet Europe Fafard Fernand
+ Fernet Flamand Florient Foisy Forget Fourier
+ FrameMaker France Francine Frank Fraser
+ Freedman Gagnon Gaston Gatien Gaudreault
+ Gauthier Gavrel Gendron Gentilly Geoff
+ Geoffray George Georges Gilles Ginette Girard
+ Goodwin Gordon Gosselin Gratton Greg Gregory
+ Guy Harry Harwell Hayward Hollerbach Horne
+ Houde Hubert Hz Inc Inmos Intel Interleaf
+ Internet iRMX iRMXII iRMXIII Isabelle ISPELL
+ Jackson Jacobsen Jacquelin Jacques
+ Jacques_Cartier Jamie Jean Jean_Claude
+ Jean_Louis Jean_Maurice Jeannine Jean_Paul
+ Jean_Pierre Jean_Yves Jill Jobin Jocelyne John
+ Jones Joynes Jude Julian Julien Juneau Jupiter
+ Kansas Kent Khan King Kuenning kV Lachapelle
+ Laflamme Lafontaine Lamothe Lapointe Laroche
+ LaSalle LaTeX Laugier Laurendeau Laval Lavoie
+ Leblanc Lecavalier Leclerc Lepage Lessard
+ Letarte Linda LISP Longueuil Louis Louise
+ Louis_Marc Ltd Lucie Mahoney Maltais Manseau
+ Marc Marcel Marcoux Marie Marielle Mark
+ Marseille Martin Masson Mathematica Matlab
+ McGee McGill Messier METAFONT Michel Mike
+ Minneapolis Mireille Mongenot Monique
+ Mont_Tremblant Morin Morissette Moshe Mulhouse
+ mW Nagle Nelligan Nestor Nicole OHara Olivier
+ Ontario Ottawa Ouellet Owen Ozias Papineau
+ Paul Pellan Pelletier PERL Phaneuf Phil Pierre
+ Pierrefonds Plante Pointe_Claire PostScript
+ Poussart Pronovost Provost Raymond Re README
+ Renato Ricard Richard Ringuet Riopelle Rioux
+ Roberge Robert Rochefort Roger Romano Ronald
+ Roy Rubin Sacramento Saint_Amand Sainte_Foy
+ Sainte_Julie Saint_Marc_sur_Richelieu Seattle
+ Shawinigan Sherbrooke Sirois Smith Sorel Soucy
+ SPARC SPARCs SPICE St_Antoine St_Bruno
+ Ste_Anne Steele Ste_Julie Stephen St_Jacques
+ St_Jean St_Paul Strasbourg Sun SunOS Suzanne
+ Tanguay Tessier TeX Texas Thibault Thierry
+ Todd Tokyo Toronto Toulouse Tremblay Turcotte
+ Uintas UniPress Unix UNIX Utah Vancouver
+ Varennes Verville Victoria Victoriaville Viger
+ Vincent VxWorks Wilfrid William Williams
+ Wright Yolande Yvan Yves Zawinski);
+
+ AlvinMisc::melange(\@name_list);
+
+ my($u);
+ foreach $u (keys %$nodes) {
+ if($$nodes{$u}{host}==1) {
+ $$nodes{$u}{name} = shift @name_list;
+ }
+ }
+}
+
+sub assign_link_speed{
+ my($nodes,$edges) = @_;
+
+ my($e);
+
+ foreach $e (keys %$edges) {
+ my($bw) = $$edges{$e}{bw};
+
+ my(@choice) = @{$network{"bw"}{$bw}};
+ my($choice_nb) = scalar(@choice);
+ my($chosen_link) = $choice[(int rand($choice_nb))];
+ $$edges{$e}{bw} = $$chosen_link[0]/8000;
+ $$edges{$e}{delay} = $$chosen_link[1];
+ }
+}
+
+
+sub affiche_graph{
+ my($nodes,$edges,$filename) = @_;
+ my($u,$v,$w,$e);
+
+ my(%node_to_export);
+ my(%edge_to_export);
+
+ my(@host_list,@routeur_list,@link_list);
+
+ foreach $u (keys %{$nodes}) {
+ if (!((defined($$nodes{$u}{host}))&&($$nodes{$u}{host}==1))) { next; }
+ if (!((defined($$nodes{$u}{Mflops}))&&($$nodes{$u}{host}==1))) {
+ die "Lacking Mflops for $u\n";
+ }
+ push @host_list,$u;
+ $node_to_export{$u}=$#host_list;
+ }
+
+ foreach $u (@host_list){
+ foreach $v (@host_list){
+ if($u ne $v) {
+ $w = $u;
+ if(!defined($node_to_export{$w})) {
+ push @routeur_list,$w;
+ $node_to_export{$w}=$#host_list + $#routeur_list + 1;
+ }
+ while ($w ne $v) {
+ my($next) = $$nodes{$w}{shortest_route}{$v};
+ my($e) = $$nodes{$w}{out}{$next};
+ if(!defined($edge_to_export{$e})) {
+ push @link_list,$e;
+ $edge_to_export{$e}=$#link_list;
+ }
+ $w = $next;
+ if(!defined($node_to_export{$w})) {
+ push @routeur_list,$w;
+ $node_to_export{$w}=$#host_list + $#routeur_list + 1;
+ }
+ }
+ }
+ }
+ }
+
+ open VIZ, "> $filename.dot";
+ print VIZ "graph essai { \n";
+ print VIZ " graph [overlap=scale]\n";
+ #print VIZ " graph [overlap=false spline=true]\n";
+ print VIZ " node [shape=box, style=filled]\n";
+ print VIZ " node [width=.3, height=.3, style=filled]\n";
+
+ foreach $u (@host_list) {
+ print VIZ " \"$u\" [label=\"$$nodes{$u}{name}\",color=red,shape=box];\n";
+ }
+ foreach $u (@routeur_list) {
+ print VIZ " \"$u\" [label=\"$$nodes{$u}{name}\",fontsize=2,color=skyblue,shape=circle];\n";
+ }
+ foreach $e (@link_list) {
+ my($src)=$$edges{$e}{src};
+ my($dst)=$$edges{$e}{dst};
+ (defined($$edges{$e}{bw})) or die "Lacking bw for $u\n";
+ (defined($$edges{$e}{delay})) or die "Lacking bw for $u\n";
+ print VIZ " \"$src\" -- \"$dst\";\n";
+ }
+
+ print VIZ "}\n";
+ close VIZ;
+
+ system("neato -Tps $filename.dot > $filename.ps");
+# system("gv $filename.ps");
+ system("pstoedit -f fig $filename.ps $filename.fig 2>/dev/null");
+# system("xfig -startg 0 $filename.fig ");
+}
+
+sub main {
+ my($nodes,$edges,$interferences,$host_list,$count_interferences);
+
+ $#ARGV>=0 or die "Need a tiers file!";
+ my($filename)=$ARGV[0];
+ $filename =~ s/\.[^\.]*$//g;
+ if(1) {
+ ($nodes,$edges) = parse_tiers_file $ARGV[0];
+
+ print STDERR "Graph built\n";
+ $host_list = generate_host_list($nodes,$edges,.7);
+ assign_host_speed($nodes,$edges);
+ assign_link_speed($nodes,$edges);
+ assign_host_names($nodes,$edges);
+ print STDERR "Host list built\n";
+ shortest_paths($nodes,$edges);
+ print STDERR "Shortest Paths built\n";
+# G_helene_export($nodes,$edges,"$filename.helene");
+ G_surfxml_export($nodes,$edges,"$filename.xml");
+ affiche_graph($nodes,$edges,"$filename");
+ }
+}
+
+main;
