# Determine separated node in graph

4 views (last 30 days)
NA on 14 Apr 2020
Edited: NA on 15 Apr 2020
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]}}

Akira Agata on 15 Apr 2020
Edited: Akira Agata on 15 Apr 2020
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
NA on 15 Apr 2020
Edited: NA on 15 Apr 2020
Thank you for the code.
If the input is bellow, how I can use your code?
Separated_edge_sets = {[7,10; 7,8; 7,12; 8,12],[11,2; 2,3; 3,1],[4,5; 5,6; 4,6],[9,13]};
node_sets = cellfun(@(x) unique(x'),Separated_edge_sets,'uniformoutput',false);
G = cellfun(@(x) graph(x(:,1),x(:,2)),Separated_edge_sets,'UniformOutput',false);
subGraph = cellfun(@(x,y) subgraph(x,y),G,node_sets,'UniformOutput',false);
I got this error
Unrecognized table variable name 'Name'.
As G
G =
graph with properties:
Edges: [4×1 table]
Nodes: [4×0 table] ---> how can I change the nodes here?
How can I change this?