Package 'eulerian'

eulerian: A package to handle eulerian paths from graphs

Description

An eulerian path is a path in a graph which visits every edge exactly once. This package provides methods to handle eulerian paths or cycles.

Examples

require(graph)
	require(eulerian)
	g <- new("graphNEL", nodes=LETTERS[1:4], edgemode="directed")
	g <- addEdge(graph=g, from=LETTERS[1:4], to=LETTERS[c(2:4,1)])
	if(hasEulerianCycle(g)){
		ecycle <- eulerian(g)
		writeLines(paste(ecycle, collapse=" -> "))
	}

---

Method for finding an eulerian path or cycle.

Description

An eulerian path is a path in a graph which visits every edge exactly once. This function returns an eulerian path from a graph (if there is any). It works for both directed and undirected graphs.

Usage

eulerian(graph, start = NULL)

Arguments

graph	a graphNEL object.
start	character or NULL. The name of the start node of an eulerian path.

Details

If start is not NULL, then eulerian returns a path starting from it. Otherwise, the start node is automatically selected.

Value

A character vector representing an eulerian path/cycle in graph. Each entry in the vector represents the name of a node in the graph.

Author(s)

Ashis Saha

Examples

require(graph)
	require(eulerian)
	g <- new("graphNEL", nodes=LETTERS[1:4], edgemode="uirected")
	g <- addEdge(graph=g, from=LETTERS[1:3], to=LETTERS[2:4])
	ep <- eulerian(g)
	
	g <- new("graphNEL", nodes=as.character(1:10), edgemode="directed")
	g <- addEdge(graph=g, from=c("1","2","2","3","4","5","6","6","7","8","9","10"), 
			to=c("10","1","6","2","2","4","5","8","9","7","6","3"))
	ep <- eulerian(g, "6")

---

Method for checking whether an eulerian cycle exists.

Description

An eulerian cycle is a path in a graph which visits every edge exactly once, and starts and ends at the same node.

Usage

hasEulerianCycle(graph)

Arguments

graph

a graphNEL object.

Details

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.

Value

TRUE, if graph has an auler cycle. FALSE, otherwise.

Author(s)

Ashis Saha

Examples

require(graph)
	require(eulerian)
	g <- new("graphNEL", nodes=LETTERS[1:4], edgemode="directed")
	g <- addEdge(graph=g, from=LETTERS[1:4], to=LETTERS[c(2:4,1)])
	hasEulerianCycle(g)

---

Method for checking whether an eulerian path exists.

Description

An eulerian path is a path in a graph which visits every edge exactly once.

Usage

hasEulerianPath(graph, start = NULL)

Arguments

graph	a graphNEL object.
start	character or NULL. The name of the start node of an eulerian path.

Details

If start is NULL, this function returns whether there exists any eulerian path in graph. If start is not NULL, the function determines if there exists an eulerian path starting from start.

Value

TRUE, if there is an eulerian path. FALSE, otherwise.

Author(s)

Ashis Saha

Examples

require(graph)
	require(eulerian)
	g <- new("graphNEL", nodes=LETTERS[1:4], edgemode="undirected")
	g <- addEdge(graph=g, from=LETTERS[c(1:4)], to=LETTERS[c(2:4,4)])
	hasEulerianPath(g)	#TRUE
	hasEulerianPath(g, "B")	#FALSE

---