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