Выполнение сжатия ребра на графике

Question

Я пытаюсь сделать ребро на графике. n - количество вершин в графе. Вектор f, содержащий пары вершин, представляющих ребро, содержит ребра, которые должны быть сжаты.

График не содержит собственных циклов.

Пожалуйста, укажите любые логические ошибки, если таковые имеются в коде. Если метод совершенно неверный, сообщите мне правильный алгоритм.

void modify(vector<pair<int, int> > &f)
{
    // sorting elements of each pair
    for(vector<pair<int, int> >::iterator it = f.begin(); it != f.end(); it++)
    {
      if(it->first > it->second)
        swap(it->first, it->second);
    }

    // sorting elements of set f
    sort(f.begin(), f.end());
    reverse(f.begin(), f.end());

    for(vector<pair<int, int> >::iterator it = f.begin(); it != f.end(); it++)
    {
      int x, y;
      x = it->first;
      y = it->second;

      for(int i = 0; i < n; i++)
        if(x != i)
        {
          graph[x][i] = graph[y][i] = graph[x][i] + graph[y][i];
          graph[i][x] = graph[i][y] = graph[i][x] + graph[i][y];
        }
    }


    vector<bool> pos(n, false); // array of positions to be deleted

    for(vector<pair<int, int> >::iterator it = f.begin(); it != f.end(); it++)
      pos[it->second] = true;

    // deleting rows
    int count = 0;
    for(int i = 0; i < n; i++)
    {
            for(int j = 0; j < n; j++)
              graph[i-count][j] = graph[i][j];
            if(pos[i])
              count++;
    }

    // deleting columns
    count = 0;
    for(int j = 0; j < n; j++)
    {
            for(int i = 0; i < n; i++)
              graph[i][j-count] = graph[i][j];
            if(pos[j])
              count++;
    }

    // finally dimension of the matrix becomes n - count
    n = n - count;
}

Заранее спасибо.

Answer 1

Учитывая следующий пример графика:

a       d
 \     /
  b---e
 /     \
c       f

Не приведет ли "сокращение" края {b, e} к следующему?:

a   d
 \ /
  g
 / \
c   f

«Да, это именно так» - амит. Спасибо, я хотел получить правильную спецификацию, прежде чем ответить на Ваш вопрос. Дальнейшие предположения:

• График направлен
• Вершины представлены целыми числами.
• График хранится в двумерном массиве graph, graph[x][y] - вес ребра (x, y); 0 указывает на отсутствие ребра от х до у

Давайте попробуем использовать псевдокод :

void contractEdge(int v1, int v2) {
    for (int i = 0; i < n; i++) {
        if (graph[v2][i] > 0) {
            graph[v1][i] = graph[v1][i] > 0 ? min(graph[v1][i], graph[v2][i]) :
                                              graph[v2][i];
            graph[v2][i] = 0;
        }
        if (graph[i][v2] > 0) {
            graph[i][v1] = graph[i][v1] > 0 ? min(graph[i][v1], graph[i][v2]) :
                                              graph[i][v2];
            graph[i][v2] = 0;
        }
        graph[v1][v2] = graph[v2][v1] = 0;
    }
}

Код работает так: учитывая ребро {v1, v2}, v1 становится «свернутой» вершиной. Это означает, что вместо вставки новой вершины («g» в моем первом примере) v1 остается в графе, а v2 удаляется из него (при назначении 0 весов на ребрах всем остальным вершинам фактическое количество вершин не изменяется ). Кроме того, все ребра, содержащие v2, сгибаются, чтобы содержать v1.

Теперь этот метод можно вызвать для набора ребер. Время выполнения будет O (n * #edges_to_contract). Я надеюсь, что это поведение, которое вы хотели.

Важно: Если вы используете другое представление для веса ребер, а именно 0 означает ребро с весом 0 и ∞ (бесконечно), указывающее на отсутствие ребра, то ваша проблема становится тривиальной, поскольку все вы должен сделать это:

graph[v1][v2] = graph[v2][v1] = 0

, который эффективно сжимает ребро {v1, v2}, поскольку теперь между v1 и v2 ничего не стоит ехать

Answer 2

Это не сжатие ребер, а сжатие вершин. Конечно, ребро, связывающее сжатые вершины, исчезает, и веса ребер, соединяющих исходные вершины с их соседями, необходимо суммировать.