Mixing
Count unique quadrangles
2
Given an planar undirected graph with n points marked by integer number [1,2,..n]
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.
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.
Output: An M-by-4 matrix or list of arrays. M is the final unique quadrangle count you have found.
In the following undirected complete graph of five points:
5 10
1 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
There are only five unique quadrangles (ignore the relative order of the vertex sequence):
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
I don't have a perfect solution now.
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.
%% 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 && 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))
Test Cases
Edge inputs by using vertices index (Note: starting from "1" not "0"):
Case-1:
Input:
5 10
1 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Output:
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
Case-2:
Input:
8 8
1 3
2 3
1 4
2 4
1 8
2 5
3 6
4 7
Output:
1 2 3 4
algorithm graph-algorithm computational-geometry combinatorics
asked Nov 19 '18 at 17:25
ZPascal
111
add a comment |
2
Given an planar undirected graph with n points marked by integer number [1,2,..n]
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.
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.
Output: An M-by-4 matrix or list of arrays. M is the final unique quadrangle count you have found.
In the following undirected complete graph of five points:
5 10
1 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
There are only five unique quadrangles (ignore the relative order of the vertex sequence):
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
I don't have a perfect solution now.
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.
%% 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 && 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))
Test Cases
Edge inputs by using vertices index (Note: starting from "1" not "0"):
Case-1:
Input:
5 10
1 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Output:
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
Case-2:
Input:
8 8
1 3
2 3
1 4
2 4
1 8
2 5
3 6
4 7
Output:
1 2 3 4
algorithm graph-algorithm computational-geometry combinatorics
asked Nov 19 '18 at 17:25
ZPascal
111
Thanks. I deliberately "let" the index number become larger in the next iteration loop every time -- because if you don't do that, in some graph, repeated solutions will be found together. However, ironically, this way cannot handle case-2 as I listed above, where no solution can be found. You can drawn the graph for both the cases I listed and you will get the point.
– ZPascal
Nov 19 '18 at 17:57
Good point. I'll try again. For each vertex ('start'), for each pair of nodes connected to 'start' ('neighbors'), find a node connected to both 'neighbors' ('end'), where the node numbers for 'neighbors' and 'end' are all greater than the node number for 'start'.
– user3386109
Nov 19 '18 at 18:34
I figure out a non-elegant way: 1. Find all (allowing non-unique) sequence of quadrangles,suppose the number is N; 2. Sort all the sequences, O(N log4) = O(N) 3. Detect and remove repeated sequence, Many tricks can be applied in this step, e.g. map [1,2,3,4] to 1234 and hash it. But, I am still expecting anyone can provide a straightforward and elegant algorithm.
– ZPascal
Nov 19 '18 at 20:35
add a comment |
2
2
2
Given an planar undirected graph with n points marked by integer number [1,2,..n]
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.
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.
Output: An M-by-4 matrix or list of arrays. M is the final unique quadrangle count you have found.
In the following undirected complete graph of five points:
5 10
1 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
There are only five unique quadrangles (ignore the relative order of the vertex sequence):
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
I don't have a perfect solution now.
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.
%% 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 && 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))
Test Cases
Edge inputs by using vertices index (Note: starting from "1" not "0"):
Case-1:
Input:
5 10
1 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Output:
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
Case-2:
Input:
8 8
1 3
2 3
1 4
2 4
1 8
2 5
3 6
4 7
Output:
1 2 3 4
algorithm graph-algorithm computational-geometry combinatorics
asked Nov 19 '18 at 17:25
ZPascal
111
Given an planar undirected graph with n points marked by integer number [1,2,..n]
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.
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.
Output: An M-by-4 matrix or list of arrays. M is the final unique quadrangle count you have found.
In the following undirected complete graph of five points:
5 10
1 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
There are only five unique quadrangles (ignore the relative order of the vertex sequence):
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
I don't have a perfect solution now.
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.
%% 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 && 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))
Test Cases
Edge inputs by using vertices index (Note: starting from "1" not "0"):
Case-1:
Input:
5 10
1 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Output:
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
Case-2:
Input:
8 8
1 3
2 3
1 4
2 4
1 8
2 5
3 6
4 7
Output:
1 2 3 4
algorithm graph-algorithm computational-geometry combinatorics
algorithm graph-algorithm computational-geometry combinatorics
asked Nov 19 '18 at 17:25
ZPascal
111
asked Nov 19 '18 at 17:25
ZPascal
111
asked Nov 19 '18 at 17:25
ZPascal
111
asked Nov 19 '18 at 17:25
ZPascal
111
asked Nov 19 '18 at 17:25
ZPascal
111
111
Thanks. I deliberately "let" the index number become larger in the next iteration loop every time -- because if you don't do that, in some graph, repeated solutions will be found together. However, ironically, this way cannot handle case-2 as I listed above, where no solution can be found. You can drawn the graph for both the cases I listed and you will get the point.
– ZPascal
Nov 19 '18 at 17:57
Good point. I'll try again. For each vertex ('start'), for each pair of nodes connected to 'start' ('neighbors'), find a node connected to both 'neighbors' ('end'), where the node numbers for 'neighbors' and 'end' are all greater than the node number for 'start'.
– user3386109
Nov 19 '18 at 18:34
I figure out a non-elegant way: 1. Find all (allowing non-unique) sequence of quadrangles,suppose the number is N; 2. Sort all the sequences, O(N log4) = O(N) 3. Detect and remove repeated sequence, Many tricks can be applied in this step, e.g. map [1,2,3,4] to 1234 and hash it. But, I am still expecting anyone can provide a straightforward and elegant algorithm.
– ZPascal
Nov 19 '18 at 20:35
add a comment |
Thanks. I deliberately "let" the index number become larger in the next iteration loop every time -- because if you don't do that, in some graph, repeated solutions will be found together. However, ironically, this way cannot handle case-2 as I listed above, where no solution can be found. You can drawn the graph for both the cases I listed and you will get the point.
– ZPascal
Nov 19 '18 at 17:57
Good point. I'll try again. For each vertex ('start'), for each pair of nodes connected to 'start' ('neighbors'), find a node connected to both 'neighbors' ('end'), where the node numbers for 'neighbors' and 'end' are all greater than the node number for 'start'.
– user3386109
Nov 19 '18 at 18:34
I figure out a non-elegant way: 1. Find all (allowing non-unique) sequence of quadrangles,suppose the number is N; 2. Sort all the sequences, O(N log4) = O(N) 3. Detect and remove repeated sequence, Many tricks can be applied in this step, e.g. map [1,2,3,4] to 1234 and hash it. But, I am still expecting anyone can provide a straightforward and elegant algorithm.
– ZPascal
Nov 19 '18 at 20:35
Thanks. I deliberately "let" the index number become larger in the next iteration loop every time -- because if you don't do that, in some graph, repeated solutions will be found together. However, ironically, this way cannot handle case-2 as I listed above, where no solution can be found. You can drawn the graph for both the cases I listed and you will get the point.
– ZPascal
Nov 19 '18 at 17:57
Thanks. I deliberately "let" the index number become larger in the next iteration loop every time -- because if you don't do that, in some graph, repeated solutions will be found together. However, ironically, this way cannot handle case-2 as I listed above, where no solution can be found. You can drawn the graph for both the cases I listed and you will get the point.
– ZPascal
Nov 19 '18 at 17:57
Good point. I'll try again. For each vertex ('start'), for each pair of nodes connected to 'start' ('neighbors'), find a node connected to both 'neighbors' ('end'), where the node numbers for 'neighbors' and 'end' are all greater than the node number for 'start'.
– user3386109
Nov 19 '18 at 18:34
Good point. I'll try again. For each vertex ('start'), for each pair of nodes connected to 'start' ('neighbors'), find a node connected to both 'neighbors' ('end'), where the node numbers for 'neighbors' and 'end' are all greater than the node number for 'start'.
– user3386109
Nov 19 '18 at 18:34
I figure out a non-elegant way: 1. Find all (allowing non-unique) sequence of quadrangles,suppose the number is N; 2. Sort all the sequences, O(N log4) = O(N) 3. Detect and remove repeated sequence, Many tricks can be applied in this step, e.g. map [1,2,3,4] to 1234 and hash it. But, I am still expecting anyone can provide a straightforward and elegant algorithm.
– ZPascal
Nov 19 '18 at 20:35
I figure out a non-elegant way: 1. Find all (allowing non-unique) sequence of quadrangles,suppose the number is N; 2. Sort all the sequences, O(N log4) = O(N) 3. Detect and remove repeated sequence, Many tricks can be applied in this step, e.g. map [1,2,3,4] to 1234 and hash it. But, I am still expecting anyone can provide a straightforward and elegant algorithm.
– ZPascal
Nov 19 '18 at 20:35
add a comment |
2 Answers
2
active
oldest
votes
0
I have another approach to find the quadrangles. It's using the concept of DFS. Traverse the graph for all node to find the quadrangles for a certain depth. To remove duplicates, sort the quadrangles then remove the quadrangles or use hash table. My c++ implementation is given below:
#include<bits/stdc++.h>
using namespace std;
// if Edge[a][b] = 1, then there is an edge between node 'a' and 'b'
int Edge[100][100] = {0};
// to keep the list of quadrangles
// here 'set' is a data structure that keep unique elements
set< vector<int> > quadrangles;
// forbiddenNode[n] = 1, if this node 'n' is forbidden to visit
// forbiddenNode[n] = 0, if this node 'n' is not forbidden to visit
int forbiddenNode[100]={0};
// taken[n] = 1, if this node 'n' is taken in current Quadrangles
// taken[n] = 0, if this node 'n' is not taken in current Quadrangles
int taken[1000]={0};
void AddQuadrangle(vector<int> q) {
sort(q.begin(), q.end());
quadrangles.insert(q);
}
void findQuadrangles(int curNode, int depth, vector<int> &curQuadrangles, int numOfNodes) {
if(depth == 0) {
if( Edge[curNode][curQuadrangles[0]] == 1) {
// found a quadrangle
AddQuadrangle(curQuadrangles);
}
}
for(int i = 1; i <= numOfNodes; i++) {
if(forbiddenNode[i] == 0 && taken[i] == 0 && Edge[curNode][i] == 1) {
// take this node
taken[i] = 1;
// add this node to curQuadrangles in the back
curQuadrangles.push_back(i);
findQuadrangles(i, depth - 1, curQuadrangles, numOfNodes);
// undo take this node
taken[i] = 0;
// remove this node to curQuadrangles from the back
curQuadrangles.pop_back();
}
}
}
int main() {
int numOfNodes, numOfEdge;
// take input for number of nodes, edges
scanf("%d %d", &numOfNodes, &numOfEdge);
// take input for edges
for(int i=0; i < numOfEdge; i++) {
int x, y;
scanf("%d %d",&x, &y);
Edge[x][y] = 1;
Edge[y][x] = 1;
}
for(int i = 1; i <= numOfNodes; i++) {
vector<int> curQuadrangle;
curQuadrangle.push_back(i);
taken[i] = 1;
findQuadrangles(i, 3, curQuadrangle, numOfNodes);
// set this node as forbidden to include in any quadrangle
forbiddenNode[i];
}
// print quadrangles
for( set<vector<int> >::iterator it = quadrangles.begin(); it != quadrangles.end(); it++) {
vector<int> q = *it;
printf("%d %d %d %dn",q[0], q[1], q[2], q[3]);
}
return 0;
}
answered Nov 20 '18 at 11:02
nightfury1204
1,43048
Thanks. I will take a read for your code. I am doubting that, there will be any "smart/elegant" way to fulfill my purpose WITHOUT using any special data structure like stack, hash-table (or hashmap) or queue,etc. Or in other words, avoiding the "deleting duplicates" process.
– ZPascal
Nov 20 '18 at 18:45
The following is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs).
– ZPascal
Nov 20 '18 at 18:50
add a comment |
0
Here is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs):
clc;
v = vertex(:,1);
t = vertex(:,2);
G = zeros( max(max(v),max(t)));
n = length(G);
% For multi-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)); % comment here is input is bi-directional
end
quad_cnt = 0;
quad_points = ;
for i = 1:n
for j = i+1:n
if (j==i || G(j,i)==0)
continue;
end
for k = i+1:n
if ( k==i || k==j || (G(k,i)==0 && G(k,j)==0))
continue;
end
if (G(k,i)~=0 && G(k,j)~=0)
for p = i+1:n
if ( p==i || p==j || p==k)
continue;
end
if (G(p,i)~=0 && G(p,j)~=0)||(G(p,i)~=0 && G(p,k)~=0)||(G(p,j)~=0 && G(p,k)~=0)
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
end
if (G(k,i)==0 && G(k,j)~=0)
for p = i+1:n
if (p==i || p==j || p==k || G(p,k)==0 || G(p,i) == 0)
continue;
end
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
if (G(k,i)~=0 && G(k,j)==0)
for p = i+1:n
if ( p==i || p==j || p==k || G(p,j)==0 || G(p,k) == 0)
continue;
end
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
end
end
end
% quad_cnt
% Remove repeat
% 1) sort
hash = ;
Base = max(max(v),max(t))+ 1;
for i =1: quad_cnt
temp = sort(quad_points(i,:));
quad_points(i,:) = temp;
hash(i) = quad_points(i,1)*Base^3 + quad_points(i,2)*Base^2 + quad_points(i,3)*Base + quad_points(i,4);
end
% 2) remove repeats
[C, ~, ~] = unique(hash);
quad_cnt = length(C);
quad_cnt
quad_points = ;
for i = 1: quad_cnt
num = C(i);
digit = ;
for k = 1:4
digit(k) = mod(num, Base);
num = fix(num/Base); % or use "floor()"
end
quad_points(i,:) = digit;
end
% output each quadrangle:
quad_points;
answered Nov 20 '18 at 18:56
ZPascal
111
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53379768%2fcount-unique-quadrangles%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
0
I have another approach to find the quadrangles. It's using the concept of DFS. Traverse the graph for all node to find the quadrangles for a certain depth. To remove duplicates, sort the quadrangles then remove the quadrangles or use hash table. My c++ implementation is given below:
#include<bits/stdc++.h>
using namespace std;
// if Edge[a][b] = 1, then there is an edge between node 'a' and 'b'
int Edge[100][100] = {0};
// to keep the list of quadrangles
// here 'set' is a data structure that keep unique elements
set< vector<int> > quadrangles;
// forbiddenNode[n] = 1, if this node 'n' is forbidden to visit
// forbiddenNode[n] = 0, if this node 'n' is not forbidden to visit
int forbiddenNode[100]={0};
// taken[n] = 1, if this node 'n' is taken in current Quadrangles
// taken[n] = 0, if this node 'n' is not taken in current Quadrangles
int taken[1000]={0};
void AddQuadrangle(vector<int> q) {
sort(q.begin(), q.end());
quadrangles.insert(q);
}
void findQuadrangles(int curNode, int depth, vector<int> &curQuadrangles, int numOfNodes) {
if(depth == 0) {
if( Edge[curNode][curQuadrangles[0]] == 1) {
// found a quadrangle
AddQuadrangle(curQuadrangles);
}
}
for(int i = 1; i <= numOfNodes; i++) {
if(forbiddenNode[i] == 0 && taken[i] == 0 && Edge[curNode][i] == 1) {
// take this node
taken[i] = 1;
// add this node to curQuadrangles in the back
curQuadrangles.push_back(i);
findQuadrangles(i, depth - 1, curQuadrangles, numOfNodes);
// undo take this node
taken[i] = 0;
// remove this node to curQuadrangles from the back
curQuadrangles.pop_back();
}
}
}
int main() {
int numOfNodes, numOfEdge;
// take input for number of nodes, edges
scanf("%d %d", &numOfNodes, &numOfEdge);
// take input for edges
for(int i=0; i < numOfEdge; i++) {
int x, y;
scanf("%d %d",&x, &y);
Edge[x][y] = 1;
Edge[y][x] = 1;
}
for(int i = 1; i <= numOfNodes; i++) {
vector<int> curQuadrangle;
curQuadrangle.push_back(i);
taken[i] = 1;
findQuadrangles(i, 3, curQuadrangle, numOfNodes);
// set this node as forbidden to include in any quadrangle
forbiddenNode[i];
}
// print quadrangles
for( set<vector<int> >::iterator it = quadrangles.begin(); it != quadrangles.end(); it++) {
vector<int> q = *it;
printf("%d %d %d %dn",q[0], q[1], q[2], q[3]);
}
return 0;
}
answered Nov 20 '18 at 11:02
nightfury1204
1,43048
Thanks. I will take a read for your code. I am doubting that, there will be any "smart/elegant" way to fulfill my purpose WITHOUT using any special data structure like stack, hash-table (or hashmap) or queue,etc. Or in other words, avoiding the "deleting duplicates" process.
– ZPascal
Nov 20 '18 at 18:45
The following is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs).
– ZPascal
Nov 20 '18 at 18:50
add a comment |
0
I have another approach to find the quadrangles. It's using the concept of DFS. Traverse the graph for all node to find the quadrangles for a certain depth. To remove duplicates, sort the quadrangles then remove the quadrangles or use hash table. My c++ implementation is given below:
#include<bits/stdc++.h>
using namespace std;
// if Edge[a][b] = 1, then there is an edge between node 'a' and 'b'
int Edge[100][100] = {0};
// to keep the list of quadrangles
// here 'set' is a data structure that keep unique elements
set< vector<int> > quadrangles;
// forbiddenNode[n] = 1, if this node 'n' is forbidden to visit
// forbiddenNode[n] = 0, if this node 'n' is not forbidden to visit
int forbiddenNode[100]={0};
// taken[n] = 1, if this node 'n' is taken in current Quadrangles
// taken[n] = 0, if this node 'n' is not taken in current Quadrangles
int taken[1000]={0};
void AddQuadrangle(vector<int> q) {
sort(q.begin(), q.end());
quadrangles.insert(q);
}
void findQuadrangles(int curNode, int depth, vector<int> &curQuadrangles, int numOfNodes) {
if(depth == 0) {
if( Edge[curNode][curQuadrangles[0]] == 1) {
// found a quadrangle
AddQuadrangle(curQuadrangles);
}
}
for(int i = 1; i <= numOfNodes; i++) {
if(forbiddenNode[i] == 0 && taken[i] == 0 && Edge[curNode][i] == 1) {
// take this node
taken[i] = 1;
// add this node to curQuadrangles in the back
curQuadrangles.push_back(i);
findQuadrangles(i, depth - 1, curQuadrangles, numOfNodes);
// undo take this node
taken[i] = 0;
// remove this node to curQuadrangles from the back
curQuadrangles.pop_back();
}
}
}
int main() {
int numOfNodes, numOfEdge;
// take input for number of nodes, edges
scanf("%d %d", &numOfNodes, &numOfEdge);
// take input for edges
for(int i=0; i < numOfEdge; i++) {
int x, y;
scanf("%d %d",&x, &y);
Edge[x][y] = 1;
Edge[y][x] = 1;
}
for(int i = 1; i <= numOfNodes; i++) {
vector<int> curQuadrangle;
curQuadrangle.push_back(i);
taken[i] = 1;
findQuadrangles(i, 3, curQuadrangle, numOfNodes);
// set this node as forbidden to include in any quadrangle
forbiddenNode[i];
}
// print quadrangles
for( set<vector<int> >::iterator it = quadrangles.begin(); it != quadrangles.end(); it++) {
vector<int> q = *it;
printf("%d %d %d %dn",q[0], q[1], q[2], q[3]);
}
return 0;
}
answered Nov 20 '18 at 11:02
nightfury1204
1,43048
Thanks. I will take a read for your code. I am doubting that, there will be any "smart/elegant" way to fulfill my purpose WITHOUT using any special data structure like stack, hash-table (or hashmap) or queue,etc. Or in other words, avoiding the "deleting duplicates" process.
– ZPascal
Nov 20 '18 at 18:45
The following is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs).
– ZPascal
Nov 20 '18 at 18:50
add a comment |
0
0
0
I have another approach to find the quadrangles. It's using the concept of DFS. Traverse the graph for all node to find the quadrangles for a certain depth. To remove duplicates, sort the quadrangles then remove the quadrangles or use hash table. My c++ implementation is given below:
#include<bits/stdc++.h>
using namespace std;
// if Edge[a][b] = 1, then there is an edge between node 'a' and 'b'
int Edge[100][100] = {0};
// to keep the list of quadrangles
// here 'set' is a data structure that keep unique elements
set< vector<int> > quadrangles;
// forbiddenNode[n] = 1, if this node 'n' is forbidden to visit
// forbiddenNode[n] = 0, if this node 'n' is not forbidden to visit
int forbiddenNode[100]={0};
// taken[n] = 1, if this node 'n' is taken in current Quadrangles
// taken[n] = 0, if this node 'n' is not taken in current Quadrangles
int taken[1000]={0};
void AddQuadrangle(vector<int> q) {
sort(q.begin(), q.end());
quadrangles.insert(q);
}
void findQuadrangles(int curNode, int depth, vector<int> &curQuadrangles, int numOfNodes) {
if(depth == 0) {
if( Edge[curNode][curQuadrangles[0]] == 1) {
// found a quadrangle
AddQuadrangle(curQuadrangles);
}
}
for(int i = 1; i <= numOfNodes; i++) {
if(forbiddenNode[i] == 0 && taken[i] == 0 && Edge[curNode][i] == 1) {
// take this node
taken[i] = 1;
// add this node to curQuadrangles in the back
curQuadrangles.push_back(i);
findQuadrangles(i, depth - 1, curQuadrangles, numOfNodes);
// undo take this node
taken[i] = 0;
// remove this node to curQuadrangles from the back
curQuadrangles.pop_back();
}
}
}
int main() {
int numOfNodes, numOfEdge;
// take input for number of nodes, edges
scanf("%d %d", &numOfNodes, &numOfEdge);
// take input for edges
for(int i=0; i < numOfEdge; i++) {
int x, y;
scanf("%d %d",&x, &y);
Edge[x][y] = 1;
Edge[y][x] = 1;
}
for(int i = 1; i <= numOfNodes; i++) {
vector<int> curQuadrangle;
curQuadrangle.push_back(i);
taken[i] = 1;
findQuadrangles(i, 3, curQuadrangle, numOfNodes);
// set this node as forbidden to include in any quadrangle
forbiddenNode[i];
}
// print quadrangles
for( set<vector<int> >::iterator it = quadrangles.begin(); it != quadrangles.end(); it++) {
vector<int> q = *it;
printf("%d %d %d %dn",q[0], q[1], q[2], q[3]);
}
return 0;
}
answered Nov 20 '18 at 11:02
nightfury1204
1,43048
I have another approach to find the quadrangles. It's using the concept of DFS. Traverse the graph for all node to find the quadrangles for a certain depth. To remove duplicates, sort the quadrangles then remove the quadrangles or use hash table. My c++ implementation is given below:
#include<bits/stdc++.h>
using namespace std;
// if Edge[a][b] = 1, then there is an edge between node 'a' and 'b'
int Edge[100][100] = {0};
// to keep the list of quadrangles
// here 'set' is a data structure that keep unique elements
set< vector<int> > quadrangles;
// forbiddenNode[n] = 1, if this node 'n' is forbidden to visit
// forbiddenNode[n] = 0, if this node 'n' is not forbidden to visit
int forbiddenNode[100]={0};
// taken[n] = 1, if this node 'n' is taken in current Quadrangles
// taken[n] = 0, if this node 'n' is not taken in current Quadrangles
int taken[1000]={0};
void AddQuadrangle(vector<int> q) {
sort(q.begin(), q.end());
quadrangles.insert(q);
}
void findQuadrangles(int curNode, int depth, vector<int> &curQuadrangles, int numOfNodes) {
if(depth == 0) {
if( Edge[curNode][curQuadrangles[0]] == 1) {
// found a quadrangle
AddQuadrangle(curQuadrangles);
}
}
for(int i = 1; i <= numOfNodes; i++) {
if(forbiddenNode[i] == 0 && taken[i] == 0 && Edge[curNode][i] == 1) {
// take this node
taken[i] = 1;
// add this node to curQuadrangles in the back
curQuadrangles.push_back(i);
findQuadrangles(i, depth - 1, curQuadrangles, numOfNodes);
// undo take this node
taken[i] = 0;
// remove this node to curQuadrangles from the back
curQuadrangles.pop_back();
}
}
}
int main() {
int numOfNodes, numOfEdge;
// take input for number of nodes, edges
scanf("%d %d", &numOfNodes, &numOfEdge);
// take input for edges
for(int i=0; i < numOfEdge; i++) {
int x, y;
scanf("%d %d",&x, &y);
Edge[x][y] = 1;
Edge[y][x] = 1;
}
for(int i = 1; i <= numOfNodes; i++) {
vector<int> curQuadrangle;
curQuadrangle.push_back(i);
taken[i] = 1;
findQuadrangles(i, 3, curQuadrangle, numOfNodes);
// set this node as forbidden to include in any quadrangle
forbiddenNode[i];
}
// print quadrangles
for( set<vector<int> >::iterator it = quadrangles.begin(); it != quadrangles.end(); it++) {
vector<int> q = *it;
printf("%d %d %d %dn",q[0], q[1], q[2], q[3]);
}
return 0;
}
answered Nov 20 '18 at 11:02
nightfury1204
1,43048
answered Nov 20 '18 at 11:02
nightfury1204
1,43048
answered Nov 20 '18 at 11:02
nightfury1204
1,43048
answered Nov 20 '18 at 11:02
nightfury1204
1,43048
1,43048
Thanks. I will take a read for your code. I am doubting that, there will be any "smart/elegant" way to fulfill my purpose WITHOUT using any special data structure like stack, hash-table (or hashmap) or queue,etc. Or in other words, avoiding the "deleting duplicates" process.
– ZPascal
Nov 20 '18 at 18:45
The following is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs).
– ZPascal
Nov 20 '18 at 18:50
add a comment |
Thanks. I will take a read for your code. I am doubting that, there will be any "smart/elegant" way to fulfill my purpose WITHOUT using any special data structure like stack, hash-table (or hashmap) or queue,etc. Or in other words, avoiding the "deleting duplicates" process.
– ZPascal
Nov 20 '18 at 18:45
The following is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs).
– ZPascal
Nov 20 '18 at 18:50
Thanks. I will take a read for your code. I am doubting that, there will be any "smart/elegant" way to fulfill my purpose WITHOUT using any special data structure like stack, hash-table (or hashmap) or queue,etc. Or in other words, avoiding the "deleting duplicates" process.
– ZPascal
Nov 20 '18 at 18:45
Thanks. I will take a read for your code. I am doubting that, there will be any "smart/elegant" way to fulfill my purpose WITHOUT using any special data structure like stack, hash-table (or hashmap) or queue,etc. Or in other words, avoiding the "deleting duplicates" process.
– ZPascal
Nov 20 '18 at 18:45
The following is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs).
– ZPascal
Nov 20 '18 at 18:50
The following is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs).
– ZPascal
Nov 20 '18 at 18:50
add a comment |
0
Here is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs):
clc;
v = vertex(:,1);
t = vertex(:,2);
G = zeros( max(max(v),max(t)));
n = length(G);
% For multi-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)); % comment here is input is bi-directional
end
quad_cnt = 0;
quad_points = ;
for i = 1:n
for j = i+1:n
if (j==i || G(j,i)==0)
continue;
end
for k = i+1:n
if ( k==i || k==j || (G(k,i)==0 && G(k,j)==0))
continue;
end
if (G(k,i)~=0 && G(k,j)~=0)
for p = i+1:n
if ( p==i || p==j || p==k)
continue;
end
if (G(p,i)~=0 && G(p,j)~=0)||(G(p,i)~=0 && G(p,k)~=0)||(G(p,j)~=0 && G(p,k)~=0)
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
end
if (G(k,i)==0 && G(k,j)~=0)
for p = i+1:n
if (p==i || p==j || p==k || G(p,k)==0 || G(p,i) == 0)
continue;
end
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
if (G(k,i)~=0 && G(k,j)==0)
for p = i+1:n
if ( p==i || p==j || p==k || G(p,j)==0 || G(p,k) == 0)
continue;
end
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
end
end
end
% quad_cnt
% Remove repeat
% 1) sort
hash = ;
Base = max(max(v),max(t))+ 1;
for i =1: quad_cnt
temp = sort(quad_points(i,:));
quad_points(i,:) = temp;
hash(i) = quad_points(i,1)*Base^3 + quad_points(i,2)*Base^2 + quad_points(i,3)*Base + quad_points(i,4);
end
% 2) remove repeats
[C, ~, ~] = unique(hash);
quad_cnt = length(C);
quad_cnt
quad_points = ;
for i = 1: quad_cnt
num = C(i);
digit = ;
for k = 1:4
digit(k) = mod(num, Base);
num = fix(num/Base); % or use "floor()"
end
quad_points(i,:) = digit;
end
% output each quadrangle:
quad_points;
answered Nov 20 '18 at 18:56
ZPascal
111
add a comment |
0
Here is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs):
clc;
v = vertex(:,1);
t = vertex(:,2);
G = zeros( max(max(v),max(t)));
n = length(G);
% For multi-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)); % comment here is input is bi-directional
end
quad_cnt = 0;
quad_points = ;
for i = 1:n
for j = i+1:n
if (j==i || G(j,i)==0)
continue;
end
for k = i+1:n
if ( k==i || k==j || (G(k,i)==0 && G(k,j)==0))
continue;
end
if (G(k,i)~=0 && G(k,j)~=0)
for p = i+1:n
if ( p==i || p==j || p==k)
continue;
end
if (G(p,i)~=0 && G(p,j)~=0)||(G(p,i)~=0 && G(p,k)~=0)||(G(p,j)~=0 && G(p,k)~=0)
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
end
if (G(k,i)==0 && G(k,j)~=0)
for p = i+1:n
if (p==i || p==j || p==k || G(p,k)==0 || G(p,i) == 0)
continue;
end
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
if (G(k,i)~=0 && G(k,j)==0)
for p = i+1:n
if ( p==i || p==j || p==k || G(p,j)==0 || G(p,k) == 0)
continue;
end
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
end
end
end
% quad_cnt
% Remove repeat
% 1) sort
hash = ;
Base = max(max(v),max(t))+ 1;
for i =1: quad_cnt
temp = sort(quad_points(i,:));
quad_points(i,:) = temp;
hash(i) = quad_points(i,1)*Base^3 + quad_points(i,2)*Base^2 + quad_points(i,3)*Base + quad_points(i,4);
end
% 2) remove repeats
[C, ~, ~] = unique(hash);
quad_cnt = length(C);
quad_cnt
quad_points = ;
for i = 1: quad_cnt
num = C(i);
digit = ;
for k = 1:4
digit(k) = mod(num, Base);
num = fix(num/Base); % or use "floor()"
end
quad_points(i,:) = digit;
end
% output each quadrangle:
quad_points;
answered Nov 20 '18 at 18:56
ZPascal
111
add a comment |
0
0
0
Here is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs):
clc;
v = vertex(:,1);
t = vertex(:,2);
G = zeros( max(max(v),max(t)));
n = length(G);
% For multi-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)); % comment here is input is bi-directional
end
quad_cnt = 0;
quad_points = ;
for i = 1:n
for j = i+1:n
if (j==i || G(j,i)==0)
continue;
end
for k = i+1:n
if ( k==i || k==j || (G(k,i)==0 && G(k,j)==0))
continue;
end
if (G(k,i)~=0 && G(k,j)~=0)
for p = i+1:n
if ( p==i || p==j || p==k)
continue;
end
if (G(p,i)~=0 && G(p,j)~=0)||(G(p,i)~=0 && G(p,k)~=0)||(G(p,j)~=0 && G(p,k)~=0)
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
end
if (G(k,i)==0 && G(k,j)~=0)
for p = i+1:n
if (p==i || p==j || p==k || G(p,k)==0 || G(p,i) == 0)
continue;
end
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
if (G(k,i)~=0 && G(k,j)==0)
for p = i+1:n
if ( p==i || p==j || p==k || G(p,j)==0 || G(p,k) == 0)
continue;
end
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
end
end
end
% quad_cnt
% Remove repeat
% 1) sort
hash = ;
Base = max(max(v),max(t))+ 1;
for i =1: quad_cnt
temp = sort(quad_points(i,:));
quad_points(i,:) = temp;
hash(i) = quad_points(i,1)*Base^3 + quad_points(i,2)*Base^2 + quad_points(i,3)*Base + quad_points(i,4);
end
% 2) remove repeats
[C, ~, ~] = unique(hash);
quad_cnt = length(C);
quad_cnt
quad_points = ;
for i = 1: quad_cnt
num = C(i);
digit = ;
for k = 1:4
digit(k) = mod(num, Base);
num = fix(num/Base); % or use "floor()"
end
quad_points(i,:) = digit;
end
% output each quadrangle:
quad_points;
answered Nov 20 '18 at 18:56
ZPascal
111
Here is my updated MATLAB code that works (you are welcome to test my code to see if it fails on any special graphs):
clc;
v = vertex(:,1);
t = vertex(:,2);
G = zeros( max(max(v),max(t)));
n = length(G);
% For multi-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)); % comment here is input is bi-directional
end
quad_cnt = 0;
quad_points = ;
for i = 1:n
for j = i+1:n
if (j==i || G(j,i)==0)
continue;
end
for k = i+1:n
if ( k==i || k==j || (G(k,i)==0 && G(k,j)==0))
continue;
end
if (G(k,i)~=0 && G(k,j)~=0)
for p = i+1:n
if ( p==i || p==j || p==k)
continue;
end
if (G(p,i)~=0 && G(p,j)~=0)||(G(p,i)~=0 && G(p,k)~=0)||(G(p,j)~=0 && G(p,k)~=0)
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
end
if (G(k,i)==0 && G(k,j)~=0)
for p = i+1:n
if (p==i || p==j || p==k || G(p,k)==0 || G(p,i) == 0)
continue;
end
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
if (G(k,i)~=0 && G(k,j)==0)
for p = i+1:n
if ( p==i || p==j || p==k || G(p,j)==0 || G(p,k) == 0)
continue;
end
quad_cnt = quad_cnt+1;
quad_points(quad_cnt,:) = [i,j,k,p];
end
end
end
end
end
% quad_cnt
% Remove repeat
% 1) sort
hash = ;
Base = max(max(v),max(t))+ 1;
for i =1: quad_cnt
temp = sort(quad_points(i,:));
quad_points(i,:) = temp;
hash(i) = quad_points(i,1)*Base^3 + quad_points(i,2)*Base^2 + quad_points(i,3)*Base + quad_points(i,4);
end
% 2) remove repeats
[C, ~, ~] = unique(hash);
quad_cnt = length(C);
quad_cnt
quad_points = ;
for i = 1: quad_cnt
num = C(i);
digit = ;
for k = 1:4
digit(k) = mod(num, Base);
num = fix(num/Base); % or use "floor()"
end
quad_points(i,:) = digit;
end
% output each quadrangle:
quad_points;
answered Nov 20 '18 at 18:56
ZPascal
111
answered Nov 20 '18 at 18:56
ZPascal
111
answered Nov 20 '18 at 18:56
ZPascal
111
answered Nov 20 '18 at 18:56
ZPascal
111
111
add a comment |
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53379768%2fcount-unique-quadrangles%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Thanks. I deliberately "let" the index number become larger in the next iteration loop every time -- because if you don't do that, in some graph, repeated solutions will be found together. However, ironically, this way cannot handle case-2 as I listed above, where no solution can be found. You can drawn the graph for both the cases I listed and you will get the point.
– ZPascal
Nov 19 '18 at 17:57
Good point. I'll try again. For each vertex ('start'), for each pair of nodes connected to 'start' ('neighbors'), find a node connected to both 'neighbors' ('end'), where the node numbers for 'neighbors' and 'end' are all greater than the node number for 'start'.
– user3386109
Nov 19 '18 at 18:34
I figure out a non-elegant way: 1. Find all (allowing non-unique) sequence of quadrangles,suppose the number is N; 2. Sort all the sequences, O(N log4) = O(N) 3. Detect and remove repeated sequence, Many tricks can be applied in this step, e.g. map [1,2,3,4] to 1234 and hash it. But, I am still expecting anyone can provide a straightforward and elegant algorithm.
– ZPascal
Nov 19 '18 at 20:35