MKSE150

Homework 1

due 2013/2/7

Overview

Do these exercises from the text book: 2.5.1, and 3.7.{3,4,5}, which test knowledge of distance and triadic closure. Two programming problems follow below. And for extra credit, you may try 5.6.4 in the text. The paper problems should be handed in during class on Feb 7; the program should be submitted via turnin.

Programming Background

Now that you have succeeded at HW0, the mechanics of using Eclipse and turnin should be out of the way.

In this assignment you will implement a Breadth-First Search (BFS), and a count of the number of shortest paths from one node to another. Do the BFS first, and verify that your answers are correct. Some example answers are given below for you to check against. The second part will use the datastructures you created in the first, so you want to start the second part only when you are confident about the first.

Your job is to edit the file GraphBFS.java, and this is the only file you will turn in. Edits you might make in other files will not be accepted as part of your final solution.

Setting up the Project

Download this eclipse project hw1.zip and Import it into Eclipse as you did for HW0.

In the Package Explorer, open hw1/src/edu.upenn.cis.mkse150.hw1.
Highlight GraphExercises.java and run it. You should get this:

calling explore with root node 36
layer 0 size 1
[36]
layer 1 size 0
[]

calling countPaths
layer 0 size 1
 36
layer 1 size 0
This means that you have succeeded to compile and run the code. There is no interesting output because you have not done your homework yet!

Doing the Breadth-First Search

Open the file GraphBFS.java in the editor and look it over. You will find a bunch of import statements that list several data types (Map, HashMap, HashSet, LinkedList, Queue, and Set) that you might find useful. Inside the class, you will see these three member fields:
	Graph graph;            // the graph that a search will be conducted over
	
	String startNode;       // stores the root of the search tree
	
	HashMap<String,Integer> depth;      // shortest distance between a node and the startNode
	// Also used to indicate if a node has been examined yet: if it has a null depth it has not been.

The Graph is something that gets initialized when a GraphBFS object gets created. That much is already done for you. The only method you might use that directly uses this object is getNeighbors(), which obtains a list (actually a Set<String>) of adjacent vertices.

A HashMap datastructure acts like a hash table; you insert <key,value> pairs into it using put() and later you can obtain a value by supplying the same key to get().

You will use the depth object to store distance information about nodes. Nodes are represented as distinct Strings, and the distances are integers, so the HashMap<String,Integer> is specifically tailored to storing these data. If you examine the getDepthOf() method you will see how information gets retrieved from it. Note that if you get() some key value that does not exist, what is returned is null; this is an important behavior. (You can employ this feature to determine if you have already dealt with a node.)

Your first job is to edit the method called explore in the file GraphBFS.java. It returns void; its purpose is only to fill the depth structure with distances from the node supplied in its argument. When you have this working correctly, subsequent calls to getDepthOf() will return the individual depth numbers. The main method in GraphExercises.java will produce this as output:

calling explore with root node 36
layer 0 size 1
[36]
layer 1 size 2
[128, 109]
layer 2 size 6
[117, 59, 45, 99, 118, 85]
layer 3 size 25
[135, 114, 139, 57, 33, 108, 41, 65, 86, 101, 61, 100, 98, 143, 126, 145, 147, 149, 124, 46, 90, 70, 88, 76, 141]
layer 4 size 40
[116, 79, 132, 78, 77, 112, 110, 55, 111, 35, 38, 119, 43, 40, 64, 106, 82, 105, 63, 60, 131, 87, 49, 67, 125, 144, 48, 97, 66, 146, 68, 121, 93, 92, 30, 32, 120, 71, 54, 72]
layer 5 size 29
[115, 133, 58, 113, 136, 56, 137, 42, 83, 80, 104, 81, 102, 84, 96, 69, 95, 122, 148, 47, 123, 23, 31, 51, 52, 74, 75, 50, 89]
layer 6 size 23
[134, 127, 138, 94, 44, 19, 91, 17, 15, 34, 16, 129, 39, 13, 12, 20, 107, 53, 62, 103, 73, 130, 142]
layer 7 size 7
[150, 22, 18, 140, 14, 11, 37]
layer 8 size 10
[3, 2, 10, 1, 7, 6, 5, 4, 9, 8]
layer 9 size 1
[21]
layer 10 size 0
[]

Check that your answers match these before proceeding further.

Doing the Shortest Path Count

The second component of the assignment is to employ the information collected in depth to help count the number of shortest paths from the root node to other nodes. So the calling sequence will be: to create the GraphBFS, then to call explore, then to call countPaths. These three things must happen in that order.

Here we have supplied you with another hash table called spCount:

    HashMap<String,Integer> spCount;    // # shortest paths from each node to start node
This is the structure you will fill to indicate how many shortest paths there are from startNode to each of the other nodes. (Recall that startNode was defined back when explore was first called.)

The algorithm for counting shortest paths was covered in class. Work from the root node out, and make use of getNodesAt() to obtain the different levels.

When you have this working, the output from the main method in GraphExercises.java will produce this as output:

calling countPaths
layer 0 size 1
 36
layer 1 size 2
 128 109
layer 2 size 6
 117 59 45 99 118 85
layer 3 size 25
 135 114 139 57 33(2) 108 41 65 86 101 61 100 98 143 126 145 147 149(2) 124 46 90 70 88 76 141
layer 4 size 40
 116 79 132 78 77 112 110 55 111(3) 35(2) 38 119 43 40(2) 64 106(3) 82 105 63 60 131(2) 87 49(2) 67(2) 125 144(2) 48(3) 97 66(2) 146 68(2) 121 93(2) 92(2) 30(4) 32 120 71(3) 54 72(2)
layer 5 size 29
 115 133(6) 58(2) 113(6) 136 56(3) 137 42 83 80(3) 104 81(2) 102(2) 84 96(2) 69(3) 95(3) 122(2) 148(3) 47 123(2) 23(6) 31 51(3) 52 74(3) 75 50(3) 89(2)
layer 6 size 23
 134 127(9) 138(3) 94(2) 44(3) 19(6) 91(7) 17(6) 15(6) 34(4) 16(6) 129(3) 39 13(6) 12(6) 20(6) 107 53(10) 62(5) 103(6) 73(3) 130(8) 142(2)
layer 7 size 7
 150(5) 22(42) 18(42) 140(17) 14(42) 11(36) 37(3)
layer 8 size 10
 3(42) 2(42) 10(42) 1(42) 7(42) 6(42) 5(42) 4(42) 9(42) 8(42)
layer 9 size 1
 21(294)
layer 10 size 0

Finishing up

Use turnin to turn in just the single file called GraphBFS.java.