How to plan the most efficient route for patio lights Part 2

Question

This is a continuation of some questions I posed earlier, How to plan the most efficient route for patio lights and Christmas Light Route Efficiency (CS), about my attempt to cover a screened-in structure with patio lights as efficiently as possible.

Here's the rules:

• Minimize light overlapping
• Each string of lights is 234" long (this is important because I can't start a new branch of lights unless it's at the end of another branch).

• Think of these as Christmas lights, you have a male and a female side:

  start (male) end (female) =[}~~~o~~~o~~~o~~~o~~~o~~~o~~~o~~~{=] <- to outlet to other lights ->

  So multiple strands can daisy chain as long as there's a female for the male to plug into, like this:

  

• A female plug must supply power to the next strand of lights via a male plug, a male plug can't give power to another male plug.

• Here is a diagram of my structure:

  

• Pink Circle = Place to hang lights (No, there is not a place to hang lights at the intersection of 10, 11 & 12 - that is not a mistake).

• "Start" = The only available electrical outlet.
• Yellow Dots = Parts of the structure I want to run the lights along.

---

Based on my previous questions, I began looking into "Route Efficiency Problem" Algorithms. I used this post, Solving Chinese Postman algorithm with eulerization, to get started, which lead me to this code (with thanks to @DamianoFantini for his help in my previous post to set the graph up correctly):

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)

# SOURCE: https://stackoverflow.com/q/40576910/1152809
make.eulerian <- function(graph){
  # Carl Hierholzer (1873) had explained how eulirian cycles exist for graphs that are
  # 1) connected, and 2) contain only vertecies with even degrees. Based on this proof
  # the posibility of an eulerian cycle existing in a graph can be tested by testing
  # on these two conditions.
  #
  # This function assumes a connected graph.
  # It adds edges to a graph to ensure that all nodes eventuall has an even numbered. It
  # tries to maintain the structure of the graph by primarily adding duplicates of already
  # existing edges, but can also add "structurally new" edges if the structure of the
  # graph does not allow.

  # save output
  info <- c("broken" = FALSE, "Added" = 0, "Successfull" = TRUE)

  # Is a number even
  is.even <- function(x){ x %% 2 == 0 }

  # Graphs with an even number of verticies with uneven degree will more easily converge
  # as eulerian.
  # Should we even out the number of unevenly degreed verticies?
  search.for.even.neighbor <- !is.even(sum(!is.even(degree(graph))))

  # Loop to add edges but never to change nodes that have been set to have even degree
  for(i in V(graph)){
    set.j <- NULL

    #neighbors of i with uneven number of edges are good candidates for new edges
    uneven.neighbors <- !is.even(degree(graph, neighbors(graph,i)))

    if(!is.even(degree(graph,i))){
      # This node needs a new connection. That edge e(i,j) needs an appropriate j:

      if(sum(uneven.neighbors) == 0){
        # There is no neighbor of i that has uneven degree. We will
        # have to break the graph structure and connect nodes that
        # were not connected before:

        if(sum(!is.even(degree(graph))) > 0){
          # Only break the structure if it's absolutely nessecary
          # to force the graph into a structure where an euclidian
          # cycle exists:
          info["Broken"] <- TRUE

          # Find candidates for j amongst any unevenly degreed nodes
          uneven.candidates <- !is.even(degree(graph, V(graph)))

          # Sugest a new edge between i and any node with uneven degree
          if(sum(uneven.candidates) != 0){
            set.j <- V(graph)[uneven.candidates][[1]]
          }else{
            # No candidate with uneven degree exists!

            # If all edges except the last have even degrees, thith
            # function will fail to make the graph eulerian:
            info["Successfull"] <- FALSE
          }
        }

      }else{
        # A "structurally duplicated" edge may be formed between i one of
        # the nodes of uneven degree that is already connected to it.

        # Sugest a new edge between i and its first neighbor with uneven degree
        set.j <- neighbors(graph, i)[uneven.neighbors][[1]]
      }
    }else if(search.for.even.neighbor == TRUE & is.null(set.j)){
      # This only happens once (probably) in the beginning of the loop of
      # treating graphs that have an uneven number of verticies with uneven
      # degree. It creates a duplicate between a node and one of its evenly
      # degreed neighbors (if possible)
      info["Added"] <- info["Added"] + 1

      set.j <- neighbors(graph, i)[ !uneven.neighbors ][[1]]
      # Never do this again if a j is correctly set
      if(!is.null(set.j)){search.for.even.neighbor <- FALSE}
    }

    # Add that a new edge to alter degrees in the desired direction
    # OBS: as.numeric() since set.j might be NULL
    if(!is.null(set.j)){
      # i may not link to j
      if(i != set.j){
        graph <- add_edges(graph, edges=c(i, set.j))
        info["Added"] <- info["Added"] + 1
      }
    }
  }

  # return the graph
  (list("graph" = graph, "info" = info))
}

# Look at what we did
eulerian <- make.eulerian(gg)
g <- eulerian$graph

par(mfrow=c(1,2))
plot(gg)
plot(g)

Here's the result of the code:

Which, I think translates to this (but I am a graph/algorithm noob, so correct me if I'm wrong):

Obviously, there are some issues here:

1. I have no idea where the end/beginning of each strand of lights should be (and neither does the algorithm I think)
2. Node 1 is supplying power independently. This will not work in reality. All power must come from the "Start" position.
3. The distances and structure do not seem to be accounted for.

Is there a way to add these constraints into the algorithm? Is there another algorithm I could use that would make this easier?

Answer 1

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

You can imeplement Dijkstra's algorithm using different edge data for different metrics for your path, such as light overlap, or for example, the total illuminance for the lights at each edge. I assume you might need a higher density of light in deep corners...

So the goal, can be the widest area of low light, or the perceived visibility of obstacles, or a path to which creates a homogenous ambient light. Regardless of how it is tuned though I believe Dijkstra's algorithm is a pretty standard goto for finding these things.

Update: In the case of creating the widest covered area of light you would want a spanning tree rather than an optimal path algorithm. This might be more of what you have in mind:

https://en.wikipedia.org/wiki/Prim%27s_algorithm