Skip to content

Commit 6a3a5fd

Browse files
OneCodeMonkeyOneCodeMonkey
committed
graph: GraphGenerator
1 parent c7bedf3 commit 6a3a5fd

1 file changed

Lines changed: 207 additions & 0 deletions

File tree

‎Algorithm_full_features/graph/GraphGenerator.java‎

Lines changed: 207 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,207 @@
1+
/**
2+
* A graph generator.
3+
*
4+
* The `GraphGenerator` class provides static methods for creating various graphs,
5+
* including Erdos-Renyi random graphs, random bipartite graphs, from k-regular graphs,
6+
* and random rooted trees.
7+
*
8+
*/
9+
public class GraphGenerator {
10+
private static final class Edge implements Comparable<Edge> {
11+
private int v,;
12+
private int w;
13+
private Edge(int v, int w) {
14+
if(v < w) {
15+
this.v = v;
16+
this.w = w;
17+
} else {
18+
this.v = w;
19+
this.w = v;
20+
}
21+
}
22+
23+
public int compareTo(Edge that) {
24+
if(this.v < that.v)
25+
return -1;
26+
if(this.v > that.v)
27+
return 1;
28+
if(this.w < that.w)
29+
return -1;
30+
if(this.w > that.w)
31+
return 1;
32+
return 0;
33+
}
34+
}
35+
36+
// this class can't be instantiated
37+
private GraphGenerator() {}
38+
39+
// returns a random simple graph containing `V` vertices and `E` edges.
40+
public static Graph simple(int V, int E) {
41+
if(E > (long)V*(V - 1) / 2)
42+
throw new IllegalArgumentException("Too many edges");
43+
if(E < 0)
44+
throw new IllegalArgumentException("edges can't be negative");
45+
Graph G = new Graph(V);
46+
SET<Edge> set = new SET<Edge>();
47+
while(G.E() < E) {
48+
int v = StdRandom.uniform(V);
49+
int w = StdRandom.uniform(V);
50+
Edge e = new Edge(v, w);
51+
if((v != w) && !set.contains(e)) {
52+
set.add(e);
53+
G.addEdge(v, w);
54+
}
55+
}
56+
return G;
57+
}
58+
59+
// Returns a random simple graph on `V` vertices, with an edge between any two
60+
// vertices with probability `p`. This is sometimes referred to as the Erdos-Renyi
61+
// random graph model.
62+
public static Graph simple(int V, double p) {
63+
if(p < 0.0 || p > 1.0)
64+
throw new IllegalArgumentException("probability must be [0, 1]");
65+
Graph G = new Graph(V);
66+
for(int v = 0; v < V; v++) {
67+
for(int w = v + 1; w < V; w++)
68+
if(StdRandom.bernoulli(p))
69+
G.addEdge(v, w);
70+
}
71+
72+
return G;
73+
}
74+
75+
// Returns the complete graph on `V` vertices.
76+
public static Graph complete(int V) {
77+
return simple(V, 1.0);
78+
}
79+
80+
// Returns a complete bipartite graph on `V1` and `V2` vertices.
81+
public static Graph completeBipartite(int V1, int V2) {
82+
return bipartite(V1, V2, V1*V2);
83+
}
84+
85+
// Returns a random simple bipartite graph on `V1` and `V2` vertices with `E` edges.
86+
public static Graph bipartite(int V1, int V2, int E) {
87+
if(E > (long)V1 * V2)
88+
throw new IllegalArgumentException("Too many edges");
89+
if(E < 0)
90+
throw new IllegalArgumentException("Edges can't be negative");
91+
Graph G = new Graph(V1 + V2);
92+
int[] vertices = new int[V1 + V2];
93+
for(int i = 0; i < V1 + V2; i++)
94+
vertices[i] = i;
95+
96+
StdRandom.shuffle(vertices);
97+
98+
SET<Edge> set = new SET<Edge>();
99+
100+
while(G.E() < E) {
101+
int i = StdRandom.uniform(V1);
102+
int j = V1 + StdRandom.uniform(V2);
103+
Edge e = new Edge(vertices[i], vertices[j]);
104+
if(!set.contains(e)) {
105+
set.add(e);
106+
G.addEdge(vertices[i], vertices[j]);
107+
}
108+
}
109+
110+
return G;
111+
}
112+
113+
// Returns a random simple bipartite graph on `V1` and `V2` vertices.
114+
// containing each possible edge with probability `p`
115+
public static Graph bipartite(int V1, int V2, double p) {
116+
if(p < 0.0 || p > 1.0)
117+
throw new IllegalArgumentException("probability must between 0 and 1");
118+
int[] vertices = new int[V1 + V2];
119+
for(int i = 0; i < V1 + V2; i++)
120+
vertices[i] = i;
121+
StdRandom.shuffle(vertices);
122+
Graph G = new Graph(V1 + V2);
123+
for(int i = 0; i < V1; i++)
124+
for(int j = 0; j < V2; j++)
125+
if(StdRandom.bernoulli(p))
126+
G.addEdge(vertices[i], vertices[V1 + j]);
127+
128+
return G;
129+
}
130+
131+
// Returns a path graph on `V` vertices.
132+
public static Graph path(int V) {
133+
Graph G = new Graph(V);
134+
int[] vertices = new int[V];
135+
for(int i = 0; i < V; i++)
136+
vertices[i] = i;
137+
StdRandom.shuffle(vertices);
138+
for(int i = 0; i < V - 1; i++)
139+
G.addEdge(vertices[i], vertices[i + 1]);
140+
141+
return G;
142+
}
143+
144+
// Returns a complete binary tree graph on `V` vertices
145+
public static Graph binaryTree(int V) {
146+
Graph G = new Graph(V);
147+
int[] vertices = new int[V];
148+
for(int i = 0; i < V; i++)
149+
vertices[i] = i;
150+
StdRandom.shuffle(vertices);
151+
for(int i = 1; i < V; i++)
152+
G.addEdge(vertices[i], vertices[(i - 1) / 2]);
153+
154+
return G;
155+
}
156+
157+
// Returns a cycle graph on `V` vertices.
158+
public static Graph cycle(int V) {
159+
Graph G = new Graph(V);
160+
int[] vertices = new int[V];
161+
for(int i = 0; i < V; i++) {
162+
vertices[i] = i;
163+
}
164+
165+
StdRandom.shuffle(vertices);
166+
for(int i = 0; i < V - 1; i++)
167+
G.addEdge(vertices[i], vertices[i + 1]);
168+
G.addEdge(vertices[V - 1], vertices[0]);
169+
170+
return G;
171+
}
172+
173+
// Returns an Eulerian cycle graph on `V` vertices
174+
public static Graph eulerianCycle(int V, int E) {
175+
if(E <= 0)
176+
throw new IllegalArgumentException("An Eulerian cycle must have at least one edge");
177+
if(V <= 0)
178+
throw new IllegalArgumentException("An Eulerian cycle must have at least one vertex");
179+
Graph G = new Graph(V);
180+
int[] vertices = new int[E];
181+
for(int i = 0; i < E; i++)
182+
vertices[i] = StdRandom.uniform(V);
183+
for(int i = 0; i < E - 1; i++)
184+
G.addEdge(vertices[i], vertices[i + 1]);
185+
G.addEdge(vertices[E - 1], vertices[0]);
186+
187+
return G;
188+
}
189+
190+
// Returns an Eulerian path graph on `V` vertices.
191+
public static Graph eulerianPath(int V, int E) {
192+
if(E < 0)
193+
throw new IllegalArgumentException("negative number of edges");
194+
if(V <= 0)
195+
throw new IllegalArgumentException("An Eulerian path must have at least one vertex");
196+
Graph G = new Graph(V);
197+
int[] vertices = new int[E + 1];
198+
for(int i = 0; i < E + 1; i++)
199+
vertices[i] = StdRandom.uniform(V);
200+
for(int i = 0; i < E; i++)
201+
G.addEdge(vertices[i], vertices[i + 1]);
202+
203+
return G;
204+
}
205+
206+
// Returns a wheel on `V` vertices
207+
}

0 commit comments

Comments
 (0)