February 14, 2014

How to find an euler cycle from a balanced directed graph in R

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.

No comments:

Post a Comment