Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit4f40206

Browse files
LucasAHornprashantdubeypng
and
prashantdubeypng
authored
Add unit tests for graph algorithms (#7133) (#7156)
* Add unit tests for graph algorithms (BFS, DFS, Dijkstra, Bellman-Ford)#7133- Created BellmanFordTest.java with 10 test methods covering various graph scenarios- Created ConnectedComponentTest.java with 15 test methods for DFS-based component counting- Enhanced MatrixGraphsTest.java with additional BFS/DFS test cases- Enhanced DijkstraAlgorithmTest.java with comprehensive shortest path testsFixes#7133* fix: format files using clang* fix: removing my changes on pull_request_template---------Co-authored-by: prashantdubeypng <vinoddubey6059@gmail.com>
1 parent520151a commit4f40206

File tree

4 files changed

+690
-0
lines changed

4 files changed

+690
-0
lines changed
Lines changed: 158 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,158 @@
1+
packagecom.thealgorithms.datastructures.graphs;
2+
3+
importstaticorg.junit.jupiter.api.Assertions.assertEquals;
4+
importstaticorg.junit.jupiter.api.Assertions.assertNotNull;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
/**
9+
* Unit tests for the BellmanFord algorithm implementation.
10+
* Tests cover various graph scenarios including:
11+
* - Simple weighted graphs
12+
* - Graphs with negative weights
13+
* - Single vertex graphs
14+
* - Disconnected graphs
15+
* - Linear path graphs
16+
*/
17+
classBellmanFordTest {
18+
19+
@Test
20+
voidtestSimpleGraph() {
21+
// Create a simple graph with 5 vertices and 8 edges
22+
// Graph visualization:
23+
// 1
24+
// /|\
25+
// 6 | 7
26+
// / | \
27+
// 0 5 2
28+
// \ | /
29+
// 8 | -2
30+
// \|/
31+
// 4---3
32+
// 9
33+
BellmanFordbellmanFord =newBellmanFord(5,8);
34+
bellmanFord.addEdge(0,1,6);
35+
bellmanFord.addEdge(0,4,8);
36+
bellmanFord.addEdge(1,2,7);
37+
bellmanFord.addEdge(1,4,5);
38+
bellmanFord.addEdge(2,3, -2);
39+
bellmanFord.addEdge(2,4, -3);
40+
bellmanFord.addEdge(3,4,9);
41+
bellmanFord.addEdge(4,3,7);
42+
43+
// Verify edge array creation
44+
assertNotNull(bellmanFord.getEdgeArray());
45+
assertEquals(8,bellmanFord.getEdgeArray().length);
46+
}
47+
48+
@Test
49+
voidtestGraphWithNegativeWeights() {
50+
// Graph with negative edge weights (but no negative cycle)
51+
BellmanFordbellmanFord =newBellmanFord(4,5);
52+
bellmanFord.addEdge(0,1,4);
53+
bellmanFord.addEdge(0,2,5);
54+
bellmanFord.addEdge(1,2, -3);
55+
bellmanFord.addEdge(2,3,4);
56+
bellmanFord.addEdge(1,3,6);
57+
58+
assertNotNull(bellmanFord.getEdgeArray());
59+
assertEquals(5,bellmanFord.getEdgeArray().length);
60+
}
61+
62+
@Test
63+
voidtestSingleVertexGraph() {
64+
// Graph with single vertex and no edges
65+
BellmanFordbellmanFord =newBellmanFord(1,0);
66+
assertNotNull(bellmanFord.getEdgeArray());
67+
assertEquals(0,bellmanFord.getEdgeArray().length);
68+
}
69+
70+
@Test
71+
voidtestLinearGraph() {
72+
// Linear graph: 0 -> 1 -> 2 -> 3
73+
BellmanFordbellmanFord =newBellmanFord(4,3);
74+
bellmanFord.addEdge(0,1,2);
75+
bellmanFord.addEdge(1,2,3);
76+
bellmanFord.addEdge(2,3,4);
77+
78+
assertNotNull(bellmanFord.getEdgeArray());
79+
assertEquals(3,bellmanFord.getEdgeArray().length);
80+
}
81+
82+
@Test
83+
voidtestEdgeAddition() {
84+
BellmanFordbellmanFord =newBellmanFord(3,3);
85+
86+
bellmanFord.addEdge(0,1,5);
87+
bellmanFord.addEdge(1,2,3);
88+
bellmanFord.addEdge(0,2,10);
89+
90+
// Verify all edges were added
91+
assertNotNull(bellmanFord.getEdgeArray());
92+
assertEquals(3,bellmanFord.getEdgeArray().length);
93+
}
94+
95+
@Test
96+
voidtestGraphWithZeroWeightEdges() {
97+
// Graph with zero weight edges
98+
BellmanFordbellmanFord =newBellmanFord(3,3);
99+
bellmanFord.addEdge(0,1,0);
100+
bellmanFord.addEdge(1,2,0);
101+
bellmanFord.addEdge(0,2,1);
102+
103+
assertNotNull(bellmanFord.getEdgeArray());
104+
assertEquals(3,bellmanFord.getEdgeArray().length);
105+
}
106+
107+
@Test
108+
voidtestLargerGraph() {
109+
// Larger graph with 6 vertices
110+
BellmanFordbellmanFord =newBellmanFord(6,9);
111+
bellmanFord.addEdge(0,1,5);
112+
bellmanFord.addEdge(0,2,3);
113+
bellmanFord.addEdge(1,3,6);
114+
bellmanFord.addEdge(1,2,2);
115+
bellmanFord.addEdge(2,4,4);
116+
bellmanFord.addEdge(2,5,2);
117+
bellmanFord.addEdge(2,3,7);
118+
bellmanFord.addEdge(3,4, -1);
119+
bellmanFord.addEdge(4,5, -2);
120+
121+
assertNotNull(bellmanFord.getEdgeArray());
122+
assertEquals(9,bellmanFord.getEdgeArray().length);
123+
}
124+
125+
@Test
126+
voidtestVertexAndEdgeCount() {
127+
BellmanFordbellmanFord =newBellmanFord(10,15);
128+
assertEquals(10,bellmanFord.vertex);
129+
assertEquals(15,bellmanFord.edge);
130+
}
131+
132+
@Test
133+
voidtestMultipleEdgesBetweenSameVertices() {
134+
// Graph allowing multiple edges between same vertices
135+
BellmanFordbellmanFord =newBellmanFord(2,3);
136+
bellmanFord.addEdge(0,1,5);
137+
bellmanFord.addEdge(0,1,3);
138+
bellmanFord.addEdge(1,0,2);
139+
140+
assertNotNull(bellmanFord.getEdgeArray());
141+
assertEquals(3,bellmanFord.getEdgeArray().length);
142+
}
143+
144+
@Test
145+
voidtestCompleteGraph() {
146+
// Complete graph with 4 vertices (6 edges for undirected equivalent)
147+
BellmanFordbellmanFord =newBellmanFord(4,6);
148+
bellmanFord.addEdge(0,1,1);
149+
bellmanFord.addEdge(0,2,2);
150+
bellmanFord.addEdge(0,3,3);
151+
bellmanFord.addEdge(1,2,4);
152+
bellmanFord.addEdge(1,3,5);
153+
bellmanFord.addEdge(2,3,6);
154+
155+
assertNotNull(bellmanFord.getEdgeArray());
156+
assertEquals(6,bellmanFord.getEdgeArray().length);
157+
}
158+
}
Lines changed: 204 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,204 @@
1+
packagecom.thealgorithms.datastructures.graphs;
2+
3+
importstaticorg.junit.jupiter.api.Assertions.assertEquals;
4+
importstaticorg.junit.jupiter.api.Assertions.assertNotNull;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
/**
9+
* Unit tests for the Graph class in ConnectedComponent.java.
10+
* Tests the depth-first search implementation and connected component counting.
11+
* Covers various graph topologies including:
12+
* - Single connected components
13+
* - Multiple disconnected components
14+
* - Self-loops
15+
* - Linear chains
16+
* - Cyclic graphs
17+
*/
18+
classConnectedComponentTest {
19+
20+
@Test
21+
voidtestSingleConnectedComponent() {
22+
Graph<Integer>graph =newGraph<>();
23+
graph.addEdge(1,2);
24+
graph.addEdge(2,3);
25+
graph.addEdge(3,4);
26+
graph.addEdge(4,1);
27+
28+
assertEquals(1,graph.countGraphs());
29+
}
30+
31+
@Test
32+
voidtestTwoDisconnectedComponents() {
33+
Graph<Integer>graph =newGraph<>();
34+
// Component 1: 1-2-3
35+
graph.addEdge(1,2);
36+
graph.addEdge(2,3);
37+
// Component 2: 4-5
38+
graph.addEdge(4,5);
39+
40+
assertEquals(2,graph.countGraphs());
41+
}
42+
43+
@Test
44+
voidtestThreeDisconnectedComponents() {
45+
Graph<Character>graph =newGraph<>();
46+
// Component 1: a-b-c-d-e
47+
graph.addEdge('a','b');
48+
graph.addEdge('a','e');
49+
graph.addEdge('b','e');
50+
graph.addEdge('b','c');
51+
graph.addEdge('c','d');
52+
graph.addEdge('d','a');
53+
// Component 2: x-y-z
54+
graph.addEdge('x','y');
55+
graph.addEdge('x','z');
56+
// Component 3: w (self-loop)
57+
graph.addEdge('w','w');
58+
59+
assertEquals(3,graph.countGraphs());
60+
}
61+
62+
@Test
63+
voidtestSingleNodeSelfLoop() {
64+
Graph<Integer>graph =newGraph<>();
65+
graph.addEdge(1,1);
66+
67+
assertEquals(1,graph.countGraphs());
68+
}
69+
70+
@Test
71+
voidtestLinearChain() {
72+
Graph<Integer>graph =newGraph<>();
73+
graph.addEdge(1,2);
74+
graph.addEdge(2,3);
75+
graph.addEdge(3,4);
76+
graph.addEdge(4,5);
77+
78+
assertEquals(1,graph.countGraphs());
79+
}
80+
81+
@Test
82+
voidtestStarTopology() {
83+
// Star graph with center node 0 connected to nodes 1, 2, 3, 4
84+
Graph<Integer>graph =newGraph<>();
85+
graph.addEdge(0,1);
86+
graph.addEdge(0,2);
87+
graph.addEdge(0,3);
88+
graph.addEdge(0,4);
89+
90+
assertEquals(1,graph.countGraphs());
91+
}
92+
93+
@Test
94+
voidtestCompleteGraph() {
95+
// Complete graph K4: every node connected to every other node
96+
Graph<Integer>graph =newGraph<>();
97+
graph.addEdge(1,2);
98+
graph.addEdge(1,3);
99+
graph.addEdge(1,4);
100+
graph.addEdge(2,3);
101+
graph.addEdge(2,4);
102+
graph.addEdge(3,4);
103+
104+
assertEquals(1,graph.countGraphs());
105+
}
106+
107+
@Test
108+
voidtestStringVertices() {
109+
Graph<String>graph =newGraph<>();
110+
// Component 1
111+
graph.addEdge("New York","Los Angeles");
112+
graph.addEdge("Los Angeles","Chicago");
113+
// Component 2
114+
graph.addEdge("London","Paris");
115+
// Component 3
116+
graph.addEdge("Tokyo","Tokyo");
117+
118+
assertEquals(3,graph.countGraphs());
119+
}
120+
121+
@Test
122+
voidtestEmptyGraph() {
123+
Graph<Integer>graph =newGraph<>();
124+
assertEquals(0,graph.countGraphs());
125+
}
126+
127+
@Test
128+
voidtestDepthFirstSearchBasic() {
129+
Graph<Integer>graph =newGraph<>();
130+
graph.addEdge(1,2);
131+
graph.addEdge(2,3);
132+
133+
// Get the first node and perform DFS
134+
assertNotNull(graph.nodeList);
135+
assertEquals(3,graph.nodeList.size());
136+
}
137+
138+
@Test
139+
voidtestManyIsolatedComponents() {
140+
Graph<Integer>graph =newGraph<>();
141+
// Create 5 isolated components (each is a self-loop)
142+
graph.addEdge(1,1);
143+
graph.addEdge(2,2);
144+
graph.addEdge(3,3);
145+
graph.addEdge(4,4);
146+
graph.addEdge(5,5);
147+
148+
assertEquals(5,graph.countGraphs());
149+
}
150+
151+
@Test
152+
voidtestBidirectionalEdges() {
153+
Graph<Integer>graph =newGraph<>();
154+
// Note: This is a directed graph representation
155+
// Adding edge 1->2 does not automatically add 2->1
156+
graph.addEdge(1,2);
157+
graph.addEdge(2,1);
158+
graph.addEdge(2,3);
159+
graph.addEdge(3,2);
160+
161+
assertEquals(1,graph.countGraphs());
162+
}
163+
164+
@Test
165+
voidtestCyclicGraph() {
166+
Graph<Integer>graph =newGraph<>();
167+
// Create a cycle: 1 -> 2 -> 3 -> 4 -> 1
168+
graph.addEdge(1,2);
169+
graph.addEdge(2,3);
170+
graph.addEdge(3,4);
171+
graph.addEdge(4,1);
172+
173+
assertEquals(1,graph.countGraphs());
174+
}
175+
176+
@Test
177+
voidtestMultipleCycles() {
178+
Graph<Integer>graph =newGraph<>();
179+
// Cycle 1: 1 -> 2 -> 3 -> 1
180+
graph.addEdge(1,2);
181+
graph.addEdge(2,3);
182+
graph.addEdge(3,1);
183+
// Cycle 2: 4 -> 5 -> 4
184+
graph.addEdge(4,5);
185+
graph.addEdge(5,4);
186+
187+
assertEquals(2,graph.countGraphs());
188+
}
189+
190+
@Test
191+
voidtestIntegerGraphFromMainExample() {
192+
// Recreate the example from main method
193+
Graph<Integer>graph =newGraph<>();
194+
graph.addEdge(1,2);
195+
graph.addEdge(2,3);
196+
graph.addEdge(2,4);
197+
graph.addEdge(3,5);
198+
graph.addEdge(7,8);
199+
graph.addEdge(8,10);
200+
graph.addEdge(10,8);
201+
202+
assertEquals(2,graph.countGraphs());
203+
}
204+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp