I've created an undirected graph and extracted all the possible cycles inside it. I want just the simple cycles because I'm creating polygons from them. The problem is that I don't find an algorithm of how to do it. The following graph generates 6 possible cycles listed below which is working as intended.
int[][] graph = {{1, 2}, {1, 6}, {1, 5}, {2, 6}, {2, 3}, {3, 7}, {7, 4}, {3, 4}, {5, 4}};
1,6,2
1,5,4,7,3,2
1,5,4,3,2
1,5,4,7,3,2,6
1,5,4,3,2,6
3,4,7
How do I extract only the simple cycles from here? I've tried with the following code that removes all the cycles that contains another smaller cycle but I'm aware that the logic here isn't what I want because the result was: 1,6,2 1,5,4,3,2 3,4,7
when it should be 1,6,2 1,5,4,7,3,2,6 3,4,7
.
static void cleanMultiples() {
Set<Integer> toRemove = new HashSet<>();
for (int i = 0; i < cycles.size(); i++) {
for (int j = 0; j < cycles.size(); j++) {
if (j == i) {
continue;
}
Set<Integer> s = new HashSet<>();
for (int k = 0; k < cycles.get(i).length; k++) {
s.add(cycles.get(i)[k]);
}
int p = s.size();
for (int k = 0; k < cycles.get(j).length; k++) {
s.add(cycles.get(j)[k]);
}
if (s.size() == p) {
toRemove.add(i);
}
}
}
List<Integer> list = new LinkedList<>(toRemove);
Collections.sort(list);
Collections.reverse(list);
list.forEach((t) -> {
cycles.remove(t.intValue());
});
if(!toRemove.isEmpty()){
cleanMultiples();
}
}