Re: [igraph] Chinese Postman Problem with igraph?
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 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 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
___
igraph-help mailing list
igraph-help@nongnu.org
https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] Chinese Postman Problem with igraph?
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 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
Re: [igraph] Chinese Postman Problem with igraph?
> 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
Re: [igraph] Chinese Postman Problem with igraph?
On Tue, 8 Jan 2019 at 14:34, Victor Snesarev wrote: > > Out of curiosity... There is an extensive set of functions in igraph dealing > with paths but not with circuits. Why is that? Is it simply because circuits > are not very useful for problems people use igraph to solve? > You are very welcome to contribute implementations if you are interested in this topic. I think it is a good fit for igraph. Personally, I am happy to help you (or anyone else) get started if you are not yet familiar with the code base. ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] Chinese Postman Problem with igraph?
Sounds like you're describing the Hierholzer's algorithm. Thank you, Tamas! That answers my question. Out of curiosity... There is an extensive set of functions in igraph dealing with paths but not with circuits. Why is that? Is it simply because circuits are not very useful for problems people use igraph to solve? -SD On Tue, Jan 8, 2019 at 6:05 AM Tamas Nepusz wrote: > > 6: Modify the graph by adding all the edges that have been found in > step 5. > > SD: igraph_add_vertices() > igraph_add_edges(), most likely > > > 8: Print Euler Circuit of the modified graph. This Euler Circuit is > Chinese Postman Tour. > > SD: I cannot find any functions that, given a starting vertex, calculate > a circuit, a tour, or a closed path. Recommendations? > There is no such function, but if there is an Euler circuit in the > graph, all you need to do is to start from anywhere, and keep on > following any unvisited edge going outwards from the current vertex, > marking the edge as "visited" while doing so. If you get stuck > somewhere, then you have found the Euler circuit of the connected > component containing the start vertex. (If there are multiple > connected components, proceed with the next one). > > T. > > ___ > igraph-help mailing list > igraph-help@nongnu.org > https://lists.nongnu.org/mailman/listinfo/igraph-help > ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] Chinese Postman Problem with igraph?
> 6: Modify the graph by adding all the edges that have been found in step 5. > SD: igraph_add_vertices() igraph_add_edges(), most likely > 8: Print Euler Circuit of the modified graph. This Euler Circuit is Chinese > Postman Tour. > SD: I cannot find any functions that, given a starting vertex, calculate a > circuit, a tour, or a closed path. Recommendations? There is no such function, but if there is an Euler circuit in the graph, all you need to do is to start from anywhere, and keep on following any unvisited edge going outwards from the current vertex, marking the edge as "visited" while doing so. If you get stuck somewhere, then you have found the Euler circuit of the connected component containing the start vertex. (If there are multiple connected components, proceed with the next one). T. ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
[igraph] Chinese Postman Problem with igraph?
Hi, I am very new to graph theory, but I am interested in solving a real-world trail hiking problem using Chinese Postman Problem on a weighted undirected graph. Could someone help identify igraph functions for the steps? (especially the last one.) My guesses are on lines starting with "SD:". Algorithm to find shortest closed path or optimal Chinese postman route in a weighted graph that may not be Eulerian. 1: If graph is Eulerian,return sum of all edge weights.Else do following steps. SD: Check whether igraph_degree() returns even degree for every vertex in the graph. 2: We find all the vertices with odd degree SD: use vertex degrees from step one to find vertices with odd degree. 3: List all possible pairings of odd vertices. SD: no igraph necessary 4: For each set of pairings, find the shortest path connecting them. SD: igraph_shortest_paths_dijkstra() for pairings from step 3. 5: Find the pairing with minimum shortest path connecting pairs. SD: no igraph necessary 6: Modify the graph by adding all the edges that have been found in step 5. SD: igraph_add_vertices() 7: Weight of Chinese Postman Tour is sum of all edges in the modified graph. SD: sum all weights of all edges 8: Print Euler Circuit of the modified graph. This Euler Circuit is Chinese Postman Tour. SD: I cannot find any functions that, given a starting vertex, calculate a circuit, a tour, or a closed path. Recommendations? Thanks in advance! P.S. Steps are copied from https://www.geeksforgeeks.org/chinese-postman-route-inspection-set-1-introduction/ ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
