graph_representations.cpp

#include <cassert>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <iostream>
#include <vector>

using Incidence = std::bitset<2>;

template <typename T>
class Matrix {
	std::vector<T> array; // std::vector<bool> is compact
public:
	size_t rows;
	const size_t columns;
	Matrix(size_t columns_, size_t rows_=0): array(columns_ * rows_), rows(rows_), columns(columns_) {}
	decltype(auto) operator() (size_t row, size_t column) { return array[row * columns + column]; }
	auto operator() (size_t row, size_t column) const { return array[row * columns + column]; }
	auto begin() const { return array.begin(); }
	auto end() const { return array.end(); }

	/* For dynamically adding edges to transposed incidence matrix.
	I don't ask the number of edges in advance.
	Trying to convert an adjacency matrix representing undirected graph
	to incidence matrix results in duplicate edges. */
	void append(const std::vector<T>& rows) {
		assert(rows.size() % columns == 0);
		// array.append_range(rows);
		array.insert(array.end(), rows.begin(), rows.end());
		this->rows += rows.size() / columns;
	}
};

template <typename T>
std::ostream& operator<<(std::ostream& out, const Matrix<T>& matrix) {
	auto width = out.width();
	for (size_t i = 0; i < matrix.rows; i++) {
		for (size_t j = 0; j < matrix.columns; j++) {
			out << std::setw(width) << matrix(i, j) << ' ';
		}
		out << '\n';
	}
	return out;
}

int main() {
	std::string line;
	unsigned vertices;
	std::cout << "Number of vertices? ";
	std::cin.exceptions(std::ios_base::badbit | std::ios_base::failbit | std::ios_base::eofbit);
	std::cin >> vertices;

	std::cout << "Directed [y/n]? ";
	std::getline(std::cin, line); // nothing else works...
	bool directed = tolower(std::cin.get()) != 'n';
	std::getline(std::cin, line); // nothing else works...
	const Incidence IN  = directed ? 0x2 : 0x3;
	const Incidence OUT = directed ? 0x1 : 0x3;

	Matrix<unsigned> adjacency(vertices, vertices);
	Matrix<Incidence> incidence(vertices);

	std::vector<Incidence> edge;
	for (unsigned vertex = 0, neighbour; vertex < vertices; vertex++) {
		std::cout << "Neighbours of vertex " << vertex << " (space-separated)? ";
		std::getline(std::cin, line);
		std::istringstream iss(line);
		while (iss >> neighbour) {
			edge.assign(vertices, 0);
			edge[vertex] |= OUT;
			edge[neighbour] |= IN;
			incidence.append(edge);
			adjacency(vertex, neighbour)++;
			adjacency(neighbour, vertex) += !directed && vertex != neighbour;
		}
	}

	std::cout
		<< "\nAdjacency matrix:\n" << std::setw(2) << adjacency
		<< "\nTransposed incidence matrix:\n" << incidence;

	std::cin.exceptions(std::ios_base::goodbit);
	do {
		unsigned vertex;
		std::cout << "\nQuery a vertex? ";
		if (!(std::cin >> vertex)) break;
		std::cout << "Connected to: ";
		for (unsigned i = 0; i < vertices; i++)
			if (adjacency(vertex, i))
				std::cout << i << ' ';
		std::cout << "\nReachable from: ";
		for (unsigned i = 0; i < vertices; i++)
			if (adjacency(i, vertex))
				std::cout << i << ' ';
	} while (true);
}