MATLAB: How to search all elements in two cell arrays

cell arrays

Hi,
I have two cell arrays, each cell in these two arrays represent a connected component in a graph.
 C = {[21,45,87,99,121],[37,918],[150,700],[218,851],[420,728],[464,761],[695,709],16,34}; % Connected components in Graph G
 B = {[4,600,303,5,56,88,87,63],[142,257,481,785],[103,33,509],[99,588],[251,524],[572,683],8,65,105} % Connected components in Graph H
I want to go through each cell in array C and check if it's members (Nodes) connected to other cell's members (nodes) in B.
That is, if the nodes [37,918] in C (in the same component) are connected to the two nodes 251 and 588 in B (different component) remove the edge between 37,918.
I would appreciate your help and tips.

Best Answer

All right, let's assume you have a graph containing both G and H stored as graph object GH, and that this graph contains the black and red edges from your picture, but not the purple ones which are just the mapping between G and H.
I'll also assume you have a vector which mapGH which maps between those two sets of points (that's the purple lines): mapGH(i) == j and mapGH(j) == i, where i is a node in G and j is its corresponding node in H.
Am I right to assume these inputs are available?
Then, we can find all edges to remove as follows:
bins = conncomp(GH);
[s, t] = findedge(GH); % list start and end nodes of all edges in GH


st = [s, t];
% We know bins(s) == bins(t), because two nodes connected by an edge are always in the same component.


% Check if their mapped edges are also in the same component:


needRemoveEdge = bins(mapGH(s)) ~= bins(mapGH(t));
GH = rmedge(GH, find(needRemoveEdge));
This removes all edges where the mapped nodes aren't in the same component of the other graph. But removing these edges will change the connected components, so it's probably a good idea to do this several times (stages), until there are no edges that have to be removed:
bins = conncomp(GH);
[s, t] = findedge(GH); % list start and end nodes of all edges in GH
st = [s, t];
% We know bins(s) == bins(t), because two nodes connected by an edge are always in the same component.
% Check if their mapped edges are also in the same component:
needRemoveEdge = bins(mapGH(s)) ~= bins(mapGH(t));
while any(needRemoveEdge)
    GH = rmedge(GH, find(needRemoveEdge));
    bins = conncomp(GH);
    [s, t] = findedge(GH); % list start and end nodes of all edges in GH
    st = [s, t];
    % We know bins(s) == bins(t), because two nodes connected by an edge are always in the same component.
    % Check if their mapped edges are also in the same component:
    needRemoveEdge = bins(mapGH(s)) ~= bins(mapGH(t));
end
This will never be an infinite loop because every iteration removes at least one edge from GH.
Keep in mind I haven't tested this because I don't have time to write up example inputs right now. Can you try it and let me know if it works? If not, could you include some example data for GH and mapGH?
Related Question