Here is the mat file with the example social network: sn.mat
maximum clique problem solve
48 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
Parth Tushar Deodhar
am 14 Mär. 2021
Kommentiert: Walter Roberson
am 28 Jul. 2024 um 22:07
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 Kommentare
Jan
am 3 Apr. 2021
Bearbeitet: Jan
am 16 Jun. 2021
@Parth Tushar Deodhar: You have set a flag:
"please delete this thread as it is an home work assignment and might lead to some one copying it."
With using this forum you agree to the Terms of Use. This implies that the posted contents is made available for the community. The nature of this forum is the sharing of problems and solutions. To support this, many voluntary Matlab users spend their time. Removing a question after an answer has been given, would not respect their work.
Please think twice before you post homework questions in the internet. Remember that even if the thread is deleted in the forum, you will still find a copy e.g. in Googles cache. Therefore I remove the flag without deleting the thread.
Akzeptierte Antwort
Jan
am 15 Mär. 2021
Bearbeitet: Jan
am 15 Mär. 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 Kommentare
Walter Roberson
am 19 Aug. 2021
I suspect you could write the code more efficiently using ismember() in check_clique
Weitere Antworten (5)
Black Woods
am 18 Dez. 2022
function clique = max_clique(g,clique)
if nargin < 2
clique = [];
end
max_clq = clique;
if isempty(clique)
for ii = 1:length(g)
clq = max_clique(g,ii);
if length(clq) > length(max_clq)
max_clq = clq;
end
end
else
candidates = g{clique(1)};
candidates = candidates(g{clique(1)} > max(clique));
for ii = 1:length(candidates)
if check_clq(clique,candidates(ii),g)
clq = max_clique(g,[clique candidates(ii)]);
if length(clq) > length(max_clq)
max_clq = clq;
end
end
end
end
clique = max_clq;
end
function ok = check_clq(clq,id,g)
ok = false;
if ~isempty(find(id == clq))
return;
end
for ii = 1:length(clq)
if isempty(find(clq(ii) == g{id})) || isempty(find(id == g{clq(ii)}))
return;
end
end
ok = true;
end
0 Kommentare
Mehrail Nabil
am 17 Aug. 2021
Anyone can send me in comment the answer of it???? The code please
1 Kommentar
Jonathan Paul Yuquilema Aldaz
am 9 Okt. 2021
@Mehrail Nabil Were you able to solve the problem? I would appreciate if you help me with the code. Please.
MR MB
am 4 Sep. 2021
Bearbeitet: MR MB
am 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 Kommentare
ghazal
am 3 Jul. 2022
Thanks Jan, but now I get this error
Undefined function 'max_clique' for input arguments of type 'cell'.
Rajith
am 17 Dez. 2023
function clique = max_clique(g,clique)
if nargin < 2
clique = [];
end
max_clq = clique;
if isempty(clique)
for ii = 1:length(g)
clq = max_clique(g,ii);
if length(clq) > length(max_clq)
max_clq = clq;
end
end
else
candidates = g{clique(1)}; % it is enough to check nodes that the first member of the clique follows
candidates = candidates(g{clique(1)} > max(clique)); % since nodes are ordered, a potential new member must have a greater ID than current members
for ii = 1:length(candidates)
if check_clq(clique,candidates(ii),g)
clq = max_clique(g,[clique candidates(ii)]);
if length(clq) > length(max_clq)
max_clq = clq;
end
end
end
end
clique = max_clq;
end
function ok = check_clq(clq,id,g)
ok = false;
if ~isempty(find(id == clq))
return;
end
for ii = 1:length(clq)
if isempty(find(clq(ii) == g{id})) || isempty(find(id == g{clq(ii)}))
return;
end
end
ok = true;
end
0 Kommentare
Divyanshu
am 28 Jul. 2024 um 11:04
Bearbeitet: Walter Roberson
am 28 Jul. 2024 um 22:02
function clique = max_clique(g,clique)
if nargin < 2
clique = [];
end
max_clq = clique;
if isempty(clique)
for ii = 1:length(g)
clq = max_clique(g,ii);
if length(clq) > length(max_clq)
max_clq = clq;
end
end
else
candidates = g{clique(1)}; % it is enough to check nodes that the first member of the clique follows
candidates = candidates(g{clique(1)} > max(clique)); % since nodes are ordered, a potential new member must have a greater ID than current members
for ii = 1:length(candidates)
if check_clq(clique,candidates(ii),g)
clq = max_clique(g,[clique candidates(ii)]);
if length(clq) > length(max_clq)
max_clq = clq;
end
end
end
end
clique = max_clq;
end
function ok = check_clq(clq,id,g)
ok = false;
if ~isempty(find(id == clq))
return;
end
for ii = 1:length(clq)
if isempty(find(clq(ii) == g{id})) || isempty(find(id == g{clq(ii)}))
return;
end
end
ok = true;
end
1 Kommentar
Walter Roberson
am 28 Jul. 2024 um 22:07
This is the same as what @Rajith posted, except for using slightly different number of spaces at the beginning of lines. There is no difference other than the spacing.
Siehe auch
Kategorien
Mehr zu Logical finden Sie in Help Center und File Exchange
Produkte
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!