Solving Chinese Postman algorithm with eulerizatio

Question

I'm would like to solve Chinese Postman problem in a graph where an eulerian cycle does not exist. So basically I'm looking for a path in a graph which visits every edge exactly once, and starts and ends at the same node. A graph will have an euler cycle if and only if every node has same number of edges entering into and going out of it. Obviously my graph doesn't .

I found out that Eulerization (making a graph Eulerian) could solve my question LINK. Can anyone suggest a script to add duplicate edges to a graph so that the resulting graph has no vertices of odd degree (and thus does have an Euler Circuit)?

Here is my example:

require(igraph)
require(graph)
require(eulerian)
require(GA)
g1 <- graph(c(1,2, 1,3, 2,4, 2,5, 1,5, 3,5, 4,7, 5,7, 5,8, 3,6, 6,8, 6,9, 9,11, 8,11, 8,10, 8,12, 7,10, 10,12, 11,12), directed = FALSE)
mat <- get.adjacency(g1)
mat <- as.matrix(mat)
rownames(mat) <- LETTERS[1:12]
colnames(mat) <- LETTERS[1:12]
g2 <- as(graphAM(adjMat=mat), "graphNEL")
hasEulerianCycle(g2)

Answer 1

Fun problem.

The graph you sugest in the code above, can be made to have duplicates that enable a eulerian cycle to be created. The function I provide below tries to add the minimum amount of duplicate edges, but also readily breaks the graph structure by adding new links if it has to.

You can run:

eulerian.g1 <- make.eulerian(g1)$graph

Check what the function did to your graph with:

make.eulerian(g1)$info

Bare in mind that:

1. This is not the only graph structure where duplicates added to the original g1 graph can form an eulerian cycle. Imagine for example my function looping the vertices of the graph backwards instead.
2. Your graph already has an uneven number of vertices with uneven degree, and all of the vertices that are, have neighbours with uneven degrees to pair them with. This function therefore works well four your particular example data.
3. The function could fail to produce a graph using only duplicates even in graphs where eulerian cycles are possible with correctly added duplicates. This is since it always goes for connecting a node with the first of its neighbours with uneven degree. If this is something that you'd absolutely like to get around, an MCMC-approach would be the way to go.

See also this excellent answer on probability calculation:

Here's my function in a full script that you can source out-of-the-box:

library(igraph)

# You asked about this graph
g1 <- graph(c(1,2, 1,3, 2,4, 2,5, 1,5, 3,5, 4,7, 5,7, 5,8, 3,6, 6,8, 6,9, 9,11, 8,11, 8,10, 8,12, 7,10, 10,12, 11,12), directed = FALSE)

# Make a CONNECTED random graph with at least n nodes
connected.erdos.renyi.game <- function(n,m){
       graph <- erdos.renyi.game(n,m,"gnm",directed=FALSE)
       graph <- delete_vertices(graph, (degree(graph) == 0))
}

# This is a random graph
g2 <- connected.erdos.renyi.game(n=12, m=16)



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(g1)
eulerian$info
g <- eulerian$graph

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