| 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 |
no test coverage detected