Правильно ли это код Sedgewick? - программирование

Я решаю проблему оптимизации, в которой, среди прочего, я должен максимизировать потоковые сети. Я реализовал алгоритм максимизации потока на основе кода С++, основанный на следующем Java-коде, который содержится в книге Sedgewick "Алгоритмы в Java, третье издание, часть 5: Алгоритмы графа", который максимизирует сетевой поток используя алгоритм PREFLOW-push на основе вершины:

class NetworkMaxFlow
{ private Network G; private int s, t;
  private int[] h, wt;
  private void initheights()
  NetworkMaxFlow(Network G, int s, int t)
  { this.G = G; this.s = s; this.t = t;
    wt = new int[G.V()]; h = new int[G.V()];
    initheights();
    intGQ gQ = new intGQ(G.V());
    gQ.put(s); wt[t] = -(wt[s] = Edge.M*G.V());
    while (!gQ.empty())
    { int v = gQ.get();
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt())
        { int w = e.other(v), cap = e.capRto(w);
          int P = cap < wt[v] ? cap : wt[v];
          if (P > 0 && v == s || h[v] == h[w]+1) // first observation (see below)
            { e.addflowRto(w, P);
              wt[v] -= P; wt[w] += P;
              if ((w != s) && (w != t)) gQ.put(w); // enqueue w if it is not source or sink
            }
        }
      if (v != s && v != t && wt[v] > 0) // why check v != t if t never enter the queue?
        { h[v]++; gQ.put(v); }
    }
  }
}

Моя реализация, основанная на этом коде, не позволяет максимизировать следующую сеть После выполнения результирующий поток выглядит следующим образом При этом потоке значение потока равно 8, но максимум равно 9, что указано потоком на рисунке ниже По моему мнению, алгоритм согласуется с объяснением книги. Однако я вижу две странные вещи

Не существует явной фазы предварительного потока из исходного кода. Он включен в while и выполняется первым и только один раз, когда предикат P > 0 && v == s равен true. Возможно, это было сделано для сокращения кода
В соответствии с моим пониманием и дискурсом книги раковина никогда не входит в очередь. Однако, когда высота увеличивается, код проверяет, что v!= T. Любая причина для этого?

Это выдержка из моей реализации этого алгоритма в С++

template <class Net, class Q_Type> typename Net::Flow_Type
generic_preflow_vertex_push_maximum_flow(Net & net)
{
  init_height_in_nodes(net); // breadth first traverse from sink to
                 // source. Nodes are labeled with their
                 // minimal distance (in nodes) to sink
  auto source = net.get_source();
  auto sink   = net.get_sink();

  using Itor = __Net_Iterator<Net>;
  Q_Type q; // generic queue (can be fifo, heap or random) of active nodes

  // preflow: floods all nodes connected to the source 
  for (Itor it(source); it.has_curr(); it.next()) 
    {
      auto arc  = it.get_curr();  
      arc->flow = arc->cap; // saturate arc to its maximum 
      auto tgt = net.get_tgt_node(arc);
      put_in_active_queue(q, tgt);
      assert(node_height<Net>(source) == node_height<Net>(tgt) + 1);
      assert(not is_residual<Net>(source, arc));
    }

  while (not q.is_empty()) // while there are active nodes
    {
      auto src = get_from_active_queue(q);
      auto excess = net.get_in_flow(src) - net.get_out_flow(src);

      for (Itor it(src); it.has_curr(); it.next()) 
        {
          auto arc = it.get_curr();
          auto tgt = net.get_connected_node(arc, src);

          if (node_height<Net>(src) != node_height<Net>(tgt) + 1)
            continue; // this arc is not eligible

          typename Net::Flow_Type flow_to_push;
          if (is_residual<Net>(src, arc))
            {
              flow_to_push = std::min(arc->flow, excess);
              arc->flow -= flow_to_push;
            }
          else
            {
              flow_to_push = std::min(arc->cap - arc->flow, excess);
              arc->flow += flow_to_push;
            }

          excess -= flow_to_push;
          if (tgt != sink and tgt != source)
            put_in_active_queue(q, tgt);
        }

    if (excess > 0) // src still active?
      { 
        node_height<Net>(src)++;
        put_in_active_queue(q, src);
      }
  }

  return net.flow_value(); // sum of all outing flow from source
}

¿Кто-то находит логическую несогласованность между моим кодом и кодом Sedgewick? У меня сложилось впечатление, что мой код (и, возможно, также Sedgewick) неправильно обрабатывает увеличение высоты. Но я не понимаю, почему

Я показываю подробную трассировку выполнения с сетью, которая не может максимизировать (трассировка начинается с первого q.get() while. Значения в круглых скобках являются значениями высот. IN - это входящий поток в node OUT out out.

В качестве примера, строка

    4104 (2) --> 0 (1) pushing 1 from 4104 toward 0

обозначает подходящую дугу 4104 → 0. node 4104 имеет высоту 2, а node 0 имеет высоту 1. Выражение "нажатие 1" означает, что 1 единство потока сдвигается к цели node (0). Строка ================ разделяет выделение каждой очереди. Очередь - это FIFO, и ее состояние печатается в конце каждой обработки.

Обратите внимание, что многократно нулевые единицы расхода толкаются или уменьшаются, но пункт назначения node становится активным.

Это трассировка выполнения

Initial Queue = 4104 4105 4106 4107 4108

Active node 4104 Height = 2 IN = 1 OUT = 0
    4104 (2) --> source (3) not eligible
    4104 (2) --> 0 (1) pushing 1 from 4104 toward 0
    4104 (2) --> 1 (1) pushing 0 from 4104 toward 1
    4104 (2) --> 2 (1) pushing 0 from 4104 toward 2
    4104 (2) --> 4 (1) pushing 0 from 4104 toward 4
    Excess = 0
    Queue = 4105 4106 4107 4108 0 1 2 4
================
Active node 4105 Height = 2 IN = 3 OUT = 0
    4105 (2) --> source (3) not eligible
    4105 (2) --> 1 (1) pushing 1 from 4105 toward 1
    4105 (2) --> 4 (1) pushing 1 from 4105 toward 4
    4105 (2) --> 6 (1) pushing 1 from 4105 toward 6
    Excess = 0
    Queue = 4106 4107 4108 0 1 2 4 6
================
Active node 4106 Height = 2 IN = 1 OUT = 0
    4106 (2) --> source (3) not eligible
    4106 (2) --> 1 (1) pushing 1 from 4106 toward 1
    4106 (2) --> 5 (1) pushing 0 from 4106 toward 5
    Excess = 0
    Queue = 4107 4108 0 1 2 4 6 5
================
Active node 4107 Height = 2 IN = 1 OUT = 0
    4107 (2) --> source (3) not eligible
    4107 (2) --> 1 (1) pushing 1 from 4107 toward 1
    4107 (2) --> 2 (1) pushing 0 from 4107 toward 2
    4107 (2) --> 3 (1) pushing 0 from 4107 toward 3
    4107 (2) --> 4 (1) pushing 0 from 4107 toward 4
    4107 (2) --> 6 (1) pushing 0 from 4107 toward 6
    Excess = 0
    Queue = 4108 0 1 2 4 6 5 3
================
Active node 4108 Height = 2 IN = 3 OUT = 0
    4108 (2) --> source (3) not eligible
    4108 (2) --> 1 (1) pushing 1 from 4108 toward 1
    4108 (2) --> 2 (1) pushing 1 from 4108 toward 2
    4108 (2) --> 4 (1) pushing 1 from 4108 toward 4
    4108 (2) --> 5 (1) pushing 0 from 4108 toward 5
    4108 (2) --> 6 (1) pushing 0 from 4108 toward 6
    Excess = 0
    Queue = 0 1 2 4 6 5 3
================
Active node 0 Height = 1 IN = 1 OUT = 0
    0 (1) --> sink (0) pushing 1 from 0 toward sink
    0 (1) --> 4104 (2) not eligible
    Excess = 0
    Queue = 1 2 4 6 5 3
================
Active node 1 Height = 1 IN = 4 OUT = 0
    1 (1) --> sink (0) pushing 2 from 1 toward sink
    1 (1) --> 4105 (2) not eligible
    1 (1) --> 4106 (2) not eligible
    1 (1) --> 4107 (2) not eligible
    1 (1) --> 4108 (2) not eligible
    Excess = 2    1 goes back onto queue with label 2
    Queue = 2 4 6 5 3 1
================
Active node 2 Height = 1 IN = 1 OUT = 0
    2 (1) --> sink (0) pushing 1 from 2 toward sink
    2 (1) --> 4108 (2) not eligible
    Excess = 0
    Queue = 4 6 5 3 1
================
Active node 4 Height = 1 IN = 2 OUT = 0
    4 (1) --> sink (0) pushing 2 from 4 toward sink
    4 (1) --> 4105 (2) not eligible
    4 (1) --> 4108 (2) not eligible
    Excess = 0
    Queue = 6 5 3 1
================
Active node 6 Height = 1 IN = 1 OUT = 0
    6 (1) --> sink (0) pushing 1 from 6 toward sink
    6 (1) --> 4105 (2) not eligible
    Excess = 0
    Queue = 5 3 1
================
Active node 5 Height = 1 IN = 0 OUT = 0
    5 (1) --> sink (0) pushing 0 from 5 toward sink
    Excess = 0
    Queue = 3 1
================
Active node 3 Height = 1 IN = 0 OUT = 0
    3 (1) --> sink (0) pushing 0 from 3 toward sink
    Excess = 0
    Queue = 1
================
Active node 1 Height = 2 IN = 4 OUT = 2
    1 (2) --> 4105 (2) not eligible
    1 (2) --> 4106 (2) not eligible
    1 (2) --> 4107 (2) not eligible
    1 (2) --> 4108 (2) not eligible
    Excess = 2    1 goes back onto queue with label 3
    Queue = 1
================
Active node 1 Height = 3 IN = 4 OUT = 2
    1 (3) --> 4105 (2) Reducing 1 from 1 toward 4105
    1 (3) --> 4106 (2) Reducing 1 from 1 toward 4106
    1 (3) --> 4107 (2) Reducing 0 from 1 toward 4107
    1 (3) --> 4108 (2) Reducing 0 from 1 toward 4108
    Excess = 0
    Queue = 4105 4106 4107 4108
================
Active node 4105 Height = 2 IN = 3 OUT = 2
    4105 (2) --> source (3) not eligible
    4105 (2) --> 1 (3) not eligible
    Excess = 1    4105 goes back onto queue with label 3
    Queue = 4106 4107 4108 4105
================
Active node 4106 Height = 2 IN = 1 OUT = 0
    4106 (2) --> source (3) not eligible
    4106 (2) --> 1 (3) not eligible
    4106 (2) --> 5 (1) pushing 1 from 4106 toward 5
    Excess = 0
    Queue = 4107 4108 4105 5
================
Active node 4107 Height = 2 IN = 1 OUT = 1
    4107 (2) --> source (3) not eligible
    4107 (2) --> 2 (1) pushing 0 from 4107 toward 2
    4107 (2) --> 3 (1) pushing 0 from 4107 toward 3
    4107 (2) --> 4 (1) pushing 0 from 4107 toward 4
    4107 (2) --> 6 (1) pushing 0 from 4107 toward 6
    Excess = 0
    Queue = 4108 4105 5 2 3 4 6
================
Active node 4108 Height = 2 IN = 3 OUT = 3
    4108 (2) --> source (3) not eligible
    4108 (2) --> 5 (1) pushing 0 from 4108 toward 5
    4108 (2) --> 6 (1) pushing 0 from 4108 toward 6
    Excess = 0
    Queue = 4105 5 2 3 4 6
================
Active node 4105 Height = 3 IN = 3 OUT = 2
    4105 (3) --> source (3) not eligible
    4105 (3) --> 1 (3) not eligible
    Excess = 1    4105 goes back onto queue with label 4
    Queue = 5 2 3 4 6 4105
================
Active node 5 Height = 1 IN = 1 OUT = 0
    5 (1) --> sink (0) pushing 1 from 5 toward sink
    5 (1) --> 4106 (2) not eligible
    Excess = 0
    Queue = 2 3 4 6 4105
================
Active node 2 Height = 1 IN = 1 OUT = 1
    2 (1) --> sink (0) pushing 0 from 2 toward sink
    2 (1) --> 4108 (2) not eligible
    Excess = 0
    Queue = 3 4 6 4105
================
Active node 3 Height = 1 IN = 0 OUT = 0
    3 (1) --> sink (0) pushing 0 from 3 toward sink
    Excess = 0
    Queue = 4 6 4105
================
Active node 4 Height = 1 IN = 2 OUT = 2
    4 (1) --> 4105 (4) not eligible
    4 (1) --> 4108 (2) not eligible
    Excess = 0
    Queue = 6 4105
================
Active node 6 Height = 1 IN = 1 OUT = 1
    6 (1) --> sink (0) pushing 0 from 6 toward sink
    6 (1) --> 4105 (4) not eligible
    Excess = 0
    Queue = 4105
================
Active node 4105 Height = 4 IN = 3 OUT = 2
    4105 (4) --> source (3) Reducing 1 from 4105 toward source
    4105 (4) --> 1 (3) pushing 0 from 4105 toward 1
    Excess = 0
    Queue = 1
================
Active node 1 Height = 3 IN = 2 OUT = 2
    1 (3) --> 4107 (2) Reducing 0 from 1 toward 4107
    1 (3) --> 4108 (2) Reducing 0 from 1 toward 4108
    Excess = 0
    Queue = 4107 4108
================
Active node 4107 Height = 2 IN = 1 OUT = 1
    4107 (2) --> source (3) not eligible
    4107 (2) --> 2 (1) pushing 0 from 4107 toward 2
    4107 (2) --> 3 (1) pushing 0 from 4107 toward 3
    4107 (2) --> 4 (1) pushing 0 from 4107 toward 4
    4107 (2) --> 6 (1) pushing 0 from 4107 toward 6
    Excess = 0
    Queue = 4108 2 3 4 6
================
Active node 4108 Height = 2 IN = 3 OUT = 3
    4108 (2) --> source (3) not eligible
    4108 (2) --> 5 (1) pushing 0 from 4108 toward 5
    4108 (2) --> 6 (1) pushing 0 from 4108 toward 6
    Excess = 0
    Queue = 2 3 4 6 5
================
Active node 2 Height = 1 IN = 1 OUT = 1
    2 (1) --> sink (0) pushing 0 from 2 toward sink
    2 (1) --> 4108 (2) not eligible
    Excess = 0
    Queue = 3 4 6 5
================
Active node 3 Height = 1 IN = 0 OUT = 0
    3 (1) --> sink (0) pushing 0 from 3 toward sink
    Excess = 0
    Queue = 4 6 5
================
Active node 4 Height = 1 IN = 2 OUT = 2
    4 (1) --> 4105 (4) not eligible
    4 (1) --> 4108 (2) not eligible
    Excess = 0
    Queue = 6 5
================
Active node 6 Height = 1 IN = 1 OUT = 1
    6 (1) --> sink (0) pushing 0 from 6 toward sink
    6 (1) --> 4105 (4) not eligible
    Excess = 0
    Queue = 5
================
Active node 5 Height = 1 IN = 1 OUT = 1
    5 (1) --> sink (0) pushing 0 from 5 toward sink
    5 (1) --> 4106 (2) not eligible
    Excess = 0
    Queue =

Ответ 1

Ваши вопросы

предварительной подачи

Нет явной фазы предварительного потока от source. Он включен в while и выполняется первым и только один раз, когда предикат P > 0 && v == s равен true. Возможно, это было сделано для сокращения кода

Да, я думаю, что это было сделано для уплотнения кода. В связи с назначением wt[s] = Edge.M*G.V() в начале источник имеет достаточно "виртуального" избытка, чтобы подогревать превенцию в первой итерации алгоритма. Если вы хотите сделать тот же трюк в своей реализации, вам придется раздуть переменную excess (которую вы вычисляете "на лету" вместо того, чтобы хранить ее в массиве вроде Sedgewick) во время первой итерации, когда вы сталкиваетесь с источником node. Но вам не нужно так поступать, ваше явное предтопление кажется просто прекрасным и, вероятно, даже делает вещи более читабельными.

Я также подозреваю, что в условии P > 0 && v == s || h[v] == h[w]+1 неявный приоритет оператора (P > 0 && v == s) || h[v] == h[w]+1 не был предназначен. Как это записано, проверка P > 0 выполняется только для исходного кода. Не проверять его в других случаях не повредит, потому что выполнение тела с помощью P == 0 просто приведет к избытку 0 к другим узлам (что ничего не делает) и излишне добавит эти другие узлы в очередь, только для них немедленно удалить. Я видел, что вы реализовали его таким же образом. Это нормально, хотя и небольшая потеря вычислительного времени. Вероятно, P > 0 && (v == s || h[v] == h[w]+1) был действительно предназначен.

Поместить в очередь

Согласно моему пониманию и дискурсу книги, раковина никогда не входит в очередь. Однако, когда высота увеличивается, код проверяет, что v!= T. Любая причина для этого?

Я согласен, это странно. Единственный способ, по которому приемник может войти в очередь, является источником одновременно (на графике только с одним node и без ребер). Однако в этом случае условие v != s уже избегает бесконечного цикла, не требует дополнительного условия.

Неверные результаты

После выполнения результирующий поток выглядит следующим образом [...] При этом потоке значение потока равно 8, но максимум равно 9

Начальные высоты

Вы получаете неправильные результаты, потому что ваши первоначальные высоты ошибочны. Я не могу сравнить код инициализации Sedgewick с вашим, потому что ваше сообщение также не указывает. Но я узнаю из вашего файла журнала, что вы начинаете с высоты 3 для source. Это явно против условий для функций высоты: source должен начинаться с высоты, равной количеству узлов в вашем графике и будет хранить его во время всего алгоритма.

В вашем случае высота source слишком близко к высоте его соседних по течению соседей. Это приводит к тому, что соседи по нисходящему потоку немного ускоряют поток обратно к источнику, прежде чем пытаться достаточно сильно, чтобы позволить ему двигаться дальше по течению. Они должны делать это только в том случае, если нет возможности допустить, чтобы он стекал к раковине.

Сломанный граф?

Что еще беспокоит меня, так это то, что край [4104 -> 1], кажется, исчезает. Хотя он упоминается во время обработки node 4104, он никогда не появляется во время обработки node 1. Все другие входящие грани упомянуты, будь то в отношении "неприемлемых", "толкающих" или "толкающих", сокращение". Я ожидаю, что он появится как один из трех типов, как и другие. Но опять же, я не знаю, где именно вы помещаете эти записи ведения журнала. Тем не менее, это оставляет немного беспокойства, и я думал, что упомянул об этом, если у вас все еще есть проблемы после исправления ваших высот.