OSDN Git Service

cflib は plugins プロジェクトから,Stigmata直下のプロジェクトに移行したため,このリポジトリからは削除した.
[stigmata/stigmata-plugins.git] / osb / src / test / java / jp / sourceforge / stigmata / birthmarks / osb / hungarian / HungarianMethodTest.java
1 package jp.sourceforge.stigmata.birthmarks.osb.hungarian;\r
2 \r
3 import org.junit.Assert;\r
4 import org.junit.Before;\r
5 import org.junit.Test;\r
6 \r
7 public class HungarianMethodTest{\r
8     @Before\r
9     public void setUp(){\r
10     }\r
11 \r
12     @Test\r
13     public void testBasic(){\r
14         CostMatrix matrix = new CostMatrix(new double[][] {\r
15             { 0.2, 0.2, 0.333, 0.1, },\r
16             { 0.75, 0.75, 0.666, 0.2, },\r
17             { 0.3, 0.3, 0.4, 0.15, },\r
18             { 0.2, 0.2, 1, 0.2, },\r
19         }, true);\r
20         HungarianMethod method = new HungarianMethod(matrix);\r
21         Assert.assertEquals(2.15, method.solve(), 1E-6);\r
22     }\r
23 \r
24     @Test\r
25     public void testBasic2(){\r
26         CostMatrix matrix = new CostMatrix(new double[][] {\r
27             { 0.209595, 0.465415, 0.760024, 0.956651, 0.838918, 0.914212, 0.299751, },\r
28             { 0.350187, 0.043090, 0.996489, 0.130135, 0.116187, 0.395586, 0.257572, },\r
29             { 0.400339, 0.340549, 0.518255, 0.301846, 0.215443, 0.481817, 0.167668, },\r
30             { 0.844414, 0.737599, 0.894256, 0.667530, 0.029905, 0.256991, 0.867919, },\r
31             { 0.113587, 0.433392, 0.067705, 0.763238, 0.508876, 0.460116, 0.168199, },\r
32             { 0.697585, 0.874909, 0.568728, 0.646872, 0.027345, 0.428272, 0.857028, },\r
33             { 0.110312, 0.561466, 0.112358, 0.069674, 0.665109, 0.041041, 0.130386, },\r
34             { 0.014101, 0.773713, 0.924393, 0.638526, 0.703886, 0.770603, 0.928259, },\r
35             { 0.426957, 0.288075, 0.947143, 0.093035, 0.241806, 0.970468, 0.891780, },\r
36         }, true);\r
37         HungarianMethod method = new HungarianMethod(matrix);\r
38         Assert.assertEquals(6.236299, method.solve(), 1E-6);\r
39     }\r
40 \r
41     @Test\r
42     public void testBasic3(){\r
43         CostMatrix matrix = new CostMatrix(new double[][] {\r
44             { 0.109821, 0.108200, 0.967758, 0.879690, 0.606278, 0.627169, 0.230391, },  \r
45             { 0.517603, 0.045502, 0.279343, 0.942029, 0.630428, 0.517259, 0.659899, },  \r
46             { 0.846279, 0.220084, 0.929258, 0.009920, 0.773227, 0.304251, 0.406748, },  \r
47             { 0.075661, 0.022613, 0.006470, 0.847046, 0.869278, 0.147251, 0.313651, },  \r
48             { 0.118903, 0.911011, 0.800919, 0.634199, 0.909296, 0.865808, 0.780742, },  \r
49             { 0.701107, 0.889183, 0.226646, 0.516193, 0.681720, 0.694964, 0.842307, },  \r
50             { 0.035120, 0.579560, 0.203825, 0.639133, 0.871800, 0.143418, 0.718832, },  \r
51         }, true);\r
52         HungarianMethod method = new HungarianMethod(matrix);\r
53         Assert.assertEquals(6.099167, method.solve(), 1E-6);\r
54     }\r
55 \r
56     @Test\r
57     public void testBasic4(){\r
58         CostMatrix matrix = new CostMatrix(new double[][] {\r
59             { 0.2, 0.3, 0.5, 0.2, 0.6, },\r
60             { 0.4, 0.6, 0.6, 0.6, 0.7, },\r
61             { 0.4, 0.4, 0.7, 0.3, 0.4, },\r
62             { 0.3, 0.6, 0.4, 0.5, 0.5, },\r
63             { 0.4, 0.2, 0.7, 0.4, 0.4, },\r
64         }, false);\r
65         HungarianMethod method = new HungarianMethod(matrix);\r
66         double value = method.solve();\r
67         Cell[] solution = method.getSolutions();\r
68         Assert.assertEquals(5, solution.length);\r
69 \r
70         Assert.assertEquals(0, solution[0].getX());\r
71         Assert.assertEquals(3, solution[0].getY());\r
72         Assert.assertEquals(0.2, solution[0].getValue(), 1E-6);\r
73 \r
74         Assert.assertEquals(1, solution[1].getX());\r
75         Assert.assertEquals(0, solution[1].getY());\r
76         Assert.assertEquals(0.4, solution[1].getValue(), 1E-6);\r
77 \r
78         Assert.assertEquals(2, solution[2].getX());\r
79         Assert.assertEquals(4, solution[2].getY());\r
80         Assert.assertEquals(0.4, solution[2].getValue(), 1E-6);\r
81 \r
82         Assert.assertEquals(3, solution[3].getX());\r
83         Assert.assertEquals(2, solution[3].getY());\r
84         Assert.assertEquals(0.4, solution[3].getValue(), 1E-6);\r
85 \r
86         Assert.assertEquals(4, solution[4].getX());\r
87         Assert.assertEquals(1, solution[4].getY());\r
88         Assert.assertEquals(0.2, solution[4].getValue(), 1E-6);\r
89 \r
90         Assert.assertEquals(1.6, value, 1E-6);\r
91     }\r
92 \r
93     @Test\r
94     public void testBasic5(){\r
95         CostMatrix matrix = new CostMatrix(new double[][] {\r
96             { 0.2, 0.3, 0.4, 0.3, 0.6, },\r
97             { 0.4, 0.6, 0.5, 0.6, 0.7, },\r
98             { 0.4, 0.4, 0.6, 0.3, 0.4, },\r
99             { 0.4, 0.6, 0.3, 0.5, 0.5, },\r
100             { 0.4, 0.2, 0.6, 0.4, 0.4, },\r
101         }, false);\r
102         HungarianMethod method = new HungarianMethod(matrix);\r
103         double value = method.solve();\r
104         Cell[] solution = method.getSolutions();\r
105         Assert.assertEquals(5, solution.length);\r
106 \r
107         Assert.assertEquals(0, solution[0].getX());\r
108         Assert.assertEquals(3, solution[0].getY());\r
109         Assert.assertEquals(0.3, solution[0].getValue(), 1E-6);\r
110 \r
111         Assert.assertEquals(1, solution[1].getX());\r
112         Assert.assertEquals(0, solution[1].getY());\r
113         Assert.assertEquals(0.4, solution[1].getValue(), 1E-6);\r
114 \r
115         Assert.assertEquals(2, solution[2].getX());\r
116         Assert.assertEquals(4, solution[2].getY());\r
117         Assert.assertEquals(0.4, solution[2].getValue(), 1E-6);\r
118 \r
119         Assert.assertEquals(3, solution[3].getX());\r
120         Assert.assertEquals(2, solution[3].getY());\r
121         Assert.assertEquals(0.3, solution[3].getValue(), 1E-6);\r
122 \r
123         Assert.assertEquals(4, solution[4].getX());\r
124         Assert.assertEquals(1, solution[4].getY());\r
125         Assert.assertEquals(0.2, solution[4].getValue(), 1E-6);\r
126 \r
127         Assert.assertEquals(1.6, value, 1E-6);\r
128     }\r
129 \r
130     @Test\r
131     public void testBasic6(){\r
132         CostMatrix matrix = new CostMatrix(new double[][] {\r
133             { 0.8, 0.9, 0.3, 0.8, },\r
134             { 0.6, 0.8, 0.6, 0.2, },\r
135             { 0.7, 0.7, 0.9, 0.6, },\r
136             { 0.2, 0.5, 0.8, 0.4, },\r
137             { 0.4, 0.6, 0.2, 0.7, },\r
138         }, true);\r
139         HungarianMethod method = new HungarianMethod(matrix);\r
140         double value = method.solve();\r
141         Cell[] solutions = method.getSolutions();\r
142 \r
143         Assert.assertEquals(3.2, value, 1E-6);\r
144         Assert.assertEquals(4, solutions.length);\r
145 \r
146         Assert.assertEquals(0, solutions[0].getX());\r
147         Assert.assertEquals(0, solutions[0].getY());\r
148         Assert.assertEquals(0.8, solutions[0].getValue(), 1E-6);\r
149 \r
150         Assert.assertEquals(1, solutions[1].getX());\r
151         Assert.assertEquals(1, solutions[1].getY());\r
152         Assert.assertEquals(0.8, solutions[1].getValue(), 1E-6);\r
153 \r
154         Assert.assertEquals(2, solutions[2].getX());\r
155         Assert.assertEquals(2, solutions[2].getY());\r
156         Assert.assertEquals(0.9, solutions[2].getValue(), 1E-6);\r
157 \r
158         Assert.assertEquals(4, solutions[3].getX());\r
159         Assert.assertEquals(3, solutions[3].getY());\r
160         Assert.assertEquals(0.7, solutions[3].getValue(), 1E-6);\r
161     }\r
162 \r
163     @Test\r
164     public void testBasic7(){\r
165         CostMatrix matrix = new CostMatrix(new double[][]{\r
166             { 1.0, 0.0, 0.2, 0.0, 0.33, 0.2, 0.1, 0.08, 0.2, 0.2, 0.0, 0.2, 0.2, 0.2, 0.2, 0.14, 0.14, 0.11, 0.2, 0.25, 0.09, 0.2, 0.0, 0.0, 0.25, 0.0, },\r
167             { 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.33, },\r
168             { 0.2, 0.0, 1.0, 0.17, 0.0, 0.0, 0.44, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.17, 0.27, 0.0, 0.0, 0.2, 0.0, 0.0, },\r
169             { 0.0, 0.0, 0.17, 1.0, 0.0, 0.17, 0.2, 0.07, 0.17, 0.17, 0.0, 0.17, 0.17, 0.17, 0.17, 0.13, 0.13, 0.1, 0.17, 0.2, 0.08, 0.17, 0.0, 0.25, 0.2, 0.0, },\r
170             { 0.33, 0.0, 0.0, 0.0, 1.0, 0.2, 0.1, 0.08, 0.2, 0.2, 0.0, 0.2, 0.2, 0.2, 0.2, 0.14, 0.14, 0.11, 0.2, 0.25, 0.09, 0.2, 0.0, 0.0, 0.25, 0.0, },\r
171             { 0.2, 0.0, 0.0, 0.17, 0.2, 1.0, 0.18, 0.23, 1.0, 0.6, 0.0, 0.6, 0.6, 0.6, 0.6, 0.43, 0.43, 0.33, 0.6, 0.4, 0.17, 0.33, 0.0, 0.0, 0.4, 0.17, },\r
172             { 0.1, 0.0, 0.44, 0.2, 0.1, 0.18, 1.0, 0.24, 0.18, 0.18, 0.0, 0.18, 0.18, 0.18, 0.18, 0.25, 0.25, 0.31, 0.18, 0.33, 0.73, 0.18, 0.0, 0.1, 0.33, 0.09, },\r
173             { 0.08, 0.0, 0.0, 0.07, 0.08, 0.23, 0.24, 1.0, 0.23, 0.33, 0.0, 0.33, 0.33, 0.33, 0.33, 0.5, 0.5, 0.67, 0.33, 0.15, 0.29, 0.23, 0.0, 0.08, 0.15, 0.15, },\r
174             { 0.2, 0.0, 0.0, 0.17, 0.2, 1.0, 0.18, 0.23, 1.0, 0.6, 0.0, 0.6, 0.6, 0.6, 0.6, 0.43, 0.43, 0.33, 0.6, 0.4, 0.17, 0.33, 0.0, 0.0, 0.4, 0.17, },\r
175             { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
176             { 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, },\r
177             { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
178             { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
179             { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
180             { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
181             { 0.14, 0.0, 0.0, 0.13, 0.14, 0.43, 0.25, 0.5, 0.43, 0.67, 0.0, 0.67, 0.67, 0.67, 0.67, 1.0, 1.0, 0.75, 0.67, 0.29, 0.23, 0.43, 0.0, 0.14, 0.29, 0.29, },\r
182             { 0.14, 0.0, 0.0, 0.13, 0.14, 0.43, 0.25, 0.5, 0.43, 0.67, 0.0, 0.67, 0.67, 0.67, 0.67, 1.0, 1.0, 0.75, 0.67, 0.29, 0.23, 0.43, 0.0, 0.14, 0.29, 0.29, },\r
183             { 0.11, 0.0, 0.0, 0.1, 0.11, 0.33, 0.31, 0.67, 0.33, 0.5, 0.0, 0.5, 0.5, 0.5, 0.5, 0.75, 0.75, 1.0, 0.5, 0.22, 0.29, 0.33, 0.0, 0.11, 0.22, 0.22, },\r
184             { 0.2, 0.0, 0.0, 0.17, 0.2, 0.6, 0.18, 0.33, 0.6, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.67, 0.67, 0.5, 1.0, 0.4, 0.17, 0.6, 0.0, 0.0, 0.4, 0.17, },\r
185             { 0.25, 0.0, 0.17, 0.2, 0.25, 0.4, 0.33, 0.15, 0.4, 0.4, 0.0, 0.4, 0.4, 0.4, 0.4, 0.29, 0.29, 0.22, 0.4, 1.0, 0.18, 0.4, 0.0, 0.25, 0.2, 0.2, },\r
186             { 0.09, 0.0, 0.27, 0.08, 0.09, 0.17, 0.73, 0.29, 0.17, 0.17, 0.0, 0.17, 0.17, 0.17, 0.17, 0.23, 0.23, 0.29, 0.17, 0.18, 1.0, 0.17, 0.0, 0.09, 0.3, 0.18, },\r
187             { 0.2, 0.0, 0.0, 0.17, 0.2, 0.33, 0.18, 0.23, 0.33, 0.6, 0.0, 0.6, 0.6, 0.6, 0.6, 0.43, 0.43, 0.33, 0.6, 0.4, 0.17, 1.0, 0.0, 0.0, 0.17, 0.17, },\r
188             { 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, },\r
189             { 0.0, 0.0, 0.2, 0.25, 0.0, 0.0, 0.1, 0.08, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.14, 0.14, 0.11, 0.0, 0.25, 0.09, 0.0, 0.0, 1.0, 0.0, 0.25, },\r
190             { 0.25, 0.0, 0.0, 0.2, 0.25, 0.4, 0.33, 0.15, 0.4, 0.4, 0.0, 0.4, 0.4, 0.4, 0.4, 0.29, 0.29, 0.22, 0.4, 0.2, 0.3, 0.17, 0.0, 0.0, 1.0, 0.2, },\r
191             { 0.0, 0.33, 0.0, 0.0, 0.0, 0.17, 0.09, 0.15, 0.17, 0.17, 0.0, 0.17, 0.17, 0.17, 0.17, 0.29, 0.29, 0.22, 0.17, 0.2, 0.18, 0.17, 0.0, 0.25, 0.2, 1.0, },\r
192         }, true);\r
193         HungarianMethod method = new HungarianMethod(matrix);\r
194         double value = method.solve();\r
195         Assert.assertEquals(26, value, 1E-6);\r
196     }\r
197 \r
198     @Test\r
199     public void testBasic8(){\r
200         CostMatrix matrix = new CostMatrix(new double[][] {\r
201             { 1.0000, 0.0000, 0.0000, 0.0000, 0.2000, 0.1429, 0.6667, 0.0000, },\r
202             { 0.0000, 1.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 1.0000, },\r
203             { 0.0000, 0.0000, 1.0000, 1.0000, 0.2000, 0.1429, 0.0000, 0.0000, },\r
204             { 0.0000, 0.0000, 1.0000, 1.0000, 0.2000, 0.1429, 0.0000, 0.0000, },\r
205             { 0.2000, 0.0000, 0.2000, 0.2000, 1.0000, 0.4286, 0.1667, 0.0000, },\r
206             { 0.6667, 0.0000, 0.0000, 0.0000, 0.1667, 0.1250, 1.0000, 0.0000, },\r
207             { 0.0000, 1.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 1.0000, },\r
208         }, true);\r
209 \r
210         HungarianMethod method = new HungarianMethod(matrix);\r
211         double value = method.solve();\r
212         Assert.assertEquals(7, value, 1E-6);\r
213     }\r
214 }\r