CS 3343/3341
 Analysis of Algorithms 
Spring 2012
  Breadth-First Search  
Capitals in USA


BFS Tree From Node 19 (MO) (larger picture: here)


BFS Tree From Node 3 (WA) (larger picture: here)


BFS Tree From Node 47 (ME) (larger picture: here)

Node names and locations in a grid. Pairs of edges and weights. Plus main class.
// Graph.java: set up data structure for graph
import java.io.*;
import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class Graph {
   private int count; // number of nodes
   private Reader in; // internal input file name
   private GraphNode[] graph;
   private List list;
   private Queue queue;

   public Graph(String fileName, int ct,
         List cList) {
      count = ct;
      queue = new Queue(100);
      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 breadthSearch(int s) { // 0<=s<=47
      int u, v; // vertices used in loop
      graph[s].color = 1; // gray
      graph[s].d = 0;
      graph[s].pi = -1;
      queue.enqueue(s);
      while (!queue.isEmpty()) {
         u = queue.dequeue();
         EdgeNode vnode = graph[u].firstEdgeNode;
         v = vnode.vertexNum;
         while(true) {
            if (graph[v].color == 0) {  // white
               graph[v].color = 1; // gray
               graph[v].d = graph[u].d + 1;
               graph[v].pi = u;
               queue.enqueue(v);
            }
            vnode = vnode.nextEdgeNode;
            if (vnode == null) break;
            else v = vnode.vertexNum;
         }
         graph[u].color = 2; // black
      }
   }

   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");
         }
      }
   }
   private int transX(int x) {
      return 80*x;
   }
   private int transY(int y) {
      return 80*(8-y);
   }

   private void drawBlob(Graphics g, int x1, int y1,
         int x2, int y2, int nRad) {
      int blobSize = 8; // was 6
      double r = 0.75;
      double c = Math.sqrt((x1-x2)*(x1-x2) +
         (y1-y2)*(y1-y2));
      r = (c - (nRad + 4))/c;
      g.fillOval((int)(x1 + r*(x2 - x1)) - blobSize/2,
        (int)(y1 + r*(y2 - y1)) - blobSize/2,
         blobSize, blobSize);
   }

   private void drawMyLine(Graphics g, int x1,
         int y1, int x2, int y2, int nRad) {
      g.drawLine(x1, y1, x2, y2);
   }

   private void drawMyThickLine(Graphics g, int x1,
         int y1, int x2, int y2, int nRad) {
      g.drawLine(x1, y1, x2, y2);
      // thicklines
      drawThickLine(g, x1, y1, x2, y2);
      // now add blob
      drawBlob(g, x1, y1, x2, y2, nRad);
   }

   private void drawThickLine(Graphics g, int x1,
         int y1, int x2, int y2) {
      // thicklines
      double slope;
      if (Math.abs(x2 - x1) < 4)
         slope = (y2 - y1)/3.0;
      else slope = (double)(y2 - y1)/(x2 - x1);
      if (slope > 0.2 && slope < 5.0) {
         g.drawLine(x1-1, y1+1, x2-1, y2+1);
         g.drawLine(x1,   y1+1, x2,   y2+1);
         g.drawLine(x1-1, y1,   x2-1, y2  );
         g.drawLine(x1+1, y1-1, x2+1, y2-1);
         g.drawLine(x1+1, y1,   x2+1, y2  );
         g.drawLine(x1,   y1-1, x2,   y2-1);
      } else {
         g.drawLine(x1-1, y1-1, x2-1, y2-1);
         g.drawLine(x1,   y1-1, x2,   y2-1);
         g.drawLine(x1-1, y1,   x2-1, y2  );
         g.drawLine(x1+1, y1+1, x2+1, y2+1);
         g.drawLine(x1,   y1+1, x2,   y2+1);
         g.drawLine(x1+1, y1,   x2+1, y2  );
      }
   }

   public void drawEdges(Graphics g, int nRad) {
      for (int i = 0; i < count; i++) {
         EdgeNode node = graph[i].firstEdgeNode;
         int ix = list.getXCoord(i);
         int iy = list.getYCoord(i);
         String s = list.getNodeName(i);
         
         g.setColor(Color.BLACK);

         while (node != null) {
            int num = node.vertexNum;
            int jx = list.getXCoord(num);
            int jy = list.getYCoord(num);
            drawMyLine(g, transX(ix), transY(iy),
               transX(jx), transY(jy), nRad);
            int dt = node.edgeDist;
            node = node.nextEdgeNode;
          }
       }
   }

   public void drawBFTedges(Graphics g, int nRad) {
      for (int i = 0; i < count; i++) {
         int ix = list.getXCoord(i);
         int iy = list.getYCoord(i);
         int j = graph[i].pi; // from j to i
         if (j >= 0) {
            int jx = list.getXCoord(j);
            int jy = list.getYCoord(j);
            drawMyThickLine(g, transX(jx), transY(jy),
               transX(ix), transY(iy), nRad);
         }
      }
   }

   public void drawNames(Graphics g) {
      for (int i = 0; i < count; i++) {
         int ix = list.getXCoord(i);
         int iy = list.getYCoord(i);
         String s = list.getNodeName(i);
         g.setColor(Color.BLACK);
         if (s.length() < 2)
            g.drawString(s, transX(ix) - 4,
               transY(iy)+ 4);
         else
            g.drawString(s, transX(ix) - 8,
               transY(iy)+ 4);
      }
   }
   public void drawDCount(Graphics g) {
      for (int i = 0; i < count; i++) {
         int dCount = graph[i].d;
         int ix = list.getXCoord(i);
         int iy = list.getYCoord(i);
         g.setColor(Color.BLACK);
         if (dCount < 10)
            g.drawString(dCount + " ", transX(ix) - 4,
                 transY(iy)+ 4);
         else
            g.drawString(dCount + " ", transX(ix) - 8,
               transY(iy)+ 4);
      }
   }
}

// GraphApplet.java: applet to draw graph
import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class GraphApplet extends JApplet {
   List list = new List("capslocnum.txt");
   //   capsList.printCapsList();
   int count = list.getCount();
   Graph graph =  new Graph("capsdistnum.txt",
        count, list);

   public void init() {
      setBackground(Color.YELLOW);
   }

   public void paint(Graphics g) {
       int s = 19; // vertex for Washington
       graph.breadthSearch(s);
       int x, y;
       int nRad = 12; // radius of node
       // edges will overwrite nodes
       graph.drawEdges(g, nRad);         
       g.setColor(Color.RED);
       graph.drawBFTedges(g, nRad);
       g.setColor(Color.BLACK);
       for (int i = 0; i < count; i++) {
          x = list.getXCoord(i);
          y = list.getYCoord(i);
          g.setColor(Color.WHITE);
          g.fillOval(transX(x) - 12,
             transY(y) - 12, 24, 24);
          g.setColor(Color.BLACK);
          g.drawOval(transX(x) - 12,
             transY(y) - 12, 24, 24);
       }
       // graph.drawNames(g);
       graph.drawDCount(g);
   }
   private int transX(int x) {
      return 80*x;
   }
   private int transY(int y) {
      return 80*(8-y);
   }
}

// 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, for B-F search
   public int color; // 0,1,2=white,gray,black
   public int d;
   public int pi;

   public GraphNode() {
      firstEdgeNode = null;
      // initialize other vertex info here
      color = 0; // white
      d = 100000000;
      pi = -1;
   }
}

// 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 from data 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()) == ' ')
            ;
         // 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");
   }

   public static void main(String[] args) {
       // "capsloc.txt" = file of node names,
       //   along with grid coordinates.
       List list = new List("capsloc.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

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