MCPcopy Create free account
hub / github.com/davisking/dlib / run_test_on_graphs

Function run_test_on_graphs

dlib/test/graph_cuts.cpp:739–795  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

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

Callers 1

test_graph_cutsFunction · 0.85

Calls 9

graph_is_connectedFunction · 0.85
brute_force_min_cutFunction · 0.85
print_graphFunction · 0.85
copy_edge_weightsFunction · 0.85
graph_cut_scoreFunction · 0.85
absFunction · 0.85
number_of_childrenMethod · 0.80
number_of_nodesMethod · 0.45

Tested by

no test coverage detected