Is there a MATLAB function for contracting vertices of a graph?

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

Sign in to comment.

Answers (0)

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Products

Release

R2019b

Asked:

on 27 Feb 2020

Edited:

on 14 Apr 2022

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!