Your job is to determine whether or not a graph contains a cycle. A cycle in a directed graph is a set of nodes {x1, , xn} in which an edge exists from xi to xi+1 for all 1 <= i < n and an edge from xn to x1

You will edit the function bool hasCycles(const Graph& g), which returns true/false based on whether or not a graph g contains a cycle.

There are many ways to determine whether or not a directed graph contains a cycle. There are brute force ways and there are more elegant ways, but as long as your implementation works, you will get full points!

Example

Consider the following:

Graph g(3); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); 

This would create a graph with 3 nodes (0, 1, 2) with edges from 0 to 1, 0 to 2, and 1 to 2.

The output of hasCycles(g) should return false.

On the other hand:

Graph g(3); g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(2, 0); 

Would create a graph with 3 nodes in which hasCycles(g) returns true

//main.cpp

#include

#include

#include "cycle_detection.cpp"

int main() {

// Construct graph

Graph g(3);

g.addEdge(0, 1);

g.addEdge(1, 2);

g.addEdge(2, 0);

// Print the edges

printGraph(g);

bool cycles = hasCycles(g);

std::cout << "Has cycles: " << cycles << std::endl;

//graph.cpp

#include

#include

#include

struct Node {

Node(int v): value(v) {};

int value;

std::vector outgoingNeighbors;

bool operator==(Node const & other) const {

return value == other.value && outgoingNeighbors == other.outgoingNeighbors;

}

};

struct Graph {

std::vector nodes;

Graph(int n) {

for (size_t i = 0; i < n; i++) {

Node* newNode = new Node(i);

nodes.push_back(newNode);

}

};

~Graph() {

for (size_t i = 0; i < nodes.size(); i++) {

free(nodes[i]);

}

}

void addEdge(int src, int dst) {

if (containsEdge(src, dst)) {

return;

}

Node* srcNode = nodes[src];

Node* dstNode = nodes[dst];

srcNode->outgoingNeighbors.push_back(dstNode);

}

bool containsEdge(int src, int dst) {

Node* srcNode = nodes[src];

Node* dstNode = nodes[dst];

for (auto neighborIter = srcNode->outgoingNeighbors.begin(); neighborIter != srcNode->outgoingNeighbors.end(); neighborIter++) {

Node* neighbor = *neighborIter;

if (*neighbor == *dstNode) {

return true;

}

}

return false;

}

};

void printGraph(Graph const & g) {

for (auto nodeIter = g.nodes.begin(); nodeIter != g.nodes.end(); nodeIter++) {

Node * node = *nodeIter;

std::cout << "Node: " << node->value;

std::cout << " neighbors: ";

for (auto neighborIter = node->outgoingNeighbors.begin(); neighborIter != node->outgoingNeighbors.end(); neighborIter++) {

Node * neighbor = *neighborIter;

std::cout << neighbor->value << " ";

}

std::cout << ' ';

}

}

bool contains(std::vector v, Node* n){

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

if(*v[i] == *n){

return true;

}

}

return false;

}

//cycle_detection.cpp

#include

#include

#include

#include "graph.cpp"

// TODO: Implement this function

bool hasCycles(Graph const & g) {

int V = g.nodes.size();

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

Node* node = g.nodes[i];

// Do something

}

return false;

}