1  import java.util.*;
  2  
  3  public class UnweightedGraph<V> implements Graph<V> {
  4    protected List<V> vertices = new ArrayList<>(); // Store vertices
  5    protected List<List<Edge>> neighbors 
  6      = new ArrayList<>(); // Adjacency lists
  7  
  8    /** Construct an empty graph */
  9    public UnweightedGraph() {
 10    }
 11    
 12    /** Construct a graph from vertices and edges stored in arrays */
 13    public UnweightedGraph(V[] vertices, int[][] edges) {
 14      for (int i = 0; i < vertices.length; i++)
 15        addVertex(vertices[i]);
 16      
 17      createAdjacencyLists(edges, vertices.length);
 18    }
 19  
 20    /** Construct a graph from vertices and edges stored in List */
 21    public UnweightedGraph(List<V> vertices, List<Edge> edges) {
 22      for (int i = 0; i < vertices.size(); i++)
 23        addVertex(vertices.get(i));
 24          
 25      createAdjacencyLists(edges, vertices.size());
 26    }
 27  
 28    /** Construct a graph for integer vertices 0, 1, 2 and edge list */
 29    public UnweightedGraph(List<Edge> edges, int numberOfVertices) {
 30      for (int i = 0; i < numberOfVertices; i++) 
 31        addVertex((V)(Integer.valueOf(i))); // vertices is {0, 1, ...}
 32      
 33      createAdjacencyLists(edges, numberOfVertices);
 34    }
 35  
 36    /** Construct a graph from integer vertices 0, 1, and edge array */
 37    public UnweightedGraph(int[][] edges, int numberOfVertices) {
 38      for (int i = 0; i < numberOfVertices; i++) 
 39        addVertex((V)(Integer.valueOf(i))); // vertices is {0, 1, ...}
 40      
 41      createAdjacencyLists(edges, numberOfVertices);
 42    }
 43  
 44    /** Create adjacency lists for each vertex */
 45    private void createAdjacencyLists(
 46        int[][] edges, int numberOfVertices) {
 47      for (int i = 0; i < edges.length; i++) {
 48        addEdge(edges[i][0], edges[i][1]);
 49      }
 50    }
 51  
 52    /** Create adjacency lists for each vertex */
 53    private void createAdjacencyLists(
 54        List<Edge> edges, int numberOfVertices) {
 55      for (Edge edge: edges) {
 56        addEdge(edge.u, edge.v);
 57      }
 58    }
 59  
 60    @Override /** Return the number of vertices in the graph */
 61    public int getSize() {
 62      return vertices.size();
 63    }
 64  
 65    @Override /** Return the vertices in the graph */
 66    public List<V> getVertices() {
 67      return vertices;
 68    }
 69  
 70    @Override /** Return the object for the specified vertex */
 71    public V getVertex(int index) {
 72      return vertices.get(index);
 73    }
 74  
 75    @Override /** Return the index for the specified vertex object */
 76    public int getIndex(V v) {
 77      return vertices.indexOf(v);
 78    }
 79  
 80    @Override /** Return the neighbors of the specified vertex */
 81    public List<Integer> getNeighbors(int index) {
 82      List<Integer> result = new ArrayList<>();
 83      for (Edge e: neighbors.get(index))
 84        result.add(e.v);
 85      
 86      return result;
 87    }
 88  
 89    @Override /** Return the degree for a specified vertex */
 90    public int getDegree(int v) {
 91      return neighbors.get(v).size();
 92    }
 93  
 94    @Override /** Print the edges */
 95    public void printEdges() {
 96      for (int u = 0; u < neighbors.size(); u++) {
 97        System.out.print(getVertex(u) + " (" + u + "): ");
 98        for (Edge e: neighbors.get(u)) {
 99          System.out.print("(" + getVertex(e.u) + ", " +
100            getVertex(e.v) + ") ");
101        }
102        System.out.println();
103      }
104    }
105  
106    @Override /** Clear the graph */
107    public void clear() {
108      vertices.clear();
109      neighbors.clear();
110    }
111    
112    @Override /** Add a vertex to the graph */  
113    public boolean addVertex(V vertex) {
114      if (!vertices.contains(vertex)) {
115        vertices.add(vertex);
116        neighbors.add(new ArrayList<Edge>());
117        return true;
118      }
119      else {
120        return false;
121      }
122    }
123  
124    @Override /** Add an edge to the graph */  
125    public boolean addEdge(Edge e) {
126      if (e.u < 0 || e.u > getSize() - 1)
127        throw new IllegalArgumentException("No such index: " + e.u);
128  
129      if (e.v < 0 || e.v > getSize() - 1)
130        throw new IllegalArgumentException("No such index: " + e.v);
131      
132      if (!neighbors.get(e.u).contains(e)) {
133        neighbors.get(e.u).add(e);
134        return true;
135      }
136      else {
137        return false;
138      }
139    }
140    
141    @Override /** Add an edge to the graph */  
142    public boolean addEdge(int u, int v) {
143      return addEdge(new Edge(u, v));
144    }
145    
146    @Override /** Obtain a DFS tree starting from vertex u */
147    /** To be discussed in Section 28.7 */
148    public SearchTree dfs(int v) {
149      List<Integer> searchOrder = new ArrayList<>();
150      int[] parent = new int[vertices.size()];
151      for (int i = 0; i < parent.length; i++)
152        parent[i] = -1; // Initialize parent[i] to -1
153  
154      // Mark visited vertices
155      boolean[] isVisited = new boolean[vertices.size()];
156  
157      // Recursively search
158      dfs(v, parent, searchOrder, isVisited);
159  
160      // Return a search tree
161      return new SearchTree(v, parent, searchOrder);
162    }
163  
164    /** Recursive method for DFS search */
165    private void dfs(int v, int[] parent, List<Integer> searchOrder,
166        boolean[] isVisited) {
167      // Store the visited vertex
168      searchOrder.add(v);
169      isVisited[v] = true; // Vertex v visited
170  
171      for (Edge e : neighbors.get(v)) { // Note that e.u is v 
172        int w = e.v; // e.v is w in Listing 28.8
173        if (!isVisited[w]) { 
174          parent[w] = v; // The parent of w is v
175          dfs(w, parent, searchOrder, isVisited); // Recursive search
176        }
177      }
178    }
179  
180    @Override /** Starting bfs search from vertex v */
181    /** To be discussed in Section 28.9 */
182    public SearchTree bfs(int v) {
183      List<Integer> searchOrder = new ArrayList<>();
184      int[] parent = new int[vertices.size()];
185      for (int i = 0; i < parent.length; i++)
186        parent[i] = -1; // Initialize parent[i] to -1
187  
188      java.util.LinkedList<Integer> queue =
189        new java.util.LinkedList<>(); // list used as a queue
190      boolean[] isVisited = new boolean[vertices.size()];
191      queue.offer(v); // Enqueue v
192      isVisited[v] = true; // Mark it visited
193  
194      while (!queue.isEmpty()) {
195        int u = queue.poll(); // Dequeue to u
196        searchOrder.add(u); // u searched
197        for (Edge e: neighbors.get(u)) { // Note that e.u is u
198          int w = e.v; // e.v is w in Listing 28.11
199          if (!isVisited[w]) { 
200            queue.offer(w); // Enqueue w
201            parent[w] = u; // The parent of w is u
202            isVisited[w] = true; // Mark w visited
203          }
204        }
205      }
206  
207      return new SearchTree(v, parent, searchOrder);
208    }
209  
210    /** Tree inner class inside the UnweightedGraph class */
211    /** To be discussed in Section 28.6 */
212    public class SearchTree {
213      private int root; // The root of the tree
214      private int[] parent; // Store the parent of each vertex
215      private List<Integer> searchOrder; // Store the search order
216  
217      /** Construct a tree with root, parent, and searchOrder */
218      public SearchTree(int root, int[] parent, 
219          List<Integer> searchOrder) {
220        this.root = root;
221        this.parent = parent;
222        this.searchOrder = searchOrder;
223      }
224  
225      /** Return the root of the tree */
226      public int getRoot() {
227        return root;
228      }
229  
230      /** Return the parent of vertex v */
231      public int getParent(int v) {
232        return parent[v];
233      }
234  
235      /** Return an array representing search order */
236      public List<Integer> getSearchOrder() {
237        return searchOrder;
238      }
239  
240      /** Return number of vertices found */
241      public int getNumberOfVerticesFound() {
242        return searchOrder.size();
243      }
244      
245      /** Return the path of vertices from a vertex to the root */
246      public List<V> getPath(int index) {
247        ArrayList<V> path = new ArrayList<>();
248  
249        do {
250          path.add(vertices.get(index));
251          index = parent[index];
252        }
253        while (index != -1);
254  
255        return path;
256      }
257  
258      /** Print a path from the root to vertex v */
259      public void printPath(int index) {
260        List<V> path = getPath(index);
261        System.out.print("A path from " + vertices.get(root) + " to " +
262          vertices.get(index) + ": ");
263        for (int i = path.size() - 1; i >= 0; i--)
264          System.out.print(path.get(i) + " ");
265      }
266  
267      /** Print the whole tree */
268      public void printTree() {
269        System.out.println("Root is: " + vertices.get(root));
270        System.out.print("Edges: ");
271        for (int i = 0; i < parent.length; i++) {
272          if (parent[i] != -1) {
273            // Display an edge
274            System.out.print("(" + vertices.get(parent[i]) + ", " +
275              vertices.get(i) + ") ");
276          }
277        }
278        System.out.println();
279      }
280    }
281    
282    @Override /** Remove vertex v and return true if successful */  
283    public boolean remove(V v) {
284      return true; // Implementation left as an exercise
285    }
286  
287    @Override /** Remove edge (u, v) and return true if successful */  
288    public boolean remove(int u, int v) {
289      return true; // Implementation left as an exercise
290    }
291  }