问题描述
我正在尝试在图形上进行边缘收缩。
n是图中的顶点数。
包含代表一对边的一对顶点的向量f包含要收缩的边。
I am trying to do edge contraction on a graph.n is the number of vertices in the graph.The vector f containing pairs of vertices representing an edge contains the edges which are to be contracted.
图形不包含任何自环。
请指出代码中的任何逻辑错误。
如果该方法完全错误，请告诉我正确的算法。
Please point out any logical mistakes if any in the code. If the method is entirely wrong then please let me know the correct algorithm.
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;
}
谢谢。
推荐答案
给出以下示例图：
a d
\ /
b---e
/ \
c f将签订合同边缘{b，e}会导致以下结果？
Would "contracting" the edge {b, e} result in the following?:
a d
\ /
g
/ \
c f是的，就是这样-承认。谢谢，我想弄清楚规格，然后再回答您的问题。进一步的假设是：
"Yes, it is exactly that" - amit. Thx, I wanted to get the specification right, before I answer Your question. Further assumptions are:
- 图形是有向的
- 顶点通过整数表示。
- 图形存储在二维数组
graph，graph [x] [y] 是边缘的权重（x，y）; 0表示从x到y没有边缘。
- Graph is directed
- Vertices are represented through integers.
- The graph is stored in the two dimensional array
graph,graph[x][y]being the weight of the edge (x, y); 0 indicating that there is no edge from x to 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（通过为所有其他顶点分配0的权重，实际的顶点数不会改变） ）。此外，所有包含v2的边都折弯为包含v1。
The code works like this: Given the edge {v1, v2}, v1 becomes the "contracted" vertex. That means, instead of inserting a new vertex ("g" in my first example), v1 remains in the graph and v2 is deleted from it (by assigning 0 weights on edges to all other vertices, the actual vertex count doesn't change). Further, all edges that contain v2 are bend to contain v1.
现在，可以为一组边调用此方法。运行时间将为O（n * #edges_to_contract）。我希望这是您想要的行为。
Now one can call this method for a set of edges. The runtime will be O(n * #edges_to_contract). I hope this is the behavior You desired.
重要提示：如果您对边权重使用不同的表示形式，即0表示边的权重0的权重和∞（无穷大）表示不存在边，那么您的问题就变得微不足道了，因为您要做的就是：
Important: If You use a different representation for Your edge weights, namely 0 meaning an edge with 0 weight and ∞(infinite) indicating the absence of an edge, then Your problem becomes trivial because all You have to do is:
graph [ v1] [v2] = graph [v2] [v1] = 0
从现在起有效地收缩了边{v1，v2}在v1和v2之间旅行不需要任何费用
which effectively contracts the edge {v1, v2}, since now it doesn't cost anything to travel between v1 and v2
这篇关于在图上执行边缘收缩的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！