OOPS

Assignment - 6

Objective

Enter entry point & goal point & produce the matching subtree of the graph.

Programming Language & Compilation

• Python 3.9.x +

# install networkx (https://github.com/networkx/networkx)
$ python3 -m pip install networkx
# install https://github.com/matplotlib/matplotlib
$ python3 -m pip install matplotlib
# run the code below
$ python3 main.py

Source Code

The implementation derives from the code written in the Assignment - 5.

Now MapVisualizer contains two new methods:

• get_shortest_path_subgraph: returns nx.Graph after finding shortest path between start and end using Dijkstra.
• visualize_shortest_path: shows the matching subtree in user-interface.

Thus, shortest path between the entry point & goal point is calculated and then the matching subtree of the graph is drawn.

More details are available as comments in the code snippet below.

Though, generated outputs are good most of the times, there can be few issues because no weightage is assigned to the edges. This is addressed in the Assignment - 7, because we give account to weightage aswell there.

import networkx as nx
import matplotlib.pyplot as plt

# A `Location` object describes a location on the map, which holds:
# 1. Name of that location.
# 2. Other locations that it is connected to.
#
# This data is then later used to create a graph.
#
class Location:
    name: str
    connections: list[str]

    def __init__(self, name: str, connections: list[str]):
        self.name = name
        self.connections = connections


# Primary class to visualize the given map.
# This class contains the main logic to create the graph and visualize it.
# Takes in a list of `Location` objects in its parameterized constructor.
class MapVisualizer:
    # Used for map visualization.
    visual: list[list[str]] = []

    def __init__(self, locations: list[Location]):
        # Iterate over the nodes, provided as `Location` objects.
        for a in locations:
            for b in a.connections:
                self.add_edge(a.name, b)

    # Gets the sub-graph providing the shortest path between two locations.
    # Uses dijkstra algorithm.
    def get_shortest_path_subgraph(self, start: str, end: str) -> nx.Graph:
        graph = nx.Graph()
        graph.add_edges_from(self.visual)
        # returns path as a `list`.
        path = nx.shortest_path(
            graph,
            start,
            end,
            method="dijkstra",
        )
        # turn path into a `list` of edges, using generator function.
        edges = [(path[i], path[i + 1]) for i in range(len(path) - 1)]
        result = nx.Graph()
        result.add_edges_from(edges)
        return result

    # A helper method to connect to location nodes.
    def add_edge(self, a: str, b: str) -> None:
        self.visual.append([a, b])

    # Displays a sub-graph between two locations.
    def visualize_shortest_path(self, start: str, end: str) -> None:
        nx.draw(
            self.get_shortest_path_subgraph(start, end),
            with_labels=True,
            node_color="#81d4fa",
            edge_color="#aaaaaa",
            node_size=1000,
        )
        plt.show()

    # Display the created map as graph.
    def visualize(self) -> None:
        graph = nx.Graph()
        graph.add_edges_from(self.visual)
        nx.draw(
            graph,
            with_labels=True,
            node_color="#81d4fa",
            edge_color="#aaaaaa",
            node_size=1000,
        )
        plt.show()


# Entry point of the program.
if __name__ == "__main__":
    # List of location objects that should be represnted.
    locations = [
        # Location("name of location", ["places", "it", "is", "connected", "to"])
        Location(
            "Haldwani",
            ["Lal Kuan"],
        ),
        Location(
            "Lal Kuan",
            ["Haldwani", "Nagla"],
        ),
        Location(
            "College of Fisheries",
            ["Nagla", "Stevenson Stadium"],
        ),
        Location(
            "Stevenson Stadium",
            ["College of Fisheries", "Tagore Bhawan"],
        ),
        Location(
            "Tagore Bhawan",
            ["Stevenson Stadium", "Patel Bhawan", "College of Technology"],
        ),
        Location(
            "Patel Bhawan",
            ["Tagore Bhawan", "Silver Jubliee Bhawan", "College of Technology"],
        ),
        Location(
            "Silver Jubliee Bhawan",
            ["Patel Bhawan", "Visvesvaraya Bhawan"],
        ),
        Location(
            "Visvesvaraya Bhawan",
            [
                "Silver Jubliee Bhawan",
                "Badi Market",
                "Chhoti Market",
                "College of Technology",
            ],
        ),
        Location(
            "Chhoti Market",
            ["Visvesvaraya Bhawan"],
        ),
        Location(
            "Badi Market",
            ["Visvesvaraya Bhawan", "Registrar Office"],
        ),
        Location(
            "Registrar Office",
            ["Library", "Badi Market"],
        ),
        Location(
            "Library",
            ["College of Technology", "Registrar Office"],
        ),
        Location(
            "TIC",
            ["Patel Bhawan", "Silver Jubliee Bhawan"],
        ),
        Location(
            "University Hospital",
            ["Badi Market"],
        ),
    ]
    # Create new object instance & pass the location object references.
    visualizer = MapVisualizer(locations)
    # Call |visualize_shortest_path| to visualize the shortest path between two locations.
    visualizer.visualize_shortest_path("Library", "Chhoti Market")

Output

right-click & select “Open image in new tab” for larger image.

CORRECT: Shortest path sub-graph from Library to Chhoti Market.

CORRECT: Shortest path sub-graph from Badi Market to TIC.

INCORRECT: Shortest path sub-graph from Visvesvaraya Bhawan to Tagore Bhawan.

This is because College of Technology is acting as single node between the two & the two other nodes with the correct shortest path i.e. Patel Bhawan and Silver Jubliee Bhawan make the path longer without manually assigned weightage. Even though, in real life, College of Technology is situated way far compared to these two nodes i.e. Patel Bhawan and Silver Jubliee Bhawan.

This is addressed in the Assignment - 7, because we give account to weightage aswell there.