title: Count unique quadrangles
body: <p>Given an planar undirected  graph with n points marked by integer number [1,2,..n] </p>
  
  <p>The task is to find all the unique quadrangles, by "unique", we mean: if two quadrangles have all the four points be the same but only the relative order is different, then the two are treated as the "same" quadrangle. For example, [1,2,3,4] and [1,3,2,4] are the same quadrangle.</p>
  
  <p>Input: The graph can be stored by whatever format you  prefer. Here we use adjacent matrix (for undirected graph, each physical edge is inputted once in the following description), the first two numbers in the 1st line is the vertex  number and edge number respectively. Then the following lines input each edge by each time.</p>
  
  <p>Output: An M-by-4 matrix or list of arrays. M is the final unique quadrangle count you have found.</p>
  
  <p>In the following undirected complete graph of five points:</p>
  
  <pre><code>5  10
  1    4
  1    2
  1    3
  1    5
  2    3
  2    4
  2    5
  3    4
  3    5
  4    5
  </code></pre>
  
  <p>There are only five unique quadrangles (ignore the relative order of the vertex sequence):</p>
  
  <pre><code> 1     2     3     4
   1     2     3     5
   1     2     4     5
   1     3     4     5
   2     3     4     5
  </code></pre>
  
  <p>I don't have a perfect solution now.</p>
  
  <p>The following MATLAB solution can only find every unique quadrangle for Case-1, but failed in Case-2 , i.e. no quadrangle can be found.</p>
  
  <pre><code>%% Count Quadrangles
  
  clc;
  
  v = vertex(:,1);
  t = vertex(:,2);
  G = zeros( max(max(v),max(t)));
  n = length(G);
  
  % For muilt-edge graph , Build the matrix for graph:
  for i = 1:length(v)
      G(v(i), t(i)) = G(v(i), t(i)) + 1; 
      G(t(i), v(i)) = G(v(i), t(i)); 
  end
  issymmetric(G)
  max(max(G))
  
  % For single edge graph, Build the matrix for graph:
  % G(sub2ind(size(G),v, t))=1;
  % G(sub2ind(size(G),t, v))=1; % fill the symmetric position
  
  tic 
  
  quad_cnt = 0; 
  % G_ = graph(G);
  quad_points = [];
  %% O(N^3)
  for i = 1:n
      for j = i+1:n
          if (j==i || G(i,j)==0)
              continue;
          end
  
          for k = j+1:n
              if ( k==i || k==j || (G(k,i)==0 &amp;&amp; G(k,j) == 0) )
                  continue;
              end  
  
              for p = k+1:n  
  
                  if ( p==i || p==j || p==k || G(p,i)==0 || G(p,k) == 0)
                      continue;
                  end 
  
                  % otherwise, a quadrangle is ofund
                  quad_cnt = quad_cnt+1; 
                  % save the vertices
                  quad_points(quad_cnt,:) = [i,j,k,p];
              end
  
          end                  
      end   
  end
  toc
  % 0.1571 sec
  
  quad_cnt
  
  % output each triangle:
  quad_points
  
  %% O(deg*(V^2))
  </code></pre>
  
  <p>Test Cases
  Edge inputs by using vertices index (Note: starting from "1" not "0"):</p>
  
  <p>Case-1:
  Input: </p>
  
  <pre><code>5   10
  1   4
  1   2
  1   3
  1   5
  2   3
  2   4
  2   5
  3   4
  3   5
  4   5
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code> 1     2     3     4
   1     2     3     5
   1     2     4     5
   1     3     4     5
   2     3     4     5
  </code></pre>
  
  <p>Case-2:
  Input:</p>
  
  <pre><code>8    8
  1    3
  2    3
  1    4
  2    4
  1    8
  2    5
  3    6
  4    7
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code>1 2 3 4
  </code></pre>