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 <[email protected]> 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
> [email protected]
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
--
Lookman SANNI
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
