Dsa Assignment 3
Problem Statement
A. (15 marks) Generate a regular lattice.
Write a Python program to create a Regular Lattice graph. You are allowed to use the NetworkX package, but only the basic functions — you cannot use any graph generation routines that are built in. A regular lattice is one in which each node is connected to k nearest neighbours on either side – connecting each node to 2k other nodes effectively. Construct a regular lattice graph with 50 nodes and k=3. Plot the graph within the function, as given in the template.
B. (45 marks) Maze.
Given a matrix of ‘1’s and ‘0’s that represents a maze, and the indices of the starting and finishing points, generate a NetworkX graph where each node represents a ‘1’ in the input matrix, and print:
a) A list of indices in the shortest path solution to the maze (in the order of the path)
b) A list of lists of indices in the isolated components of the maze (order doesn’t matter)
● ‘0’s in the input represent walls (cannot be part of a path) and ‘1’s represent open points (allowed in paths). (Visualise the matrix like a crossword grid, where ‘0’s are the darkened out blocks.)
● Traversal is allowed up, down, left, and right - diagonally adjacent ‘1’s cannot form a path.
● The matrix is indexed from (0,0).
● Label the nodes of the graph as tuples of their indices in the input matrix.
● A path is a series of ‘1’s that can be reached with the allowed travel directions.
● An isolated component is a group of ‘1’s that can’t reach other ‘1’s via allowed travel directions.
(a) Use a BFS algorithm on the graph data structure. Assume the maze has at least one solution. The algorithm should work even if there are loops, as below.
(b) Use a DFS algorithm on the graph data structure. Hint: iterate this repeatedly until all the components are identified.
You are allowed to use only the basic functions in NetworkX, you cannot use built-in graph generation routines or traversal/shortest-path functions.
A. (15 marks) Generate a regular lattice.
Write a Python program to create a Regular Lattice graph. You are allowed to use the NetworkX package, but only the basic functions — you cannot use any graph generation routines that are built in. A regular lattice is one in which each node is connected to k nearest neighbours on either side – connecting each node to 2k other nodes effectively. Construct a regular lattice graph with 50 nodes and k=3. Plot the graph within the function, as given in the template.
B. (45 marks) Maze.
Given a matrix of ‘1’s and ‘0’s that represents a maze, and the indices of the starting and finishing points, generate a NetworkX graph where each node represents a ‘1’ in the input matrix, and print:
a) A list of indices in the shortest path solution to the maze (in the order of the path)
b) A list of lists of indices in the isolated components of the maze (order doesn’t matter)
● ‘0’s in the input represent walls (cannot be part of a path) and ‘1’s represent open points (allowed in paths). (Visualise the matrix like a crossword grid, where ‘0’s are the darkened out blocks.)
● Traversal is allowed up, down, left, and right - diagonally adjacent ‘1’s cannot form a path.
● The matrix is indexed from (0,0).
● Label the nodes of the graph as tuples of their indices in the input matrix.
● A path is a series of ‘1’s that can be reached with the allowed travel directions.
● An isolated component is a group of ‘1’s that can’t reach other ‘1’s via allowed travel directions.
(a) Use a BFS algorithm on the graph data structure. Assume the maze has at least one solution. The algorithm should work even if there are loops, as below.
(b) Use a DFS algorithm on the graph data structure. Hint: iterate this repeatedly until all the components are identified.
You are allowed to use only the basic functions in NetworkX, you cannot use built-in graph generation routines or traversal/shortest-path functions.
Comments
Post a Comment