Graph Cutpoints C++ complete empty functions dfs(), connected(), and get_cutpoin

Question

Graph Cutpoints C++ complete empty functions dfs(), connected(), and get_cutpoints()

---------------------------------------------------------------------------

Graph.h

---------------------------------------------------------------------------

#ifndef GRPH

#define GRPH

#include <iostream>

#include <vector>

using namespace std;

struct vnode {

int vertex;

vnode *next;

vnode(int u, vnode *n): vertex(u), next(n){};

};

typedef vnode * vnodeptr;

class graph {

public:

graph(); // interactive constructor using cin

bool connected(int excluded);

void dfs(vector<bool> &visited);

vector<int> get_cutpoints();

  

private:

int size;

vector<vnodeptr> adjList;

};

#endif

---------------------------------------------------------------------------

Graph.cpp

---------------------------------------------------------------------------

#include <stdio.h>

#include "graph.h"

#include <cassert>

#include <stack>

graph::graph()

{

int vertex;

cin >> size;

adjList.resize(size,NULL);

for(int i = 0; i < size; ++i) {

cin >> vertex;

while(vertex != -1) {

adjList[i] = new vnode(vertex,adjList[i]); // insert at begining

cin >> vertex;

}

}

}

//returns the first index i where b[i] == false

// if no such vertex exists, returns b.size()

int firstFalse(vector<bool> b)

{

int i = 0;

while(i < b.size() && b[i])

i += 1;

return i;

}

// returns true if all entries in b are true

bool all(vector<bool> b)

{

for(int i = 0; i < b.size(); ++i)

if(!b[i])

return false;

return true;

}

void graph::dfs(vector<bool> &visited)

{

int start = firstFalse(visited);

int nbr, current = start;

stack<int> S;

vnodeptr cursor;

visited[start] = true;

S.push(start);

// Supply the remaining code below

  

}

// if excluded is -1, return true if G is connected

// otherwise, return true if G-excluded is connected

bool graph::connected(int excluded = -1)

{

vector<bool> visited(size,false);

if(excluded != -1)

visited[excluded] = true;

  

// Supply the remaining code below

  

}

vector<int> graph::get_cutpoints()

{

vector<int> cutpts;

// Supply the remaining code below

  

  

}

---------------------------------------------------------------------------

cut_tester.cpp

---------------------------------------------------------------------------

#include <stdio.h>

#include "graph.h"

using namespace std;

int main()

{

graph G;

if(!G.connected(-1)) {

cout << "Graph is not connected; terminating" << endl;

return 1;

}

vector<int> cutpoints = G.get_cutpoints();

cout << "Number of cutpoints: " << cutpoints.size() << endl;

cout << "Cutpoints: ";

for(int i = 0; i < cutpoints.size(); ++i)

cout << cutpoints[i] << " ";

cout << endl;

return 0;

}

Explanation / Answer

Given below is completed solution for given problem. Following methods have been added or updated:
- dfs: Performs depth first traversal of given graph
- connected: Determines if given graph is connected or not
- get_cutpoints: Determines cut points in given graph which if excluded result in an unconnected graph
- getVnodeInAdjList: Helper method which returns vertex node (i.e. last node) in given adjacency list

Comments are added in updated code for readability. Sample execution output is also provided for reference.

File: graph.h

#ifndef GRPH
#define GRPH

#include <iostream>
#include <vector>

using namespace std;

struct vnode {
int vertex;
vnode *next;
vnode(int u, vnode *n): vertex(u), next(n){};
};

typedef vnode * vnodeptr;

class graph {
public:
graph(); // interactive constructor using cin
bool connected(int excluded);
void dfs(vector<bool> &visited);
vector<int> get_cutpoints();

private:
int size;
vector<vnodeptr> adjList;
};

File: graph.cpp

#include <stdio.h>

#include "graph.h"
#include <cassert>
#include <stack>

graph::graph()
{
int vertex;
cin >> size;
adjList.resize(size,NULL);

for(int i = 0; i < size; ++i) {
cin >> vertex;
while(vertex != -1) {
adjList[i] = new vnode(vertex,adjList[i]); // insert at beginning
cin >> vertex;
}
}
}

//returns the first index i where b[i] == false
// if no such vertex exists, returns b.size()
int firstFalse(vector<bool> b)
{
int i = 0;

while(i < b.size() && b[i])
i += 1;

return i;
}

// returns true if all entries in b are true
bool all(vector<bool> b)
{
for(int i = 0; i < b.size(); ++i)
if(!b[i])
return false;
return true;
}

vnode *getVnodeInAdjList(vnode* node)
{
while ((node != NULL) && (node->next != NULL))
{
node = node->next;
}
return node; // vertex node is the last one in given adjaceny list
}

void graph::dfs(vector<bool> &visited)
{
int start = firstFalse(visited);
int nbr, current = start;
stack<int> S;
vnodeptr cursor;
visited[start] = true;
S.push(start);

// Supply the remaining code below
while (!S.empty())
{
current = S.top();
S.pop();

// Find vertices adjacent to current vertex that are not yet visited;
// Add such vertices to stack and mark them as visited

cursor = adjList[current];
while ((cursor != NULL) && (cursor->next != NULL))
{
for (int index = 0; index < size; index++)
{
vnode *node = getVnodeInAdjList(adjList[index]);

if ((node != NULL) && (node->vertex == cursor->vertex) && (visited[index] == false)) {

// Found matching adjacency list index for given vertex tht is not yet visited
S.push(index);
visited[index] = true;
break;

}
}
cursor = cursor->next;
}
}
}

// if excluded is -1, return true if G is connected
// otherwise, return true if G-excluded is connected
bool graph::connected(int excluded = -1)
{
vector<bool> visited(size,false);
if(excluded != -1)
visited[excluded] = true;

// Supply the remaining code below
dfs(visited); // traverse graph
return all(visited); // return true if all vertices are visited; Otherwise, return false
}

vector<int> graph::get_cutpoints()
{
vector<int> cutpts;

// Supply the remaining code below
for (int i = 0; i < size; i++)
{
if (connected(i) == false) // exclude i-th vertex
{
// i-th vertex is a cutpoint if graph is not connected on excluding it
cutpts.push_back(getVnodeInAdjList(adjList[i])->vertex);
}
}
return cutpts;
}

#endif

File: cut_tester.cpp

#include <stdio.h>
#include "graph.h"

using namespace std;

int main()
{
graph G;
if(!G.connected(-1)) {
cout << "Graph is not connected; terminating" << endl;
return 1;
}

vector<int> cutpoints = G.get_cutpoints();
cout << "Number of cutpoints: " << cutpoints.size() << endl;
cout << "Cutpoints: ";
for(int i = 0; i < cutpoints.size(); ++i)
cout << cutpoints[i] << " ";
cout << endl;

return 0;
}

Compilation:
g++ cut_tester.cpp graph.cpp

Sample Execution:
5
1 4 3 2 -1
2 3 1 -1
3 2 1 -1
4 5 1 -1
5 4 -1
Number of cutpoints: 2
Cutpoints: 1 4

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.