| 955 | typename join_tree_type |
| 956 | > |
| 957 | void create_join_tree ( |
| 958 | const graph_type& g, |
| 959 | join_tree_type& join_tree |
| 960 | ) |
| 961 | { |
| 962 | // make sure requires clause is not broken |
| 963 | DLIB_ASSERT(graph_contains_length_one_cycle(g) == false, |
| 964 | "\tvoid create_join_tree(g, join_tree)" |
| 965 | << "\n\tInvalid graph" |
| 966 | ); |
| 967 | DLIB_ASSERT(graph_is_connected(g) == true, |
| 968 | "\tvoid create_join_tree(g, join_tree)" |
| 969 | << "\n\tInvalid graph" |
| 970 | ); |
| 971 | |
| 972 | COMPILE_TIME_ASSERT(is_graph<graph_type>::value); |
| 973 | COMPILE_TIME_ASSERT(is_graph<join_tree_type>::value); |
| 974 | |
| 975 | |
| 976 | |
| 977 | typedef typename join_tree_type::type set_of_int; |
| 978 | typedef typename join_tree_type::edge_type set_of_int_edge; |
| 979 | typedef typename set<set_of_int>::kernel_1b_c set_of_sets_of_int; |
| 980 | |
| 981 | copy_graph_structure(g, join_tree); |
| 982 | |
| 983 | // don't even bother in this case |
| 984 | if (g.number_of_nodes() == 0) |
| 985 | return; |
| 986 | |
| 987 | set_of_sets_of_int cliques; |
| 988 | set_of_int s; |
| 989 | |
| 990 | triangulate_graph_and_find_cliques(join_tree, cliques); |
| 991 | |
| 992 | join_tree.set_number_of_nodes(cliques.size()); |
| 993 | |
| 994 | // copy the cliques into each of the nodes of tree |
| 995 | for (unsigned long i = 0; i < join_tree.number_of_nodes(); ++i) |
| 996 | { |
| 997 | cliques.remove_any(s); |
| 998 | s.swap(join_tree.node(i).data); |
| 999 | } |
| 1000 | |
| 1001 | set_of_int_edge e; |
| 1002 | |
| 1003 | // add all possible edges to the join_tree |
| 1004 | for (unsigned long i = 0; i < join_tree.number_of_nodes(); ++i) |
| 1005 | { |
| 1006 | for (unsigned long j = i+1; j < join_tree.number_of_nodes(); ++j) |
| 1007 | { |
| 1008 | set_intersection( |
| 1009 | join_tree.node(i).data, |
| 1010 | join_tree.node(j).data, |
| 1011 | e); |
| 1012 | |
| 1013 | if (e.size() > 0) |
| 1014 | { |