graph 1

A B C D

A B 3 A C 10 A D 12 B C 1 B D 14 C D 4

graph 2

A B C D E F G H

A B 3 A C 12 A F 4 B G 19 B H 6 B C 4 C G 2 C H 18 C F 12 D E 7 F G 10 G H 20

graph 3

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z AA AB AC AD AE AF AG AH AI AJ AK AL AM AN AO AP AQ AR AS AT AU AV AW AX AY AZ

AQ Q 34 AG C 50 W M 5 AL K 13 AL L 45 W X 41 W Z 1 Y AM 34 W P 30 W AJ 39 W AI 6 W AG 1 W AB 15 W AX 20 W AY 19 W AV 48 H Q 33 W AQ 17 Y AU 13 AG R 49 M AV 7 M AW 7 M AH 43 M AI 22 M AF 44 U V 5 AL AT 12 AW AM 6 AG Z 7 J U 49 J N 21 J C 44 J E 39 AZ E 6 R C 6 AZ M 18 R M 9 AZ H 20 R O 15 AZ W 4 R R 24 R X 16 R Z 41 B S 20 B W 49 B B 7 B G 18 B H 32 B J 46 AS N 48 M V 22 M S 28 AD AX 25 AD AW 39 AR W 16 M Z 14 E L 11 AD AQ 31 AZ AV 33 E M 16 M C 23 M A 0 AD AF 10 AD AE 14 AD AC 28 M I 44 AL W 21 R AM 50 R AL 5 AE AC 6 R AI 49 AL U 45 AE AG 49 AF E 39 AQ L 4 R AA 47 R AC 9 AQ I 45 AE AR 22 AE AW 29 AE AX 11 AQ Y 43 AA U 36 AA F 34 AA E 38 AA O 41 AA J 44 AA I 47 S AX 47 S AY 0 E F 30 AF C 29 E E 37 S AV 24 AF G 16 AF F 4 AF Z 37 S AN 0 E V 48 S AC 47 AF U 36 E S 30 S AD 7 X AO 47 X AM 8 X AL 36 X AK 11 X AC 41 X AT 23 X AQ 14 AY AH 33 Z L 36 AS U 27 Z A 31 Z E 38 U S 46 U N 15 U O 33 F AS 36 F AR 23 F AU 21 F AT 26 U H 37 F AY 50 AV B 14 Z U 44 U C 17 AV F 10 AH G 25 G AV 35 G AU 47 G AL 3 AH T 18 AH S 6 AZ AP 21 G AG 37 AH Y 3 AS AS 11 AK M 47 AK H 40 P X 10 AK A 40 P D 32 P I 26 N AX 34 N AU 3 N AV 42 N AL 44 N AO 33 AL AM 6 AM Z 22 AM Q 48 AP AV 44 AP AB 7 AM A 44 AP AG 8 AP AE 34 O AV 43 O AW 22 H H 38 O AS 44 H F 34 H E 4 O AY 10 O AG 34 H Y 10 O AE 3 H R 50 O AL 2 AQ AL 28 L AB 0 AH AH 27 AH AS 38 AH AR 4 AH AV 35 AH AZ 38 AH AX 0 AQ AP 48 AW AA 49 AK AX 19 AK AY 25 AK AW 1 AK AT 37 B AO 7 AN AD 17 AK AL 41 AK AJ 27 AK AK 36 AK AB 2 L AI 22 K D 5 K H 16 AM AO 25 K M 21 K S 17 K Z 40 X Z 31 U B 22 X Q 45 AR V 46 AR S 46 X T 31 X K 41 X J 4 AR N 9 AX O 23 AR H 37 AR J 42 AR D 41 X E 13 AR B 45 AJ AU 37 AJ AT 39 AJ AW 31 AJ AQ 38 AD W 36 AJ AF 12 AJ AJ 41 F D 22 A F 41 AX AU 15 AO AO 3 AO AR 17 AO AS 36 AO AP 39 AO AW 35 AO AX 25 AX AL 43 AX V 27 S F 25 S G 25 S Z 7 S P 36 S R 42 AX L 4 AX K 43 AB M 13 C Z 0 AB N 3 A AY 3 AY AB 0 V V 42 AB G 34 A AW 39 T AW 42 T AV 13 C V 23 A AS 22 T AK 50 T AI 21 C K 3 A AI 18 T AM 12 T AL 16 AB T 38 T AA 28 C E 20 AB S 19 T AD 2 AG A 41 Y AG 8 AG D 46 AG E 47 Y AB 43 N T 15 Y AJ 4 N L 39 Y AV 20 Y AW 16 N H 36 Y AS 42 N G 36 N A 18 N C 27 AI AT 2 AT AT 3 AI AP 34 AI AX 36 AI AZ 32 AI AD 45 AH O 11 AI AF 18 AI AJ 37 AW R 18 AW D 14 AW J 44 AW K 14 AN AX 49 AW AX 26 AW AP 9 AN AR 33 H AS 45 AN AW 8 AV K 26 AN AH 13 AW AH 31 AW AI 39 AN AM 31 H AJ 34 AN AN 22 AW AB 46 AZ AQ 11 H AD 50 H AB 10 F U 35 AD X 20 P AS 9 AZ AM 2 AD Q 25 F Y 20 P AZ 41 AD K 32 P AF 30 F F 7 P AC 19 P AB 0 F B 24 P AM 46 P AJ 0 F K 46 AV AU 14 U AU 34 AV AV 34 AV AA 8 U AB 35 AV AF 44 U AJ 21 AV AM 37 AV AN 45 AQ E 20 AZ V 11 AN T 2 C W 46 AN A 34 AV AK 50 AC AF 27 V D 0 V A 37 AC AA 50 Q S 44 V J 28 Q J 49 AC AW 3 AC AT 29 AC AU 10 AI K 30 V S 15 AO A 12 Q B 42 AI G 24 Q G 38 I AT 14 I AW 3 I AS 22 I AX 6 AV E 32 AL AV 16 G G 25 I U 21 I X 49 I Y 44 AO S 24 AL AY 36 I B 48 I A 0 AL AA 7 I E 36 I H 6 AS J 37 AS K 16 AM AY 37 AM AP 35 K AK 5 AM AS 2 K AN 13 K AO 18 B AS 11 B AM 50 K AP 17 K AQ 17 AM AM 22 K AU 31 B AF 5 AM AE 16 B AB 17 A H 14 Q AJ 20 AB AU 17 A C 32 Q AG 47 AB AQ 9 AB AR 14 Q AX 40 AB AJ 8 AB AE 35 Q AU 14 A P 38 Q AW 4 A W 2 AB AC 7 Q AS 29 L F 35 L X 21 L R 32 AX AB 36 C AD 42 C AX 44 C AR 20 C AU 46 AY N 13 AY H 35 AY G 12 AY E 22 AY B 11 AY C 17 AY X 41 AU X 25 AC D 14 AC G 22 AC H 8 AC I 30 AC J 20 Z AJ 48 Z AQ 23 Z AR 39 AC Z 47 Z AZ 44 D AJ 39 D AI 27 D C 32 D A 30 D AL 36 D N 21 D L 40 D AZ 27 D AY 8 D AX 15 Z AK 1 D AS 1 D AQ 42 AC K 10 J AU 28 M J 6 J AG 9 J AO 4 J AN 44 J AI 2 J AH 12 T S 14 T Z 45 Y Q 5 Y V 49 T A 39 Y X 16 AP R 35 AP P 21 AU AK 30 AU AL 7 AU AN 34 AG AJ 33 AE P 43 AG AI 48 AG AO 10 AE U 17 AE Z 3 AE X 42 AS AY 7 AS AG 26 AS AE 42 AS AC 39 AG AR 1 AE H 24 AT D 25 AS AJ 2 L AC 30 O E 33 L AG 24 L AF 39 O C 10 L AJ 8 O N 2 V W 27 L AM 9 O V 18 Q I 6 L AW 26 L AZ 24 O Z 18 C X 5 AT AH 40 AQ AU 11 AA AR 28 AA AM 16 AA AN 35 T AX 49 AT AZ 28 AT AY 14 AT R 9 AW AG 27 AA AG 23 AT AS 20 AT AR 28 AA AB 2 AT AP 1 V AT 21 V AV 22 V AB 15 V AE 37 A AU 0 AY AN 44 AQ F 43 G X 16 G T 20 A AP 15 G V 15 AF AL 31 G L 50 R AN 43 AO P 23 AQ B 30 G F 24 T AT 24 AO U 2 AU B 19 AJ T 36 AQ A 0 AY AV 19 AU R 8 AU S 19 AJ F 48 AU V 25 AJ B 44 AR AY 27 AJ O 13 AT Z 32 AD AJ 23 O AU 11 AE AN 18 A AF 19 AF AA 27 E AC 17 AF AH 28 E AM 7 AF AO 28 E AO 12 AF AQ 46 AF AP 13 E AT 29 E AU 34 E AW 36 E AX 2 AR AW 50 C G 33

Design and implement a Graph class using one of the frameworks discussed in class. Your graph must be able to load in files: graph1.txt, graph2.txt, and graph3.txt and represent the graphs contained within them. The files give you first a list of all nodes in the graph, one node per line, an empty line, then the list of edges. Each edge is represented as A B X, where A and B are the nodes, and X is the weight attached to them. The graphs that are being passed in are UNDIRECTED (that is, if you have and edge (A, B), you have the edge (B, A) as well. Your graph representation must be able to do the following:

1.Insert new nodes and edges into the graph, and account for the undirected nature of the graph.

2.Determine if the graph is connected.

3.Given a node that is in the graph, output the shortest path to all other nodes in the graph (if one exists). (Prompt the user for input, determine if the node is in the graph, and then print out the shortest path to every other node in the graph).