我想用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.
所以基本上它读取输入文件。每行中的第一个代码是主题,其余代码是该主题的先决条件。然后,它将先决条件更改为包含每行先决条件的列表
事物是一门与其先决条件有关的学科,不能在同一学期内选修。但是testcase的输出仍然不是很正确:
Semester 1 : C3, C6
Semester 2 : C7, C1, C8
Semester 3 : C4
Semester 4 : C2
Semester 5 : C5
在不需要更改包含DAG的数据结构(即使用OOP类将其更改为图形表示)的情况下,是否有任何解决方案
检查我的代码: 我刚刚从
:输出:readIntoList
函数中获取了输出并提供给更新的topologicalSort
功能相关问题 更多 >
编程相关推荐