c++ - 对图执行边收缩

Question

我正在尝试对图进行边收缩。n 是图中的顶点数。包含表示边的顶点对的 vector 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表示从x到y没有边

让我们尝试一些伪代码:

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 从中删除(通过将边上的权重分配给所有其他顶点，实际的顶点数不会改变).此外，所有包含 v2 的边都会弯曲以包含 v1。

现在可以为一组边调用此方法。运行时间将为 O(n * #edges_to_contract)。我希望这是您想要的行为。

重要提示:如果您对边权重使用不同的表示，即 0 表示权重为 0 的边，∞(无限)表示没有边，那么您的问题就变得微不足道了，因为所有你要做的是:

图[v1][v2] = 图[v2][v1] = 0

这有效地收缩了边缘 {v1, v2}，因为现在在 v1 和 v2 之间移动不需要任何成本