Member Avatar for simonsayz27
simonsayz27

Hey everyone. I'm getting REALLY frustrated with this program and I've been working on this problem for too long now. I am building an undirected and unweighted bi-connected graph class which detects all the articulation points. I am able to detect all the articulation points but I cannot figure out why it is always printing out vertex #0 to be an articulation point. I don't know how to check if the root is an art point. If it has more than one child then it is considered an art. point. Can someone help me fix this issue please? Here is my long code. I have 2 classes, one for Vertex and the other for Graph. Thanks a lot!

Here is the sample input:
8 // Number of vertices
3 1 5 4 // 3 == number of computers connected.
2 5 0 // 1 5 4 == computers linked to vertex #0
2 3 6
3 2 6 7
2 0 5
4 0 1 4 6
4 5 2 3 7
2 6 3

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

/* 
 * Holds info about a vertex (or node, or computer, etc), and 
 * also has some functions which do basic operations on the node
 */
class Vertex
{

public:
	Vertex()
	{
		exists = false;
		visited = false;
		articulationPoint = false;
	}
	void setVertexId(int vId)
	{
		vertexId = vId;
	}
	void attachNewNode(Vertex *newNode)
	{
		attachedNodes.push_back(newNode);
	}
	bool visited;
	bool exists;
	bool articulationPoint;
	int vertexId;
	int num;
	int lowValue;
	int parent;
	vector<Vertex*> attachedNodes;
private:
};

/*
 * The Graph is a set of Vertex objects which are linked to one another,
 * and it is responsible for Graph-type operations, such as building,
 * iterating, calculating, etc on the vertexes
 */
class Graph
{

public:
	Graph(){
		root = NULL;
		size = 0;
		counter = 1;
	}
	Graph(Vertex* rootNode)
	{
		root = rootNode;
		size = 0;
		counter = 1;
	}
	void link(int, int);
	void findArt(Vertex *v);
	void processArt();
	void printArt();
	Vertex createdNodes[20];
	vector<int> artPoints;
private:
	Vertex* root;
	int size;
	int counter;
};

void Graph::link(int sourceId, int targetId)
{ 
	//1) If my sourceId node has NOT been created, instantiate one, set the sourceId into it,
	// and stick it into the array of createdNodes
	if(!createdNodes[sourceId].exists)
	{
		Vertex sourceComputer;
		sourceComputer.setVertexId(sourceId);
		sourceComputer.exists = true;
		createdNodes[sourceId] = sourceComputer;
		size++;

	} 
		//2) Do the exact same thing for targetId LOLlol goto your find art real quick
	if(!createdNodes[targetId].exists)
	{
		Vertex targetComputer;
		targetComputer.setVertexId(targetId);
		targetComputer.exists = true;
		createdNodes[targetId] = targetComputer;
		size++;
	}
	
	//targetNodePtr is pointing to target node inside of createdNodes list
	Vertex* targetNodePtr = &createdNodes[targetId];
	createdNodes[sourceId].attachNewNode(targetNodePtr);

	if(root == NULL)
	{
		root = &createdNodes[0];	
	}
};

void Graph::findArt(Vertex *v)
{
	Vertex *w;
	v->visited = true;
	v->lowValue = v->num = counter; 
	counter++;

	for(int i = 0; i < v->attachedNodes.size(); i++)
	{
		w = v->attachedNodes[i];
		if(!w->visited)
		{ 
			w->parent = v->vertexId;
			findArt(w);
			if(w->lowValue >= v->num)
			{
				cout << "setting " << v->vertexId << " to true articulation" << endl;
				v->articulationPoint = true;
			}
			v->lowValue = min(v->lowValue, w->lowValue);
		}else if(v->parent != w->vertexId)
		{
			v->lowValue = min(v->lowValue, w->num);
		}
	}

}

void Graph::processArt()
{
	findArt(root);
}

void Graph::printArt()
{
	cout << "printing articulation points..." << endl;
	cout << "size = " << size << endl;
	for(int x = 0; x < size; x++)
    {
		cout << "checking vertex #" << createdNodes[x].vertexId << ": ";
		if(createdNodes[x].articulationPoint)
			cout << " YES" << endl;
		else
			cout << " NO" << endl;
    }
}

/*
 * Entry-point into the application which sets up the Graph and calls the basic
 * functions to run the program.
 */
int main() {
	
	Vertex rootComputer;  //Create my root vertex
	Graph network;		  //Create my graph

	int computersInNetwork;
	//cout << "Enter number of computers in network" << endl;
	cin >> computersInNetwork;

	for(int sourceComputerID = 0; sourceComputerID < computersInNetwork; sourceComputerID++)
	{
		int attachedComputerCount;
		//cout << "Enter number of computers attached to computer #" << sourceComputerID << endl;
		cin >> attachedComputerCount;
		for(int j = 0; j < attachedComputerCount; j++)
		{
			int attachingComputerID;
			//cout << "Enter computer ID for attached computer # " << j << endl;
			cin >> attachingComputerID;
			//Now that we have sourceComputerID and attachingComputerID, we can just go ahead
			// and attach them by using functions in Graph
			network.link(sourceComputerID, attachingComputerID);
		}
	}
	network.processArt();
	network.printArt();
	return 0;
}