Search
 
SCRIPT & CODE EXAMPLE
 

PYTHON

What is topological sort?

Topological sort: 
outlines all the paths from point A to point B in a directed acyclic graph. 
Answers the question can I go from point A to point B and if yes, how?
C-> A ->B ->D
you CAN go from C to A
you CAN go from A to D
you CANNOT go from D to C
Comment

topological sort

"""
This implementation demonstrates how to
perform topological sort, which yields
a linear ordering of the vertices of a
graph. Example considered is that of
inter-dependent jobs.
Input: List of jobs and list of dependencies
Output: A valid order in which jobs can be
completed

Let j be the number of jobs and d the number
of dependencies.

Time complexity: O(j+d)
Space complexity: O(j+d)
"""


def topological_sort(jobs, deps):
    job_graph = create_graph(jobs, deps)
    return get_ordered_jobs(job_graph)


def create_graph(jobs, deps):
    # Create a graph of jobs
    graph = job_graph(jobs)
    # Add dependencies to every job node
    for prereq, job in deps:
        graph.add_prereq(job, prereq)
    return graph


def get_ordered_jobs(graph):
    ordered_jobs = []
    nodes = graph.nodes  # List of all job nodes
    while len(nodes):
        node = nodes.pop()
        print(node.job)
        contains_cycle = depth_first_search(node, ordered_jobs)
        # Jobs cannot be ordered in the presence of a cycle
        if contains_cycle:
            return []
    return ordered_jobs


def depth_first_search(node, ordered_jobs):
    print(node.job)
    if node.visited:
        return False  # Node already processed
    if node.visiting:
        return True  # A cycle is detected
    node.visiting = True
    # Process all prerequisite nodes
    for prereq_node in node.prereqs:
        contains_cycle = depth_first_search(prereq_node, ordered_jobs)
        if contains_cycle:
            return True
    node.visited = True  # Mark the node as processed
    node.visiting = False  # Finished processing the node
    ordered_jobs.append(node.job)
    print(ordered_jobs)
    return False


class job_graph:
    def __init__(self, jobs):
        self.nodes = []  # List of job nodes
        self.graph = {}  # Map job idx to job node
        for job in jobs:
            self.add_node(job)

    def add_prereq(self, job, prereq):
        job_node = self.get_node(job)
        # Every node keeps track of its prerequisites
        prereq_node = self.get_node(prereq)
        job_node.prereqs.append(prereq_node)

    def add_node(self, job):
        # Update graph with a new node
        self.graph[job] = job_node(job)
        self.nodes.append(self.graph[job])

    def get_node(self, job):
        if job not in self.graph:
            self.add_node(job)
        return self.graph[job]


class job_node:
    def __init__(self, job):
        self.job = job
        self.prereqs = []
        self.visited = False  # Already processed by DFS
        self.visiting = False  # Being processed by DFS


jobs = [1, 2, 3, 4]
# In the below array, 2 is dependent on 1, 3 on 1, etc...
deps = [[1, 2], [1, 3], [3, 2], [4, 2], [4, 3]]
print(topological_sort(jobs, deps))  # [4, 1, 3, 2]
Comment

PREVIOUS NEXT
Code Example
Python :: python all but the last element 
Python :: list count python 
Python :: map function to change type of element in python 
Python :: how to check how many key value pairs are in a dict python 
Python :: opening a file in python 
Python :: python combine two columns into matrix 
Python :: list slice in python 
Python :: python create dictionary 
Python :: print string in reverse order uing for loop python 
Python :: {"message": "401: Unauthorized", "code": 0} discord 
Python :: python responses 
Python :: check if text is python 
Python :: iterate array python with index 
Python :: Returns the first row as a Row 
Python :: logger 
Python :: Sendgrid dynamic templating 
Python :: how to make loops in python 
Python :: python math exp 
Python :: title() in python 
Python :: Python List count() example with numbers 
Python :: download button image streamlit 
Python :: NumPy invert Syntax 
Python :: numpy linspace function 
Python :: python class getters and setters 
Python :: daraja mpesa 
Python :: list add pythhon 
Python :: python language 
Python :: python in line elif 
Python :: data encapsulation in python 
Python :: rotate matrix 90 degrees clockwise in python 
ADD CONTENT
Topic
Content
Source link
Name
3+9 =