CS 3343/3341, Graph of Capitals

CS 3343/3341
Analysis of Algorithms
Spring 2012

Graph of Capitals in USA

Node names and locations in a grid, plus main class.	Pairs of edges and weights. Plus main class.
// ListNode.java: Coordinate data for nodes. // Needed only to display the graph neatly. public class ListNode { public String nodeName; // name of node public int xCoord; // coords in an public int yCoord; // integer grid. public ListNode(String name, int x, int y) { nodeName = name; xCoord = x; yCoord = y; } } // List.java: Construct list and grid // locations in file "capsloc.txt" import java.io.; public class List { private ListNode[] list; public int count; // program counts nodes private Reader in; // internal input file private int MAXCOUNT = 50; public List (String fileName) { list = new ListNode[MAXCOUNT]; count = 0; try { in = new FileReader(fileName); } catch (IOException e) { System.out.println("Excep. " + fileName); } // nasty scanning by hand; no Java tools int ch = getNextChar(); while (true) { if (ch == -1) break; String name = ""; while (!Character.isWhitespace(ch)) { name = name + (char)ch; ch = getNextChar(); } while ((ch = getNextChar()) == ' ') ; int num1 = 0; while (Character.isDigit(ch)) { num1 = 10num1 + (ch - '0'); ch = getNextChar(); } while ((ch = getNextChar()) == ' ') ; int num2 = 0; while (Character.isDigit(ch)) { num2 = 10num2 + (ch - '0'); ch = getNextChar(); } while ((ch = getNextChar()) == ' ') ; System.out.print("," + num2 + "\n"); // insert into the list list[count] = new ListNode(name, num1, num2); count++; if (count >= MAXCOUNT) { System.exit(2); } if (ch == '\n') ch = getNextChar(); } } private int getNextChar() { int ch; try { ch = in.read(); } catch (Exception exception ) { System.err.println("Read Error"); ch = -1; } return ch; } public int getCount() { return count; } public String getNodeName(int capNum) { return list[capNum].nodeName; } public int getXCoord(int capNum) { return list[capNum].xCoord; } public int getYCoord(int capNum) { return list[capNum].yCoord; } public int getNum(String name) { for (int i = 0; i < count; i++) { if (list[i].nodeName.equals(name)) return i; } return -1; } public void printList() { for (int i = 0; i < count; i++) System.out.print( list[i].nodeName + " " + list[i].xCoord + " " + list[i].yCoord + "\n"); } } // GraphMain.java: Controls Graph Program import java.io.; public class GraphMain { public static void main(String[] args) { // "capsloc.txt" is a file of node names, // along with the two grid coordinates. List list = new List("capsloc.txt"); // list.printList(); int count = list.getCount(); // "capsdist.txt" gives pairs of nodes, // and distances between them -- // edges and weights of the graph. Graph graph = new Graph( "capsdist.txt", count, list); graph.printGraph(); } }	// EdgeNode.java: holds graph's edge info // Implement adjacency list public class EdgeNode { public int vertexNum; // vertex num public EdgeNode nextEdgeNode; // next public int edgeDist; // edge length // other edge info here public EdgeNode(int num, EdgeNode node, int dist) { vertexNum = num; nextEdgeNode = node; edgeDist = dist; // initialize other edge info here } } // GraphNode.java: node for graph's vertex // Holds vertex info, link to adj. list public class GraphNode { public EdgeNode firstEdgeNode; // other vertex info here public GraphNode() { firstEdgeNode = null; // initialize other vertex info here } } // Graph.java: set up data structure for graph import java.io.; public class Graph { private int count; // number of nodes private Reader in; // internal input file name private GraphNode[] graph; private List list; public Graph(String fileName, int ct, List cList) { count = ct; list = cList; graph = new GraphNode[count]; for (int i = 0; i < count; i++) graph[i] = null; try { in = new FileReader(fileName); } catch (IOException e) { System.out.println("Exception opening "+ fileName); } int ch = getNextChar(); while (true) { if (ch == -1) break; String name1 = ""; // parse the pieces of each line while (!Character.isWhitespace(ch)) { name1 = name1 + (char)ch; ch = getNextChar(); } while ((ch = getNextChar()) == ' ') ; String name2 = ""; // parse the pieces of each line while (!Character.isWhitespace(ch)) { name2 = name2 + (char)ch; ch = getNextChar(); } while ((ch = getNextChar()) == ' ') ; int num = 0; while (Character.isDigit(ch)) { num = 10num + (ch - '0'); ch = getNextChar(); } while ((ch = getNextChar()) == ' ') ; if (ch == '\n') ch = getNextChar(); // carry out insertions, both directions insert(name1, name2, num); insert(name2, name1, num); } } private int getNextChar() { int ch; try { ch = in.read(); } catch (Exception exception ) { System.err.println("Read Error"); ch = -1; } return ch; } private void insert(String name1, String name2, int dist) { // goes into the node corresp. to name2 int num1 = list.getNum(name1); int num2 = list.getNum(name2); // patch the new node in at the start GraphNode node = graph[num1]; if (node == null) { GraphNode gnode = new GraphNode(); graph[num1] = gnode; EdgeNode enode = new EdgeNode(num2, null, dist); graph[num1].firstEdgeNode = enode; } else { EdgeNode enode = new EdgeNode(num2, graph[num1].firstEdgeNode, dist); graph[num1].firstEdgeNode = enode; } } public void printGraph() { for (int i = 0; i < count; i++) { if (i < 10) System.out.print(" "); System.out.print(i + "(" + list.getNodeName(i) + "): "); EdgeNode node = graph[i].firstEdgeNode; while (node != null) { System.out.print("["+node.vertexNum+"(" + list.getNodeName(node.vertexNum) + ")," + node.edgeDist + "]"); node = node.nextEdgeNode; if (node != null)System.out.print(","); else System.out.print("\n"); } } } }

Node names and locations in a grid, plus main class.

Pairs of edges and weights. Plus main class.

// ListNode.java:  Coordinate data for nodes.
//  Needed only to display the graph neatly.
public class ListNode {
   public String nodeName; // name of node
   public int xCoord; // coords in an
   public int yCoord; // integer grid.

   public ListNode(String name, int x, int y) {
      nodeName = name;
      xCoord = x;
      yCoord = y;
   }
}
// List.java: Construct list and grid
//   locations in file "capsloc.txt"
import java.io.*;
public class List {
   private ListNode[] list;
   public int count; // program counts nodes
   private Reader in; // internal input file
   private int MAXCOUNT = 50;

   public List (String fileName) {
      list = new ListNode[MAXCOUNT];
      count = 0;
      try {
         in = new FileReader(fileName);
      } catch (IOException e) {
         System.out.println("Excep. " +
            fileName);
      }
      // nasty scanning by hand; no Java tools
      int ch = getNextChar();
      while (true) {
         if (ch == -1) break;
         String name = "";
         while (!Character.isWhitespace(ch)) {
            name = name + (char)ch;
            ch = getNextChar();
         }
         while ((ch = getNextChar()) == ' ')
            ;
         int num1 = 0;
         while (Character.isDigit(ch)) {
            num1 = 10*num1 + (ch - '0');
            ch = getNextChar();
         }
         while ((ch = getNextChar()) == ' ')
            ;
         int num2 = 0;
         while (Character.isDigit(ch)) {
            num2 = 10*num2 + (ch - '0');
            ch = getNextChar();
         }
         while ((ch = getNextChar()) == ' ')
            ;
         System.out.print("," + num2 + "\n");
         // insert into the list
         list[count] =
            new ListNode(name, num1, num2);
         count++;
         if (count >= MAXCOUNT) {
            System.exit(2);
         }
         if (ch == '\n') ch = getNextChar();
      }
   }

   private int getNextChar() {
      int ch;
      try {
         ch = in.read();
      }
      catch (Exception exception ) {
         System.err.println("Read Error");
         ch = -1;
      }
      return ch;
   }
   public int getCount() {
      return count;
   }
   public String getNodeName(int capNum) {
      return list[capNum].nodeName;
   }
   public int getXCoord(int capNum) {
      return list[capNum].xCoord;
   }
   public int getYCoord(int capNum) {
      return list[capNum].yCoord;
   }
   public int getNum(String name) {
      for (int i = 0; i < count; i++) {
         if (list[i].nodeName.equals(name))
            return i;
      }
      return -1;
   }

   public void printList() {
      for (int i = 0; i < count; i++)
         System.out.print(
            list[i].nodeName + " " +
            list[i].xCoord + " " +
            list[i].yCoord + "\n");
   }
}
// GraphMain.java: Controls Graph Program
import java.io.*;
public class GraphMain {

   public static void main(String[] args) {
       // "capsloc.txt" is a file of node names,
       //   along with the two grid coordinates.
       List list = new List("capsloc.txt");
       // list.printList();
       int count = list.getCount();
       // "capsdist.txt" gives pairs of nodes,
       //   and distances between them --
       //   edges and weights of the graph.
       Graph graph = new Graph(
             "capsdist.txt", count, list);
       graph.printGraph();
   }
}

// EdgeNode.java: holds graph's edge info
//  Implement adjacency list
public class EdgeNode {
   public int vertexNum; // vertex num
   public EdgeNode nextEdgeNode; // next
   public int edgeDist; // edge length
   // other edge info here

   public EdgeNode(int num, EdgeNode node,
         int dist) {
      vertexNum = num;
      nextEdgeNode = node;
      edgeDist = dist;
      // initialize other edge info here
   }
}
// GraphNode.java: node for graph's vertex
//  Holds vertex info, link to adj. list
public class GraphNode {
   public EdgeNode firstEdgeNode;
   // other vertex info here

   public GraphNode() {
      firstEdgeNode = null;
      // initialize other vertex info here
   }
}
// Graph.java: set up data structure for graph
import java.io.*;
public class Graph {
   private int count; // number of nodes
   private Reader in; // internal input file name
   private GraphNode[] graph;
   private List list;

   public Graph(String fileName, int ct,
         List cList) {
      count = ct;
      list = cList;
      graph = new GraphNode[count];
      for (int i = 0; i < count; i++)
         graph[i] = null;
      try {
         in = new FileReader(fileName);
      } catch (IOException e) {
         System.out.println("Exception opening "+
            fileName);
      }
      int ch = getNextChar();
      while (true) {
         if (ch == -1) break;
         String name1 = "";
         // parse the pieces of each line
         while (!Character.isWhitespace(ch)) {
            name1 = name1 + (char)ch;
            ch = getNextChar();
         }
         while ((ch = getNextChar()) == ' ')
            ;
         String name2 = "";
         // parse the pieces of each line
         while (!Character.isWhitespace(ch)) {
            name2 = name2 + (char)ch;
            ch = getNextChar();
         }
         while ((ch = getNextChar()) == ' ')
            ;
         int num = 0;
         while (Character.isDigit(ch)) {
            num = 10*num + (ch - '0');
            ch = getNextChar();
         }
         while ((ch = getNextChar()) == ' ')
            ;
         if (ch == '\n') ch = getNextChar();
         // carry out insertions, both directions
         insert(name1, name2, num);
         insert(name2, name1, num);
     }
   }

   private int getNextChar() {
      int ch;
      try {
         ch = in.read();
      }
      catch (Exception exception ) {
         System.err.println("Read Error");
         ch = -1;
      }
      return ch;
   }

   private void insert(String name1, String name2,
         int dist) {
      // goes into the node corresp. to name2
      int num1 = list.getNum(name1);
      int num2 = list.getNum(name2);
      // patch the new node in at the start
      GraphNode node = graph[num1];
      if (node == null) {
         GraphNode gnode = new GraphNode();
         graph[num1] = gnode;
         EdgeNode enode = new EdgeNode(num2, null,
            dist);
         graph[num1].firstEdgeNode = enode;
      }
      else {
         EdgeNode enode = new EdgeNode(num2,
            graph[num1].firstEdgeNode, dist);
         graph[num1].firstEdgeNode = enode;
      }
   }

   public void printGraph() {
      for (int i = 0; i < count; i++) {
         if (i < 10) System.out.print(" ");
         System.out.print(i + "(" +
             list.getNodeName(i) + "): ");
         EdgeNode node = graph[i].firstEdgeNode;
         while (node != null) {
            System.out.print("["+node.vertexNum+"("
               + list.getNodeName(node.vertexNum) +
               ")," + node.edgeDist + "]");
            node = node.nextEdgeNode;
            if (node != null)System.out.print(",");
            else System.out.print("\n");
         }
      }

   }
}

Locations
of Cities
file: capsloc.txt Distances Between Pairs of Cities
(Lengths of Edges)
file: capsdist.txt

Locations of Cities `file: capsloc.txt`		Distances Between Pairs of Cities (Lengths of Edges) `file: capsdist.txt`
CA 1 4 NV 2 4 OR 2 5 WA 2 6 AZ 3 3 UT 3 4 ID 3 5 NM 4 3 CO 4 4 WY 4 5 MT 4 6 TX 5 2 OK 5 3 KS 5 4 NE 5 5 SD 5 6 ND 5 7 LA 6 2 AR 6 3 MO 6 4 IA 6 5 MN 6 6 MS 7 2 IL 7 5	WI 7 6 AL 8 2 TN 8 3 KY 8 4 IN 8 5 MI 8 6 FL 9 1 GA 9 2 VA 9 3 WV 9 4 OH 9 5 SC 10 1 NC 10 2 MD 10 4 PA 10 5 DE 11 4 NJ 11 5 NY 11 6 VT 11 7 CT 12 5 MA 12 6 NH 12 7 RI 13 5 ME 13 7		CA AZ 755 CA NV 129 CA OR 535 NV AZ 713 NV UT 534 NV ID 541 NV OR 663 OR ID 441 OR WA 160 WA ID 619 AZ NM 476 AZ UT 652 UT CO 488 UT WY 435 UT ID 338 ID WY 727 ID MT 438 NM TX 697 NM OK 585 NM CO 355 CO OK 626 CO KS 536 CO NE 486 CO WY 100 WY NE 444 WY SD 455 WY MT 675	MT SD 742 MT ND 624 TX LA 430 TX AR 504 TX OK 388 OK AR 337 OK MO 416 OK KS 293 KS MO 204 KS NE 165 NE MO 343 NE IA 187 NE SD 392 SD IA 490 SD MN 404 SD ND 215 ND MN 435 LA MS 150 LA AR 416 AR MS 253 AR TN 344 AR MO 340 MO TN 453 MO KY 562 MO IL 192 MO IA 255	IA IL 291 IA WI 279 IA MN 244 MN WI 258 MS AL 242 MS TN 392 IL KY 415 IL IN 190 IL WI 249 WI MI 614 AL FL 205 AL GA 160 AL TN 282 TN GA 255 TN NC 530 TN VA 597 TN KY 203 KY VA 532 KY WV 197 KY OH 186 KY IN 145 IN OH 175 IN MI 244 MI OH 237 FL GA 252 GA SC 212	GA NC 434 VA NC 156 VA MD 129 VA WV 302 WV MD 397 WV PA 354 WV OH 160 OH PA 425 SC NC 200 MD DE 62 MD PA 103 PA DE 124 PA NJ 127 PA NY 268 DE NJ 108 NJ NY 193 NY CT 111 NY MA 165 NY VT 153 VT MA 236 VT NH 106 CT RI 72 CT MA 101 MA RI 45 MA NH 68 NH ME 139


CA  1  4
NV  2  4
OR  2  5
WA  2  6
AZ  3  3
UT  3  4
ID  3  5
NM  4  3
CO  4  4
WY  4  5
MT  4  6
TX  5  2
OK  5  3
KS  5  4
NE  5  5
SD  5  6
ND  5  7
LA  6  2
AR  6  3
MO  6  4
IA  6  5
MN  6  6
MS  7  2
IL  7  5


WI  7  6
AL  8  2
TN  8  3
KY  8  4
IN  8  5
MI  8  6
FL  9  1
GA  9  2
VA  9  3
WV  9  4
OH  9  5
SC 10  1
NC 10  2
MD 10  4
PA 10  5
DE 11  4
NJ 11  5
NY 11  6
VT 11  7
CT 12  5
MA 12  6
NH 12  7
RI 13  5
ME 13  7


CA  AZ  755
CA  NV  129
CA  OR  535
NV  AZ  713
NV  UT  534
NV  ID  541
NV  OR  663
OR  ID  441
OR  WA  160
WA  ID  619
AZ  NM  476
AZ  UT  652
UT  CO  488
UT  WY  435
UT  ID  338
ID  WY  727
ID  MT  438
NM  TX  697
NM  OK  585
NM  CO  355
CO  OK  626
CO  KS  536
CO  NE  486
CO  WY  100
WY  NE  444
WY  SD  455
WY  MT  675


MT  SD  742
MT  ND  624
TX  LA  430
TX  AR  504
TX  OK  388
OK  AR  337
OK  MO  416
OK  KS  293
KS  MO  204
KS  NE  165
NE  MO  343
NE  IA  187
NE  SD  392
SD  IA  490
SD  MN  404
SD  ND  215
ND  MN  435
LA  MS  150
LA  AR  416
AR  MS  253
AR  TN  344
AR  MO  340
MO  TN  453
MO  KY  562
MO  IL  192
MO  IA  255


IA  IL  291
IA  WI  279
IA  MN  244
MN  WI  258
MS  AL  242
MS  TN  392
IL  KY  415
IL  IN  190
IL  WI  249
WI  MI  614
AL  FL  205
AL  GA  160
AL  TN  282
TN  GA  255
TN  NC  530
TN  VA  597
TN  KY  203
KY  VA  532
KY  WV  197
KY  OH  186
KY  IN  145
IN  OH  175
IN  MI  244
MI  OH  237
FL  GA  252
GA  SC  212


GA  NC  434
VA  NC  156
VA  MD  129
VA  WV  302
WV  MD  397
WV  PA  354
WV  OH  160
OH  PA  425
SC  NC  200
MD  DE  62
MD  PA  103
PA  DE  124
PA  NJ  127
PA  NY  268
DE  NJ  108
NJ  NY  193
NY  CT  111
NY  MA  165
NY  VT  153
VT  MA  236
VT  NH  106
CT  RI  72
CT  MA  101
MA  RI  45
MA  NH  68
NH  ME  139

Complete Structure of the Internal Graph Representation (undirected graph, so each edge appears twice)
0(CA): [2(OR),535],[1(NV),129],[4(AZ),755] 1(NV): [2(OR),663],[6(ID),541],[5(UT),534],[4(AZ),713],[0(CA),129] 2(OR): [3(WA),160],[6(ID),441],[1(NV),663],[0(CA),535] 3(WA): [6(ID),619],[2(OR),160] 4(AZ): [5(UT),652],[7(NM),476],[1(NV),713],[0(CA),755] 5(UT): [6(ID),338],[9(WY),435],[8(CO),488],[4(AZ),652],[1(NV),534] 6(ID): [10(MT),438],[9(WY),727],[5(UT),338],[3(WA),619],[2(OR),441],[1(NV),541] 7(NM): [8(CO),355],[12(OK),585],[11(TX),697],[4(AZ),476] 8(CO): [9(WY),100],[14(NE),486],[13(KS),536],[12(OK),626],[7(NM),355],[5(UT),488] 9(WY): [10(MT),675],[15(SD),455],[14(NE),444],[8(CO),100],[6(ID),727],[5(UT),435] 10(MT): [16(ND),624],[15(SD),742],[9(WY),675],[6(ID),438] 11(TX): [12(OK),388],[18(AR),504],[17(LA),430],[7(NM),697] 12(OK): [13(KS),293],[19(MO),416],[18(AR),337],[11(TX),388],[8(CO),626],[7(NM),585] 13(KS): [14(NE),165],[19(MO),204],[12(OK),293],[8(CO),536] 14(NE): [15(SD),392],[20(IA),187],[19(MO),343],[13(KS),165],[9(WY),444],[8(CO),486] 15(SD): [16(ND),215],[21(MN),404],[20(IA),490],[14(NE),392],[10(MT),742],[9(WY),455] 16(ND): [21(MN),435],[15(SD),215],[10(MT),624] 17(LA): [18(AR),416],[22(MS),150],[11(TX),430] 18(AR): [19(MO),340],[26(TN),344],[22(MS),253],[17(LA),416],[12(OK),337],[11(TX),504] 19(MO): [20(IA),255],[23(IL),192],[27(KY),562],[26(TN),453],[18(AR),340],[14(NE),343], [13(KS),204],[12(OK),416] 20(IA): [21(MN),244],[24(WI),279],[23(IL),291],[19(MO),255],[15(SD),490],[14(NE),187] 21(MN): [24(WI),258],[20(IA),244],[16(ND),435],[15(SD),404] 22(MS): [26(TN),392],[25(AL),242],[18(AR),253],[17(LA),150] 23(IL): [24(WI),249],[28(IN),190],[27(KY),415],[20(IA),291],[19(MO),192] 24(WI): [29(MI),614],[23(IL),249],[21(MN),258],[20(IA),279] 25(AL): [26(TN),282],[31(GA),160],[30(FL),205],[22(MS),242] 26(TN): [27(KY),203],[32(VA),597],[36(NC),530],[31(GA),255],[25(AL),282],[22(MS),392], [19(MO),453],[18(AR),344] 27(KY): [28(IN),145],[34(OH),186],[33(WV),197],[32(VA),532],[26(TN),203],[23(IL),415], [19(MO),562] 28(IN): [29(MI),244],[34(OH),175],[27(KY),145],[23(IL),190] 29(MI): [34(OH),237],[28(IN),244],[24(WI),614] 30(FL): [31(GA),252],[25(AL),205] 31(GA): [36(NC),434],[35(SC),212],[30(FL),252],[26(TN),255],[25(AL),160] 32(VA): [33(WV),302],[37(MD),129],[36(NC),156],[27(KY),532],[26(TN),597] 33(WV): [34(OH),160],[38(PA),354],[37(MD),397],[32(VA),302],[27(KY),197] 34(OH): [38(PA),425],[33(WV),160],[29(MI),237],[28(IN),175],[27(KY),186] 35(SC): [36(NC),200],[31(GA),212] 36(NC): [35(SC),200],[32(VA),156],[31(GA),434],[26(TN),530] 37(MD): [38(PA),103],[39(DE),62],[33(WV),397],[32(VA),129] 38(PA): [41(NY),268],[40(NJ),127],[39(DE),124],[37(MD),103],[34(OH),425],[33(WV),354] 39(DE): [40(NJ),108],[38(PA),124],[37(MD),62] 40(NJ): [41(NY),193],[39(DE),108],[38(PA),127] 41(NY): [42(VT),153],[44(MA),165],[43(CT),111],[40(NJ),193],[38(PA),268] 42(VT): [45(NH),106],[44(MA),236],[41(NY),153] 43(CT): [44(MA),101],[46(RI),72],[41(NY),111] 44(MA): [45(NH),68],[46(RI),45],[43(CT),101],[42(VT),236],[41(NY),165] 45(NH): [47(ME),139],[44(MA),68],[42(VT),106] 46(RI): [44(MA),45],[43(CT),72] 47(ME): [45(NH),139]

Complete Structure of the Internal Graph Representation
(undirected graph, so each edge appears twice)

 0(CA): [2(OR),535],[1(NV),129],[4(AZ),755]
 1(NV): [2(OR),663],[6(ID),541],[5(UT),534],[4(AZ),713],[0(CA),129]
 2(OR): [3(WA),160],[6(ID),441],[1(NV),663],[0(CA),535]
 3(WA): [6(ID),619],[2(OR),160]
 4(AZ): [5(UT),652],[7(NM),476],[1(NV),713],[0(CA),755]
 5(UT): [6(ID),338],[9(WY),435],[8(CO),488],[4(AZ),652],[1(NV),534]
 6(ID): [10(MT),438],[9(WY),727],[5(UT),338],[3(WA),619],[2(OR),441],[1(NV),541]
 7(NM): [8(CO),355],[12(OK),585],[11(TX),697],[4(AZ),476]
 8(CO): [9(WY),100],[14(NE),486],[13(KS),536],[12(OK),626],[7(NM),355],[5(UT),488]
 9(WY): [10(MT),675],[15(SD),455],[14(NE),444],[8(CO),100],[6(ID),727],[5(UT),435]
10(MT): [16(ND),624],[15(SD),742],[9(WY),675],[6(ID),438]
11(TX): [12(OK),388],[18(AR),504],[17(LA),430],[7(NM),697]
12(OK): [13(KS),293],[19(MO),416],[18(AR),337],[11(TX),388],[8(CO),626],[7(NM),585]
13(KS): [14(NE),165],[19(MO),204],[12(OK),293],[8(CO),536]
14(NE): [15(SD),392],[20(IA),187],[19(MO),343],[13(KS),165],[9(WY),444],[8(CO),486]
15(SD): [16(ND),215],[21(MN),404],[20(IA),490],[14(NE),392],[10(MT),742],[9(WY),455]
16(ND): [21(MN),435],[15(SD),215],[10(MT),624]
17(LA): [18(AR),416],[22(MS),150],[11(TX),430]
18(AR): [19(MO),340],[26(TN),344],[22(MS),253],[17(LA),416],[12(OK),337],[11(TX),504]
19(MO): [20(IA),255],[23(IL),192],[27(KY),562],[26(TN),453],[18(AR),340],[14(NE),343],
        [13(KS),204],[12(OK),416]
20(IA): [21(MN),244],[24(WI),279],[23(IL),291],[19(MO),255],[15(SD),490],[14(NE),187]
21(MN): [24(WI),258],[20(IA),244],[16(ND),435],[15(SD),404]
22(MS): [26(TN),392],[25(AL),242],[18(AR),253],[17(LA),150]
23(IL): [24(WI),249],[28(IN),190],[27(KY),415],[20(IA),291],[19(MO),192]
24(WI): [29(MI),614],[23(IL),249],[21(MN),258],[20(IA),279]
25(AL): [26(TN),282],[31(GA),160],[30(FL),205],[22(MS),242]
26(TN): [27(KY),203],[32(VA),597],[36(NC),530],[31(GA),255],[25(AL),282],[22(MS),392],
        [19(MO),453],[18(AR),344]
27(KY): [28(IN),145],[34(OH),186],[33(WV),197],[32(VA),532],[26(TN),203],[23(IL),415],
        [19(MO),562]
28(IN): [29(MI),244],[34(OH),175],[27(KY),145],[23(IL),190]
29(MI): [34(OH),237],[28(IN),244],[24(WI),614]
30(FL): [31(GA),252],[25(AL),205]
31(GA): [36(NC),434],[35(SC),212],[30(FL),252],[26(TN),255],[25(AL),160]
32(VA): [33(WV),302],[37(MD),129],[36(NC),156],[27(KY),532],[26(TN),597]
33(WV): [34(OH),160],[38(PA),354],[37(MD),397],[32(VA),302],[27(KY),197]
34(OH): [38(PA),425],[33(WV),160],[29(MI),237],[28(IN),175],[27(KY),186]
35(SC): [36(NC),200],[31(GA),212]
36(NC): [35(SC),200],[32(VA),156],[31(GA),434],[26(TN),530]
37(MD): [38(PA),103],[39(DE),62],[33(WV),397],[32(VA),129]
38(PA): [41(NY),268],[40(NJ),127],[39(DE),124],[37(MD),103],[34(OH),425],[33(WV),354]
39(DE): [40(NJ),108],[38(PA),124],[37(MD),62]
40(NJ): [41(NY),193],[39(DE),108],[38(PA),127]
41(NY): [42(VT),153],[44(MA),165],[43(CT),111],[40(NJ),193],[38(PA),268]
42(VT): [45(NH),106],[44(MA),236],[41(NY),153]
43(CT): [44(MA),101],[46(RI),72],[41(NY),111]
44(MA): [45(NH),68],[46(RI),45],[43(CT),101],[42(VT),236],[41(NY),165]
45(NH): [47(ME),139],[44(MA),68],[42(VT),106]
46(RI): [44(MA),45],[43(CT),72]
47(ME): [45(NH),139]

Revision date: 2011-10-27. (Please use ISO 8601, the International Standard Date and Time Notation.)