graph: GraphGenerator

OneCodeMonkey · OneCodeMonkey · commit 2e79f2266580 · 2019-08-21T15:07:58.000+08:00
diff --git a/Algorithm_full_features/graph/GraphGenerator.java b/Algorithm_full_features/graph/GraphGenerator.java
@@ -204,4 +204,163 @@ public static Graph eulerianPath(int V, int E) {
 	}
 
 	// Returns a wheel on `V` vertices
-}
+	public static Graph wheel(int V) {
+		if(V <= 1)
+			throw new IllegalArgumentException("Number of vertices must be at least 2");
+		Graph G = new Graph(V);
+		int[] vertices = new int[V];
+		for(int i = 0; i < V; i++)
+			vertices[i] = i;
+		StdRandom.shuffle(vertices);
+
+		for(int i = 0; i < V - 1; i++)
+			G.addEdge(vertices[i], vertices[i + 1]);
+		
+		G.addEdge(vertices[V - 1], vertices[1]);
+
+		for(int i = 1; i < V; i++)
+			G.addEdge(vertices[0], vertices[i]);
+
+		return G;
+	}
+
+	// Returns a star graph on `V` vertices
+	public static Graph star(int V) {
+		if(V <= 0)
+			throw new IllegalArgumentException("Number of vertices must be at least one");
+		Graph G = new Graph(V);
+		int[] vertices = new int(V);
+		for(int i = 0; i < V; i++)
+			vertices[i] = i;
+		StdRandom.shuffle(vertices);
+
+		for(int i = 1; i < V; i++)
+			G.addEdge(vertices[0], vertices[i]);
+
+		return G;
+	}
+
+	// Returns a uniformly random `k-regular` graph on `V` vertices(not necessarily
+	// simple). The graph is simple with probability only about e^(-k^2/4);, which is
+	// tiny when k = 14.
+	public static Graph regular(int V, int k) {
+		if(V * k % 2 != 0)
+			throw new IllegalArgumentException("Number of vertices * k must be even");
+		Graph G = new Graph(V);
+		int[] vertices = new int[V * k];
+		for(int v = 0; v < V; v++)
+			for(int j = 0; j < k; j++)
+				vertices[v + V * j] = v;
+
+		// pick a random perfect matching
+		StdRandom.shuffle(vertices);
+		for(int i = 0; i < V * k / 2; i++)
+			G.addEdge(vertices[2 * i], vertices[2 * i + 1]);
+
+		return G;
+	}
+
+	// Returns a uniformly random tree on `V` vertices.
+	public static Graph tree(int V) {
+		Graph G = new Graph(V);
+		// special case
+		if(V == 1)
+			return G;
+		// Cayley's theorem: there are V^(V - 2) labeled trees on V vertices
+		// Prufer sequence: sequence of V - 2 values between 0 and V - 1
+		// Prufer's proof of Cayley's theorem: Prufer sequences are in 1-1
+		// with labeled trees on V vertices.
+		int [] prufer = new int[V - 2];
+		for(int i = 0; i < V - 2; i++)
+			prufer[i] = StdRandom.uniform(V);
+
+		// degree of vertex v = 1 + number of times it appears in Prufer sequence
+		int[] degree = new int[V];
+		for(int v = 0; v < V; v++)
+			degree[v] = 1;
+		for(int i = 0; i < V - 2; i++)
+			degree[prufer[i]]++;
+
+		// pq contains all vertices of degree 1
+		MinPQ<Integer> pq = new MinPQ<Integer>();
+		for(int v = 0; v < V; v++) {
+			if(degree[v] == 1)
+				pq.insert(v);
+		}
+
+		// repeatedly delMin() degree 1 vertex that has the minimum index
+		for(int i = 0; i< V - 2; i++) {
+			int v = pq.delMin();
+			G.addEdge(v, prufer[i]);
+			degree[v]--;
+			degree[prufer[i]]--;
+			if(degree[prufer[i]] == 1)
+				pq.insert(prufer[i]);
+		}
+		G.addEdge(pq.delMin(), pq.delMin());
+
+		return G;
+	}
+
+	// test
+	public static void main(String[] args) {
+		int V = Integer.parseInt(args[0]);
+		int E = Integer.parseInt(args[1]);
+		int V1 = V / 2;
+		int V2 = V - V1;
+
+		StdOut.println("complete graph");
+		StdOut.println(complete(V));
+		StdOut.println();
+
+		StdOut.println("simple");
+		StdOut.println(simple(V, E));
+		StdOut.println();
+
+		StdOut.println("Erdos-Renyi");
+		double p = (double)E / (V * (V - 1) / 2.0);
+		StdOut.println(simple(V, p));
+		StdOut.println();
+
+		StdOut.println("complete bipartite");
+		StdOut.println(completeBipartite(V1, V2));
+		StdOut.println();
+
+		StdOut.println("bipartite");
+		StdOut.println(bipartite(V1, V2, E));
+		StdOut.println();
+
+		StdOut.println("Erods Renyi bipartite");
+		double q = (double)E / (V1 * V2);
+		StdOut.println(bipartite(V1, V2, q));
+		StdOut.println();
+
+		StdOut.println("path");
+		StdOut.println(path(V));
+		StdOut.println();
+
+		StdOut.println("cycle");
+		StdOut.println(cycle(V));
+		StdOut.println();
+
+		StdOut.println("binary tree");
+		StdOut.println(binaryTree(V));
+		StdOut.println();
+
+		StdOut.println("tree");
+		StdOut.println(tree(V));
+		StdOut.println();
+
+		StdOut.println("4-regular");
+		StdOut.println(regular(V, 4));
+		StdOut.println();
+
+		StdOut.println("star");
+		StdOut.println(star(V));
+		StdOut.println();
+
+		StdOut.println("wheel");
+		StdOut.println(wheel(V));
+		StdOut.println();
+	}
+}
