getRing(startAtom, atomSet, lookup, oatoms)->atoms, bonds
    starting at startAtom do a bfs traversal through the atoms
    in atomSet and return the smallest ring found

    returns (), () on failure
    note: atoms and bonds are not returned in traversal order

def getRing(startAtom, atomSet, lookup, oatoms):
    """getRing(startAtom, atomSet, lookup, oatoms)->atoms, bonds
    starting at startAtom do a bfs traversal through the atoms
    in atomSet and return the smallest ring found

    returns (), () on failure
    note: atoms and bonds are not returned in traversal order"""

    path = {}
    bpaths = {}
    for atomID in atomSet.keys():
	# initially the paths are empty
	path[atomID] = None
        bpaths[atomID] = []
    
    q = []
    handle = startAtom.handle
    for atom in oatoms[handle]:
	q.append((atom, handle))
        path[atom.handle] = {atom.handle:1, handle:1}
        bpaths[atom.handle] = [startAtom.findbond(atom)]
            
    qIndex = 0
    lenQ = len(q)

    while qIndex < lenQ:	
	current, sourceHandle = q[qIndex]
        handle = current.handle
	qIndex += 1

        for next in oatoms[handle]:
	    m = next.handle

	    if m != sourceHandle:
		if not atomSet.has_key(m):
		    return (), ()
                
		if path.get(m, None):
		    intersections = 0
		    for atom in path[handle].keys():
			if path[m].has_key(atom):
			    intersections = intersections + 1
			    sharedAtom = atom

		    if intersections == 1:
			del path[handle][sharedAtom]
			path[handle].update(path[m])
			result = path[handle].keys()
                        bond = next.findbond(current)
                        # assert bond not in bpaths[handle] and bond not in bpaths[m]
                        bonds = bpaths[handle] + bpaths[m] + [bond]
			return result, bonds
		else:
		    path[m] = path[handle].copy()
		    path[m][m] = 1
                    bond = next.findbond(current)
                    # assert bond not in bpaths[m] and bond not in bpaths[handle]
                    bpaths[m] = bpaths[handle] + [next.findbond(current)]
		    q.append((next, handle))
		    lenQ = lenQ + 1

    return (), ()