Assignment no.

9
Title: Applications of Tree and Graph

• Part 1
1. Problem Statement: You are tasked with designing a Logistics Tree application for a
company that manages the transportation and distribution of goods. The company operates in multiple
regions, each with its own set of warehouses and delivery routes.
2. Requirements:
a. Region Representation: Implement a tree data stmcture to represent the hierarchy of
regions. Each node represents a region, and child nodes represent sub-regions or
warehouses.
b. Warehouse Management: Allow the user to add, remove, and update information for
warehouses (e.g., name, location, capacity).
c. Route Planning: Design an algorithm to find the most efficient delivery route from one
warehouse to another within a region. Use appropriate data stmctures (e.g., graph) to
represent routes.
d. Inventory Management: Implement operations to add, remove, and update the inventory of
goods at each warehouse.
e. Goods Transfer: Provide fimctionality to transfer goods between warehouses, ensuring that
the transferred quantity does not exceed the capacity of the receiving warehouse.
f. Cost Calculation: Calculate the cost of transporting goods between warehouses, considering
factors like distance, mode of transport, and quantity of goods.
g. Route Optimization: Optimize routes for multiple deliveries within a region to minimize
overall transportation costs and time.
h. Reporting and Analytics: Generate reports on inventory levels, transportation costs, and
delivery times. Implement basic analytics to identify trends and areas for improvement.
User Interface: Develop a user-friendly interface for interacting with the application, allowing
users to perform operations easily.

• Part 2
1. Problem Statement: You are tasked with designing a Train Joumey Alternative Route application that
helps travelers find alternative routes in case of disruptions or delays in train services.
2. Requirements:
a. Graph Representation: Implement a graph data stmcture to represent the train network.
Each node represents a train station, and edges represent the train routes connecting the
stations.
b. Station Information: Allow the user to add, remove, and update information for train
stations (e.g., name, location, platform details) as nodes in the graph.
c. Route Planning: Design an algorithm to find alternative routes between two stations if there
are disruptions or delays in the original route. Use graph traversal algorithms like Dijkstm's
to find the shortest and most efficient alternative routes.
d. Disruption Handling: Simulate disruptions or delays in the train network. When a
disruption occurs, the application should quickly identify alternative routes and provide
them to the user.
e. Cost Calculation: Calculate the cost of taking alternative routes, considering factors like
travel time, number of transfers, and ticket prices.
f. Route Display: Display the alternative routes to the user, including information such as
stations, transfer points, and estimated travel time.
g. User Interface: Develop a user-friendly interface for travelers to interact with the
application, allowing them to input their departure and destination stations, view alternative
routes, and get relevant information.
 • Part 1
#include <stdio.h> #include
<stdlib.h> #include <string.h>

#define MAX WAREHOUSES 100 #define MAX

REGIONS 100

// Structure to store loca on details typedef

struct { double la tude; double longitude;

} Loca on;

// Structure to represent an item in the warehouse typedef

struct { char name[50];
int id; int
quan ty;

} Item;

// Structure to represent a warehouse typedef

struct { char name[50]; Loca on loca on; int
capacity; Item inventory[100]; int itemCount;

} Warehouse;

// Structure to represent a region (tree node) typedef

struct Region { char name[50]; struct Region
*subRegions[MAX_REGlONS]; int subRegionCount;

Wa rehouse wa HOUSES];

int wa rehouseCount;

} Region;

// Func on to create a new region

Region* createRegion(const char *name) {

Region *region = (Region *)malloc(sizeof(Region)); if (!region) {

prin ("Memory alloca on failed for region.\n"); exit(l);
 strcpy(region->name, name); region-
>subRegionCount = O; region-
>warehouseCount = O; return region;

// Func on to add a sub-region to a region void addSubRegion(Region *parent,

Region *subRegion) { if (parent->subRegionCount < MAX_REGIONS) { parent-
>subRegions[parent->subRegionCount++] = subRegion;

prin ("Maximum sub-region limit reached for region %s\n", parent->name);

// Func on to ini alize a new warehouse

Warehouse createWarehouse(const char *name, double la tude, double longitude, int capacity) {

Warehouse warehouse; strcpy(warehouse.name,

name); warehouse.loca on.la tude = la tude;
warehouse.loca on.longitude = longitude;
warehouse.capacity = capacity;
warehouse.itemCount = O; return warehouse;

// Func on to add a warehouse to a region void addWarehouse(Region *region,

Warehouse warehouse) { if (region->warehouseCount < MAX_WAREHOUSES) { region-
>warehouses[region->warehouseCount++] = warehouse;

prin ("Maximum warehouse limit reached for region %s\n", region->name);

// Func on to add an item to a warehouse

void addltemToWarehouse(Warehouse *warehouse, const char *itemName, int itemld, int quan ty) { if
(warehouse->itemCount < 100) { strcpy(warehouse->inventory[warehouse->itemCount].name, itemName);
warehouse->inventory[warehouse->itemCount].id = itemld;

warehouse->inventory[warehouse->itemCount].quan ty = quan ty; warehouse->itemCount++;

prin ("lnventory is full in warehouse %s\n", warehouse->name);

// Func on to print details of a region void
printRegionDetails(Region *region) { prin ("Region: %s\n",
region->name); prin ("Warehouses:\n"); for (int i = O; i <
region->warehouseCount; i++) {
prin (" - %s (Capacity: %d)\n", region->warehouses[i].name, region-
>warehouses[i].capacity);

prin ("Sub-regions:\n"); for (int i = O; i < region-

>subRegionCount; i++) { prin (" - %s\n", region->subRegions[i]-
>name);

// Main func on for demonstra on int main() {

// Create the root region

Region *globalRegion = createRegion("Global Region");

// Create a sub-region and add it to the root region

Region *europe = createRegion("Europe");
addSubRegion(globalRegion, europe);

// Create a warehouse and add it to the "Europe" region

Warehouse warehouseA = createWarehouse("Warehouse A", 48.8566, 2.3522, 1000); addWarehouse(europe,

warehouseA);

// Add an item to the warehouse addltemToWarehouse(&warehouseA, " Iteml", 101,

500);

// Print details of the global region printRegionDetails(globalRegion);

// Free allocated memory

free(globalRegion); free(europe);

return O;
 Part 2
#include <stdio.h> #include
<stdlib.h> #include <string.h>
#include <limits.h>

#define MAX STATIONS 100

// Structure to represent a train sta on typedef

struct Sta on { char name[50]; int
pla orm_count;

} Sta on;

// Structure to represent an edge in the graph (train route) typedef struct

Route { int des na on; int distance; int cost; struct Route* next;
} Route;

// Structure to represent the adjacency list for each sta on typedef struct
{ Sta on sta on;
Route* routes;

} Sta onNode;

// Graph structure to represent the train network

typedef struct { int num

sta ons;
Sta onNode sta ons[MAX_STATlONS];

} TrainNetwork;

// Ini alize the train network void

initNetwork(TrainNetwork* network) { network->num
sta ons = O; for (int i = O; i < MAX_STATIONS; i++) {
network->sta ons[i].routes = NULL;
// Add a sta on to the network int addSta on(TrainNetwork* network, const char* name, int
pla orm_count) { if (network->num_sta ons >= MAX_STATIONS) { prin ("Max sta on limit
reached.\n"); return -1;

int sta on id = network->num sta ons++; strcpy(network-

>sta ons[sta on_id].sta on.name, name); network-
>sta ons[sta on_id].sta on.pla orm_count = pla orm_count; return sta on id;

// Add a route (edge) between two sta ons void addRoute(TrainNetwork* network, int src, int dest,
int distance, int cost) {
Route* route = (Route*)malloc(sizeof(Route)); route->des na on = dest;

route->distance = distance; route->cost = cost; route-

>next = network->sta ons[src].routes; network-
>sta ons[src].routes = route;

// Display the train network void displayNetwork(const TrainNetwork* network)

{ for (int i = O; i < network->num_sta ons; i++) { prin ("Sta on: %s\n", network-
>sta ons[i].sta on.name);
Route* route = network->sta ons[i].routes; while
(route) { prin (" -> %s (Distance: %d, Cost: %d)\n",

.sta on.name,

route->distance,
route->cost); route =
route->next;

// Helper func on for Dijkstra's algorithm to find the minimum distance int minDistance(int
dist[], int sptSet[], int num_sta ons) { int min = INT MAX, min index; for (int v = O; v <
num_sta ons; v++) if (!sptSet[v] && dist[v] <= min) min = dist[v], min_index = v; return min
index;
// Dijkstra's algorithm to find the shortest path void
dijkstra(TrainNetwork* network, int src, int dest) { int num sta ons =
network->num sta ons; int int int

for (int i
= O; i <
num_sta ons; i++) { dist[i] = INT_MAX;
sptSet[i] = O; prev[l]

dist[src] = O;

for (int count = O; count < num_sta ons - 1; count++) { int u =

minDistance(dist, sptSet, num_sta ons); sptSet[u] = 1;

for (Route* route = network->sta ons[u].routes; route != NULL; route = route->next) { int v = route-
>des na on; if (!sptSet[v] && dist[u] != INT_MAX && dist[u] + route->distance < dist[v]) { dist[v] = dist[u]
+ route->distance; prev[v] = u;

// Display the shortest path prin ("Shortest path from %s to %s:\n", network->sta ons[src].sta on.name,
network .sta on.name); int current = dest; while (current != prin ("%s <- ", network-
>sta ons[current].sta on.name); current = prev[current];

prin ("\nTotal Distance: %d\n", dist[dest]);

// Main func on to demonstrate usage int main() {

TrainNetwork network; initNetwork(&network);

// Adding sta ons int a = addSta on(&network, "Sta on

A", 5); int b = addSta on(&network, "Sta on B", 3); int c
= addSta on(&network, "Sta on C", 4); int d =
addSta on(&network, "Sta on D", 2);
// Adding routes addRoute(&network, a, b, 10, 50); addRoute(&network, a, c, 15, 70);
addRoute(&network, b, d, 12, 40); addRoute(&network, c, d, 10, 60); addRoute(&network, d, b,
12, 40); // reverse for undirected representa on

// Display the network

displayNetwork(&network);

// Finding shortest path from Sta on A to Sta on D dijkstra(&network,

a, d);

return O;