In line with this, here is a proposal for detecting unique set of vertices in a graph cycle for your review. It only detects cycles with 4 or more vertices and removes duplicates. igraph already incorporate functions to deal with triangles. It's a first draft and I believe it can potentially be optimized.
library(igraph)
#---------------------------------------------------------------------------------------------
#Flags all edges within a graph, part of a cycle |
# Approach: subgraph_isomorphisms(make_ring()) |
#---------------------------------------------------------------------------------------------
find_cycles <- function(g) {
E(g)$cycle = 0
# Simplify & decompose graph in disconnected components
simplg = simplify(g, remove.multiple=TRUE, remove.loops = TRUE)
list_cycles <- list()
componentSet <- decompose(simplg, min.vertices = 4)
print(length(componentSet))
l = 1
#list cycles through subgraph isomorphism to ring(>4) mapping
for (i in 1:length(componentSet))
{
print(sprintf("component: %i of size %i", i, length(V(componentSet[[i]]))))
for(j in 4:length(V(componentSet[[i]])))
{
print(sprintf("Trying to match against ring of size: %i", j))
a = subgraph_isomorphisms(make_ring(j), componentSet[[i]], method=c("vf2"))
print("Isomorphism count: ")
print(length(a))
if(length(a) != 0)
for(k in 1:length(a))
{
list_cycles[[l]] = a[[k]]$name
l = l+1
#print(sprintf("cycle item: %i", length(list_cycles)))
}
}
}
#Dedup Cycles
list_cycles_dedup <- list()
list_cycles_dedup[[1]] = sort(list_cycles[[1]])
z = 2
for(x in 2:length(list_cycles))
{
a = sort(list_cycles[[x]])
found_flag = FALSE
print(sprintf("x = %i; checking...", x))
print(a)
for(y in 1:length(list_cycles_dedup))
{
print("against")
print(list_cycles_dedup[[y]])
if(all(a == list_cycles_dedup[[y]]))
{
found_flag = TRUE
break
}
}
if(found_flag==FALSE)
{
print("not found")
list_cycles_dedup[[z]] = a
z = z + 1
}
}
return(list_cycles_dedup)
#return(list_cycles)
}
And to test it:
a = make_ring(5)
b = make_star(10, mode="undirected", center="5")
c = union(a,b,byname="auto")
V(c)$name = c("A","B","C","D","E","F","G","H","I","J")
d = find_cycles(c)
Only constraint so far is to define vertices names.
Please let me know how it goes.
Lookman