# 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

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)
path = True
break
else:
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].extend(pairs)
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:
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')]))``````