Find Eventual Safe States In C++

Introduction

In the realm of computer science, particularly in the domain associated with graph theory, there are numerous scenarios where the identification of specific states or nodes as 'secure' becomes essential. A state is deemed secure when, starting from that point, the system is incapable of entering any cyclic patterns. These types of problems hold significance in real-world scenarios by improving system reliability, preventing deadlocks, and handling interdependencies effectively.

In this post, our aim is to tackle the challenge of identifying potentially secure states in a directed graph through the utilization of C++. We intend to provide a thorough overview of the problem statement, methodology, and a detailed breakdown of the code implementation.

Problem Statement

You are working with a directed graph that is represented using an adjacency list, allowing transitions between nodes. To classify a node as "eventually safe," all paths originating from that node must lead to a terminal node. A terminal node is one that has no outgoing edges, meaning it is not possible to transition to another node from there.

The objective is to pinpoint the nodes that are reliably secure over time. These are the nodes that require our concentrated focus. In this scenario, a significant number of them are consistently traversed in loops, resulting in the absence of any cycles being created (i.e. safe states).

In this graph:

• ✅ Node 0 is considered unsafe in this situation since it is possible to prolong and repeat this process.
• ✅ Nodel 1, 2, and 3 are also unsafe eventually.
• ✅ Node 4 is eventually safe because it only has an outgoing edge to node 2 (4 → 2), and node 4 does not participate in any cycle.

Approach

To address the problem, one possible solution is to invert a graph and apply topological sorting by utilizing a queue, following Kahn's algorithm for topological sorting. Initially, we focus on handling the straightforward scenarios of terminal nodes (edges without outgoing nodes) and gradually extend this method to cover a larger number of nodes, ensuring that the transitions ultimately reach safe nodes.

Steps:

• ✅ Reverse the Graph: Changes the direction of all the edges in the graph . This will help us in dealing with terminal nodes first.
• ✅ Topological Sorting: Takes a queue and deques terminal nodes to proceed in a backward way. Each node marked safe will, in turn, sustain successive nodes, all of whom will in no time be safe.
• ✅ Return Safe Nodes: In the end, after all the processing, the safe nodes are returned.

Program 1:

#include <iostream>
#include <vector>
#include <queue>
#include<bits/stdc++.h>
using namespace std;

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> reverseGraph(n);   // Reverse graph
    vector<int> outDegree(n, 0);           // Track out-degree of each node
    queue<int> safeQueue;                  // Queue for processing safe nodes
    vector<int> safeNodes;                 // Store eventual safe nodes

    // Reverse the graph and calculate out-degrees
    for (int u = 0; u < n; ++u) {
        for (int v : graph[u]) {
            reverseGraph[v].push_back(u);  // Reverse the edge direction
        }
        outDegree[u] = graph[u].size();    // Original out-degree of node u
    }

    // Nodes with out-degree 0 are terminal nodes and thus safe
    for (int i = 0; i < n; ++i) {
        if (outDegree[i] == 0) {
            safeQueue.push(i);  // Add terminal nodes to the queue
        }
    }

    // Process nodes in the queue
    while (!safeQueue.empty()) {
        int safeNode = safeQueue.front();
        safeQueue.pop();
        safeNodes.push_back(safeNode);

        // For each node thacpp tutorials to the current safe node in reverseGraph
        for (int u : reverseGraph[safeNode]) {
            outDegree[u]--;   // Reduce the out-degree
            if (outDegree[u] == 0) {
                safeQueue.push(u);  // If out-degree becomes zero, it's safe
            }
        }
    }

    // Sort the eventual safe nodes for output
    sort(safeNodes.begin(), safeNodes.end());

    return safeNodes;
}

int main() {
    vector<vector<int>> graph = {{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}};
    
    vector<int> safeNodes = eventualSafeNodes(graph);

    cout << "Safe nodes are: ";
    for (int node : safeNodes) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

Output:

Safe nodes are: 2 4 5 6

Explanation of the Code:

• ✅ Reversing the Graph: To determine nodes that eventually course back to terminal nodes, then terminal nodes and their dependencies slack would be discovered first and those led back. In the reverseGraph, original edges u → v are transformed into v → u.
• ✅ Out-degree Calculation: For every node, the edges directed away from that node are counted (out-degree). A few of the added final nodes are those with an out-degree of zero and are placed into the safeQueue.
• ✅ Managing the Safe nodes: For each node in the safeQueue , we decrement the out-degree of the nodes that are directed to it in the reverse direction of the graph. If any node's out-degree reaches to zero, it denotes that all its continue nodes are ultimately safe, and it is pushed in to the safeQueue.
• ✅ Output: Finally, the safe nodes are written and also Printed.
• ✅ For each node in the safeQueue , we decrement the out-degree of the nodes that are directed to it in the reverse direction of the graph.
• ✅ If any node's out-degree reaches to zero, it denotes that all its continue nodes are ultimately safe, and it is pushed in to the safeQueue.

Time Complexity:

• ✅ Inverting a Graph: The time complexity is O(E) where E represents the total number of edges in the graph.
• ✅ Performing Topological Sorting: The time complexity is O(V + E), where V denotes the number of vertices (or nodes) and E signifies the number of edges in the graph.

Therefore, the overall time complexity amounts to O(V + E), which proves to be acceptable for the majority of real-world graphs.

Space Complexity:

• ✅ Graph storage: /in and /out graph for both graphs are considered to be simplified O (V+E) and O (E + V) respectively
• ✅ Out-degree Array: O (V)
• ✅ Queue and stage of results: O (V)

Thus, the total space complexity is O(V + E). This level of space and time complexity is deemed adequate and aligns with the goals of implementing graph planarization in real-world scenarios, which is where the majority of graph algorithm implementations are focused.

Program 2:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Graph {
public:
    Graph(int n) : adjList(n), reverseGraph(n), outDegree(n, 0) {}

    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        reverseGraph[v].push_back(u);
        outDegree[u]++;
    }

    vector<int> eventualSafeNodes() {
        int n = adjList.size();
        queue<int> safeQueue;
        vector<int> safeNodes;

        // Identify terminal nodes (out-degree 0)
        for (int i = 0; i < n; ++i) {
            if (outDegree[i] == 0) {
                safeQueue.push(i);
            }
        }

        // Process nodes in the queue
        while (!safeQueue.empty()) {
            int safeNode = safeQueue.front();
            safeQueue.pop();
            safeNodes.push_back(safeNode);

            // Process the reverse edges
            for (int u : reverseGraph[safeNode]) {
                outDegree[u]--;   // Decrement out-degree
                if (outDegree[u] == 0) {
                    safeQueue.push(u);  // If out-degree becomes zero, it's safe
                }
            }
        }

        // Sort the eventual safe nodes for output
        sort(safeNodes.begin(), safeNodes.end());
        return safeNodes;
    }

private:
    vector<vector<int>> adjList;      // Adjacency list for the original graph
    vector<vector<int>> reverseGraph; // Adjacency list for the reversed graph
    vector<int> outDegree;             // Out-degree of each node
};

int main() {
    // Create a directed graph with 8 nodes
    Graph g(8);
    
    // Add edges to the graph (example)
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 0);
    g.addEdge(3, 5);
    g.addEdge(4, 5);
    g.addEdge(5, 6);
    g.addEdge(6, 7);

    vector<int> safeNodes = g.eventualSafeNodes();

    cout << "Safe nodes are: ";
    for (int node : safeNodes) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

Output:

Safe nodes are: 2 4, 5 6, 7

Explanation:

• ✅ Graph's Class: A Graph class that helps in encapsulating the features of our graph is elucidated here. It contains:
• ✅ Adjust: Adjacency list of the graph containing a vector of vectors of the original graph.
• ✅ reverseGraph: Reverse vector of vectors for the graph.
• ✅ outDegree: A vector meant for storage of the out-degree of a node.
• ✅ Adding Edges: The addEdge function is designed to draw an arrow from node u to node v. This action corresponds to both the adjacency list and the reverse graph and will, in addition, update the out-degree of node u.

Finding Eventual Safe Nodes:

• ✅ There is a provision for a queue that will hold all nodes with no edges emanating from them (out-degree 0).
• ✅ In the previous section, we also highlighted how terminal nodes can be determined and appended to the queue as well.
• ✅ As each node present in the queue is dealt with, other nodes that have arrows feeding into them in the reversed graph and possess arrows towards the present node have their out-degrees decremented. If the out-degree of any such nodes becomes zero, the node will also be added to the ready-for-processing queue.
• ✅ Sorting and Outputs: Last but not least, safe nodes are returned once their sorting out has been done to prepare for the return in an ordered manner.

Time Complexity:

The overall time complexity is denoted as O(V+E), with V representing the vertices (nodes) and E representing the edges. Creating the inverse graph incurs a time cost of O(E). The queue processing operation also requires O(E+V) because each vertex and edge are visited once during this process.

Space Complexity: The space complexity is O(V+E)

Advantages:

• ✅ Deadlock Prevention: In Operating Systems, the allocation of resources can also be carried out in such a manner that it eliminates the condition of deadlock. The states that are so termed can be a helpful aid in the designing of the strategies for allocating resources.
• ✅ Dependency Management: Task management in projects or software development usually involves tasks that depend on one another. The safe states can guide the way in which tasks will be scheduled to ensure all the dependencies have been cleared.
• ✅ Circuit Design: In electronic circuits, outputs need to be produced when corresponding inputs are given without any unwanted oscillation or feedback fostering extension and end. Safe states may be utilized in circuit analysis and designing stable circuits.
• ✅ Game Theory: Understanding safe states in games is important as it is through them that players can know which moves to guarantee them to win or avoid losing, especially in games whose moves are made in succession.
• ✅ Data Flow Analysis: Compilers use data flow analysis in which the data flows through different components to determine the other states where data races or inconsistencies do not happen so that no miscommunication of programs will occur.
• ✅ Network routing: In communication Networks, the way in which data packets are routed towards other processes needs to avoid the formation of cycles, which can enhance the reliability and efficiency of the system in passing on data.

Conclusion:

In summary, the main focus of this C++ guide was on establishing the concept of eventual safety in a directed graph. The strategy involved reversing the graph and computing its topological order, which proved to be an effective algorithmic solution. Understanding this concept is crucial in scenarios where preventing deadlocks, managing dependencies, or ensuring system reliability are essential.