| 737 | |
| 738 | template <typename min_cut, typename dgraph_type> |
| 739 | void run_test_on_graphs ( |
| 740 | const min_cut& mc, |
| 741 | dgraph_type& g1, |
| 742 | dgraph_type& g2, |
| 743 | unsigned long source, |
| 744 | unsigned long sink |
| 745 | ) |
| 746 | { |
| 747 | typedef typename dgraph_type::edge_type edge_weight_type; |
| 748 | using namespace std; |
| 749 | |
| 750 | |
| 751 | dlog << LTRACE << "number of nodes: "<< g1.number_of_nodes(); |
| 752 | dlog << LTRACE << "is graph connected: "<< graph_is_connected(g1); |
| 753 | dlog << LTRACE << "has self loops: "<< graph_contains_length_one_cycle(g1); |
| 754 | dlog << LTRACE << "SOURCE_CUT: " << source; |
| 755 | dlog << LTRACE << "SINK_CUT: " << sink; |
| 756 | mc(g1, source, sink); |
| 757 | brute_force_min_cut(g2, source, sink); |
| 758 | |
| 759 | print_graph(g1); |
| 760 | |
| 761 | // make sure the flow residuals are 0 at the cut locations |
| 762 | for (unsigned long i = 0; i < g1.number_of_nodes(); ++i) |
| 763 | { |
| 764 | for (unsigned long j = 0; j < g1.node(i).number_of_children(); ++j) |
| 765 | { |
| 766 | if ((g1.node(i).data == SOURCE_CUT && g1.node(i).child(j).data != SOURCE_CUT) || |
| 767 | (g1.node(i).data != SINK_CUT && g1.node(i).child(j).data == SINK_CUT) |
| 768 | ) |
| 769 | { |
| 770 | DLIB_TEST_MSG(g1.node(i).child_edge(j) == 0, g1.node(i).child_edge(j)); |
| 771 | } |
| 772 | } |
| 773 | } |
| 774 | |
| 775 | // copy the edge weights from g2 back to g1 so we can compute cut scores |
| 776 | copy_edge_weights(g1, g2); |
| 777 | |
| 778 | DLIB_TEST(g1.number_of_nodes() == g2.number_of_nodes()); |
| 779 | for (unsigned long i = 0; i < g1.number_of_nodes(); ++i) |
| 780 | { |
| 781 | dlog << LTRACE << "node " << i << ": " << (int)g1.node(i).data << ", " << (int)g2.node(i).data; |
| 782 | if (g1.node(i).data != g2.node(i).data) |
| 783 | { |
| 784 | edge_weight_type cut_score = graph_cut_score(g1); |
| 785 | edge_weight_type brute_force_score = graph_cut_score(g2); |
| 786 | dlog << LTRACE << "graph cut score: "<< cut_score; |
| 787 | dlog << LTRACE << "brute force score: "<< brute_force_score; |
| 788 | |
| 789 | if (brute_force_score != cut_score) |
| 790 | print_graph(g1); |
| 791 | DLIB_TEST_MSG(brute_force_score == cut_score,std::abs(brute_force_score-cut_score)); |
| 792 | } |
| 793 | } |
| 794 | |
| 795 | } |
| 796 |
no test coverage detected