Re: [igraph] Chinese Postman Problem with igraph?

[Tamas Nepusz]

Hi,

Unfortunately we cannot include plain R code in the C core of the
igraph library because those functions would not be usable from the
Python and Mathematica interfaces. Ideally, we would need similar
functions implemented in pure C. Using subgraph isomorphism is
probably overkill for the _efficient_ detection of cycles, although it
could work for smaller graphs.

Also, in most practical cases there are far too many cycles in a
network to enumerate all of them in an array. A better approach is to
find and return a cycle basis of the network; with m nodes, n edges
and c connected components, there are only m - n + c cycles in a cycle
basis, and every cycle of the graph can be composed from the cycles in
the cycle basis using symmetric difference operations only. So, if I
were to implement something like this in the C core, I would probably
start with a cycle basis construction.

All the best,
Tamás

On Sat, 19 Jan 2019 at 02:01, lookman sanni <address@hidden> wrote:
>
> 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 <address@hidden> 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
>> address@hidden
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
> --
>
> Lookman SANNI
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help