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

Function brute_force_min_cut

dlib/test/graph_cuts.cpp:515–555  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

513
514 template <typename directed_graph>
515 void brute_force_min_cut (
516 directed_graph& g,
517 unsigned long source,
518 unsigned long sink
519 )
520 {
521 typedef typename directed_graph::edge_type edge_weight_type;
522 const unsigned long num = (unsigned long)std::pow(2.0, (double)g.number_of_nodes());
523
524 std::vector<node_label> best_cut(g.number_of_nodes(),FREE_NODE);
525
526 edge_weight_type best_score = std::numeric_limits<edge_weight_type>::max();
527 for (unsigned long i = 0; i < num; ++i)
528 {
529 for (unsigned long j = 0; j < g.number_of_nodes(); ++j)
530 {
531 unsigned long T = (1)<<j;
532 T = (T&i);
533 if (T != 0)
534 g.node(j).data = SINK_CUT;
535 else
536 g.node(j).data = SOURCE_CUT;
537 }
538
539 // ignore cuts that don't label the source or sink node the way we want.
540 if (g.node(source).data != SOURCE_CUT ||
541 g.node(sink).data != SINK_CUT)
542 continue;
543
544 edge_weight_type score = graph_cut_score(g);
545 if (score < best_score)
546 {
547 best_score = score;
548 for (unsigned long j = 0; j < g.number_of_nodes(); ++j)
549 best_cut[j] = g.node(j).data;
550 }
551 }
552
553 for (unsigned long j = 0; j < g.number_of_nodes(); ++j)
554 g.node(j).data = best_cut[j];
555 }
556
557// ----------------------------------------------------------------------------------------
558

Callers 1

run_test_on_graphsFunction · 0.85

Calls 3

graph_cut_scoreFunction · 0.85
maxFunction · 0.50
number_of_nodesMethod · 0.45

Tested by

no test coverage detected