Here is the mat file with the example social network: sn.mat

# maximum clique problem solve

85 views (last 30 days)

Show older comments

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.

##### 9 Comments

### Accepted Answer

Jan
on 15 Mar 2021

Edited: Jan
on 15 Mar 2021

With replacing

if isempty(find(node==clique))

...

if isempty(find(clq(ii) == graph{node})) || isempty (find(node == graph{clq(ii)}))

by

if ~any(node==clique)

...

if ~any(clq(ii) == graph{node}) || ~any(node == graph{clq(ii)})

the processing time is reduced from 350 seconds to 193 seconds on my Matlab R2018b.

As next step inline the frequently called function check_clique in the main function:

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 ~any(node == clique)

ok = true; % Inlined check_clique:

for ii = 1:length(clique)

if ~any(clique(ii) == graph{node}) || ...

~any(node == graph{clique(ii)})

ok = false;

break;

end

end

if ok % check_clique(clique,node,graph)

clq = max_clique(graph, [clique, node]);

if length(clq) > length(max_clq)

max_clq = clq;

end

end

end

end

end

clique = max_clq;

end

This needs 72 seconds on my computer. 5 times faster with just tiny modifications.

##### 11 Comments

### More Answers (2)

Mehrail Nabil
on 17 Aug 2021

Anyone can send me in comment the answer of it???? The code please

##### 1 Comment

Jonathan Paul Yuquilema Aldaz
on 9 Oct 2021

MR MB
on 4 Sep 2021

Edited: MR MB
on 4 Sep 2021

%if true

function clique = max_clique(graph,clique)

if nargin < 2 % originaly we call the function with just the graph

clique = []; % hence, the clique is initialized to an empty vector

end

max_clq = clique; % max_clq will store the current largest clique

if isempty(clique) % when we first call the function

ii = 1:length(graph);

s = max_clique(graph,ii); %out of the loop

for ii = 1:length(graph) % we need to test potential cliques starting from every possible node

clq = s;

if length(clq) > length(max_clq) % if the new one is larger than the current

max_clq = clq; % we store the new one

end

end

else

for node = 1:length(graph) % we are in a recursive call now: we test every node as a new member

if isempty(find(node == clique)) % unless it is already in the clique

if check_clique(clique,node,graph) % if adding this node is still a clique

clq = max_clique(graph,[clique node]); % we call ourself with the new expanded clique

if length(clq) > length(max_clq) % if what we get is larger the curent max

max_clq = clq; % we store the new one

end

end

end

end

end

clique = max_clq; % return the largest one

end

%if true

function ok = check_clique(clq,node,graph) % adding node to clq still a clique?

ok = false;

for ii = 1:length(clq) % for every current member

if isempty(find(clq(ii) == graph{node})) || ... % the member must be on the follows list of the new guy

isempty(find(node == graph{clq(ii)})) % the new guy must be on the follows list of the member

return;

end

end

ok = true;

end

end

It is so so so fast but with wrong answer Can any one help me to find the mistake?!?

##### 5 Comments

### See Also

### Products

### Community Treasure Hunt

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

Start Hunting!