OOPS

Assignment - 7

Objective

Give the weightage for each edge of nodes, and produce the shortest path from start to end node.

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 - 6.

Major improvements in this version include the introduction of new Destination class which is used to pass various reachable destinations from a Location along with their weight/path-length.

Thus, calculated sub-graph is more precise due to correctly assigned weights to various edges.

import networkx as nx
import matplotlib.pyplot as plt


class Destination:
    name: str
    edge_weightage: int

    def __init__(self, name: str, edge_weightage: int):
        self.name = name
        self.edge_weightage = edge_weightage


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

    def __init__(self, name: str, connections: list["Destination"]):
        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] = []

    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.name, b.edge_weightage)

    # 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()
        for edge in self.visual:
            graph.add_edge(edge[0], edge[1], length=edge[2])
        # returns path as a `list`.
        path = nx.shortest_path(
            graph,
            start,
            end,
            method="dijkstra",
            weight="length",
        )
        # 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, weight: int) -> None:
        self.visual.append([a, b, weight])

    # 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()
        for edge in self.visual:
            graph.add_edge(edge[0], edge[1], length=edge[2])
        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", [Destination("name of destination", weightage), Destination("name of destination", weightage), ...])
        Location(
            "Haldwani",
            [
                Destination("Lal Kuan", 100),
            ],
        ),
        Location(
            "Lal Kuan",
            [
                Destination("Nagla", 40),
            ],
        ),
        Location(
            "Nagla",
            [
                Destination("College of Fisheries", 20),
            ],
        ),
        Location(
            "College of Fisheries",
            [
                Destination("Stevenson Stadium", 30),
            ],
        ),
        Location(
            "Tagore Bhawan",
            [
                Destination("Stevenson Stadium", 2),
                Destination("Patel Bhawan", 2),
                Destination("College of Technology", 12),
            ],
        ),
        Location(
            "Patel Bhawan",
            [
                Destination("Silver Jubliee Bhawan", 2),
                Destination("College of Technology", 10),
            ],
        ),
        Location(
            "Silver Jubliee Bhawan",
            [
                Destination("Visvesvaraya Bhawan", 2),
            ],
        ),
        Location(
            "Visvesvaraya Bhawan",
            [
                Destination("Badi Market", 16),
                Destination("Chhoti Market", 3),
                Destination("College of Technology", 11),
            ],
        ),
        Location(
            "Badi Market",
            [
                Destination("Registrar Office", 8),
            ],
        ),
        Location(
            "Registrar Office",
            [Destination("Library", 1)],
        ),
        Location(
            "Library",
            [Destination("College of Technology", 4)],
        ),
        Location(
            "TIC",
            [Destination("Patel Bhawan", 1), Destination("Silver Jubliee Bhawan", 1)],
        ),
        Location(
            "University Hospital",
            [Destination("Badi Market", 1)],
        ),
    ]
    # 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("Tagore Bhawan", "Visvesvaraya Bhawan")

Output

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

Path from Visvesvaraya Bhawan to Tagore Bhawan correctly visualized after edge weight assignment.