Part 1: The Graph Class (46 pts)
Graph.java File
* Graph.java * @author * @author * CIS 22C, Lab 6 */ import java.util.ArrayList; public class Graph { private int vertices; private int edges; private ArrayList<List<Integer> > adj; private ArrayList<Character> color; private ArrayList<Integer> distance; private ArrayList<Integer> parent; /**Constructor*/ /** * initializes an empty graph, with n vertices * and 0 edges, and intitializes all arraylists * to contain default values from indices 1 to n * @param n the number of vertices in the graph */ public Graph(int n) { } /*** Accessors ***/ /** * Returns the number of edges in the graph * @return the number of edges */ public int getNumEdges() { return -1; } /** * Returns the number of vertices in the graph * @return the number of vertices */ public int getNumVertices() { return -1; } /** * returns whether the graph is empty (no edges) * @return whether the graph is empty */ public boolean isEmpty() { return false; } /** * Returns the value of the distance[v] * @param v a vertex in the graph * @precondition 0 < v <= vertices * @return the distance of vertex v * @throws IndexOutOfBoundsException when * the precondition is violated */ public Integer getDistance(Integer v) throws IndexOutOfBoundsException{ return -1; } /** * Returns the value of the parent[v] * @param v a vertex in the graph * @precondition 0 < v <= vertices * @return the parent of vertex v * @throws IndexOutOfBoundsException when * the precondition is violated */ public Integer getParent(Integer v) throws IndexOutOfBoundsException { return -1; } /** * Returns the value of the color[v] * @param v a vertex in the graph * @precondition 0 < v <= vertices * @return the color of vertex v * @throws IndexOutOfBoundsException when * the precondition is violated */ public Character getColor(Integer v) throws IndexOutOfBoundsException { return null; } /** * Returns the List stored at index v * @param v a vertex in the graph * @return the adjacency List a v * @precondition 0 < v <= vertices * @throws IndexOutOfBoundsException when * the precondition is violated */ public List<Integer> getAdjacencyList(Integer v) throws IndexOutOfBoundsException { return null; } /*** Manipulation Procedures ***/ /** * Inserts vertex v into the adjacency list of vertex u * (i.e. inserts v into the list at index u) * @precondition 0 < u <= vertices, 0 < v <= vertices * @throws IndexOutOfBounds exception when the precondition * is violated */ public void addDirectedEdge(Integer u, Integer v) throws IndexOutOfBoundsException { } /** * Inserts vertex v into the adjacency list of vertex u * (i.e. inserts v into the list at index u) * and inserts u into the adjacent vertex list of v * @precondition 0 < u <= vertices, 0 < v <= vertices * @throws IndexOutOfBounds exception when the precondition * is violated */ public void addUndirectedEdge(Integer u, Integer v) throws IndexOutOfBoundsException { } /*** Additional Operations ***/ /** * Creates a String representation of the Graph * Prints the adjacency list of each vertex in the graph, * vertex: <space separated list of adjacent vertices> */ @Override public String toString() { String result = ""; return ""; } /** * Prints the current values in the parallel ArrayLists * after executing BFS. First prints the heading: * v <tab> c <tab> p <tab> d * Then, prints out this information for each vertex in the graph * Note that this method is intended purely to help you debug your code */ public void printBFS() { } /** * Performs breath first search on this Graph give a source vertex * @param source the source vertex * @precondition graph must not be empty * @precondition source is a vertex in the graph * @throws IllegalStateException if the graph is empty * @throws IndexOutOfBoundsException when vertex is * outside the bounds of the graph */ public void BFS(Integer source) throws IllegalStateException, IndexOutOfBoundsException { } }
private ArrayList<List<Integer> > adj;
adj.get(1) color.get(1) distance.get(1) parent.get(1) All store information about vertex 1 of the Graph.
The Graph Constructor
BFS(G, s) for all x in V(G) color[x] = white distance[x] = -1 parent[x] = Nil color[s] = grey distance[s] = 0 Enqueue(Q,s) while(Q is not empty) x = front of Q Dequeue(Q,x) for all y in adj[x] if color[y] == white color[y] = grey distance[y] = distance[x] + 1 parent[y] = x Enqueue(Q, y) color[x] = black Displaying Your Graph: toString() and printBFS()
1: 2 5
v c p d 1 B 0 0 2 B 1 1 3 B 2 2 4 B 2 2 5 B 1 1
Example Input File:101 Jiming Wu 2, 7, 10, 2 James Brown 1, 4, 5, 6, 3 Leanna Perez 6, 8, 9, 10, 4 Xing Li 2, 5, 6, 5 Stacey Cahill 2, 4, 6 Mohammed Abbas 2, 3, 4, 7, 7 Kumari Chakrabarti 1, 6, 8 Shakil Smith 3, 9 Jung Ahrin 3, 10, 10 Pedro Martinez 1, 3, 9, Example Output 1:Welcome to the Friend Recommender!Enter the name of a file: friends.txt Enter Your User Number Below: 1. Jiming Wu 2. James Brown 3. Leanna Perez 4. Xing Li 5. Stacey Cahill 6. Mohammed Abbas 7. Kumari Chakrabarti 8. Shakil Smith 9. Jung Ahrin 10. Pedro Martinez Enter your choice: 3 Here are your current friends: 6. Mohammed Abbas 8. Shakil Smith 9. Jung Ahrin 10. Pedro Martinez Here are your recommended friends: 1. Jiming Wu 2. James Brown 4. Xing Li 5. Stacey Cahill 7. Kumari Chakrabarti Enter the number of a friend to add or -1 to quit: Enter your choice: 2 Here are your current friends: 2. James Brown 6. Mohammed Abbas 8. Shakil Smith 9. Jung Ahrin 10. Pedro Martinez Here are your recommended friends: 1. Jiming Wu 4. Xing Li 5. Stacey Cahill 7. Kumari Chakrabarti Enter the number of a friend to add or -1 to quit: Enter your choice: 7 Here are your current friends: 2. James Brown 6. Mohammed Abbas 7. Kumari Chakrabarti 8. Shakil Smith 9. Jung Ahrin 10. Pedro Martinez Here are your recommended friends: 1. Jiming Wu 4. Xing Li 5. Stacey Cahill Enter the number of a friend to add or -1 to quit: Enter your choice: -1 Goodbye! Example Output 2:Welcome to the Friend Recommender! Enter the name of a file: friends Invalid file name! Enter the name of a file: friends.tx Invalid file name! Enter the name of a file: friends.txt Enter Your User Number Below: 1. Jiming Wu 2. James Brown 3. Leanna Perez 4. Xing Li 5. Stacey Cahill 6. Mohammed Abbas 7. Kumari Chakrabarti 8. Shakil Smith 9. Jung Ahrin 10. Pedro Martinez Enter your choice: 9 Here are your current friends: 3. Leanna Perez 10. Pedro Martinez Here are your recommended friends: 1. Jiming Wu 2. James Brown 4. Xing Li 5. Stacey Cahill 6. Mohammed Abbas 7. Kumari Chakrabarti 8. Shakil Smith Enter the number of a friend to add or -1 to quit: Enter your choice: 5 Here are your current friends: 3. Leanna Perez 5. Stacey Cahill 10. Pedro Martinez Here are your recommended friends: 1. Jiming Wu 2. James Brown 4. Xing Li 6. Mohammed Abbas 7. Kumari Chakrabarti 8. Shakil Smith Enter the number of a friend to add or -1 to quit: Enter your choice: 4 Here are your current friends: 3. Leanna Perez 4. Xing Li 5. Stacey Cahill 10. Pedro Martinez Here are your recommended friends: 1. Jiming Wu 2. James Brown 6. Mohammed Abbas 7. Kumari Chakrabarti 8. Shakil Smith Enter the number of a friend to add or -1 to quit: Enter your choice: 8 Here are your current friends: 3. Leanna Perez 4. Xing Li 5. Stacey Cahill 8. Shakil Smith 10. Pedro Martinez Here are your recommended friends: 1. Jiming Wu 2. James Brown 6. Mohammed Abbas 7. Kumari Chakrabarti Enter the number of a friend to add or -1 to quit: Enter your choice: -1 Goodbye! Example Input File:131 Jiming Wu 2, 4, 2 James Brown 1, 4, 3 Leanna Perez 7, 8, 4 Xing Li 1, 2, 5 Stacey Cahill 7, 6 Mohammed Abbas 10, 7 Kumari Chakrabarti 3, 5, 8 Shakil Smith 3, 9, 9 Jung Ahrin 8, 10 Pedro Martinez 6, 12, 11 Abir Fadel 12, 13, 12 Brad Feinman 10, 11, 13, 13 Xiaohang Yue 11, 12, Example Output 1:Welcome to the Friend Recommender!Enter the name of a file: friends2.txt Enter Your User Number Below: 1. Jiming Wu 2. James Brown 3. Leanna Perez 4. Xing Li 5. Stacey Cahill 6. Mohammed Abbas 7. Kumari Chakrabarti 8. Shakil Smith 9. Jung Ahrin 10. Pedro Martinez 11. Abir Fadel 12. Brad Feinman 13. Xiaohang Yue Enter your choice: 6 Here are your current friends: 10. Pedro Martinez Here are your recommended friends: 11. Abir Fadel 12. Brad Feinman 13. Xiaohang Yue Enter the number of a friend to add or -1 to quit: Enter your choice: 11 Here are your current friends: 10. Pedro Martinez 11. Abir Fadel Here are your recommended friends: 12. Brad Feinman 13. Xiaohang Yue Enter the number of a friend to add or -1 to quit: Enter your choice: 12 Here are your current friends: 10. Pedro Martinez 11. Abir Fadel 12. Brad Feinman Here are your recommended friends: 13. Xiaohang Yue Enter the number of a friend to add or -1 to quit: Enter your choice: 13 Here are your current friends: 10. Pedro Martinez 11. Abir Fadel 12. Brad Feinman 13. Xiaohang Yue Here are your recommended friends: Sorry! We don't have any recommendations for you at this time. Goodbye! Sample Output 2: Enter the name of a file: friends2.txt Enter Your User Number Below: 1. Jiming Wu 2. James Brown 3. Leanna Perez 4. Xing Li 5. Stacey Cahill 6. Mohammed Abbas 7. Kumari Chakrabarti 8. Shakil Smith 9. Jung Ahrin 10. Pedro Martinez 11. Abir Fadel 12. Brad Feinman 13. Xiaohang Yue Enter your choice: 2 Here are your current friends: 1. Jiming Wu 4. Xing Li Here are your recommended friends: Sorry! We don't have any recommendations for you at this time. Goodbye! How You Will Be Graded
What to Submit
|