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]);
}
}
}
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
Specifically what is the problem?
@DanielA.White It does not correctly search for AP and does not correctly mark low and disc
but it does not work properly, please help — What is a debugger?. Every programmer has written a program that doesn’t work properly. The next step the programmer does is debug their program to see where a variable or different variables are not what they expect, the flow of the program goes in the wrong direction than expected, etc. This is a job you should be doing. How to fix the problem is a different story, but where the problem is — you should at least discover this.
@ravenspoint Because with a fairly large number of vertices, the stack overflows