1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
#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;
}
| |
