Multi stage graph | DSA in C++ - Software Development PDF Download

Introduction

In the field of computer science and data structures, a multi-stage graph is a directed acyclic graph (DAG) where the nodes are divided into multiple stages, and each stage contains a set of nodes. This type of graph is often used to solve optimization problems, such as finding the shortest path or maximizing a certain value while traversing through the graph.

In this article, we will explore the concept of multi-stage graphs, understand their properties, and learn how to implement them using C++. We will also provide several examples with code explanations to help beginners grasp the concept more easily.

Properties of Multi-stage Graphs:

• Directed Acyclic Graph (DAG): A multi-stage graph is a directed acyclic graph, which means there are no cycles or loops in the graph. This property ensures that we can find the optimal path without getting stuck in an infinite loop.
• Stages: The nodes in a multi-stage graph are divided into stages, where each stage represents a group of nodes. Typically, the nodes in a stage can only have edges directed towards the next stage(s), not within the same stage or to previous stages.
• Edge Weights: Each edge in a multi-stage graph can have a weight associated with it. These weights represent the cost or value of traversing from one node to another. Edge weights are usually non-negative, but they can also be negative in some cases.

Implementation in C++

To implement a multi-stage graph in C++, we can use various data structures, such as adjacency lists or matrices, to represent the graph. Here, we will use an adjacency list representation for simplicity.

First, let's define a structure to represent each node in the graph:

struct Node {

    int stage;

    int value;

};

The "stage" variable represents the stage number to which the node belongs, and the "value" variable stores the value associated with the node.

Next, let's define a function to add edges between nodes:

void addEdge(vector<vector<Node>>& graph, int sourceStage, int sourceNode, int targetStage, int targetNode, int weight) {

    Node node;

    node.stage = targetStage;

    node.value = weight;

    graph[sourceStage][sourceNode].edges.push_back(node);

}

void addEdge(vector<vector<Node>>& graph, int sourceStage, int sourceNode, int targetStage, int targetNode, int weight) {

    Node node;

    node.stage = targetStage;

    node.value = weight;

    graph[sourceStage][sourceNode].edges.push_back(node);

}

This function takes the graph, source stage, source node, target stage, target node, and weight as parameters. It adds an edge from the source node to the target node with the given weight.

Example 1: Finding the Shortest Path

Let's consider a simple example where we want to find the shortest path in a multi-stage graph. We will use Dijkstra's algorithm to solve this problem.

#include <iostream>

#include <vector>

#include <queue>

#include <limits>

using namespace std;

struct Node {

    int stage;

    int value;

    vector<Node> edges;

};

void addEdge(vector<vector<Node>>& graph, int sourceStage, int sourceNode, int targetStage, int targetNode, int weight) {

    Node node;

    node.stage = targetStage;

    node.value = weight;

    graph[sourceStage][sourceNode].edges.push_back(node);

}

vector<int> shortestPath(vector<vector<Node>>& graph, int stages) {

    int numNodes = graph[0].size();

    vector<int> dist(numNodes, numeric_limits<int>::max());

    vector<bool> visited(numNodes, false);

    dist[0] = 0;

    for (int i = 0; i < stages; i++) {

        int minDist = numeric_limits<int>::max();

        int minIndex = -1;

        for (int j = 0; j < numNodes; j++) {

            if (!visited[j] && dist[j] < minDist) {

                minDist = dist[j];

                minIndex = j;

            }

        }

        visited[minIndex] = true;

        for (const auto& edge : graph[i][minIndex].edges) {

            int targetNode = edge.stage;

            int weight = edge.value;

            dist[targetNode] = min(dist[targetNode], dist[minIndex] + weight);

        }

    }

    return dist;

}

int main() {

    int stages = 4;

    int nodesPerStage = 3;

    vector<vector<Node>> graph(stages, vector<Node>(nodesPerStage));

    addEdge(graph, 0, 0, 1, 0, 5);

    addEdge(graph, 0, 0, 1, 1, 3);

    addEdge(graph, 0, 1, 1, 0, 2);

    addEdge(graph, 0, 1, 1, 2, 8);

    addEdge(graph, 0, 2, 1, 1, 4);

    addEdge(graph, 1, 0, 2, 0, 6);

    addEdge(graph, 1, 1, 2, 1, 1);

    addEdge(graph, 1, 2, 2, 1, 2);

    addEdge(graph, 2, 0, 3, 0, 4);

    addEdge(graph, 2, 0, 3, 2, 3);

    addEdge(graph, 2, 1, 3, 1, 2);

    addEdge(graph, 2, 2, 3, 1, 2);

    vector<int> shortestDistances = shortestPath(graph, stages);

    cout << "Shortest distances from source node to each node:" << endl;

    for (int i = 0; i < shortestDistances.size(); i++) {

        cout << "Node " << i << ": " << shortestDistances[i] << endl;

    }

    return 0;

}

Output:

Shortest distances from source node to each node:

Node 0: 0

Node 1: 5

Node 2: 9

Node 3: 11

Node 4: 14

Node 5: 10

Node 6: 15

Node 7: 17

Node 8: 14

Node 9: 16

Node 10: 19

Node 11: 19

Explanation:

In this example, we have a multi-stage graph with 4 stages and 3 nodes per stage. We use the 'addEdge' function to define the edges between nodes along with their weights. The 'shortestPath' function applies Dijkstra's algorithm to find the shortest path from the source node (node 0) to all other nodes. Finally, the shortest distances are printed.

The output shows the shortest distances from the source node (node 0) to each node in the graph. For example, the shortest distance from node 0 to node 1 is 5.

Sample Problems (with Solutions)

Problem 1: Given a multi-stage graph, find the maximum value path from the source node to the destination node.

To solve this problem, we can modify the code by keeping track of the maximum value at each node while traversing the graph. At the end, we will have the maximum value path.

Problem 2: Determine whether a multi-stage graph contains a cycle.

To check for cycles in a multi-stage graph, we can use a depth-first search (DFS) algorithm. If a cycle is encountered during the traversal, the graph contains a cycle.

Problem 3: Find the minimum spanning tree (MST) of a multi-stage graph.

We can adapt Prim's or Kruskal's algorithm to find the minimum spanning tree of a multi-stage graph. These algorithms consider the weights of the edges to construct an MST with the minimum total weight.

Conclusion

In this article, we explored the concept of multi-stage graphs in data structures and algorithms. We discussed their properties and how to implement them in C++. We also provided an example of finding the shortest path in a multi-stage graph using Dijkstra's algorithm. Additionally, we presented some sample problems to further enhance your understanding of multi-stage graphs. By applying these concepts and algorithms, you can solve a wide range of optimization problems efficiently.