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

Commitfafa52c

Browse files
committed
Refactor Floyd-Warshall tests.
1 parent2874637 commitfafa52c

File tree

2 files changed

+29
-27
lines changed

2 files changed

+29
-27
lines changed

‎src/algorithms/graph/floyd-warshall/__test__/floydWarshall.test.js

Lines changed: 23 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -55,7 +55,7 @@ describe('floydWarshall', () => {
5555
.addEdge(edgeFG)
5656
.addEdge(edgeEG);
5757

58-
const{ distances,previousVertices}=floydWarshall(graph);
58+
const{ distances,nextVertices}=floydWarshall(graph);
5959

6060
constvertices=graph.getAllVertices();
6161

@@ -77,13 +77,13 @@ describe('floydWarshall', () => {
7777
expect(distances[vertexAIndex][vertexGIndex]).toBe(12);
7878
expect(distances[vertexAIndex][vertexFIndex]).toBe(11);
7979

80-
expect(previousVertices[vertexAIndex][vertexFIndex]).toBe(vertexD);
81-
expect(previousVertices[vertexAIndex][vertexDIndex]).toBe(vertexB);
82-
expect(previousVertices[vertexAIndex][vertexBIndex]).toBe(vertexA);
83-
expect(previousVertices[vertexAIndex][vertexGIndex]).toBe(vertexE);
84-
expect(previousVertices[vertexAIndex][vertexCIndex]).toBe(vertexA);
85-
expect(previousVertices[vertexAIndex][vertexAIndex]).toBe(null);
86-
expect(previousVertices[vertexAIndex][vertexHIndex]).toBe(null);
80+
expect(nextVertices[vertexAIndex][vertexFIndex]).toBe(vertexD);
81+
expect(nextVertices[vertexAIndex][vertexDIndex]).toBe(vertexB);
82+
expect(nextVertices[vertexAIndex][vertexBIndex]).toBe(vertexA);
83+
expect(nextVertices[vertexAIndex][vertexGIndex]).toBe(vertexE);
84+
expect(nextVertices[vertexAIndex][vertexCIndex]).toBe(vertexA);
85+
expect(nextVertices[vertexAIndex][vertexAIndex]).toBe(null);
86+
expect(nextVertices[vertexAIndex][vertexHIndex]).toBe(null);
8787
});
8888

8989
it('should find minimum paths to all vertices for directed graph',()=>{
@@ -119,7 +119,7 @@ describe('floydWarshall', () => {
119119
.addEdge(edgeCA)
120120
.addEdge(edgeCD);
121121

122-
const{ distances,previousVertices}=floydWarshall(graph);
122+
const{ distances,nextVertices}=floydWarshall(graph);
123123

124124
constvertices=graph.getAllVertices();
125125

@@ -140,11 +140,11 @@ describe('floydWarshall', () => {
140140
[2,5,7,0],
141141
]);
142142

143-
expect(previousVertices[vertexAIndex][vertexDIndex]).toBe(vertexC);
144-
expect(previousVertices[vertexAIndex][vertexCIndex]).toBe(vertexB);
145-
expect(previousVertices[vertexBIndex][vertexDIndex]).toBe(vertexC);
146-
expect(previousVertices[vertexAIndex][vertexAIndex]).toBe(null);
147-
expect(previousVertices[vertexAIndex][vertexBIndex]).toBe(vertexA);
143+
expect(nextVertices[vertexAIndex][vertexDIndex]).toBe(vertexC);
144+
expect(nextVertices[vertexAIndex][vertexCIndex]).toBe(vertexB);
145+
expect(nextVertices[vertexBIndex][vertexDIndex]).toBe(vertexC);
146+
expect(nextVertices[vertexAIndex][vertexAIndex]).toBe(null);
147+
expect(nextVertices[vertexAIndex][vertexBIndex]).toBe(vertexA);
148148
});
149149

150150
it('should find minimum paths to all vertices for directed graph with negative edge weights',()=>{
@@ -188,7 +188,7 @@ describe('floydWarshall', () => {
188188
.addEdge(edgeCB)
189189
.addEdge(edgeBA);
190190

191-
const{ distances,previousVertices}=floydWarshall(graph);
191+
const{ distances,nextVertices}=floydWarshall(graph);
192192

193193
constvertices=graph.getAllVertices();
194194

@@ -208,11 +208,13 @@ describe('floydWarshall', () => {
208208
expect(distances[vertexFIndex][vertexDIndex]).toBe(9);
209209
expect(distances[vertexFIndex][vertexEIndex]).toBe(8);
210210

211-
expect(previousVertices[vertexFIndex][vertexGIndex]).toBe(null);
212-
expect(previousVertices[vertexFIndex][vertexFIndex]).toBe(null);
213-
// expect(previousVertices[vertexFIndex][vertexBIndex]).toBe(vertexC);
214-
// expect(previousVertices[vertexFIndex][vertexCIndex].getKey()).toBe(vertexA.getKey());
215-
// expect(previousVertices[vertexFIndex][vertexAIndex]).toBe(vertexD);
216-
// expect(previousVertices[vertexFIndex][vertexDIndex]).toBe(vertexE);
211+
expect(nextVertices[vertexFIndex][vertexGIndex]).toBe(null);
212+
expect(nextVertices[vertexFIndex][vertexFIndex]).toBe(null);
213+
expect(nextVertices[vertexAIndex][vertexBIndex]).toBe(vertexC);
214+
expect(nextVertices[vertexAIndex][vertexCIndex]).toBe(vertexA);
215+
expect(nextVertices[vertexFIndex][vertexBIndex]).toBe(vertexE);
216+
expect(nextVertices[vertexEIndex][vertexBIndex]).toBe(vertexD);
217+
expect(nextVertices[vertexDIndex][vertexBIndex]).toBe(vertexC);
218+
expect(nextVertices[vertexCIndex][vertexBIndex]).toBe(vertexC);
217219
});
218220
});

‎src/algorithms/graph/floyd-warshall/floydWarshall.js

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,14 @@
11
/**
22
*@param {Graph} graph
3-
*@return {{distances: number[][],previousVertices: GraphVertex[][]}}
3+
*@return {{distances: number[][],nextVertices: GraphVertex[][]}}
44
*/
55
exportdefaultfunctionfloydWarshall(graph){
66
// Get all graph vertices.
77
constvertices=graph.getAllVertices();
88

99
// Init previous vertices matrix with nulls meaning that there are no
1010
// previous vertices exist that will give us shortest path.
11-
constpreviousVertices=Array(vertices.length).fill(null).map(()=>{
11+
constnextVertices=Array(vertices.length).fill(null).map(()=>{
1212
returnArray(vertices.length).fill(null);
1313
});
1414

@@ -33,7 +33,7 @@ export default function floydWarshall(graph) {
3333
// There is an edge from vertex with startIndex to vertex with endIndex.
3434
// Save distance and previous vertex.
3535
distances[startIndex][endIndex]=edge.weight;
36-
previousVertices[startIndex][endIndex]=startVertex;
36+
nextVertices[startIndex][endIndex]=startVertex;
3737
}else{
3838
distances[startIndex][endIndex]=Infinity;
3939
}
@@ -60,13 +60,13 @@ export default function floydWarshall(graph) {
6060
if(distances[startIndex][endIndex]>distViaMiddle){
6161
// We've found a shortest pass via middle vertex.
6262
distances[startIndex][endIndex]=distViaMiddle;
63-
previousVertices[startIndex][endIndex]=middleVertex;
63+
nextVertices[startIndex][endIndex]=middleVertex;
6464
}
6565
});
6666
});
6767
});
6868

6969
// Shortest distance from x to y: distance[x][y].
70-
//Previous vertexof shortestpath from x to y:previousVertices[x][y].
71-
return{ distances,previousVertices};
70+
//Next vertexafter x one inpath from x to y:nextVertices[x][y].
71+
return{ distances,nextVertices};
7272
}

0 commit comments

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