guohanghui/graph-theory
0
1from graph import Graph2from itertools import product3 4 5def grid(x, y, bidirectional=False):6 """7 :param x: number of columns8 :param y: number of rows9 :param bidirectional: boolean10 :return: Graph with grid.11 """12 g = Graph()13 for i, j in product(range(x), range(y)):14 if i % x > 0: # connect west15 n1 = i - 1, j16 n2 = i, j17 g.add_edge(n1, n2, bidirectional=bidirectional)18 19 if j % y > 0: # connect north20 n1 = i, j - 121 n2 = i, j22 g.add_edge(n1, n2, bidirectional=bidirectional)23 return g24 25 26def london_underground():27 """the london underground network"""28 london_underground_stations = { # id:(latitude,longitude,station name),29 1: (51.5028, -0.2801, "Acton Town"),30 2: (51.5143, -0.0755, "Aldgate"),31 3: (51.5154, -0.0726, "Aldgate East"),32 4: (51.5107, -0.013, "All Saints"),33 5: (51.5407, -0.2997, "Alperton"),34 7: (51.5322, -0.1058, "Angel"),35 8: (51.5653, -0.1353, "Archway"),36 9: (51.6164, -0.1331, "Arnos Grove"),37 10: (51.5586, -0.1059, "Arsenal"),38 11: (51.5226, -0.1571, "Baker Street"),39 12: (51.4431, -0.1525, "Balham"),40 13: (51.5133, -0.0886, "Bank"),41 14: (51.5204, -0.0979, "Barbican"),42 15: (51.5396, 0.081, "Barking"),43 16: (51.5856, 0.0887, "Barkingside"),44 17: (51.4905, -0.2139, "Barons Court"),45 18: (51.5121, -0.1879, "Bayswater"),46 19: (51.5148, 0.0613, "Beckton"),47 20: (51.5087, 0.055, "Beckton Park"),48 21: (51.5403, 0.127, "Becontree"),49 22: (51.5504, -0.1642, "Belsize Park"),50 24: (51.527, -0.0549, "Bethnal Green"),51 25: (51.512, -0.1031, "Blackfriars"),52 26: (51.5867, -0.0417, "Blackhorse Road"),53 27: (51.5079, -0.0066, "Blackwall"),54 28: (51.5142, -0.1494, "Bond Street"),55 29: (51.5011, -0.0943, "Borough"),56 30: (51.4956, -0.325, "Boston Manor"),57 31: (51.6071, -0.1243, "Bounds Green"),58 32: (51.5273, -0.0208, "Bow Church"),59 33: (51.5269, -0.0247, "Bow Road"),60 34: (51.5766, -0.2136, "Brent Cross"),61 36: (51.5248, -0.0119, "Bromley-By-Bow"),62 38: (51.6028, -0.2641, "Burnt Oak"),63 39: (51.5481, -0.1188, "Caledonian Road"),64 40: (51.5392, -0.1426, "Camden Town"),65 42: (51.5051, -0.0209, "Canary Wharf"),66 44: (51.5113, -0.0904, "Cannon Street"),67 45: (51.6078, -0.2947, "Canons Park"),68 47: (51.5441, -0.1538, "Chalk Farm"),69 48: (51.5185, -0.1111, "Chancery Lane"),70 49: (51.508, -0.1247, "Charing Cross"),71 51: (51.6177, 0.0755, "Chigwell"),72 52: (51.4946, -0.2678, "Chiswick Park"),73 54: (51.4618, -0.1384, "Clapham Common"),74 55: (51.4649, -0.1299, "Clapham North"),75 56: (51.4527, -0.148, "Clapham South"),76 58: (51.5955, -0.2502, "Colindale"),77 59: (51.418, -0.1778, "Colliers Wood"),78 60: (51.5129, -0.1243, "Covent Garden"),79 61: (51.4957, -0.0144, "Crossharbour & London Arena"),80 63: (51.5095, 0.0276, "Custom House"),81 65: (51.5085, 0.064, "Cyprus"),82 66: (51.5443, 0.1655, "Dagenham East"),83 67: (51.5417, 0.1469, "Dagenham Heathway"),84 70: (51.5223, -0.0173, "Devons Road"),85 71: (51.552, -0.2387, "Dollis Hill"),86 72: (51.5152, -0.3017, "Ealing Broadway"),87 73: (51.5101, -0.2882, "Ealing Common"),88 74: (51.492, -0.1973, "Earl's Court"),89 75: (51.5765, -0.397, "Eastcote"),90 76: (51.5168, -0.2474, "East Acton"),91 77: (51.5874, -0.165, "East Finchley"),92 78: (51.5394, 0.0518, "East Ham"),93 79: (51.5093, -0.0021, "East India"),94 80: (51.4586, -0.2112, "East Putney"),95 81: (51.6137, -0.275, "Edgware"),96 82: (51.5199, -0.1679, "Edgware Road (B)"),97 83: (51.5203, -0.17, "Edgware Road (C)"),98 84: (51.4943, -0.1001, "Elephant & Castle"),99 85: (51.5496, 0.1977, "Elm Park"),100 87: (51.5074, -0.1223, "Embankment"),101 89: (51.5282, -0.1337, "Euston"),102 90: (51.526, -0.1359, "Euston Square"),103 91: (51.596, 0.0912, "Fairlop"),104 92: (51.5203, -0.1053, "Farringdon"),105 93: (51.6012, -0.1932, "Finchley Central"),106 94: (51.5472, -0.1803, "Finchley Road"),107 95: (51.5642, -0.1065, "Finsbury Park"),108 96: (51.4804, -0.195, "Fulham Broadway"),109 97: (51.5096, 0.0716, "Gallions Reach"),110 98: (51.5765, 0.0663, "Gants Hill"),111 99: (51.4945, -0.1829, "Gloucester Road"),112 100: (51.5724, -0.1941, "Golders Green"),113 101: (51.5018, -0.2267, "Goldhawk Road"),114 102: (51.5205, -0.1347, "Goodge Street"),115 103: (51.6132, 0.0923, "Grange Hill"),116 104: (51.5238, -0.1439, "Great Portland Street"),117 105: (51.5423, -0.3456, "Greenford"),118 107: (51.5067, -0.1428, "Green Park"),119 108: (51.4915, -0.2754, "Gunnersbury"),120 109: (51.603, 0.0933, "Hainault"),121 110: (51.4936, -0.2251, "Hammersmith"),122 111: (51.5568, -0.178, "Hampstead"),123 112: (51.5302, -0.2933, "Hanger Lane"),124 113: (51.5362, -0.2575, "Harlesden"),125 114: (51.5925, -0.3351, "Harrow & Wealdston"),126 115: (51.5793, -0.3366, "Harrow-on-the-Hill"),127 116: (51.4669, -0.4227, "Hatton Cross"),128 117: (51.4713, -0.4524, "Heathrow Terminals 1, 2 & 3"),129 118: (51.4598, -0.4476, "Heathrow Terminal 4"),130 119: (51.5829, -0.2259, "Hendon Central"),131 120: (51.5033, -0.0215, "Heron Quays"),132 122: (51.5009, -0.1925, "High Street Kensington"),133 123: (51.546, -0.104, "Highbury & Islington"),134 124: (51.5777, -0.1458, "Highgate"),135 125: (51.5538, -0.4499, "Hillingdon"),136 126: (51.5174, -0.12, "Holborn"),137 127: (51.5075, -0.206, "Holland Park"),138 128: (51.5526, -0.1132, "Holloway Road"),139 129: (51.5539, 0.2184, "Hornchurch"),140 130: (51.4713, -0.3665, "Hounslow Central"),141 131: (51.4733, -0.3564, "Hounslow East"),142 132: (51.4734, -0.3855, "Hounslow West"),143 133: (51.5027, -0.1527, "Hyde Park Corner"),144 134: (51.5619, -0.4421, "Ickenham"),145 135: (51.4871, -0.0101, "Island Gardens"),146 136: (51.4884, -0.1053, "Kennington"),147 137: (51.5304, -0.225, "Kensal Green"),148 138: (51.4983, -0.2106, "Kensington (Olympia)"),149 139: (51.5507, -0.1402, "Kentish Town"),150 140: (51.5816, -0.3162, "Kenton"),151 141: (51.477, -0.285, "Kew Gardens"),152 142: (51.5471, -0.2047, "Kilburn"),153 143: (51.5351, -0.1939, "Kilburn Park"),154 144: (51.5846, -0.2786, "Kingsbury"),155 145: (51.5308, -0.1238, "King's Cross St. Pancras"),156 146: (51.5015, -0.1607, "Knightsbridge"),157 147: (51.5172, -0.2107, "Ladbroke Grove"),158 148: (51.4991, -0.1115, "Lambeth North"),159 149: (51.5119, -0.1756, "Lancaster Gate"),160 150: (51.5139, -0.2172, "Latimer Road"),161 151: (51.5113, -0.1281, "Leicester Square"),162 153: (51.5566, -0.0053, "Leyton"),163 154: (51.5683, 0.0083, "Leytonstone"),164 155: (51.5123, -0.0396, "Limehouse"),165 156: (51.5178, -0.0823, "Liverpool Street"),166 157: (51.5052, -0.0864, "London Bridge"),167 159: (51.53, -0.1854, "Maida Vale"),168 160: (51.5712, -0.0958, "Manor House"),169 161: (51.5122, -0.094, "Mansion House"),170 162: (51.5136, -0.1586, "Marble Arch"),171 163: (51.5225, -0.1631, "Marylebone"),172 164: (51.5249, -0.0332, "Mile End"),173 165: (51.6082, -0.2103, "Mill Hill East"),174 166: (51.5108, -0.0863, "Monument"),175 167: (51.5186, -0.0886, "Moorgate"),176 168: (51.6294, -0.432, "Moor Park"),177 169: (51.4022, -0.1948, "Morden"),178 170: (51.5342, -0.1387, "Mornington Crescent"),179 171: (51.4902, -0.0145, "Mudchute"),180 172: (51.5542, -0.2503, "Neasden"),181 173: (51.5756, 0.0899, "Newbury Park"),182 176: (51.4995, -0.3142, "Northfields"),183 177: (51.5483, -0.3687, "Northolt"),184 178: (51.5784, -0.3184, "Northwick Park"),185 179: (51.6111, -0.424, "Northwood"),186 180: (51.6004, -0.4092, "Northwood Hills"),187 181: (51.5237, -0.2597, "North Acton"),188 182: (51.5175, -0.2887, "North Ealing"),189 184: (51.5846, -0.3626, "North Harrow"),190 185: (51.5621, -0.3034, "North Wembley"),191 186: (51.5094, -0.1967, "Notting Hill Gate"),192 188: (51.5263, -0.0873, "Old Street"),193 190: (51.4813, -0.3522, "Osterley"),194 191: (51.4819, -0.113, "Oval"),195 192: (51.515, -0.1415, "Oxford Circus"),196 193: (51.5154, -0.1755, "Paddington"),197 194: (51.527, -0.2841, "Park Royal"),198 195: (51.4753, -0.2011, "Parsons Green"),199 196: (51.5366, -0.3232, "Perivale"),200 197: (51.5098, -0.1342, "Picadilly Circus"),201 198: (51.4893, -0.1334, "Pimlico"),202 199: (51.5926, -0.3805, "Pinner"),203 200: (51.5313, 0.0172, "Plaistow"),204 201: (51.5077, -0.0173, "Poplar"),205 202: (51.572, -0.2954, "Preston Road"),206 203: (51.5093, 0.0336, "Prince Regent"),207 205: (51.4682, -0.2089, "Putney Bridge"),208 206: (51.5341, -0.2047, "Queen's Park"),209 207: (51.5942, -0.2861, "Queensbury"),210 208: (51.5107, -0.1877, "Queensway"),211 209: (51.4942, -0.2359, "Ravenscourt Park"),212 210: (51.5753, -0.3714, "Rayners Lane"),213 211: (51.5763, 0.0454, "Redbridge"),214 212: (51.5234, -0.1466, "Regent's Park"),215 213: (51.4633, -0.3013, "Richmond"),216 215: (51.6171, 0.0439, "Roding Valley"),217 216: (51.501, -0.0525, "Rotherhithe"),218 217: (51.5084, 0.0465, "Royal Albert"),219 218: (51.519, -0.188, "Royal Oak"),220 219: (51.5091, 0.0181, "Royal Victoria"),221 220: (51.5715, -0.4213, "Ruislip"),222 222: (51.5732, -0.4125, "Ruislip Manor"),223 223: (51.523, -0.1244, "Russell Square"),224 224: (51.5822, -0.0749, "Seven Sisters"),225 225: (51.5117, -0.056, "Shadwell"),226 226: (51.5046, -0.2187, "Shepherd's Bush (C)"),227 227: (51.5058, -0.2265, "Shepherd's Bush (H)"),228 228: (51.5227, -0.0708, "Shoreditch"),229 229: (51.4924, -0.1565, "Sloane Square"),230 230: (51.5808, 0.0216, "Snaresbrook"),231 231: (51.4454, -0.2066, "Southfields"),232 234: (51.5011, -0.3072, "South Ealing"),233 235: (51.5646, -0.3521, "South Harrow"),234 236: (51.4941, -0.1738, "South Kensington"),235 237: (51.5701, -0.3081, "South Kenton"),236 238: (51.5007, -0.0191, "South Quay"),237 239: (51.5569, -0.3988, "South Ruislip"),238 240: (51.4154, -0.1919, "South Wimbledon"),239 241: (51.5917, 0.0275, "South Woodford"),240 242: (51.495, -0.2459, "Stamford Brook"),241 243: (51.6194, -0.3028, "Stanmore"),242 244: (51.5221, -0.047, "Stepney Green"),243 245: (51.4723, -0.123, "Stockwell"),244 246: (51.5439, -0.2759, "Stonebridge Park"),245 247: (51.5416, -0.0042, "Stratford"),246 248: (51.4994, -0.1335, "St. James's Park"),247 249: (51.5347, -0.174, "St. John's Wood"),248 250: (51.5146, -0.0973, "St. Paul's"),249 251: (51.5569, -0.3366, "Sudbury Hill"),250 252: (51.5507, -0.3156, "Sudbury Town"),251 253: (51.4933, -0.0478, "Surrey Quays"),252 254: (51.5432, -0.1738, "Swiss Cottage"),253 255: (51.5111, -0.1141, "Temple"),254 257: (51.4361, -0.1598, "Tooting Bec"),255 258: (51.4275, -0.168, "Tooting Broadway"),256 259: (51.5165, -0.131, "Tottenham Court Road"),257 260: (51.5882, -0.0594, "Tottenham Hale"),258 262: (51.5106, -0.0743, "Tower Gateway"),259 263: (51.5098, -0.0766, "Tower Hill"),260 264: (51.5567, -0.1374, "Tufnell Park"),261 265: (51.4951, -0.2547, "Turnham Green"),262 266: (51.5904, -0.1028, "Turnpike Lane"),263 267: (51.559, 0.251, "Upminster"),264 268: (51.5582, 0.2343, "Upminster Bridge"),265 269: (51.5385, 0.1014, "Upney"),266 270: (51.5352, 0.0343, "Upton Park"),267 271: (51.5463, -0.4786, "Uxbridge"),268 272: (51.4861, -0.1253, "Vauxhall"),269 273: (51.4965, -0.1447, "Victoria"),270 274: (51.583, -0.0195, "Walthamstow Central"),271 275: (51.5775, 0.0288, "Wanstead"),272 276: (51.5043, -0.0558, "Wapping"),273 277: (51.5247, -0.1384, "Warren Street"),274 278: (51.5235, -0.1835, "Warwick Avenue"),275 279: (51.5036, -0.1143, "Waterloo"),276 281: (51.5519, -0.2963, "Wembley Central"),277 282: (51.5635, -0.2795, "Wembley Park"),278 283: (51.521, -0.2011, "Westbourne Park"),279 284: (51.5097, -0.0265, "Westferry"),280 285: (51.501, -0.1254, "Westminster"),281 286: (51.518, -0.2809, "West Acton"),282 287: (51.4872, -0.1953, "West Brompton"),283 288: (51.6095, -0.1883, "West Finchley"),284 289: (51.5287, 0.0056, "West Ham"),285 290: (51.5469, -0.1906, "West Hampstead"),286 291: (51.5795, -0.3533, "West Harrow"),287 292: (51.507, -0.0203, "West India Quay"),288 293: (51.4907, -0.2065, "West Kensington"),289 294: (51.5696, -0.4376, "West Ruislip"),290 295: (51.5194, -0.0612, "Whitechapel"),291 296: (51.512, -0.2239, "White City"),292 297: (51.5492, -0.2215, "Willesden Green"),293 298: (51.5326, -0.2478, "Willesden Junction"),294 299: (51.4214, -0.2064, "Wimbledon"),295 300: (51.4343, -0.1992, "Wimbledon Park"),296 301: (51.607, 0.0341, "Woodford"),297 302: (51.6179, -0.1856, "Woodside Park"),298 303: (51.5975, -0.1097, "Wood Green"),299 35: (51.4627, -0.1145, "Brixton"),300 6: (51.6736, -0.607, "Amersham"),301 23: (51.4979, -0.0637, "Bermondsey"),302 50: (51.7052, -0.611, "Chesham"),303 46: (51.6679, -0.561, "Chalfont & Latimer"),304 53: (51.6543, -0.5183, "Chorleywood"),305 214: (51.6404, -0.4733, "Rickmansworth"),306 62: (51.647, -0.4412, "Croxley"),307 280: (51.6573, -0.4177, "Watford"),308 221: (51.5606, -0.4103, "Ruislip Gardens"),309 121: (51.6503, -0.1943, "High Barnet"),310 261: (51.6302, -0.1791, "Totteridge & Whetstone"),311 57: (51.6517, -0.1496, "Cockfosters"),312 187: (51.6476, -0.1318, "Oakwood"),313 232: (51.6322, -0.128, "Southgate"),314 88: (51.6937, 0.1139, "Epping"),315 256: (51.6717, 0.1033, "Theydon Bois"),316 68: (51.6455, 0.0838, "Debden"),317 158: (51.6412, 0.0558, "Loughton"),318 37: (51.6266, 0.0471, "Buckhurst Hill"),319 204: (51.5343, -0.0139, "Pudding Mill Lane"),320 233: (51.501, -0.1052, "Southwark"),321 41: (51.4982, -0.0502, "Canada Water"),322 43: (51.5147, 0.0082, "Canning Town"),323 183: (51.5005, 0.0039, "North Greenwich"),324 64: (51.4827, -0.0096, "Cutty Sark"),325 106: (51.4781, -0.0149, "Greenwich"),326 69: (51.474, -0.0216, "Deptford Bridge"),327 86: (51.4693, -0.0174, "Elverson Road"),328 152: (51.4657, -0.0142, "Lewisham"),329 174: (51.4767, -0.0327, "New Cross"),330 175: (51.4757, -0.0402, "New Cross Gate"),331 }332 333 london_underground_lines = { # line: "name"334 1: "Bakerloo Line",335 3: "Circle Line",336 6: "Hammersmith & City Line",337 7: "Jubilee Line",338 11: "Victoria Line",339 2: "Central Line",340 4: "District Line",341 5: "East London Line",342 8: "Metropolitan Line",343 9: "Northern Line",344 10: "Piccadilly Line",345 12: "Waterloo & City Line",346 13: "Docklands Light Railway",347 }348 349 london_underground_connections = [ # (station1,station2), (line, time)350 (11, 163), (1, 1),351 (11, 212), (1, 2),352 (49, 87), (1, 1),353 (49, 197), (1, 2),354 (82, 163), (1, 2),355 (82, 193), (1, 3),356 (84, 148), (1, 3),357 (87, 279), (1, 2),358 (113, 246), (1, 2),359 (113, 298), (1, 2),360 (114, 140), (1, 2),361 (137, 206), (1, 3),362 (137, 298), (1, 3),363 (140, 237), (1, 2),364 (143, 159), (1, 2),365 (143, 206), (1, 2),366 (148, 279), (1, 1),367 (159, 278), (1, 1),368 (185, 237), (1, 2),369 (185, 281), (1, 2),370 (192, 197), (1, 2),371 (192, 212), (1, 2),372 (193, 278), (1, 2),373 (246, 281), (1, 3),374 (13, 156), (2, 2),375 (13, 250), (2, 2),376 (16, 91), (2, 2),377 (16, 173), (2, 2),378 (24, 156), (2, 3),379 (24, 164), (2, 2),380 (28, 162), (2, 1),381 (28, 192), (2, 1),382 (37, 158), (2, 3),383 (37, 301), (2, 3),384 (48, 126), (2, 1),385 (48, 250), (2, 2),386 (51, 103), (2, 2),387 (51, 215), (2, 2),388 (68, 158), (2, 2),389 (68, 256), (2, 3),390 (72, 286), (2, 3),391 (76, 181), (2, 2),392 (76, 296), (2, 3),393 (88, 256), (2, 2),394 (91, 109), (2, 2),395 (98, 173), (2, 3),396 (98, 211), (2, 2),397 (103, 109), (2, 3),398 (105, 177), (2, 2),399 (105, 196), (2, 2),400 (112, 181), (2, 3),401 (112, 196), (2, 2),402 (126, 259), (2, 2),403 (127, 186), (2, 2),404 (127, 226), (2, 1),405 (149, 162), (2, 3),406 (149, 208), (2, 1),407 (153, 154), (2, 3),408 (153, 247), (2, 2),409 (154, 230), (2, 2),410 (154, 275), (2, 2),411 (164, 247), (2, 4),412 (177, 239), (2, 3),413 (181, 286), (2, 2),414 (186, 208), (2, 2),415 (192, 259), (2, 2),416 (211, 275), (2, 2),417 (215, 301), (2, 3),418 (221, 239), (2, 1),419 (221, 294), (2, 3),420 (226, 296), (2, 3),421 (230, 241), (2, 2),422 (241, 301), (2, 2),423 (2, 156), (3, 2),424 (2, 263), (3, 4),425 (11, 83), (3, 3),426 (11, 104), (3, 3),427 (14, 92), (3, 1),428 (14, 167), (3, 2),429 (18, 186), (3, 2),430 (18, 193), (3, 2),431 (25, 161), (3, 1),432 (25, 255), (3, 2),433 (44, 161), (3, 1),434 (44, 166), (3, 2),435 (83, 193), (3, 3),436 (87, 255), (3, 2),437 (87, 285), (3, 2),438 (90, 104), (3, 2),439 (90, 145), (3, 2),440 (92, 145), (3, 4),441 (99, 122), (3, 4),442 (99, 236), (3, 1),443 (122, 186), (3, 3),444 (156, 167), (3, 2),445 (166, 263), (3, 2),446 (229, 236), (3, 2),447 (229, 273), (3, 2),448 (248, 273), (3, 2),449 (248, 285), (3, 2),450 (3, 263), (4, 2),451 (3, 295), (4, 2),452 (15, 78), (4, 4),453 (15, 269), (4, 2),454 (17, 110), (4, 1),455 (17, 293), (4, 2),456 (18, 186), (4, 2),457 (18, 193), (4, 2),458 (21, 67), (4, 3),459 (21, 269), (4, 2),460 (25, 161), (4, 1),461 (25, 255), (4, 2),462 (33, 36), (4, 2),463 (33, 164), (4, 1),464 (36, 289), (4, 2),465 (44, 161), (4, 1),466 (44, 166), (4, 2),467 (52, 1), (4, 2),468 (52, 265), (4, 2),469 (66, 67), (4, 4),470 (66, 85), (4, 3),471 (72, 73), (4, 4),472 (73, 1), (4, 2),473 (74, 99), (4, 3),474 (74, 122), (4, 3),475 (74, 138), (4, 2),476 (74, 287), (4, 2),477 (74, 293), (4, 1),478 (78, 270), (4, 2),479 (80, 205), (4, 2),480 (80, 231), (4, 2),481 (83, 193), (4, 3),482 (85, 129), (4, 2),483 (87, 255), (4, 2),484 (87, 285), (4, 2),485 (96, 195), (4, 2),486 (96, 287), (4, 1),487 (99, 236), (4, 1),488 (108, 141), (4, 3),489 (108, 265), (4, 3),490 (110, 209), (4, 2),491 (122, 186), (4, 3),492 (129, 268), (4, 2),493 (141, 213), (4, 3),494 (164, 244), (4, 2),495 (166, 263), (4, 2),496 (195, 205), (4, 3),497 (200, 270), (4, 2),498 (200, 289), (4, 2),499 (209, 242), (4, 2),500 (229, 236), (4, 2),501 (229, 273), (4, 2),502 (231, 300), (4, 3),503 (242, 265), (4, 1),504 (244, 295), (4, 3),505 (248, 273), (4, 2),506 (248, 285), (4, 2),507 (267, 268), (4, 3),508 (299, 300), (4, 3),509 (4, 70), (13, 2),510 (4, 201), (13, 2),511 (13, 225), (13, 2),512 (19, 97), (13, 2),513 (20, 65), (13, 2),514 (20, 217), (13, 2),515 (27, 79), (13, 2),516 (27, 201), (13, 2),517 (32, 70), (13, 2),518 (32, 204), (13, 2),519 (42, 120), (13, 2),520 (42, 292), (13, 2),521 (43, 79), (13, 2),522 (43, 219), (13, 2),523 (61, 171), (13, 2),524 (61, 238), (13, 2),525 (63, 203), (13, 2),526 (63, 219), (13, 2),527 (64, 106), (13, 2),528 (64, 135), (13, 2),529 (65, 97), (13, 2),530 (69, 86), (13, 2),531 (69, 106), (13, 2),532 (86, 152), (13, 2),533 (120, 238), (13, 2),534 (135, 171), (13, 2),535 (155, 225), (13, 2),536 (155, 284), (13, 2),537 (201, 284), (13, 2),538 (201, 292), (13, 2),539 (203, 217), (13, 2),540 (204, 247), (13, 2),541 (225, 262), (13, 2),542 (284, 292), (13, 2),543 (41, 216), (5, 1),544 (41, 253), (5, 2),545 (174, 253), (5, 4),546 (175, 253), (5, 4),547 (216, 276), (5, 1),548 (225, 276), (5, 1),549 (225, 295), (5, 2),550 (228, 295), (5, 2),551 (3, 156), (6, 4),552 (3, 295), (6, 2),553 (11, 83), (6, 3),554 (11, 104), (6, 3),555 (14, 92), (6, 1),556 (14, 167), (6, 2),557 (15, 78), (6, 4),558 (33, 36), (6, 2),559 (33, 164), (6, 1),560 (36, 289), (6, 2),561 (78, 270), (6, 2),562 (83, 193), (6, 4),563 (90, 104), (6, 2),564 (90, 145), (6, 2),565 (92, 145), (6, 4),566 (101, 110), (6, 2),567 (101, 227), (6, 1),568 (147, 150), (6, 1),569 (147, 283), (6, 2),570 (150, 227), (6, 2),571 (156, 167), (6, 2),572 (164, 244), (6, 2),573 (193, 218), (6, 1),574 (200, 270), (6, 2),575 (200, 289), (6, 2),576 (218, 283), (6, 2),577 (244, 295), (6, 3),578 (11, 28), (7, 2),579 (11, 249), (7, 4),580 (23, 41), (7, 2),581 (23, 157), (7, 3),582 (28, 107), (7, 2),583 (41, 42), (7, 3),584 (42, 183), (7, 3),585 (43, 183), (7, 3),586 (43, 289), (7, 3),587 (45, 207), (7, 2),588 (45, 243), (7, 2),589 (71, 172), (7, 2),590 (71, 297), (7, 2),591 (94, 254), (7, 2),592 (94, 290), (7, 1),593 (107, 285), (7, 3),594 (142, 290), (7, 2),595 (142, 297), (7, 2),596 (144, 207), (7, 2),597 (144, 282), (7, 4),598 (157, 233), (7, 2),599 (172, 282), (7, 4),600 (233, 279), (7, 1),601 (247, 289), (7, 3),602 (249, 254), (7, 1),603 (279, 285), (7, 2),604 (2, 156), (8, 2),605 (6, 46), (8, 4),606 (11, 94), (8, 6),607 (11, 104), (8, 3),608 (14, 92), (8, 1),609 (14, 167), (8, 2),610 (46, 50), (8, 8),611 (46, 53), (8, 4),612 (53, 214), (8, 4),613 (62, 168), (8, 4),614 (62, 280), (8, 3),615 (75, 210), (8, 2),616 (75, 222), (8, 2),617 (90, 104), (8, 2),618 (90, 145), (8, 2),619 (92, 145), (8, 4),620 (94, 282), (8, 7),621 (115, 178), (8, 2),622 (115, 184), (8, 3),623 (115, 291), (8, 2),624 (125, 134), (8, 2),625 (125, 271), (8, 3),626 (134, 220), (8, 3),627 (156, 167), (8, 2),628 (168, 179), (8, 3),629 (168, 214), (8, 4),630 (178, 202), (8, 2),631 (179, 180), (8, 2),632 (180, 199), (8, 2),633 (184, 199), (8, 3),634 (202, 282), (8, 3),635 (210, 291), (8, 3),636 (220, 222), (8, 2),637 (7, 145), (9, 2),638 (7, 188), (9, 3),639 (8, 124), (9, 3),640 (8, 264), (9, 2),641 (12, 56), (9, 2),642 (12, 257), (9, 1),643 (13, 157), (9, 2),644 (13, 167), (9, 3),645 (22, 47), (9, 2),646 (22, 111), (9, 2),647 (29, 84), (9, 1),648 (29, 157), (9, 2),649 (34, 100), (9, 3),650 (34, 119), (9, 2),651 (38, 58), (9, 2),652 (38, 81), (9, 3),653 (40, 47), (9, 2),654 (40, 89), (9, 3),655 (40, 139), (9, 2),656 (40, 170), (9, 1),657 (49, 87), (9, 1),658 (49, 151), (9, 2),659 (54, 55), (9, 2),660 (54, 56), (9, 2),661 (55, 245), (9, 1),662 (58, 119), (9, 3),663 (59, 240), (9, 2),664 (59, 258), (9, 2),665 (77, 93), (9, 4),666 (77, 124), (9, 2),667 (84, 136), (9, 2),668 (87, 279), (9, 2),669 (89, 145), (9, 2),670 (89, 170), (9, 2),671 (89, 277), (9, 1),672 (93, 165), (9, 3),673 (93, 288), (9, 2),674 (100, 111), (9, 4),675 (102, 259), (9, 1),676 (102, 277), (9, 2),677 (121, 261), (9, 3),678 (136, 191), (9, 2),679 (136, 279), (9, 3),680 (139, 264), (9, 2),681 (151, 259), (9, 1),682 (167, 188), (9, 1),683 (169, 240), (9, 4),684 (191, 245), (9, 3),685 (257, 258), (9, 2),686 (261, 302), (9, 3),687 (288, 302), (9, 1),688 (1, 73), (10, 2),689 (1, 234), (10, 4),690 (1, 265), (10, 3),691 (5, 194), (10, 3),692 (5, 252), (10, 2),693 (9, 31), (10, 3),694 (9, 232), (10, 3),695 (10, 95), (10, 2),696 (10, 128), (10, 1),697 (17, 74), (10, 3),698 (17, 110), (10, 2),699 (30, 176), (10, 2),700 (30, 190), (10, 3),701 (31, 303), (10, 2),702 (39, 128), (10, 2),703 (39, 145), (10, 5),704 (57, 187), (10, 4),705 (60, 126), (10, 1),706 (60, 151), (10, 1),707 (73, 182), (10, 3),708 (74, 99), (10, 2),709 (75, 210), (10, 2),710 (75, 222), (10, 2),711 (95, 160), (10, 2),712 (99, 236), (10, 1),713 (107, 133), (10, 2),714 (107, 197), (10, 1),715 (110, 265), (10, 2),716 (116, 117), (10, 3),717 (116, 118), (10, 3),718 (116, 132), (10, 4),719 (117, 118), (10, 5),720 (125, 134), (10, 2),721 (125, 271), (10, 3),722 (126, 223), (10, 2),723 (130, 131), (10, 2),724 (130, 132), (10, 2),725 (131, 190), (10, 2),726 (133, 146), (10, 2),727 (134, 220), (10, 3),728 (145, 223), (10, 2),729 (146, 236), (10, 3),730 (151, 197), (10, 2),731 (160, 266), (10, 3),732 (176, 234), (10, 1),733 (182, 194), (10, 2),734 (187, 232), (10, 3),735 (210, 235), (10, 3),736 (220, 222), (10, 2),737 (235, 251), (10, 2),738 (251, 252), (10, 3),739 (266, 303), (10, 2),740 (26, 260), (11, 2),741 (26, 274), (11, 2),742 (35, 245), (11, 2),743 (89, 145), (11, 2),744 (89, 277), (11, 1),745 (95, 123), (11, 2),746 (95, 224), (11, 4),747 (107, 192), (11, 2),748 (107, 273), (11, 2),749 (123, 145), (11, 4),750 (192, 277), (11, 2),751 (198, 272), (11, 1),752 (198, 273), (11, 3),753 (224, 260), (11, 3),754 (245, 272), (11, 3),755 (13, 279), (12, 4),756 ]757 758 g = Graph()759 760 for sid, station in london_underground_stations.items():761 g.add_node(sid, obj=station)762 for i in range(0,len(london_underground_connections),2):763 n1,n2 = london_underground_connections[i]764 _,time = london_underground_connections[i+1]765 g.add_edge(n1, n2, time, bidirectional=True)766 return g767