Cut vertex iterative algorithm

Question

I need to convert Trajan's recursive algorithm to Trajan's iterative algorithm.I have a class Graph it contains several methods and fields here is the basic structure that will be needed

class Graph {
protected:
 vector< vector<int> > adjList;
 int n;

This is what the recursive code looks like

void DFSforTarjan(int u, vector<bool>& visited,
    set<int>& AP, vector<int>& disc, vector<int>& low, int& time, int parent) {

    int children = 0;
    visited[u] = true;
    disc[u] = low[u] = ++time;
    for (int v : this->getNeighborVertex(u)) {
        if (!visited[v]) {
            children++;
            DFSforTarjan(v, visited, AP, disc, low, time, u);
            low[u] = min(low[u], low[v]);
            if (parent != -1 && low[v] >= disc[u])
                AP.insert(u);
        }
        else if (v != parent)
            low[u] = min(low[u], disc[v]);
    }
    if (parent == -1 && children > 1)
        AP.insert(u);
}

And this is the code that I tried to implement iteratively, but it does not work properly, please help

void DFSforTarjan(int u, vector<bool>& visited,
    set<int>& AP, vector<int>& disc, vector<int>& low, vector<int>& parent, vector<int>& children, int& time) {

    stack<int> st;
    st.push(u);
    
    while (!st.empty()) {
        u = st.top();
        st.pop();

        if (parent[u] != -1) {
            children[parent[u]]++;
        }
        visited[u] = true;
        disc[u] = low[u] = ++time;

        for (int v : this->getNeighborVertex(u)) {
            if (!visited[v]) {
                st.push(v);
                parent[v] = u;
                visited[v] = true;
            }
            else if (v != parent[u]) {
                low[u] = min(low[u], disc[v]);
            }
        }

        if (parent[u] == -1 && children[u] > 1)
            AP.insert(u);

        if (parent[u] != -1 && low[u] >= disc[parent[u]])
            AP.insert(parent[u]);
    }
    for (int v : this->getNeighborVertex(u)) {
        if (v != parent[u] && visited[v]) {
            low[u] = min(low[u], low[v]);
        }
    }
}

Answer 1

When designing a recursive function it is important to minimize the use of stack memory. So, reduce the number of parameters used on each call by making the recursive function the method of a class. Then, instead of passing the references to the graph details, visited vertices, etc. you can access them directly as attributes of the class.

( The same effect can also be achieved by making those parameters global, but this is frowned upon because your code becomes vulnerable to global name collisions, which can be tricky to debug hence the expression for this: polluting the global namespace )

Here is the definition of a class which implements Tarjan with just three parameters.

       /// @brief Find articulation points in an undirected graph
        /// An articulation point is a vertex whose removal
        /// increases the number of connected components in the graph.

        class cTarjan
        {
        public:
            /// @brief Find articulation points with Tarjan's algorithm
            /// @param gd undirected graph description ( directed will raise exception )
            /// @return vector of articulation point names

            std::vector<std::string> ArticulationPoints(sGraphData &gd);

        private:
            std::vector<bool> visited; // true if vertex index has been visited
            std::vector<int> disc;     // discovery times of visited vertices
            std::vector<int> low;      // earliest visited vertex (the vertex with minimum
                                       // discovery time) that can be reached from subtree
                                       // rooted with vertex
            std::set<int> sAP;         // set of articulation point vertex indices

            /// @brief Recursive search graph for articulation points
            /// @param gd graph description
            /// @param time current time
            /// @param parent vertex index to start search from

            void APRecurse(
                sGraphData &gd,
                int &time, int parent);
        };

and here is the implementation

        std::vector<std::string> cTarjan::ArticulationPoints(sGraphData &gd)
        {
            if (gd.g.isDirected())
                throw std::runtime_error(
                    "Tarjan works only for undirected graphs");

            visited.clear();
            visited.resize(gd.g.vertexCount(), false);
            disc.clear();
            disc.resize(gd.g.vertexCount(), 0);
            low.clear();
            low.resize(gd.g.vertexCount(), 0);
            sAP.clear();

            std::vector<std::string> vAP;
            int time = 0, parent = -1;

            // Adding this loop so that the
            // code works even if we are given
            // disconnected graph
            for (int u = 0; u < gd.g.vertexCount(); u++)
                if (!visited[u])
                {
                    gd.startName = gd.g.userName(u);
                    APRecurse(
                        gd,
                        time, parent);
                }

            for (int p : sAP)
                vAP.push_back(gd.g.userName(p));

            return vAP;
        }

        // find articulation points in an undirected graph

        // A recursive function that find articulation
        // points using DFS traversal
        // adj[] --> Adjacency List representation of the graph
        // u --> The vertex to be visited next
        // visited[] --> keeps track of visited vertices
        // disc[] --> Stores discovery times of visited vertices
        // low[] -- >> earliest visited vertex (the vertex with minimum
        // discovery time) that can be reached from subtree
        // rooted with current vertex
        // parent --> Stores the parent vertex in DFS tree
        // sAP[] --> Stores articulation points
        void cTarjan::APRecurse(
            sGraphData &gd,
            int &time, int parent)
        {
            int u = gd.g.find(gd.startName);

            // Count of children in DFS Tree
            int children = 0;

            // Mark the current node as visited
            visited[u] = true;

            // Initialize discovery time and low value
            disc[u] = low[u] = ++time;

            // Go through all vertices adjacent to this
            for (auto v : gd.g.adjacentOut(u))
            {
                // If v is not visited yet, then make it a child of u
                // in DFS tree and recur for it
                if (!visited[v])
                {
                    children++;
                    sGraphData gd2;
                    gd2 = gd;
                    gd2.startName = gd.g.userName(v);
                    APRecurse(
                        gd2, time, u);

                    // Check if the subtree rooted with v has
                    // a connection to one of the ancestors of u
                    low[u] = std::min(low[u], low[v]);

                    // If u is not root and low value of one of
                    // its child is more than discovery value of u.
                    if (parent != -1 && low[v] >= disc[u])
                        sAP.insert(u);
                }

                // Update low value of u for parent function calls.
                else if (v != parent)
                    low[u] = std::min(low[u], disc[v]);
            }

            // If u is root of DFS tree and has two or more children.
            if (parent == -1 && children > 1)
                sAP.insert(u);
        }

Complete code and docs at https://github.com/JamesBremner/PathFinder.

This code can handle, without exhausting the default stack size, a graph with 4,720 vertices 13,722 edges from https://dyngraphlab.github.io/ ( 3elt.graph.seq.txt ) in 27 seconds.

If stack memory is still being exhausted you can increase it's size by using the method described in this answer: https://stackoverflow.com/a/54838059/16582