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> |
10 | #include <boost/core/lightweight_test.hpp> |
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 | |
20 | struct coord_t |
21 | { |
22 | std::size_t x; |
23 | std::size_t y; |
24 | }; |
25 | |
26 | int main(int, char*[]) |
27 | { |
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(u: 0, v: 1, g_&: g); |
40 | add_edge(u: 2, v: 3, g_&: g); |
41 | |
42 | drawing_storage_t drawing_storage(num_vertices(g_: g)); |
43 | drawing_t drawing(drawing_storage.begin(), get(p: 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(u: 0, v: 1, g_&: g); |
92 | add_edge(u: 0, v: 2, g_&: g); |
93 | add_edge(u: 0, v: 3, g_&: g); |
94 | add_edge(u: 1, v: 2, g_&: g); |
95 | add_edge(u: 1, v: 3, g_&: g); |
96 | add_edge(u: 2, v: 3, g_&: g); |
97 | |
98 | drawing_storage = drawing_storage_t(num_vertices(g_: g)); |
99 | drawing = drawing_t(drawing_storage.begin(), get(p: 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(u: 0, v: 1, g_&: g); |
128 | add_edge(u: 2, v: 3, g_&: g); |
129 | add_edge(u: 4, v: 5, g_&: g); |
130 | add_edge(u: 6, v: 7, g_&: g); |
131 | |
132 | drawing_storage = drawing_storage_t(num_vertices(g_: g)); |
133 | drawing = drawing_t(drawing_storage.begin(), get(p: 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(u: 2 * i, v: 2 * i + 1, g_&: g); |
159 | |
160 | drawing_storage = drawing_storage_t(num_vertices(g_: g)); |
161 | drawing = drawing_t(drawing_storage.begin(), get(p: vertex_index, g)); |
162 | |
163 | for (int i = 0; i < 10; ++i) |
164 | { |
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; |
169 | } |
170 | |
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; |
176 | |
177 | BOOST_TEST(!is_straight_line_drawing(g, drawing)); |
178 | |
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; |
184 | |
185 | BOOST_TEST(!is_straight_line_drawing(g, drawing)); |
186 | |
187 | // reverse the slope |
188 | drawing[20].x = 2; |
189 | drawing[20].y = 7; |
190 | drawing[21].x = 9; |
191 | drawing[21].y = 4; |
192 | |
193 | BOOST_TEST(!is_straight_line_drawing(g, drawing)); |
194 | |
195 | return boost::report_errors(); |
196 | } |
197 | |