breadth.first <- function(graph, startNode, endNodes)
{
	if (is.null(rownames(graph)))
		vNames <- 1:nrow(graph)
	else
		vNames <- rownames(graph)

	startNode <- which(vNames %in% startNode)
	endNodes <- which(vNames %in% endNodes)


	queue <- vector()
	marked <- rep(FALSE, len = nrow(graph))
	from <- rep(-1, len = nrow(graph))

	marked[startNode] <- TRUE	
	queue <- c(queue, startNode)
	print(paste("Dajem v vrsto vozlisce", vNames[startNode]))
	
	
	while (length(queue) > 0)
	{
		curNode <- queue[1]
		queue <- queue[-1]
		print(paste("Odstranjujem iz vrste vozlisce", vNames[curNode]))

		if (curNode %in% endNodes)
		{
			print(paste("Resitev BFS v vozliscu", vNames[curNode]))

			path <- vNames[curNode]
			while (TRUE)
			{
				curNode <- from[curNode]
				if (curNode != -1)
					path <- paste(path, "<--", vNames[curNode])
				else
					return(path)
			}
		}

		for (nextNode in 1:ncol(graph))
		{
			if (!is.na(graph[curNode, nextNode]) && !marked[nextNode])
			{
				marked[nextNode] <- TRUE
				from[nextNode] <- curNode
				queue <- c(queue, nextNode)
				print(paste("Dajem v vrsto vozlisce", vNames[nextNode]))
			}
		}
	}
}

depth.first <- function(graph, startNode, endNodes)
{
	if (is.null(rownames(graph)))
		vNames <- 1:nrow(graph)
	else
		vNames <- rownames(graph)

	startNode <- which(vNames %in% startNode)
	endNodes <- which(vNames %in% endNodes)


	stack <- vector()
	marked <- rep(FALSE, len = nrow(graph))
	from <- rep(-1, len = nrow(graph))

	marked[startNode] <- TRUE	
	stack <- c(stack, startNode)
	print(paste("Polagam na sklad vozlisce", vNames[startNode]))
	
	
	while (length(stack) > 0)
	{
		curNode <- stack[length(stack)]
		
		if (curNode %in% endNodes)
		{
			print(paste("Resitev DFS v vozliscu", vNames[curNode]))
			
			path <- vNames[curNode]
			while (TRUE)
			{
				curNode <- from[curNode]
				if (curNode != -1)
					path <- paste(path, "<--", vNames[curNode])
				else
					return(path)
			}
		}

		sel <- which(!is.na(graph[curNode,]) & !marked)
		if (any(sel))
		{
			nextNode <- sel[1]
			marked[nextNode] <- TRUE
			from[nextNode] <- curNode
			stack <- c(stack, nextNode)

			print(paste("Polagam na sklad vozlisce", vNames[nextNode]))
		}
		else
		{
			stack <- stack[-length(stack)]
			print(paste("Odstranjujem s sklada vozlisce", vNames[curNode]))
		}
	}
}

iter.deep <- function(graph, startNode, endNodes)
{
	if (is.null(rownames(graph)))
		vNames <- 1:nrow(graph)
	else
		vNames <- rownames(graph)

	startNode <- which(vNames %in% startNode)
	endNodes <- which(vNames %in% endNodes)


	for (depthLimit in 0:nrow(graph))
	{
		print(paste("Globina iskanja je ", depthLimit))

		stack <- vector()
		marked <- rep(FALSE, len = nrow(graph))
		from <- rep(-1, len = nrow(graph))

		marked[startNode] <- TRUE	
		stack <- c(stack, startNode)
		print(paste("Polagam na sklad vozlisce", vNames[startNode]))
	
	
		while (length(stack) > 0)
		{
			curNode <- stack[length(stack)]
		
			if (curNode %in% endNodes)
			{
				print(paste("Resitev DFS v vozliscu", vNames[curNode]))
			
				path <- vNames[curNode]
				while (TRUE)
				{
					curNode <- from[curNode]
					if (curNode != -1)
						path <- paste(path, "<--", vNames[curNode])
					else
						return(path)
				}
			}

			found <- FALSE
			if (length(stack) <= depthLimit)
			{
				sel <- which(!is.na(graph[curNode,]) & !marked)
				if (any(sel))
				{
					found <- TRUE
					nextNode <- sel[1]
					marked[nextNode] <- TRUE
					from[nextNode] <- curNode
					stack <- c(stack, nextNode)

					print(paste("Polagam na sklad vozlisce", vNames[nextNode]))
				}
			}
			
			if (!found)
			{
				stack <- stack[-length(stack)]
				print(paste("Odstranjujem s sklada vozlisce", vNames[curNode]))
			}
		}

		print("-------------------------------------------------")
	}
}


graph <- matrix(c(NA, 1,NA,NA,NA,NA,NA,NA,
		     	NA,NA, 1,NA,NA,NA,NA, 1,
		     	NA,NA,NA,NA, 1, 1,NA,NA,
			NA, 1,NA,NA,NA,NA,NA, 1,
			NA,NA,NA,NA,NA,NA, 1, 1,
			NA,NA,NA, 1,NA,NA, 1,NA,
			NA,NA,NA,NA,NA,NA,NA,NA,
			NA,NA,NA,NA,NA,NA,NA,NA), byrow=TRUE, ncol=8, nrow=8)

colnames(graph) <- c("a","b","c","d","e","f","g","h")
rownames(graph) <- c("a","b","c","d","e","f","g","h")
graph

breadth.first(graph, "a", c("g", "h"))
depth.first(graph, "a", c("g", "h"))
iter.deep(graph, "a", c("g", "h"))





#
# Primer naloge iz vaj
#

graph <- matrix(c(NA, 1, 1, 1,NA,NA,NA,NA,NA,NA,NA,NA,NA,
		     	NA,NA,NA,NA, 1, 1,NA,NA,NA,NA,NA,NA,NA,
		     	NA,NA,NA,NA,NA, 1, 1, 1,NA,NA,NA,NA,NA,
			NA,NA,NA,NA,NA,NA,NA,NA, 1, 1,NA,NA,NA,
			NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,
			NA,NA,NA,NA,NA,NA,NA,NA,NA,NA, 1, 1,NA,
			NA,NA,NA,NA,NA, 1,NA,NA,NA,NA,NA,NA,NA,
			NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,
			NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA, 1,
			NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,
			NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,
			NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,
			NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA), byrow=TRUE, ncol=13, nrow=13)

colnames(graph) <- c("s","a","b","c","d","e","f","g","h","i","j","k","l")
rownames(graph) <- c("s","a","b","c","d","e","f","g","h","i","j","k","l")
graph

depth.first(graph, "s", c("g","k","l"))

breadth.first(graph, "s", c("g","k","l"))

iter.deep(graph, "s", c("g","k","l"))


#
# Naloga iz vaj (samostojno delo)
#

graph <- matrix(c(NA, 1, 1,NA, 1,NA, 1,
		     	NA,NA,NA,NA,NA,NA,NA,
		     	NA,NA,NA,NA,NA,NA,NA,
			NA,NA,NA,NA,NA, 1,NA,
			 1,NA,NA, 1,NA, 1,NA,
			NA,NA,NA,NA,NA,NA,NA,
			NA,NA,NA,NA,NA, 1,NA), byrow=TRUE, ncol=7, nrow=7)

colnames(graph) <- c("a","b","c","d","e","f","g")
rownames(graph) <- c("a","b","c","d","e","f","g")
graph

depth.first(graph, "a", "f")

breadth.first(graph, "a", "f")

iter.deep(graph, "a", "f")