Algorithm: Course Order

Question

Given the number of courses and it's pre-requisite I have to return the correct order in which a student can take the courses i.e. student can not take a course if it has not completed it's pre-requisite. See the below Sample input and Output for explaination

Course order

Sample Input:
- Number of Courses: 4
- Prerequisite list: [[1,2],[3,2],[2,4]] // [i,j] means i is j's prerequisite
Output: either [1,3,2,4] or [3,1,2,4]

Sample Input:
- Number of Courses: 2
- Prerequisite list: [[1,2],[2,1]]
Output: [] // no possible solution because of cyclic dependency

This is my solution which is naive :

class Solution:
    def __init__(self):
        self.order = []
        self.mapping = {}

    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """

        for pre_req in prerequisites:
            if pre_req[1] not in self.mapping:
                self.mapping[pre_req[1]] = [pre_req[0]]
            else:
                self.mapping[pre_req[1]].append(pre_req[0])

        # for i in range(1, numCourses+1):
        #     if i not in self.mapping:
        #         self.order.append(i)

        j = 0
        # for key in self.mapping:
        #     i += 1
        #     if key not in self.order:
        #         self.helper(key, i)
        #     break
        for i in range(1, numCourses+1):
            if i in self.mapping:
                self.helper(i, j)



        return self.order

    def helper(self, key, i):
        if len(self.mapping[key]) == 0:
            if key not in self.order:
                self.order.append(key)

                for ki in self.mapping:
                    if key in self.mapping[ki]:
                        self.mapping[k].remove(value)
                self.mapping.pop(key, None)   
            return


        for k in self.mapping:
            for value in self.mapping[k]:    
                if value not in self.mapping:
                    if value not in self.order:
                        self.order.append(value)
                        for ki in self.mapping:
                            if value in self.mapping[ki]:
                                self.mapping[k].remove(value)
                    else:
                        self.mapping[k].remove(value)
                else:
                    self.helper(k, i+1)
                if len(self.mapping[key]) == 0:
                    if key not in self.order:
                        self.order.append(key)

                        for ki in self.mapping:
                            if key in self.mapping[ki]:
                                self.mapping[k].remove(value)



s = Solution()
prereq = [[1,2],[3,2],[2,4]]
courses = 4
res = s.canFinish(courses, prereq)
print(res)

• My code works correct for following input:
• Number of Courses: 4
• Prerequisite list: [[1,2],[3,2],[2,4]]
• My code does not take care of cyclic dependency
• My solution is not optimal
• I want to know a correct and optimal solution to this problem
• Before Down-voting please comment what extra information you need from me to add

============================= UPDATED ================================

• It does not take care of cyclic dependency because in the helper function I only check for the prerequisite which are the values of the key in the mapping dictionary and is that prerequisite i.e. value as a different key in the mapping dictionary then I add that in the self.order and I am doing this recursively
• So I am not checking if a key and value and the same value is the key to it's own key.
  • Obviously it's not optimal because I am not checking cyclic dependency
  • I think there can be a better data structure to solve this problem
  • Idea of dictionary : mapping = {course1 : [prereq1, prereq2], course2: [prereq1, prereq3]}
  • helper function check if mapping has prereq1 as the key then it adds the value of prereq1 to self.order

Answer 1

from collections import defaultdict

class CourseSelection(object):
  def __init__(self):
    self.num_of_courses = 0
    self.prereq_map = defaultdict(list)
    self.seen = set()
    self.is_cycle = False

  def add_prereq(self, parent, prereq):
    self.num_of_courses += 1
    self.prereq_map[parent].append(prereq)    

  def topological_util(self, courses_order, visited, node):

    if self.is_cycle:
      return

    self.seen.add(node)

    for prereq in self.prereq_map[node]:
      if prereq in self.seen:
        print("Cycle Found")
        self.is_cycle = True
        return True
      if prereq not in visited:  
        visited.add(prereq)  
        self.topological_util(courses_order, visited, prereq)

    self.seen.remove(node)
    courses_order.append(node)


  def topological_sort(self, start_node):
    visited = set([])
    courses_order = []
    for i in range(self.num_of_courses):
      # print(i, visited)
      if i not in visited:
        visited.add(i)
        self.topological_util(courses_order, visited, i)
    print(courses_order)

cs = CourseSelection()
cs.add_prereq(5, 0)
cs.add_prereq(5, 2)
# g.add_prereq(2, 5)
cs.add_prereq(2, 3)
cs.add_prereq(3, 1)
cs.add_prereq(4, 0)
cs.add_prereq(4, 1)
cs.topological_sort(0)

Answer 2

This is a classic use case for topological sorting. If you treat your prerequisites like a directed graph where there is an edge from prerequisite to another course you can simply find the topological sort of the graph and you will have your answer. A topological sort is not defined when the graph has cycles and similarly, your courses shouldn't have cycles because you would never be able to take those courses. In python you can do topological sorting with a simple depth-first search keeping track of when you enter and exit nodes. As you exit the nodes (after you've looked at all the children) you add that node to the from of the list. For example:

from collections import defaultdict
graph = defaultdict(set)

def getCourses(prereq):
    for p in prereq:
        # build a simple graph structure: keys are node value is a set of children
        graph[p[1]]
        graph[p[0]].add(p[1])

    visited = set()  
    seen = set()
    courses = []

    def dfs(node): # depth-first search
        if node in visited: return
        if node in seen:
            raise ValueError("Error cycle in prerequisites")
        seen.add(node)
        for e in graph[node]:
            dfs(e) #recurse on children
        seen.remove(node)
        visited.add(node)
        courses.insert(0, node)


    for k in graph.keys():
        if k in visited:
            continue        
        try: dfs(k)
        except ValueError: # in case of cycle
            return []

    return courses

print(getCourses([[1,2],[3,2],[2,4]]))

Answer 3

Here's my solution. I keep track of courses in this object:

class Course():
  '''A course object. Holds a pre-req, maybe'''
  def __init__(self, id):
    self.id = id
    self.reqs = []

  def add_req(self, course):
    self.reqs.append(course)

  def has_req(self):
    return len(self.reqs) > 0

  def reqs_satisfied(self, path):
    return set(self.reqs).issubset(set(path))

So given a course, I can look up its requirement if any.

I'm only interested in having all the courses added to the list, following these rules:

1. A course will only be added if it hasn't already been added.
2. If a course can be been added, that means all of its prerequistes were added.

If a course cannot be added, it is because we could not find a way to satisfy the prerequisites (in this case, when there are cyclic prereqs, because we don't let ourselves go into a cycle)

Which translates to something like

class Solution():  

  def __init__(self, course_data, prereq_data):
    '''Create courses, and fill in pre-reqs'''
    self.courses = {}
    for id in course_data:
      self.courses[id] = Course(id)

    # [i, j], assuming course i is the pre-req for course j
    for data in prereq_data:
      pre_req = self.courses[data[0]]
      course = self.courses[data[1]]
      course.add_req(pre_req)     

  def build_path(self):

    all_courses = list(self.courses.values())
    num_courses = len(all_courses)
    path = []

    # Add each course recursively
    while len(all_courses) > 0:
      course = all_courses.pop(0)      
      self.add_course(course, path, [])

    # Check if the path is valid (ie: all courses are taken)
    if len(path) == num_courses:
      return path
    else:
      return []

  def add_course(self, course, path, visited):
    # ignore courses that have already been added.
    # also, ignore courses that have been visited already (avoid cycle)
    if course in path or course in visited:
      return
    visited.append(course)

    # if this course has requirement, add it. Possible that we don't add it
    for req in course.reqs:
      self.add_course(req, path, visited)

    # try adding this course, after pre-reqs have been checked. 
    if (course.reqs_satisfied(path)):
      path.append(course)

path = Solution([1,2,3,4], [[1,2],[3,2],[2,4]]).build_path()
print("Solution: ", [course.id for course in path])

path = Solution([2,1,7,4], []).build_path()
print("Solution: ", [course.id for course in path])