Повышение MinCut от MaxFlow

Для создания ( виртуальный) граф, который имеет только ребра с ненулевой остаточной пропускной способностью (или любым другим критерием)

Я сделал это следующим образом (в графической библиотеке LEDA есть функция, которая сделает это за вас). Я перебрал все ребра на графе и собрал все ребра, которые либо насыщены, либо имеют нулевой поток. Теперь подмножество этих ребер должно быть минимальным разрезом.

Затем я использовал gsl_combination.h для создания подмножеств этого набора. Каждое подмножество было проверено, если его значение отсечения равно максимальному потоку. Если нет, то сгенерируйте следующее подмножество, если да, то проверьте, не разобьёт ли граф удаление этих ребер на две части. Теперь ваша проблема заключается в том, как проверить, не разбивает ли удаление определенных ребер из графа граф на две части, так что одна часть имеет исходный и другой узел-приемник.

Это просто. Удалите из графа те ребра, которые заданы как возможные сечения. Создайте стек ss и поместите в него исходный узел. Теперь создайте цикл while, который завершается, когда ss пуст. Внутри цикла, pop узел из ss и получить все исходящие ребра из ss; нажмите на вершину ss target для этих ребер. Если во время итерации вы найдете узел, который равен узлу приемника, это означает, что и источник, и приемник имеют путь между ними. Поэтому это не разрез. Выкладываю фрагмент кода. Обратите внимание, что я не удаляю ребра из графа, я просто устанавливаю их поток равным 0. Я беру все ребра с нулевым потоком как ребра, удаленные из графа.

template<typename Graph>
vector<typename Graph::edge_descriptor> getMinCutWhenFlowIsGiven(
    Graph& flowG, typename Graph::vertex_descriptor src
    , typename Graph::vertex_descriptor tgt
    , unsigned flow)
{
  /* Find saturated edges */
  vector<typename Graph::edge_descriptor> possibleCutEdges;
  unsigned totalCutWeight = 0;

  /* Find all saturated or zero-flow edges. */
  for(auto e = edges(flowG); e.first != e.second; e.first++)
  {
    typename Graph::edge_descriptor ee = *e.first;
    if(flowG[ee].flow == 0 || flowG[ee].capacity - flowG[ee].flow == 0)
    {
      possibleCutEdges.push_back(ee);
      totalCutWeight += flowG[ee].flow;
      cerr << flowG[ee].flow << ",";
    }
  }
  cerr << endl;
  cerr << "[INFO] Total " << possibleCutEdges.size() << " edges." 
    << " with capacity : " << totalCutWeight 
    << " in flow-network after flow-computation." << endl;


#if  SAVE_GRAPH
  /* Save this graph. */
  write_graph(flowG, "dots/overlap.ml");
#endif     /* -----  SAVE_GRAPH  ----- */


  /*-----------------------------------------------------------------------------
   * Good, now we have a set of vertices. Generate all possible subsets of set
   * and see if any of them satisfy our need.
   *-----------------------------------------------------------------------------*/
  size_t n = possibleCutEdges.size();

  vector<typename Graph::edge_descriptor> cut;

  gsl_combination *c;
  for (size_t i = 0; i < n; i++)
  {
    c = gsl_combination_calloc (n, i);
    do
    {
      /* Check if this combination satify the max-flow condition */
      unsigned edgesFlow = 0;
      vector<typename Graph::edge_descriptor> potentialCut;
      for(size_t ii = 0; ii < c->k; ii++)
      {
        size_t elem = gsl_combination_get(c, ii);
        edgesFlow += flowG[possibleCutEdges[elem]].flow;
        potentialCut.push_back(possibleCutEdges[elem]);
      }
      if(edgesFlow == flow)
      {
        if(isCut(potentialCut, flowG, src, tgt))
          return potentialCut;  // got it!
      }
    }
    while (gsl_combination_next (c) == GSL_SUCCESS);
    gsl_combination_free (c);
  }
  return cut;
}