Finding the root | Python Fiddle

from collections import deque, OrderedDict
def findroot():
    tup = ['Elemental#Nitrogen','Entry#Substance','Substance#Elemental','Substance#Compound','Compound#Phosphate','Compound#Pigments',
           'Substance#Unclassified','Pigments#Chlorophyll']
    c = '#'
    dictva= OrderedDict()
    for t in tup:
        ind = t.index(c)
        key = t[:ind]
        val = t[ind+1:]
        dictva.setdefault(key,[]).append(val)
    rootls = []
    keyls = []
    for key,value in dictva.iteritems():
        keyls.append(key)
        for val in dictva.values():
            if key in val:
              rootls.append(key)
        dictva[key] = set(value)
    root = filter(lambda x:x not in rootls,keyls)[0]
    longls = []
    shortls = []
    finalshortls = []
    finallongls = []
    finaldict = {}
    for val in dictva.values():
        for value in val:
            data = list(longest_path(dictva, root, value))[0]
            longls.append(data)

short = shortest_path(dictva,root, value)
            shortls.append(short)
    for data in longls:
        if len(data) > 2:
            if finallongls and len(data) > finallongls[1]:
                finallongls.pop(0)
                finallongls.append(data)
            elif not finallongls:
                finallongls.append(data)
                finallongls.append(len(data))
    for data in shortls:
        if len(data) > 2:
            if finalshortls and len(data) < finalshortls[1] and len(data) > 2:
                finalshortls.pop(0)
                finalshortls.append(data)
                finalshortls.append(len(data))
            elif not finalshortls:
                finalshortls.append(data)
                finalshortls.append(len(data))
    print "Root:", root
    print "Longest Path:", finallongls[1]
    print "Shortest Path:", finalshortls[0]
    finaldict["Root"] = root
    finaldict["Longest Path:"] = finallongls[1]
    finaldict["Shortest Path:"] = finalshortls[0]
    return finaldict

def shortest_path(graph, start, goal):
    try:
        return next(longest_path(graph, start, goal))
    except StopIteration:
        return None

def longest_path(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        try:
            for next in graph[vertex] - set(path):
                if next == goal:
                    yield path + [next]
                else:
                    queue.append((next, path + [next]))
        except:
            pass

datq =findroot()
print "data", dataq

Python Fiddle

Python Cloud IDE