SimpleGraph

SimpleGraph.cpp

/*
 * A DFS/BFS implementation for simple unweighted connected graphs.
 * Max DeLiso <[email protected]>
 * 10/31/15
 */

#include <iostream>
#include <cassert>

#include <stack>
#include <queue>
#include <algorithm>
#include <vector>

#include <chrono>
#include <random>
#include <functional>

 /* Create a type alias. */
typedef size_t graph_t;

/*
 * A simple connected graph.
 */
class SimpleGraph {
	/* number of nodes in the graph. nodes are numbered 0 to n - 1. */
	const graph_t N;

	/*
	 * An unweighted 2D adjacency matrix.
	 * The nth row describes the edges between the nth node and the rest of the node in the graph.
	 */
	std::vector<std::vector<bool>> adj;

public:

	SimpleGraph(graph_t n);

	void reset();
	graph_t size();
	void addEdge(const graph_t src, const graph_t dst);
	std::vector<graph_t> BFS(const graph_t src_node);
	std::vector<graph_t> DFS(const graph_t src_node);
	friend std::ostream& operator<< (std::ostream& out, const SimpleGraph& G);
};

SimpleGraph::SimpleGraph(graph_t n) : N(n) {
	reset();
}

/* Reset the graph to empty. */
void SimpleGraph::reset() {
	adj.resize(N);

	std::for_each(adj.begin(), adj.end(), [=](std::vector<bool>& row) {
		row.resize(N, false);
	});
}

graph_t SimpleGraph::size() {
	return N;
}

/* Add an adjacency between source and dst nodes. */
void SimpleGraph::addEdge(const graph_t src_node, const graph_t dst_node) {
	assert(src_node < N);
	assert(dst_node < N);

	adj[src_node][dst_node] = true;
	adj[dst_node][src_node] = true;
}

/* Allow the Graph to be printed using the output stream operator. */
std::ostream & operator<< (std::ostream& out, const SimpleGraph& G) {
	std::for_each(G.adj.begin(), G.adj.end(), [&out](const std::vector<bool>& row) {
		std::for_each(row.begin(), row.end(), [&out](const bool & rowVal) {
			out << rowVal << " ";
		});

		out << std::endl;
	});
	return out;
}

/* Returns a BFS ordering of nodes, starting from src_node. */
std::vector<graph_t> SimpleGraph::BFS(const graph_t src_node) {
	assert(src_node < N);

	std::queue<graph_t> Q; /* to keep track of node ordering */
	std::vector<bool> nodeSeen(N); /* to keep track of nodes visited */
	std::vector<graph_t> bfsOrdering; /* to store the ordering */

	Q.push(src_node);

	while (!Q.empty()) {
		graph_t u = Q.front();
		Q.pop();

		if (!nodeSeen[u]) {
			nodeSeen[u] = true;

			bfsOrdering.push_back(u);

			/* visit each neighbor */
			for (graph_t n = 0; n < N; ++n) {
				if (adj[u][n]) {
					Q.push(n);
				}
			}
		}
	}

	std::reverse(bfsOrdering.begin(), bfsOrdering.end());
	return bfsOrdering;
}


/* Returns a DFS ordering of nodes, starting from src_node. */
std::vector<graph_t> SimpleGraph::DFS(const graph_t src_node) {
	assert(src_node < N);

	std::stack<graph_t> S; /* to keep track of node ordering */
	std::vector<bool> nodeSeen(N); /* to keep track of nodes visited */
	std::vector<graph_t> dfsOrdering; /* to store the ordering */

	S.push(src_node);

	while (!S.empty()) {
		/* retrieve current node from stack */
		graph_t currentNode = S.top();
		S.pop();

		/* if it hasn't been seen already, push all its neighbors onto the stack */
		if (!nodeSeen[currentNode]) {
			/* and mark it visited*/
			nodeSeen[currentNode] = true;

			/* store the node */
			dfsOrdering.push_back(currentNode);

			/* visit each neighbor */
			for (graph_t n = 0; n < N; ++n) {
				if (adj[currentNode][n]) {
					S.push(n);
				}
			}
		}
	}

	std::reverse(dfsOrdering.begin(), dfsOrdering.end());
	return dfsOrdering;
}

int main() {
	SimpleGraph G(16);

	unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
	std::default_random_engine generator(seed);
	std::uniform_int_distribution<graph_t> distribution(0, G.size() - 1);
	auto randNode = std::bind(distribution, generator);

	for (graph_t i = 0; i < G.size() * 2; ++i) {
		G.addEdge(randNode(), randNode());
	}

	std::cout << G << std::endl;
	std::vector<graph_t> dfsOrdering = G.DFS(0);
	std::vector<graph_t> bfsOrdering = G.BFS(0);

	std::for_each(dfsOrdering.begin(), dfsOrdering.end(), [](const graph_t& n) {
		std::cout << n << " ";
	});

	std::cout << std::endl;

	std::for_each(bfsOrdering.begin(), bfsOrdering.end(), [](const graph_t& n) {
		std::cout << n << " ";
	});

	std::cout << std::endl;
	return 0;
}