Prerequisite checking for subjects in each semester

Question

I want to make a scheduler of subjects with topological sort, but here I am using list comprehension analogue to DAG concepts.

The code:

def readIntoList(filename):
    # Open and Read File
    file = open(filename, 'r');
    
    # Initialize an empty list
    fullList = []
    
    # Preprocess the string
    for line in file:
        # Clean the text
        line = line.replace(".", "")
        line = line.replace('\n', "")
        line = line.replace(" ", "")
        
        # Split and get each subjects
        lineList = (line.split(","))
        
        # Append to the end list
        fullList.append(lineList)
    
    # Close the file
    file.close()
        
    return fullList

# Check if a subject is a prerequisite of other subject
def checkPrereq(subject, new, target):
    # Find Target Subject
    prereqList = []
    foundNew = False
    foundTarget = False
    
    for prereq in subject:
        if(prereq[0] == target):
            prereqList = prereq
            if(new in prereqList):
                foundNew = True
        if(prereq[0] == new):
            prereqList = prereq
            if(target in prereqList):
                foundTarget = True
                
    # Check if new is in the prerequisite list of target
    return foundNew and foundTarget

def topologicalSort(subject):
    
    # Init a copy of Subject List and an empty list to contain results
    copySubject = subject
    result = []
    matkul = ""
    
    # Iterate until the subject list is empty -> no more nodes in graph
    while(len(subject) != 0):
        # Find subject without any input edges
        for subjects in subject:
            
            # Init empty list to contain subjects in each semester
            semesterList = []
            
            # Get the subjects if the length of the list is 1 -> In-Degree = 0
            if(len(subjects) == 1):
                matkul = subjects[0]
                semesterList.append(matkul)
                
                # Remove the subject from current list
                subject.remove(subjects) 
                
                # Append the subject to corresponding semester
                for rest in subject:
                    if(len(rest) == 1 and not checkPrereq(copySubject, rest[0], matkul)):
                        matkul = rest[0]
                        semesterList.append(matkul)
                        
                        # Remove the subject from current list
                        subject.remove(rest)
                        
                # Add each semester to the end result
                result.append(semesterList)
            
            # Remove the subject from remaining list (graph nodes connected with the subject)
            for choosen in semesterList:
                for remaining in subject:
                    if(choosen in remaining):
                        remaining.remove(choosen)                
                    
        print(subject)
    return result

def schedule(sortedResult):
    # Init counter
    counter = 1
    
    # Iterate over result
    for semester in sortedResult:
        if(len(semester) == 1):
            print("Semester", counter, ":", semester[0])
        else:
            print("Semester", counter, ":", end = " ")
            for idx in range(len(semester)):
                if(idx == len(semester) - 1):
                    print(semester[idx])
                else:
                    print(semester[idx], end = ", ")
        counter += 1

subject = readIntoList("3.txt")
sortedResult = topologicalSort(subject)
schedule(sortedResult)

The file as input:

C1, C3.
C2, C1, C4.
C3.
C4, C1, C3.
C5, C2, C4.
C6.
C7.
C8, C3.

So basically it reads the input file. First code in each line is a subject and the rest are prerequisites for that subject. It then changes the prerequisites into list of list containing prerequisites in each line.

The thing is a subject with relationship with its prerequisites cannot be taken in the same semester. But the output of the testcase is still not very correct:

Semester 1 : C3, C6
Semester 2 : C7, C1, C8
Semester 3 : C4
Semester 4 : C2
Semester 5 : C5

Is there any solution to this, without the needs to change the data structure containing the DAG, i.e. changing it to the graph representation using OOP class?

Answer 1

Check my code : From your readIntoList function I just taken output and supply to updated topologicalSort function.

var = [['C1', 'C3'], ['C2', 'C1', 'C4'], ['C3'], ['C4', 'C1', 'C3'], ['C5', 'C2', 'C4'], ['C6'], ['C7'], ['C8', 'C3']]
sem = 1

def topologicalSort(var):
    listSem = []
    semSet = []
    for i in var:
        if len(i) == 1:
            listSem.append(i)
    var = [i for i in var if i not in listSem]
    semSet.append(listSem)

    updateVar = []
    for j in var:
        for i in listSem:
            if (i[0] in j):
                j.remove(i[0])
        updateVar.append(j)

    string = ', '.join([i[0] for i in semSet[0]])
    global sem
    print(f'Semester {sem}', string)
    sem += 1
    if len(updateVar) == 0:
        return 0
    return call(updateVar)

topologicalSort(var)

: Output :

Semester 1 C3, C6, C7
Semester 2 C1, C8
Semester 3 C4
Semester 4 C2
Semester 5 C5