Is there a MATLAB function for contracting vertices of a graph?
Show older comments
I have a graph that I want to contract the vertices of. There is a way to do it manually in code but I was wondering if the MATLAB library has functionality for this so that I don't have to write unnecessary code. Vertex contraction is best explained in the following link: http://mathworld.wolfram.com/VertexContraction.html. However, I will summarize the image that is on the page here:

In the image above, I have the original graph on the left and the vertex-contracted graph on the left. I want to contract vertex 9 to vertex 7. Essentially the process results in a graph where the edges of vertex 9 is now connected to vertex 7. As you can see, edges 9-8 and 9-3 now becomes 7,9-3 and 7,9-8 but it maintains the edge 7-1 that already exists. If we contract two vertices that share an edge togehter, the edge will be removed. So if there was an edge 9-7, the edge will be removed since it will be an edge 7,9-7,9 in the new construction, which is a self loop, and that should not be there.
The code I currently have is
function G = contract(G, v, w)
ns = neighbors(G, v);
for n = ns'
G = addedge(G, w, n, 1);
end
G = rmnode(G, v);
G = rmedge(G, w, w);
end
I wonder if there is a one liner MATLAB function that allows me to do this?
1 Comment
You can simply remove selfloops first then remove the nodes. But this function will also remove all original self-loops.
function G = contract(G, v, w)
ns = neighbors(G, v);
for n = ns'
G = addedge(G, w, n, 1);
end
G = rmedge(G, w, w);
G = rmnode(G, v);
end
Answers (0)
Categories
Find more on Graph and Network Algorithms in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!