I was trying to find an euler cycle from a balanced (for every node, indegree=outdegree) directed graph in R. Firstly, I tried the PairViz package. However, it works only for undirected even (every node has even degree) graph. I posted in
StackOverflow too, but I found that the solution is not readily available. So, I implemented the algorithm as below.
library(graph)
eulerCycle <- function(g, start=NULL){
eulerCycle <- c()
curNode <- ifelse(is.null(start), nodes(g)[1], start)
while(!is.na(curNode)){
cycle <- curNode
while(!is.na(nextNode <- randomWalkNext(g, curNode))){
g <- removeEdge(graph=g, from=curNode, to=nextNode)
cycle <- append(cycle, nextNode)
curNode <- nextNode
}
if(length(eulerCycle)==0){
eulerCycle <- cycle
}
else{
insertIndex <- which(eulerCycle==cycle[1])[1]
eulerCycle <- append(eulerCycle,after=insertIndex,values=cycle[-1])
}
curNode <- getAnUnexploredNode(g, nodes=eulerCycle)
}
return(eulerCycle)
}
getAnUnexploredNode <- function(g, nodes){
degrees <- degree(g, Nodes=nodes)
nodeIndexes <- which(degrees$outDegree+degrees$inDegree>0)
node <- NA
if(length(nodeIndexes)>0){
node <- nodes[nodeIndexes[1]]
}
return(node)
}
randomWalkNext <- function(g, from){
outEdges <- edges(object=g, which=from)[[1]]
nextNode <- NA
if(length(outEdges)>0){
nextNode <- outEdges[1]
}
return(nextNode)
}
Verification Code:
> g <- new("graphNEL", nodes=as.character(1:10), edgemode="directed")
> g <- addEdge(graph=g, from="1", to="10")
> g <- addEdge(graph=g, from="2", to="1")
> g <- addEdge(graph=g, from="2", to="6")
> g <- addEdge(graph=g, from="3", to="2")
> g <- addEdge(graph=g, from="4", to="2")
> g <- addEdge(graph=g, from="5", to="4")
> g <- addEdge(graph=g, from="6", to="5")
> g <- addEdge(graph=g, from="6", to="8")
> g <- addEdge(graph=g, from="7", to="9")
> g <- addEdge(graph=g, from="8", to="7")
> g <- addEdge(graph=g, from="9", to="6")
> g <- addEdge(graph=g, from="10", to="3")
>
> ec <- eulerCycle(g, start="6")
> print(ec)
[1] "6" "5" "4" "2" "1" "10" "3" "2" "6" "8" "7" "9" "6"
Update:
I have published a R package at CRAN,
euler, to find eulerian paths from graphs.