CODEWITHSUNDEEP
python
C H
C H

Reputation: 35

ASCII-alphabetical topological sort

I have been trying to figure out a issue, in which my program does the topological sort but not in the format that I'm trying to get. For instance if I give it the input:

Learn Python
Understand higher-order functions
Learn Python
Read the Python tutorial
Do assignment 1
Learn Python

It should output:

Read the python tutorial
Understand higher-order functions
Learn Python
Do assignment 1

Instead I get it where the first two instances are swapped, for some of my other test cases this occurs as well where it will swap 2 random instances, heres my code:

import sys 
graph={}

def populate(name,dep):
    if name in graph:
        graph[name].append(dep)
    else:
        graph[name]=[dep]
        
    if dep not in graph:
        graph[dep]=[]
    

def main():
    last = ""
    for line in sys.stdin:
        lne=line.strip()
        if last == "":
            last=lne
        else:
            populate(last,lne)
            last=""
            
            
def topoSort(graph):
    sortedList=[] #result
    zeroDegree=[]
    inDegree = { u : 0 for u in graph }
    for u in graph:
        for v in graph[u]:
            inDegree[v]+=1
    for i in inDegree:
        if(inDegree[i]==0):
            zeroDegree.append(i)
    while zeroDegree:
        v=zeroDegree.pop(0)
        sortedList.append(v)
        #selection sort for alphabetical sort 
            
        for x in graph[v]:
            inDegree[x]-=1
            if (inDegree[x]==0):
                zeroDegree.insert(0,x)
    
    sortedList.reverse()
    
    #for y in range(len(sortedList)):
    #       min=y
    #       for j in range(y+1,len(sortedList)):
    #           if sortedList[min]>sortedList[y]:
    #               min=j
    #               sortedList[y],sortedList[min]=sortedList[min],sortedList[y]
            
    return sortedList
    
if __name__=='__main__':
    main()
    result=topoSort(graph)
    if (len(result)==len(graph)):
        print(result)
    else:
        print("cycle")

Any Ideas as to why this may be occurring?

Upvotes: 0

Views: 339

Answers (1)

areop-enap
areop-enap

Reputation: 418

The elements within dictionaries or sets are not ordered. If you add elements they are randomly inserted and not appended to the end. I think that is the reason why you get random results with your sorting algorithm. I guess it must have to do something with inDegree but I didn't debug very much.
I can't offer you a specific fix for your code, but accordingly to the wanted input and output it should look like this:

# read tuples from stdin until ctrl+d is pressed (on linux) or EOF is reached
graph = set()
while True:
  try:
    graph |= { (input().strip(), input().strip()) }
  except:
    break

# apply topological sort and print it to stdout
print("----")
while graph:
  z = { (a,b) for a,b in graph if not [1 for c,d in graph if b==c] }
  print ( "\n".join ( sorted ( {b for a,b in z} )
    + sorted ( {a for a,b in z if not [1 for c,d in graph if a==d]} ) ) )
  graph -= z

The great advantage of Python (here 3.9.1) is the short solution you might get. Instead of lists I would use sets because those can be easier edited: graph|{elements} inserts items to this set and graph-{elements} removes entities from it. Duplicates are ignored.
At first are some tuples red from stdin with ... = input(), input() into the graph item set.
The line z = {result loop condition...} filters the printable elements which are then subtracted from the so called graph set.
The generated sets are randomly ordered so the printed output must be turned to sorted lists at the end which are separated by newlines.

Upvotes: 1

Related Questions