每学期科目先决条件检查

Question

我想用 topological sort 制作一个主题调度程序，但在这里我使用的是类似于 DAG 概念的列表理解。

代码：

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)

作为输入的文件：

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

所以基本上它读取输入文件。每行中的第一个代码是一个主题，其余代码是该主题的先决条件。然后它将先决条件更改为每行包含先决条件的列表列表。

这门学科与其先决条件有关系，不能在同一学期修读。但是测试用例的输出还是不太正确：

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

有没有解决这个问题的方法，无需更改包含 DAG 的数据结构，即将其更改为使用 OOP 的图形表示class？

Answer 1

检查我的代码：从你的 readIntoList 函数中，我刚刚将输出和供给更新为 topologicalSort 功能。

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)

：输出：

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

每学期科目先决条件检查

Prerequisite checking for subjects in each semester

python

topological-sort