| 1149 | typename join_tree_type |
| 1150 | > |
| 1151 | bool is_join_tree ( |
| 1152 | const graph_type& g, |
| 1153 | const join_tree_type& join_tree |
| 1154 | ) |
| 1155 | { |
| 1156 | |
| 1157 | // make sure requires clause is not broken |
| 1158 | DLIB_ASSERT(graph_contains_length_one_cycle(g) == false, |
| 1159 | "\tvoid create_join_tree(g, join_tree)" |
| 1160 | << "\n\tInvalid graph" |
| 1161 | ); |
| 1162 | DLIB_ASSERT(graph_is_connected(g) == true, |
| 1163 | "\tvoid create_join_tree(g, join_tree)" |
| 1164 | << "\n\tInvalid graph" |
| 1165 | ); |
| 1166 | |
| 1167 | COMPILE_TIME_ASSERT(is_graph<graph_type>::value || is_directed_graph<graph_type>::value); |
| 1168 | COMPILE_TIME_ASSERT(is_graph<join_tree_type>::value); |
| 1169 | |
| 1170 | |
| 1171 | if (graph_contains_undirected_cycle(join_tree)) |
| 1172 | return false; |
| 1173 | |
| 1174 | if (graph_is_connected(join_tree) == false) |
| 1175 | return false; |
| 1176 | |
| 1177 | // verify that the path condition of the join tree is valid |
| 1178 | for (unsigned long i = 0; i < join_tree.number_of_nodes(); ++i) |
| 1179 | { |
| 1180 | typename join_tree_type::type deads; |
| 1181 | if (graph_helpers::validate_join_tree(join_tree.node(i), deads) == false) |
| 1182 | return false; |
| 1183 | } |
| 1184 | |
| 1185 | typename join_tree_type::edge_type e; |
| 1186 | typename join_tree_type::edge_type all; |
| 1187 | // now make sure that the edges contain correct intersections |
| 1188 | for (unsigned long i = 0; i < join_tree.number_of_nodes(); ++i) |
| 1189 | { |
| 1190 | set_union(all,join_tree.node(i).data, all); |
| 1191 | for (unsigned long j = 0; j < join_tree.node(i).number_of_neighbors(); ++j) |
| 1192 | { |
| 1193 | set_intersection(join_tree.node(i).data, |
| 1194 | join_tree.node(i).neighbor(j).data, |
| 1195 | e); |
| 1196 | |
| 1197 | if (!(e == join_tree.node(i).edge(j))) |
| 1198 | return false; |
| 1199 | } |
| 1200 | } |
| 1201 | |
| 1202 | // and finally check that all the nodes in g show up in the join tree |
| 1203 | if (all.size() != g.number_of_nodes()) |
| 1204 | return false; |
| 1205 | all.reset(); |
| 1206 | while (all.move_next()) |
| 1207 | { |
| 1208 | if (all.element() >= g.number_of_nodes()) |