maximum clique problem solve
Maximum Clique
People in the social network are identified by unique IDs, consecutive integers from 1 to N. Who follows who is captured in a cell array called sn: the ii th element of sn is a vector that contains a list of IDs the person with ID ii follows. You may assume that these lists are ordered in ascending order by ID. Note that the follows relationship is not necessarily symmetrical: if person A follows person B, person B may or may not follow person A. :
function clique = max_clique(graph, clique)
if nargin < 2
clique = [];
end
max_clq = clique;
if isempty(clique)
for ii= 1:length(graph)
clq = max_clique(graph,ii);
if length(clq) > length(max_clq)
max_clq = clq;
end
end
else
for node=1:length(graph)
if isempty(find(node==clique))
if check_clique(clique,node,graph)
clq = max_clique(graph, [clique node]);
if length(clq) > length(max_clq)
max_clique == clq
end
end
end
end
end
clique = max_clq;
end
function ok = check_clique(clq,node,graph)
ok = false;
for ii=1:length(clq)
if isempty(find(clq(ii) == graph{node})) || isempty (find(node == graph{clq(ii)}))
return;
end
end
ok = true;
end
Unfortunately, it is too slow and the grader will time out. Your task is to modify the code to speed it up. Remember, the question to ask: am I doing any unncessary work? Call the modified function max_clique. (Hint: when we try to expand the current clique, do we really need to consider all the nodes?)
Please solve this problem with entire new code that is fast.Maximum Clique
People in the social network are identified by unique IDs, consecutive integers from 1 to N. Who follows who is captured in a cell array called sn: the ii th element of sn is a vector that contains a list of IDs the person with ID ii follows. You may assume that these lists are ordered in ascending order by ID. Note that the follows relationship is not necessarily symmetrical: if person A follows person B, person B may or may not follow person A. :
function clique = max_clique(graph, clique)
if nargin < 2
clique = [];
end
max_clq = clique;
if isempty(clique)
for ii= 1:length(graph)
clq = max_clique(graph,ii);
if length(clq) > length(max_clq)
max_clq = clq;
end
end
else
for node=1:length(graph)
if isempty(find(node==clique))
if check_clique(clique,node,graph)
clq = max_clique(graph, [clique node]);
if length(clq) > length(max_clq)
max_clique == clq
end
end
end
end
end
clique = max_clq;
end
function ok = check_clique(clq,node,graph)
ok = false;
for ii=1:length(clq)
if isempty(find(clq(ii) == graph{node})) || isempty (find(node == graph{clq(ii)}))
return;
end
end
ok = true;
end
Unfortunately, it is too slow and the grader will time out. Your task is to modify the code to speed it up. Remember, the question to ask: am I doing any unncessary work? Call the modified function max_clique. (Hint: when we try to expand the current clique, do we really need to consider all the nodes?)
Please solve this problem with entire new code that is fast. Maximum Clique
People in the social network are identified by unique IDs, consecutive integers from 1 to N. Who follows who is captured in a cell array called sn: the ii th element of sn is a vector that contains a list of IDs the person with ID ii follows. You may assume that these lists are ordered in ascending order by ID. Note that the follows relationship is not necessarily symmetrical: if person A follows person B, person B may or may not follow person A. :
function clique = max_clique(graph, clique)
if nargin < 2
clique = [];
end
max_clq = clique;
if isempty(clique)
for ii= 1:length(graph)
clq = max_clique(graph,ii);
if length(clq) > length(max_clq)
max_clq = clq;
end
end
else
for node=1:length(graph)
if isempty(find(node==clique))
if check_clique(clique,node,graph)
clq = max_clique(graph, [clique node]);
if length(clq) > length(max_clq)
max_clique == clq
end
end
end
end
end
clique = max_clq;
end
function ok = check_clique(clq,node,graph)
ok = false;
for ii=1:length(clq)
if isempty(find(clq(ii) == graph{node})) || isempty (find(node == graph{clq(ii)}))
return;
end
end
ok = true;
end
Unfortunately, it is too slow and the grader will time out. Your task is to modify the code to speed it up. Remember, the question to ask: am I doing any unncessary work? Call the modified function max_clique. (Hint: when we try to expand the current clique, do we really need to consider all the nodes?)
Please solve this problem with entire new code that is fast. maximum_clique MATLAB Answers — New Questions
