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?

Your output is correct. It satisfies all of the pre-requisites. Are you trying to optimize the list in some way? It's true that you could take C7 in semester 1. — Tim Roberts, Feb 26 '21 at 06:31
@TimRoberts yes that is correct. I am trying to optimize the result. While the result shown is not wrong, I think that by concept it is better to put C7 in semester 1. — Errata, Feb 26 '21 at 06:36
Your big problem is that you are modifying "subject" while you are iterating it. Twice, in fact. `subject.remove(rest)` is inside both `for rest in subject` and `for subjects in subject`. Python can't handle that, the results are unpredictable. That causes you to miss several lines. — Tim Roberts, Feb 26 '21 at 06:51
@TimRoberts I see, I was also thinking about the same thing but I just can't seem to reproduce another code that provides better result. Thank you for the pointers. — Errata, Feb 26 '21 at 07:24

score 2 · Accepted Answer · answered Feb 26 '21 at 06:49

2

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

answered Feb 26 '21 at 06:49

Davinder Singh

2,060
2
7
22

Here no need of using your `topologicalSort `and `checkPrereq` function I managed it into single function in more optimal way. Please check by removing your `topologicalSort `and `checkPrereq` function and place updated `topologicalSort ` function – Davinder Singh Feb 26 '21 at 06:52
Ah nice one! But I've got a few questions about the code. For me, the code first find a single subject without any prerequisites and update the list of ```var``` by removing it and update the ```semSet``` list. But I don't quite understand the next part of ```updateVar```. Does it remove the subjects in the remaining subject list? Also, the last section is to print the output, but here I got an error in ```call(updateVar)``` and to be honest it is my first time seeing it. Is it for older Python and what does it do? Please elaborate more on this because I can't find any references of it. – Errata Feb 26 '21 at 07:21
2

Actually my code only work around `list` having `single element` then at one stage I club all single element and place into another list for future use, then i remove these element and update `var` in line 10. Next `for loop` focus on how to remove semester dependency as I completed this semester and assign into new list name `updateVar` and I reached to second semester and again I will check same condition as above and for that I make recursive function for optimization of code – Davinder Singh Feb 26 '21 at 07:31
Oh! I get it now. The function works to process a list with single element and then you grouped and updated the element list by removing the dependencies. Lastly, the ```call(updateVar)``` part is a recursive act to finish all the remaining subjects. At one point before I started doing this I also consider the practicality of using ```recursion```, but I didn't get to the bottom of it. Greatly appreciated this simple approach. Thank you very much. – Errata Feb 26 '21 at 07:43

Prerequisite checking for subjects in each semester

1 Answers1