How to plan the most efficient route for patio lights

Question

I'm trying to string up some patio lights. Based on another question I asked, I realize I need an algorithm to solve a Route Inspection Problem to figure out the most efficient route the lights should take so there's minimal duplicate edges covered with lights. After some searching I realized that perhaps something like this would be my best bet: Solving Chinese Postman algorithm with eulerization.

However, I'm having trouble creating the graph.

Here's what it needs to look like:

pink circles represent places in the structure I can hang lights from
"Start" is the only available electrical outlet
The yellow dots represent all the places lights should cover

And here's what my graph looks like after referencing this post: Visualizing distance between nodes according to weights - with R:

As you can see, all the nodes are in the correct place, but the edges are connecting where they shouldn't connect. Here's my code:

library(igraph)
gg<-graph.ring(20)
ll=matrix(
  c( 0,0,    75.25,0,    150.5,0,    225.8125,0,    302.8125,0, 
     0,-87,                                          302.8125,-87,
     0,-173.8125,                                    302.8125,-173.8125,
     0,-260.9375,                                    302.8125,-260.9375,
     16,-384.3125,                                   302.8125,-384.3125,
     16,-435.9575,                                   302.8125,-435.9375,
     16,-525.1875, 75.25,-525.1875, 150.5,-525.1875, 225.8125,-525.1875, 302.8175,-525.1875),
  ncol=2,byrow=TRUE)
plot(gg,layout=ll)

I think this has something to do with the nature of graph.ring, but I am unable to figure out another way to define the graphs' edges' lengths without error.

Damiano Fantini · Answer 1 · 2017-08-17T17:28:42.113

I think you can use graph_from_edgelist for a precise specification of which nodes to connect. It is sufficient to specify which nodes to connect in which order. Nice question btw!

  gg <- graph_from_edgelist(cbind(c(1:4, 6, 8, 10, 12, 14, 16:19, 1, 6, 8, 21, 12, 14, 5, 7, 9, 11, 13, 15), 
                                  c(2:5, 7, 9, 11, 13, 15, 17:20, 6, 8, 10, 12, 14, 16, 7, 9, 11, 13, 15, 20)))
  ll=matrix(
    c( 0,0,    75.25,0,    150.5,0,    225.8125,0,    302.8125,0, 
       0,-87,                                          302.8125,-87,
       0,-173.8125,                                    302.8125,-173.8125,
       0,-260.9375,                                    302.8125,-260.9375,
       16,-384.3125,                                   302.8125,-384.3125,
       16,-435.9575,                                   302.8125,-435.9375,
       16,-525.1875, 75.25,-525.1875, 150.5,-525.1875, 225.8125,-525.1875, 302.8175,-525.1875, 16, -260.9375),
    ncol=2,byrow=TRUE)
  plot(gg,layout=ll, edge.arrow.size = 0, vertex.size = c(rep(18, 20), 0),
       edge.color="orange")

I added a node (n 21) to allow a branching that is similar to your scheme. Does this look more or less as it should?

I had a look at the previous post on Stack Overflow (the one you suggested) to try making this an Euler cycle. Actually, the custom function does work out of the box, but you may want to double check if you can use the resulting solution or not. Maybe, you could try defining a better connection design before "eulerizing" the circuit. This is what I got.

# load custom f(x) as in
# https://stackoverflow.com/questions/40576910/solving-chinese-postman-algorithm-with-eulerization/40596816#40596816

eulerian <- make.eulerian(gg)
eulerian$info
g <- eulerian$graph

# set the layout as before to keep the circuit formatted according to your specs
par(mfrow=c(1,2))
plot(gg,layout=ll, edge.arrow.size = 0, vertex.size = c(rep(18, 20), 0),
     edge.color="orange", main = "Proposed")
plot(g,layout=ll, edge.arrow.size = 0, vertex.size = c(rep(18, 20), 0),
     edge.color="orange", main = "Eulerized")

Yes, that is exactly it! Thanks! However, how can I make this into a graph object, which can be used for this: `eulerian.g1 <- make.eulerian(g1)$graph`, where `g1` is the graph? (from this post about solving Postman Problems: https://stackoverflow.com/a/40596816/1152809) — Travis Heeter, Aug 17 '17 at 03:50
Interesting, I was not aware of that. So, you'd like to make eulerian a cycle that is not eulerian per se. I'll look into that. The custom f(x) is not working out of the box in my hands.. But I'll look into this tomorrow morning! :-) — Damiano Fantini, Aug 17 '17 at 04:04
Yeah, I'm not sure why it doesn't work out of the box, but if you check that question: https://stackoverflow.com/a/40596816/1152809, the accepted answer gives a `make.eulerian` replacement you can use. I basically copy/pasted it, then did this: `eulerian<-make.eulerian(gg); g<-eulerian$graph; par(mfrow=c(1,2)); plot(gg); plot(g)`. However, I'm not sure if that's what I need because it doesn't seem to account for the structure (all the edge lengths). — Travis Heeter, Aug 17 '17 at 04:11

How to plan the most efficient route for patio lights

1 Answers1

Linked