1 /*
2 * steghide 0.5.1 - a steganography program
3 * Copyright (C) 1999-2003 Stefan Hetzl <shetzl@chello.at>
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * as published by the Free Software Foundation; either version 2
8 * of the License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18 *
19 */
20
21 #define private public
22 #define protected public
23 #include "DFSAPHeuristic.h"
24 #undef private
25 #undef protected
26 #include "BitString.h"
27 #include "Edge.h"
28 #include "Graph.h"
29 #include "Matching.h"
30 #include "Selector.h"
31
32 #include "DummyFile.h"
33 #include "DFSAPHeuristicTest.h"
34
35 #define CREATEEDGE(G,V1,V2) (new Edge ((G)->getVertex(V1), 0, (G)->getVertex(V2), 1))
36
DFSAPHeuristicTest(TestSuite * s)37 DFSAPHeuristicTest::DFSAPHeuristicTest (TestSuite* s)
38 : UnitTest ("DFSAPHeuristic", s)
39 {
40 ADDTESTCATEGORY (DFSAPHeuristicTest, testAlgorithm) ;
41 }
42
setup()43 void DFSAPHeuristicTest::setup ()
44 {
45 UnitTest::setup() ;
46
47 // a trivial case to start with
48 {
49 Globs.reset() ;
50 std::vector<std::list<UWORD16> > adjlist (2) ;
51 adjlist[0].push_back(1) ;
52 DummyFile::createGraph (adjlist, &bs1, &f1, &s1) ;
53 g1 = new Graph (f1, *bs1, *s1) ;
54 m1 = new Matching (g1) ;
55 aph1 = new DFSAPHeuristic (g1, m1, 100.0) ;
56 gl1 = Globs ;
57 }
58
59 {
60 Globs.reset() ;
61 std::vector<std::list<UWORD16> > adjlist (4) ;
62 adjlist[0].push_back(1) ;
63 adjlist[1].push_back(2) ;
64 adjlist[2].push_back(3) ;
65 DummyFile::createGraph (adjlist, &bs2, &f2, &s2) ;
66 g2 = new Graph (f2, *bs2, *s2) ;
67 m2 = new Matching (g2) ;
68 m2->addEdge (CREATEEDGE (g2, 1, 2)) ;
69 aph2 = new DFSAPHeuristic (g2, m2, 100.0) ;
70 gl2 = Globs ;
71 }
72
73 // this is the example from Moehring's and Mueller-Hannemann's paper (Figure 2)
74 {
75 Globs.reset() ;
76 std::vector<std::list<UWORD16> > adjlist (8) ;
77 adjlist[0].push_back(1) ;
78 adjlist[1].push_back(2) ;
79 adjlist[2].push_back(3) ; adjlist[2].push_back(6) ;
80 adjlist[3].push_back(4) ;
81 adjlist[4].push_back(5) ;
82 adjlist[5].push_back(6) ; adjlist[5].push_back(7) ;
83 DummyFile::createGraph (adjlist, &bs3, &f3, &s3) ;
84 g3 = new Graph (f3, *bs3, *s3) ;
85 m3 = new Matching (g3) ;
86 m3->addEdge (CREATEEDGE (g3, 1, 2)) ;
87 m3->addEdge (CREATEEDGE (g3, 3, 4)) ;
88 m3->addEdge (CREATEEDGE (g3, 5, 6)) ;
89 aph3 = new DFSAPHeuristic (g3, m3, 100.0) ;
90 gl3 = Globs ;
91 }
92
93 // this is the counterexample from Moehring's and Mueller-Hannemann's paper (Figure 3)
94 {
95 Globs.reset() ;
96 std::vector<std::list<UWORD16> > adjlist (8) ;
97 adjlist[0].push_back(1) ; adjlist[0].push_back(6) ;
98 adjlist[1].push_back(2) ; adjlist[1].push_back(7) ;
99 adjlist[2].push_back(3) ; adjlist[2].push_back(6) ;
100 adjlist[3].push_back(4) ;
101 adjlist[4].push_back(5) ;
102 adjlist[5].push_back(6) ;
103 DummyFile::createGraph (adjlist, &bs4, &f4, &s4) ;
104 g4 = new Graph (f4, *bs4, *s4) ;
105 m4 = new Matching (g4) ;
106 m4->addEdge (CREATEEDGE (g4, 1, 2)) ;
107 m4->addEdge (CREATEEDGE (g4, 3, 4)) ;
108 m4->addEdge (CREATEEDGE (g4, 5, 6)) ;
109 aph4 = new DFSAPHeuristic (g4, m4, 100.0) ;
110 gl4 = Globs ;
111 }
112
113 // another counterexample where the existing augmenting path will not be found no matter which start vertex is chosen
114 {
115 Globs.reset() ;
116 std::vector<std::list<UWORD16> > adjlist (14) ;
117 adjlist[0].push_back(2) ; adjlist[0].push_back(4) ;
118 adjlist[1].push_back(3) ; adjlist[1].push_back(5) ;
119 adjlist[2].push_back(3) ; adjlist[2].push_back(12) ;
120 adjlist[3].push_back(13) ;
121 adjlist[4].push_back(6) ; adjlist[4].push_back(12) ;
122 adjlist[5].push_back(7) ; adjlist[5].push_back(13) ;
123 adjlist[6].push_back(8) ;
124 adjlist[7].push_back(9) ;
125 adjlist[8].push_back(10) ;
126 adjlist[9].push_back(11) ;
127 adjlist[10].push_back(12) ;
128 adjlist[11].push_back(13) ;
129 DummyFile::createGraph (adjlist, &bs5, &f5, &s5) ;
130 g5 = new Graph (f5, *bs5, *s5) ;
131 m5 = new Matching (g5) ;
132 m5->addEdge (CREATEEDGE (g5, 2, 12)) ;
133 m5->addEdge (CREATEEDGE (g5, 3, 13)) ;
134 m5->addEdge (CREATEEDGE (g5, 4, 6)) ;
135 m5->addEdge (CREATEEDGE (g5, 5, 7)) ;
136 m5->addEdge (CREATEEDGE (g5, 8, 10)) ;
137 m5->addEdge (CREATEEDGE (g5, 9, 11)) ;
138 aph5 = new DFSAPHeuristic (g5, m5, 100.0) ;
139 gl5 = Globs ;
140 }
141 }
142
cleanup()143 void DFSAPHeuristicTest::cleanup ()
144 {
145 UnitTest::cleanup() ;
146
147 delete aph1 ; delete m1 ; delete g1 ; delete s1 ; delete bs1 ; delete f1 ;
148 delete aph2 ; delete m2 ; delete g2 ; delete s2 ; delete bs2 ; delete f2 ;
149 delete aph3 ; delete m3 ; delete g3 ; delete s3 ; delete bs3 ; delete f3 ;
150 delete aph4 ; delete m4 ; delete g4 ; delete s4 ; delete bs4 ; delete f4 ;
151 delete aph5 ; delete m5 ; delete g5 ; delete s5 ; delete bs5 ; delete f5 ;
152 }
153
testAlgorithm()154 void DFSAPHeuristicTest::testAlgorithm ()
155 {
156 {
157 Globs = gl1 ;
158 aph1->run() ;
159 addTestResult ( m1->isMatched((VertexLabel) 0) &&
160 m1->isMatched((VertexLabel) 1)) ;
161 }
162
163 {
164 Globs = gl2 ;
165 Edge* e01 = CREATEEDGE (g2, 0, 1) ;
166 Edge* e23 = CREATEEDGE (g2, 2, 3) ;
167 aph2->run() ;
168 addTestResult ( m2->getCardinality() == 2 &&
169 m2->includesEdge(e01) &&
170 m2->includesEdge(e23)) ;
171 }
172
173 {
174 Globs = gl3 ;
175 Edge* e01 = CREATEEDGE (g3, 0, 1) ;
176 Edge* e26 = CREATEEDGE (g3, 2, 6) ;
177 Edge* e34 = CREATEEDGE (g3, 3, 4) ;
178 Edge* e57 = CREATEEDGE (g3, 5, 7) ;
179 aph3->run() ;
180 addTestResult ( m3->getCardinality() == 4 &&
181 m3->includesEdge(e01) &&
182 m3->includesEdge(e26) &&
183 m3->includesEdge(e34) &&
184 m3->includesEdge(e57)) ;
185 }
186
187 {
188 Globs = gl4 ;
189 const Edge** path = new const Edge*[g4->getNumVertices()] ;
190 unsigned long len = aph4->searchAugmentingPath (g4->getVertex(0), path) ;
191 addTestResult (len == 0) ;
192 delete[] path ;
193 }
194
195 {
196 Globs = gl5 ;
197 Edge* e2_12 = CREATEEDGE (g5, 2, 12) ;
198 Edge* e3_13 = CREATEEDGE (g5, 3, 13) ;
199 Edge* e4_6 = CREATEEDGE (g5, 4, 6) ;
200 Edge* e5_7 = CREATEEDGE (g5, 5, 7) ;
201 Edge* e8_10 = CREATEEDGE (g5, 8, 10) ;
202 Edge* e9_11 = CREATEEDGE (g5, 9, 11) ;
203 aph5->run() ;
204 addTestResult ( m5->getCardinality() == 6 &&
205 m5->includesEdge(e2_12) &&
206 m5->includesEdge(e3_13) &&
207 m5->includesEdge(e4_6) &&
208 m5->includesEdge(e5_7) &&
209 m5->includesEdge(e8_10) &&
210 m5->includesEdge(e9_11)) ;
211 }
212 }
213