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"
No comments:
Post a Comment