Hi Tamas, 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 On Tue, Jan 8, 2019 at 6:25 PM Tamas Nepusz <nta...@gmail.com> wrote: > > Out of curiosity... There is an extensive set of functions in igraph > dealing with paths but not with circuits. Why is that? > Well, igraph's development direction was always partly determined by > the personal needs of Gábor Csárdi and me when we were working as > researchers in network science. We did not really have many use-cases > for circuits, so these parts of graph theory were mostly left > untouched. Feel free to contribute implementations if you can dedicate > the time and effort to do it -- I'll be happy to review code addition > proposals. > > All the best, > Tamás > > _______________________________________________ > igraph-help mailing list > igraph-help@nongnu.org > https://lists.nongnu.org/mailman/listinfo/igraph-help > -- Lookman SANNI
_______________________________________________ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help