In this post, we’ll explore how to implement a Multi-Stage Graph in Java — a specialized graph where each stage (or node) has connections to only certain other stages, and the goal is to find the optimal path and cost through the stages.
What is a Multi-Stage Graph?
A Multi-Stage Graph is a graph where the nodes are grouped into distinct stages, and each node can only connect to the next stage in the sequence. The algorithm finds the minimum cost and optimal path from the start node (source) to the end node (destination).
In this post, we’ll focus on two methods to compute the optimal path:
- Forward Method: Compute the cost and parent nodes starting from the destination.
- Backward Method: Compute the cost and parent nodes starting from the source.
How the Multi-Stage Graph Algorithm Works
- Graph Representation:
The graph is represented using a 2D matrix wherex[i][j]denotes the weight or cost of the edge from nodeito nodej. A value of 0 means there is no direct edge between the nodes. - Cost Calculation:
- In the Forward Method, we start from the destination node and move backward to compute the cost for each stage.
- In the Backward Method, we start from the source node and compute the cost to each destination node.
- Optimal Path:
The algorithm tracks the parent node for each stage, allowing us to trace the optimal path after computing the costs.
Java Code Implementation
import java.io.*;
class multi {
public static void main(String args[]) throws IOException {
// Reading input from the user
BufferedReader o = new BufferedReader(new InputStreamReader(System.in));
// Defining the multi-stage graph as a 2D array where x[i][j] denotes the cost from node i to node j
int x[][] = {
{0, 1, 2, 3, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 4, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 4, 3, 0, 0, 0, 0},
{0, 0, 0, 0, 2, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 6, 7, 2, 0},
{0, 0, 0, 0, 0, 0, 4, 2, 3, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 2},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 3},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
// Arrays to store the minimum cost and the parent for each node
int i, j, c, a;
int s[] = new int[20]; // Array to store the minimum cost to reach each stage
int p[] = new int[20]; // Array to store the parent of each node
int temp[] = new int[20]; // Temporary array for cost calculations
// Initializing the arrays for cost and parent nodes
for (i = 0; i < 10; i++) {
s[i] = 0;
temp[i] = 0;
p[i] = 0;
}
// Displaying the menu to the user to choose between the Forward or Backward method
System.out.println("\n\nProgram for MultiStage Graph\n\n");
System.out.println("Select Any one Method\n");
System.out.println("1. Forward Method\n");
System.out.println("2. Backward Method\n\t");
a = Integer.parseInt(o.readLine());
// Switch statement to select between Forward or Backward Method
switch (a) {
case 1:
// Forward Method: Start from the destination node and compute the cost for each stage
for (i = 9; i >= 0; i--) {
c = 0;
// Check all possible connections for the current node
for (j = 0; j <= 9; j++) {
if (x[i][j] != 0) { // If there is a connection from node i to node j
if (c == 0) { // First connection for node i
s[i] = s[j] + x[i][j]; // Compute the cost
p[i] = j; // Store the parent node
c = 1;
} else {
temp[i] = s[j] + x[i][j]; // Calculate the cost for the new connection
if (temp[i] < s[i]) { // Update the cost and parent if the new cost is less
s[i] = s[j] + x[i][j];
p[i] = j;
}
}
}
}
}
// Displaying the Source-Cost-Parent table
System.out.println("\nSource Cost Parent");
for (i = 9; i >= 0; i--) {
System.out.print("\n " + i);
System.out.print(" \t " + s[i]);
System.out.print(" \t " + p[i]);
}
System.out.println("\n\n");
System.out.println("\n\nOptimal Path:\n\t");
// Tracing the optimal path from source (0) to destination (9)
i = p[0];
System.out.print("0-->" + i);
while (i != 9) { // Keep tracing the parent nodes until we reach the destination
i = p[i];
System.out.print("-->" + i);
}
break;
case 2:
// Backward Method: Start from the source node and compute the cost to each destination node
for (j = 0; j <= 9; j++) {
c = 0;
// Check all possible connections for the current node
for (i = 0; i <= 9; i++) {
if (x[i][j] != 0) { // If there is a connection from node i to node j
if (c == 0) { // First connection for node j
s[j] = s[i] + x[i][j]; // Compute the cost
p[j] = i; // Store the parent node
c = 1;
} else {
temp[j] = s[i] + x[i][j]; // Calculate the cost for the new connection
if (temp[j] < s[j]) { // Update the cost and parent if the new cost is less
s[j] = s[i] + x[i][j];
p[j] = i;
}
}
}
}
}
// Displaying the Source-Cost-Parent table
System.out.println("\nSource Cost Parent");
for (i = 0; i <= 9; i++) {
System.out.print("\n " + i);
System.out.print(" \t " + s[i]);
System.out.print(" \t " + p[i]);
}
System.out.println("\n\n");
System.out.println("\n\nOptimal Path:\n\t");
// Tracing the optimal path from source (0) to destination (9)
i = p[9];
System.out.print("9-->" + i);
while (i != 0) { // Keep tracing the parent nodes until we reach the source
i = p[i];
System.out.print("-->" + i);
}
break;
}
}
}
Sample Output
Program for MultiStage Graph
Select Any one Method
1. Forward Method
2. Backward Method
1
Source Cost Parent
9 0 0
8 3 9
7 2 9
6 1 9
5 4 7
4 5 8
3 5 5
2 7 5
1 9 4
0 8 3
Optimal Path:
0-->3-->5-->7-->9
Program for MultiStage Graph
Select Any one Method
1. Forward Method
2. Backward Method
2
Source Cost Parent
0 0 0
1 1 0
2 2 0
3 3 0
4 5 1
5 4 3
6 8 5
7 6 5
8 7 4
9 8 7
Optimal Path:
9-->7-->5-->3-->0Explanation of the Output
Let’s break down the output step by step in more detail, both for the Forward Method and the Backward Method.
1. Forward Method
Step 1: Source-Cost-Parent Table
After selecting the Forward Method, the program starts from the destination node (node 9) and works backwards to compute the minimum cost and the parent node for each stage. The output shows the Source-Cost-Parent table, which represents the minimum cost to reach each node and its parent node in the optimal path.
Here’s the table for the Forward Method:
Source Cost Parent
9 0 0
8 3 9
7 2 9
6 1 9
5 4 7
4 5 8
3 5 5
2 7 5
1 9 4
0 8 3- Source (Node): The node number.
- Cost: The minimum cost to reach that node from the destination (node 9) in the case of the Forward Method.
- Parent: The parent node that leads to the optimal path for that particular node.
Step 2: How the Costs Are Computed
To understand how the costs are calculated, let’s take a look at how the program computes the minimum cost for each node. The algorithm starts at node 9 (destination) and calculates the cost for each node moving backward through the stages:
- For node 9:
- The minimum cost is
0because we are at the destination. - There is no parent because this is the end node.
- The minimum cost is
- For node 8:
- The possible connection is from node 9 to node 8 with a cost of 3 (
x[9][8] = 3). - The total cost is 3 (the cost from node 9 to node 8).
- The parent is node 9, as it’s the only node that connects to node 8.
- The possible connection is from node 9 to node 8 with a cost of 3 (
- For node 7:
- The possible connection is from node 9 to node 7 with a cost of 2 (
x[9][7] = 2). - The total cost is 2 (the cost from node 9 to node 7).
- The parent is node 9.
- The possible connection is from node 9 to node 7 with a cost of 2 (
- This pattern continues for all the other nodes, with the minimum cost calculated for each based on available connections.
Step 3: Tracing the Optimal Path
After calculating the cost and parent nodes, the algorithm then traces the optimal path from the source (node 0) to the destination (node 9).
Here’s how the path is traced:
- Start from node 0, and look at the parent of node 0, which is node 3 (from the table).
- Move to node 3, and the parent of node 3 is node 5.
- Move to node 5, and the parent of node 5 is node 7.
- Move to node 7, and the parent of node 7 is node 9.
- The destination node 9 has no parent (it’s the end of the path).
Thus, the optimal path for the Forward Method is:
Optimal Path:
0-->3-->5-->7-->92. Backward Method
Step 1: Source-Cost-Parent Table
After selecting the Backward Method, the program starts from the source node (node 0) and works forwards to compute the minimum cost and parent node for each stage. The output shows the Source-Cost-Parent table, representing the minimum cost to reach each node and its parent node in the optimal path.
Here’s the table for the Backward Method:
Source Cost Parent
0 0 0
1 1 0
2 2 0
3 3 0
4 5 1
5 4 3
6 8 5
7 6 5
8 7 4
9 8 7- Source (Node): The node number.
- Cost: The minimum cost to reach that node from the source (node 0) in the case of the Backward Method.
- Parent: The parent node that leads to the optimal path for that particular node.
Step 2: How the Costs Are Computed
In the Backward Method, the algorithm starts at node 0 (source) and calculates the cost for each node moving forward to the destination (node 9). The cost is calculated in a similar way as in the Forward Method, but this time we compute the cost from the source to the destination.
- For node 0:
- The cost is 0 because it’s the source node.
- There is no parent because this is the starting node.
- For node 1:
- The possible connection is from node 0 to node 1 with a cost of 1 (
x[0][1] = 1). - The total cost is 1.
- The parent is node 0.
- The possible connection is from node 0 to node 1 with a cost of 1 (
- For node 2:
- The possible connection is from node 0 to node 2 with a cost of 2 (
x[0][2] = 2). - The total cost is 2.
- The parent is node 0.
- The possible connection is from node 0 to node 2 with a cost of 2 (
- This pattern continues for all the other nodes.
Step 3: Tracing the Optimal Path
After calculating the cost and parent nodes, the algorithm then traces the optimal path from the source (node 0) to the destination (node 9).
Here’s how the path is traced:
- Start from node 9, and look at the parent of node 9, which is node 7 (from the table).
- Move to node 7, and the parent of node 7 is node 5.
- Move to node 5, and the parent of node 5 is node 3.
- Move to node 3, and the parent of node 3 is node 0.
- The source node 0 has no parent (it’s the start of the path).
Thus, the optimal path for the Backward Method is:
Optimal Path:
9-->7-->5-->3-->0