0
# Utility Classes
1

2
Helper classes providing graph generation and testing utilities for development, testing, and demonstration purposes. These utilities create various graph structures for algorithm testing, performance evaluation, and educational examples.
3

4
## Capabilities
5

6
### TestGraphs
7

8
Comprehensive graph generator providing various test graph structures for development and testing purposes.
9

10
```java { .api }
11
/**
12
 * Provides generators for several different test graphs suitable for 
13
 * testing graph algorithms and demonstrating graph structures.
14
 */
15
public class TestGraphs {
16
    
17
    /**
18
     * A series of pairs useful for generating graphs (8 edges, 10 nodes, two connected components)
19
     */
20
    public static String[][] pairs;
21
    
22
    /**
23
     * Creates a small sample graph for testing purposes
24
     * @param directed If true, creates directed graph; if false, creates undirected graph
25
     * @return Small test graph with predefined structure
26
     */
27
    public static Graph<String, Number> createTestGraph(boolean directed);
28
    
29
    /**
30
     * Creates a graph with a chain of vertices and isolated vertices
31
     * @param chain_length Number of vertices in the chain
32
     * @param isolate_count Number of isolated vertices to add
33
     * @return Graph with linear chain plus isolated vertices
34
     */
35
    public static Graph<String,Number> createChainPlusIsolates(int chain_length, int isolate_count);
36
    
37
    /**
38
     * Creates a sample directed acyclic graph with multiple layers
39
     * @param layers Number of layers in the DAG
40
     * @param maxNodesPerLayer Maximum number of nodes in each layer
41
     * @param linkprob Probability of creating edges between adjacent layers
42
     * @return Layered directed acyclic graph
43
     */
44
    public static Graph<String,Number> createDirectedAcyclicGraph(int layers, int maxNodesPerLayer, double linkprob);
45
    
46
    /**
47
     * Returns a bigger, undirected test graph with just one component
48
     * @return Single-component undirected graph for testing
49
     */
50
    public static Graph<String,Number> getOneComponentGraph();
51
    
52
    /**
53
     * Returns a bigger test graph with a clique, several components, and other parts
54
     * @return Complex test graph with multiple structural features
55
     */
56
    public static Graph<String, Number> getDemoGraph();
57
    
58
    /**
59
     * Returns a small graph with directed and undirected edges, and parallel edges
60
     * @return Mixed-type test graph demonstrating various edge types
61
     */
62
    public static Graph<String, Number> getSmallGraph();
63
    
64
    // Private helper method
65
    private static void createEdge(Graph<String, Number> g, String v1Label, String v2Label, int weight);
66
}
67
```
68

69
**Usage Examples:**
70

71
```java
72
import edu.uci.ics.jung.graph.util.TestGraphs;
73
import edu.uci.ics.jung.graph.Graph;
74

75
// Create basic test graphs
76
Graph<String, Number> directedTest = TestGraphs.createTestGraph(true);   // Directed test graph
77
Graph<String, Number> undirectedTest = TestGraphs.createTestGraph(false); // Undirected test graph
78

79
System.out.println("Directed test graph:");
80
System.out.println("Vertices: " + directedTest.getVertices());
81
System.out.println("Edges: " + directedTest.getEdges());
82

83
// Create chain with isolated vertices
84
Graph<String, Number> chainGraph = TestGraphs.createChainPlusIsolates(5, 3);
85
// Creates: V0-V1-V2-V3-V4 (chain) plus V5, V6, V7 (isolated)
86

87
System.out.println("Chain graph vertices: " + chainGraph.getVertexCount()); // 8 total
88
System.out.println("Chain graph edges: " + chainGraph.getEdgeCount());     // 4 edges in chain
89

90
// Create directed acyclic graph (DAG)
91
Graph<String, Number> dag = TestGraphs.createDirectedAcyclicGraph(
92
    4,      // 4 layers
93
    3,      // max 3 nodes per layer  
94
    0.5     // 50% probability of edges between layers
95
);
96

97
System.out.println("DAG structure:");
98
System.out.println("Vertices: " + dag.getVertices());
99
System.out.println("Edges: " + dag.getEdges());
100

101
// Get predefined complex graphs
102
Graph<String, Number> oneComponent = TestGraphs.getOneComponentGraph();
103
Graph<String, Number> demo = TestGraphs.getDemoGraph();
104
Graph<String, Number> mixed = TestGraphs.getSmallGraph();
105

106
// Analyze graph properties
107
System.out.println("One component graph - Vertices: " + oneComponent.getVertexCount());
108
System.out.println("Demo graph - Components and features: " + demo.getVertexCount() + " vertices");
109
System.out.println("Mixed graph - Edge types: " + mixed.getEdgeCount() + " edges");
110
```
111

112
## Predefined Graph Structures
113

114
### Basic Test Graph
115

116
The `createTestGraph()` method creates a small, well-structured graph suitable for basic algorithm testing:
117

118
```java
119
Graph<String, Number> testGraph = TestGraphs.createTestGraph(false);
120

121
// Typical structure includes:
122
// - Multiple connected components
123
// - Various vertex degrees
124
// - Predictable structure for verification
125
```
126

127
### Chain Plus Isolates
128

129
Creates a linear chain of connected vertices with additional isolated vertices:
130

131
```java
132
Graph<String, Number> chain = TestGraphs.createChainPlusIsolates(4, 2);
133

134
// Structure: V0-V1-V2-V3 (connected chain) + V4, V5 (isolated)
135
// Useful for testing:
136
// - Connected component algorithms
137
// - Graph traversal behavior with disconnected vertices
138
// - Isolation detection algorithms
139
```
140

141
### Directed Acyclic Graph (DAG)
142

143
Generates layered DAGs with configurable structure:
144

145
```java
146
Graph<String, Number> dag = TestGraphs.createDirectedAcyclicGraph(3, 4, 0.7);
147

148
// Creates 3 layers with up to 4 vertices each
149
// 70% probability of edges between adjacent layers
150
// Guarantees acyclic property
151
// Useful for:
152
// - Topological sorting algorithms
153
// - Dependency resolution testing
154
// - Scheduling algorithm verification
155
```
156

157
### One Component Graph
158

159
Provides a larger connected graph with single component:
160

161
```java
162
Graph<String, Number> connected = TestGraphs.getOneComponentGraph();
163

164
// Features:
165
// - All vertices reachable from any starting vertex
166
// - Various local structures (paths, cycles, branches)
167
// - Suitable for testing connectivity algorithms
168
```
169

170
### Demo Graph
171

172
Complex graph with multiple structural features:
173

174
```java
175
Graph<String, Number> demo = TestGraphs.getDemoGraph();
176

177
// Includes:
178
// - Cliques (fully connected subgraphs)
179
// - Multiple components
180
// - Various structural patterns
181
// - Comprehensive test case for complex algorithms
182
```
183

184
### Small Mixed Graph
185

186
Demonstrates various edge types in a compact structure:
187

188
```java
189
Graph<String, Number> mixed = TestGraphs.getSmallGraph();
190

191
// Features:
192
// - Directed edges
193
// - Undirected edges  
194
// - Parallel edges (if using multigraph)
195
// - Compact size for debugging mixed-graph algorithms
196
```
197

198
## Usage Patterns
199

200
### Algorithm Testing
201

202
```java
203
// Test graph algorithms with various structures
204
Graph<String, Number> testCase = TestGraphs.createTestGraph(true);
205

206
// Run your algorithm
207
MyGraphAlgorithm algorithm = new MyGraphAlgorithm();
208
Result result = algorithm.process(testCase);
209

210
// Verify expected behavior on known structure
211
assert result.isValid() : "Algorithm failed on test graph";
212
```
213

214
### Performance Benchmarking
215

216
```java
217
// Create graphs of different sizes for performance testing
218
Graph<String, Number> small = TestGraphs.createChainPlusIsolates(10, 5);
219
Graph<String, Number> medium = TestGraphs.createDirectedAcyclicGraph(5, 10, 0.3);
220
Graph<String, Number> large = TestGraphs.getOneComponentGraph();
221

222
// Measure algorithm performance across different graph sizes
223
long startTime = System.currentTimeMillis();
224
algorithm.process(large);
225
long endTime = System.currentTimeMillis();
226
System.out.println("Processing time: " + (endTime - startTime) + "ms");
227
```
228

229
### Educational Examples
230

231
```java
232
// Demonstrate different graph properties
233
Graph<String, Number> dag = TestGraphs.createDirectedAcyclicGraph(3, 3, 0.5);
234
System.out.println("DAG has " + dag.getVertexCount() + " vertices");
235

236
// Show connectivity properties
237
Graph<String, Number> disconnected = TestGraphs.createChainPlusIsolates(3, 2);
238
System.out.println("Graph has isolated vertices: " + hasIsolatedVertices(disconnected));
239
```
240

241
### Regression Testing
242

243
```java
244
// Use consistent test graphs for regression testing
245
public void testMyAlgorithm() {
246
    Graph<String, Number> standardTest = TestGraphs.createTestGraph(false);
247
    
248
    Result result = myAlgorithm.process(standardTest);
249
    
250
    // Verify against known good results
251
    assertEquals(expectedVertexCount, result.getProcessedVertices());
252
    assertEquals(expectedEdgeCount, result.getProcessedEdges());
253
}
254
```
255

256
## Graph Properties
257

258
### Vertex and Edge Naming
259

260
TestGraphs uses consistent naming conventions:
261
- **Vertices**: Usually named as strings like "V0", "V1", "V2", etc.
262
- **Edges**: Numbered using Integer objects: 0, 1, 2, etc.
263
- **Weights**: Edge weights are meaningful integers when applicable
264

265
### Structural Guarantees
266

267
- **DAGs**: `createDirectedAcyclicGraph()` guarantees no cycles
268
- **Connectivity**: `getOneComponentGraph()` ensures single connected component
269
- **Isolation**: `createChainPlusIsolates()` creates predictable isolated vertices
270
- **Reproducibility**: All methods create deterministic structures (same inputs → same graph)
271

272
### Size Characteristics
273

274
| Method | Typical Vertex Count | Typical Edge Count | Components |
275
|--------|---------------------|-------------------|------------|
276
| `createTestGraph()` | 6-10 | 8-15 | Multiple |
277
| `createChainPlusIsolates(n,m)` | n+m | n-1 | m+1 |
278
| `createDirectedAcyclicGraph()` | Varies by parameters | Probabilistic | 1 |
279
| `getOneComponentGraph()` | 10-20 | 15-30 | 1 |
280
| `getDemoGraph()` | 15-25 | 20-40 | Multiple |
281
| `getSmallGraph()` | 4-8 | 6-12 | Varies |
282
283
## Integration with JUNG Framework
284

285
TestGraphs integrates seamlessly with all JUNG graph implementations:
286

287
```java
288
// Works with any JUNG graph type
289
DirectedGraph<String, Number> directed = new DirectedSparseGraph<>();
290
Graph<String, Number> testData = TestGraphs.createTestGraph(true);
291

292
// Copy test structure to your graph type
293
for (String vertex : testData.getVertices()) {
294
    directed.addVertex(vertex);
295
}
296
for (Number edge : testData.getEdges()) {
297
    Pair<String> endpoints = testData.getEndpoints(edge);
298
    directed.addEdge(edge, endpoints.getFirst(), endpoints.getSecond());
299
}
300
```