Find maximum clique with recursive function

7 visualizaciones (últimos 30 días)
hmhuang
hmhuang el 9 de Ag. de 2021
Comentada: breksam Amr el 12 de Sept. de 2021
I am solving an problem which has been stated and discussed here: maximum clique problem solve
As the OP showed in the above thread, the original version is inefficient because it is checking a bunch of sets of nodes that cannot possibly be part of a clique. So we need a smarter way to pick which nodes to check.
Therefore, based the tiny improvement in the accepted answer in maximum clique problem solve, I also tried:
  1. disregard nodes with length < length(clique)
  2. disregard nodes with the first element > clique(1)
  3. disregard nodes with the last element < clique(end)
  4. disregard nodes that are not in the follow list of first elemnt in the current clique
So my version of modification based on what @Jan wrote is changing line 15 to:
if ~any(node == clique) && length(graph{node}) >= length(clique) && graph{node}(1) <= clique(1) && graph{node}(end) >= clique(end) && any(node == graph{clique(1)})
Unfortunately, this runs for ~60 seconds on my computer, which is still not fast enough to pass the grader...
I also come up with the order of operands of && operator. So I change the above line to:
if any(node == graph{clique(1)}) && length(graph{node}) >= length(clique) && graph{node}(1) <= clique(1) && graph{node}(end) >= clique(end) && ~any(node == clique)
Although this gets a bit faster and runs for ~40 seconds on my computer, unfortunately this is still not fast enough to pass the grader...
I HOPE SOMEONE COULD PROVIDE SOME ADVICES.
ANY SUGGESTIONS WILL BE APPRECIATED.
  5 comentarios
hmhuang
hmhuang el 10 de Ag. de 2021
Editada: hmhuang el 10 de Ag. de 2021
@Jan Thanks for asking. Yes, everyone can also follow themselves. The array was randomly generated. But to be qualified as an element of the clique, everyone should follow everyone else in the clique, following themselves isn't enough to be an element of a clique. For example, by the result: [ 1769 1773 1774 1833 2222 ], this means 1769 must follow 1773, 1774, 1833, 2222 and 1773 must follow 1769, 1774, 1833, 2222, and so on.
I hope this makes things more clear.
Jan
Jan el 12 de Ag. de 2021
Okay, it's clear now.

Iniciar sesión para comentar.

Respuesta aceptada

Jan
Jan el 12 de Ag. de 2021
Editada: Jan el 12 de Ag. de 2021
I've reduced the run time from 60 to 2 seconds using this method:
  • Convert the {1 x N} cell array of vectors to a [N x N] logical array X, which is true, if an ID in a specific column follows an ID in a specific row.
  • Omit elements of X if the corresponding elements of X.' are not true: A following cannot belong to a clique, if it points it is not mutual.
  • Run a loop over the rows (or columns - X is symmetric now). Select the sumbatrix:
v = X(k, :);
Y = X(v, v);
  • Convert this back to the original represantation using a cell vector and indices.
  • Call the original function as suggested in the other thread
An alternative description of the idea: I do not search the complete graph, but for the k'th ID only the elements of graph(graph{k}) are considered. The others cannot be part of a clique, which contains the k'th node of the graph.
I do not post the code, because this is a question of a course. A clean solution would stay at the representation as logical array to apply the recursive search. But my lazy method yields an acceleration of factor 30 already by a divide and conquer approach without touching the actual algorithm.
  7 comentarios
Jan
Jan el 19 de Ag. de 2021
@Mehrail Nabil: Sorry, no. The question is part of a course. If a solution is found in the net, the homework question is not useful anymore.
I've explained a solution and hmhuang has mentioned, that you need to change one line of the original code only. Please read his last comment and find the solution by your own.
breksam Amr
breksam Amr el 12 de Sept. de 2021
@Mehrail Nabil did you find the answer i still don't understand it yet

Iniciar sesión para comentar.

Más respuestas (0)

Categorías

Más información sobre MATLAB en Help Center y File Exchange.

Etiquetas

Community Treasure Hunt

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

Start Hunting!

Translated by