-
Notifications
You must be signed in to change notification settings - Fork 292
/
Johnson_Tests.cs
116 lines (88 loc) · 3.47 KB
/
Johnson_Tests.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
using System.Linq;
using Advanced.Algorithms.DataStructures.Graph.AdjacencyList;
using Advanced.Algorithms.Graph;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace Advanced.Algorithms.Tests.Graph
{
[TestClass]
public class JohnsonsTests
{
[TestMethod]
public void Johnsons_AdjacencyListGraph_Smoke_Test()
{
var graph = new WeightedDiGraph<char, int>();
graph.AddVertex('S');
graph.AddVertex('A');
graph.AddVertex('B');
graph.AddVertex('C');
graph.AddVertex('D');
graph.AddVertex('T');
graph.AddEdge('S', 'A', -5);
graph.AddEdge('S', 'C', 10);
graph.AddEdge('A', 'B', 10);
graph.AddEdge('A', 'C', 1);
graph.AddEdge('A', 'D', 8);
graph.AddEdge('B', 'T', 4);
graph.AddEdge('C', 'D', 1);
graph.AddEdge('D', 'B', 1);
graph.AddEdge('D', 'T', 10);
var algorithm = new JohnsonsShortestPath<char, int>(new JohnsonsShortestPathOperators());
var result = algorithm.FindAllPairShortestPaths(graph);
var testCase = result.First(x => x.Source == 'S' && x.Destination == 'T');
Assert.AreEqual(2, testCase.Distance);
var expectedPath = new[] { 'S', 'A', 'C', 'D', 'B', 'T' };
for (var i = 0; i < expectedPath.Length; i++) Assert.AreEqual(expectedPath[i], testCase.Path[i]);
}
[TestMethod]
public void Johnsons_AdjacencyMatrixGraph_Smoke_Test()
{
var graph = new Algorithms.DataStructures.Graph.AdjacencyMatrix.WeightedDiGraph<char, int>();
graph.AddVertex('S');
graph.AddVertex('A');
graph.AddVertex('B');
graph.AddVertex('C');
graph.AddVertex('D');
graph.AddVertex('T');
graph.AddEdge('S', 'A', -5);
graph.AddEdge('S', 'C', 10);
graph.AddEdge('A', 'B', 10);
graph.AddEdge('A', 'C', 1);
graph.AddEdge('A', 'D', 8);
graph.AddEdge('B', 'T', 4);
graph.AddEdge('C', 'D', 1);
graph.AddEdge('D', 'B', 1);
graph.AddEdge('D', 'T', 10);
var algorithm = new JohnsonsShortestPath<char, int>(new JohnsonsShortestPathOperators());
var result = algorithm.FindAllPairShortestPaths(graph);
var testCase = result.First(x => x.Source == 'S' && x.Destination == 'T');
Assert.AreEqual(2, testCase.Distance);
var expectedPath = new[] { 'S', 'A', 'C', 'D', 'B', 'T' };
for (var i = 0; i < expectedPath.Length; i++) Assert.AreEqual(expectedPath[i], testCase.Path[i]);
}
/// <summary>
/// generic operations for int type
/// </summary>
public class JohnsonsShortestPathOperators
: IJohnsonsShortestPathOperators<char, int>
{
public int DefaultValue => 0;
public int MaxValue => int.MaxValue;
/// <summary>
/// return a char not in graph
/// </summary>
/// <returns></returns>
public char RandomVertex()
{
return '*';
}
public int Substract(int a, int b)
{
return checked(a - b);
}
public int Sum(int a, int b)
{
return checked(a + b);
}
}
}
}