]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 2008 Aaron Windsor | |
3 | // | |
4 | // Distributed under the Boost Software License, Version 1.0. (See | |
5 | // accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | //======================================================================= | |
8 | ||
9 | #include <boost/property_map/property_map.hpp> | |
f67539c2 | 10 | #include <boost/core/lightweight_test.hpp> |
7c673cae FG |
11 | #include <boost/graph/adjacency_list.hpp> |
12 | #include <boost/graph/properties.hpp> | |
13 | #include <boost/graph/graph_traits.hpp> | |
14 | #include <boost/graph/is_straight_line_drawing.hpp> | |
15 | ||
16 | #include <vector> | |
17 | ||
18 | using namespace boost; | |
19 | ||
f67539c2 | 20 | struct coord_t |
7c673cae | 21 | { |
f67539c2 TL |
22 | std::size_t x; |
23 | std::size_t y; | |
7c673cae FG |
24 | }; |
25 | ||
f67539c2 | 26 | int main(int, char*[]) |
7c673cae | 27 | { |
f67539c2 TL |
28 | typedef adjacency_list< vecS, vecS, undirectedS, |
29 | property< vertex_index_t, int > > | |
30 | graph_t; | |
31 | ||
32 | typedef std::vector< coord_t > drawing_storage_t; | |
33 | ||
34 | typedef boost::iterator_property_map< drawing_storage_t::iterator, | |
35 | property_map< graph_t, vertex_index_t >::type > | |
36 | drawing_t; | |
37 | ||
38 | graph_t g(4); | |
39 | add_edge(0, 1, g); | |
40 | add_edge(2, 3, g); | |
41 | ||
42 | drawing_storage_t drawing_storage(num_vertices(g)); | |
43 | drawing_t drawing(drawing_storage.begin(), get(vertex_index, g)); | |
44 | ||
45 | // two perpendicular lines that intersect at (1,1) | |
46 | drawing[0].x = 1; | |
47 | drawing[0].y = 0; | |
48 | drawing[1].x = 1; | |
49 | drawing[1].y = 2; | |
50 | drawing[2].x = 0; | |
51 | drawing[2].y = 1; | |
52 | drawing[3].x = 2; | |
53 | drawing[3].y = 1; | |
54 | ||
55 | BOOST_TEST(!is_straight_line_drawing(g, drawing)); | |
56 | ||
57 | // two parallel horizontal lines | |
58 | drawing[0].x = 0; | |
59 | drawing[0].y = 0; | |
60 | drawing[1].x = 2; | |
61 | drawing[1].y = 0; | |
62 | ||
63 | BOOST_TEST(is_straight_line_drawing(g, drawing)); | |
64 | ||
65 | // two parallel vertical lines | |
66 | drawing[0].x = 0; | |
67 | drawing[0].y = 0; | |
68 | drawing[1].x = 0; | |
69 | drawing[1].y = 2; | |
70 | drawing[2].x = 1; | |
71 | drawing[2].y = 0; | |
72 | drawing[3].x = 1; | |
73 | drawing[3].y = 2; | |
74 | ||
75 | BOOST_TEST(is_straight_line_drawing(g, drawing)); | |
76 | ||
77 | // two lines that intersect at (1,1) | |
78 | drawing[0].x = 0; | |
79 | drawing[0].y = 0; | |
80 | drawing[1].x = 2; | |
81 | drawing[1].y = 2; | |
82 | drawing[2].x = 0; | |
83 | drawing[2].y = 2; | |
84 | drawing[3].x = 2; | |
85 | drawing[3].y = 0; | |
86 | ||
87 | BOOST_TEST(!is_straight_line_drawing(g, drawing)); | |
88 | ||
89 | // K_4 arranged in a diamond pattern, so that edges intersect | |
90 | g = graph_t(4); | |
91 | add_edge(0, 1, g); | |
92 | add_edge(0, 2, g); | |
93 | add_edge(0, 3, g); | |
94 | add_edge(1, 2, g); | |
95 | add_edge(1, 3, g); | |
96 | add_edge(2, 3, g); | |
97 | ||
98 | drawing_storage = drawing_storage_t(num_vertices(g)); | |
99 | drawing = drawing_t(drawing_storage.begin(), get(vertex_index, g)); | |
100 | ||
101 | drawing[0].x = 1; | |
102 | drawing[0].y = 2; | |
103 | drawing[1].x = 2; | |
104 | drawing[1].y = 1; | |
105 | drawing[2].x = 1; | |
106 | drawing[2].y = 0; | |
107 | drawing[3].x = 0; | |
108 | drawing[3].y = 1; | |
109 | ||
110 | BOOST_TEST(!is_straight_line_drawing(g, drawing)); | |
111 | ||
112 | // K_4 arranged so that no edges intersect | |
113 | drawing[0].x = 0; | |
114 | drawing[0].y = 0; | |
115 | drawing[1].x = 1; | |
116 | drawing[1].y = 1; | |
117 | drawing[2].x = 1; | |
118 | drawing[2].y = 2; | |
119 | drawing[3].x = 2; | |
120 | drawing[3].y = 0; | |
121 | ||
122 | BOOST_TEST(is_straight_line_drawing(g, drawing)); | |
123 | ||
124 | // a slightly more complicated example - edges (0,1) and (4,5) | |
125 | // intersect | |
126 | g = graph_t(8); | |
127 | add_edge(0, 1, g); | |
128 | add_edge(2, 3, g); | |
129 | add_edge(4, 5, g); | |
130 | add_edge(6, 7, g); | |
131 | ||
132 | drawing_storage = drawing_storage_t(num_vertices(g)); | |
133 | drawing = drawing_t(drawing_storage.begin(), get(vertex_index, g)); | |
134 | ||
135 | drawing[0].x = 1; | |
136 | drawing[0].y = 1; | |
137 | drawing[1].x = 5; | |
138 | drawing[1].y = 4; | |
139 | drawing[2].x = 2; | |
140 | drawing[2].y = 5; | |
141 | drawing[3].x = 4; | |
142 | drawing[3].y = 4; | |
143 | drawing[4].x = 3; | |
144 | drawing[4].y = 4; | |
145 | drawing[5].x = 3; | |
146 | drawing[5].y = 2; | |
147 | drawing[6].x = 4; | |
148 | drawing[6].y = 2; | |
149 | drawing[7].x = 1; | |
150 | drawing[7].y = 1; | |
151 | ||
152 | BOOST_TEST(!is_straight_line_drawing(g, drawing)); | |
153 | ||
154 | // form a graph consisting of a bunch of parallel vertical edges, | |
155 | // then place an edge at various positions to intersect edges | |
156 | g = graph_t(22); | |
157 | for (int i = 0; i < 11; ++i) | |
158 | add_edge(2 * i, 2 * i + 1, g); | |
159 | ||
160 | drawing_storage = drawing_storage_t(num_vertices(g)); | |
161 | drawing = drawing_t(drawing_storage.begin(), get(vertex_index, g)); | |
162 | ||
163 | for (int i = 0; i < 10; ++i) | |
7c673cae | 164 | { |
f67539c2 TL |
165 | drawing[2 * i].x = i; |
166 | drawing[2 * i].y = 0; | |
167 | drawing[2 * i + 1].x = i; | |
168 | drawing[2 * i + 1].y = 10; | |
7c673cae | 169 | } |
7c673cae | 170 | |
f67539c2 TL |
171 | // put the final edge as a horizontal edge intersecting one other edge |
172 | drawing[20].x = 5; | |
173 | drawing[20].y = 5; | |
174 | drawing[21].x = 7; | |
175 | drawing[21].y = 5; | |
7c673cae | 176 | |
f67539c2 | 177 | BOOST_TEST(!is_straight_line_drawing(g, drawing)); |
7c673cae | 178 | |
f67539c2 TL |
179 | // make the final edge a diagonal intersecting multiple edges |
180 | drawing[20].x = 2; | |
181 | drawing[20].y = 4; | |
182 | drawing[21].x = 9; | |
183 | drawing[21].y = 7; | |
7c673cae | 184 | |
f67539c2 | 185 | BOOST_TEST(!is_straight_line_drawing(g, drawing)); |
7c673cae | 186 | |
f67539c2 TL |
187 | // reverse the slope |
188 | drawing[20].x = 2; | |
189 | drawing[20].y = 7; | |
190 | drawing[21].x = 9; | |
191 | drawing[21].y = 4; | |
7c673cae | 192 | |
f67539c2 | 193 | BOOST_TEST(!is_straight_line_drawing(g, drawing)); |
7c673cae | 194 | |
f67539c2 TL |
195 | return boost::report_errors(); |
196 | } |