Graph-processing code in C++.

graphs.cpp

class Graph
{
public:
	
	using size_t = std::size_t;
	
	using vertex_t = std::size_t;
	
	struct Edge { vertex_t vertex; size_t id; };
	
	using adjacent_t = std::vector<Edge>;
	
	using component_t = std::vector<vertex_t>;

	using container_t = std::vector<adjacent_t>;
	
	Graph(size_t vertices)
	: _edges(0)
	, _vertices(vertices)
	{ }
	
	container_t::const_iterator begin() const
	{
		return _vertices.begin();
	}
	
	container_t::const_iterator end() const
	{
		return _vertices.end();
	}
	
	vertex_t add_vertex()
	{
		_vertices.push_back({});
		
		return _vertices.size() - 1;
	}
	
	void add_edge(vertex_t first, vertex_t second)
	{
		_vertices[first].push_back({second, _edges});
		
		if (first != second)
		{
			_vertices[second].push_back({first, _edges});
		}
		
		++_edges;
	}
	
	const adjacent_t& adjacent(vertex_t vertex) const
	{
		return _vertices[vertex];
	}
	
	const adjacent_t& operator[](vertex_t vertex) const
	{
		return _vertices[vertex];
	}
	
	size_t vertex_number() const
	{
		return _vertices.size();
	}
	
	size_t edge_number() const
	{
		return _edges;
	}
	
private:
	
	size_t _edges;
	
	container_t _vertices;
};

class Components
{
public:
	
	using id_t = std::size_t;
	
	using vertex_t = Graph::vertex_t;
	
	using component_t = Graph::component_t;
	
	using iterator = std::vector<component_t>::const_iterator;
	
	Components(const Graph& graph)
	: _ids(graph.vertex_number())
	{
		id_t id = 0;
		
		std::vector<bool> visited(graph.vertex_number());
		
		for (vertex_t vertex = 0; vertex < graph.vertex_number(); ++vertex)
		{
			if (! visited[vertex])
			{
				component_t component;
				
				_set_ids(graph, vertex, id++, component, visited);
				
				_components.push_back(component);
			}
		}
	}
	
	iterator begin() const
	{
		return _components.begin();
	}
	
	iterator end() const
	{
		return _components.end();
	}
	
	bool connected(vertex_t first, vertex_t second) const
	{
		_assert_vertex_in_range(first);
		_assert_vertex_in_range(second);
		
		return _ids.at(first) == _ids.at(second);
	}
	
	const std::vector<component_t>& components() const
	{
		return _components;
	}
	
	const component_t& operator[](size_t index) const
	{
		return _components[index];
	}
	
	id_t count() const
	{
		return _components.size();
	}
	
	id_t id(vertex_t vertex) const
	{
		return _ids[vertex];
	}
	
private:
	
	using bitset_t = std::vector<bool>;
	
	void _assert_vertex_in_range(vertex_t vertex) const
	{
		if (vertex >= _ids.size())
		{
			throw std::invalid_argument("Vertex index out of range!");
		}
	}
	
	void _set_ids(const Graph& graph,
				  vertex_t vertex,
				  id_t id,
				  component_t& component,
				  bitset_t& visited)
	{
		if (visited[vertex]) return;
		
		visited[vertex] = true;
		
		_ids[vertex] = id;
		
		component.push_back(vertex);
		
		for (const auto& adjacent : graph[vertex])
		{
			_set_ids(graph, adjacent.vertex, id, component, visited);
		}
	}
	
	std::vector<id_t> _ids;
	
	std::vector<component_t> _components;
};

class GraphOperations
{
public:
	
	using size_t = Graph::size_t;
	
	using vertex_t = Graph::vertex_t;
	
	using adjacent_t = Graph::adjacent_t;
	
	using component_t = Graph::component_t;
	
	using predicate_t = std::function<bool(vertex_t)>;
	
	
	static size_t degree(const Graph& graph, vertex_t vertex)
	{
		return graph[vertex].size();
	}
	
	static size_t max_degree(const Graph& graph)
	{
		size_t max = 0;
		
		for (const auto& v : graph) max = std::max(v.size(), max);
		
		return max;
	}
	
	static double average_degree(const Graph& graph)
	{
		return (graph.edge_number() * 2.0) / graph.vertex_number();
	}
	
	static size_t self_loops_number(const Graph& graph)
	{
		size_t count = 0;
		
		for (size_t vertex = 0; vertex < graph.vertex_number(); ++vertex)
		{
			count += std::count_if(graph[vertex].begin(),
								   graph[vertex].end(),
								   [&] (const Graph::Edge& edge)
								   {
									   return edge.vertex == vertex;
								   });
		}
		
		return count;
	}
	
	static bool is_connected(const Graph& graph,
							 vertex_t vertex,
							 vertex_t target)
	{
		bitset_t visited(graph.vertex_number());
		
		return _is_connected(graph, vertex, target, visited);
	}
	
	static size_t shortest_distance(const Graph& graph,
									 vertex_t vertex,
									 vertex_t target)
	{
		if (vertex == target) return 0;
		
		bitset_t visited(graph.vertex_number());
		
		queue_t queue;
		
		queue.push(vertex);
		
		size_t distance = 0;
		
		vertex_t last_of_level = vertex;
		
		while (! queue.empty())
		{
			vertex = queue.front();
			
			queue.pop();
			
			if (visited[vertex]) continue;
			
			if (vertex == target) break;
			
			visited[vertex] = true;
			
			for (const auto& adjacent : graph[vertex])
			{
				if (! visited[adjacent.vertex])
				{
					queue.push(adjacent.vertex);
				}
			}
			
			if (vertex == last_of_level)
			{
				++distance;
				
				last_of_level = queue.back();
			}
		}
		
		if (queue.empty())
		{
			throw std::invalid_argument("No connection between "
										"the given vertex and target!");
		}
		
		return distance;
	}
	
	static component_t shortest_path(const Graph& graph,
							  vertex_t vertex,
							  vertex_t target)
	{
		if (vertex == target) return {};
		
		size_t vertex_number = graph.vertex_number();
		
		bitset_t visited(vertex_number, false);
		
		queue_t queue;
		
		queue.push(vertex);
		
		std::vector<vertex_t> source(vertex_number);
		
		size_t distance = 0;
		
		vertex_t last_of_level = vertex;
		
		while (! queue.empty())
		{
			auto old_vertex = vertex;
			
			vertex = queue.front();
			
			queue.pop();
			
			if (visited[vertex]) continue;
			
			source[vertex] = old_vertex;
			
			if (vertex == target) break;
			
			visited[vertex] = true;
			
			for (const auto& adjacent : graph[vertex])
			{
				if (! visited[adjacent.vertex])
				{
					queue.push(adjacent.vertex);
				}
			}
			
			if (vertex == last_of_level)
			{
				++distance;
				
				last_of_level = queue.back();
			}
		}
		
		component_t path(1 + distance);
		
		for (long v = distance; v >= 0; --v)
		{
			path[v] = vertex;
			
			vertex = source[vertex];
		}
	
		return path;
	}
	
	static bool is_bipartite(const Graph& graph,
					  const predicate_t& predicate)
	{
		Components connected_components(graph);
		
		for (const auto& component : connected_components)
		{
			vertex_t vertex = component[0];
			
			bitset_t visited(graph.edge_number(), false);
			
			if (! _is_bipartite(graph,
								vertex,
								! predicate(vertex),
								predicate,
								visited))
			{
				return false;
			}
		}
		
		return true;
	}
	
	static bool euler_tour_possible(const Graph& graph)
	{
		Components connected_components(graph);
		
		if (connected_components.count() > 1) return false;
		
		for (vertex_t vertex = 0; vertex < graph.vertex_number(); ++vertex)
		{
			if (degree(graph, vertex) % 2 != 0) return false;
		}
		
		return true;
	}
	
	static component_t euler_tour(const Graph& graph)
	{
		if (! euler_tour_possible(graph))
		{
			throw std::invalid_argument("Euler tour is not possible "
										"for this graph!");
		}
		
		component_t path(graph.edge_number() + 1);
		
		bitset_t visited(graph.edge_number(), false);
		
		_euler_tour(graph, visited, path);
		
		return path;
	}
	
private:
	
	using bitset_t = std::vector<bool>;
	
	using queue_t = std::queue<vertex_t>;
	
	static bool _euler_tour(const Graph& graph,
							bitset_t& visited,
							component_t& path,
							vertex_t vertex = 0,
							id_t edge_count = 0)
	{
		if (edge_count == graph.edge_number())
		{
			path[edge_count] = vertex;
			
			return true;
		}
		
		for (const auto& adjacent : graph[vertex])
		{
			if (! visited[adjacent.id])
			{
				bitset_t copy = visited;
				
				copy[adjacent.id] = true;
				
				if (_euler_tour(graph,
								copy,
								path,
								adjacent.vertex,
								edge_count + 1))
				{
					path[edge_count] = vertex;
					
					return true;
				}
			}
		}
		
		return false;
	}
	
	static bool _is_bipartite(const Graph& graph,
							  vertex_t vertex,
							  bool was,
							  const predicate_t& predicate,
							  bitset_t& visited)
	{
		bool is = predicate(vertex);
		
		if (is == was) return false;
		
		for (const auto& adjacent : graph[vertex])
		{
			if (! visited[adjacent.id])
			{
				visited[adjacent.id] = true;
				
				if (! _is_bipartite(graph,
									adjacent.vertex,
									is,
									predicate,
									visited))
				{
					return false;
				}
			}
		}
		
		return true;
	}
	
	static bool _is_connected(const Graph& graph,
							  vertex_t vertex,
							  vertex_t target,
							  bitset_t& visited)
	{
		if (visited[vertex]) return false;
		
		if (vertex == target) return true;
		
		visited[vertex] = true;
		
		for (const auto& adjacent : graph[vertex])
		{
			if (_is_connected(graph, adjacent.vertex, target, visited))
			{
				return true;
			}
		}
		
		return false;
	}
};



int main(int argc, char* argv[])
{
	Graph graph(5);
	
	graph.add_edge(0, 1);
	
	graph.add_edge(1, 2);
	graph.add_edge(2, 1);
	
	graph.add_edge(2, 3);
	graph.add_edge(3, 2);
	
	graph.add_edge(3, 0);
	
	graph.add_edge(1, 4);
	graph.add_edge(4, 3);
	
	print::booleans();
	
	if (GraphOperations::euler_tour_possible(graph))
	{
		for (const auto& edge : GraphOperations::euler_tour(graph))
		{
			print::ln(edge);
		}
	}
	
	else print::ln("Euler tour not possible!");
}