AIT — Discrete Mathematics (PCC-203-COM) | CCE-II Case Studies | Roll No: 12
CODE — CASE STUDY 1
JAVA FILE :
1 import [Link].*;
2
3 public class KruskalMST {
4
5 static int[] parent, rank;
6
7 // Find root with path compression
8 static int find(int x) {
9 if (parent[x] != x)
10 parent[x] = find(parent[x]);
11 return parent[x];
12 }
13
14 // Union by rank
15 static void union(int x, int y) {
16 int rootX = find(x);
17 int rootY = find(y);
18 if (rootX == rootY) return;
19 parent[rootY] = rootX;
23 else {
24 parent[rootY] = rootX; rank[rootX]++;
25 }
26 }
27
28 public static void main(String[] args) {
29 String[] cities = {
30 "Pune", "Mumbai", "Nashik", "Aurangabad",
31 "Kolhapur", "Solapur", "Nagpur"};
32 int V = [Link];
33
34 // edges: {cityA_index, cityB_index, cost_crores}
AIT — Discrete Mathematics (PCC-203-COM) | CCE-II Case Studies | Roll No: 12
35 int[][] edges = {
36 {0,1,15}, {0,2,22}, {1,2,18},
37 {2,3,12}, {3,6,30}, {0,4,20},
38 {4,5,16}, {5,3,14}, {5,0,25} };
39
40 // Sort edges by cost (Kruskal's Step 1)
41 [Link](edges, (a, b) -> a[2] - b[2]);
42
43 parent = new int[V];
44 rank = new int[V];
45 for (int i = 0; i < V; i++) parent[i] = i;
46
47 int totalCost = 0;
48 [Link]("%-20s %-20s %s%n",
49 "City A", "City B", "Cost (Cr)");
50
51 for (int[] edge : edges), {
52 int u = edge[0], v = edge[1], w = edge[2];
53 if (find(u) != find(v)) {
54 union(u, v); totalCost += w;
55 [Link]("%-20s %-20s %d%n",
56 cities[u], cities[v], w);
57 }
58 }
59 [Link]("Total Minimum Cost: " + totalCost + " Crores");
60 }
61 }
HTML FILE :
1 <!DOCTYPE html>
2 <html lang="en">
3 <head>
4 <meta charset="UTF-8">
5 <title>MST City Network Visualizer</title>
AIT — Discrete Mathematics (PCC-203-COM) | CCE-II Case Studies | Roll No: 12
6 <script src="[Link]
7 <style>
8 body { font-family: Arial; background: "#f0f4f8"; text-align: center; }
9 h2 { color: "#1F3864"; }
10 #info { color: "#2E75B6"; font-size: 18px; font-weight: bold; }
11 button { background: "#2E75B6"; color: #fff; border: none;
12 padding: 8px 16px; margin: 6px; border-radius: 4px; cursor: pointer; }
13 </style>
14 </head>
15 <body>
16 <h2>MST — Minimum Spanning Tree: City Network</h2>
17 <div id="applet1"></div>
18 <div id="info">Total MST Cost: 0 Crores</div>
19 <button onclick="showAllEdges()">Show All Edges</button>
20 <button onclick="showMSTOnly()">Animate MST</button>
21 <button onclick="resetGraph()">Reset</button>
22
23 <script>
24 var params = {
25 appName: "geometry",
26 width: 750, height: 500,
27 showToolBar: false, showAlgebraInput: false,
28 showMenuBar: false, enableRightClick: false,
29 appletOnLoad: function(api) { [Link] = api; initGraph(); }
30 };
31 var applet = new GGBApplet(params, true);
32 [Link]("load", function() {
33 [Link]("applet1");
34 });
35
36 // City positions (x,y) — approximate geographic layout
37 var cities = [
38 {name: "Pune", x: 2, y: 3},
39 {name: "Mumbai", x: 0, y: 5},
40 {name: "Nashik", x: 3, y: 6},
AIT — Discrete Mathematics (PCC-203-COM) | CCE-II Case Studies | Roll No: 12
41 {name: "Aurangabad", x: 5, y: 5},
42 {name: "Kolhapur", x: 1, y: 1},
43 {name: "Solapur", x: 4, y: 2},
44 {name: "Nagpur", x: 8, y: 5} ];
45
46 var mstEdges = [
47 {a:2,b:3,w:12}, {a:5,b:3,w:14},
48 {a:0,b:1,w:15}, {a:4,b:5,w:16},
49 {a:1,b:2,w:18}, {a:3,b:6,w:30} ];
50
51 function showMSTOnly() {
52 var api = [Link], total = 0, delay = 0;
53 [Link](function(e, i) {
54 setTimeout(function() {
55 [Link]('mst'+i+'=Segment(C'+e.a+',C'+e.b+')');
56 [Link]('SetColor(mst'+i+",0,150,80)');
57 [Link]('SetLineThickness(mst'+i+',5)');
58 total += e.w;
59 [Link]("info").innerText =
60 "Total MST Cost: " + total + " Crores";
61 }, delay); delay += 800;
62 });
63 }
64 </script>
65 </body></html>if (rank[rootX] < rank[rootY])
20 parent[rootX] = rootY;
21 else if (rank[rootX] > rank[rootY])
22 parent[rootY] = rootX;
23 else {
24 parent[rootY] = rootX; rank[rootX]++;
25 }
26 }
27
28 public static void main(String[] args) {
29 String[] cities = {
AIT — Discrete Mathematics (PCC-203-COM) | CCE-II Case Studies | Roll No: 12
30 "Pune", "Mumbai", "Nashik", "Aurangabad",
31 "Kolhapur", "Solapur", "Nagpur"};
32 int V = [Link];
33
34 // edges: {cityA_index, cityB_index, cost_crores}
35 int[][] edges = {
36 {0,1,15}, {0,2,22}, {1,2,18},
37 {2,3,12}, {3,6,30}, {0,4,20},
38 {4,5,16}, {5,3,14}, {5,0,25} };
39
40 // Sort edges by cost (Kruskal's Step 1)
41 [Link](edges, (a, b) -> a[2] - b[2]);
42
43 parent = new int[V];
44 rank = new int[V];
45 for (int i = 0; i < V; i++) parent[i] = i;
46
47 int totalCost = 0;
48 [Link]("%-20s %-20s %s%n",
49 "City A", "City B", "Cost (Cr)");
50
51 for (int[] edge : edges), {
52 int u = edge[0], v = edge[1], w = edge[2];
53 if (find(u) != find(v)) {
54 union(u, v); totalCost += w;
55 [Link]("%-20s %-20s %d%n",
56 cities[u], cities[v], w);
57 }
58 }
59 [Link]("Total Minimum Cost: " + totalCost + " Crores");
60 }
61 }