This is how we can implement this algorithm:

a. Initialization

1. We will store the graph in Adjacency Lists, which means each parent vertex will have a list containing all of its children. We will do this using a HashMap where the ‘key’ will be the parent vertex number and the value will be a List containing children vertices.

2. To find the sources, we will keep a HashMap to count the in-degrees i.e., count of incoming edges of each vertex. Any vertex with ‘0’ in-degree will be a source.

b. Build the graph and find in-degrees of all vertices

1. We will build the graph from the input and populate the in-degrees HashMap.

c. Find all sources

1. All vertices with ‘0’ in-degrees will be our sources and we will store them in a Queue.

d. Sort

1. For each source, do the following things:

• Add it to the sorted list.
• Get all of its children from the graph.
• Decrement the in-degree of each child by 1.
• If a child’s in-degree becomes ‘0’, add it to the sources Queue.

2. Repeat step 1, until the source Queue is empty.

Topological Sort

from collections import deque

def topological_sort(vertices, edges):
  sortedOrder = []
  sources = deque()
  graph = {}
  inDegrees = {}
  
  # If the number of vertices is 0, return empty list
  if vertices <= 0:
    return sortedOrder


  # Initialize Adjacency List and Indegrees Hashmap
  graph = {i: [] for i in range(vertices)}
  inDegrees = {i: 0 for i in range(vertices)}

  # Build the graph and Indegrees Hashmap
  for parent, child in edges:
    graph[parent].append(child)
    inDegrees[child] += 1

  # Add sources to source queue
  for vertex in inDegrees:
    if inDegrees[vertex] == 0:
      sources.append(vertex)

  # While source queue, pop source. 
  # - Add to sourtedOrder list
  # - Decrement indegrees map
  # - If 0 indegrees, add to sources queue
  while sources:
    source = sources.popleft()
    sortedOrder.append(source)
    for child in graph[source]:
      inDegrees[child] -= 1
      if inDegrees[child] == 0:
        sources.append(child)

  return sortedOrder


def main():
  print("Topological sort: " +
        str(topological_sort(4, [3, 2], [3, 0], [2, 0], [2, 1](/kjingers/Grokking-Notes/wiki/3,-2],-[3,-0],-[2,-0],-[2,-1))))
  print("Topological sort: " +
        str(topological_sort(5, [4, 2], [4, 3], [2, 0], [2, 1], [3, 1](/kjingers/Grokking-Notes/wiki/4,-2],-[4,-3],-[2,-0],-[2,-1],-[3,-1))))
  print("Topological sort: " +
        str(topological_sort(7, [6, 4], [6, 2], [5, 3], [5, 4], [3, 0], [3, 1], [3, 2], [4, 1](/kjingers/Grokking-Notes/wiki/6,-4],-[6,-2],-[5,-3],-[5,-4],-[3,-0],-[3,-1],-[3,-2],-[4,-1))))


main()

Task Scheduling (COurse Schedule)

from collections import deque


def is_scheduling_possible(tasks, prerequisites):
      sortedOrder = []
      sources = deque()
      graph = {i: [] for i in range(tasks)}
      inDegrees = {i: 0 for i in range(tasks)}

      # Build Graph and inDegrees
      for parent, child in prerequisites:
            graph[parent].append(child)
            inDegrees[child] += 1
      
      # Add all sources to queue
      for vertex, numInDegrees in inDegrees.items():
            if numInDegrees == 0:
                  sources.append(vertex)

      # While sources: pop source, add to sorted order
      # Decrement inDegrees. Add to sources if 0 inDegrees
      while sources:
            source = sources.popleft()
            sortedOrder.append(source)
            for vertex in graph[source]:
                  inDegrees[vertex] -= 1
                  if inDegrees[vertex] == 0:
                        sources.append(vertex)
      
      
      return tasks == len(sortedOrder)
  


def main():
  print("Is scheduling possible: " +
        str(is_scheduling_possible(3, [0, 1], [1, 2](/kjingers/Grokking-Notes/wiki/0,-1],-[1,-2))))
  print("Is scheduling possible: " +
        str(is_scheduling_possible(3, [0, 1], [1, 2], [2, 0](/kjingers/Grokking-Notes/wiki/0,-1],-[1,-2],-[2,-0))))
  print("Is scheduling possible: " +
        str(is_scheduling_possible(6, [0, 4], [1, 4], [3, 2], [1, 3](/kjingers/Grokking-Notes/wiki/0,-4],-[1,-4],-[3,-2],-[1,-3))))

main()

All Tasks Scheduling Orders

'''
This problem requires topological sort in addition to subsets algorithm.

We will generate the graph and inDegrees and initial sources like usual.
For this one, we will create a function that we will call recursively.
- We will loop through all the sources and call the recursive function for each source.
- After the recursive call, we will backtrack - removing the vertex from the output sortedOrder
- If len(sortedOrder) == tasks, then we have a valid order of tasks, so print


'''
from collections import deque

def print_orders(tasks, prerequisites):
  sources = deque()
  sortedOrder = []

  # 1. Initialize graph and inDegrees
  graph = {i: [] for i in range(tasks)}
  inDegrees = {i: 0 for i in range(tasks)}

  # 2. Build graph and inDegrees
  for parent, child in prerequisites:
    graph[parent].append(child)
    inDegrees[child] += 1

  # 3. Add initial sources
  for vertex in inDegrees:
    if inDegrees[vertex] == 0:
      sources.append(vertex)

  # 4. Call recursive function with initial sources and empty sortedOrder
  print_all_orders_rec(graph, inDegrees, sources, sortedOrder)
  
def print_all_orders_rec(graph, inDegrees, sources, sortedOrder):
  if sources:

    # Loop through all current sources.
    # We will call recursively to get all combinations where the next vertex
    # in the soortedOrder is the current vertex
    for vertex in sources:

      # Make copy of sources. Remove current vertex
      nextSources = deque(sources)
      nextSources.remove(vertex)

      sortedOrder.append(vertex)

      # Update inDegrees. Update nextSources in necessary
      for child in graph[vertex]:
        inDegrees[child] -= 1
        if inDegrees[child] == 0:
          nextSources.append(child)

      # Call this funtion recursively
      print_all_orders_rec(graph, inDegrees, nextSources, sortedOrder)

      # Backtrack - Remove current vertex from sortedOrder and replace routes
      # By incrementing inDegrees
      sortedOrder.pop()
      for child in graph[vertex]:
        inDegrees[child] += 1

  if len(sortedOrder) == len(graph):
    print(sortedOrder)

def main():
  print("Task Orders: ")
  print_orders(3, [0, 1], [1, 2](/kjingers/Grokking-Notes/wiki/0,-1],-[1,-2))

  print("Task Orders: ")
  print_orders(4, [3, 2], [3, 0], [2, 0], [2, 1](/kjingers/Grokking-Notes/wiki/3,-2],-[3,-0],-[2,-0],-[2,-1))

  print("Task Orders: ")
  print_orders(6, [2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3](/kjingers/Grokking-Notes/wiki/2,-5],-[0,-5],-[0,-4],-[1,-4],-[3,-2],-[1,-3))


main()

Alien Dictionary

'''
Similar to typical topological sort problem. 
Main difference is that we don't have the prerequisite pairs. To build the graph, we
must compare all adjacent word pairs. Compare letter by letter until a letter is different.
The different character in the left word is a parent, and the different character in the right
word is the child.

'''

from collections import deque

def find_order(words):
  sortedOrder = []
  sources = deque()


  # Initialize Graph and inDegrees
  graph = {}
  inDegrees = {}

  # Make sure each distint character is a key in both maps
  for word in words:
    for char in word:
      graph[char] = []
      inDegrees[char] = 0

  # Build Graph and inDegrees by comparing adjacent word pairs
  for i in range(len(words)- 1):
    w1, w2 = words[i], words[i+1]
    for j in range(min(len(w1), len(w2))):
      parent = w1[j]
      child = w2[j]
      if parent != child:
        if child not in graph[parent]:
          graph[parent].append(child)
          inDegrees[child] += 1
        break
  
  # Add Sources
  for vertex in inDegrees:
    if inDegrees[vertex] == 0:
      sources.append(vertex)

  # While sources, process each source
  while sources:
    source = sources.popleft()
    sortedOrder.append(source)
    for child in graph[source]:
      inDegrees[child] -= 1
      if inDegrees[child] == 0:
        sources.append(child)

  if len(sortedOrder) != len(graph):
    return ""

  return ''.join(sortedOrder)


def main():
  print("Character order: " + find_order(["ba", "bc", "ac", "cab"]))
  print("Character order: " + find_order(["cab", "aaa", "aab"]))
  print("Character order: " + find_order(["ywx", "wz", "xww", "xz", "zyy", "zwz"]))


main()