Interview Questions on Graphs

Route Between Nodes

We’re given a directed graph and two nodes (X and Y). Design an algorithm to check whether there exists a route between the two nodes.

For the implementation of the solution to the given problem, we need to initialize the graph class and overwrite the __init__ function as per our requirements. Then, we add the addEdge method to the Graph class.

#Initializing the Graph class
class Graph:
    def __init__(self, gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
    
    def addEdge(self, vertex, edge):
        self.gdict[vertex].append(edge)

The checkRoute method will be used to find out whether or not there exists a path between the two given nodes. It takes two variables as parameters – the start node and the end node.

The checkRoute method is based on the following algorithm:

• Create function and input the start and end nodes as parameters.
• Create a queue and enqueue start node into it.
• Find all the neighbours of the enqueued node and add them to the queue.
• Repeat this process until all the elements of the graph are inserted into the queue.
• While performing the above steps, if at some point the end node is encountered, the boolean value True is returned.
• Mark visited nodes as visited by placing them in a seperate temporary queue.

#Function to check whether a path exists between two nodes
def checkRoute(self, startNode, endNode):
    visited = [startNode]
    queue = [startNode]
    path = False
    while queue:
        deVertex = queue.pop(0)
        for adjacentVertex in self.gdict[deVertex]:
            if adjacentVertex not in visited:
                if adjacentVertex == endNode:
                    path = True
                    break
                else:
                    visited.append(adjacentVertex)
                    queue.append(adjacentVertex)
    return path
 
customDict = { "a" : ["c","d", "b"],
            "b" : ["j"],
            "c" : ["g"],
            "d" : [],
            "e" : ["f", "a"],
            "f" : ["i"],
            "g" : ["d", "h"],
            "h" : [],
            "i" : [],
            "j" : []
               }

tempGraph = Graph(customDict)
print(tempGraph.checkRoute("a", "j"))
print(tempGraph.checkRoute("a", "e"))
print(tempGraph.checkRoute("a", "i"))

#Output 
True
False 
False

Build Order

We are given a list of projects and a list of dependencies(i.e., a list of pairs of projects, and the second poject is dependent on the first project). Each project’s dependencies must be built before the project. Create a build order that will allow projects to be built. If no valid order exists, return an error.

A simple approach towards creating the build order using graphs would be:

• Find nodes with dependencies.
• Find nodes without dependencies.
• First take out the nodes without dependencies. Break their links.
• Next take out the other nodes by keeping in mind their dependencies.
• Repeat these steps until all nodes are taken out.

For the implementation of the solution to the given problem, we need to initialize a function create_graph which takes two parameters as input – the projects and the dependencies. The function creates a virtual graph using dictionaries.

#Initializing the function to create graph
def create_graph(projects, dependencies):
   project_graph = {}
   for project in projects:
       project_graph[project] = []
   for pairs in dependencies:
       project_graph[pairs[0]].extend(pairs[1])
   return project_graph
graph = create_graph(['A', 'B', 'C', 'D', 'E', 'F'], 
                     [('A','D'), ('F', 'B'), ('B','D'), ('F','A'), ('D','C')])

Further, we create the get_projects_wo_dependencies function which returns the set of projects without dependencies. Also, we create the get_projects_with_dependencies to return set of projects having dependencies.

#Functions to get projects with and w/o dependencies
#Getting projects with dependencies
def get_projects_with_dependencies(graph):
   projects_with_depen = set()
   for project in graph:
       projects_with_depen = projects_with_depen.union(set(graph[project]))
   
   return projects_with_depen

#Variable to store dependent projects 
dependents = get_projects_with_dependencies(graph)
 
#Getting projects without dependencies
def get_projects_wo_dependencies(projects_with, graph):
   projects_wo_dependencies = set()
   for project in graph:
       if not project in projects_with:
           projects_wo_dependencies.add(project)
   return projects_wo_dependencies
notDependents = get_projects_wo_dependencies(dependents, graph)

Finally, we create the find_build_order which takes projects and dependencies as parameters. The function creates a build order if possible. Otherwise, it returns an error message.

The find_build_order function is based on the following algorithm:

• Create the function and input projects and dependencies as parameters.
• Create an empty list called build_order.
• Iterate through the graph and store projects with dependencies and projects without dependencies into the variables projects_with_depen and projects_wo_depen respectively.
• Firstly, display all the projects without dependencies.
• If there are no projects without dependencies, raise a ValueError exception stating that the build order contains a cycle.
• Once, projects without dependencies are removed, there’ll be new projects without dependencies.
• Keep on displaying and removing independent projects until the graph is empty.

#Function to find the order of projects and dependencies
def find_build_order(projects, dependencies):
   build_order = []
   project_graph = create_graph(projects, dependencies)
   while project_graph:
       print(project_graph)
       projects_with_depen = get_projects_with_dependencies(project_graph)
       projects_wo_depen = get_projects_wo_dependencies(projects_with_depen, project_graph)
       print(projects_wo_depen)
       if len(projects_wo_depen) == 0 and project_graph:
           raise ValueError('There is a cycle in the build order')
       for independent_project in projects_wo_depen:
           build_order.append(independent_project)
           del project_graph[independent_project]
   return build_order
 
print(find_build_order(['A', 'B', 'C', 'D', 'E', 'F'], 
                       [('A','D'), ('F', 'B'), ('B','D'), ('F','A'), ('D','C')]))