An implementation of Depth First Search in Python

README

This is a search algorithm implementation.
It takes a text file used to construct the tree
(use the example one exampletree.txt or your own)


To run:
$ python search.py <textfile.txt>

exampletree.txt

a[b[def]][c[g[h]]]

node.py

"""
Class Node is a tree node that stores data, a parent, and a list of children
	
	Samantha Goldstein 2015

"""

class Node:


	def __init__(self, data, parent=None, children=None):
		#setup of default variables. Only need the node's data to construct
		self.data = data 
		if parent is None:
			self.parent = None
		else: 
			self.parent = parent

		if children is None:
			self.children = []
		else:
			self.children = children

	def __str__(self):
		string = self.data + " " + "[ "
		for i in range(len(self.children)):
			string += str(self.children[i]) + ", "
		string +="]"
		return string


	def getData(self):
		return self.data

	def setData(self, data):
		self.data = data
		return 

	def getChildren(self):
		return self.children

	def addChild(self, node):
		self.children.append(node)
		return node

	def getParent(self):
		return self.parent

	def setParent(self, par):
		self.parent = par
		return 



if __name__ == '__main__':
  main()

search.py

"""
This program is an implementation of Depth First Search in Python

	Samantha Goldstein 2015

"""

from node import *
from tree import *
import sys

def main():
	if len(sys.argv) != 2:
		print "Invalid, need two arguments. e.g.\n\t$ python search.py <textfile.txt>"
		return

	filename = sys.argv[1]

	tree = Tree()
	tree.makeTree(filename)
	print "\nLet's Search!"
	find = raw_input("Give me a character to search for: ")
	if len(find)>1:
		print "Sorry that's invalid"
	result = DFS(tree, find)

	if result == -1:
		print "We could not find the element you are looking for. Sorry"
	else:
		print "Found your node! \n" + str(result)



def DFS(tree, item):
	"""
	This is an implementation of depth first search that takes two parameters
		tree: a tree structure to search from
		item: an element to search the tree for

	returns a node if the item is found, else returns -1
	"""

	#Initialize vars
	stack = []
	curr = tree.getRoot()
	stack.append(curr)

	while len(stack)> 0:
		#Pop off the most recently added element
		curr = stack.pop()

		#If the current element is our search item, then return that node
		if curr.getData() == item:
			return curr

		else:
			[stack.append(elem) for elem in curr.getChildren()[-1::-1]]

	return -1
			







main()

tree.py

"""
An implementation of a tree structure.
Trees can be constructed independently or given a file 
to create the tree from

	Samantha Goldstein 2015

"""
from node import *


class Tree:


	def __init__(self):
		#Initialize a tree structure
		self.root = None

	def getRoot(self):
		#Accesses root element
		return self.root

	def setRoot(self, root):
		#Sets root element
		self.root = root
		return

	def isEmpty(self):
		#Bool for status of tree
		if self.root == None:
			return True
		else:
			return False


	def makeTree(self, textfl):
		"""
		Creates the tree structure based on input from a file. 
		elements in brackets represent child nodes
		Text File Ex: a[b[cd]ef[g]]
		Represents tree: 

				     a
				    /|\
				   b e f
				  /\   |
				 c  d  g

		Parameters:
			textfl: a text file that houses a tree data structure
			tree: an initialized tree structure

		Returns: nothing, -1 if empty file	

		"""

		#Initialization, open file, set vars
		text = open(textfl, "r")
		curr = None
		line = text.readline()


		#Confirm valid file, not empty
		if len(line) == 0:
			return -1

		#Initialize vars
		nd = Node(line[0])
		self.root = nd 
		curr = nd
		place = 1 #will be used to traverse text


		#Traverse text file to set up tree
		while place < len(line):
			#'[' means the following char will represent a child node 
			# so we create a node for the following char, update current node
			if line[place] == '[':
				place += 1 
				nd = Node(line[place], curr)
				curr.addChild(nd)
				curr = nd

			#']' means we've just finished the whole array of children 
			#for an element, so we reset current to a parent element which
			#may still need to add child elements
			elif line[place] == ']':
				curr = curr.getParent()

			#Else we create a node for the char, and set it's parent
			else:
				curr = curr.getParent()
				nd = Node(line[place], curr)
				curr.addChild(nd)
				curr= nd

			place += 1	#update position in text


		return