MATLAB: Determine separated node in graph

find separate node in graph

I have a graph like this
s = [1 2 2 4 5 4 8 7 7 8 13];
t = [3 3 11 5 6 6 7 10 12 12 9];
G = graph(s,t);
plot(G)
Here, I have 4 separated sets.
Separated_sets = {[7,10; 7,8; 7,12; 8,12],[11,2; 2,3; 3,1],[4,5; 5,6; 4,6],[9,13]};
I want to find node that is not connected to chosen node in each set.
I mean, first set is [7,10; 7,8; 7,12; 8,12]. Nodes in this set are 7, 8,10 and 12
Node 7 is connected to others so it is empty.
Node 8 not connected to node 10.
Node 10 not connected to node 8 and 12
Node 12 not connected to node 10.
So, the result of first set becomes
{[],[10],[8,12],[10]}
For second set is also the same [11,2; 2,3; 3,1]. Nodes in this set are 1, 2,3 and 11
Node 1 is not connected 2 and 11.
Node 2 is not connected 1.
Node 3 is not connected 11.
Node 11 is not connected 1 and 3.
result of second set becomes
{[2,11],[1],[11],[1,3]}
For third and 4th sets all nodes are connected so they are empty.
{[],[],[]}
{[],[]}
Until this stage result should be
{{[],[10],[8,12],[10]},{[2,11],[1],[11],[1,3]},{[],[],[]},{[],[]}}
If the chosen node is empty, put the correspond node in the result
Final result should be
{{[7],[10],[8,12],[10]},{[2,11],[1],[11],[1,3]},{[4],[5],[6]},{[9],[13]}}

Best Answer

I'm not sure what is the final goal and/or application of this process. But let me try to do this task (since this "puzzle" will be a good excerise for me!)
% Create Graph object with fixed node name
s = [1 2 2 4 5 4 8 7 7 8 13];
t = [3 3 11 5 6 6 7 10 12 12 9];
G = graph(s,t,[],compose('%d',1:13));
% Separate G to subgraphs
group = conncomp(G,'OutputForm','cell');
subGraph = cellfun(@(x) subgraph(G,x),group,'UniformOutput',false);
% Initialize the output cell array (= result)
C_out = cell(1,numel(subGraph));
for kk1 = 1:numel(subGraph)
  % kk1-th subgraph
  G = subGraph{kk1};
  nodes = G.Nodes.Name';
  c = cell(1,numel(nodes));
  % Find non-neighbouring nodes for each node and create the output cell
  % arrray for each subgraph
  for kk2 = 1:numel(nodes)
    nextNodes = neighbors(G,nodes{kk2})';
    nonNextNodes = setdiff(nodes,[nodes(kk2),nextNodes]);
    if isempty(nonNextNodes)
      c{kk2} = str2double(nodes(kk2));
    else
      [~,pt] = sort(str2double(nonNextNodes));
      c{kk2} = str2double(nonNextNodes(pt));
    end
  end
  
  % Store the result for each subgraph
  C_out{kk1} = c;
end
Related Question