001package algs41; 002import stdlib.*; 003import java.util.Iterator; 004import java.util.NoSuchElementException; 005/* *********************************************************************** 006 * Compilation: javac AdjMatrixGraph.java 007 * Execution: java AdjMatrixGraph V E 008 * Dependencies: StdOut.java 009 * 010 * A graph, implemented using an adjacency matrix. 011 * Parallel edges are disallowed; self-loops are allowd. 012 * 013 *************************************************************************/ 014 015public class XAdjMatrixGraph { 016 private final int V; 017 private int E; 018 private final boolean[][] adj; 019 020 // empty graph with V vertices 021 public XAdjMatrixGraph(int V) { 022 if (V < 0) throw new Error("Number of vertices must be nonnegative"); 023 this.V = V; 024 this.E = 0; 025 this.adj = new boolean[V][V]; 026 } 027 028 // random graph with V vertices and E edges 029 public XAdjMatrixGraph(int V, int E) { 030 this(V); 031 if (E < 0) throw new Error("Number of edges must be nonnegative"); 032 if (E > V*(V-1) + V) throw new Error("Too many edges"); 033 034 // can be inefficient 035 while (this.E != E) { 036 int v = (int) (V * Math.random()); 037 int w = (int) (V * Math.random()); 038 addEdge(v, w); 039 } 040 } 041 042 // number of vertices and edges 043 public int V() { return V; } 044 public int E() { return E; } 045 046 047 // add undirected edge v-w 048 public void addEdge(int v, int w) { 049 if (!adj[v][w]) E++; 050 adj[v][w] = true; 051 adj[w][v] = true; 052 } 053 054 // does the graph contain the edge v-w? 055 public boolean contains(int v, int w) { 056 return adj[v][w]; 057 } 058 059 // return list of neighbors of v 060 public Iterable<Integer> adj(int v) { 061 return new AdjIterator(v); 062 } 063 064 // support iteration over graph vertices 065 private class AdjIterator implements Iterator<Integer>, Iterable<Integer> { 066 int v, w = 0; 067 AdjIterator(int v) { this.v = v; } 068 069 public Iterator<Integer> iterator() { return this; } 070 071 public boolean hasNext() { 072 while (w < V) { 073 if (adj[v][w]) return true; 074 w++; 075 } 076 return false; 077 } 078 079 public Integer next() { 080 if (hasNext()) { return w++; } 081 else { throw new NoSuchElementException(); } 082 } 083 084 public void remove() { throw new UnsupportedOperationException(); } 085 } 086 087 088 // string representation of Graph - takes quadratic time 089 public String toString() { 090 String NEWLINE = System.getProperty("line.separator"); 091 StringBuilder s = new StringBuilder(); 092 s.append(V + " " + E + NEWLINE); 093 for (int v = 0; v < V; v++) { 094 s.append(v + ": "); 095 for (int w : adj(v)) { 096 s.append(w + " "); 097 } 098 s.append(NEWLINE); 099 } 100 return s.toString(); 101 } 102 103 104 // test client 105 public static void main(String[] args) { 106 int V = Integer.parseInt(args[0]); 107 int E = Integer.parseInt(args[1]); 108 XAdjMatrixGraph G = new XAdjMatrixGraph(V, E); 109 StdOut.println(G); 110 } 111 112}