algorithm,matlab,adjacency-matrix,clique-problem , Sorting rows and columns of adjacency matrix to reveal cliques

Sorting rows and columns of adjacency matrix to reveal cliques


Tag: algorithm,matlab,adjacency-matrix,clique-problem

I'm looking for a reordering technique to group connected components of an adjacency matrix together.

For example, I've made an illustration with two groups, blue and green. Initially the '1's entries are distributed across the rows and columns of the matrix. By reordering the rows and columns, all '1''s can be located in two contiguous sections of the matrix, revealing the blue and green components more clearly.


I can't remember what this reordering technique is called. I've searched for many combinations of adjacency matrix, clique, sorting, and reordering.

The closest hits I've found are

  1. symrcm moves the elements closer to the diagonal, but does not make groups.

  2. Is there a way to reorder the rows and columns of matrix to create a dense corner, in R? which focuses on removing completely empty rows and columns

Please either provide the common name for this technique so that I can google more effectively, or point me in the direction of a Matlab function.


I don't know whether there is a better alternative which should give you direct results, but here is one approach which may serve your purpose.

Your input:

>> A

A =

 0     1     1     0     1
 1     0     0     1     0
 0     1     1     0     1
 1     0     0     1     0
 0     1     1     0     1

Method 1

Taking first row and first column as Column-Mask(maskCol) and Row-Mask(maskRow) respectively.

Get the mask of which values contains ones in both first row, and first column

maskRow = A(:,1)==1;
maskCol = A(1,:)~=1;

Rearrange the Rows (according to the Row-mask)

out = [A(maskRow,:);A(~maskRow,:)];

Gives something like this:

out =

 1     0     0     1     0
 1     0     0     1     0
 0     1     1     0     1
 0     1     1     0     1
 0     1     1     0     1

Rearrange columns (according to the column-mask)

out = [out(:,maskCol),out(:,~maskCol)]

Gives the desired results:

out =

 1     1     0     0     0
 1     1     0     0     0
 0     0     1     1     1
 0     0     1     1     1
 0     0     1     1     1

Just a check whether the indices are where they are supposed to be or if you want the corresponding re-arranged indices ;)

Before Re-arranging:

idx = reshape(1:25,5,[])

idx =

 1     6    11    16    21
 2     7    12    17    22
 3     8    13    18    23
 4     9    14    19    24
 5    10    15    20    25

After re-arranging (same process we did before)

outidx = [idx(maskRow,:);idx(~maskRow,:)];
outidx = [outidx(:,maskCol),outidx(:,~maskCol)]


outidx =

 2    17     7    12    22
 4    19     9    14    24
 1    16     6    11    21
 3    18     8    13    23
 5    20    10    15    25

Method 2

For Generic case, if you don't know the matrix beforehand, here is the procedure to find the maskRow and maskCol

Logic used:

  1. Take first row. Consider it as column mask (maskCol).

  2. For 2nd row to last row, the following process are repeated.

  3. Compare the current row with maskCol.

  4. If any one value matches with the maskCol, then find the element wise logical OR and update it as new maskCol

  5. Repeat this process till the last row.

  6. Same process for finding maskRow while the column are used for iterations instead.


%// If you have a square matrix, you can combine both these loops into a single loop.
maskCol = A(1,:);
for ii = 2:size(A,1)
    if sum(A(ii,:) & maskCol)>0 
        maskCol = maskCol | A(ii,:);

maskCol = ~maskCol;

maskRow = A(:,1);
for ii = 2:size(A,2)
    if sum(A(:,ii) & maskRow)>0 
        maskRow = maskRow | A(:,ii);

Here is an example to try that:

%// Here I removed some 'ones' from first, last rows and columns.
%// Compare it with the original example.
A = [0     0     1     0     1
     0     0     0     1     0
     0     1     1     0     0
     1     0     0     1     0
     0     1     0     0     1];

Then, repeat the procedure you followed before:

out = [A(maskRow,:);A(~maskRow,:)];        %// same code used
out = [out(:,maskCol),out(:,~maskCol)];    %// same code used

Here is the result:

>> out

out =

 0     1     0     0     0
 1     1     0     0     0
 0     0     0     1     1
 0     0     1     1     0
 0     0     1     0     1

Note: This approach may work for most of the cases but still may fail for some rare cases.

Here, is an example:

%// this works well.
A = [0     0     1     0     1    0
     1     0     0     1     0    0
     0     1     0     0     0    1
     1     0     0     1     0    0
     0     0     1     0     1    0
     0     1     0     0     1    1];

%// This may not
%// Second col, last row changed to zero from one
A = [0     0     1     0     1    0
     1     0     0     1     0    0
     0     1     0     0     0    1
     1     0     0     1     0    0
     0     0     1     0     1    0
     0     0     0     0     1    1];

Why does it fail?

As we loop through each row (to find the column mask), for eg, when we move to 3rd row, none of the cols match the first row (current maskCol). So the only information carried by 3rd row (2nd element) is lost.

This may be the rare case because some other row might still contain the same information. See the first example. There also none of the elements of third row matches with 1st row but since the last row has the same information (1 at the 2nd element), it gave correct results. Only in rare cases, similar to this might happen. Still it is good to know this disadvantage.

Method 3

This one is Brute-force Alternative. Could be applied if you think the previous case might fail. Here, we use while loop to run the previous code (finding row and col mask) number of times with updated maskCol, so that it finds the correct mask.


 maskCol = A(1,:);
 count = 1;
     for ii = 2:size(A,1)
         if sum(A(ii,:) & maskCol)>0
             maskCol = maskCol | A(ii,:);
     count = count+1;

Previous example is taken (where the previous method fails) and is run with and without while-loop

Without Brute force:

>> out

out =

 1     0     1     0     0     0
 1     0     1     0     0     0
 0     0     0     1     1     0
 0     1     0     0     0     1
 0     0     0     1     1     0
 0     0     0     0     1     1

With Brute-Forcing while loop:

>> out

out =

 1     1     0     0     0     0
 1     1     0     0     0     0
 0     0     0     1     1     0
 0     0     1     0     0     1
 0     0     0     1     1     0
 0     0     0     0     1     1

The number of iterations required to get the correct results may vary. But it is safe to have a good number.

Good Luck!


What is this algorithm mapping coordinates to numbers called?

I'm writing a program for visualizing crystals. As a part of the program, I have to generate all different basic points in a lattice structure. For those that aren't familiar with crystallography, you can find the most general cases of these structures here: The problem was that I wanted...

Plotting random signal on circle

I have some random signal (for example sin signal) with the time scale. t=0:0.1:2*pi y=sin(t) plot(t,y) Now I want to draw this signal on this circle. So the time vector actually becomes an envelope of the circle. Envelope of the circle represents "y = 0" in cartesian coordinate system. Here...

How to force my output data in a inputdlg on Matlab be a double?

I'm currently using a MATLAB to work and I need some help: I need to convert my output data (variable: units) be a double instead of a cell because I must perform a sum: units = inputdlg(question,title); sum = units + i; I've tried this code also but didn't solve...

How to switch Matlab plot tick labels to scientific form?

I have a semilogarithmic plot which works so far with semilogx. Now I would like to change the tick labels. Now it says 10^8 10^9 ... 10^13, but I would like to see 1e8, 1e9, ... 1e13 on the x-axis. How can I change that? Cheers Manuel...

function wait to execute

In Matlab functions can be started at events,but occasionally, like with the resize function, the events are called in rapid order and the function is called many times in succession, which can cause weird behavior and lag. Is there a way to have it listen for the event but only...

Matlab — SVM — All Majority Class Predictions with Same Score and AUC = .50

I'm having a weird problem in training an SVM with an RBF kernel in Matlab. The issue is that, when doing a grid search, using 10-fold cross-validation, for the C and Sigma values I always get AUC values equal to approximately .50 (varying between .48 and .54 depending) -- I...

3 X 3 magic square recursively

I'm trying to find all possible solutions to the 3X3 magic square. There should be exactly 8 solutions. My code gets them all but there are a lot of repeats. I'm having a hard time tracking the recursive steps to see why I'm getting all the repeats. // This program...

Why can't I calculate CostFunction J

This is my implementation of CostFunctionJ: function J = CostFunctionJ(X,y,theta) m = size(X,1); predictions = X*theta; sqrErrors =(predictions - y).^2; J = 1/(2*m)* sum(sqrErrors); But when I try to enter the command in MATLAB as: >> X = [1 1; 1 2; 1 3]; >> y = [1; 2; 3];...

Giving a string variable as a filename in matlab

I am using the below mentioned code to get the file names of images according to their id's from images_1 text file as strings and use them to read the images from their directory image_count=1; for image_count=1:6 file=fopen('D:\Academics\New folder\CUB_200_2011\images_1.txt','r'); C = textscan(file, '%s'); original_image=imread('D:\Academics\New folder\CUB_200_2011\images\%s','C{1}{2*(image_count)}'); imshow(original_image) end I am able...

Identify that a string could be a datetime object

If I knew the format in which a string represents date-time information, then I can easily use datetime.datetime.strptime(s, fmt). However, without knowing the format of the string beforehand, would it be possible to determine whether a given string contains something that could be parsed as a datetime object with the...

Interpolation inside a matrix. Matlab

I have a matrix looks like: 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 1 0 1 0 0 0 1 0 4 0 0 0 0 0 3 0 0 6 0 0 4...

Knapsack with unbounded items

I am familiar with the 0-1 knapsack problem and when you are given a certain number of copies from each item but I can figure out how to solve it when you are given infinite copies of each item using dynamic programming. I am trying to solve it by hand...

How to give mathemarical proof or support my answer through reasoning as a general case?

You are managing a software project that involves building a computer-assisted instrument for medical surgery. The exact placement of the surgical knife is dependent on a number of different parameters, usually at least 25, sometimes more. Your programmer has developed two algorithms for positioning the cutting tool, and is seeking...

Does there exist an algorithm for iterating through all strings that conform to a particular regex?

I'm making a script to try and hack into an account whose login password is at least 8 characters long and includes at least 1 number, 1 special character and 1 capital letter. I will use brute force. Is there a compact, elegant and efficient way to iterate through every...

MATLAB - How to merge figure sections vertically

I want to display three figures in a figure window. Assuming that I divide 2x2 regions. subplot(2,2,1) ---------+----------- | R1 | R2 | ---------+----------- | R3 | R4 | ---------+----------- I want to show a figure merging R1 and R3 ant other two in R2 and R4 I can display...

Reverse ^ operator for decryption

I'm trying to reverse the following code in order to provide a function which takes the buffer and decrypts it. void crypt_buffer(unsigned char *buffer, size_t size, char *key) { size_t i; int j; j = 0; for(i = 0; i < size; i++) { if(j >= KEY_SIZE) j = 0;...

two dimensional unique values in Matlab

I have two vectors, one of them stores the width dimension of a set of images and another one the height of these set of images. I want to use these values as two dimensional vectors [width height] and store them in a matrix. The first line, for instance, keeps...

How to normalise polynomial coefficients in a fraction?

I have the following code: syms z Gc=1.582*(1-0.3679*z^-1)/(1+.418*z^-1); Ghp=.3679*(z^-1)*(1+.718*z^-1)/((1-z^-1)*(1-.3679*z^-1)); T=(Gc*Ghp)/(1+Gc*Ghp); clipboard('copy', latex(simplifyFraction(T))); Which results in following for T: How can I normalise coefficients? I.e. I want the z2 in denominator and z in numerator to have the coefficient of 1. Is there any function in Matlab to do so?...

How to reduce time to find the n-th place from consecutive digits number for less than 1 second

I'm following the programming test, and there are questions like this From this consecutive digits: 123456789101112131415161718192021.... For example The 10th digit is 1 The 11th digit is 0 and so on What is the 1,000,000th digit? What is the 1,000,000,000th digit? What is the 1,000,000,000,000th digit? Your solution should run...

Can we add a statement in between MATLAB codes?

Is it possible to add statements in between the codes. For example: If I have a code like this, r(:,1) = a(:,1) - a(:,2); Then can I write it as, r(:,1) = a(:,1)("this is a constant") - a(:,2)("this is a variable"); ...

Disconnect all vertices in a graph - Algorithm

I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (i.e. the graph won't have any edges). Is there such algorithm? If not: Could you recommend some kind of heuristics...

Dynamic programming: how to design algorithm for when there are two factors to consider?

I have the following problem and I only have a slight idea about it: Consider a tape storage problem. Given n files of length l1,...,ln and frequencies with which they are accessed f1,...,fn, where sum of all frequencies is 1 and 0<fi<1. "Optimal" means to minimize the average retrieval time...

Determining if a graph has a cycle without using DFS

I came around one of those questions in my exams: Topologocial sorting using Kahn's Algorithm requires the graph to be DAG (Directed Acyclic Graph). How can we determine if a graph contains no cycles without using DFS/BFS first? I am trying to answer that for too long now and I...

Operating a C++ class from Matlab without mex [closed]

Is there an alternative way to call a C++ class using MATLAB, and operate its methods on MATLAB variables?

Understanding Big-Ω (Big-Omega) notation

I was doing some reading on logarithms and the rate of growth of the running time of algorithms. I have, however, a problem understanding the Big-Ω (Big-Omega) notation. I know that we use it for 'asymptotic lower bounds', and that we can express the idea that an algorithm takes at...

Create string without repeating the same element jn the string (Matlab)

I have a string "FDFACCFFFBDCGGHBBCFGE" . Could anyone help me to generate a new string with the same order but no element inside repeated twice. Thanks ! The expected output should be like this : "FDACBGHE"...

how to calculate probability for each class for predicate with knn without fitcknn?

my matlab version is 2012a. when I use fitcknn,has this error: Undefined function 'fitcknn' for input arguments of type 'cell'. how to calculate probability for each class for predicate with knn without fitcknn? after use this code, I want to calculate prob_estimates for each neighbors: knn =, trainlabel,'NumNeighbors',7); y...

Matlab - Multiply specific entries by a scalar in multidimensional matrix

I'm having problems multiplying specific values within my multidimensional matrix by a scalar. My matrix has the following dimension: size(comDatabe) = 5 10 3 397 10 The third dimension is an x-y-z coordinate frame. Something went wrong and now my y-axis is defined upside down for one subject (#8 out...

Saving images with more than 8 bits per pixel in matlab

I need to save a set of pre-processing images in matlab, resulting in grayscale images. The problem is the fact that these pre-processed images have pixel values higher than 255. If I save them with imwrite() as, for instance, .PNG files, does matlab normalize the values to be in [0,255]...

Algorithmic big o order of growth code

I'm doing an online course and i'm stuck on this question. I know there are similar questions but they don't help me. What is the order of growth of the worst case running time of the following code fragment as a function of N? int sum = 0; for (int...

Find the shortest path sum in a matrix. Is Dijkstra not optimal for this case?

I am trying to solve the following problem from project euler (please take a look at description and the example in the link, but here is the short explanation). in the matrix, find the minimal path sum from the top left to the bottom right, by moving left, right, up,...

what does ellipsis mean in a Matlab function's argument list?

What is the ellipsis for in this Matlab statement? frame = insertObjectAnnotation(frame, 'rectangle', ... bboxes, labels); ...I could not find in their online doc....

Should checking loop conditions be counted towards total number of comparisons?

I have implemented three different sorting algorithms and now I want to confirm that my approach of counting the total number of comparisons is correct. In my mind, the number of comparisons shouldn't be tied to the conditional branches because if the condition isn't met, the comparison was still made...

How to solve for matrix in Matlab?

How can I solve , where and and in the least squares sense in matlab? So I'd like to have the minimizing as output....

Reading all the files in sequence in MATLAB

I am trying to read all the images in the folder in MATLAB using this code flst=dir(str_Expfold); But it shows me output like this. which is not the sequence as i want. Can anyone please tell me how can i read all of them in sequence? for giving downmark, please...

Create mask from bwtraceboundary in Matlab

I'm trying to create a mask (or similar result) in order to erase pieces of a binary image that are not attached to the object surrounded by the boundary. I saw this thread ( to do this from bwboundaries, but I'm having trouble making suitable changes to it. My goal...

thicken an object of image to a curve in matlab

I have a labeled matrix containing two objects. How can I thicken an object to a curve? Actually I have the following image: and I want this: Each pixel of the resulting curve is the median of each column. But if you have another idea, it is acceptable, because I...

Getting Wrong Answer in “Longest non regular parentheses sub-sequence ”codechef june cook off

I attended a programming competition(it has ended now). I don't know why my solution is giving WA, I read the editorial, saw other people solution but unable to find a flaw in my solution. Obviously I am missing somewhere. Please help! Question Link My Solution My approach If the pattern...

MATLAB Access Classreg

So, I want to be able to look at (read: copy) MATLAB's NonLinearModel method of printing the regression results to the screen such as this. Nonlinear regression model: y ~ (alpha1 - alpha2*t^0.5) Estimated Coefficients: Estimate SE tStat pValue alpha1 1.0253 0.0082253 124.66 4.8823e-24 alpha2 0.0061783 0.00073277 8.4314 4.4834e-07 Number...

Connecting two binary objects in matlab

I have a binary matrix containing several binary objects and I want to bridge between them. Actually I have the following picture: And the result has to be like this: Is there any function or a shortcut way, other than loops, for this problem?...

Animate through multiple 2D Matlab plots

I have multiple 2D line plots in Matlab (they represent some wave moving through space). Each plot represents the wave at some time t. I want to animate through these plots (i.e. show the first plot for a fraction of a second, then show the next one, and the next,...

matlab plots as movie with legend

i have a question regarding legend for movies. This is my code: fig = figure(); for i = 1: 70000 plot(signal1) hold on; plot([i,i],[-5,5]) plot(signal2,'r') hold off; title('\fontsize{14} my data'); legend('signal1','signal2'); axis tight; f(i) = getframe(fig); end The legend shows the same colors for the first two things I plot....

Why black surf from this Matlab command?

Code tfr = abs ( tfr ); [row_size, column_size] = size(tfr); tfr = tfr(1:round(row_size/2), 1:row_size); surf(tfr); view(2); I get in R2014b of OSX 10.10.3 Yosemite but rotating around shows that the cells should not be black Why is the output black? I wonder if this is a hardware problem or...

Algorithm for [inclusive/exclusive]_scan in parallel proposal N3554

Proposal N3554 (A Parallel Algorithms Library) for C++14, proposes (among other things), what seem to be parallel versions of the current std::partial_sum, e.g.: template< class ExecutionPolicy, class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator inclusive_scan( ExecutionPolicy &&exec, InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); With the explanation Effects: For each...

xcorr function with impulse response

I'm trying to design a Wiener filter in Matlab for a deconvolution problem but I'm having a lot of problems. I have a gaussian white noise process with a variance of 1.2 and a impulse response which has length two. Its values are g(0) = 5 and g(1) = 4....

Matlab Distribution Sampling

How can I create a vector x in Matlab that has values between 0.8 and 1.2, randomly sampled from a: 1. Uniform 2. Normal distribution? There are a lot of functions dealing with distributions, but I'm having trouble using them properly....

How to access variables in the properties block of a Matlab System Object?

I am working on a simple System Object in Matlab/Simulink. It looks like this : classdef realtime_header_detectorSO < matlab.System & matlab.system.mixin.Propagates % correlateHeader % % This template includes the minimum set of functions required % to define a System object with discrete state. properties Header %nrOfBitsInPreviousStep=0; s=100; d=zeros(1,s); end properties...

Plot multiple functions on one figure

I'm struggling to plot multiple functions on one figure. Here is the code that I have: syms t a; a=0.9514; F1=0.5*sqrt(3*t^2); F2=-0.28375*t^2+1.155*a*(t-a)+1; F3=1; E1=diff(F1,t); E2=diff(F2,t); E3=diff(F3,t); I want to plot E1, E2 and E3, each only within a certain range, to make a "composite" line. I've tried plotting with ezplot...

solve symbolic system of equations inside an array

sorry if it already has a answer..i tried other links but it didn't understand i have 2 1*63 array .landa and v. each of their members are syms. and each v member is a function of all landa members.i have already calculated v members and they are all symbolic equations...

Recursive solution doesn't iterate correctly

I'm working through a toy problem in Ruby: how to produce all possible 10-digit phone numbers where each successive number is adjacent to the last on the keypad. I've represented the adjacent relationships between numbers, and have a recursive function, but my method isn't iterating through the whole solution space....