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
main(int,char * [])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(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)
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