Lab Assignment (Graph, Part-1)

1. A telecommunications company has a network of relay stations connected by data

transmission lines. To ensure optimal network performance, they need to know the
diameter of the network-the longest possible shortest path between any two relay stations.
The diameter represents the maximum communication delay, and the company aims to
minimize this by adjusting routes if needed. Write a C program to find the diameter of the
network in linear time. The network is represented as an undirected, unweighted graph
where nodes are relay stations and edges are transmission lines.

2. An energy company is planning to build a new power distribution grid that will supply
electricity to several new industrial plants across a large region. The company needs to
connect all these plants in a way that minimizes the total cost of building the grid. Each
pair of plants has a direct transmission line with a specific cost. The goal is to connect all
plants with the minimum possible cost, ensuring there is a continuous power supply to all
plants.

3. An Internet Service Provider (ISP) needs to optimize routing across its network of
routers. The ISP has several routers connected by various network links. Each link has a
latency associated with it, representing the time (in milliseconds) it takes for data packets
to travel from one router to another. Some links have optimizations or other conditions
(such as traffic priorities) that may result in negative latency values, making certain routes
faster than expected.

The ISP needs a solution to:

 Find the shortest path (minimum latency) from a primary router (source) to every
other router in the network.
 Detect any negative latency cycles, which could indicate routing issues or
inconsistencies that allow packets to endlessly circulate and delay transmission.

Input Format:

 Number of routers: N (1<=N<=100)

 Number of network links: M {1<=M<=N (N-1)}
 List of network links between routers: Each link is defined by three values: u, v, and
latency, where:
1. u and v are the router IDs.
2. Latency represents the time in milliseconds to transmit data from u to
v. This value can be negative.

Output Format:

 If there are no negative latency cycles:

1. Print the shortest latency values from the source router to each other router.
2. For each router, display either the minimum latency or a message indicating it
is unreachable from the source.
 If a negative latency cycle exists, display a warning indicating an issue in the
routing network.
4. An oil and gas company operates a vast network of pipelines connecting various pumping
stations and storage facilities across a region. To ensure operational safety and efficiency,
the company needs to inspect each pipeline and station periodically. During an inspection
round, each station and pipeline must be visited to ensure there are no leaks, corrosion, or
blockages. However, due to operational limitations, the inspection team can only visit
each station once per round. To plan the inspection route, the company wants to start
from a primary station and traverse the entire network, visiting each station and pipeline
exactly once.

Write a C program that:

 Traverse the pipeline network starting from a specified source station.

 Ensures that each station is visited only once.
 Outputs the order of visited stations, which the inspection team will use as
their route.

(Dr. Vibhav Prakash Singh)